1 #![cfg(feature = "stable_graph")]
2
3 extern crate itertools;
4 extern crate petgraph;
5 #[macro_use]
6 extern crate defmac;
7
8 use std::collections::HashSet;
9
10 use itertools::assert_equal;
11 use petgraph::algo::{kosaraju_scc, min_spanning_tree, tarjan_scc};
12 use petgraph::dot::Dot;
13 use petgraph::prelude::*;
14 use petgraph::stable_graph::edge_index as e;
15 use petgraph::stable_graph::node_index as n;
16 use petgraph::visit::{EdgeIndexable, IntoEdgeReferences, IntoNodeReferences, NodeIndexable};
17 use petgraph::EdgeType;
18
19 #[test]
node_indices()20 fn node_indices() {
21 let mut g = StableGraph::<_, ()>::new();
22 let a = g.add_node(0);
23 let b = g.add_node(1);
24 let c = g.add_node(2);
25 g.remove_node(b);
26 let mut iter = g.node_indices();
27 assert_eq!(iter.next(), Some(a));
28 assert_eq!(iter.next(), Some(c));
29 assert_eq!(iter.next(), None);
30 }
31
32 #[test]
node_bound()33 fn node_bound() {
34 let mut g = StableGraph::<_, ()>::new();
35 assert_eq!(g.node_bound(), g.node_count());
36 for i in 0..10 {
37 g.add_node(i);
38 assert_eq!(g.node_bound(), g.node_count());
39 }
40 let full_count = g.node_count();
41 g.remove_node(n(0));
42 g.remove_node(n(2));
43 assert_eq!(g.node_bound(), full_count);
44 g.clear();
45 assert_eq!(g.node_bound(), 0);
46 }
47
48 #[test]
edge_bound()49 fn edge_bound() {
50 let mut g = StableGraph::<_, _>::new();
51 assert_eq!(g.edge_bound(), g.edge_count());
52 for i in 0..10 {
53 g.add_node(i);
54 }
55 for i in 0..9 {
56 g.add_edge(n(i), n(i + 1), i);
57 assert_eq!(g.edge_bound(), g.edge_count());
58 }
59 let full_count = g.edge_count();
60 g.remove_edge(e(0));
61 g.remove_edge(e(2));
62 assert_eq!(g.edge_bound(), full_count);
63 g.clear();
64 assert_eq!(g.edge_bound(), 0);
65 }
66
67 #[test]
clear_edges()68 fn clear_edges() {
69 let mut gr = scc_graph();
70 gr.remove_node(n(1));
71 gr.clear_edges();
72 // check that we use the free list for the vacancies
73 assert_eq!(gr.add_node(()), n(1));
74 assert_eq!(gr.add_node(()), n(4));
75 assert!(gr.edge_references().next().is_none());
76 assert!(gr.node_indices().all(|i| gr.neighbors(i).next().is_none()));
77 }
78
assert_sccs_eq(mut res: Vec<Vec<NodeIndex>>, normalized: Vec<Vec<NodeIndex>>)79 fn assert_sccs_eq(mut res: Vec<Vec<NodeIndex>>, normalized: Vec<Vec<NodeIndex>>) {
80 // normalize the result and compare with the answer.
81 for scc in &mut res {
82 scc.sort();
83 }
84 // sort by minimum element
85 res.sort_by(|v, w| v[0].cmp(&w[0]));
86 assert_eq!(res, normalized);
87 }
88
scc_graph() -> StableGraph<(), ()>89 fn scc_graph() -> StableGraph<(), ()> {
90 let mut gr: StableGraph<(), ()> = StableGraph::from_edges(&[
91 (6, 0),
92 (0, 3),
93 (3, 6),
94 (8, 6),
95 (8, 2),
96 (2, 5),
97 (5, 8),
98 (7, 5),
99 (1, 7),
100 (7, 4),
101 (4, 1),
102 ]);
103 // make an identical replacement of n(4) and leave a hole
104 let x = gr.add_node(());
105 gr.add_edge(n(7), x, ());
106 gr.add_edge(x, n(1), ());
107 gr.remove_node(n(4));
108 gr
109 }
110
111 #[test]
test_scc()112 fn test_scc() {
113 let gr = scc_graph();
114 println!("{:?}", gr);
115
116 let x = n(gr.node_bound() - 1);
117 assert_sccs_eq(
118 kosaraju_scc(&gr),
119 vec![
120 vec![n(0), n(3), n(6)],
121 vec![n(1), n(7), x],
122 vec![n(2), n(5), n(8)],
123 ],
124 );
125 }
126
127 #[test]
test_tarjan_scc()128 fn test_tarjan_scc() {
129 let gr = scc_graph();
130
131 let x = n(gr.node_bound() - 1);
132 assert_sccs_eq(
133 tarjan_scc(&gr),
134 vec![
135 vec![n(0), n(3), n(6)],
136 vec![n(1), n(7), x],
137 vec![n(2), n(5), n(8)],
138 ],
139 );
140 }
141
make_graph<Ty>() -> StableGraph<(), i32, Ty> where Ty: EdgeType,142 fn make_graph<Ty>() -> StableGraph<(), i32, Ty>
143 where
144 Ty: EdgeType,
145 {
146 let mut gr = StableGraph::default();
147 let mut c = 0..;
148 let mut e = || -> i32 { c.next().unwrap() };
149 gr.extend_with_edges(&[
150 (6, 0, e()),
151 (0, 3, e()),
152 (3, 6, e()),
153 (8, 6, e()),
154 (8, 2, e()),
155 (2, 5, e()),
156 (5, 8, e()),
157 (7, 5, e()),
158 (1, 7, e()),
159 (7, 4, e()),
160 (8, 6, e()), // parallel edge
161 (4, 1, e()),
162 ]);
163 // make an identical replacement of n(4) and leave a hole
164 let x = gr.add_node(());
165 gr.add_edge(n(7), x, e());
166 gr.add_edge(x, n(1), e());
167 gr.add_edge(x, x, e()); // make two self loops
168 let rm_self_loop = gr.add_edge(x, x, e());
169 gr.add_edge(x, x, e());
170 gr.remove_node(n(4));
171 gr.remove_node(n(6));
172 gr.remove_edge(rm_self_loop);
173 gr
174 }
175
176 defmac!(edges ref gr, x => gr.edges(x).map(|r| (r.target(), *r.weight())));
177
178 #[test]
test_edges_directed()179 fn test_edges_directed() {
180 let gr = make_graph::<Directed>();
181 let x = n(9);
182 assert_equal(edges!(&gr, x), vec![(x, 16), (x, 14), (n(1), 13)]);
183 assert_equal(edges!(&gr, n(0)), vec![(n(3), 1)]);
184 assert_equal(edges!(&gr, n(4)), vec![]);
185 }
186
187 #[test]
test_edge_references()188 fn test_edge_references() {
189 let gr = make_graph::<Directed>();
190 assert_eq!(gr.edge_count(), gr.edge_references().count());
191 }
192
193 #[test]
test_edges_undirected()194 fn test_edges_undirected() {
195 let gr = make_graph::<Undirected>();
196 let x = n(9);
197 assert_equal(
198 edges!(&gr, x),
199 vec![(x, 16), (x, 14), (n(1), 13), (n(7), 12)],
200 );
201 assert_equal(edges!(&gr, n(0)), vec![(n(3), 1)]);
202 assert_equal(edges!(&gr, n(4)), vec![]);
203 }
204
205 #[test]
test_edge_iterators_directed()206 fn test_edge_iterators_directed() {
207 let gr = make_graph::<Directed>();
208 for i in gr.node_indices() {
209 itertools::assert_equal(gr.edges_directed(i, Outgoing), gr.edges(i));
210 for edge in gr.edges_directed(i, Outgoing) {
211 assert_eq!(
212 edge.source(),
213 i,
214 "outgoing edges should have a fixed source"
215 );
216 }
217 }
218 let mut incoming = vec![Vec::new(); gr.node_bound()];
219
220 for i in gr.node_indices() {
221 for j in gr.neighbors(i) {
222 incoming[j.index()].push(i);
223 }
224 }
225
226 println!("{:#?}", gr);
227 for i in gr.node_indices() {
228 itertools::assert_equal(
229 gr.edges_directed(i, Incoming).map(|e| e.source()),
230 incoming[i.index()].iter().rev().cloned(),
231 );
232 for edge in gr.edges_directed(i, Incoming) {
233 assert_eq!(
234 edge.target(),
235 i,
236 "incoming edges should have a fixed target"
237 );
238 }
239 }
240 }
241
242 #[test]
test_edge_iterators_undir()243 fn test_edge_iterators_undir() {
244 let gr = make_graph::<Undirected>();
245 for i in gr.node_indices() {
246 itertools::assert_equal(gr.edges_directed(i, Outgoing), gr.edges(i));
247 for edge in gr.edges_directed(i, Outgoing) {
248 assert_eq!(
249 edge.source(),
250 i,
251 "outgoing edges should have a fixed source"
252 );
253 }
254 }
255 for i in gr.node_indices() {
256 itertools::assert_equal(gr.edges_directed(i, Incoming), gr.edges(i));
257 for edge in gr.edges_directed(i, Incoming) {
258 assert_eq!(
259 edge.target(),
260 i,
261 "incoming edges should have a fixed target"
262 );
263 }
264 }
265 }
266
267 #[test]
268 #[should_panic(expected = "is not a node")]
add_edge_vacant()269 fn add_edge_vacant() {
270 let mut g = StableGraph::<_, _>::new();
271 let a = g.add_node(0);
272 let b = g.add_node(1);
273 let _ = g.add_node(2);
274 let _ = g.remove_node(b);
275 g.add_edge(a, b, 1);
276 }
277
278 #[test]
279 #[should_panic(expected = "is not a node")]
add_edge_oob()280 fn add_edge_oob() {
281 let mut g = StableGraph::<_, _>::new();
282 let a = g.add_node(0);
283 let _ = g.add_node(1);
284 let _ = g.add_node(2);
285 g.add_edge(a, n(4), 1);
286 }
287
288 #[test]
test_node_references()289 fn test_node_references() {
290 let gr = scc_graph();
291
292 itertools::assert_equal(gr.node_references().map(|(i, _)| i), gr.node_indices());
293 }
294
295 #[test]
iterators_undir()296 fn iterators_undir() {
297 let mut g = StableUnGraph::<_, _>::default();
298 let a = g.add_node(0);
299 let b = g.add_node(1);
300 let c = g.add_node(2);
301 let d = g.add_node(3);
302 g.extend_with_edges(&[(a, b, 1), (a, c, 2), (b, c, 3), (c, c, 4), (a, d, 5)]);
303 g.remove_node(b);
304
305 itertools::assert_equal(g.neighbors(a), vec![d, c]);
306 itertools::assert_equal(g.neighbors(c), vec![c, a]);
307 itertools::assert_equal(g.neighbors(d), vec![a]);
308
309 // the node that was removed
310 itertools::assert_equal(g.neighbors(b), vec![]);
311
312 // remove one more
313 g.remove_node(c);
314 itertools::assert_equal(g.neighbors(c), vec![]);
315 }
316
317 #[test]
iter_multi_edges()318 fn iter_multi_edges() {
319 let mut gr = StableGraph::new();
320 let a = gr.add_node("a");
321 let b = gr.add_node("b");
322 let c = gr.add_node("c");
323
324 let mut connecting_edges = HashSet::new();
325
326 gr.add_edge(a, a, ());
327 connecting_edges.insert(gr.add_edge(a, b, ()));
328 gr.add_edge(a, c, ());
329 gr.add_edge(c, b, ());
330 connecting_edges.insert(gr.add_edge(a, b, ()));
331 gr.add_edge(b, a, ());
332
333 let mut iter = gr.edges_connecting(a, b);
334
335 let edge_id = iter.next().unwrap().id();
336 assert!(connecting_edges.contains(&edge_id));
337 connecting_edges.remove(&edge_id);
338
339 let edge_id = iter.next().unwrap().id();
340 assert!(connecting_edges.contains(&edge_id));
341 connecting_edges.remove(&edge_id);
342
343 assert_eq!(None, iter.next());
344 assert!(connecting_edges.is_empty());
345 }
346
347 #[test]
iter_multi_undirected_edges()348 fn iter_multi_undirected_edges() {
349 let mut gr: StableUnGraph<_, _> = Default::default();
350 let a = gr.add_node("a");
351 let b = gr.add_node("b");
352 let c = gr.add_node("c");
353
354 let mut connecting_edges = HashSet::new();
355
356 gr.add_edge(a, a, ());
357 connecting_edges.insert(gr.add_edge(a, b, ()));
358 gr.add_edge(a, c, ());
359 gr.add_edge(c, b, ());
360 connecting_edges.insert(gr.add_edge(a, b, ()));
361 connecting_edges.insert(gr.add_edge(b, a, ()));
362
363 let mut iter = gr.edges_connecting(a, b);
364
365 let edge_id = iter.next().unwrap().id();
366 assert!(connecting_edges.contains(&edge_id));
367 connecting_edges.remove(&edge_id);
368
369 let edge_id = iter.next().unwrap().id();
370 assert!(connecting_edges.contains(&edge_id));
371 connecting_edges.remove(&edge_id);
372
373 let edge_id = iter.next().unwrap().id();
374 assert!(connecting_edges.contains(&edge_id));
375 connecting_edges.remove(&edge_id);
376
377 assert_eq!(None, iter.next());
378 assert!(connecting_edges.is_empty());
379 }
380
381 #[test]
dot()382 fn dot() {
383 let mut gr = StableGraph::new();
384 let a = gr.add_node("x");
385 let b = gr.add_node("y");
386 gr.add_edge(a, a, "10");
387 gr.add_edge(a, b, "20");
388 let dot_output = format!("{}", Dot::new(&gr));
389 assert_eq!(
390 dot_output,
391 r#"digraph {
392 0 [ label = "x" ]
393 1 [ label = "y" ]
394 0 -> 0 [ label = "10" ]
395 0 -> 1 [ label = "20" ]
396 }
397 "#
398 );
399 }
400
401 defmac!(iter_eq a, b => a.eq(b));
402 defmac!(nodes_eq ref a, ref b => a.node_references().eq(b.node_references()));
403 defmac!(edgew_eq ref a, ref b => a.edge_references().eq(b.edge_references()));
404 defmac!(edges_eq ref a, ref b =>
405 iter_eq!(
406 a.edge_references().map(|e| (e.source(), e.target())),
407 b.edge_references().map(|e| (e.source(), e.target()))));
408
409 #[test]
from()410 fn from() {
411 let mut gr1 = StableGraph::new();
412 let a = gr1.add_node(1);
413 let b = gr1.add_node(2);
414 let c = gr1.add_node(3);
415 gr1.add_edge(a, a, 10);
416 gr1.add_edge(a, b, 20);
417 gr1.add_edge(b, c, 30);
418 gr1.add_edge(a, c, 40);
419
420 let gr2 = Graph::from(gr1.clone());
421 let gr3 = StableGraph::from(gr2);
422 assert!(nodes_eq!(&gr1, &gr3));
423 assert!(edgew_eq!(&gr1, &gr3));
424 assert!(edges_eq!(&gr1, &gr3));
425
426 gr1.remove_node(b);
427
428 let gr4 = Graph::from(gr1);
429 let gr5 = StableGraph::from(gr4.clone());
430
431 let mut ans = StableGraph::new();
432 let a = ans.add_node(1);
433 let c = ans.add_node(3);
434 ans.add_edge(a, a, 10);
435 ans.add_edge(a, c, 40);
436
437 assert!(nodes_eq!(&gr4, &ans));
438 assert!(edges_eq!(&gr4, &ans));
439
440 assert!(nodes_eq!(&gr5, &ans));
441 assert!(edgew_eq!(&gr5, &ans));
442 assert!(edges_eq!(&gr5, &ans));
443 }
444
445 use petgraph::data::FromElements;
446 use petgraph::stable_graph::StableGraph;
447
448 #[test]
from_min_spanning_tree()449 fn from_min_spanning_tree() {
450 let mut g = StableGraph::new();
451 let mut nodes = Vec::new();
452 for _ in 0..6 {
453 nodes.push(g.add_node(()));
454 }
455 let es = [(4, 5), (3, 4), (3, 5)];
456 for &(a, b) in es.iter() {
457 g.add_edge(NodeIndex::new(a), NodeIndex::new(b), ());
458 }
459 for i in 0..3 {
460 let _ = g.remove_node(nodes[i]);
461 }
462 let _ = StableGraph::<(), (), Undirected, usize>::from_elements(min_spanning_tree(&g));
463 }
464
465 #[test]
weights_mut_iterator()466 fn weights_mut_iterator() {
467 let mut gr = StableGraph::new();
468 let a = gr.add_node(1);
469 let b = gr.add_node(2);
470 let c = gr.add_node(3);
471 let e1 = gr.add_edge(a, a, 10);
472 let e2 = gr.add_edge(a, b, 20);
473 let e3 = gr.add_edge(b, c, 30);
474 let e4 = gr.add_edge(a, c, 40);
475
476 for n in gr.node_weights_mut() {
477 *n += 1;
478 }
479 assert_eq!(gr[a], 2);
480 assert_eq!(gr[b], 3);
481 assert_eq!(gr[c], 4);
482
483 for e in gr.edge_weights_mut() {
484 *e -= 1;
485 }
486 assert_eq!(gr[e1], 9);
487 assert_eq!(gr[e2], 19);
488 assert_eq!(gr[e3], 29);
489 assert_eq!(gr[e4], 39);
490
491 // test on deletion
492 gr.remove_node(b);
493 assert_eq!(gr.node_weights_mut().count(), gr.node_count());
494 assert_eq!(gr.edge_weights_mut().count(), gr.edge_count());
495 }
496