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