1 extern crate petgraph;
2
3 use std::collections::HashSet;
4 use std::hash::Hash;
5
6 use petgraph::prelude::*;
7 use petgraph::EdgeType;
8
9 use petgraph as pg;
10
11 use petgraph::algo::{
12 dominators, has_path_connecting, is_bipartite_undirected, is_cyclic_undirected,
13 is_isomorphic_matching, min_spanning_tree,
14 };
15
16 use petgraph::graph::node_index as n;
17 use petgraph::graph::IndexType;
18
19 use petgraph::algo::{astar, dijkstra, DfsSpace};
20 use petgraph::visit::{
21 IntoEdges, IntoEdgesDirected, IntoNeighbors, IntoNodeIdentifiers, NodeFiltered, Reversed, Topo,
22 VisitMap, Walker,
23 };
24
25 use petgraph::dot::Dot;
26
set<I>(iter: I) -> HashSet<I::Item> where I: IntoIterator, I::Item: Hash + Eq,27 fn set<I>(iter: I) -> HashSet<I::Item>
28 where
29 I: IntoIterator,
30 I::Item: Hash + Eq,
31 {
32 iter.into_iter().collect()
33 }
34
35 #[test]
undirected()36 fn undirected() {
37 let mut og = Graph::new_undirected();
38 let a = og.add_node(0);
39 let b = og.add_node(1);
40 let c = og.add_node(2);
41 let d = og.add_node(3);
42 let _ = og.add_edge(a, b, 0);
43 let _ = og.add_edge(a, c, 1);
44 og.add_edge(c, a, 2);
45 og.add_edge(a, a, 3);
46 og.add_edge(b, c, 4);
47 og.add_edge(b, a, 5);
48 og.add_edge(a, d, 6);
49 assert_eq!(og.node_count(), 4);
50 assert_eq!(og.edge_count(), 7);
51
52 assert!(og.find_edge(a, b).is_some());
53 assert!(og.find_edge(d, a).is_some());
54 assert!(og.find_edge(a, a).is_some());
55
56 for edge in og.raw_edges() {
57 assert!(og.find_edge(edge.source(), edge.target()).is_some());
58 assert!(og.find_edge(edge.target(), edge.source()).is_some());
59 }
60
61 assert_eq!(og.neighbors(b).collect::<Vec<_>>(), vec![a, c, a]);
62
63 og.remove_node(a);
64 assert_eq!(og.neighbors(b).collect::<Vec<_>>(), vec![c]);
65 assert_eq!(og.node_count(), 3);
66 assert_eq!(og.edge_count(), 1);
67 assert!(og.find_edge(a, b).is_none());
68 assert!(og.find_edge(d, a).is_none());
69 assert!(og.find_edge(a, a).is_none());
70 assert!(og.find_edge(b, c).is_some());
71 assert_graph_consistent(&og);
72 }
73
74 #[test]
dfs()75 fn dfs() {
76 let mut gr = Graph::new();
77 let h = gr.add_node("H");
78 let i = gr.add_node("I");
79 let j = gr.add_node("J");
80 let k = gr.add_node("K");
81 // Z is disconnected.
82 let _ = gr.add_node("Z");
83 gr.add_edge(h, i, 1.);
84 gr.add_edge(h, j, 3.);
85 gr.add_edge(i, j, 1.);
86 gr.add_edge(i, k, 2.);
87
88 println!("{}", Dot::new(&gr));
89
90 assert_eq!(Dfs::new(&gr, h).iter(&gr).count(), 4);
91 assert_eq!(Dfs::new(&gr, h).iter(&gr).clone().count(), 4);
92
93 assert_eq!(Dfs::new(&gr, h).iter(Reversed(&gr)).count(), 1);
94
95 assert_eq!(Dfs::new(&gr, k).iter(Reversed(&gr)).count(), 3);
96
97 assert_eq!(Dfs::new(&gr, i).iter(&gr).count(), 3);
98 }
99
100 #[test]
dfs_order()101 fn dfs_order() {
102 let mut gr = Graph::new();
103 let h = gr.add_node("H");
104 let i = gr.add_node("I");
105 let j = gr.add_node("J");
106 let k = gr.add_node("K");
107 gr.add_edge(h, i, ());
108 gr.add_edge(h, j, ());
109 gr.add_edge(h, k, ());
110 gr.add_edge(i, k, ());
111 gr.add_edge(k, i, ());
112
113 // H
114 // / | \
115 // I J K
116 // \___/
117 //
118 // J cannot be visited between I and K in a depth-first search from H
119
120 let mut seen_i = false;
121 let mut seen_k = false;
122 for node in Dfs::new(&gr, h).iter(&gr) {
123 seen_i |= i == node;
124 seen_k |= k == node;
125 assert!(!(j == node && (seen_i ^ seen_k)), "Invalid DFS order");
126 }
127 }
128
129 #[test]
bfs()130 fn bfs() {
131 let mut gr = Graph::new();
132 let h = gr.add_node("H");
133 let i = gr.add_node("I");
134 let j = gr.add_node("J");
135 let k = gr.add_node("K");
136 // Z is disconnected.
137 let _ = gr.add_node("Z");
138 gr.add_edge(h, i, 1.);
139 gr.add_edge(h, j, 3.);
140 gr.add_edge(i, j, 1.);
141 gr.add_edge(i, k, 2.);
142
143 assert_eq!(Bfs::new(&gr, h).iter(&gr).count(), 4);
144 assert_eq!(Bfs::new(&gr, h).iter(&gr).clone().count(), 4);
145
146 assert_eq!(Bfs::new(&gr, h).iter(Reversed(&gr)).count(), 1);
147
148 assert_eq!(Bfs::new(&gr, k).iter(Reversed(&gr)).count(), 3);
149
150 assert_eq!(Bfs::new(&gr, i).iter(&gr).count(), 3);
151
152 let mut bfs = Bfs::new(&gr, h);
153 let nx = bfs.next(&gr);
154 assert_eq!(nx, Some(h));
155
156 let nx1 = bfs.next(&gr);
157 assert!(nx1 == Some(i) || nx1 == Some(j));
158
159 let nx2 = bfs.next(&gr);
160 assert!(nx2 == Some(i) || nx2 == Some(j));
161 assert!(nx1 != nx2);
162
163 let nx = bfs.next(&gr);
164 assert_eq!(nx, Some(k));
165 assert_eq!(bfs.next(&gr), None);
166 }
167
168 #[test]
mst()169 fn mst() {
170 use petgraph::data::FromElements;
171
172 let mut gr = Graph::<_, _>::new();
173 let a = gr.add_node("A");
174 let b = gr.add_node("B");
175 let c = gr.add_node("C");
176 let d = gr.add_node("D");
177 let e = gr.add_node("E");
178 let f = gr.add_node("F");
179 let g = gr.add_node("G");
180 gr.add_edge(a, b, 7.);
181 gr.add_edge(a, d, 5.);
182 gr.add_edge(d, b, 9.);
183 gr.add_edge(b, c, 8.);
184 gr.add_edge(b, e, 7.);
185 gr.add_edge(c, e, 5.);
186 gr.add_edge(d, e, 15.);
187 gr.add_edge(d, f, 6.);
188 gr.add_edge(f, e, 8.);
189 gr.add_edge(f, g, 11.);
190 gr.add_edge(e, g, 9.);
191
192 // add a disjoint part
193 let h = gr.add_node("H");
194 let i = gr.add_node("I");
195 let j = gr.add_node("J");
196 gr.add_edge(h, i, 1.);
197 gr.add_edge(h, j, 3.);
198 gr.add_edge(i, j, 1.);
199
200 println!("{}", Dot::new(&gr));
201
202 let mst = UnGraph::from_elements(min_spanning_tree(&gr));
203
204 println!("{}", Dot::new(&mst));
205 println!("{:?}", Dot::new(&mst));
206 println!("MST is:\n{:#?}", mst);
207 assert!(mst.node_count() == gr.node_count());
208 // |E| = |N| - 2 because there are two disconnected components.
209 assert!(mst.edge_count() == gr.node_count() - 2);
210
211 // check the exact edges are there
212 assert!(mst.find_edge(a, b).is_some());
213 assert!(mst.find_edge(a, d).is_some());
214 assert!(mst.find_edge(b, e).is_some());
215 assert!(mst.find_edge(e, c).is_some());
216 assert!(mst.find_edge(e, g).is_some());
217 assert!(mst.find_edge(d, f).is_some());
218
219 assert!(mst.find_edge(h, i).is_some());
220 assert!(mst.find_edge(i, j).is_some());
221
222 assert!(mst.find_edge(d, b).is_none());
223 assert!(mst.find_edge(b, c).is_none());
224 }
225
226 #[test]
selfloop()227 fn selfloop() {
228 let mut gr = Graph::new();
229 let a = gr.add_node("A");
230 let b = gr.add_node("B");
231 let c = gr.add_node("C");
232 gr.add_edge(a, b, 7.);
233 gr.add_edge(c, a, 6.);
234 let sed = gr.add_edge(a, a, 2.);
235
236 assert!(gr.find_edge(a, b).is_some());
237 assert!(gr.find_edge(b, a).is_none());
238 assert!(gr.find_edge_undirected(b, a).is_some());
239 assert!(gr.find_edge(a, a).is_some());
240 println!("{:?}", gr);
241
242 gr.remove_edge(sed);
243 assert!(gr.find_edge(a, a).is_none());
244 println!("{:?}", gr);
245 }
246
247 #[test]
cyclic()248 fn cyclic() {
249 let mut gr = Graph::new();
250 let a = gr.add_node("A");
251 let b = gr.add_node("B");
252 let c = gr.add_node("C");
253
254 assert!(!is_cyclic_undirected(&gr));
255 gr.add_edge(a, b, 7.);
256 gr.add_edge(c, a, 6.);
257 assert!(!is_cyclic_undirected(&gr));
258 {
259 let e = gr.add_edge(a, a, 0.);
260 assert!(is_cyclic_undirected(&gr));
261 gr.remove_edge(e);
262 assert!(!is_cyclic_undirected(&gr));
263 }
264
265 {
266 let e = gr.add_edge(b, c, 0.);
267 assert!(is_cyclic_undirected(&gr));
268 gr.remove_edge(e);
269 assert!(!is_cyclic_undirected(&gr));
270 }
271
272 let d = gr.add_node("D");
273 let e = gr.add_node("E");
274 gr.add_edge(b, d, 0.);
275 gr.add_edge(d, e, 0.);
276 assert!(!is_cyclic_undirected(&gr));
277 gr.add_edge(c, e, 0.);
278 assert!(is_cyclic_undirected(&gr));
279 assert_graph_consistent(&gr);
280 }
281
282 #[test]
bipartite()283 fn bipartite() {
284 {
285 let mut gr = Graph::new_undirected();
286 let a = gr.add_node("A");
287 let b = gr.add_node("B");
288 let c = gr.add_node("C");
289
290 let d = gr.add_node("D");
291 let e = gr.add_node("E");
292 let f = gr.add_node("F");
293
294 gr.add_edge(a, d, 7.);
295 gr.add_edge(b, d, 6.);
296
297 assert!(is_bipartite_undirected(&gr, a));
298
299 let e_index = gr.add_edge(a, b, 6.);
300
301 assert!(!is_bipartite_undirected(&gr, a));
302
303 gr.remove_edge(e_index);
304
305 assert!(is_bipartite_undirected(&gr, a));
306
307 gr.add_edge(b, e, 7.);
308 gr.add_edge(b, f, 6.);
309 gr.add_edge(c, e, 6.);
310
311 assert!(is_bipartite_undirected(&gr, a));
312 }
313 {
314 let mut gr = Graph::new_undirected();
315 let a = gr.add_node("A");
316 let b = gr.add_node("B");
317 let c = gr.add_node("C");
318 let d = gr.add_node("D");
319 let e = gr.add_node("E");
320
321 let f = gr.add_node("F");
322 let g = gr.add_node("G");
323 let h = gr.add_node("H");
324
325 gr.add_edge(a, f, 7.);
326 gr.add_edge(a, g, 7.);
327 gr.add_edge(a, h, 7.);
328
329 gr.add_edge(b, f, 6.);
330 gr.add_edge(b, g, 6.);
331 gr.add_edge(b, h, 6.);
332
333 gr.add_edge(c, f, 6.);
334 gr.add_edge(c, g, 6.);
335 gr.add_edge(c, h, 6.);
336
337 gr.add_edge(d, f, 6.);
338 gr.add_edge(d, g, 6.);
339 gr.add_edge(d, h, 6.);
340
341 gr.add_edge(e, f, 6.);
342 gr.add_edge(e, g, 6.);
343 gr.add_edge(e, h, 6.);
344
345 assert!(is_bipartite_undirected(&gr, a));
346
347 gr.add_edge(a, b, 6.);
348
349 assert!(!is_bipartite_undirected(&gr, a));
350 }
351 }
352
353 #[test]
multi()354 fn multi() {
355 let mut gr = Graph::new();
356 let a = gr.add_node("a");
357 let b = gr.add_node("b");
358 gr.add_edge(a, b, ());
359 gr.add_edge(a, b, ());
360 assert_eq!(gr.edge_count(), 2);
361 }
362
363 #[test]
iter_multi_edges()364 fn iter_multi_edges() {
365 let mut gr = Graph::new();
366 let a = gr.add_node("a");
367 let b = gr.add_node("b");
368 let c = gr.add_node("c");
369
370 let mut connecting_edges = HashSet::new();
371
372 gr.add_edge(a, a, ());
373 connecting_edges.insert(gr.add_edge(a, b, ()));
374 gr.add_edge(a, c, ());
375 gr.add_edge(c, b, ());
376 connecting_edges.insert(gr.add_edge(a, b, ()));
377 gr.add_edge(b, a, ());
378
379 let mut iter = gr.edges_connecting(a, b);
380
381 let edge_id = iter.next().unwrap().id();
382 assert!(connecting_edges.contains(&edge_id));
383 connecting_edges.remove(&edge_id);
384
385 let edge_id = iter.next().unwrap().id();
386 assert!(connecting_edges.contains(&edge_id));
387 connecting_edges.remove(&edge_id);
388
389 assert_eq!(None, iter.next());
390 assert!(connecting_edges.is_empty());
391 }
392
393 #[test]
iter_multi_undirected_edges()394 fn iter_multi_undirected_edges() {
395 let mut gr = Graph::new_undirected();
396 let a = gr.add_node("a");
397 let b = gr.add_node("b");
398 let c = gr.add_node("c");
399
400 let mut connecting_edges = HashSet::new();
401
402 gr.add_edge(a, a, ());
403 connecting_edges.insert(gr.add_edge(a, b, ()));
404 gr.add_edge(a, c, ());
405 gr.add_edge(c, b, ());
406 connecting_edges.insert(gr.add_edge(a, b, ()));
407 connecting_edges.insert(gr.add_edge(b, a, ()));
408
409 let mut iter = gr.edges_connecting(a, b);
410
411 let edge_id = iter.next().unwrap().id();
412 assert!(connecting_edges.contains(&edge_id));
413 connecting_edges.remove(&edge_id);
414
415 let edge_id = iter.next().unwrap().id();
416 assert!(connecting_edges.contains(&edge_id));
417 connecting_edges.remove(&edge_id);
418
419 let edge_id = iter.next().unwrap().id();
420 assert!(connecting_edges.contains(&edge_id));
421 connecting_edges.remove(&edge_id);
422
423 assert_eq!(None, iter.next());
424 assert!(connecting_edges.is_empty());
425 }
426
427 #[test]
update_edge()428 fn update_edge() {
429 {
430 let mut gr = Graph::new();
431 let a = gr.add_node("a");
432 let b = gr.add_node("b");
433 let e = gr.update_edge(a, b, 1);
434 let f = gr.update_edge(a, b, 2);
435 let _ = gr.update_edge(b, a, 3);
436 assert_eq!(gr.edge_count(), 2);
437 assert_eq!(e, f);
438 assert_eq!(*gr.edge_weight(f).unwrap(), 2);
439 }
440
441 {
442 let mut gr = Graph::new_undirected();
443 let a = gr.add_node("a");
444 let b = gr.add_node("b");
445 let e = gr.update_edge(a, b, 1);
446 let f = gr.update_edge(b, a, 2);
447 assert_eq!(gr.edge_count(), 1);
448 assert_eq!(e, f);
449 assert_eq!(*gr.edge_weight(f).unwrap(), 2);
450 }
451 }
452
453 #[test]
dijk()454 fn dijk() {
455 let mut g = Graph::new_undirected();
456 let a = g.add_node("A");
457 let b = g.add_node("B");
458 let c = g.add_node("C");
459 let d = g.add_node("D");
460 let e = g.add_node("E");
461 let f = g.add_node("F");
462 g.add_edge(a, b, 7);
463 g.add_edge(c, a, 9);
464 g.add_edge(a, d, 14);
465 g.add_edge(b, c, 10);
466 g.add_edge(d, c, 2);
467 g.add_edge(d, e, 9);
468 g.add_edge(b, f, 15);
469 g.add_edge(c, f, 11);
470 g.add_edge(e, f, 6);
471 println!("{:?}", g);
472 for no in Bfs::new(&g, a).iter(&g) {
473 println!("Visit {:?} = {:?}", no, g.node_weight(no));
474 }
475
476 let scores = dijkstra(&g, a, None, |e| *e.weight());
477 let mut scores: Vec<_> = scores.into_iter().map(|(n, s)| (g[n], s)).collect();
478 scores.sort();
479 assert_eq!(
480 scores,
481 vec![
482 ("A", 0),
483 ("B", 7),
484 ("C", 9),
485 ("D", 11),
486 ("E", 20),
487 ("F", 20)
488 ]
489 );
490
491 let scores = dijkstra(&g, a, Some(c), |e| *e.weight());
492 assert_eq!(scores[&c], 9);
493 }
494
495 #[test]
test_astar_null_heuristic()496 fn test_astar_null_heuristic() {
497 let mut g = Graph::new();
498 let a = g.add_node("A");
499 let b = g.add_node("B");
500 let c = g.add_node("C");
501 let d = g.add_node("D");
502 let e = g.add_node("E");
503 let f = g.add_node("F");
504 g.add_edge(a, b, 7);
505 g.add_edge(c, a, 9);
506 g.add_edge(a, d, 14);
507 g.add_edge(b, c, 10);
508 g.add_edge(d, c, 2);
509 g.add_edge(d, e, 9);
510 g.add_edge(b, f, 15);
511 g.add_edge(c, f, 11);
512 g.add_edge(e, f, 6);
513
514 let path = astar(&g, a, |finish| finish == e, |e| *e.weight(), |_| 0);
515 assert_eq!(path, Some((23, vec![a, d, e])));
516
517 // check against dijkstra
518 let dijkstra_run = dijkstra(&g, a, Some(e), |e| *e.weight());
519 assert_eq!(dijkstra_run[&e], 23);
520
521 let path = astar(&g, e, |finish| finish == b, |e| *e.weight(), |_| 0);
522 assert_eq!(path, None);
523 }
524
525 #[test]
test_astar_manhattan_heuristic()526 fn test_astar_manhattan_heuristic() {
527 let mut g = Graph::new();
528 let a = g.add_node((0., 0.));
529 let b = g.add_node((2., 0.));
530 let c = g.add_node((1., 1.));
531 let d = g.add_node((0., 2.));
532 let e = g.add_node((3., 3.));
533 let f = g.add_node((4., 2.));
534 let _ = g.add_node((5., 5.)); // no path to node
535 g.add_edge(a, b, 2.);
536 g.add_edge(a, d, 4.);
537 g.add_edge(b, c, 1.);
538 g.add_edge(b, f, 7.);
539 g.add_edge(c, e, 5.);
540 g.add_edge(e, f, 1.);
541 g.add_edge(d, e, 1.);
542
543 let heuristic_for = |f: NodeIndex| {
544 let g = &g;
545 move |node: NodeIndex| -> f32 {
546 let (x1, y1): (f32, f32) = g[node];
547 let (x2, y2): (f32, f32) = g[f];
548
549 (x2 - x1).abs() + (y2 - y1).abs()
550 }
551 };
552 let path = astar(
553 &g,
554 a,
555 |finish| finish == f,
556 |e| *e.weight(),
557 heuristic_for(f),
558 );
559
560 assert_eq!(path, Some((6., vec![a, d, e, f])));
561
562 // check against dijkstra
563 let dijkstra_run = dijkstra(&g, a, None, |e| *e.weight());
564
565 for end in g.node_indices() {
566 let astar_path = astar(
567 &g,
568 a,
569 |finish| finish == end,
570 |e| *e.weight(),
571 heuristic_for(end),
572 );
573 assert_eq!(dijkstra_run.get(&end).cloned(), astar_path.map(|t| t.0));
574 }
575 }
576
577 #[cfg(feature = "generate")]
578 #[test]
test_generate_undirected()579 fn test_generate_undirected() {
580 for size in 0..4 {
581 let mut gen = pg::generate::Generator::<Undirected>::all(size, true);
582 let nedges = (size * size - size) / 2 + size;
583 let mut n = 0;
584 while let Some(g) = gen.next_ref() {
585 n += 1;
586 println!("{:?}", g);
587 }
588
589 assert_eq!(n, 1 << nedges);
590 }
591 }
592
593 #[cfg(feature = "generate")]
594 #[test]
test_generate_directed()595 fn test_generate_directed() {
596 // Number of DAG out of all graphs (all permutations) per node size
597 // 0, 1, 2, 3, 4, 5 ..
598 let n_dag = &[1, 1, 3, 25, 543, 29281, 3781503];
599 for (size, &dags_exp) in (0..4).zip(n_dag) {
600 let mut gen = pg::generate::Generator::<Directed>::all(size, true);
601 let nedges = size * size;
602 let mut n = 0;
603 let mut dags = 0;
604 while let Some(g) = gen.next_ref() {
605 n += 1;
606 if !pg::algo::is_cyclic_directed(g) {
607 dags += 1;
608 }
609 }
610
611 /*
612 // check that all generated graphs have unique adjacency matrices
613 let mut adjmats = graphs.iter().map(Graph::adjacency_matrix).collect::<Vec<_>>();
614 adjmats.sort(); adjmats.dedup();
615 assert_eq!(adjmats.len(), n);
616 */
617 assert_eq!(dags_exp, dags);
618 assert_eq!(n, 1 << nedges);
619 }
620 }
621
622 #[cfg(feature = "generate")]
623 #[test]
test_generate_dag()624 fn test_generate_dag() {
625 use petgraph::visit::GetAdjacencyMatrix;
626 for size in 1..5 {
627 let gen = pg::generate::Generator::directed_acyclic(size);
628 let nedges = (size - 1) * size / 2;
629 let graphs = gen.collect::<Vec<_>>();
630
631 assert_eq!(graphs.len(), 1 << nedges);
632
633 // check that all generated graphs have unique adjacency matrices
634 let mut adjmats = graphs
635 .iter()
636 .map(Graph::adjacency_matrix)
637 .collect::<Vec<_>>();
638 adjmats.sort();
639 adjmats.dedup();
640 assert_eq!(adjmats.len(), graphs.len());
641 for gr in &graphs {
642 assert!(
643 !petgraph::algo::is_cyclic_directed(gr),
644 "Assertion failed: {:?} acyclic",
645 gr
646 );
647 }
648 }
649 }
650
651 #[test]
without()652 fn without() {
653 let mut og = Graph::new_undirected();
654 let a = og.add_node(0);
655 let b = og.add_node(1);
656 let c = og.add_node(2);
657 let d = og.add_node(3);
658 let _ = og.add_edge(a, b, 0);
659 let _ = og.add_edge(a, c, 1);
660 let v: Vec<NodeIndex> = og.externals(Outgoing).collect();
661 assert_eq!(v, vec![d]);
662
663 let mut og = Graph::new();
664 let a = og.add_node(0);
665 let b = og.add_node(1);
666 let c = og.add_node(2);
667 let d = og.add_node(3);
668 let _ = og.add_edge(a, b, 0);
669 let _ = og.add_edge(a, c, 1);
670 let init: Vec<NodeIndex> = og.externals(Incoming).collect();
671 let term: Vec<NodeIndex> = og.externals(Outgoing).collect();
672 assert_eq!(init, vec![a, d]);
673 assert_eq!(term, vec![b, c, d]);
674 }
675
assert_is_topo_order<N, E>(gr: &Graph<N, E, Directed>, order: &[NodeIndex])676 fn assert_is_topo_order<N, E>(gr: &Graph<N, E, Directed>, order: &[NodeIndex]) {
677 assert_eq!(gr.node_count(), order.len());
678 // check all the edges of the graph
679 for edge in gr.raw_edges() {
680 let a = edge.source();
681 let b = edge.target();
682 let ai = order.iter().position(|x| *x == a).unwrap();
683 let bi = order.iter().position(|x| *x == b).unwrap();
684 println!("Check that {:?} is before {:?}", a, b);
685 assert!(
686 ai < bi,
687 "Topo order: assertion that node {:?} is before {:?} failed",
688 a,
689 b
690 );
691 }
692 }
693
694 #[test]
test_toposort()695 fn test_toposort() {
696 let mut gr = Graph::<_, _>::new();
697 let a = gr.add_node("A");
698 let b = gr.add_node("B");
699 let c = gr.add_node("C");
700 let d = gr.add_node("D");
701 let e = gr.add_node("E");
702 let f = gr.add_node("F");
703 let g = gr.add_node("G");
704 gr.extend_with_edges(&[
705 (a, b, 7.),
706 (a, d, 5.),
707 (d, b, 9.),
708 (b, c, 8.),
709 (b, e, 7.),
710 (c, e, 5.),
711 (d, e, 15.),
712 (d, f, 6.),
713 (f, e, 8.),
714 (f, g, 11.),
715 (e, g, 9.),
716 ]);
717
718 // add a disjoint part
719 let h = gr.add_node("H");
720 let i = gr.add_node("I");
721 let j = gr.add_node("J");
722 gr.add_edge(h, i, 1.);
723 gr.add_edge(h, j, 3.);
724 gr.add_edge(i, j, 1.);
725
726 let order = petgraph::algo::toposort(&gr, None).unwrap();
727 println!("{:?}", order);
728 assert_eq!(order.len(), gr.node_count());
729
730 assert_is_topo_order(&gr, &order);
731 }
732
733 #[test]
test_toposort_eq()734 fn test_toposort_eq() {
735 let mut g = Graph::<_, _>::new();
736 let a = g.add_node("A");
737 let b = g.add_node("B");
738 g.add_edge(a, b, ());
739
740 assert_eq!(petgraph::algo::toposort(&g, None), Ok(vec![a, b]));
741 }
742
743 #[test]
is_cyclic_directed()744 fn is_cyclic_directed() {
745 let mut gr = Graph::<_, _>::new();
746 let a = gr.add_node("A");
747 let b = gr.add_node("B");
748 let c = gr.add_node("C");
749 let d = gr.add_node("D");
750 let e = gr.add_node("E");
751 let f = gr.add_node("F");
752 let g = gr.add_node("G");
753 gr.add_edge(a, b, 7.0);
754 gr.add_edge(a, d, 5.);
755 gr.add_edge(d, b, 9.);
756 gr.add_edge(b, c, 8.);
757 gr.add_edge(b, e, 7.);
758 gr.add_edge(c, e, 5.);
759 gr.add_edge(d, e, 15.);
760 gr.add_edge(d, f, 6.);
761 gr.add_edge(f, e, 8.);
762 gr.add_edge(f, g, 11.);
763 gr.add_edge(e, g, 9.);
764
765 assert!(!petgraph::algo::is_cyclic_directed(&gr));
766
767 // add a disjoint part
768 let h = gr.add_node("H");
769 let i = gr.add_node("I");
770 let j = gr.add_node("J");
771 gr.add_edge(h, i, 1.);
772 gr.add_edge(h, j, 3.);
773 gr.add_edge(i, j, 1.);
774 assert!(!petgraph::algo::is_cyclic_directed(&gr));
775
776 gr.add_edge(g, e, 0.);
777 assert!(petgraph::algo::is_cyclic_directed(&gr));
778 }
779
780 /// Compare two scc sets. Inside each scc, the order does not matter,
781 /// but the order of the sccs is significant.
assert_sccs_eq( mut res: Vec<Vec<NodeIndex>>, mut answer: Vec<Vec<NodeIndex>>, scc_order_matters: bool, )782 fn assert_sccs_eq(
783 mut res: Vec<Vec<NodeIndex>>,
784 mut answer: Vec<Vec<NodeIndex>>,
785 scc_order_matters: bool,
786 ) {
787 // normalize the result and compare with the answer.
788 for scc in &mut res {
789 scc.sort();
790 }
791 for scc in &mut answer {
792 scc.sort();
793 }
794 if !scc_order_matters {
795 res.sort();
796 answer.sort();
797 }
798 assert_eq!(res, answer);
799 }
800
801 #[test]
scc()802 fn scc() {
803 let gr: Graph<(), ()> = Graph::from_edges(&[
804 (6, 0),
805 (0, 3),
806 (3, 6),
807 (8, 6),
808 (8, 2),
809 (2, 5),
810 (5, 8),
811 (7, 5),
812 (1, 7),
813 (7, 4),
814 (4, 1),
815 ]);
816
817 assert_sccs_eq(
818 petgraph::algo::kosaraju_scc(&gr),
819 vec![
820 vec![n(0), n(3), n(6)],
821 vec![n(2), n(5), n(8)],
822 vec![n(1), n(4), n(7)],
823 ],
824 true,
825 );
826 // Reversed edges gives the same sccs (when sorted)
827 assert_sccs_eq(
828 petgraph::algo::kosaraju_scc(Reversed(&gr)),
829 vec![
830 vec![n(1), n(4), n(7)],
831 vec![n(2), n(5), n(8)],
832 vec![n(0), n(3), n(6)],
833 ],
834 true,
835 );
836
837 // Test an undirected graph just for fun.
838 // Sccs are just connected components.
839 let mut hr = gr.into_edge_type::<Undirected>();
840 // Delete an edge to disconnect it
841 let ed = hr.find_edge(n(6), n(8)).unwrap();
842 assert!(hr.remove_edge(ed).is_some());
843
844 assert_sccs_eq(
845 petgraph::algo::kosaraju_scc(&hr),
846 vec![
847 vec![n(0), n(3), n(6)],
848 vec![n(1), n(2), n(4), n(5), n(7), n(8)],
849 ],
850 false,
851 );
852
853 // acyclic non-tree, #14
854 let n = NodeIndex::new;
855 let mut gr = Graph::new();
856 gr.add_node(0);
857 gr.add_node(1);
858 gr.add_node(2);
859 gr.add_node(3);
860 gr.add_edge(n(3), n(2), ());
861 gr.add_edge(n(3), n(1), ());
862 gr.add_edge(n(2), n(0), ());
863 gr.add_edge(n(1), n(0), ());
864
865 assert_sccs_eq(
866 petgraph::algo::kosaraju_scc(&gr),
867 vec![vec![n(0)], vec![n(1)], vec![n(2)], vec![n(3)]],
868 true,
869 );
870
871 // Kosaraju bug from PR #60
872 let mut gr = Graph::<(), ()>::new();
873 gr.extend_with_edges(&[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)]);
874 gr.add_node(());
875 // no order for the disconnected one
876 assert_sccs_eq(
877 petgraph::algo::kosaraju_scc(&gr),
878 vec![vec![n(0)], vec![n(1)], vec![n(2)], vec![n(3)]],
879 false,
880 );
881 }
882
883 #[test]
tarjan_scc()884 fn tarjan_scc() {
885 let gr: Graph<(), ()> = Graph::from_edges(&[
886 (6, 0),
887 (0, 3),
888 (3, 6),
889 (8, 6),
890 (8, 2),
891 (2, 5),
892 (5, 8),
893 (7, 5),
894 (1, 7),
895 (7, 4),
896 (4, 1),
897 ]);
898
899 assert_sccs_eq(
900 petgraph::algo::tarjan_scc(&gr),
901 vec![
902 vec![n(0), n(3), n(6)],
903 vec![n(2), n(5), n(8)],
904 vec![n(1), n(4), n(7)],
905 ],
906 true,
907 );
908
909 // Test an undirected graph just for fun.
910 // Sccs are just connected components.
911 let mut hr = gr.into_edge_type::<Undirected>();
912 // Delete an edge to disconnect it
913 let ed = hr.find_edge(n(6), n(8)).unwrap();
914 assert!(hr.remove_edge(ed).is_some());
915
916 assert_sccs_eq(
917 petgraph::algo::tarjan_scc(&hr),
918 vec![
919 vec![n(1), n(2), n(4), n(5), n(7), n(8)],
920 vec![n(0), n(3), n(6)],
921 ],
922 false,
923 );
924
925 // acyclic non-tree, #14
926 let n = NodeIndex::new;
927 let mut gr = Graph::new();
928 gr.add_node(0);
929 gr.add_node(1);
930 gr.add_node(2);
931 gr.add_node(3);
932 gr.add_edge(n(3), n(2), ());
933 gr.add_edge(n(3), n(1), ());
934 gr.add_edge(n(2), n(0), ());
935 gr.add_edge(n(1), n(0), ());
936
937 assert_sccs_eq(
938 petgraph::algo::tarjan_scc(&gr),
939 vec![vec![n(0)], vec![n(1)], vec![n(2)], vec![n(3)]],
940 true,
941 );
942
943 // Kosaraju bug from PR #60
944 let mut gr = Graph::<(), ()>::new();
945 gr.extend_with_edges(&[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)]);
946 gr.add_node(());
947 // no order for the disconnected one
948 assert_sccs_eq(
949 petgraph::algo::tarjan_scc(&gr),
950 vec![vec![n(0)], vec![n(1)], vec![n(2)], vec![n(3)]],
951 false,
952 );
953 }
954
955 #[test]
condensation()956 fn condensation() {
957 let gr: Graph<(), ()> = Graph::from_edges(&[
958 (6, 0),
959 (0, 3),
960 (3, 6),
961 (8, 6),
962 (8, 2),
963 (2, 3),
964 (2, 5),
965 (5, 8),
966 (7, 5),
967 (1, 7),
968 (7, 4),
969 (4, 1),
970 ]);
971
972 // make_acyclic = true
973
974 let cond = petgraph::algo::condensation(gr.clone(), true);
975
976 assert!(cond.node_count() == 3);
977 assert!(cond.edge_count() == 2);
978 assert!(
979 !petgraph::algo::is_cyclic_directed(&cond),
980 "Assertion failed: {:?} acyclic",
981 cond
982 );
983
984 // make_acyclic = false
985
986 let cond = petgraph::algo::condensation(gr.clone(), false);
987
988 assert!(cond.node_count() == 3);
989 assert!(cond.edge_count() == gr.edge_count());
990 }
991
992 #[test]
connected_comp()993 fn connected_comp() {
994 let n = NodeIndex::new;
995 let mut gr = Graph::new();
996 gr.add_node(0);
997 gr.add_node(1);
998 gr.add_node(2);
999 gr.add_node(3);
1000 gr.add_node(4);
1001 gr.add_node(5);
1002 gr.add_node(6);
1003 gr.add_node(7);
1004 gr.add_node(8);
1005 gr.add_edge(n(6), n(0), ());
1006 gr.add_edge(n(0), n(3), ());
1007 gr.add_edge(n(3), n(6), ());
1008 gr.add_edge(n(8), n(6), ());
1009 gr.add_edge(n(8), n(2), ());
1010 gr.add_edge(n(2), n(5), ());
1011 gr.add_edge(n(5), n(8), ());
1012 gr.add_edge(n(7), n(5), ());
1013 gr.add_edge(n(1), n(7), ());
1014 gr.add_edge(n(7), n(4), ());
1015 gr.add_edge(n(4), n(1), ());
1016 assert_eq!(petgraph::algo::connected_components(&gr), 1);
1017
1018 gr.add_node(9);
1019 gr.add_node(10);
1020 assert_eq!(petgraph::algo::connected_components(&gr), 3);
1021
1022 gr.add_edge(n(9), n(10), ());
1023 assert_eq!(petgraph::algo::connected_components(&gr), 2);
1024
1025 let gr = gr.into_edge_type::<Undirected>();
1026 assert_eq!(petgraph::algo::connected_components(&gr), 2);
1027 }
1028
1029 #[should_panic]
1030 #[test]
oob_index()1031 fn oob_index() {
1032 let mut gr = Graph::<_, ()>::new();
1033 let a = gr.add_node(0);
1034 let b = gr.add_node(1);
1035 gr.remove_node(a);
1036 gr[b];
1037 }
1038
1039 #[test]
usize_index()1040 fn usize_index() {
1041 let mut gr = Graph::<_, _, Directed, usize>::with_capacity(0, 0);
1042 let a = gr.add_node(0);
1043 let b = gr.add_node(1);
1044 let e = gr.add_edge(a, b, 1.2);
1045 let mut dfs = Dfs::new(&gr, a);
1046 while let Some(nx) = dfs.next(&gr) {
1047 gr[nx] += 1;
1048 }
1049 assert_eq!(gr[a], 1);
1050 assert_eq!(gr[b], 2);
1051 assert_eq!(gr[e], 1.2);
1052 }
1053
1054 #[test]
u8_index()1055 fn u8_index() {
1056 let mut gr = Graph::<_, (), Undirected, u8>::with_capacity(0, 0);
1057 for _ in 0..255 {
1058 gr.add_node(());
1059 }
1060 }
1061
1062 #[should_panic]
1063 #[test]
u8_index_overflow()1064 fn u8_index_overflow() {
1065 let mut gr = Graph::<_, (), Undirected, u8>::with_capacity(0, 0);
1066 for _ in 0..256 {
1067 gr.add_node(());
1068 }
1069 }
1070
1071 #[should_panic]
1072 #[test]
u8_index_overflow_edges()1073 fn u8_index_overflow_edges() {
1074 let mut gr = Graph::<_, (), Undirected, u8>::with_capacity(0, 0);
1075 let a = gr.add_node('a');
1076 let b = gr.add_node('b');
1077 for _ in 0..256 {
1078 gr.add_edge(a, b, ());
1079 }
1080 }
1081
1082 #[test]
test_weight_iterators()1083 fn test_weight_iterators() {
1084 let mut gr = Graph::<_, _>::new();
1085 let a = gr.add_node("A");
1086 let b = gr.add_node("B");
1087 let c = gr.add_node("C");
1088 let d = gr.add_node("D");
1089 let e = gr.add_node("E");
1090 let f = gr.add_node("F");
1091 let g = gr.add_node("G");
1092 gr.add_edge(a, b, 7.0);
1093 gr.add_edge(a, d, 5.);
1094 gr.add_edge(d, b, 9.);
1095 gr.add_edge(b, c, 8.);
1096 gr.add_edge(b, e, 7.);
1097 gr.add_edge(c, e, 5.);
1098 gr.add_edge(d, e, 15.);
1099 gr.add_edge(d, f, 6.);
1100 gr.add_edge(f, e, 8.);
1101 gr.add_edge(f, g, 11.);
1102 gr.add_edge(e, g, 9.);
1103
1104 assert_eq!(gr.node_weights_mut().count(), gr.node_count());
1105 assert_eq!(gr.edge_weights_mut().count(), gr.edge_count());
1106
1107 // add a disjoint part
1108 let h = gr.add_node("H");
1109 let i = gr.add_node("I");
1110 let j = gr.add_node("J");
1111 gr.add_edge(h, i, 1.);
1112 gr.add_edge(h, j, 3.);
1113 gr.add_edge(i, j, 1.);
1114
1115 assert_eq!(gr.node_weights_mut().count(), gr.node_count());
1116 assert_eq!(gr.edge_weights_mut().count(), gr.edge_count());
1117
1118 for nw in gr.node_weights_mut() {
1119 *nw = "x";
1120 }
1121 for node in gr.raw_nodes() {
1122 assert_eq!(node.weight, "x");
1123 }
1124
1125 let old = gr.clone();
1126 for (index, ew) in gr.edge_weights_mut().enumerate() {
1127 assert_eq!(old[EdgeIndex::new(index)], *ew);
1128 *ew = -*ew;
1129 }
1130 for (index, edge) in gr.raw_edges().iter().enumerate() {
1131 assert_eq!(edge.weight, -1. * old[EdgeIndex::new(index)]);
1132 }
1133 }
1134
1135 #[test]
walk_edges()1136 fn walk_edges() {
1137 let mut gr = Graph::<_, _>::new();
1138 let a = gr.add_node(0.);
1139 let b = gr.add_node(1.);
1140 let c = gr.add_node(2.);
1141 let d = gr.add_node(3.);
1142 let e0 = gr.add_edge(a, b, 0.);
1143 let e1 = gr.add_edge(a, d, 0.);
1144 let e2 = gr.add_edge(b, c, 0.);
1145 let e3 = gr.add_edge(c, a, 0.);
1146
1147 // Set edge weights to difference: target - source.
1148 let mut dfs = Dfs::new(&gr, a);
1149 while let Some(source) = dfs.next(&gr) {
1150 let mut edges = gr.neighbors_directed(source, Outgoing).detach();
1151 while let Some((edge, target)) = edges.next(&gr) {
1152 gr[edge] = gr[target] - gr[source];
1153 }
1154 }
1155 assert_eq!(gr[e0], 1.);
1156 assert_eq!(gr[e1], 3.);
1157 assert_eq!(gr[e2], 1.);
1158 assert_eq!(gr[e3], -2.);
1159
1160 let mut nedges = 0;
1161 let mut dfs = Dfs::new(&gr, a);
1162 while let Some(node) = dfs.next(&gr) {
1163 let mut edges = gr.neighbors_directed(node, Incoming).detach();
1164 while let Some((edge, source)) = edges.next(&gr) {
1165 assert_eq!(gr.find_edge(source, node), Some(edge));
1166 nedges += 1;
1167 }
1168
1169 let mut edges = gr.neighbors_directed(node, Outgoing).detach();
1170 while let Some((edge, target)) = edges.next(&gr) {
1171 assert_eq!(gr.find_edge(node, target), Some(edge));
1172 nedges += 1;
1173 }
1174 }
1175 assert_eq!(nedges, 8);
1176 }
1177
1178 #[test]
index_twice_mut()1179 fn index_twice_mut() {
1180 let mut gr = Graph::<_, _>::new();
1181 let a = gr.add_node(0.);
1182 let b = gr.add_node(0.);
1183 let c = gr.add_node(0.);
1184 let d = gr.add_node(0.);
1185 let e = gr.add_node(0.);
1186 let f = gr.add_node(0.);
1187 let g = gr.add_node(0.);
1188 gr.add_edge(a, b, 7.0);
1189 gr.add_edge(a, d, 5.);
1190 gr.add_edge(d, b, 9.);
1191 gr.add_edge(b, c, 8.);
1192 gr.add_edge(b, e, 7.);
1193 gr.add_edge(c, e, 5.);
1194 gr.add_edge(d, e, 15.);
1195 gr.add_edge(d, f, 6.);
1196 gr.add_edge(f, e, 8.);
1197 gr.add_edge(f, g, 11.);
1198 gr.add_edge(e, g, 9.);
1199
1200 for dir in &[Incoming, Outgoing] {
1201 for nw in gr.node_weights_mut() {
1202 *nw = 0.;
1203 }
1204
1205 // walk the graph and sum incoming edges
1206 let mut dfs = Dfs::new(&gr, a);
1207 while let Some(node) = dfs.next(&gr) {
1208 let mut edges = gr.neighbors_directed(node, *dir).detach();
1209 while let Some(edge) = edges.next_edge(&gr) {
1210 let (nw, ew) = gr.index_twice_mut(node, edge);
1211 *nw += *ew;
1212 }
1213 }
1214
1215 // check the sums
1216 for i in 0..gr.node_count() {
1217 let ni = NodeIndex::new(i);
1218 let s = gr
1219 .edges_directed(ni, *dir)
1220 .map(|e| *e.weight())
1221 .fold(0., |a, b| a + b);
1222 assert_eq!(s, gr[ni]);
1223 }
1224 println!("Sum {:?}: {:?}", dir, gr);
1225 }
1226 }
1227
make_edge_iterator_graph<Ty: EdgeType>() -> Graph<f64, f64, Ty>1228 fn make_edge_iterator_graph<Ty: EdgeType>() -> Graph<f64, f64, Ty> {
1229 let mut gr = Graph::default();
1230 let a = gr.add_node(0.);
1231 let b = gr.add_node(0.);
1232 let c = gr.add_node(0.);
1233 let d = gr.add_node(0.);
1234 let e = gr.add_node(0.);
1235 let f = gr.add_node(0.);
1236 let g = gr.add_node(0.);
1237 gr.add_edge(a, b, 7.0);
1238 gr.add_edge(a, d, 5.);
1239 gr.add_edge(d, b, 9.);
1240 gr.add_edge(b, c, 8.);
1241 gr.add_edge(b, e, 7.);
1242 gr.add_edge(c, c, 8.);
1243 gr.add_edge(c, e, 5.);
1244 gr.add_edge(d, e, 15.);
1245 gr.add_edge(d, f, 6.);
1246 gr.add_edge(f, e, 8.);
1247 gr.add_edge(f, g, 11.);
1248 gr.add_edge(e, g, 9.);
1249
1250 gr
1251 }
1252
1253 #[test]
test_edge_iterators_directed()1254 fn test_edge_iterators_directed() {
1255 let gr = make_edge_iterator_graph::<Directed>();
1256
1257 for i in gr.node_indices() {
1258 itertools::assert_equal(gr.edges_directed(i, Outgoing), gr.edges(i));
1259
1260 // Reversed reverses edges, so target and source need to be reversed once more.
1261 itertools::assert_equal(
1262 gr.edges_directed(i, Outgoing)
1263 .map(|edge| (edge.source(), edge.target())),
1264 Reversed(&gr)
1265 .edges_directed(i, Incoming)
1266 .map(|edge| (edge.target(), edge.source())),
1267 );
1268
1269 for edge in gr.edges_directed(i, Outgoing) {
1270 assert_eq!(
1271 edge.source(),
1272 i,
1273 "outgoing edges should have a fixed source"
1274 );
1275 }
1276 for edge in Reversed(&gr).edges_directed(i, Incoming) {
1277 assert_eq!(
1278 edge.target(),
1279 i,
1280 "reversed incoming edges should have a fixed target"
1281 );
1282 }
1283 }
1284
1285 let mut reversed_gr = gr.clone();
1286 reversed_gr.reverse();
1287
1288 println!("{:#?}", gr);
1289 for i in gr.node_indices() {
1290 // Compare against reversed graphs two different ways: using .reverse() and Reversed.
1291 itertools::assert_equal(gr.edges_directed(i, Incoming), reversed_gr.edges(i));
1292
1293 // Reversed reverses edges, so target and source need to be reversed once more.
1294 itertools::assert_equal(
1295 gr.edges_directed(i, Incoming)
1296 .map(|edge| (edge.source(), edge.target())),
1297 Reversed(&gr)
1298 .edges(i)
1299 .map(|edge| (edge.target(), edge.source())),
1300 );
1301
1302 for edge in gr.edges_directed(i, Incoming) {
1303 assert_eq!(
1304 edge.target(),
1305 i,
1306 "incoming edges should have a fixed target"
1307 );
1308 }
1309 for edge in Reversed(&gr).edges_directed(i, Outgoing) {
1310 assert_eq!(
1311 edge.source(),
1312 i,
1313 "reversed outgoing edges should have a fixed source"
1314 );
1315 }
1316 }
1317 }
1318
1319 #[test]
test_edge_iterators_undir()1320 fn test_edge_iterators_undir() {
1321 let gr = make_edge_iterator_graph::<Undirected>();
1322
1323 for i in gr.node_indices() {
1324 itertools::assert_equal(gr.edges_directed(i, Outgoing), gr.edges(i));
1325
1326 // Reversed reverses edges, so target and source need to be reversed once more.
1327 itertools::assert_equal(
1328 gr.edges_directed(i, Outgoing)
1329 .map(|edge| (edge.source(), edge.target())),
1330 Reversed(&gr)
1331 .edges_directed(i, Incoming)
1332 .map(|edge| (edge.target(), edge.source())),
1333 );
1334
1335 for edge in gr.edges_directed(i, Outgoing) {
1336 assert_eq!(
1337 edge.source(),
1338 i,
1339 "outgoing edges should have a fixed source"
1340 );
1341 }
1342 for edge in Reversed(&gr).edges_directed(i, Incoming) {
1343 assert_eq!(
1344 edge.target(),
1345 i,
1346 "reversed incoming edges should have a fixed target"
1347 );
1348 }
1349 }
1350
1351 for i in gr.node_indices() {
1352 itertools::assert_equal(gr.edges_directed(i, Incoming), gr.edges(i));
1353
1354 // Reversed reverses edges, so target and source need to be reversed once more.
1355 itertools::assert_equal(
1356 gr.edges_directed(i, Incoming)
1357 .map(|edge| (edge.source(), edge.target())),
1358 Reversed(&gr)
1359 .edges(i)
1360 .map(|edge| (edge.target(), edge.source())),
1361 );
1362
1363 for edge in gr.edges_directed(i, Incoming) {
1364 assert_eq!(
1365 edge.target(),
1366 i,
1367 "incoming edges should have a fixed target"
1368 );
1369 }
1370 for edge in Reversed(&gr).edges_directed(i, Outgoing) {
1371 assert_eq!(
1372 edge.source(),
1373 i,
1374 "reversed outgoing edges should have a fixed source"
1375 );
1376 }
1377 }
1378 }
1379
1380 #[test]
toposort_generic()1381 fn toposort_generic() {
1382 // This is a DAG, visit it in order
1383 let mut gr = Graph::<_, _>::new();
1384 let b = gr.add_node(("B", 0.));
1385 let a = gr.add_node(("A", 0.));
1386 let c = gr.add_node(("C", 0.));
1387 let d = gr.add_node(("D", 0.));
1388 let e = gr.add_node(("E", 0.));
1389 let f = gr.add_node(("F", 0.));
1390 let g = gr.add_node(("G", 0.));
1391 gr.add_edge(a, b, 7.0);
1392 gr.add_edge(a, d, 5.);
1393 gr.add_edge(d, b, 9.);
1394 gr.add_edge(b, c, 8.);
1395 gr.add_edge(b, e, 7.);
1396 gr.add_edge(c, e, 5.);
1397 gr.add_edge(d, e, 15.);
1398 gr.add_edge(d, f, 6.);
1399 gr.add_edge(f, e, 8.);
1400 gr.add_edge(f, g, 11.);
1401 gr.add_edge(e, g, 9.);
1402
1403 assert!(!pg::algo::is_cyclic_directed(&gr));
1404 let mut index = 0.;
1405 let mut topo = Topo::new(&gr);
1406 while let Some(nx) = topo.next(&gr) {
1407 gr[nx].1 = index;
1408 index += 1.;
1409 }
1410
1411 let mut order = Vec::new();
1412 index = 0.;
1413 let mut topo = Topo::new(&gr);
1414 while let Some(nx) = topo.next(&gr) {
1415 order.push(nx);
1416 assert_eq!(gr[nx].1, index);
1417 index += 1.;
1418 }
1419 println!("{:?}", gr);
1420 assert_is_topo_order(&gr, &order);
1421
1422 {
1423 order.clear();
1424 let mut topo = Topo::new(&gr);
1425 while let Some(nx) = topo.next(&gr) {
1426 order.push(nx);
1427 }
1428 println!("{:?}", gr);
1429 assert_is_topo_order(&gr, &order);
1430 }
1431 let mut gr2 = gr.clone();
1432 gr.add_edge(e, d, -1.);
1433 assert!(pg::algo::is_cyclic_directed(&gr));
1434 assert!(pg::algo::toposort(&gr, None).is_err());
1435 gr2.add_edge(d, d, 0.);
1436 assert!(pg::algo::is_cyclic_directed(&gr2));
1437 assert!(pg::algo::toposort(&gr2, None).is_err());
1438 }
1439
1440 #[test]
test_has_path()1441 fn test_has_path() {
1442 // This is a DAG, visit it in order
1443 let mut gr = Graph::<_, _>::new();
1444 let b = gr.add_node(("B", 0.));
1445 let a = gr.add_node(("A", 0.));
1446 let c = gr.add_node(("C", 0.));
1447 let d = gr.add_node(("D", 0.));
1448 let e = gr.add_node(("E", 0.));
1449 let f = gr.add_node(("F", 0.));
1450 let g = gr.add_node(("G", 0.));
1451 gr.add_edge(a, b, 7.0);
1452 gr.add_edge(a, d, 5.);
1453 gr.add_edge(d, b, 9.);
1454 gr.add_edge(b, c, 8.);
1455 gr.add_edge(b, e, 7.);
1456 gr.add_edge(c, e, 5.);
1457 gr.add_edge(d, e, 15.);
1458 gr.add_edge(d, f, 6.);
1459 gr.add_edge(f, e, 8.);
1460 gr.add_edge(f, g, 11.);
1461 gr.add_edge(e, g, 9.);
1462 // disconnected island
1463
1464 let h = gr.add_node(("H", 0.));
1465 let i = gr.add_node(("I", 0.));
1466 gr.add_edge(h, i, 2.);
1467 gr.add_edge(i, h, -2.);
1468
1469 let mut state = DfsSpace::default();
1470
1471 gr.add_edge(b, a, 99.);
1472
1473 assert!(has_path_connecting(&gr, c, c, None));
1474
1475 for edge in gr.edge_references() {
1476 assert!(has_path_connecting(&gr, edge.source(), edge.target(), None));
1477 }
1478 assert!(has_path_connecting(&gr, a, g, Some(&mut state)));
1479 assert!(!has_path_connecting(&gr, a, h, Some(&mut state)));
1480 assert!(has_path_connecting(&gr, a, c, None));
1481 assert!(has_path_connecting(&gr, a, c, Some(&mut state)));
1482 assert!(!has_path_connecting(&gr, h, a, Some(&mut state)));
1483 }
1484
1485 #[test]
map_filter_map()1486 fn map_filter_map() {
1487 let mut g = Graph::new_undirected();
1488 let a = g.add_node("A");
1489 let b = g.add_node("B");
1490 let c = g.add_node("C");
1491 let d = g.add_node("D");
1492 let e = g.add_node("E");
1493 let f = g.add_node("F");
1494 g.add_edge(a, b, 7);
1495 g.add_edge(c, a, 9);
1496 g.add_edge(a, d, 14);
1497 g.add_edge(b, c, 10);
1498 g.add_edge(d, c, 2);
1499 g.add_edge(d, e, 9);
1500 g.add_edge(b, f, 15);
1501 g.add_edge(c, f, 11);
1502 g.add_edge(e, f, 6);
1503 println!("{:?}", g);
1504
1505 let g2 = g.filter_map(
1506 |_, name| Some(*name),
1507 |_, &weight| if weight >= 10 { Some(weight) } else { None },
1508 );
1509 assert_eq!(g2.edge_count(), 4);
1510 for edge in g2.raw_edges() {
1511 assert!(edge.weight >= 10);
1512 }
1513
1514 let g3 = g.filter_map(
1515 |i, &name| if i == a || i == e { None } else { Some(name) },
1516 |i, &weight| {
1517 let (source, target) = g.edge_endpoints(i).unwrap();
1518 // don't map edges from a removed node
1519 assert!(source != a);
1520 assert!(target != a);
1521 assert!(source != e);
1522 assert!(target != e);
1523 Some(weight)
1524 },
1525 );
1526 assert_eq!(g3.node_count(), g.node_count() - 2);
1527 assert_eq!(g3.edge_count(), g.edge_count() - 5);
1528 assert_graph_consistent(&g3);
1529
1530 let mut g4 = g.clone();
1531 g4.retain_edges(|gr, i| {
1532 let (s, t) = gr.edge_endpoints(i).unwrap();
1533 !(s == a || s == e || t == a || t == e)
1534 });
1535 assert_eq!(g4.edge_count(), g.edge_count() - 5);
1536 assert_graph_consistent(&g4);
1537 }
1538
1539 #[test]
from_edges()1540 fn from_edges() {
1541 let n = NodeIndex::new;
1542 let gr =
1543 Graph::<(), (), Undirected>::from_edges(&[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]);
1544 assert_eq!(gr.node_count(), 4);
1545 assert_eq!(gr.edge_count(), 6);
1546 assert_eq!(gr.neighbors(n(0)).count(), 3);
1547 assert_eq!(gr.neighbors(n(1)).count(), 3);
1548 assert_eq!(gr.neighbors(n(2)).count(), 3);
1549 assert_eq!(gr.neighbors(n(3)).count(), 3);
1550 assert_graph_consistent(&gr);
1551 }
1552
1553 #[test]
retain()1554 fn retain() {
1555 let mut gr = Graph::<i32, i32, Undirected>::from_edges(&[
1556 (0, 1, 2),
1557 (1, 1, 1),
1558 (0, 2, 0),
1559 (1, 2, 3),
1560 (2, 3, 3),
1561 ]);
1562 gr.retain_edges(|mut gr, i| {
1563 if gr[i] <= 0 {
1564 false
1565 } else {
1566 gr[i] -= 1;
1567 let (s, t) = gr.edge_endpoints(i).unwrap();
1568 gr[s] += 1;
1569 gr[t] += 1;
1570
1571 gr[i] > 0
1572 }
1573 });
1574
1575 assert_eq!(gr.edge_count(), 3);
1576 assert_eq!(gr[n(0)], 1);
1577 assert_eq!(gr[n(1)], 4);
1578 assert_eq!(gr[n(2)], 2);
1579 assert_eq!(gr[n(3)], 1);
1580 assert!(gr.find_edge(n(1), n(1)).is_none());
1581 assert!(gr.find_edge(n(0), n(2)).is_none());
1582 assert_graph_consistent(&gr);
1583 }
1584
assert_graph_consistent<N, E, Ty, Ix>(g: &Graph<N, E, Ty, Ix>) where Ty: EdgeType, Ix: IndexType,1585 fn assert_graph_consistent<N, E, Ty, Ix>(g: &Graph<N, E, Ty, Ix>)
1586 where
1587 Ty: EdgeType,
1588 Ix: IndexType,
1589 {
1590 assert_eq!(g.node_count(), g.node_indices().count());
1591 assert_eq!(g.edge_count(), g.edge_indices().count());
1592 for edge in g.raw_edges() {
1593 assert!(
1594 g.find_edge(edge.source(), edge.target()).is_some(),
1595 "Edge not in graph! {:?} to {:?}",
1596 edge.source(),
1597 edge.target()
1598 );
1599 }
1600 }
1601
1602 #[test]
neighbors_selfloops()1603 fn neighbors_selfloops() {
1604 // Directed graph
1605 let mut gr = Graph::<_, ()>::new();
1606 let a = gr.add_node("a");
1607 let b = gr.add_node("b");
1608 let c = gr.add_node("c");
1609 gr.extend_with_edges(&[(a, a), (a, b), (c, a), (a, a)]);
1610
1611 let out_edges = [a, a, b];
1612 let in_edges = [a, a, c];
1613 let undir_edges = [a, a, b, c];
1614 let mut seen_out = gr.neighbors(a).collect::<Vec<_>>();
1615 seen_out.sort();
1616 assert_eq!(&seen_out, &out_edges);
1617 let mut seen_in = gr.neighbors_directed(a, Incoming).collect::<Vec<_>>();
1618 seen_in.sort();
1619 assert_eq!(&seen_in, &in_edges);
1620
1621 let mut seen_undir = gr.neighbors_undirected(a).collect::<Vec<_>>();
1622 seen_undir.sort();
1623 assert_eq!(&seen_undir, &undir_edges);
1624
1625 let mut seen_out = gr.edges(a).map(|e| e.target()).collect::<Vec<_>>();
1626 seen_out.sort();
1627 assert_eq!(&seen_out, &out_edges);
1628
1629 let mut seen_walk = Vec::new();
1630 let mut walk = gr.neighbors(a).detach();
1631 while let Some(n) = walk.next_node(&gr) {
1632 seen_walk.push(n);
1633 }
1634 seen_walk.sort();
1635 assert_eq!(&seen_walk, &out_edges);
1636
1637 seen_walk.clear();
1638 let mut walk = gr.neighbors_directed(a, Incoming).detach();
1639 while let Some(n) = walk.next_node(&gr) {
1640 seen_walk.push(n);
1641 }
1642 seen_walk.sort();
1643 assert_eq!(&seen_walk, &in_edges);
1644
1645 seen_walk.clear();
1646 let mut walk = gr.neighbors_undirected(a).detach();
1647 while let Some(n) = walk.next_node(&gr) {
1648 seen_walk.push(n);
1649 }
1650 seen_walk.sort();
1651 assert_eq!(&seen_walk, &undir_edges);
1652
1653 // Undirected graph
1654 let mut gr: Graph<_, (), _> = Graph::new_undirected();
1655 let a = gr.add_node("a");
1656 let b = gr.add_node("b");
1657 let c = gr.add_node("c");
1658 gr.extend_with_edges(&[(a, a), (a, b), (c, a)]);
1659
1660 let out_edges = [a, b, c];
1661 let in_edges = [a, b, c];
1662 let undir_edges = [a, b, c];
1663 let mut seen_out = gr.neighbors(a).collect::<Vec<_>>();
1664 seen_out.sort();
1665 assert_eq!(&seen_out, &out_edges);
1666
1667 let mut seen_out = gr.edges(a).map(|e| e.target()).collect::<Vec<_>>();
1668 seen_out.sort();
1669 assert_eq!(&seen_out, &out_edges);
1670
1671 let mut seen_in = gr.neighbors_directed(a, Incoming).collect::<Vec<_>>();
1672 seen_in.sort();
1673 assert_eq!(&seen_in, &in_edges);
1674
1675 let mut seen_undir = gr.neighbors_undirected(a).collect::<Vec<_>>();
1676 seen_undir.sort();
1677 assert_eq!(&seen_undir, &undir_edges);
1678 }
1679
degree<'a, G>(g: G, node: G::NodeId) -> usize where G: IntoNeighbors, G::NodeId: PartialEq,1680 fn degree<'a, G>(g: G, node: G::NodeId) -> usize
1681 where
1682 G: IntoNeighbors,
1683 G::NodeId: PartialEq,
1684 {
1685 // self loops count twice
1686 let original_node = node.clone();
1687 let mut degree = 0;
1688 for v in g.neighbors(node) {
1689 degree += if v == original_node { 2 } else { 1 };
1690 }
1691 degree
1692 }
1693
1694 #[cfg(feature = "graphmap")]
1695 #[test]
degree_sequence()1696 fn degree_sequence() {
1697 let mut gr = Graph::<usize, (), Undirected>::from_edges(&[
1698 (0, 1),
1699 (1, 2),
1700 (1, 3),
1701 (2, 4),
1702 (3, 4),
1703 (4, 4),
1704 (4, 5),
1705 (3, 5),
1706 ]);
1707 gr.add_node(0); // add isolated node
1708 let mut degree_sequence = gr
1709 .node_indices()
1710 .map(|i| degree(&gr, i))
1711 .collect::<Vec<_>>();
1712
1713 degree_sequence.sort_by(|x, y| Ord::cmp(y, x));
1714 assert_eq!(°ree_sequence, &[5, 3, 3, 2, 2, 1, 0]);
1715
1716 let mut gr = GraphMap::<_, (), Undirected>::from_edges(&[
1717 (0, 1),
1718 (1, 2),
1719 (1, 3),
1720 (2, 4),
1721 (3, 4),
1722 (4, 4),
1723 (4, 5),
1724 (3, 5),
1725 ]);
1726 gr.add_node(6); // add isolated node
1727 let mut degree_sequence = gr.nodes().map(|i| degree(&gr, i)).collect::<Vec<_>>();
1728
1729 degree_sequence.sort_by(|x, y| Ord::cmp(y, x));
1730 assert_eq!(°ree_sequence, &[5, 3, 3, 2, 2, 1, 0]);
1731 }
1732
1733 #[test]
neighbor_order()1734 fn neighbor_order() {
1735 let mut gr = Graph::new();
1736 let a = gr.add_node("a");
1737 let b = gr.add_node("b");
1738 let c = gr.add_node("c");
1739 gr.add_edge(a, b, 0);
1740 gr.add_edge(a, a, 1);
1741
1742 gr.add_edge(c, a, 2);
1743
1744 gr.add_edge(a, c, 3);
1745
1746 gr.add_edge(c, a, 4);
1747 gr.add_edge(b, a, 5);
1748
1749 // neighbors (edges) are in lifo order, if it's a directed graph
1750 assert_eq!(gr.neighbors(a).collect::<Vec<_>>(), vec![c, a, b]);
1751 assert_eq!(
1752 gr.neighbors_directed(a, Incoming).collect::<Vec<_>>(),
1753 vec![b, c, c, a]
1754 );
1755 }
1756
1757 #[test]
dot()1758 fn dot() {
1759 // test alternate formatting
1760 #[derive(Debug)]
1761 struct Record {
1762 a: i32,
1763 b: &'static str,
1764 };
1765 let mut gr = Graph::new();
1766 let a = gr.add_node(Record { a: 1, b: r"abc\" });
1767 gr.add_edge(a, a, (1, 2));
1768 let dot_output = format!("{:?}", Dot::new(&gr));
1769 assert_eq!(
1770 dot_output,
1771 // The single \ turns into four \\\\ because of Debug which turns it to \\ and then escaping each \ to \\.
1772 r#"digraph {
1773 0 [ label = "Record { a: 1, b: \"abc\\\\\" }" ]
1774 0 -> 0 [ label = "(1, 2)" ]
1775 }
1776 "#
1777 );
1778 }
1779
1780 #[test]
filtered()1781 fn filtered() {
1782 let mut g = Graph::new();
1783 let a = g.add_node("A");
1784 let b = g.add_node("B");
1785 let c = g.add_node("C");
1786 let d = g.add_node("D");
1787 let e = g.add_node("E");
1788 let f = g.add_node("F");
1789 g.add_edge(a, b, 7);
1790 g.add_edge(c, a, 9);
1791 g.add_edge(a, d, 14);
1792 g.add_edge(b, c, 10);
1793 g.add_edge(d, c, 2);
1794 g.add_edge(d, e, 9);
1795 g.add_edge(b, f, 15);
1796 g.add_edge(c, f, 11);
1797 g.add_edge(e, f, 6);
1798 println!("{:?}", g);
1799
1800 let filt = NodeFiltered(&g, |n: NodeIndex| n != c && n != e);
1801
1802 let mut dfs = DfsPostOrder::new(&filt, a);
1803 let mut po = Vec::new();
1804 while let Some(nx) = dfs.next(&filt) {
1805 println!("Next: {:?}", nx);
1806 po.push(nx);
1807 }
1808 assert_eq!(set(po), set(g.node_identifiers().filter(|n| (filt.1)(*n))));
1809 }
1810
1811 #[test]
filtered_edge_reverse()1812 fn filtered_edge_reverse() {
1813 use petgraph::visit::EdgeFiltered;
1814 #[derive(Eq, PartialEq)]
1815 enum E {
1816 A,
1817 B,
1818 }
1819
1820 // Start with single node graph with loop
1821 let mut g = Graph::new();
1822 let a = g.add_node("A");
1823 g.add_edge(a, a, E::A);
1824 let ef_a = EdgeFiltered::from_fn(&g, |edge| *edge.weight() == E::A);
1825 let mut po = Vec::new();
1826 let mut dfs = Dfs::new(&ef_a, a);
1827 while let Some(next_n_ix) = dfs.next(&ef_a) {
1828 po.push(next_n_ix);
1829 }
1830 assert_eq!(set(po), set(vec![a]));
1831
1832 // Check in reverse
1833 let mut po = Vec::new();
1834 let mut dfs = Dfs::new(&Reversed(&ef_a), a);
1835 while let Some(next_n_ix) = dfs.next(&Reversed(&ef_a)) {
1836 po.push(next_n_ix);
1837 }
1838 assert_eq!(set(po), set(vec![a]));
1839
1840 let mut g = Graph::new();
1841 let a = g.add_node("A");
1842 let b = g.add_node("B");
1843 let c = g.add_node("C");
1844 let d = g.add_node("D");
1845 let e = g.add_node("E");
1846 let f = g.add_node("F");
1847 let h = g.add_node("H");
1848 let i = g.add_node("I");
1849 let j = g.add_node("J");
1850
1851 g.add_edge(a, b, E::A);
1852 g.add_edge(b, c, E::A);
1853 g.add_edge(c, d, E::B);
1854 g.add_edge(d, e, E::A);
1855 g.add_edge(e, f, E::A);
1856 g.add_edge(e, h, E::A);
1857 g.add_edge(e, i, E::A);
1858 g.add_edge(i, j, E::A);
1859
1860 let ef_a = EdgeFiltered::from_fn(&g, |edge| *edge.weight() == E::A);
1861 let ef_b = EdgeFiltered::from_fn(&g, |edge| *edge.weight() == E::B);
1862
1863 // DFS down from a, filtered by E::A.
1864 let mut po = Vec::new();
1865 let mut dfs = Dfs::new(&ef_a, a);
1866 while let Some(next_n_ix) = dfs.next(&ef_a) {
1867 po.push(next_n_ix);
1868 }
1869 assert_eq!(set(po), set(vec![a, b, c]));
1870
1871 // Reversed DFS from f, filtered by E::A.
1872 let mut dfs = Dfs::new(&Reversed(&ef_a), f);
1873 let mut po = Vec::new();
1874 while let Some(next_n_ix) = dfs.next(&Reversed(&ef_a)) {
1875 po.push(next_n_ix);
1876 }
1877 assert_eq!(set(po), set(vec![d, e, f]));
1878
1879 // Reversed DFS from j, filtered by E::A.
1880 let mut dfs = Dfs::new(&Reversed(&ef_a), j);
1881 let mut po = Vec::new();
1882 while let Some(next_n_ix) = dfs.next(&Reversed(&ef_a)) {
1883 po.push(next_n_ix);
1884 }
1885 assert_eq!(set(po), set(vec![d, e, i, j]));
1886
1887 // Reversed DFS from c, filtered by E::A.
1888 let mut dfs = Dfs::new(&Reversed(&ef_a), c);
1889 let mut po = Vec::new();
1890 while let Some(next_n_ix) = dfs.next(&Reversed(&ef_a)) {
1891 po.push(next_n_ix);
1892 }
1893 assert_eq!(set(po), set(vec![a, b, c]));
1894
1895 // Reversed DFS from c, filtered by E::B.
1896 let mut dfs = Dfs::new(&Reversed(&ef_b), c);
1897 let mut po = Vec::new();
1898 while let Some(next_n_ix) = dfs.next(&Reversed(&ef_b)) {
1899 po.push(next_n_ix);
1900 }
1901 assert_eq!(set(po), set(vec![c]));
1902
1903 // Reversed DFS from d, filtered by E::B.
1904 let mut dfs = Dfs::new(&Reversed(&ef_b), d);
1905 let mut po = Vec::new();
1906 while let Some(next_n_ix) = dfs.next(&Reversed(&ef_b)) {
1907 po.push(next_n_ix);
1908 }
1909 assert_eq!(set(po), set(vec![c, d]));
1910
1911 // Now let's test the same graph but undirected
1912
1913 let mut g = Graph::new_undirected();
1914 let a = g.add_node("A");
1915 let b = g.add_node("B");
1916 let c = g.add_node("C");
1917 let d = g.add_node("D");
1918 let e = g.add_node("E");
1919 let f = g.add_node("F");
1920 let h = g.add_node("H");
1921 let i = g.add_node("I");
1922 let j = g.add_node("J");
1923
1924 g.add_edge(a, b, E::A);
1925 g.add_edge(b, c, E::A);
1926 g.add_edge(c, d, E::B);
1927 g.add_edge(d, e, E::A);
1928 g.add_edge(e, f, E::A);
1929 g.add_edge(e, h, E::A);
1930 g.add_edge(e, i, E::A);
1931 g.add_edge(i, j, E::A);
1932
1933 let ef_a = EdgeFiltered::from_fn(&g, |edge| *edge.weight() == E::A);
1934 let ef_b = EdgeFiltered::from_fn(&g, |edge| *edge.weight() == E::B);
1935 let mut po = Vec::new();
1936 let mut dfs = Dfs::new(&Reversed(&ef_b), d);
1937 while let Some(next_n_ix) = dfs.next(&Reversed(&ef_b)) {
1938 po.push(next_n_ix);
1939 }
1940 assert_eq!(set(po), set(vec![c, d]));
1941
1942 let mut po = Vec::new();
1943 let mut dfs = Dfs::new(&Reversed(&ef_a), h);
1944 while let Some(next_n_ix) = dfs.next(&Reversed(&ef_a)) {
1945 po.push(next_n_ix);
1946 }
1947 assert_eq!(set(po), set(vec![d, e, f, h, i, j]));
1948 }
1949
1950 #[test]
dfs_visit()1951 fn dfs_visit() {
1952 use petgraph::visit::Control;
1953 use petgraph::visit::DfsEvent::*;
1954 use petgraph::visit::{depth_first_search, Time};
1955 use petgraph::visit::{VisitMap, Visitable};
1956 let gr: Graph<(), ()> = Graph::from_edges(&[
1957 (0, 5),
1958 (0, 2),
1959 (0, 3),
1960 (0, 1),
1961 (1, 3),
1962 (2, 3),
1963 (2, 4),
1964 (4, 0),
1965 (4, 5),
1966 ]);
1967
1968 let invalid_time = Time(!0);
1969 let mut discover_time = vec![invalid_time; gr.node_count()];
1970 let mut finish_time = vec![invalid_time; gr.node_count()];
1971 let mut has_tree_edge = gr.visit_map();
1972 let mut edges = HashSet::new();
1973 depth_first_search(&gr, Some(n(0)), |evt| {
1974 println!("Event: {:?}", evt);
1975 match evt {
1976 Discover(n, t) => discover_time[n.index()] = t,
1977 Finish(n, t) => finish_time[n.index()] = t,
1978 TreeEdge(u, v) => {
1979 // v is an ancestor of u
1980 assert!(has_tree_edge.visit(v), "Two tree edges to {:?}!", v);
1981 assert!(discover_time[v.index()] == invalid_time);
1982 assert!(discover_time[u.index()] != invalid_time);
1983 assert!(finish_time[u.index()] == invalid_time);
1984 edges.insert((u, v));
1985 }
1986 BackEdge(u, v) => {
1987 // u is an ancestor of v
1988 assert!(discover_time[v.index()] != invalid_time);
1989 assert!(finish_time[v.index()] == invalid_time);
1990 edges.insert((u, v));
1991 }
1992 CrossForwardEdge(u, v) => {
1993 edges.insert((u, v));
1994 }
1995 }
1996 });
1997 assert!(discover_time.iter().all(|x| *x != invalid_time));
1998 assert!(finish_time.iter().all(|x| *x != invalid_time));
1999 assert_eq!(edges.len(), gr.edge_count());
2000 assert_eq!(
2001 edges,
2002 set(gr.edge_references().map(|e| (e.source(), e.target())))
2003 );
2004 println!("{:?}", discover_time);
2005 println!("{:?}", finish_time);
2006
2007 // find path from 0 to 4
2008 let mut predecessor = vec![NodeIndex::end(); gr.node_count()];
2009 let start = n(0);
2010 let goal = n(4);
2011 let ret = depth_first_search(&gr, Some(start), |event| {
2012 if let TreeEdge(u, v) = event {
2013 predecessor[v.index()] = u;
2014 if v == goal {
2015 return Control::Break(u);
2016 }
2017 }
2018 Control::Continue
2019 });
2020 // assert we did terminate early
2021 assert!(ret.break_value().is_some());
2022 assert!(predecessor.iter().any(|x| *x == NodeIndex::end()));
2023
2024 let mut next = goal;
2025 let mut path = vec![next];
2026 while next != start {
2027 let pred = predecessor[next.index()];
2028 path.push(pred);
2029 next = pred;
2030 }
2031 path.reverse();
2032 assert_eq!(&path, &[n(0), n(2), n(4)]);
2033
2034 // check that if we prune 2, we never see 4.
2035 let start = n(0);
2036 let prune = n(2);
2037 let nongoal = n(4);
2038 let ret = depth_first_search(&gr, Some(start), |event| {
2039 if let Discover(n, _) = event {
2040 if n == prune {
2041 return Control::Prune;
2042 }
2043 } else if let TreeEdge(u, v) = event {
2044 if v == nongoal {
2045 return Control::Break(u);
2046 }
2047 }
2048 Control::Continue
2049 });
2050 assert!(ret.break_value().is_none());
2051 }
2052
2053 #[test]
filtered_post_order()2054 fn filtered_post_order() {
2055 use petgraph::visit::NodeFiltered;
2056
2057 let mut gr: Graph<(), ()> =
2058 Graph::from_edges(&[(0, 2), (1, 2), (0, 3), (1, 4), (2, 4), (4, 5), (3, 5)]);
2059 // map reachable nodes
2060 let mut dfs = Dfs::new(&gr, n(0));
2061 while let Some(_) = dfs.next(&gr) {}
2062
2063 let map = dfs.discovered;
2064 gr.add_edge(n(0), n(1), ());
2065 let mut po = Vec::new();
2066 let mut dfs = DfsPostOrder::new(&gr, n(0));
2067 let f = NodeFiltered(&gr, map);
2068 while let Some(n) = dfs.next(&f) {
2069 po.push(n);
2070 }
2071 assert!(!po.contains(&n(1)));
2072 }
2073
2074 #[test]
filter_elements()2075 fn filter_elements() {
2076 use petgraph::data::Element::{Edge, Node};
2077 use petgraph::data::ElementIterator;
2078 use petgraph::data::FromElements;
2079 let elements = vec![
2080 Node { weight: "A" },
2081 Node { weight: "B" },
2082 Node { weight: "C" },
2083 Node { weight: "D" },
2084 Node { weight: "E" },
2085 Node { weight: "F" },
2086 Edge {
2087 source: 0,
2088 target: 1,
2089 weight: 7,
2090 },
2091 Edge {
2092 source: 2,
2093 target: 0,
2094 weight: 9,
2095 },
2096 Edge {
2097 source: 0,
2098 target: 3,
2099 weight: 14,
2100 },
2101 Edge {
2102 source: 1,
2103 target: 2,
2104 weight: 10,
2105 },
2106 Edge {
2107 source: 3,
2108 target: 2,
2109 weight: 2,
2110 },
2111 Edge {
2112 source: 3,
2113 target: 4,
2114 weight: 9,
2115 },
2116 Edge {
2117 source: 1,
2118 target: 5,
2119 weight: 15,
2120 },
2121 Edge {
2122 source: 2,
2123 target: 5,
2124 weight: 11,
2125 },
2126 Edge {
2127 source: 4,
2128 target: 5,
2129 weight: 6,
2130 },
2131 ];
2132 let mut g = DiGraph::<_, _>::from_elements(elements.iter().cloned());
2133 println!("{:#?}", g);
2134 assert!(g.contains_edge(n(1), n(5)));
2135 let g2 =
2136 DiGraph::<_, _>::from_elements(elements.iter().cloned().filter_elements(|elt| match elt {
2137 Node { ref weight } if **weight == "B" => false,
2138 _ => true,
2139 }));
2140 println!("{:#?}", g2);
2141 g.remove_node(n(1));
2142 assert!(is_isomorphic_matching(
2143 &g,
2144 &g2,
2145 PartialEq::eq,
2146 PartialEq::eq
2147 ));
2148 }
2149
2150 #[test]
test_edge_filtered()2151 fn test_edge_filtered() {
2152 use petgraph::algo::connected_components;
2153 use petgraph::visit::EdgeFiltered;
2154 use petgraph::visit::IntoEdgeReferences;
2155
2156 let gr = UnGraph::<(), _>::from_edges(&[
2157 // cycle
2158 (0, 1, 7),
2159 (1, 2, 9),
2160 (2, 1, 14),
2161 // cycle
2162 (3, 4, 10),
2163 (4, 5, 2),
2164 (5, 3, 9),
2165 // cross edges
2166 (0, 3, -1),
2167 (1, 4, -2),
2168 (2, 5, -3),
2169 ]);
2170 assert_eq!(connected_components(&gr), 1);
2171 let positive_edges = EdgeFiltered::from_fn(&gr, |edge| *edge.weight() >= 0);
2172 assert_eq!(positive_edges.edge_references().count(), 6);
2173 assert!(positive_edges
2174 .edge_references()
2175 .all(|edge| *edge.weight() >= 0));
2176 assert_eq!(connected_components(&positive_edges), 2);
2177
2178 let mut dfs = DfsPostOrder::new(&positive_edges, n(0));
2179 while let Some(_) = dfs.next(&positive_edges) {}
2180
2181 let n = n::<u32>;
2182 for node in &[n(0), n(1), n(2)] {
2183 assert!(dfs.discovered.is_visited(node));
2184 }
2185 for node in &[n(3), n(4), n(5)] {
2186 assert!(!dfs.discovered.is_visited(node));
2187 }
2188 }
2189
2190 #[test]
test_dominators_simple_fast()2191 fn test_dominators_simple_fast() {
2192 // Construct the following graph:
2193 //
2194 // .-----.
2195 // | <--------------------------------.
2196 // .--------+--------------| r |--------------. |
2197 // | | | | | |
2198 // | | '-----' | |
2199 // | .--V--. .--V--. |
2200 // | | | | | |
2201 // | | b | | c |--------. |
2202 // | | | | | | |
2203 // | '-----' '-----' | |
2204 // .--V--. | | .--V--. |
2205 // | | | | | | |
2206 // | a <-----+ | .----| g | |
2207 // | | | .----' | | | |
2208 // '-----' | | | '-----' |
2209 // | | | | | |
2210 // .--V--. | .-----. .--V--. | | |
2211 // | | | | | | | | | |
2212 // | d <-----+----> e <----. | f | | | |
2213 // | | | | | | | | | |
2214 // '-----' '-----' | '-----' | | |
2215 // | .-----. | | | | .--V--. |
2216 // | | | | | | .-' | | |
2217 // '-----> l | | | | | | j | |
2218 // | | '--. | | | | | |
2219 // '-----' | | | | '-----' |
2220 // | .--V--. | | .--V--. | |
2221 // | | | | | | | | |
2222 // '-------> h |-' '---> i <------' |
2223 // | | .---------> | |
2224 // '-----' | '-----' |
2225 // | .-----. | |
2226 // | | | | |
2227 // '----------> k <---------' |
2228 // | | |
2229 // '-----' |
2230 // | |
2231 // '----------------------------'
2232 //
2233 // This graph has the following dominator tree:
2234 //
2235 // r
2236 // |-- a
2237 // |-- b
2238 // |-- c
2239 // | |-- f
2240 // | `-- g
2241 // | `-- j
2242 // |-- d
2243 // | `-- l
2244 // |-- e
2245 // |-- i
2246 // |-- k
2247 // `-- h
2248 //
2249 // This graph and dominator tree are taken from figures 1 and 2 of "A Fast
2250 // Algorithm for Finding Dominators in a Flowgraph" by Lengauer et al:
2251 // http://www.cs.princeton.edu/courses/archive/spr03/cs423/download/dominators.pdf.
2252
2253 let mut graph = DiGraph::<_, _>::new();
2254
2255 let r = graph.add_node("r");
2256 let a = graph.add_node("a");
2257 let b = graph.add_node("b");
2258 let c = graph.add_node("c");
2259 let d = graph.add_node("d");
2260 let e = graph.add_node("e");
2261 let f = graph.add_node("f");
2262 let g = graph.add_node("g");
2263 let h = graph.add_node("h");
2264 let i = graph.add_node("i");
2265 let j = graph.add_node("j");
2266 let k = graph.add_node("k");
2267 let l = graph.add_node("l");
2268
2269 graph.add_edge(r, a, ());
2270 graph.add_edge(r, b, ());
2271 graph.add_edge(r, c, ());
2272 graph.add_edge(a, d, ());
2273 graph.add_edge(b, a, ());
2274 graph.add_edge(b, d, ());
2275 graph.add_edge(b, e, ());
2276 graph.add_edge(c, f, ());
2277 graph.add_edge(c, g, ());
2278 graph.add_edge(d, l, ());
2279 graph.add_edge(e, h, ());
2280 graph.add_edge(f, i, ());
2281 graph.add_edge(g, i, ());
2282 graph.add_edge(g, j, ());
2283 graph.add_edge(h, e, ());
2284 graph.add_edge(h, k, ());
2285 graph.add_edge(i, k, ());
2286 graph.add_edge(j, i, ());
2287 graph.add_edge(k, r, ());
2288 graph.add_edge(k, i, ());
2289 graph.add_edge(l, h, ());
2290
2291 let doms = dominators::simple_fast(&graph, r);
2292
2293 assert_eq!(doms.root(), r);
2294 assert_eq!(
2295 doms.immediate_dominator(r),
2296 None,
2297 "The root node has no idom"
2298 );
2299
2300 assert_eq!(
2301 doms.immediate_dominator(a),
2302 Some(r),
2303 "r is the immediate dominator of a"
2304 );
2305 assert_eq!(
2306 doms.immediate_dominator(b),
2307 Some(r),
2308 "r is the immediate dominator of b"
2309 );
2310 assert_eq!(
2311 doms.immediate_dominator(c),
2312 Some(r),
2313 "r is the immediate dominator of c"
2314 );
2315 assert_eq!(
2316 doms.immediate_dominator(f),
2317 Some(c),
2318 "c is the immediate dominator of f"
2319 );
2320 assert_eq!(
2321 doms.immediate_dominator(g),
2322 Some(c),
2323 "c is the immediate dominator of g"
2324 );
2325 assert_eq!(
2326 doms.immediate_dominator(j),
2327 Some(g),
2328 "g is the immediate dominator of j"
2329 );
2330 assert_eq!(
2331 doms.immediate_dominator(d),
2332 Some(r),
2333 "r is the immediate dominator of d"
2334 );
2335 assert_eq!(
2336 doms.immediate_dominator(l),
2337 Some(d),
2338 "d is the immediate dominator of l"
2339 );
2340 assert_eq!(
2341 doms.immediate_dominator(e),
2342 Some(r),
2343 "r is the immediate dominator of e"
2344 );
2345 assert_eq!(
2346 doms.immediate_dominator(i),
2347 Some(r),
2348 "r is the immediate dominator of i"
2349 );
2350 assert_eq!(
2351 doms.immediate_dominator(k),
2352 Some(r),
2353 "r is the immediate dominator of k"
2354 );
2355 assert_eq!(
2356 doms.immediate_dominator(h),
2357 Some(r),
2358 "r is the immediate dominator of h"
2359 );
2360
2361 let mut graph = graph.clone();
2362 let z = graph.add_node("z");
2363 let doms = dominators::simple_fast(&graph, r);
2364 assert_eq!(
2365 doms.immediate_dominator(z),
2366 None,
2367 "nodes that aren't reachable from the root do not have an idom"
2368 );
2369 }
2370