fera_graph/
unionfind.rs

1// This Source Code Form is subject to the terms of the Mozilla Public
2// License, v. 2.0. If a copy of the MPL was not distributed with this
3// file, You can obtain one at http://mozilla.org/MPL/2.0/.
4
5//! Union-find ([disjoint-set]) data structure.
6//!
7//! [disjoint-set]: https://en.wikipedia.org/wiki/Disjoint-set_data_structure
8use params::{Owned, ParamDerefMut};
9use prelude::*;
10
11use fera_fun::first;
12use fera_unionfind::UnionFind as InnerUnionFind;
13
14// FIXME: only union and reset should need &mut self
15
16pub struct UnionFind<G: Graph> {
17    inner: InnerUnionFind<
18        Vertex<G>,
19        DefaultVertexPropMut<G, Vertex<G>>,
20        DefaultVertexPropMut<G, usize>,
21    >,
22}
23
24impl<G: Graph> UnionFind<G> {
25    #[inline]
26    pub fn union(&mut self, u: Vertex<G>, v: Vertex<G>) {
27        self.inner.union(u, v)
28    }
29
30    #[inline]
31    pub fn in_same_set(&mut self, u: Vertex<G>, v: Vertex<G>) -> bool {
32        self.inner.in_same_set(u, v)
33    }
34
35    #[inline]
36    pub fn find_set(&mut self, v: Vertex<G>) -> Vertex<G> {
37        self.inner.find_set(v)
38    }
39
40    #[inline]
41    pub fn num_sets(&self) -> usize {
42        self.inner.num_sets()
43    }
44
45    pub fn reset(&mut self, g: &G) {
46        for v in g.vertices() {
47            self.inner.make_set(v)
48        }
49    }
50}
51
52pub trait WithUnionFind: Graph {
53    fn new_unionfind(&self) -> UnionFind<Self> {
54        // FIXME: do not work with null graphs
55        let v = first(self.vertices());
56        let mut parent = self.default_vertex_prop(v);
57        for v in self.vertices() {
58            parent[v] = v;
59        }
60        UnionFind {
61            inner: InnerUnionFind::with_parent_rank_num_sets(
62                parent,
63                self.vertex_prop(0),
64                self.num_vertices(),
65            ),
66        }
67    }
68}
69
70impl<G: Graph> WithUnionFind for G {}
71
72pub struct NewUnionFind<'a, G: 'a>(pub &'a G);
73
74impl<'a, G: 'a + WithUnionFind> ParamDerefMut for NewUnionFind<'a, G> {
75    type Target = UnionFind<G>;
76    type Output = Owned<UnionFind<G>>;
77
78    fn build(self) -> Self::Output {
79        Owned(self.0.new_unionfind())
80    }
81}
82
83#[cfg(test)]
84mod tests {
85    use super::{UnionFind, WithUnionFind};
86    use fera_fun::vec;
87    use prelude::*;
88
89    fn check_groups(
90        ds: &mut UnionFind<StaticGraph>,
91        num_sets: usize,
92        groups: &[&[Vertex<StaticGraph>]],
93    ) {
94        assert_eq!(num_sets, ds.num_sets());
95        for group in groups {
96            for &a in *group {
97                assert!(ds.in_same_set(group[0], a));
98            }
99        }
100    }
101
102    #[test]
103    fn unionfind() {
104        let g: StaticGraph = graph!(5);
105        let v = vec(g.vertices());
106        let mut ds = g.new_unionfind();
107        assert_eq!(5, ds.num_sets());
108        ds.union(v[0], v[2]);
109        check_groups(&mut ds, 4, &[&[v[0], v[2]]]);
110        ds.union(v[1], v[3]);
111        check_groups(&mut ds, 3, &[&[v[0], v[2]], &[v[1], v[3]]]);
112        ds.union(v[2], v[4]);
113        check_groups(&mut ds, 2, &[&[v[0], v[2], v[4]], &[v[1], v[3]]]);
114        ds.union(v[3], v[4]);
115        check_groups(&mut ds, 1, &[&[v[0], v[2], v[4], v[1], v[3]]]);
116    }
117}
fera_graph/unionfind.rs

fera_graph/
unionfind.rs
