vendor/petgraph/tests/stable_graph.rs

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