blob: e76c04f02ba20bda138d2786afc2ff0d9f432fb9 [file] [log] [blame]
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, min_spanning_tree,
};
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 mst() {
use petgraph::data::FromElements;
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.);
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.);
// 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.);
println!("{}", Dot::new(&gr));
let mst = UnGraph::from_elements(min_spanning_tree(&gr));
println!("{}", Dot::new(&mst));
println!("{:?}", Dot::new(&mst));
println!("MST is:\n{:#?}", mst);
assert!(mst.node_count() == gr.node_count());
// |E| = |N| - 2 because there are two disconnected components.
assert!(mst.edge_count() == gr.node_count() - 2);
// check the exact edges are there
assert!(mst.find_edge(a, b).is_some());
assert!(mst.find_edge(a, d).is_some());
assert!(mst.find_edge(b, e).is_some());
assert!(mst.find_edge(e, c).is_some());
assert!(mst.find_edge(e, g).is_some());
assert!(mst.find_edge(d, f).is_some());
assert!(mst.find_edge(h, i).is_some());
assert!(mst.find_edge(i, j).is_some());
assert!(mst.find_edge(d, b).is_none());
assert!(mst.find_edge(b, c).is_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));
}
}
#[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),
]);
assert_sccs_eq(
petgraph::algo::tarjan_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,
);
// 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::tarjan_scc(&hr),
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), ());
assert_sccs_eq(
petgraph::algo::tarjan_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::tarjan_scc(&gr),
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_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 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.clone();
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 let Some(_) = dfs.next(&gr) {}
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 let Some(_) = dfs.next(&positive_edges) {}
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"