toolbox_rs/
union_find.rs

1use std::cmp::Ordering;
2
3pub struct UnionFind {
4    number_of_sets: usize,
5    parent: Vec<usize>,
6    rank: Vec<usize>,
7}
8
9impl UnionFind {
10    pub fn new(max: usize) -> Self {
11        Self {
12            number_of_sets: max,
13            parent: (0..max).collect(),
14            rank: vec![0; max],
15        }
16    }
17
18    pub fn len(&self) -> usize {
19        self.parent.len()
20    }
21
22    pub fn is_empty(&self) -> bool {
23        self.len() == 0
24    }
25
26    // union of two sets represented by x and y.
27    pub fn union(&mut self, x: usize, y: usize) {
28        let x_set = self.find(x);
29        let y_set = self.find(y);
30
31        if x_set == y_set {
32            return;
33        }
34
35        // merge lower ranked set with higher ranked set
36        match self.rank[x_set].cmp(&self.rank[y_set]) {
37            Ordering::Less => {
38                self.parent[x_set] = y_set;
39            }
40            Ordering::Greater => {
41                self.parent[y_set] = x_set;
42            }
43            Ordering::Equal => {
44                self.parent[y_set] = x_set;
45                self.rank[x_set] += 1;
46            }
47        }
48
49        self.number_of_sets -= 1;
50    }
51
52    // find the representative of the set that x is an element of
53    pub fn find(&mut self, x: usize) -> usize {
54        let mut p = x;
55        while self.parent[p] != p {
56            // lazy path compression, set every node to it's parent
57            self.parent[p] = self.parent[self.parent[p]];
58            p = self.parent[p];
59        }
60        p
61    }
62
63    pub fn number_of_sets(&self) -> usize {
64        self.number_of_sets
65    }
66}
67
68#[cfg(test)]
69mod tests {
70
71    use crate::union_find::UnionFind;
72
73    #[test]
74    fn default_all_self_parent() {
75        let mut uf = UnionFind::new(10);
76        assert!(!uf.is_empty());
77        assert_eq!(10, uf.len());
78        assert_eq!(10, uf.number_of_sets);
79        for i in 0..10_usize {
80            assert_eq!(i, uf.find(i));
81        }
82        assert_eq!(10, uf.number_of_sets);
83    }
84
85    #[test]
86    fn unions_in_a_row() {
87        let mut uf = UnionFind::new(10);
88        assert!(!uf.is_empty());
89        assert_eq!(10, uf.len());
90        assert_eq!(10, uf.number_of_sets);
91
92        for i in 0..10_usize {
93            uf.union(3, i);
94        }
95
96        for i in 0..10_usize {
97            // all elements are merged into the representative
98            assert_eq!(3, uf.find(i));
99        }
100
101        // check that all paths are compressed
102        assert_eq!(uf.parent, vec![3, 3, 3, 3, 3, 3, 3, 3, 3, 3]);
103
104        // check that all ranks are 0 except for item '3' it's 1
105        assert_eq!(uf.rank, vec![0, 0, 0, 1, 0, 0, 0, 0, 0, 0]);
106
107        // check that all sets have been merged into a single one
108        assert_eq!(1, uf.number_of_sets);
109    }
110
111    #[test]
112    fn test_number_of_sets() {
113        let mut uf = UnionFind::new(6);
114
115        // Initial state: 6 separate sets
116        assert_eq!(6, uf.number_of_sets());
117
118        // Unite elements 0 and 1 -> 5 sets
119        uf.union(0, 1);
120        assert_eq!(5, uf.number_of_sets());
121
122        // Unite elements 2 and 3 -> 4 sets
123        uf.union(2, 3);
124        assert_eq!(4, uf.number_of_sets());
125
126        // Unite elements 0 and 2 (merging two existing sets) -> 3 sets
127        uf.union(0, 2);
128        assert_eq!(3, uf.number_of_sets());
129
130        // Unite elements already in same set -> still 3 sets
131        uf.union(1, 3);
132        assert_eq!(3, uf.number_of_sets());
133
134        // Unite remaining elements
135        uf.union(4, 5);
136        assert_eq!(2, uf.number_of_sets());
137
138        uf.union(0, 4);
139        assert_eq!(1, uf.number_of_sets());
140    }
141}
toolbox_rs/union_find.rs

toolbox_rs/
union_find.rs
