summaryrefslogtreecommitdiff
path: root/vendor/petgraph-0.6.5/tests/graph.rs
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/petgraph-0.6.5/tests/graph.rs')
-rw-r--r--vendor/petgraph-0.6.5/tests/graph.rs2452
1 files changed, 0 insertions, 2452 deletions
diff --git a/vendor/petgraph-0.6.5/tests/graph.rs b/vendor/petgraph-0.6.5/tests/graph.rs
deleted file mode 100644
index de943b47..00000000
--- a/vendor/petgraph-0.6.5/tests/graph.rs
+++ /dev/null
@@ -1,2452 +0,0 @@
-extern crate petgraph;
-
-use std::collections::HashSet;
-use std::hash::Hash;
-
-use petgraph::prelude::*;
-use petgraph::EdgeType;
-
-use petgraph as pg;
-
-use petgraph::algo::{
- dominators, has_path_connecting, is_bipartite_undirected, is_cyclic_undirected,
- is_isomorphic_matching,
-};
-
-use petgraph::graph::node_index as n;
-use petgraph::graph::IndexType;
-
-use petgraph::algo::{astar, dijkstra, DfsSpace};
-use petgraph::visit::{
- IntoEdges, IntoEdgesDirected, IntoNeighbors, IntoNodeIdentifiers, NodeFiltered, Reversed, Topo,
- VisitMap, Walker,
-};
-
-use petgraph::dot::Dot;
-
-fn set<I>(iter: I) -> HashSet<I::Item>
-where
- I: IntoIterator,
- I::Item: Hash + Eq,
-{
- iter.into_iter().collect()
-}
-
-#[test]
-fn undirected() {
- let mut og = Graph::new_undirected();
- let a = og.add_node(0);
- let b = og.add_node(1);
- let c = og.add_node(2);
- let d = og.add_node(3);
- let _ = og.add_edge(a, b, 0);
- let _ = og.add_edge(a, c, 1);
- og.add_edge(c, a, 2);
- og.add_edge(a, a, 3);
- og.add_edge(b, c, 4);
- og.add_edge(b, a, 5);
- og.add_edge(a, d, 6);
- assert_eq!(og.node_count(), 4);
- assert_eq!(og.edge_count(), 7);
-
- assert!(og.find_edge(a, b).is_some());
- assert!(og.find_edge(d, a).is_some());
- assert!(og.find_edge(a, a).is_some());
-
- for edge in og.raw_edges() {
- assert!(og.find_edge(edge.source(), edge.target()).is_some());
- assert!(og.find_edge(edge.target(), edge.source()).is_some());
- }
-
- assert_eq!(og.neighbors(b).collect::<Vec<_>>(), vec![a, c, a]);
-
- og.remove_node(a);
- assert_eq!(og.neighbors(b).collect::<Vec<_>>(), vec![c]);
- assert_eq!(og.node_count(), 3);
- assert_eq!(og.edge_count(), 1);
- assert!(og.find_edge(a, b).is_none());
- assert!(og.find_edge(d, a).is_none());
- assert!(og.find_edge(a, a).is_none());
- assert!(og.find_edge(b, c).is_some());
- assert_graph_consistent(&og);
-}
-
-#[test]
-fn dfs() {
- let mut gr = Graph::new();
- let h = gr.add_node("H");
- let i = gr.add_node("I");
- let j = gr.add_node("J");
- let k = gr.add_node("K");
- // Z is disconnected.
- let _ = gr.add_node("Z");
- gr.add_edge(h, i, 1.);
- gr.add_edge(h, j, 3.);
- gr.add_edge(i, j, 1.);
- gr.add_edge(i, k, 2.);
-
- println!("{}", Dot::new(&gr));
-
- assert_eq!(Dfs::new(&gr, h).iter(&gr).count(), 4);
- assert_eq!(Dfs::new(&gr, h).iter(&gr).clone().count(), 4);
-
- assert_eq!(Dfs::new(&gr, h).iter(Reversed(&gr)).count(), 1);
-
- assert_eq!(Dfs::new(&gr, k).iter(Reversed(&gr)).count(), 3);
-
- assert_eq!(Dfs::new(&gr, i).iter(&gr).count(), 3);
-}
-
-#[test]
-fn dfs_order() {
- let mut gr = Graph::new();
- let h = gr.add_node("H");
- let i = gr.add_node("I");
- let j = gr.add_node("J");
- let k = gr.add_node("K");
- gr.add_edge(h, i, ());
- gr.add_edge(h, j, ());
- gr.add_edge(h, k, ());
- gr.add_edge(i, k, ());
- gr.add_edge(k, i, ());
-
- // H
- // / | \
- // I J K
- // \___/
- //
- // J cannot be visited between I and K in a depth-first search from H
-
- let mut seen_i = false;
- let mut seen_k = false;
- for node in Dfs::new(&gr, h).iter(&gr) {
- seen_i |= i == node;
- seen_k |= k == node;
- assert!(!(j == node && (seen_i ^ seen_k)), "Invalid DFS order");
- }
-}
-
-#[test]
-fn bfs() {
- let mut gr = Graph::new();
- let h = gr.add_node("H");
- let i = gr.add_node("I");
- let j = gr.add_node("J");
- let k = gr.add_node("K");
- // Z is disconnected.
- let _ = gr.add_node("Z");
- gr.add_edge(h, i, 1.);
- gr.add_edge(h, j, 3.);
- gr.add_edge(i, j, 1.);
- gr.add_edge(i, k, 2.);
-
- assert_eq!(Bfs::new(&gr, h).iter(&gr).count(), 4);
- assert_eq!(Bfs::new(&gr, h).iter(&gr).clone().count(), 4);
-
- assert_eq!(Bfs::new(&gr, h).iter(Reversed(&gr)).count(), 1);
-
- assert_eq!(Bfs::new(&gr, k).iter(Reversed(&gr)).count(), 3);
-
- assert_eq!(Bfs::new(&gr, i).iter(&gr).count(), 3);
-
- let mut bfs = Bfs::new(&gr, h);
- let nx = bfs.next(&gr);
- assert_eq!(nx, Some(h));
-
- let nx1 = bfs.next(&gr);
- assert!(nx1 == Some(i) || nx1 == Some(j));
-
- let nx2 = bfs.next(&gr);
- assert!(nx2 == Some(i) || nx2 == Some(j));
- assert!(nx1 != nx2);
-
- let nx = bfs.next(&gr);
- assert_eq!(nx, Some(k));
- assert_eq!(bfs.next(&gr), None);
-}
-
-#[test]
-fn selfloop() {
- let mut gr = Graph::new();
- let a = gr.add_node("A");
- let b = gr.add_node("B");
- let c = gr.add_node("C");
- gr.add_edge(a, b, 7.);
- gr.add_edge(c, a, 6.);
- let sed = gr.add_edge(a, a, 2.);
-
- assert!(gr.find_edge(a, b).is_some());
- assert!(gr.find_edge(b, a).is_none());
- assert!(gr.find_edge_undirected(b, a).is_some());
- assert!(gr.find_edge(a, a).is_some());
- println!("{:?}", gr);
-
- gr.remove_edge(sed);
- assert!(gr.find_edge(a, a).is_none());
- println!("{:?}", gr);
-}
-
-#[test]
-fn cyclic() {
- let mut gr = Graph::new();
- let a = gr.add_node("A");
- let b = gr.add_node("B");
- let c = gr.add_node("C");
-
- assert!(!is_cyclic_undirected(&gr));
- gr.add_edge(a, b, 7.);
- gr.add_edge(c, a, 6.);
- assert!(!is_cyclic_undirected(&gr));
- {
- let e = gr.add_edge(a, a, 0.);
- assert!(is_cyclic_undirected(&gr));
- gr.remove_edge(e);
- assert!(!is_cyclic_undirected(&gr));
- }
-
- {
- let e = gr.add_edge(b, c, 0.);
- assert!(is_cyclic_undirected(&gr));
- gr.remove_edge(e);
- assert!(!is_cyclic_undirected(&gr));
- }
-
- let d = gr.add_node("D");
- let e = gr.add_node("E");
- gr.add_edge(b, d, 0.);
- gr.add_edge(d, e, 0.);
- assert!(!is_cyclic_undirected(&gr));
- gr.add_edge(c, e, 0.);
- assert!(is_cyclic_undirected(&gr));
- assert_graph_consistent(&gr);
-}
-
-#[test]
-fn bipartite() {
- {
- let mut gr = Graph::new_undirected();
- let a = gr.add_node("A");
- let b = gr.add_node("B");
- let c = gr.add_node("C");
-
- let d = gr.add_node("D");
- let e = gr.add_node("E");
- let f = gr.add_node("F");
-
- gr.add_edge(a, d, 7.);
- gr.add_edge(b, d, 6.);
-
- assert!(is_bipartite_undirected(&gr, a));
-
- let e_index = gr.add_edge(a, b, 6.);
-
- assert!(!is_bipartite_undirected(&gr, a));
-
- gr.remove_edge(e_index);
-
- assert!(is_bipartite_undirected(&gr, a));
-
- gr.add_edge(b, e, 7.);
- gr.add_edge(b, f, 6.);
- gr.add_edge(c, e, 6.);
-
- assert!(is_bipartite_undirected(&gr, a));
- }
- {
- let mut gr = Graph::new_undirected();
- let a = gr.add_node("A");
- let b = gr.add_node("B");
- let c = gr.add_node("C");
- let d = gr.add_node("D");
- let e = gr.add_node("E");
-
- let f = gr.add_node("F");
- let g = gr.add_node("G");
- let h = gr.add_node("H");
-
- gr.add_edge(a, f, 7.);
- gr.add_edge(a, g, 7.);
- gr.add_edge(a, h, 7.);
-
- gr.add_edge(b, f, 6.);
- gr.add_edge(b, g, 6.);
- gr.add_edge(b, h, 6.);
-
- gr.add_edge(c, f, 6.);
- gr.add_edge(c, g, 6.);
- gr.add_edge(c, h, 6.);
-
- gr.add_edge(d, f, 6.);
- gr.add_edge(d, g, 6.);
- gr.add_edge(d, h, 6.);
-
- gr.add_edge(e, f, 6.);
- gr.add_edge(e, g, 6.);
- gr.add_edge(e, h, 6.);
-
- assert!(is_bipartite_undirected(&gr, a));
-
- gr.add_edge(a, b, 6.);
-
- assert!(!is_bipartite_undirected(&gr, a));
- }
-}
-
-#[test]
-fn multi() {
- let mut gr = Graph::new();
- let a = gr.add_node("a");
- let b = gr.add_node("b");
- gr.add_edge(a, b, ());
- gr.add_edge(a, b, ());
- assert_eq!(gr.edge_count(), 2);
-}
-
-#[test]
-fn iter_multi_edges() {
- let mut gr = Graph::new();
- let a = gr.add_node("a");
- let b = gr.add_node("b");
- let c = gr.add_node("c");
-
- let mut connecting_edges = HashSet::new();
-
- gr.add_edge(a, a, ());
- connecting_edges.insert(gr.add_edge(a, b, ()));
- gr.add_edge(a, c, ());
- gr.add_edge(c, b, ());
- connecting_edges.insert(gr.add_edge(a, b, ()));
- gr.add_edge(b, a, ());
-
- let mut iter = gr.edges_connecting(a, b);
-
- let edge_id = iter.next().unwrap().id();
- assert!(connecting_edges.contains(&edge_id));
- connecting_edges.remove(&edge_id);
-
- let edge_id = iter.next().unwrap().id();
- assert!(connecting_edges.contains(&edge_id));
- connecting_edges.remove(&edge_id);
-
- assert_eq!(None, iter.next());
- assert!(connecting_edges.is_empty());
-}
-
-#[test]
-fn iter_multi_undirected_edges() {
- let mut gr = Graph::new_undirected();
- let a = gr.add_node("a");
- let b = gr.add_node("b");
- let c = gr.add_node("c");
-
- let mut connecting_edges = HashSet::new();
-
- gr.add_edge(a, a, ());
- connecting_edges.insert(gr.add_edge(a, b, ()));
- gr.add_edge(a, c, ());
- gr.add_edge(c, b, ());
- connecting_edges.insert(gr.add_edge(a, b, ()));
- connecting_edges.insert(gr.add_edge(b, a, ()));
-
- let mut iter = gr.edges_connecting(a, b);
-
- let edge_id = iter.next().unwrap().id();
- assert!(connecting_edges.contains(&edge_id));
- connecting_edges.remove(&edge_id);
-
- let edge_id = iter.next().unwrap().id();
- assert!(connecting_edges.contains(&edge_id));
- connecting_edges.remove(&edge_id);
-
- let edge_id = iter.next().unwrap().id();
- assert!(connecting_edges.contains(&edge_id));
- connecting_edges.remove(&edge_id);
-
- assert_eq!(None, iter.next());
- assert!(connecting_edges.is_empty());
-}
-
-#[test]
-fn update_edge() {
- {
- let mut gr = Graph::new();
- let a = gr.add_node("a");
- let b = gr.add_node("b");
- let e = gr.update_edge(a, b, 1);
- let f = gr.update_edge(a, b, 2);
- let _ = gr.update_edge(b, a, 3);
- assert_eq!(gr.edge_count(), 2);
- assert_eq!(e, f);
- assert_eq!(*gr.edge_weight(f).unwrap(), 2);
- }
-
- {
- let mut gr = Graph::new_undirected();
- let a = gr.add_node("a");
- let b = gr.add_node("b");
- let e = gr.update_edge(a, b, 1);
- let f = gr.update_edge(b, a, 2);
- assert_eq!(gr.edge_count(), 1);
- assert_eq!(e, f);
- assert_eq!(*gr.edge_weight(f).unwrap(), 2);
- }
-}
-
-#[test]
-fn dijk() {
- let mut g = Graph::new_undirected();
- let a = g.add_node("A");
- let b = g.add_node("B");
- let c = g.add_node("C");
- let d = g.add_node("D");
- let e = g.add_node("E");
- let f = g.add_node("F");
- g.add_edge(a, b, 7);
- g.add_edge(c, a, 9);
- g.add_edge(a, d, 14);
- g.add_edge(b, c, 10);
- g.add_edge(d, c, 2);
- g.add_edge(d, e, 9);
- g.add_edge(b, f, 15);
- g.add_edge(c, f, 11);
- g.add_edge(e, f, 6);
- println!("{:?}", g);
- for no in Bfs::new(&g, a).iter(&g) {
- println!("Visit {:?} = {:?}", no, g.node_weight(no));
- }
-
- let scores = dijkstra(&g, a, None, |e| *e.weight());
- let mut scores: Vec<_> = scores.into_iter().map(|(n, s)| (g[n], s)).collect();
- scores.sort();
- assert_eq!(
- scores,
- vec![
- ("A", 0),
- ("B", 7),
- ("C", 9),
- ("D", 11),
- ("E", 20),
- ("F", 20)
- ]
- );
-
- let scores = dijkstra(&g, a, Some(c), |e| *e.weight());
- assert_eq!(scores[&c], 9);
-}
-
-#[test]
-fn test_astar_null_heuristic() {
- let mut g = Graph::new();
- let a = g.add_node("A");
- let b = g.add_node("B");
- let c = g.add_node("C");
- let d = g.add_node("D");
- let e = g.add_node("E");
- let f = g.add_node("F");
- g.add_edge(a, b, 7);
- g.add_edge(c, a, 9);
- g.add_edge(a, d, 14);
- g.add_edge(b, c, 10);
- g.add_edge(d, c, 2);
- g.add_edge(d, e, 9);
- g.add_edge(b, f, 15);
- g.add_edge(c, f, 11);
- g.add_edge(e, f, 6);
-
- let path = astar(&g, a, |finish| finish == e, |e| *e.weight(), |_| 0);
- assert_eq!(path, Some((23, vec![a, d, e])));
-
- // check against dijkstra
- let dijkstra_run = dijkstra(&g, a, Some(e), |e| *e.weight());
- assert_eq!(dijkstra_run[&e], 23);
-
- let path = astar(&g, e, |finish| finish == b, |e| *e.weight(), |_| 0);
- assert_eq!(path, None);
-}
-
-#[test]
-fn test_astar_manhattan_heuristic() {
- let mut g = Graph::new();
- let a = g.add_node((0., 0.));
- let b = g.add_node((2., 0.));
- let c = g.add_node((1., 1.));
- let d = g.add_node((0., 2.));
- let e = g.add_node((3., 3.));
- let f = g.add_node((4., 2.));
- let _ = g.add_node((5., 5.)); // no path to node
- g.add_edge(a, b, 2.);
- g.add_edge(a, d, 4.);
- g.add_edge(b, c, 1.);
- g.add_edge(b, f, 7.);
- g.add_edge(c, e, 5.);
- g.add_edge(e, f, 1.);
- g.add_edge(d, e, 1.);
-
- let heuristic_for = |f: NodeIndex| {
- let g = &g;
- move |node: NodeIndex| -> f32 {
- let (x1, y1): (f32, f32) = g[node];
- let (x2, y2): (f32, f32) = g[f];
-
- (x2 - x1).abs() + (y2 - y1).abs()
- }
- };
- let path = astar(
- &g,
- a,
- |finish| finish == f,
- |e| *e.weight(),
- heuristic_for(f),
- );
-
- assert_eq!(path, Some((6., vec![a, d, e, f])));
-
- // check against dijkstra
- let dijkstra_run = dijkstra(&g, a, None, |e| *e.weight());
-
- for end in g.node_indices() {
- let astar_path = astar(
- &g,
- a,
- |finish| finish == end,
- |e| *e.weight(),
- heuristic_for(end),
- );
- assert_eq!(dijkstra_run.get(&end).cloned(), astar_path.map(|t| t.0));
- }
-}
-
-#[test]
-fn test_astar_runtime_optimal() {
- let mut g = Graph::new();
- let a = g.add_node("A");
- let b = g.add_node("B");
- let c = g.add_node("C");
- let d = g.add_node("D");
- let e = g.add_node("E");
- g.add_edge(a, b, 2);
- g.add_edge(a, c, 3);
- g.add_edge(b, d, 3);
- g.add_edge(c, d, 1);
- g.add_edge(d, e, 1);
-
- let mut times_called = 0;
-
- let _ = astar(
- &g,
- a,
- |n| n == e,
- |edge| {
- times_called += 1;
- *edge.weight()
- },
- |_| 0,
- );
-
- // A* is runtime optimal in the sense it won't expand more nodes than needed, for the given
- // heuristic. Here, A* should expand, in order: A, B, C, D, E. This should should ask for the
- // costs of edges (A, B), (A, C), (B, D), (C, D), (D, E). Node D will be added to `visit_next`
- // twice, but should only be expanded once. If it is erroneously expanded twice, it will call
- // for (D, E) again and `times_called` will be 6.
- assert_eq!(times_called, 5);
-}
-
-#[test]
-fn test_astar_admissible_inconsistent() {
- let mut g = Graph::new();
- let a = g.add_node("A");
- let b = g.add_node("B");
- let c = g.add_node("C");
- let d = g.add_node("D");
- g.add_edge(a, b, 3);
- g.add_edge(b, c, 3);
- g.add_edge(c, d, 3);
- g.add_edge(a, c, 8);
- g.add_edge(a, d, 10);
-
- let admissible_inconsistent = |n: NodeIndex| match g[n] {
- "A" => 9,
- "B" => 6,
- "C" => 0,
- &_ => 0,
- };
-
- let optimal = astar(&g, a, |n| n == d, |e| *e.weight(), admissible_inconsistent);
- assert_eq!(optimal, Some((9, vec![a, b, c, d])));
-}
-
-#[cfg(feature = "generate")]
-#[test]
-fn test_generate_undirected() {
- for size in 0..4 {
- let mut gen = pg::generate::Generator::<Undirected>::all(size, true);
- let nedges = (size * size - size) / 2 + size;
- let mut n = 0;
- while let Some(g) = gen.next_ref() {
- n += 1;
- println!("{:?}", g);
- }
-
- assert_eq!(n, 1 << nedges);
- }
-}
-
-#[cfg(feature = "generate")]
-#[test]
-fn test_generate_directed() {
- // Number of DAG out of all graphs (all permutations) per node size
- // 0, 1, 2, 3, 4, 5 ..
- let n_dag = &[1, 1, 3, 25, 543, 29281, 3781503];
- for (size, &dags_exp) in (0..4).zip(n_dag) {
- let mut gen = pg::generate::Generator::<Directed>::all(size, true);
- let nedges = size * size;
- let mut n = 0;
- let mut dags = 0;
- while let Some(g) = gen.next_ref() {
- n += 1;
- if !pg::algo::is_cyclic_directed(g) {
- dags += 1;
- }
- }
-
- /*
- // check that all generated graphs have unique adjacency matrices
- let mut adjmats = graphs.iter().map(Graph::adjacency_matrix).collect::<Vec<_>>();
- adjmats.sort(); adjmats.dedup();
- assert_eq!(adjmats.len(), n);
- */
- assert_eq!(dags_exp, dags);
- assert_eq!(n, 1 << nedges);
- }
-}
-
-#[cfg(feature = "generate")]
-#[test]
-fn test_generate_dag() {
- use petgraph::visit::GetAdjacencyMatrix;
- for size in 1..5 {
- let gen = pg::generate::Generator::directed_acyclic(size);
- let nedges = (size - 1) * size / 2;
- let graphs = gen.collect::<Vec<_>>();
-
- assert_eq!(graphs.len(), 1 << nedges);
-
- // check that all generated graphs have unique adjacency matrices
- let mut adjmats = graphs
- .iter()
- .map(Graph::adjacency_matrix)
- .collect::<Vec<_>>();
- adjmats.sort();
- adjmats.dedup();
- assert_eq!(adjmats.len(), graphs.len());
- for gr in &graphs {
- assert!(
- !petgraph::algo::is_cyclic_directed(gr),
- "Assertion failed: {:?} acyclic",
- gr
- );
- }
- }
-}
-
-#[test]
-fn without() {
- let mut og = Graph::new_undirected();
- let a = og.add_node(0);
- let b = og.add_node(1);
- let c = og.add_node(2);
- let d = og.add_node(3);
- let _ = og.add_edge(a, b, 0);
- let _ = og.add_edge(a, c, 1);
- let v: Vec<NodeIndex> = og.externals(Outgoing).collect();
- assert_eq!(v, vec![d]);
-
- let mut og = Graph::new();
- let a = og.add_node(0);
- let b = og.add_node(1);
- let c = og.add_node(2);
- let d = og.add_node(3);
- let _ = og.add_edge(a, b, 0);
- let _ = og.add_edge(a, c, 1);
- let init: Vec<NodeIndex> = og.externals(Incoming).collect();
- let term: Vec<NodeIndex> = og.externals(Outgoing).collect();
- assert_eq!(init, vec![a, d]);
- assert_eq!(term, vec![b, c, d]);
-}
-
-fn assert_is_topo_order<N, E>(gr: &Graph<N, E, Directed>, order: &[NodeIndex]) {
- assert_eq!(gr.node_count(), order.len());
- // check all the edges of the graph
- for edge in gr.raw_edges() {
- let a = edge.source();
- let b = edge.target();
- let ai = order.iter().position(|x| *x == a).unwrap();
- let bi = order.iter().position(|x| *x == b).unwrap();
- println!("Check that {:?} is before {:?}", a, b);
- assert!(
- ai < bi,
- "Topo order: assertion that node {:?} is before {:?} failed",
- a,
- b
- );
- }
-}
-
-#[test]
-fn test_toposort() {
- let mut gr = Graph::<_, _>::new();
- let a = gr.add_node("A");
- let b = gr.add_node("B");
- let c = gr.add_node("C");
- let d = gr.add_node("D");
- let e = gr.add_node("E");
- let f = gr.add_node("F");
- let g = gr.add_node("G");
- gr.extend_with_edges(&[
- (a, b, 7.),
- (a, d, 5.),
- (d, b, 9.),
- (b, c, 8.),
- (b, e, 7.),
- (c, e, 5.),
- (d, e, 15.),
- (d, f, 6.),
- (f, e, 8.),
- (f, g, 11.),
- (e, g, 9.),
- ]);
-
- // add a disjoint part
- let h = gr.add_node("H");
- let i = gr.add_node("I");
- let j = gr.add_node("J");
- gr.add_edge(h, i, 1.);
- gr.add_edge(h, j, 3.);
- gr.add_edge(i, j, 1.);
-
- let order = petgraph::algo::toposort(&gr, None).unwrap();
- println!("{:?}", order);
- assert_eq!(order.len(), gr.node_count());
-
- assert_is_topo_order(&gr, &order);
-}
-
-#[test]
-fn test_toposort_eq() {
- let mut g = Graph::<_, _>::new();
- let a = g.add_node("A");
- let b = g.add_node("B");
- g.add_edge(a, b, ());
-
- assert_eq!(petgraph::algo::toposort(&g, None), Ok(vec![a, b]));
-}
-
-#[test]
-fn is_cyclic_directed() {
- let mut gr = Graph::<_, _>::new();
- let a = gr.add_node("A");
- let b = gr.add_node("B");
- let c = gr.add_node("C");
- let d = gr.add_node("D");
- let e = gr.add_node("E");
- let f = gr.add_node("F");
- let g = gr.add_node("G");
- gr.add_edge(a, b, 7.0);
- gr.add_edge(a, d, 5.);
- gr.add_edge(d, b, 9.);
- gr.add_edge(b, c, 8.);
- gr.add_edge(b, e, 7.);
- gr.add_edge(c, e, 5.);
- gr.add_edge(d, e, 15.);
- gr.add_edge(d, f, 6.);
- gr.add_edge(f, e, 8.);
- gr.add_edge(f, g, 11.);
- gr.add_edge(e, g, 9.);
-
- assert!(!petgraph::algo::is_cyclic_directed(&gr));
-
- // add a disjoint part
- let h = gr.add_node("H");
- let i = gr.add_node("I");
- let j = gr.add_node("J");
- gr.add_edge(h, i, 1.);
- gr.add_edge(h, j, 3.);
- gr.add_edge(i, j, 1.);
- assert!(!petgraph::algo::is_cyclic_directed(&gr));
-
- gr.add_edge(g, e, 0.);
- assert!(petgraph::algo::is_cyclic_directed(&gr));
-}
-
-/// Compare two scc sets. Inside each scc, the order does not matter,
-/// but the order of the sccs is significant.
-fn assert_sccs_eq(
- mut res: Vec<Vec<NodeIndex>>,
- mut answer: Vec<Vec<NodeIndex>>,
- scc_order_matters: bool,
-) {
- // normalize the result and compare with the answer.
- for scc in &mut res {
- scc.sort();
- }
- for scc in &mut answer {
- scc.sort();
- }
- if !scc_order_matters {
- res.sort();
- answer.sort();
- }
- assert_eq!(res, answer);
-}
-
-#[test]
-fn scc() {
- let gr: Graph<(), ()> = Graph::from_edges(&[
- (6, 0),
- (0, 3),
- (3, 6),
- (8, 6),
- (8, 2),
- (2, 5),
- (5, 8),
- (7, 5),
- (1, 7),
- (7, 4),
- (4, 1),
- ]);
-
- assert_sccs_eq(
- petgraph::algo::kosaraju_scc(&gr),
- vec![
- vec![n(0), n(3), n(6)],
- vec![n(2), n(5), n(8)],
- vec![n(1), n(4), n(7)],
- ],
- true,
- );
- // Reversed edges gives the same sccs (when sorted)
- assert_sccs_eq(
- petgraph::algo::kosaraju_scc(Reversed(&gr)),
- vec![
- vec![n(1), n(4), n(7)],
- vec![n(2), n(5), n(8)],
- vec![n(0), n(3), n(6)],
- ],
- true,
- );
-
- // Test an undirected graph just for fun.
- // Sccs are just connected components.
- let mut hr = gr.into_edge_type::<Undirected>();
- // Delete an edge to disconnect it
- let ed = hr.find_edge(n(6), n(8)).unwrap();
- assert!(hr.remove_edge(ed).is_some());
-
- assert_sccs_eq(
- petgraph::algo::kosaraju_scc(&hr),
- vec![
- vec![n(0), n(3), n(6)],
- vec![n(1), n(2), n(4), n(5), n(7), n(8)],
- ],
- false,
- );
-
- // acyclic non-tree, #14
- let n = NodeIndex::new;
- let mut gr = Graph::new();
- gr.add_node(0);
- gr.add_node(1);
- gr.add_node(2);
- gr.add_node(3);
- gr.add_edge(n(3), n(2), ());
- gr.add_edge(n(3), n(1), ());
- gr.add_edge(n(2), n(0), ());
- gr.add_edge(n(1), n(0), ());
-
- assert_sccs_eq(
- petgraph::algo::kosaraju_scc(&gr),
- vec![vec![n(0)], vec![n(1)], vec![n(2)], vec![n(3)]],
- true,
- );
-
- // Kosaraju bug from PR #60
- let mut gr = Graph::<(), ()>::new();
- gr.extend_with_edges(&[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)]);
- gr.add_node(());
- // no order for the disconnected one
- assert_sccs_eq(
- petgraph::algo::kosaraju_scc(&gr),
- vec![vec![n(0)], vec![n(1)], vec![n(2)], vec![n(3)]],
- false,
- );
-}
-
-#[test]
-fn tarjan_scc() {
- let gr: Graph<(), ()> = Graph::from_edges(&[
- (6, 0),
- (0, 3),
- (3, 6),
- (8, 6),
- (8, 2),
- (2, 5),
- (5, 8),
- (7, 5),
- (1, 7),
- (7, 4),
- (4, 1),
- ]);
-
- let mut tarjan_scc = petgraph::algo::TarjanScc::new();
-
- let mut result = Vec::new();
- tarjan_scc.run(&gr, |scc| result.push(scc.iter().rev().cloned().collect()));
- assert_sccs_eq(
- result,
- vec![
- vec![n(0), n(3), n(6)],
- vec![n(2), n(5), n(8)],
- vec![n(1), n(4), n(7)],
- ],
- true,
- );
-
- // Test an undirected graph just for fun.
- // Sccs are just connected components.
- let mut hr = gr.into_edge_type::<Undirected>();
- // Delete an edge to disconnect it
- let ed = hr.find_edge(n(6), n(8)).unwrap();
- assert!(hr.remove_edge(ed).is_some());
-
- let mut result = Vec::new();
- tarjan_scc.run(&hr, |scc| result.push(scc.iter().rev().cloned().collect()));
- assert_sccs_eq(
- result,
- vec![
- vec![n(1), n(2), n(4), n(5), n(7), n(8)],
- vec![n(0), n(3), n(6)],
- ],
- false,
- );
-
- // acyclic non-tree, #14
- let n = NodeIndex::new;
- let mut gr = Graph::new();
- gr.add_node(0);
- gr.add_node(1);
- gr.add_node(2);
- gr.add_node(3);
- gr.add_edge(n(3), n(2), ());
- gr.add_edge(n(3), n(1), ());
- gr.add_edge(n(2), n(0), ());
- gr.add_edge(n(1), n(0), ());
-
- let mut result = Vec::new();
- tarjan_scc.run(&gr, |scc| result.push(scc.iter().rev().cloned().collect()));
- assert_sccs_eq(
- result,
- vec![vec![n(0)], vec![n(1)], vec![n(2)], vec![n(3)]],
- true,
- );
-
- // Kosaraju bug from PR #60
- let mut gr = Graph::<(), ()>::new();
- gr.extend_with_edges(&[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)]);
- gr.add_node(());
- // no order for the disconnected one
- let mut result = Vec::new();
- tarjan_scc.run(&gr, |scc| result.push(scc.iter().rev().cloned().collect()));
- assert_sccs_eq(
- result,
- vec![vec![n(0)], vec![n(1)], vec![n(2)], vec![n(3)]],
- false,
- );
-}
-
-#[test]
-fn condensation() {
- let gr: Graph<(), ()> = Graph::from_edges(&[
- (6, 0),
- (0, 3),
- (3, 6),
- (8, 6),
- (8, 2),
- (2, 3),
- (2, 5),
- (5, 8),
- (7, 5),
- (1, 7),
- (7, 4),
- (4, 1),
- ]);
-
- // make_acyclic = true
-
- let cond = petgraph::algo::condensation(gr.clone(), true);
-
- assert!(cond.node_count() == 3);
- assert!(cond.edge_count() == 2);
- assert!(
- !petgraph::algo::is_cyclic_directed(&cond),
- "Assertion failed: {:?} acyclic",
- cond
- );
-
- // make_acyclic = false
-
- let cond = petgraph::algo::condensation(gr.clone(), false);
-
- assert!(cond.node_count() == 3);
- assert!(cond.edge_count() == gr.edge_count());
-}
-
-#[test]
-fn connected_comp() {
- let n = NodeIndex::new;
- let mut gr = Graph::new();
- gr.add_node(0);
- gr.add_node(1);
- gr.add_node(2);
- gr.add_node(3);
- gr.add_node(4);
- gr.add_node(5);
- gr.add_node(6);
- gr.add_node(7);
- gr.add_node(8);
- gr.add_edge(n(6), n(0), ());
- gr.add_edge(n(0), n(3), ());
- gr.add_edge(n(3), n(6), ());
- gr.add_edge(n(8), n(6), ());
- gr.add_edge(n(8), n(2), ());
- gr.add_edge(n(2), n(5), ());
- gr.add_edge(n(5), n(8), ());
- gr.add_edge(n(7), n(5), ());
- gr.add_edge(n(1), n(7), ());
- gr.add_edge(n(7), n(4), ());
- gr.add_edge(n(4), n(1), ());
- assert_eq!(petgraph::algo::connected_components(&gr), 1);
-
- gr.add_node(9);
- gr.add_node(10);
- assert_eq!(petgraph::algo::connected_components(&gr), 3);
-
- gr.add_edge(n(9), n(10), ());
- assert_eq!(petgraph::algo::connected_components(&gr), 2);
-
- let gr = gr.into_edge_type::<Undirected>();
- assert_eq!(petgraph::algo::connected_components(&gr), 2);
-}
-
-#[should_panic]
-#[test]
-fn oob_index() {
- let mut gr = Graph::<_, ()>::new();
- let a = gr.add_node(0);
- let b = gr.add_node(1);
- gr.remove_node(a);
- gr[b];
-}
-
-#[test]
-fn usize_index() {
- let mut gr = Graph::<_, _, Directed, usize>::with_capacity(0, 0);
- let a = gr.add_node(0);
- let b = gr.add_node(1);
- let e = gr.add_edge(a, b, 1.2);
- let mut dfs = Dfs::new(&gr, a);
- while let Some(nx) = dfs.next(&gr) {
- gr[nx] += 1;
- }
- assert_eq!(gr[a], 1);
- assert_eq!(gr[b], 2);
- assert_eq!(gr[e], 1.2);
-}
-
-#[test]
-fn u8_index() {
- let mut gr = Graph::<_, (), Undirected, u8>::with_capacity(0, 0);
- for _ in 0..255 {
- gr.add_node(());
- }
-}
-
-#[should_panic]
-#[test]
-fn u8_index_overflow() {
- let mut gr = Graph::<_, (), Undirected, u8>::with_capacity(0, 0);
- for _ in 0..256 {
- gr.add_node(());
- }
-}
-
-#[should_panic]
-#[test]
-fn u8_index_overflow_edges() {
- let mut gr = Graph::<_, (), Undirected, u8>::with_capacity(0, 0);
- let a = gr.add_node('a');
- let b = gr.add_node('b');
- for _ in 0..256 {
- gr.add_edge(a, b, ());
- }
-}
-
-#[test]
-fn test_weight_iterators() {
- let mut gr = Graph::<_, _>::new();
- let a = gr.add_node("A");
- let b = gr.add_node("B");
- let c = gr.add_node("C");
- let d = gr.add_node("D");
- let e = gr.add_node("E");
- let f = gr.add_node("F");
- let g = gr.add_node("G");
- gr.add_edge(a, b, 7.0);
- gr.add_edge(a, d, 5.);
- gr.add_edge(d, b, 9.);
- gr.add_edge(b, c, 8.);
- gr.add_edge(b, e, 7.);
- gr.add_edge(c, e, 5.);
- gr.add_edge(d, e, 15.);
- gr.add_edge(d, f, 6.);
- gr.add_edge(f, e, 8.);
- gr.add_edge(f, g, 11.);
- gr.add_edge(e, g, 9.);
-
- assert_eq!(gr.node_weights_mut().count(), gr.node_count());
- assert_eq!(gr.edge_weights_mut().count(), gr.edge_count());
-
- // add a disjoint part
- let h = gr.add_node("H");
- let i = gr.add_node("I");
- let j = gr.add_node("J");
- gr.add_edge(h, i, 1.);
- gr.add_edge(h, j, 3.);
- gr.add_edge(i, j, 1.);
-
- assert_eq!(gr.node_weights_mut().count(), gr.node_count());
- assert_eq!(gr.edge_weights_mut().count(), gr.edge_count());
-
- for nw in gr.node_weights_mut() {
- *nw = "x";
- }
- for node in gr.raw_nodes() {
- assert_eq!(node.weight, "x");
- }
-
- let old = gr.clone();
- for (index, ew) in gr.edge_weights_mut().enumerate() {
- assert_eq!(old[EdgeIndex::new(index)], *ew);
- *ew = -*ew;
- }
- for (index, edge) in gr.raw_edges().iter().enumerate() {
- assert_eq!(edge.weight, -1. * old[EdgeIndex::new(index)]);
- }
-}
-
-#[test]
-fn walk_edges() {
- let mut gr = Graph::<_, _>::new();
- let a = gr.add_node(0.);
- let b = gr.add_node(1.);
- let c = gr.add_node(2.);
- let d = gr.add_node(3.);
- let e0 = gr.add_edge(a, b, 0.);
- let e1 = gr.add_edge(a, d, 0.);
- let e2 = gr.add_edge(b, c, 0.);
- let e3 = gr.add_edge(c, a, 0.);
-
- // Set edge weights to difference: target - source.
- let mut dfs = Dfs::new(&gr, a);
- while let Some(source) = dfs.next(&gr) {
- let mut edges = gr.neighbors_directed(source, Outgoing).detach();
- while let Some((edge, target)) = edges.next(&gr) {
- gr[edge] = gr[target] - gr[source];
- }
- }
- assert_eq!(gr[e0], 1.);
- assert_eq!(gr[e1], 3.);
- assert_eq!(gr[e2], 1.);
- assert_eq!(gr[e3], -2.);
-
- let mut nedges = 0;
- let mut dfs = Dfs::new(&gr, a);
- while let Some(node) = dfs.next(&gr) {
- let mut edges = gr.neighbors_directed(node, Incoming).detach();
- while let Some((edge, source)) = edges.next(&gr) {
- assert_eq!(gr.find_edge(source, node), Some(edge));
- nedges += 1;
- }
-
- let mut edges = gr.neighbors_directed(node, Outgoing).detach();
- while let Some((edge, target)) = edges.next(&gr) {
- assert_eq!(gr.find_edge(node, target), Some(edge));
- nedges += 1;
- }
- }
- assert_eq!(nedges, 8);
-}
-
-#[test]
-fn index_twice_mut() {
- let mut gr = Graph::<_, _>::new();
- let a = gr.add_node(0.);
- let b = gr.add_node(0.);
- let c = gr.add_node(0.);
- let d = gr.add_node(0.);
- let e = gr.add_node(0.);
- let f = gr.add_node(0.);
- let g = gr.add_node(0.);
- gr.add_edge(a, b, 7.0);
- gr.add_edge(a, d, 5.);
- gr.add_edge(d, b, 9.);
- gr.add_edge(b, c, 8.);
- gr.add_edge(b, e, 7.);
- gr.add_edge(c, e, 5.);
- gr.add_edge(d, e, 15.);
- gr.add_edge(d, f, 6.);
- gr.add_edge(f, e, 8.);
- gr.add_edge(f, g, 11.);
- gr.add_edge(e, g, 9.);
-
- for dir in &[Incoming, Outgoing] {
- for nw in gr.node_weights_mut() {
- *nw = 0.;
- }
-
- // walk the graph and sum incoming edges
- let mut dfs = Dfs::new(&gr, a);
- while let Some(node) = dfs.next(&gr) {
- let mut edges = gr.neighbors_directed(node, *dir).detach();
- while let Some(edge) = edges.next_edge(&gr) {
- let (nw, ew) = gr.index_twice_mut(node, edge);
- *nw += *ew;
- }
- }
-
- // check the sums
- for i in 0..gr.node_count() {
- let ni = NodeIndex::new(i);
- let s = gr
- .edges_directed(ni, *dir)
- .map(|e| *e.weight())
- .fold(0., |a, b| a + b);
- assert_eq!(s, gr[ni]);
- }
- println!("Sum {:?}: {:?}", dir, gr);
- }
-}
-
-fn make_edge_iterator_graph<Ty: EdgeType>() -> Graph<f64, f64, Ty> {
- let mut gr = Graph::default();
- let a = gr.add_node(0.);
- let b = gr.add_node(0.);
- let c = gr.add_node(0.);
- let d = gr.add_node(0.);
- let e = gr.add_node(0.);
- let f = gr.add_node(0.);
- let g = gr.add_node(0.);
- gr.add_edge(a, b, 7.0);
- gr.add_edge(a, d, 5.);
- gr.add_edge(d, b, 9.);
- gr.add_edge(b, c, 8.);
- gr.add_edge(b, e, 7.);
- gr.add_edge(c, c, 8.);
- gr.add_edge(c, e, 5.);
- gr.add_edge(d, e, 15.);
- gr.add_edge(d, f, 6.);
- gr.add_edge(f, e, 8.);
- gr.add_edge(f, g, 11.);
- gr.add_edge(e, g, 9.);
-
- gr
-}
-
-#[test]
-fn test_edge_iterators_directed() {
- let gr = make_edge_iterator_graph::<Directed>();
-
- for i in gr.node_indices() {
- itertools::assert_equal(gr.edges_directed(i, Outgoing), gr.edges(i));
-
- // Reversed reverses edges, so target and source need to be reversed once more.
- itertools::assert_equal(
- gr.edges_directed(i, Outgoing)
- .map(|edge| (edge.source(), edge.target())),
- Reversed(&gr)
- .edges_directed(i, Incoming)
- .map(|edge| (edge.target(), edge.source())),
- );
-
- for edge in gr.edges_directed(i, Outgoing) {
- assert_eq!(
- edge.source(),
- i,
- "outgoing edges should have a fixed source"
- );
- }
- for edge in Reversed(&gr).edges_directed(i, Incoming) {
- assert_eq!(
- edge.target(),
- i,
- "reversed incoming edges should have a fixed target"
- );
- }
- }
-
- let mut reversed_gr = gr.clone();
- reversed_gr.reverse();
-
- println!("{:#?}", gr);
- for i in gr.node_indices() {
- // Compare against reversed graphs two different ways: using .reverse() and Reversed.
- itertools::assert_equal(gr.edges_directed(i, Incoming), reversed_gr.edges(i));
-
- // Reversed reverses edges, so target and source need to be reversed once more.
- itertools::assert_equal(
- gr.edges_directed(i, Incoming)
- .map(|edge| (edge.source(), edge.target())),
- Reversed(&gr)
- .edges(i)
- .map(|edge| (edge.target(), edge.source())),
- );
-
- for edge in gr.edges_directed(i, Incoming) {
- assert_eq!(
- edge.target(),
- i,
- "incoming edges should have a fixed target"
- );
- }
- for edge in Reversed(&gr).edges_directed(i, Outgoing) {
- assert_eq!(
- edge.source(),
- i,
- "reversed outgoing edges should have a fixed source"
- );
- }
- }
-}
-
-#[test]
-fn test_edge_filtered_iterators_directed() {
- use petgraph::{
- graph::EdgeReference,
- visit::{EdgeFiltered, IntoEdgesDirected},
- };
-
- let gr = make_edge_iterator_graph::<Directed>();
- let filter = |edge: EdgeReference<f64>| -> bool { *edge.weight() > 8.0 };
- let filtered = EdgeFiltered::from_fn(&gr, filter);
-
- for i in gr.node_indices() {
- itertools::assert_equal(
- filtered.edges_directed(i, Outgoing),
- gr.edges_directed(i, Outgoing).filter(|edge| filter(*edge)),
- );
- itertools::assert_equal(
- filtered.edges_directed(i, Incoming),
- gr.edges_directed(i, Incoming).filter(|edge| filter(*edge)),
- );
- }
-}
-
-#[test]
-fn test_node_filtered_iterators_directed() {
- use petgraph::{
- graph::NodeIndex,
- visit::{IntoEdgesDirected, NodeFiltered},
- };
-
- let gr = make_edge_iterator_graph::<Directed>();
- 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)
- let filtered = NodeFiltered::from_fn(&gr, filter);
-
- for i in gr.node_indices() {
- itertools::assert_equal(
- filtered.edges_directed(i, Outgoing),
- gr.edges_directed(i, Outgoing)
- .filter(|edge| filter(edge.source()) && filter(edge.target())),
- );
- itertools::assert_equal(
- filtered.edges_directed(i, Incoming),
- gr.edges_directed(i, Incoming)
- .filter(|edge| filter(edge.source()) && filter(edge.target())),
- );
- }
-}
-
-#[test]
-fn test_edge_iterators_undir() {
- let gr = make_edge_iterator_graph::<Undirected>();
-
- for i in gr.node_indices() {
- itertools::assert_equal(gr.edges_directed(i, Outgoing), gr.edges(i));
-
- // Reversed reverses edges, so target and source need to be reversed once more.
- itertools::assert_equal(
- gr.edges_directed(i, Outgoing)
- .map(|edge| (edge.source(), edge.target())),
- Reversed(&gr)
- .edges_directed(i, Incoming)
- .map(|edge| (edge.target(), edge.source())),
- );
-
- for edge in gr.edges_directed(i, Outgoing) {
- assert_eq!(
- edge.source(),
- i,
- "outgoing edges should have a fixed source"
- );
- }
- for edge in Reversed(&gr).edges_directed(i, Incoming) {
- assert_eq!(
- edge.target(),
- i,
- "reversed incoming edges should have a fixed target"
- );
- }
- }
-
- for i in gr.node_indices() {
- itertools::assert_equal(gr.edges_directed(i, Incoming), gr.edges(i));
-
- // Reversed reverses edges, so target and source need to be reversed once more.
- itertools::assert_equal(
- gr.edges_directed(i, Incoming)
- .map(|edge| (edge.source(), edge.target())),
- Reversed(&gr)
- .edges(i)
- .map(|edge| (edge.target(), edge.source())),
- );
-
- for edge in gr.edges_directed(i, Incoming) {
- assert_eq!(
- edge.target(),
- i,
- "incoming edges should have a fixed target"
- );
- }
- for edge in Reversed(&gr).edges_directed(i, Outgoing) {
- assert_eq!(
- edge.source(),
- i,
- "reversed outgoing edges should have a fixed source"
- );
- }
- }
-}
-
-#[test]
-fn toposort_generic() {
- // This is a DAG, visit it in order
- let mut gr = Graph::<_, _>::new();
- let b = gr.add_node(("B", 0.));
- let a = gr.add_node(("A", 0.));
- let c = gr.add_node(("C", 0.));
- let d = gr.add_node(("D", 0.));
- let e = gr.add_node(("E", 0.));
- let f = gr.add_node(("F", 0.));
- let g = gr.add_node(("G", 0.));
- gr.add_edge(a, b, 7.0);
- gr.add_edge(a, d, 5.);
- gr.add_edge(d, b, 9.);
- gr.add_edge(b, c, 8.);
- gr.add_edge(b, e, 7.);
- gr.add_edge(c, e, 5.);
- gr.add_edge(d, e, 15.);
- gr.add_edge(d, f, 6.);
- gr.add_edge(f, e, 8.);
- gr.add_edge(f, g, 11.);
- gr.add_edge(e, g, 9.);
-
- assert!(!pg::algo::is_cyclic_directed(&gr));
- let mut index = 0.;
- let mut topo = Topo::new(&gr);
- while let Some(nx) = topo.next(&gr) {
- gr[nx].1 = index;
- index += 1.;
- }
-
- let mut order = Vec::new();
- index = 0.;
- let mut topo = Topo::new(&gr);
- while let Some(nx) = topo.next(&gr) {
- order.push(nx);
- assert_eq!(gr[nx].1, index);
- index += 1.;
- }
- println!("{:?}", gr);
- assert_is_topo_order(&gr, &order);
-
- {
- order.clear();
- let init_nodes = gr.node_identifiers().filter(|n| {
- gr.neighbors_directed(*n, Direction::Incoming)
- .next()
- .is_none()
- });
- let mut topo = Topo::with_initials(&gr, init_nodes);
- while let Some(nx) = topo.next(&gr) {
- order.push(nx);
- }
- assert_is_topo_order(&gr, &order);
- }
-
- {
- // test `with_initials` API using nodes with incoming edges
- order.clear();
- let mut topo = Topo::with_initials(&gr, gr.node_identifiers());
- while let Some(nx) = topo.next(&gr) {
- order.push(nx);
- }
- assert_is_topo_order(&gr, &order);
- }
-
- {
- order.clear();
- let mut topo = Topo::new(&gr);
- while let Some(nx) = topo.next(&gr) {
- order.push(nx);
- }
- println!("{:?}", gr);
- assert_is_topo_order(&gr, &order);
- }
- let mut gr2 = gr.clone();
- gr.add_edge(e, d, -1.);
- assert!(pg::algo::is_cyclic_directed(&gr));
- assert!(pg::algo::toposort(&gr, None).is_err());
- gr2.add_edge(d, d, 0.);
- assert!(pg::algo::is_cyclic_directed(&gr2));
- assert!(pg::algo::toposort(&gr2, None).is_err());
-}
-
-#[test]
-fn test_has_path() {
- // This is a DAG, visit it in order
- let mut gr = Graph::<_, _>::new();
- let b = gr.add_node(("B", 0.));
- let a = gr.add_node(("A", 0.));
- let c = gr.add_node(("C", 0.));
- let d = gr.add_node(("D", 0.));
- let e = gr.add_node(("E", 0.));
- let f = gr.add_node(("F", 0.));
- let g = gr.add_node(("G", 0.));
- gr.add_edge(a, b, 7.0);
- gr.add_edge(a, d, 5.);
- gr.add_edge(d, b, 9.);
- gr.add_edge(b, c, 8.);
- gr.add_edge(b, e, 7.);
- gr.add_edge(c, e, 5.);
- gr.add_edge(d, e, 15.);
- gr.add_edge(d, f, 6.);
- gr.add_edge(f, e, 8.);
- gr.add_edge(f, g, 11.);
- gr.add_edge(e, g, 9.);
- // disconnected island
-
- let h = gr.add_node(("H", 0.));
- let i = gr.add_node(("I", 0.));
- gr.add_edge(h, i, 2.);
- gr.add_edge(i, h, -2.);
-
- let mut state = DfsSpace::default();
-
- gr.add_edge(b, a, 99.);
-
- assert!(has_path_connecting(&gr, c, c, None));
-
- for edge in gr.edge_references() {
- assert!(has_path_connecting(&gr, edge.source(), edge.target(), None));
- }
- assert!(has_path_connecting(&gr, a, g, Some(&mut state)));
- assert!(!has_path_connecting(&gr, a, h, Some(&mut state)));
- assert!(has_path_connecting(&gr, a, c, None));
- assert!(has_path_connecting(&gr, a, c, Some(&mut state)));
- assert!(!has_path_connecting(&gr, h, a, Some(&mut state)));
-}
-
-#[test]
-fn map_filter_map() {
- let mut g = Graph::new_undirected();
- let a = g.add_node("A");
- let b = g.add_node("B");
- let c = g.add_node("C");
- let d = g.add_node("D");
- let e = g.add_node("E");
- let f = g.add_node("F");
- g.add_edge(a, b, 7);
- g.add_edge(c, a, 9);
- g.add_edge(a, d, 14);
- g.add_edge(b, c, 10);
- g.add_edge(d, c, 2);
- g.add_edge(d, e, 9);
- g.add_edge(b, f, 15);
- g.add_edge(c, f, 11);
- g.add_edge(e, f, 6);
- println!("{:?}", g);
-
- let g2 = g.filter_map(
- |_, name| Some(*name),
- |_, &weight| if weight >= 10 { Some(weight) } else { None },
- );
- assert_eq!(g2.edge_count(), 4);
- for edge in g2.raw_edges() {
- assert!(edge.weight >= 10);
- }
-
- let g3 = g.filter_map(
- |i, &name| if i == a || i == e { None } else { Some(name) },
- |i, &weight| {
- let (source, target) = g.edge_endpoints(i).unwrap();
- // don't map edges from a removed node
- assert!(source != a);
- assert!(target != a);
- assert!(source != e);
- assert!(target != e);
- Some(weight)
- },
- );
- assert_eq!(g3.node_count(), g.node_count() - 2);
- assert_eq!(g3.edge_count(), g.edge_count() - 5);
- assert_graph_consistent(&g3);
-
- let mut g4 = g.clone();
- g4.retain_edges(|gr, i| {
- let (s, t) = gr.edge_endpoints(i).unwrap();
- !(s == a || s == e || t == a || t == e)
- });
- assert_eq!(g4.edge_count(), g.edge_count() - 5);
- assert_graph_consistent(&g4);
-}
-
-#[test]
-fn from_edges() {
- let n = NodeIndex::new;
- let gr =
- Graph::<(), (), Undirected>::from_edges(&[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]);
- assert_eq!(gr.node_count(), 4);
- assert_eq!(gr.edge_count(), 6);
- assert_eq!(gr.neighbors(n(0)).count(), 3);
- assert_eq!(gr.neighbors(n(1)).count(), 3);
- assert_eq!(gr.neighbors(n(2)).count(), 3);
- assert_eq!(gr.neighbors(n(3)).count(), 3);
- assert_graph_consistent(&gr);
-}
-
-#[test]
-fn retain() {
- let mut gr = Graph::<i32, i32, Undirected>::from_edges(&[
- (0, 1, 2),
- (1, 1, 1),
- (0, 2, 0),
- (1, 2, 3),
- (2, 3, 3),
- ]);
- gr.retain_edges(|mut gr, i| {
- if gr[i] <= 0 {
- false
- } else {
- gr[i] -= 1;
- let (s, t) = gr.edge_endpoints(i).unwrap();
- gr[s] += 1;
- gr[t] += 1;
-
- gr[i] > 0
- }
- });
-
- assert_eq!(gr.edge_count(), 3);
- assert_eq!(gr[n(0)], 1);
- assert_eq!(gr[n(1)], 4);
- assert_eq!(gr[n(2)], 2);
- assert_eq!(gr[n(3)], 1);
- assert!(gr.find_edge(n(1), n(1)).is_none());
- assert!(gr.find_edge(n(0), n(2)).is_none());
- assert_graph_consistent(&gr);
-}
-
-fn assert_graph_consistent<N, E, Ty, Ix>(g: &Graph<N, E, Ty, Ix>)
-where
- Ty: EdgeType,
- Ix: IndexType,
-{
- assert_eq!(g.node_count(), g.node_indices().count());
- assert_eq!(g.edge_count(), g.edge_indices().count());
- for edge in g.raw_edges() {
- assert!(
- g.find_edge(edge.source(), edge.target()).is_some(),
- "Edge not in graph! {:?} to {:?}",
- edge.source(),
- edge.target()
- );
- }
-}
-
-#[test]
-fn neighbors_selfloops() {
- // Directed graph
- let mut gr = Graph::<_, ()>::new();
- let a = gr.add_node("a");
- let b = gr.add_node("b");
- let c = gr.add_node("c");
- gr.extend_with_edges(&[(a, a), (a, b), (c, a), (a, a)]);
-
- let out_edges = [a, a, b];
- let in_edges = [a, a, c];
- let undir_edges = [a, a, b, c];
- let mut seen_out = gr.neighbors(a).collect::<Vec<_>>();
- seen_out.sort();
- assert_eq!(&seen_out, &out_edges);
- let mut seen_in = gr.neighbors_directed(a, Incoming).collect::<Vec<_>>();
- seen_in.sort();
- assert_eq!(&seen_in, &in_edges);
-
- let mut seen_undir = gr.neighbors_undirected(a).collect::<Vec<_>>();
- seen_undir.sort();
- assert_eq!(&seen_undir, &undir_edges);
-
- let mut seen_out = gr.edges(a).map(|e| e.target()).collect::<Vec<_>>();
- seen_out.sort();
- assert_eq!(&seen_out, &out_edges);
-
- let mut seen_walk = Vec::new();
- let mut walk = gr.neighbors(a).detach();
- while let Some(n) = walk.next_node(&gr) {
- seen_walk.push(n);
- }
- seen_walk.sort();
- assert_eq!(&seen_walk, &out_edges);
-
- seen_walk.clear();
- let mut walk = gr.neighbors_directed(a, Incoming).detach();
- while let Some(n) = walk.next_node(&gr) {
- seen_walk.push(n);
- }
- seen_walk.sort();
- assert_eq!(&seen_walk, &in_edges);
-
- seen_walk.clear();
- let mut walk = gr.neighbors_undirected(a).detach();
- while let Some(n) = walk.next_node(&gr) {
- seen_walk.push(n);
- }
- seen_walk.sort();
- assert_eq!(&seen_walk, &undir_edges);
-
- // Undirected graph
- let mut gr: Graph<_, (), _> = Graph::new_undirected();
- let a = gr.add_node("a");
- let b = gr.add_node("b");
- let c = gr.add_node("c");
- gr.extend_with_edges(&[(a, a), (a, b), (c, a)]);
-
- let out_edges = [a, b, c];
- let in_edges = [a, b, c];
- let undir_edges = [a, b, c];
- let mut seen_out = gr.neighbors(a).collect::<Vec<_>>();
- seen_out.sort();
- assert_eq!(&seen_out, &out_edges);
-
- let mut seen_out = gr.edges(a).map(|e| e.target()).collect::<Vec<_>>();
- seen_out.sort();
- assert_eq!(&seen_out, &out_edges);
-
- let mut seen_in = gr.neighbors_directed(a, Incoming).collect::<Vec<_>>();
- seen_in.sort();
- assert_eq!(&seen_in, &in_edges);
-
- let mut seen_undir = gr.neighbors_undirected(a).collect::<Vec<_>>();
- seen_undir.sort();
- assert_eq!(&seen_undir, &undir_edges);
-}
-
-fn degree<'a, G>(g: G, node: G::NodeId) -> usize
-where
- G: IntoNeighbors,
- G::NodeId: PartialEq,
-{
- // self loops count twice
- let original_node = node;
- let mut degree = 0;
- for v in g.neighbors(node) {
- degree += if v == original_node { 2 } else { 1 };
- }
- degree
-}
-
-#[cfg(feature = "graphmap")]
-#[test]
-fn degree_sequence() {
- let mut gr = Graph::<usize, (), Undirected>::from_edges(&[
- (0, 1),
- (1, 2),
- (1, 3),
- (2, 4),
- (3, 4),
- (4, 4),
- (4, 5),
- (3, 5),
- ]);
- gr.add_node(0); // add isolated node
- let mut degree_sequence = gr
- .node_indices()
- .map(|i| degree(&gr, i))
- .collect::<Vec<_>>();
-
- degree_sequence.sort_by(|x, y| Ord::cmp(y, x));
- assert_eq!(&degree_sequence, &[5, 3, 3, 2, 2, 1, 0]);
-
- let mut gr = GraphMap::<_, (), Undirected>::from_edges(&[
- (0, 1),
- (1, 2),
- (1, 3),
- (2, 4),
- (3, 4),
- (4, 4),
- (4, 5),
- (3, 5),
- ]);
- gr.add_node(6); // add isolated node
- let mut degree_sequence = gr.nodes().map(|i| degree(&gr, i)).collect::<Vec<_>>();
-
- degree_sequence.sort_by(|x, y| Ord::cmp(y, x));
- assert_eq!(&degree_sequence, &[5, 3, 3, 2, 2, 1, 0]);
-}
-
-#[test]
-fn neighbor_order() {
- let mut gr = Graph::new();
- let a = gr.add_node("a");
- let b = gr.add_node("b");
- let c = gr.add_node("c");
- gr.add_edge(a, b, 0);
- gr.add_edge(a, a, 1);
-
- gr.add_edge(c, a, 2);
-
- gr.add_edge(a, c, 3);
-
- gr.add_edge(c, a, 4);
- gr.add_edge(b, a, 5);
-
- // neighbors (edges) are in lifo order, if it's a directed graph
- assert_eq!(gr.neighbors(a).collect::<Vec<_>>(), vec![c, a, b]);
- assert_eq!(
- gr.neighbors_directed(a, Incoming).collect::<Vec<_>>(),
- vec![b, c, c, a]
- );
-}
-
-#[test]
-fn dot() {
- // test alternate formatting
- #[derive(Debug)]
- struct Record {
- a: i32,
- b: &'static str,
- }
- let mut gr = Graph::new();
- let a = gr.add_node(Record { a: 1, b: r"abc\" });
- gr.add_edge(a, a, (1, 2));
- let dot_output = format!("{:?}", Dot::new(&gr));
- assert_eq!(
- dot_output,
- // The single \ turns into four \\\\ because of Debug which turns it to \\ and then escaping each \ to \\.
- r#"digraph {
- 0 [ label = "Record { a: 1, b: \"abc\\\\\" }" ]
- 0 -> 0 [ label = "(1, 2)" ]
-}
-"#
- );
-}
-
-#[test]
-fn filtered() {
- let mut g = Graph::new();
- let a = g.add_node("A");
- let b = g.add_node("B");
- let c = g.add_node("C");
- let d = g.add_node("D");
- let e = g.add_node("E");
- let f = g.add_node("F");
- g.add_edge(a, b, 7);
- g.add_edge(c, a, 9);
- g.add_edge(a, d, 14);
- g.add_edge(b, c, 10);
- g.add_edge(d, c, 2);
- g.add_edge(d, e, 9);
- g.add_edge(b, f, 15);
- g.add_edge(c, f, 11);
- g.add_edge(e, f, 6);
- println!("{:?}", g);
-
- let filt = NodeFiltered(&g, |n: NodeIndex| n != c && n != e);
-
- let mut dfs = DfsPostOrder::new(&filt, a);
- let mut po = Vec::new();
- while let Some(nx) = dfs.next(&filt) {
- println!("Next: {:?}", nx);
- po.push(nx);
- }
- assert_eq!(set(po), set(g.node_identifiers().filter(|n| (filt.1)(*n))));
-}
-
-#[test]
-fn filtered_edge_reverse() {
- use petgraph::visit::EdgeFiltered;
- #[derive(Eq, PartialEq)]
- enum E {
- A,
- B,
- }
-
- // Start with single node graph with loop
- let mut g = Graph::new();
- let a = g.add_node("A");
- g.add_edge(a, a, E::A);
- let ef_a = EdgeFiltered::from_fn(&g, |edge| *edge.weight() == E::A);
- let mut po = Vec::new();
- let mut dfs = Dfs::new(&ef_a, a);
- while let Some(next_n_ix) = dfs.next(&ef_a) {
- po.push(next_n_ix);
- }
- assert_eq!(set(po), set(vec![a]));
-
- // Check in reverse
- let mut po = Vec::new();
- let mut dfs = Dfs::new(&Reversed(&ef_a), a);
- while let Some(next_n_ix) = dfs.next(&Reversed(&ef_a)) {
- po.push(next_n_ix);
- }
- assert_eq!(set(po), set(vec![a]));
-
- let mut g = Graph::new();
- let a = g.add_node("A");
- let b = g.add_node("B");
- let c = g.add_node("C");
- let d = g.add_node("D");
- let e = g.add_node("E");
- let f = g.add_node("F");
- let h = g.add_node("H");
- let i = g.add_node("I");
- let j = g.add_node("J");
-
- g.add_edge(a, b, E::A);
- g.add_edge(b, c, E::A);
- g.add_edge(c, d, E::B);
- g.add_edge(d, e, E::A);
- g.add_edge(e, f, E::A);
- g.add_edge(e, h, E::A);
- g.add_edge(e, i, E::A);
- g.add_edge(i, j, E::A);
-
- let ef_a = EdgeFiltered::from_fn(&g, |edge| *edge.weight() == E::A);
- let ef_b = EdgeFiltered::from_fn(&g, |edge| *edge.weight() == E::B);
-
- // DFS down from a, filtered by E::A.
- let mut po = Vec::new();
- let mut dfs = Dfs::new(&ef_a, a);
- while let Some(next_n_ix) = dfs.next(&ef_a) {
- po.push(next_n_ix);
- }
- assert_eq!(set(po), set(vec![a, b, c]));
-
- // Reversed DFS from f, filtered by E::A.
- let mut dfs = Dfs::new(&Reversed(&ef_a), f);
- let mut po = Vec::new();
- while let Some(next_n_ix) = dfs.next(&Reversed(&ef_a)) {
- po.push(next_n_ix);
- }
- assert_eq!(set(po), set(vec![d, e, f]));
-
- // Reversed DFS from j, filtered by E::A.
- let mut dfs = Dfs::new(&Reversed(&ef_a), j);
- let mut po = Vec::new();
- while let Some(next_n_ix) = dfs.next(&Reversed(&ef_a)) {
- po.push(next_n_ix);
- }
- assert_eq!(set(po), set(vec![d, e, i, j]));
-
- // Reversed DFS from c, filtered by E::A.
- let mut dfs = Dfs::new(&Reversed(&ef_a), c);
- let mut po = Vec::new();
- while let Some(next_n_ix) = dfs.next(&Reversed(&ef_a)) {
- po.push(next_n_ix);
- }
- assert_eq!(set(po), set(vec![a, b, c]));
-
- // Reversed DFS from c, filtered by E::B.
- let mut dfs = Dfs::new(&Reversed(&ef_b), c);
- let mut po = Vec::new();
- while let Some(next_n_ix) = dfs.next(&Reversed(&ef_b)) {
- po.push(next_n_ix);
- }
- assert_eq!(set(po), set(vec![c]));
-
- // Reversed DFS from d, filtered by E::B.
- let mut dfs = Dfs::new(&Reversed(&ef_b), d);
- let mut po = Vec::new();
- while let Some(next_n_ix) = dfs.next(&Reversed(&ef_b)) {
- po.push(next_n_ix);
- }
- assert_eq!(set(po), set(vec![c, d]));
-
- // Now let's test the same graph but undirected
-
- let mut g = Graph::new_undirected();
- let a = g.add_node("A");
- let b = g.add_node("B");
- let c = g.add_node("C");
- let d = g.add_node("D");
- let e = g.add_node("E");
- let f = g.add_node("F");
- let h = g.add_node("H");
- let i = g.add_node("I");
- let j = g.add_node("J");
-
- g.add_edge(a, b, E::A);
- g.add_edge(b, c, E::A);
- g.add_edge(c, d, E::B);
- g.add_edge(d, e, E::A);
- g.add_edge(e, f, E::A);
- g.add_edge(e, h, E::A);
- g.add_edge(e, i, E::A);
- g.add_edge(i, j, E::A);
-
- let ef_a = EdgeFiltered::from_fn(&g, |edge| *edge.weight() == E::A);
- let ef_b = EdgeFiltered::from_fn(&g, |edge| *edge.weight() == E::B);
- let mut po = Vec::new();
- let mut dfs = Dfs::new(&Reversed(&ef_b), d);
- while let Some(next_n_ix) = dfs.next(&Reversed(&ef_b)) {
- po.push(next_n_ix);
- }
- assert_eq!(set(po), set(vec![c, d]));
-
- let mut po = Vec::new();
- let mut dfs = Dfs::new(&Reversed(&ef_a), h);
- while let Some(next_n_ix) = dfs.next(&Reversed(&ef_a)) {
- po.push(next_n_ix);
- }
- assert_eq!(set(po), set(vec![d, e, f, h, i, j]));
-}
-
-#[test]
-fn dfs_visit() {
- use petgraph::visit::Control;
- use petgraph::visit::DfsEvent::*;
- use petgraph::visit::{depth_first_search, Time};
- use petgraph::visit::{VisitMap, Visitable};
- let gr: Graph<(), ()> = Graph::from_edges(&[
- (0, 5),
- (0, 2),
- (0, 3),
- (0, 1),
- (1, 3),
- (2, 3),
- (2, 4),
- (4, 0),
- (4, 5),
- ]);
-
- let invalid_time = Time(!0);
- let mut discover_time = vec![invalid_time; gr.node_count()];
- let mut finish_time = vec![invalid_time; gr.node_count()];
- let mut has_tree_edge = gr.visit_map();
- let mut edges = HashSet::new();
- depth_first_search(&gr, Some(n(0)), |evt| {
- println!("Event: {:?}", evt);
- match evt {
- Discover(n, t) => discover_time[n.index()] = t,
- Finish(n, t) => finish_time[n.index()] = t,
- TreeEdge(u, v) => {
- // v is an ancestor of u
- assert!(has_tree_edge.visit(v), "Two tree edges to {:?}!", v);
- assert!(discover_time[v.index()] == invalid_time);
- assert!(discover_time[u.index()] != invalid_time);
- assert!(finish_time[u.index()] == invalid_time);
- edges.insert((u, v));
- }
- BackEdge(u, v) => {
- // u is an ancestor of v
- assert!(discover_time[v.index()] != invalid_time);
- assert!(finish_time[v.index()] == invalid_time);
- edges.insert((u, v));
- }
- CrossForwardEdge(u, v) => {
- edges.insert((u, v));
- }
- }
- });
- assert!(discover_time.iter().all(|x| *x != invalid_time));
- assert!(finish_time.iter().all(|x| *x != invalid_time));
- assert_eq!(edges.len(), gr.edge_count());
- assert_eq!(
- edges,
- set(gr.edge_references().map(|e| (e.source(), e.target())))
- );
- println!("{:?}", discover_time);
- println!("{:?}", finish_time);
-
- // find path from 0 to 4
- let mut predecessor = vec![NodeIndex::end(); gr.node_count()];
- let start = n(0);
- let goal = n(4);
- let ret = depth_first_search(&gr, Some(start), |event| {
- if let TreeEdge(u, v) = event {
- predecessor[v.index()] = u;
- if v == goal {
- return Control::Break(u);
- }
- }
- Control::Continue
- });
- // assert we did terminate early
- assert!(ret.break_value().is_some());
- assert!(predecessor.iter().any(|x| *x == NodeIndex::end()));
-
- let mut next = goal;
- let mut path = vec![next];
- while next != start {
- let pred = predecessor[next.index()];
- path.push(pred);
- next = pred;
- }
- path.reverse();
- assert_eq!(&path, &[n(0), n(2), n(4)]);
-
- // check that if we prune 2, we never see 4.
- let start = n(0);
- let prune = n(2);
- let nongoal = n(4);
- let ret = depth_first_search(&gr, Some(start), |event| {
- if let Discover(n, _) = event {
- if n == prune {
- return Control::Prune;
- }
- } else if let TreeEdge(u, v) = event {
- if v == nongoal {
- return Control::Break(u);
- }
- }
- Control::Continue
- });
- assert!(ret.break_value().is_none());
-}
-
-#[test]
-fn filtered_post_order() {
- use petgraph::visit::NodeFiltered;
-
- let mut gr: Graph<(), ()> =
- Graph::from_edges(&[(0, 2), (1, 2), (0, 3), (1, 4), (2, 4), (4, 5), (3, 5)]);
- // map reachable nodes
- let mut dfs = Dfs::new(&gr, n(0));
- while dfs.next(&gr).is_some() {}
-
- let map = dfs.discovered;
- gr.add_edge(n(0), n(1), ());
- let mut po = Vec::new();
- let mut dfs = DfsPostOrder::new(&gr, n(0));
- let f = NodeFiltered(&gr, map);
- while let Some(n) = dfs.next(&f) {
- po.push(n);
- }
- assert!(!po.contains(&n(1)));
-}
-
-#[test]
-fn filter_elements() {
- use petgraph::data::Element::{Edge, Node};
- use petgraph::data::ElementIterator;
- use petgraph::data::FromElements;
- let elements = vec![
- Node { weight: "A" },
- Node { weight: "B" },
- Node { weight: "C" },
- Node { weight: "D" },
- Node { weight: "E" },
- Node { weight: "F" },
- Edge {
- source: 0,
- target: 1,
- weight: 7,
- },
- Edge {
- source: 2,
- target: 0,
- weight: 9,
- },
- Edge {
- source: 0,
- target: 3,
- weight: 14,
- },
- Edge {
- source: 1,
- target: 2,
- weight: 10,
- },
- Edge {
- source: 3,
- target: 2,
- weight: 2,
- },
- Edge {
- source: 3,
- target: 4,
- weight: 9,
- },
- Edge {
- source: 1,
- target: 5,
- weight: 15,
- },
- Edge {
- source: 2,
- target: 5,
- weight: 11,
- },
- Edge {
- source: 4,
- target: 5,
- weight: 6,
- },
- ];
- let mut g = DiGraph::<_, _>::from_elements(elements.iter().cloned());
- println!("{:#?}", g);
- assert!(g.contains_edge(n(1), n(5)));
- let g2 =
- DiGraph::<_, _>::from_elements(elements.iter().cloned().filter_elements(|elt| match elt {
- Node { ref weight } if **weight == "B" => false,
- _ => true,
- }));
- println!("{:#?}", g2);
- g.remove_node(n(1));
- assert!(is_isomorphic_matching(
- &g,
- &g2,
- PartialEq::eq,
- PartialEq::eq
- ));
-}
-
-#[test]
-fn test_edge_filtered() {
- use petgraph::algo::connected_components;
- use petgraph::visit::EdgeFiltered;
- use petgraph::visit::IntoEdgeReferences;
-
- let gr = UnGraph::<(), _>::from_edges(&[
- // cycle
- (0, 1, 7),
- (1, 2, 9),
- (2, 1, 14),
- // cycle
- (3, 4, 10),
- (4, 5, 2),
- (5, 3, 9),
- // cross edges
- (0, 3, -1),
- (1, 4, -2),
- (2, 5, -3),
- ]);
- assert_eq!(connected_components(&gr), 1);
- let positive_edges = EdgeFiltered::from_fn(&gr, |edge| *edge.weight() >= 0);
- assert_eq!(positive_edges.edge_references().count(), 6);
- assert!(positive_edges
- .edge_references()
- .all(|edge| *edge.weight() >= 0));
- assert_eq!(connected_components(&positive_edges), 2);
-
- let mut dfs = DfsPostOrder::new(&positive_edges, n(0));
- while dfs.next(&positive_edges).is_some() {}
-
- let n = n::<u32>;
- for node in &[n(0), n(1), n(2)] {
- assert!(dfs.discovered.is_visited(node));
- }
- for node in &[n(3), n(4), n(5)] {
- assert!(!dfs.discovered.is_visited(node));
- }
-}
-
-#[test]
-fn test_dominators_simple_fast() {
- // Construct the following graph:
- //
- // .-----.
- // | <--------------------------------.
- // .--------+--------------| r |--------------. |
- // | | | | | |
- // | | '-----' | |
- // | .--V--. .--V--. |
- // | | | | | |
- // | | b | | c |--------. |
- // | | | | | | |
- // | '-----' '-----' | |
- // .--V--. | | .--V--. |
- // | | | | | | |
- // | a <-----+ | .----| g | |
- // | | | .----' | | | |
- // '-----' | | | '-----' |
- // | | | | | |
- // .--V--. | .-----. .--V--. | | |
- // | | | | | | | | | |
- // | d <-----+----> e <----. | f | | | |
- // | | | | | | | | | |
- // '-----' '-----' | '-----' | | |
- // | .-----. | | | | .--V--. |
- // | | | | | | .-' | | |
- // '-----> l | | | | | | j | |
- // | | '--. | | | | | |
- // '-----' | | | | '-----' |
- // | .--V--. | | .--V--. | |
- // | | | | | | | | |
- // '-------> h |-' '---> i <------' |
- // | | .---------> | |
- // '-----' | '-----' |
- // | .-----. | |
- // | | | | |
- // '----------> k <---------' |
- // | | |
- // '-----' |
- // | |
- // '----------------------------'
- //
- // This graph has the following dominator tree:
- //
- // r
- // |-- a
- // |-- b
- // |-- c
- // | |-- f
- // | `-- g
- // | `-- j
- // |-- d
- // | `-- l
- // |-- e
- // |-- i
- // |-- k
- // `-- h
- //
- // This graph and dominator tree are taken from figures 1 and 2 of "A Fast
- // Algorithm for Finding Dominators in a Flowgraph" by Lengauer et al:
- // http://www.cs.princeton.edu/courses/archive/spr03/cs423/download/dominators.pdf.
-
- let mut graph = DiGraph::<_, _>::new();
-
- let r = graph.add_node("r");
- let a = graph.add_node("a");
- let b = graph.add_node("b");
- let c = graph.add_node("c");
- let d = graph.add_node("d");
- let e = graph.add_node("e");
- let f = graph.add_node("f");
- let g = graph.add_node("g");
- let h = graph.add_node("h");
- let i = graph.add_node("i");
- let j = graph.add_node("j");
- let k = graph.add_node("k");
- let l = graph.add_node("l");
-
- graph.add_edge(r, a, ());
- graph.add_edge(r, b, ());
- graph.add_edge(r, c, ());
- graph.add_edge(a, d, ());
- graph.add_edge(b, a, ());
- graph.add_edge(b, d, ());
- graph.add_edge(b, e, ());
- graph.add_edge(c, f, ());
- graph.add_edge(c, g, ());
- graph.add_edge(d, l, ());
- graph.add_edge(e, h, ());
- graph.add_edge(f, i, ());
- graph.add_edge(g, i, ());
- graph.add_edge(g, j, ());
- graph.add_edge(h, e, ());
- graph.add_edge(h, k, ());
- graph.add_edge(i, k, ());
- graph.add_edge(j, i, ());
- graph.add_edge(k, r, ());
- graph.add_edge(k, i, ());
- graph.add_edge(l, h, ());
-
- let doms = dominators::simple_fast(&graph, r);
-
- assert_eq!(doms.root(), r);
- assert_eq!(
- doms.immediate_dominator(r),
- None,
- "The root node has no idom"
- );
-
- assert_eq!(
- doms.immediate_dominator(a),
- Some(r),
- "r is the immediate dominator of a"
- );
- assert_eq!(
- doms.immediate_dominator(b),
- Some(r),
- "r is the immediate dominator of b"
- );
- assert_eq!(
- doms.immediate_dominator(c),
- Some(r),
- "r is the immediate dominator of c"
- );
- assert_eq!(
- doms.immediate_dominator(f),
- Some(c),
- "c is the immediate dominator of f"
- );
- assert_eq!(
- doms.immediate_dominator(g),
- Some(c),
- "c is the immediate dominator of g"
- );
- assert_eq!(
- doms.immediate_dominator(j),
- Some(g),
- "g is the immediate dominator of j"
- );
- assert_eq!(
- doms.immediate_dominator(d),
- Some(r),
- "r is the immediate dominator of d"
- );
- assert_eq!(
- doms.immediate_dominator(l),
- Some(d),
- "d is the immediate dominator of l"
- );
- assert_eq!(
- doms.immediate_dominator(e),
- Some(r),
- "r is the immediate dominator of e"
- );
- assert_eq!(
- doms.immediate_dominator(i),
- Some(r),
- "r is the immediate dominator of i"
- );
- assert_eq!(
- doms.immediate_dominator(k),
- Some(r),
- "r is the immediate dominator of k"
- );
- assert_eq!(
- doms.immediate_dominator(h),
- Some(r),
- "r is the immediate dominator of h"
- );
-
- let mut graph = graph.clone();
- let z = graph.add_node("z");
- let doms = dominators::simple_fast(&graph, r);
- assert_eq!(
- doms.immediate_dominator(z),
- None,
- "nodes that aren't reachable from the root do not have an idom"
- );
-}
generated by cgit v1.2.3 (git 2.39.1) at 2026-02-02 02:58:42 +0000