src/vendor/petgraph/tests/stable_graph.rs

   1 #![cfg(feature = "stable_graph")]
   2
   3 extern crate petgraph;
   4 extern crate itertools;
   5 #[macro_use] extern crate defmac;
   6
   7 use petgraph::prelude::*;
   8 use petgraph::stable_graph::node_index as n;
   9 use petgraph::EdgeType;
  10 use petgraph::algo::{kosaraju_scc, tarjan_scc};
  11 use petgraph::visit::{
  12     NodeIndexable,
  13     IntoNodeReferences,
  14     IntoEdgeReferences,
  15 };
  16 use petgraph::dot::Dot;
  17
  18 use itertools::assert_equal;
  19
  20 #[test]
  21 fn node_indices() {
  22     let mut g = StableGraph::<_, ()>::new();
  23     let a = g.add_node(0);
  24     let b = g.add_node(1);
  25     let c = g.add_node(2);
  26     g.remove_node(b);
  27     let mut iter = g.node_indices();
  28     assert_eq!(iter.next(), Some(a));
  29     assert_eq!(iter.next(), Some(c));
  30     assert_eq!(iter.next(), None);
  31 }
  32
  33 #[test]
  34 fn node_bound() {
  35     let mut g = StableGraph::<_, ()>::new();
  36     assert_eq!(g.node_bound(), g.node_count());
  37     for i in 0..10 {
  38         g.add_node(i);
  39         assert_eq!(g.node_bound(), g.node_count());
  40     }
  41     let full_count = g.node_count();
  42     g.remove_node(n(0));
  43     g.remove_node(n(2));
  44     assert_eq!(g.node_bound(), full_count);
  45     g.clear();
  46     assert_eq!(g.node_bound(), 0);
  47 }
  48
  49 #[test]
  50 fn clear_edges() {
  51     let mut gr = scc_graph();
  52     gr.remove_node(n(1));
  53     gr.clear_edges();
  54     // check that we use the free list for the vacancies
  55     assert_eq!(gr.add_node(()), n(1));
  56     assert_eq!(gr.add_node(()), n(4));
  57     assert!(gr.edge_references().next().is_none());
  58     assert!(gr.node_indices().all(|i| gr.neighbors(i).next().is_none()));
  59 }
  60
  61 fn assert_sccs_eq(mut res: Vec<Vec<NodeIndex>>, normalized: Vec<Vec<NodeIndex>>) {
  62     // normalize the result and compare with the answer.
  63     for scc in &mut res {
  64         scc.sort();
  65     }
  66     // sort by minimum element
  67     res.sort_by(|v, w| v[0].cmp(&w[0]));
  68     assert_eq!(res, normalized);
  69 }
  70
  71 fn scc_graph() -> StableGraph<(), ()> {
  72     let mut gr: StableGraph<(), ()> = StableGraph::from_edges(&[
  73         (6, 0),
  74         (0, 3),
  75         (3, 6),
  76         (8, 6), (8, 2),
  77         (2, 5), (5, 8), (7, 5),
  78         (1, 7),
  79         (7, 4),
  80         (4, 1)]);
  81     // make an identical replacement of n(4) and leave a hole
  82     let x = gr.add_node(());
  83     gr.add_edge(n(7), x, ());
  84     gr.add_edge(x, n(1), ());
  85     gr.remove_node(n(4));
  86     gr
  87 }
  88
  89 #[test]
  90 fn test_scc() {
  91     let gr = scc_graph();
  92     println!("{:?}", gr);
  93
  94     let x = n(gr.node_bound() - 1);
  95     assert_sccs_eq(kosaraju_scc(&gr), vec![
  96         vec![n(0), n(3), n(6)],
  97         vec![n(1), n(7),   x ],
  98         vec![n(2), n(5), n(8)],
  99     ]);
 100 }
 101
 102
 103 #[test]
 104 fn test_tarjan_scc() {
 105     let gr = scc_graph();
 106
 107     let x = n(gr.node_bound() - 1);
 108     assert_sccs_eq(tarjan_scc(&gr), vec![
 109         vec![n(0), n(3), n(6)],
 110         vec![n(1), n(7),   x ],
 111         vec![n(2), n(5), n(8)],
 112     ]);
 113 }
 114
 115 fn make_graph<Ty>() -> StableGraph<(), i32, Ty>
 116     where Ty: EdgeType,
 117 {
 118     let mut gr = StableGraph::default();
 119     let mut c = 0..;
 120     let mut e = || -> i32 { c.next().unwrap() };
 121     gr.extend_with_edges(&[
 122         (6, 0, e()),
 123         (0, 3, e()),
 124         (3, 6, e()),
 125         (8, 6, e()),
 126         (8, 2, e()),
 127         (2, 5, e()),
 128         (5, 8, e()),
 129         (7, 5, e()),
 130         (1, 7, e()),
 131         (7, 4, e()),
 132         (8, 6, e()), // parallel edge
 133         (4, 1, e())]);
 134     // make an identical replacement of n(4) and leave a hole
 135     let x = gr.add_node(());
 136     gr.add_edge(n(7), x, e());
 137     gr.add_edge(x, n(1), e());
 138     gr.add_edge(x, x, e()); // make two self loops
 139     let rm_self_loop = gr.add_edge(x, x, e());
 140     gr.add_edge(x, x, e());
 141     gr.remove_node(n(4));
 142     gr.remove_node(n(6));
 143     gr.remove_edge(rm_self_loop);
 144     gr
 145 }
 146
 147 defmac!(edges ref gr, x => gr.edges(x).map(|r| (r.target(), *r.weight())));
 148
 149 #[test]
 150 fn test_edges_directed() {
 151     let gr = make_graph::<Directed>();
 152     let x = n(9);
 153     assert_equal(edges!(gr, x), vec![(x, 16), (x, 14), (n(1), 13)]);
 154     assert_equal(edges!(gr, n(0)), vec![(n(3), 1)]);
 155     assert_equal(edges!(gr, n(4)), vec![]);
 156 }
 157
 158 #[test]
 159 fn test_edge_references() {
 160     let gr = make_graph::<Directed>();
 161     assert_eq!(gr.edge_count(), gr.edge_references().count());
 162 }
 163
 164 #[test]
 165 fn test_edges_undirected() {
 166     let gr = make_graph::<Undirected>();
 167     let x = n(9);
 168     assert_equal(edges!(gr, x), vec![(x, 16), (x, 14), (n(1), 13), (n(7), 12)]);
 169     assert_equal(edges!(gr, n(0)), vec![(n(3), 1)]);
 170     assert_equal(edges!(gr, n(4)), vec![]);
 171 }
 172
 173 #[test]
 174 fn test_edge_iterators_directed() {
 175     let gr = make_graph::<Directed>();
 176     for i in gr.node_indices() {
 177         itertools::assert_equal(
 178             gr.edges_directed(i, Outgoing),
 179             gr.edges(i));
 180     }
 181     let mut incoming = vec![Vec::new(); gr.node_bound()];
 182
 183     for i in gr.node_indices() {
 184         for j in gr.neighbors(i) {
 185             incoming[j.index()].push(i);
 186         }
 187     }
 188
 189     println!("{:#?}", gr);
 190     for i in gr.node_indices() {
 191         itertools::assert_equal(
 192             gr.edges_directed(i, Incoming).map(|e| e.source()),
 193             incoming[i.index()].iter().rev().cloned());
 194     }
 195 }
 196
 197 #[test]
 198 fn test_edge_iterators_undir() {
 199     let gr = make_graph::<Undirected>();
 200     for i in gr.node_indices() {
 201         itertools::assert_equal(
 202             gr.edges_directed(i, Outgoing),
 203             gr.edges(i));
 204     }
 205     for i in gr.node_indices() {
 206         itertools::assert_equal(
 207             gr.edges_directed(i, Incoming),
 208             gr.edges(i));
 209     }
 210 }
 211
 212 #[test]
 213 #[should_panic(expected="is not a node")]
 214 fn add_edge_vacant() {
 215     let mut g = StableGraph::<_, _>::new();
 216     let a = g.add_node(0);
 217     let b = g.add_node(1);
 218     let _ = g.add_node(2);
 219     let _ = g.remove_node(b);
 220     g.add_edge(a, b, 1);
 221 }
 222
 223 #[test]
 224 #[should_panic(expected="is not a node")]
 225 fn add_edge_oob() {
 226     let mut g = StableGraph::<_, _>::new();
 227     let a = g.add_node(0);
 228     let _ = g.add_node(1);
 229     let _ = g.add_node(2);
 230     g.add_edge(a, n(4), 1);
 231 }
 232
 233 #[test]
 234 fn test_node_references() {
 235     let gr = scc_graph();
 236
 237     itertools::assert_equal(
 238         gr.node_references().map(|(i, _)| i),
 239         gr.node_indices());
 240 }
 241
 242 #[test]
 243 fn iterators_undir() {
 244     let mut g = StableUnGraph::<_, _>::default();
 245     let a = g.add_node(0);
 246     let b = g.add_node(1);
 247     let c = g.add_node(2);
 248     let d = g.add_node(3);
 249     g.extend_with_edges(&[
 250         (a, b, 1),
 251         (a, c, 2),
 252         (b, c, 3),
 253         (c, c, 4),
 254         (a, d, 5),
 255     ]);
 256     g.remove_node(b);
 257
 258     itertools::assert_equal(
 259         g.neighbors(a),
 260         vec![d, c],
 261     );
 262     itertools::assert_equal(
 263         g.neighbors(c),
 264         vec![c, a],
 265     );
 266     itertools::assert_equal(
 267         g.neighbors(d),
 268         vec![a],
 269     );
 270
 271     // the node that was removed
 272     itertools::assert_equal(
 273         g.neighbors(b),
 274         vec![],
 275     );
 276
 277     // remove one more
 278     g.remove_node(c);
 279     itertools::assert_equal(
 280         g.neighbors(c),
 281         vec![],
 282     );
 283 }
 284
 285 #[test]
 286 fn dot() {
 287     let mut gr = StableGraph::new();
 288     let a = gr.add_node("x");
 289     let b = gr.add_node("y");
 290     gr.add_edge(a, a, "10");
 291     gr.add_edge(a, b, "20");
 292     let dot_output = format!("{}", Dot::new(&gr));
 293     assert_eq!(dot_output,
 294 r#"digraph {
 295     0 [label="x"]
 296     1 [label="y"]
 297     0 -> 0 [label="10"]
 298     0 -> 1 [label="20"]
 299 }
 300 "#);
 301 }
 302
 303 defmac!(iter_eq a, b => a.eq(b));
 304 defmac!(nodes_eq ref a, ref b => a.node_references().eq(b.node_references()));
 305 defmac!(edgew_eq ref a, ref b => a.edge_references().eq(b.edge_references()));
 306 defmac!(edges_eq ref a, ref b =>
 307         iter_eq!(
 308             a.edge_references().map(|e| (e.source(), e.target())),
 309             b.edge_references().map(|e| (e.source(), e.target()))));
 310
 311 #[test]
 312 fn from() {
 313     let mut gr1 = StableGraph::new();
 314     let a = gr1.add_node(1);
 315     let b = gr1.add_node(2);
 316     let c = gr1.add_node(3);
 317     gr1.add_edge(a, a, 10);
 318     gr1.add_edge(a, b, 20);
 319     gr1.add_edge(b, c, 30);
 320     gr1.add_edge(a, c, 40);
 321
 322     let gr2 = Graph::from(gr1.clone());
 323     let gr3 = StableGraph::from(gr2.clone());
 324     assert!(nodes_eq!(gr1, gr3));
 325     assert!(edgew_eq!(gr1, gr3));
 326     assert!(edges_eq!(gr1, gr3));
 327
 328     gr1.remove_node(b);
 329
 330     let gr4 = Graph::from(gr1.clone());
 331     let gr5 = StableGraph::from(gr4.clone());
 332
 333     let mut ans = StableGraph::new();
 334     let a = ans.add_node(1);
 335     let c = ans.add_node(3);
 336     ans.add_edge(a, a, 10);
 337     ans.add_edge(a, c, 40);
 338
 339     assert!(nodes_eq!(gr4, ans));
 340     assert!(edges_eq!(gr4, ans));
 341
 342     assert!(nodes_eq!(gr5, ans));
 343     assert!(edgew_eq!(gr5, ans));
 344     assert!(edges_eq!(gr5, ans));
 345 }