1 extern crate petgraph;
2 extern crate rand;
3 
4 use petgraph::unionfind::UnionFind;
5 use rand::{thread_rng, ChaChaRng, Rng, SeedableRng};
6 use std::collections::HashSet;
7 
8 #[test]
uf_test()9 fn uf_test() {
10     let n = 8;
11     let mut u = UnionFind::new(n);
12     for i in 0..n {
13         assert_eq!(u.find(i), i);
14         assert_eq!(u.find_mut(i), i);
15         assert!(!u.union(i, i));
16     }
17 
18     u.union(0, 1);
19     assert_eq!(u.find(0), u.find(1));
20     u.union(1, 3);
21     u.union(1, 4);
22     u.union(4, 7);
23     assert_eq!(u.find(0), u.find(3));
24     assert_eq!(u.find(1), u.find(3));
25     assert!(u.find(0) != u.find(2));
26     assert_eq!(u.find(7), u.find(0));
27     u.union(5, 6);
28     assert_eq!(u.find(6), u.find(5));
29     assert!(u.find(6) != u.find(7));
30 
31     // check that there are now 3 disjoint sets
32     let set = (0..n).map(|i| u.find(i)).collect::<HashSet<_>>();
33     assert_eq!(set.len(), 3);
34 }
35 
36 #[test]
uf_test_with_equiv()37 fn uf_test_with_equiv() {
38     let n = 8;
39     let mut u = UnionFind::new(n);
40     for i in 0..n {
41         assert_eq!(u.find(i), i);
42         assert_eq!(u.find_mut(i), i);
43         assert!(u.equiv(i, i));
44     }
45 
46     u.union(0, 1);
47     assert!(u.equiv(0, 1));
48     u.union(1, 3);
49     u.union(1, 4);
50     u.union(4, 7);
51     assert!(u.equiv(0, 7));
52     assert!(u.equiv(1, 3));
53     assert!(!u.equiv(0, 2));
54     assert!(u.equiv(7, 0));
55     u.union(5, 6);
56     assert!(u.equiv(6, 5));
57     assert!(!u.equiv(6, 7));
58 
59     // check that there are now 3 disjoint sets
60     let set = (0..n).map(|i| u.find(i)).collect::<HashSet<_>>();
61     assert_eq!(set.len(), 3);
62 }
63 
64 #[test]
uf_rand()65 fn uf_rand() {
66     let n = 1 << 14;
67     let mut rng = ChaChaRng::from_rng(thread_rng()).unwrap();
68     let mut u = UnionFind::new(n);
69     for _ in 0..100 {
70         let a = rng.gen_range(0, n);
71         let b = rng.gen_range(0, n);
72         let ar = u.find(a);
73         let br = u.find(b);
74         assert_eq!(ar != br, u.union(a, b));
75     }
76 }
77 
78 #[test]
uf_u8()79 fn uf_u8() {
80     let n = 256;
81     let mut rng = ChaChaRng::from_rng(thread_rng()).unwrap();
82     let mut u = UnionFind::<u8>::new(n);
83     for _ in 0..(n * 8) {
84         let a = rng.gen();
85         let b = rng.gen();
86         let ar = u.find(a);
87         let br = u.find(b);
88         assert_eq!(ar != br, u.union(a, b));
89     }
90 }
91 
92 #[test]
labeling()93 fn labeling() {
94     let mut u = UnionFind::<u32>::new(48);
95     for i in 0..24 {
96         u.union(i + 1, i);
97     }
98     for i in 25..47 {
99         u.union(i, i + 1);
100     }
101     u.union(23, 25);
102     u.union(24, 23);
103     let v = u.into_labeling();
104     assert!(v.iter().all(|x| *x == v[0]));
105 }
106