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