1 extern crate itertools;
2 extern crate petgraph;
3 #[macro_use]
4 extern crate defmac;
5 
6 use petgraph::adj::DefaultIx;
7 use petgraph::adj::IndexType;
8 use petgraph::adj::{List, UnweightedList};
9 use petgraph::algo::tarjan_scc;
10 use petgraph::data::{DataMap, DataMapMut};
11 use petgraph::dot::Dot;
12 use petgraph::prelude::*;
13 use petgraph::visit::{
14     IntoEdgeReferences, IntoEdges, IntoNeighbors, IntoNodeReferences, NodeCount, NodeIndexable,
15 };
16 
17 use itertools::assert_equal;
18 
n(x: u32) -> DefaultIx19 fn n(x: u32) -> DefaultIx {
20     DefaultIx::new(x as _)
21 }
22 
23 #[test]
node_indices()24 fn node_indices() {
25     let mut g = List::<()>::new();
26     let a = g.add_node();
27     let b = g.add_node();
28     let c = g.add_node();
29     let mut iter = g.node_indices();
30     assert_eq!(iter.next(), Some(a));
31     assert_eq!(iter.next(), Some(b));
32     assert_eq!(iter.next(), Some(c));
33     assert_eq!(iter.next(), None);
34 }
35 
test_node_count<E>(g: &List<E>, n: usize)36 fn test_node_count<E>(g: &List<E>, n: usize) {
37     assert_eq!(n, g.node_count());
38     assert_eq!(g.node_bound(), n);
39     assert_eq!(g.node_indices().count(), n);
40     assert_eq!(g.node_indices().len(), n);
41     assert_eq!(g.node_references().count(), n);
42     assert_eq!(g.node_references().len(), n);
43 }
44 
45 #[test]
node_bound()46 fn node_bound() {
47     let mut g = List::<()>::new();
48     test_node_count(&g, 0);
49     for i in 0..10 {
50         g.add_node();
51         test_node_count(&g, i + 1);
52     }
53     g.clear();
54     test_node_count(&g, 0);
55 }
56 
assert_sccs_eq<Ix: IndexType>(mut res: Vec<Vec<Ix>>, normalized: Vec<Vec<Ix>>)57 fn assert_sccs_eq<Ix: IndexType>(mut res: Vec<Vec<Ix>>, normalized: Vec<Vec<Ix>>) {
58     // normalize the result and compare with the answer.
59     for scc in &mut res {
60         scc.sort();
61     }
62     // sort by minimum element
63     res.sort_by(|v, w| v[0].cmp(&w[0]));
64     assert_eq!(res, normalized);
65 }
66 
scc_graph() -> UnweightedList<DefaultIx>67 fn scc_graph() -> UnweightedList<DefaultIx> {
68     let mut gr = List::new();
69     for _ in 0..9 {
70         gr.add_node();
71     }
72     for (a, b) in &[
73         (6, 0),
74         (0, 3),
75         (3, 6),
76         (8, 6),
77         (8, 2),
78         (2, 5),
79         (5, 8),
80         (7, 5),
81         (1, 7),
82     ] {
83         gr.add_edge(n(*a), n(*b), ());
84     }
85     // make an identical replacement of n(4) and leave a hole
86     let x = gr.add_node();
87     gr.add_edge(n(7), x, ());
88     gr.add_edge(x, n(1), ());
89     gr
90 }
91 
92 #[test]
test_tarjan_scc()93 fn test_tarjan_scc() {
94     let gr = scc_graph();
95 
96     let x = n(gr.node_bound() as u32 - 1);
97     assert_sccs_eq(
98         tarjan_scc(&gr),
99         vec![
100             vec![n(0), n(3), n(6)],
101             vec![n(1), n(7), x],
102             vec![n(2), n(5), n(8)],
103             vec![n(4)],
104         ],
105     );
106 }
107 
make_graph() -> List<i32>108 fn make_graph() -> List<i32> {
109     let mut gr = List::new();
110     let mut c = 0..;
111     let mut e = || -> i32 { c.next().unwrap() };
112     for _ in 0..=9 {
113         gr.add_node();
114     }
115     for &(from, to) in &[
116         (6, 0),
117         (0, 3),
118         (3, 6),
119         (8, 6),
120         (8, 2),
121         (2, 5),
122         (5, 8),
123         (7, 5),
124         (1, 7),
125         (7, 9),
126         (8, 6), // parallel edge
127         (9, 1),
128         (9, 9),
129         (9, 9),
130     ] {
131         gr.add_edge(n(from), n(to), e());
132     }
133     gr
134 }
135 
136 defmac!(edges ref gr, x => gr.edges(x).map(|r| (r.target(), *r.weight())));
137 
138 #[test]
test_edges_directed()139 fn test_edges_directed() {
140     let gr = make_graph();
141     dbg!(&gr);
142     let x = n(9);
143     assert_equal(edges!(&gr, x), vec![(1, 11), (x, 12), (x, 13)]);
144     assert_equal(edges!(&gr, n(0)), vec![(n(3), 1)]);
145     //assert_equal(edges!(&gr, n(4)), vec![]);
146 }
147 
148 #[test]
test_edge_references()149 fn test_edge_references() {
150     let mut gr = make_graph();
151     assert_eq!(gr.edge_count(), gr.edge_references().count());
152     for i in gr.edge_references() {
153         assert_eq!(gr.edge_endpoints(i.id()), Some((i.source(), i.target())));
154         assert_eq!(gr.edge_weight(i.id()), Some(i.weight()));
155     }
156     for n in gr.node_indices() {
157         for e in gr.edge_indices_from(n) {
158             match gr.edge_weight_mut(e) {
159                 None => {}
160                 Some(r) => {
161                     *r = 1;
162                 }
163             }
164         }
165     }
166     for i in gr.edge_references() {
167         assert_eq!(*i.weight(), 1);
168     }
169 }
170 
171 #[test]
test_edge_iterators()172 fn test_edge_iterators() {
173     let gr = make_graph();
174     for i in gr.node_indices() {
175         itertools::assert_equal(
176             gr.neighbors(n(i)),
177             gr.edges(n(i)).map(|r| {
178                 assert_eq!(r.source(), n(i));
179                 r.target()
180             }),
181         );
182     }
183 }
184 
185 #[test]
186 #[should_panic(expected = "is not a valid node")]
add_edge_vacant()187 fn add_edge_vacant() {
188     let mut g = List::new();
189     let a: DefaultIx = g.add_node();
190     let b = g.add_node();
191     let _ = g.add_node();
192     g.clear();
193     g.add_edge(a, b, 1);
194 }
195 
196 #[test]
197 #[should_panic(expected = "is not a valid node")]
add_edge_oob()198 fn add_edge_oob() {
199     let mut g = List::new();
200     let a = g.add_node();
201     let _ = g.add_node();
202     let _ = g.add_node();
203     g.add_edge(a, n(4), 1);
204 }
205 
206 #[test]
207 #[should_panic(expected = "index out of bounds")]
add_edge_oob_2()208 fn add_edge_oob_2() {
209     let mut g = List::new();
210     let a = g.add_node();
211     let _ = g.add_node();
212     let _ = g.add_node();
213     g.add_edge(n(4), a, 1);
214 }
215 
216 #[test]
test_node_references()217 fn test_node_references() {
218     let gr = scc_graph();
219 
220     itertools::assert_equal(gr.node_references(), gr.node_indices());
221 }
222 
223 #[test]
iterators_undir()224 fn iterators_undir() {
225     let mut g = List::with_capacity(2);
226     let a = g.add_node();
227     let b = g.add_node();
228     let c = g.add_node();
229     let d = g.add_node();
230     for &(from, to, w) in &[(a, b, 1), (a, c, 2), (b, c, 3), (c, c, 4), (a, d, 5)] {
231         g.add_edge(n(from), n(to), w);
232     }
233 
234     itertools::assert_equal(g.neighbors(a), vec![b, c, d]);
235     itertools::assert_equal(g.neighbors(c), vec![c]);
236     itertools::assert_equal(g.neighbors(d), vec![]);
237 
238     itertools::assert_equal(g.neighbors(b), vec![c]);
239 }
240 
241 #[test]
dot()242 fn dot() {
243     let mut gr = List::new();
244     let a: DefaultIx = gr.add_node();
245     let b = gr.add_node();
246     gr.add_edge(a, a, 10u8);
247     gr.add_edge(a, b, 20);
248     let dot_output = format!("{:?}", Dot::new(&gr));
249     assert_eq!(
250         dot_output,
251         r#"digraph {
252     0 [ label = "()" ]
253     1 [ label = "()" ]
254     0 -> 0 [ label = "10" ]
255     0 -> 1 [ label = "20" ]
256 }
257 "#
258     );
259 }
260