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