graph_tools/
lib.rs

1pub mod union_find;
2pub mod tricnt;
3pub mod csr;
4pub mod heap;
5pub mod slashburn;
6pub mod csbv;
7
8
9#[cfg(test)]
10mod test{
11    use super::*;
12
13    #[test]
14    fn test_tri_csbv(){
15        let edges = vec![(1, 37), (1,40), (1,68), (37, 40), (37,68), (37,75), (40, 68), (40, 75)];
16        let n_nodes = 76;
17
18        let graph = csbv::CSBV::from_sorted_edges(&edges, n_nodes);
19
20        let cnt = tricnt::csbv::count(&graph);
21        assert_eq!(cnt, 5);
22    }
23
24    #[test]
25    fn test_tri_csr(){
26        let edges = vec![(1, 37), (1,40), (1,68), (37, 40), (37,68), (37,75), (40, 68), (40, 75)];
27        let n_nodes = 76;
28
29        let graph = csr::CSR::from_sorted_edges(&edges, n_nodes);
30
31        let cnt = tricnt::csr::count(&graph);
32        assert_eq!(cnt, 5);
33    }
34
35    
36    #[test]
37    fn test_csbv(){
38
39        let edges = vec![(0,1), (0, 10), (0, 50), (0, 64), (0, 127), (3, 64), (3, 127)];
40        let n_nodes = 128;
41
42        let graph = csbv::CSBV::from_sorted_edges(&edges, n_nodes);
43
44        assert_eq!(graph.bit_blocks, vec![1125899906843650, 9223372036854775809, 9223372036854775809]);
45        assert_eq!(graph.block_ids, vec![0,1,1]);
46        assert_eq!(graph.ptrs, vec![0, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
47            3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
48            3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
49            3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
50            3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]);
51
52        assert_eq!(graph.neighbor_iter(0).collect::<Vec<usize>>(), vec![1,10,50,64,127]);
53        assert_eq!(graph.neighbor_iter(3).collect::<Vec<usize>>(), vec![64,127]);
54
55        assert_eq!(graph.block_iter(0).collect::<Vec<(usize, usize)>>(), vec![(0, 1125899906843650), (1, 9223372036854775809)]);
56        assert_eq!(graph.block_iter(3).collect::<Vec<(usize, usize)>>(), vec![(1, 9223372036854775809)]);
57
58    }
59
60    #[test]
61    fn test_heap(){
62        let priorities = vec![6usize,3,7,1,9,5,4,8];
63        let mut indices : Vec<usize> = (0..priorities.len()).collect();
64
65        heap::heapify_indices(&mut indices, &priorities);
66        heap::sort_heap_indices(&mut indices, &priorities);
67        
68        let sorted_priorities : Vec<usize> = indices.iter().map(|x| priorities[*x]).collect();
69        let mut true_sorted_priorities = priorities.clone();
70        true_sorted_priorities.sort_by(|a, b| b.cmp(a));
71        
72        assert_eq!(sorted_priorities, true_sorted_priorities);
73    }
74
75    #[test]
76    fn test_csr_edge_iterator(){
77        let edges = vec![(1usize,3usize), (1,4), (1,5), (4,5)];
78        let n_nodes = 6;
79        let graph = csr::CSR::from_edges(&edges, n_nodes);
80        
81        let mut true_edges = vec![];
82        for (u, v) in &edges {
83            true_edges.push( (*u, *v) );
84            true_edges.push( (*v, *u) );
85        }
86
87        let mut edges_from_iter : Vec<(usize, usize)> = graph.iter_edges().collect();
88
89        true_edges.sort();
90        edges_from_iter.sort();
91
92        assert_eq!(true_edges, edges_from_iter);
93    }
94
95    #[test]
96    fn test_csr(){
97        let edges = vec![(1usize, 3usize), (3, 8), (3, 7),
98                         (8, 9), (0, 4), (0, 2),
99                         (0, 5), (2, 4), (4, 5), (5, 6)];
100        
101        let n_nodes = 10;
102        let graph = csr::CSR::from_edges(&edges, n_nodes);
103        
104        //check degrees
105        let true_degrees = [3,1,2,3,3,3,1,1,2,1];
106
107        for n in 0..n_nodes{
108            assert_eq!(graph.degree(n), true_degrees[n]);
109        }
110
111        //check neighbors
112        let true_neighbors = [vec![2,4,5],vec![3],vec![0,4],vec![1,7,8],
113                            vec![0,2,5],vec![0,4,6],vec![5],vec![3],vec![3,9],vec![8]];
114        
115        for n in 0..n_nodes{
116            let mut neighbors : Vec<usize> = vec![0; graph.degree(n)];
117            neighbors.clone_from_slice(graph.neighbors(n));
118            neighbors.sort();
119            assert_eq!(neighbors, true_neighbors[n]);
120        }
121    }
122
123    #[test]
124    fn test_tri(){
125        let adj = vec![
126            vec![2,4,5],
127            vec![3],
128            vec![4,5],
129            vec![7,8],
130            vec![5],
131            vec![6],
132            vec![],
133            vec![],
134            vec![9],
135            vec![]
136            ];
137        
138        let cnt = tricnt::count_total(adj);
139        assert_eq!(cnt, 4);
140    }
141
142    #[test]
143    fn test_uf(){
144        let mut uf = union_find::UnionFind::new(10);
145        
146        let edges = vec![(1usize, 3usize), (3, 7), (3, 8),
147                         (8, 9), (0, 2), (0, 4),
148                         (0, 5), (2, 4), (4, 5), (5, 6)];
149        
150        for (u, v) in &edges{
151            uf.union(*u, *v);
152        }
153        
154        assert_eq!(uf.n_components(), 2);
155        assert_eq!(uf.n_nodes(), 10);
156        
157        let true_ccs = vec![vec![1usize,3,7,8,9], vec![0usize,2,4,5,6]];
158
159        // test if ccs are correctly found
160        for cc in &true_ccs {
161            cc.iter().reduce(|accum, item| {
162                assert_eq!(uf.find(*accum), uf.find(*item));
163                return accum;
164            });
165        }
166
167        // test if nodes in different ccs are identified.
168        for u in &true_ccs[0]{
169            for v in &true_ccs[1]{
170                assert_ne!(uf.find(*u), uf.find(*v));
171            }
172        }
173    }
174}
graph_tools/lib.rs

graph_tools/
lib.rs
