vendor/petgraph/tests/graph.rs

   1 extern crate petgraph;
   2
   3 use std::collections::HashSet;
   4 use std::hash::Hash;
   5
   6 use petgraph::prelude::*;
   7 use petgraph::{
   8     EdgeType,
   9 };
  10
  11 use petgraph as pg;
  12
  13 use petgraph::algo::{
  14     dominators,
  15     has_path_connecting,
  16     is_cyclic_undirected,
  17     min_spanning_tree,
  18     is_isomorphic_matching,
  19 };
  20
  21 use petgraph::graph::node_index as n;
  22 use petgraph::graph::{
  23     IndexType,
  24 };
  25
  26 use petgraph::visit::{
  27     IntoNodeIdentifiers,
  28     NodeFiltered,
  29     Reversed,
  30     Topo,
  31     IntoNeighbors,
  32     VisitMap,
  33     Walker,
  34 };
  35 use petgraph::algo::{
  36     DfsSpace,
  37     dijkstra,
  38     astar,
  39 };
  40
  41 use petgraph::dot::{
  42     Dot,
  43 };
  44
  45 fn set<I>(iter: I) -> HashSet<I::Item>
  46     where I: IntoIterator,
  47           I::Item: Hash + Eq,
  48 {
  49     iter.into_iter().collect()
  50 }
  51
  52 #[test]
  53 fn undirected()
  54 {
  55     let mut og = Graph::new_undirected();
  56     let a = og.add_node(0);
  57     let b = og.add_node(1);
  58     let c = og.add_node(2);
  59     let d = og.add_node(3);
  60     let _ = og.add_edge(a, b, 0);
  61     let _ = og.add_edge(a, c, 1);
  62     og.add_edge(c, a, 2);
  63     og.add_edge(a, a, 3);
  64     og.add_edge(b, c, 4);
  65     og.add_edge(b, a, 5);
  66     og.add_edge(a, d, 6);
  67     assert_eq!(og.node_count(), 4);
  68     assert_eq!(og.edge_count(), 7);
  69
  70     assert!(og.find_edge(a, b).is_some());
  71     assert!(og.find_edge(d, a).is_some());
  72     assert!(og.find_edge(a, a).is_some());
  73
  74     for edge in og.raw_edges() {
  75         assert!(og.find_edge(edge.source(), edge.target()).is_some());
  76         assert!(og.find_edge(edge.target(), edge.source()).is_some());
  77     }
  78
  79     assert_eq!(og.neighbors(b).collect::<Vec<_>>(), vec![a, c, a]);
  80
  81     og.remove_node(a);
  82     assert_eq!(og.neighbors(b).collect::<Vec<_>>(), vec![c]);
  83     assert_eq!(og.node_count(), 3);
  84     assert_eq!(og.edge_count(), 1);
  85     assert!(og.find_edge(a, b).is_none());
  86     assert!(og.find_edge(d, a).is_none());
  87     assert!(og.find_edge(a, a).is_none());
  88     assert!(og.find_edge(b, c).is_some());
  89     assert_graph_consistent(&og);
  90
  91 }
  92
  93 #[test]
  94 fn dfs() {
  95     let mut gr = Graph::new();
  96     let h = gr.add_node("H");
  97     let i = gr.add_node("I");
  98     let j = gr.add_node("J");
  99     let k = gr.add_node("K");
 100     // Z is disconnected.
 101     let _ = gr.add_node("Z");
 102     gr.add_edge(h, i, 1.);
 103     gr.add_edge(h, j, 3.);
 104     gr.add_edge(i, j, 1.);
 105     gr.add_edge(i, k, 2.);
 106
 107     println!("{}", Dot::new(&gr));
 108
 109     assert_eq!(Dfs::new(&gr, h).iter(&gr).count(), 4);
 110     assert_eq!(Dfs::new(&gr, h).iter(&gr).clone().count(), 4);
 111
 112     assert_eq!(Dfs::new(&gr, h).iter(Reversed(&gr)).count(), 1);
 113
 114     assert_eq!(Dfs::new(&gr, k).iter(Reversed(&gr)).count(), 3);
 115
 116     assert_eq!(Dfs::new(&gr, i).iter(&gr).count(), 3);
 117 }
 118
 119
 120 #[test]
 121 fn bfs() {
 122     let mut gr = Graph::new();
 123     let h = gr.add_node("H");
 124     let i = gr.add_node("I");
 125     let j = gr.add_node("J");
 126     let k = gr.add_node("K");
 127     // Z is disconnected.
 128     let _ = gr.add_node("Z");
 129     gr.add_edge(h, i, 1.);
 130     gr.add_edge(h, j, 3.);
 131     gr.add_edge(i, j, 1.);
 132     gr.add_edge(i, k, 2.);
 133
 134     assert_eq!(Bfs::new(&gr, h).iter(&gr).count(), 4);
 135     assert_eq!(Bfs::new(&gr, h).iter(&gr).clone().count(), 4);
 136
 137     assert_eq!(Bfs::new(&gr, h).iter(Reversed(&gr)).count(), 1);
 138
 139     assert_eq!(Bfs::new(&gr, k).iter(Reversed(&gr)).count(), 3);
 140
 141     assert_eq!(Bfs::new(&gr, i).iter(&gr).count(), 3);
 142
 143     let mut bfs = Bfs::new(&gr, h);
 144     let nx = bfs.next(&gr);
 145     assert_eq!(nx, Some(h));
 146
 147     let nx1 = bfs.next(&gr);
 148     assert!(nx1 == Some(i) || nx1 == Some(j));
 149
 150     let nx2 = bfs.next(&gr);
 151     assert!(nx2 == Some(i) || nx2 == Some(j));
 152     assert!(nx1 != nx2);
 153
 154     let nx = bfs.next(&gr);
 155     assert_eq!(nx, Some(k));
 156     assert_eq!(bfs.next(&gr), None);
 157 }
 158
 159
 160
 161 #[test]
 162 fn mst() {
 163     use petgraph::data::FromElements;
 164
 165     let mut gr = Graph::<_,_>::new();
 166     let a = gr.add_node("A");
 167     let b = gr.add_node("B");
 168     let c = gr.add_node("C");
 169     let d = gr.add_node("D");
 170     let e = gr.add_node("E");
 171     let f = gr.add_node("F");
 172     let g = gr.add_node("G");
 173     gr.add_edge(a, b, 7.);
 174     gr.add_edge(a, d, 5.);
 175     gr.add_edge(d, b, 9.);
 176     gr.add_edge(b, c, 8.);
 177     gr.add_edge(b, e, 7.);
 178     gr.add_edge(c, e, 5.);
 179     gr.add_edge(d, e, 15.);
 180     gr.add_edge(d, f, 6.);
 181     gr.add_edge(f, e, 8.);
 182     gr.add_edge(f, g, 11.);
 183     gr.add_edge(e, g, 9.);
 184
 185     // add a disjoint part
 186     let h = gr.add_node("H");
 187     let i = gr.add_node("I");
 188     let j = gr.add_node("J");
 189     gr.add_edge(h, i, 1.);
 190     gr.add_edge(h, j, 3.);
 191     gr.add_edge(i, j, 1.);
 192
 193     println!("{}", Dot::new(&gr));
 194
 195     let mst = UnGraph::from_elements(min_spanning_tree(&gr));
 196
 197     println!("{}", Dot::new(&mst));
 198     println!("{:?}", Dot::new(&mst));
 199     println!("MST is:\n{:#?}", mst);
 200     assert!(mst.node_count() == gr.node_count());
 201     // |E| = |N| - 2  because there are two disconnected components.
 202     assert!(mst.edge_count() == gr.node_count() - 2);
 203
 204     // check the exact edges are there
 205     assert!(mst.find_edge(a, b).is_some());
 206     assert!(mst.find_edge(a, d).is_some());
 207     assert!(mst.find_edge(b, e).is_some());
 208     assert!(mst.find_edge(e, c).is_some());
 209     assert!(mst.find_edge(e, g).is_some());
 210     assert!(mst.find_edge(d, f).is_some());
 211
 212     assert!(mst.find_edge(h, i).is_some());
 213     assert!(mst.find_edge(i, j).is_some());
 214
 215     assert!(mst.find_edge(d, b).is_none());
 216     assert!(mst.find_edge(b, c).is_none());
 217
 218 }
 219
 220 #[test]
 221 fn selfloop() {
 222     let mut gr = Graph::new();
 223     let a = gr.add_node("A");
 224     let b = gr.add_node("B");
 225     let c = gr.add_node("C");
 226     gr.add_edge(a, b, 7.);
 227     gr.add_edge(c, a, 6.);
 228     let sed = gr.add_edge(a, a, 2.);
 229
 230     assert!(gr.find_edge(a, b).is_some());
 231     assert!(gr.find_edge(b, a).is_none());
 232     assert!(gr.find_edge_undirected(b, a).is_some());
 233     assert!(gr.find_edge(a, a).is_some());
 234     println!("{:?}", gr);
 235
 236     gr.remove_edge(sed);
 237     assert!(gr.find_edge(a, a).is_none());
 238     println!("{:?}", gr);
 239 }
 240
 241 #[test]
 242 fn cyclic() {
 243     let mut gr = Graph::new();
 244     let a = gr.add_node("A");
 245     let b = gr.add_node("B");
 246     let c = gr.add_node("C");
 247
 248     assert!(!is_cyclic_undirected(&gr));
 249     gr.add_edge(a, b, 7.);
 250     gr.add_edge(c, a, 6.);
 251     assert!(!is_cyclic_undirected(&gr));
 252     {
 253         let e = gr.add_edge(a, a, 0.);
 254         assert!(is_cyclic_undirected(&gr));
 255         gr.remove_edge(e);
 256         assert!(!is_cyclic_undirected(&gr));
 257     }
 258
 259     {
 260         let e = gr.add_edge(b, c, 0.);
 261         assert!(is_cyclic_undirected(&gr));
 262         gr.remove_edge(e);
 263         assert!(!is_cyclic_undirected(&gr));
 264     }
 265
 266     let d = gr.add_node("D");
 267     let e = gr.add_node("E");
 268     gr.add_edge(b, d, 0.);
 269     gr.add_edge(d, e, 0.);
 270     assert!(!is_cyclic_undirected(&gr));
 271     gr.add_edge(c, e, 0.);
 272     assert!(is_cyclic_undirected(&gr));
 273     assert_graph_consistent(&gr);
 274 }
 275
 276 #[test]
 277 fn multi() {
 278     let mut gr = Graph::new();
 279     let a = gr.add_node("a");
 280     let b = gr.add_node("b");
 281     gr.add_edge(a, b, ());
 282     gr.add_edge(a, b, ());
 283     assert_eq!(gr.edge_count(), 2);
 284
 285 }
 286 #[test]
 287 fn update_edge()
 288 {
 289     {
 290         let mut gr = Graph::new();
 291         let a = gr.add_node("a");
 292         let b = gr.add_node("b");
 293         let e = gr.update_edge(a, b, 1);
 294         let f = gr.update_edge(a, b, 2);
 295         let _ = gr.update_edge(b, a, 3);
 296         assert_eq!(gr.edge_count(), 2);
 297         assert_eq!(e, f);
 298         assert_eq!(*gr.edge_weight(f).unwrap(), 2);
 299     }
 300
 301     {
 302         let mut gr = Graph::new_undirected();
 303         let a = gr.add_node("a");
 304         let b = gr.add_node("b");
 305         let e = gr.update_edge(a, b, 1);
 306         let f = gr.update_edge(b, a, 2);
 307         assert_eq!(gr.edge_count(), 1);
 308         assert_eq!(e, f);
 309         assert_eq!(*gr.edge_weight(f).unwrap(), 2);
 310     }
 311 }
 312
 313 #[test]
 314 fn dijk() {
 315     let mut g = Graph::new_undirected();
 316     let a = g.add_node("A");
 317     let b = g.add_node("B");
 318     let c = g.add_node("C");
 319     let d = g.add_node("D");
 320     let e = g.add_node("E");
 321     let f = g.add_node("F");
 322     g.add_edge(a, b, 7);
 323     g.add_edge(c, a, 9);
 324     g.add_edge(a, d, 14);
 325     g.add_edge(b, c, 10);
 326     g.add_edge(d, c, 2);
 327     g.add_edge(d, e, 9);
 328     g.add_edge(b, f, 15);
 329     g.add_edge(c, f, 11);
 330     g.add_edge(e, f, 6);
 331     println!("{:?}", g);
 332     for no in Bfs::new(&g, a).iter(&g) {
 333         println!("Visit {:?} = {:?}", no, g.node_weight(no));
 334     }
 335
 336     let scores = dijkstra(&g, a, None, |e| *e.weight());
 337     let mut scores: Vec<_> = scores.into_iter().map(|(n, s)| (g[n], s)).collect();
 338     scores.sort();
 339     assert_eq!(scores,
 340        vec![("A", 0), ("B", 7), ("C", 9), ("D", 11), ("E", 20), ("F", 20)]);
 341
 342     let scores = dijkstra(&g, a, Some(c), |e| *e.weight());
 343     assert_eq!(scores[&c], 9);
 344 }
 345
 346 #[test]
 347 fn test_astar_null_heuristic() {
 348     let mut g = Graph::new();
 349     let a = g.add_node("A");
 350     let b = g.add_node("B");
 351     let c = g.add_node("C");
 352     let d = g.add_node("D");
 353     let e = g.add_node("E");
 354     let f = g.add_node("F");
 355     g.add_edge(a, b, 7);
 356     g.add_edge(c, a, 9);
 357     g.add_edge(a, d, 14);
 358     g.add_edge(b, c, 10);
 359     g.add_edge(d, c, 2);
 360     g.add_edge(d, e, 9);
 361     g.add_edge(b, f, 15);
 362     g.add_edge(c, f, 11);
 363     g.add_edge(e, f, 6);
 364
 365     let path = astar(&g, a, |finish| finish == e, |e| *e.weight(), |_| 0);
 366     assert_eq!(path, Some((23, vec![a, d, e])));
 367
 368     // check against dijkstra
 369     let dijkstra_run = dijkstra(&g, a, Some(e), |e| *e.weight());
 370     assert_eq!(dijkstra_run[&e], 23);
 371
 372     let path = astar(&g, e, |finish| finish == b, |e| *e.weight(), |_| 0);
 373     assert_eq!(path, None);
 374 }
 375
 376 #[test]
 377 fn test_astar_manhattan_heuristic() {
 378     let mut g = Graph::new();
 379     let a = g.add_node((0., 0.));
 380     let b = g.add_node((2., 0.));
 381     let c = g.add_node((1., 1.));
 382     let d = g.add_node((0., 2.));
 383     let e = g.add_node((3., 3.));
 384     let f = g.add_node((4., 2.));
 385     let _ = g.add_node((5., 5.)); // no path to node
 386     g.add_edge(a, b, 2.);
 387     g.add_edge(a, d, 4.);
 388     g.add_edge(b, c, 1.);
 389     g.add_edge(b, f, 7.);
 390     g.add_edge(c, e, 5.);
 391     g.add_edge(e, f, 1.);
 392     g.add_edge(d, e, 1.);
 393
 394     let heuristic_for = |f: NodeIndex| {
 395         let g = &g;
 396         move |node: NodeIndex| -> f32 {
 397             let (x1, y1): (f32, f32) = g[node];
 398             let (x2, y2): (f32, f32) = g[f];
 399
 400             (x2 - x1).abs() + (y2 - y1).abs()
 401         }
 402     };
 403     let path = astar(&g, a, |finish| finish == f, |e| *e.weight(), heuristic_for(f));
 404
 405     assert_eq!(path, Some((6., vec![a, d, e, f])));
 406
 407     // check against dijkstra
 408     let dijkstra_run = dijkstra(&g, a, None, |e| *e.weight());
 409
 410     for end in g.node_indices() {
 411         let astar_path = astar(&g, a, |finish| finish == end, |e| *e.weight(),
 412                                heuristic_for(end));
 413         assert_eq!(dijkstra_run.get(&end).cloned(),
 414                    astar_path.map(|t| t.0));
 415     }
 416 }
 417
 418 #[cfg(feature = "generate")]
 419 #[test]
 420 fn test_generate_undirected() {
 421     for size in 0..4 {
 422         let mut gen = pg::generate::Generator::<Undirected>::all(size, true);
 423         let nedges = (size * size - size) / 2 + size;
 424         let mut n = 0;
 425         while let Some(g) = gen.next_ref() {
 426             n += 1;
 427             println!("{:?}", g);
 428         }
 429
 430         assert_eq!(n, 1 << nedges);
 431     }
 432 }
 433
 434 #[cfg(feature = "generate")]
 435 #[test]
 436 fn test_generate_directed() {
 437     // Number of DAG out of all graphs (all permutations) per node size
 438     //            0, 1, 2, 3,  4,   5 ..
 439     let n_dag = &[1, 1, 3, 25, 543, 29281, 3781503];
 440     for (size, &dags_exp) in (0..4).zip(n_dag) {
 441         let mut gen = pg::generate::Generator::<Directed>::all(size, true);
 442         let nedges = size * size;
 443         let mut n = 0;
 444         let mut dags = 0;
 445         while let Some(g) = gen.next_ref() {
 446             n += 1;
 447             if !pg::algo::is_cyclic_directed(g) {
 448                 dags += 1;
 449             }
 450         }
 451
 452         /*
 453         // check that all generated graphs have unique adjacency matrices
 454         let mut adjmats = graphs.iter().map(Graph::adjacency_matrix).collect::<Vec<_>>();
 455         adjmats.sort(); adjmats.dedup();
 456         assert_eq!(adjmats.len(), n);
 457         */
 458         assert_eq!(dags_exp, dags);
 459         assert_eq!(n, 1 << nedges);
 460     }
 461 }
 462
 463 #[cfg(feature = "generate")]
 464 #[test]
 465 fn test_generate_dag() {
 466     use petgraph::visit::GetAdjacencyMatrix;
 467     for size in 1..5 {
 468         let gen = pg::generate::Generator::directed_acyclic(size);
 469         let nedges = (size - 1) * size / 2;
 470         let graphs = gen.collect::<Vec<_>>();
 471
 472         assert_eq!(graphs.len(), 1 << nedges);
 473
 474         // check that all generated graphs have unique adjacency matrices
 475         let mut adjmats = graphs.iter().map(Graph::adjacency_matrix).collect::<Vec<_>>();
 476         adjmats.sort();
 477         adjmats.dedup();
 478         assert_eq!(adjmats.len(), graphs.len());
 479         for gr in &graphs {
 480             assert!(!petgraph::algo::is_cyclic_directed(gr),
 481                     "Assertion failed: {:?} acyclic", gr);
 482         }
 483     }
 484 }
 485
 486 #[test]
 487 fn without()
 488 {
 489     let mut og = Graph::new_undirected();
 490     let a = og.add_node(0);
 491     let b = og.add_node(1);
 492     let c = og.add_node(2);
 493     let d = og.add_node(3);
 494     let _ = og.add_edge(a, b, 0);
 495     let _ = og.add_edge(a, c, 1);
 496     let v: Vec<NodeIndex> = og.externals(Outgoing).collect();
 497     assert_eq!(v, vec![d]);
 498
 499     let mut og = Graph::new();
 500     let a = og.add_node(0);
 501     let b = og.add_node(1);
 502     let c = og.add_node(2);
 503     let d = og.add_node(3);
 504     let _ = og.add_edge(a, b, 0);
 505     let _ = og.add_edge(a, c, 1);
 506     let init: Vec<NodeIndex> = og.externals(Incoming).collect();
 507     let term: Vec<NodeIndex> = og.externals(Outgoing).collect();
 508     assert_eq!(init, vec![a, d]);
 509     assert_eq!(term, vec![b, c, d]);
 510 }
 511
 512 fn assert_is_topo_order<N, E>(gr: &Graph<N, E, Directed>, order: &[NodeIndex])
 513 {
 514     assert_eq!(gr.node_count(), order.len());
 515     // check all the edges of the graph
 516     for edge in gr.raw_edges() {
 517         let a = edge.source();
 518         let b = edge.target();
 519         let ai = order.iter().position(|x| *x == a).unwrap();
 520         let bi = order.iter().position(|x| *x == b).unwrap();
 521         println!("Check that {:?} is before {:?}", a, b);
 522         assert!(ai < bi, "Topo order: assertion that node {:?} is before {:?} failed",
 523                 a, b);
 524     }
 525 }
 526
 527 #[test]
 528 fn test_toposort() {
 529     let mut gr = Graph::<_,_>::new();
 530     let a = gr.add_node("A");
 531     let b = gr.add_node("B");
 532     let c = gr.add_node("C");
 533     let d = gr.add_node("D");
 534     let e = gr.add_node("E");
 535     let f = gr.add_node("F");
 536     let g = gr.add_node("G");
 537     gr.extend_with_edges(&[
 538         (a, b, 7.),
 539         (a, d, 5.),
 540         (d, b, 9.),
 541         (b, c, 8.),
 542         (b, e, 7.),
 543         (c, e, 5.),
 544         (d, e, 15.),
 545         (d, f, 6.),
 546         (f, e, 8.),
 547         (f, g, 11.),
 548         (e, g, 9.),
 549     ]);
 550
 551     // add a disjoint part
 552     let h = gr.add_node("H");
 553     let i = gr.add_node("I");
 554     let j = gr.add_node("J");
 555     gr.add_edge(h, i, 1.);
 556     gr.add_edge(h, j, 3.);
 557     gr.add_edge(i, j, 1.);
 558
 559     let order = petgraph::algo::toposort(&gr, None).unwrap();
 560     println!("{:?}", order);
 561     assert_eq!(order.len(), gr.node_count());
 562
 563     assert_is_topo_order(&gr, &order);
 564 }
 565
 566 #[test]
 567 fn test_toposort_eq() {
 568     let mut g = Graph::<_,_>::new();
 569     let a = g.add_node("A");
 570     let b = g.add_node("B");
 571     g.add_edge(a, b, ());
 572
 573     assert_eq!(petgraph::algo::toposort(&g, None), Ok(vec![a, b]));
 574 }
 575
 576 #[test]
 577 fn is_cyclic_directed() {
 578     let mut gr = Graph::<_,_>::new();
 579     let a = gr.add_node("A");
 580     let b = gr.add_node("B");
 581     let c = gr.add_node("C");
 582     let d = gr.add_node("D");
 583     let e = gr.add_node("E");
 584     let f = gr.add_node("F");
 585     let g = gr.add_node("G");
 586     gr.add_edge(a, b, 7.0);
 587     gr.add_edge(a, d, 5.);
 588     gr.add_edge(d, b, 9.);
 589     gr.add_edge(b, c, 8.);
 590     gr.add_edge(b, e, 7.);
 591     gr.add_edge(c, e, 5.);
 592     gr.add_edge(d, e, 15.);
 593     gr.add_edge(d, f, 6.);
 594     gr.add_edge(f, e, 8.);
 595     gr.add_edge(f, g, 11.);
 596     gr.add_edge(e, g, 9.);
 597
 598     assert!(!petgraph::algo::is_cyclic_directed(&gr));
 599
 600     // add a disjoint part
 601     let h = gr.add_node("H");
 602     let i = gr.add_node("I");
 603     let j = gr.add_node("J");
 604     gr.add_edge(h, i, 1.);
 605     gr.add_edge(h, j, 3.);
 606     gr.add_edge(i, j, 1.);
 607     assert!(!petgraph::algo::is_cyclic_directed(&gr));
 608
 609     gr.add_edge(g, e, 0.);
 610     assert!(petgraph::algo::is_cyclic_directed(&gr));
 611 }
 612
 613 /// Compare two scc sets. Inside each scc, the order does not matter,
 614 /// but the order of the sccs is significant.
 615 fn assert_sccs_eq(mut res: Vec<Vec<NodeIndex>>, mut answer: Vec<Vec<NodeIndex>>,
 616                   scc_order_matters: bool) {
 617     // normalize the result and compare with the answer.
 618     for scc in &mut res {
 619         scc.sort();
 620     }
 621     for scc in &mut answer {
 622         scc.sort();
 623     }
 624     if !scc_order_matters {
 625         res.sort();
 626         answer.sort();
 627     }
 628     assert_eq!(res, answer);
 629 }
 630
 631 #[test]
 632 fn scc() {
 633     let gr: Graph<(), ()> = Graph::from_edges(&[
 634         (6, 0),
 635         (0, 3),
 636         (3, 6),
 637         (8, 6),
 638         (8, 2),
 639         (2, 5),
 640         (5, 8),
 641         (7, 5),
 642         (1, 7),
 643         (7, 4),
 644         (4, 1)]);
 645
 646     assert_sccs_eq(petgraph::algo::kosaraju_scc(&gr), vec![
 647         vec![n(0), n(3), n(6)],
 648         vec![n(2), n(5), n(8)],
 649         vec![n(1), n(4), n(7)],
 650     ], true);
 651     // Reversed edges gives the same sccs (when sorted)
 652     assert_sccs_eq(petgraph::algo::kosaraju_scc(Reversed(&gr)), vec![
 653         vec![n(1), n(4), n(7)],
 654         vec![n(2), n(5), n(8)],
 655         vec![n(0), n(3), n(6)],
 656     ], true);
 657
 658
 659     // Test an undirected graph just for fun.
 660     // Sccs are just connected components.
 661     let mut hr = gr.into_edge_type::<Undirected>();
 662     // Delete an edge to disconnect it
 663     let ed = hr.find_edge(n(6), n(8)).unwrap();
 664     assert!(hr.remove_edge(ed).is_some());
 665
 666     assert_sccs_eq(petgraph::algo::kosaraju_scc(&hr), vec![
 667         vec![n(0), n(3), n(6)],
 668         vec![n(1), n(2), n(4), n(5), n(7), n(8)],
 669     ], false);
 670
 671
 672     // acyclic non-tree, #14
 673     let n = NodeIndex::new;
 674     let mut gr = Graph::new();
 675     gr.add_node(0);
 676     gr.add_node(1);
 677     gr.add_node(2);
 678     gr.add_node(3);
 679     gr.add_edge(n(3), n(2), ());
 680     gr.add_edge(n(3), n(1), ());
 681     gr.add_edge(n(2), n(0), ());
 682     gr.add_edge(n(1), n(0), ());
 683
 684     assert_sccs_eq(petgraph::algo::kosaraju_scc(&gr), vec![
 685         vec![n(0)], vec![n(1)], vec![n(2)], vec![n(3)],
 686     ], true);
 687
 688     // Kosaraju bug from PR #60
 689     let mut gr = Graph::<(), ()>::new();
 690     gr.extend_with_edges(&[
 691         (0, 0),
 692         (1, 0),
 693         (2, 0),
 694         (2, 1),
 695         (2, 2),
 696     ]);
 697     gr.add_node(());
 698     // no order for the disconnected one
 699     assert_sccs_eq(petgraph::algo::kosaraju_scc(&gr), vec![
 700         vec![n(0)], vec![n(1)], vec![n(2)], vec![n(3)],
 701     ], false);
 702 }
 703
 704
 705 #[test]
 706 fn tarjan_scc() {
 707     let gr: Graph<(), ()> = Graph::from_edges(&[
 708         (6, 0),
 709         (0, 3),
 710         (3, 6),
 711         (8, 6),
 712         (8, 2),
 713         (2, 5),
 714         (5, 8),
 715         (7, 5),
 716         (1, 7),
 717         (7, 4),
 718         (4, 1)]);
 719
 720     assert_sccs_eq(petgraph::algo::tarjan_scc(&gr), vec![
 721         vec![n(0), n(3), n(6)],
 722         vec![n(2), n(5), n(8)],
 723         vec![n(1), n(4), n(7)],
 724     ], true);
 725
 726
 727     // Test an undirected graph just for fun.
 728     // Sccs are just connected components.
 729     let mut hr = gr.into_edge_type::<Undirected>();
 730     // Delete an edge to disconnect it
 731     let ed = hr.find_edge(n(6), n(8)).unwrap();
 732     assert!(hr.remove_edge(ed).is_some());
 733
 734     assert_sccs_eq(petgraph::algo::tarjan_scc(&hr), vec![
 735         vec![n(1), n(2), n(4), n(5), n(7), n(8)],
 736         vec![n(0), n(3), n(6)],
 737     ], false);
 738
 739
 740     // acyclic non-tree, #14
 741     let n = NodeIndex::new;
 742     let mut gr = Graph::new();
 743     gr.add_node(0);
 744     gr.add_node(1);
 745     gr.add_node(2);
 746     gr.add_node(3);
 747     gr.add_edge(n(3), n(2), ());
 748     gr.add_edge(n(3), n(1), ());
 749     gr.add_edge(n(2), n(0), ());
 750     gr.add_edge(n(1), n(0), ());
 751
 752     assert_sccs_eq(petgraph::algo::tarjan_scc(&gr), vec![
 753         vec![n(0)], vec![n(1)], vec![n(2)], vec![n(3)],
 754     ], true);
 755
 756     // Kosaraju bug from PR #60
 757     let mut gr = Graph::<(), ()>::new();
 758     gr.extend_with_edges(&[
 759         (0, 0),
 760         (1, 0),
 761         (2, 0),
 762         (2, 1),
 763         (2, 2),
 764     ]);
 765     gr.add_node(());
 766     // no order for the disconnected one
 767     assert_sccs_eq(petgraph::algo::tarjan_scc(&gr), vec![
 768         vec![n(0)], vec![n(1)], vec![n(2)], vec![n(3)],
 769     ], false);
 770 }
 771
 772
 773 #[test]
 774 fn condensation()
 775 {
 776     let gr: Graph<(), ()> = Graph::from_edges(&[
 777         (6, 0),
 778         (0, 3),
 779         (3, 6),
 780         (8, 6),
 781         (8, 2),
 782         (2, 3),
 783         (2, 5),
 784         (5, 8),
 785         (7, 5),
 786         (1, 7),
 787         (7, 4),
 788         (4, 1)]);
 789
 790
 791     // make_acyclic = true
 792
 793     let cond = petgraph::algo::condensation(gr.clone(), true);
 794
 795     assert!(cond.node_count() == 3);
 796     assert!(cond.edge_count() == 2);
 797     assert!(!petgraph::algo::is_cyclic_directed(&cond),
 798             "Assertion failed: {:?} acyclic", cond);
 799
 800
 801     // make_acyclic = false
 802
 803     let cond = petgraph::algo::condensation(gr.clone(), false);
 804
 805     assert!(cond.node_count() == 3);
 806     assert!(cond.edge_count() == gr.edge_count());
 807 }
 808
 809 #[test]
 810 fn connected_comp()
 811 {
 812     let n = NodeIndex::new;
 813     let mut gr = Graph::new();
 814     gr.add_node(0);
 815     gr.add_node(1);
 816     gr.add_node(2);
 817     gr.add_node(3);
 818     gr.add_node(4);
 819     gr.add_node(5);
 820     gr.add_node(6);
 821     gr.add_node(7);
 822     gr.add_node(8);
 823     gr.add_edge(n(6), n(0), ());
 824     gr.add_edge(n(0), n(3), ());
 825     gr.add_edge(n(3), n(6), ());
 826     gr.add_edge(n(8), n(6), ());
 827     gr.add_edge(n(8), n(2), ());
 828     gr.add_edge(n(2), n(5), ());
 829     gr.add_edge(n(5), n(8), ());
 830     gr.add_edge(n(7), n(5), ());
 831     gr.add_edge(n(1), n(7), ());
 832     gr.add_edge(n(7), n(4), ());
 833     gr.add_edge(n(4), n(1), ());
 834     assert_eq!(petgraph::algo::connected_components(&gr), 1);
 835
 836     gr.add_node(9);
 837     gr.add_node(10);
 838     assert_eq!(petgraph::algo::connected_components(&gr), 3);
 839
 840     gr.add_edge(n(9), n(10), ());
 841     assert_eq!(petgraph::algo::connected_components(&gr), 2);
 842
 843     let gr = gr.into_edge_type::<Undirected>();
 844     assert_eq!(petgraph::algo::connected_components(&gr), 2);
 845 }
 846
 847 #[should_panic]
 848 #[test]
 849 fn oob_index()
 850 {
 851     let mut gr = Graph::<_, ()>::new();
 852     let a = gr.add_node(0);
 853     let b = gr.add_node(1);
 854     gr.remove_node(a);
 855     gr[b];
 856 }
 857
 858 #[test]
 859 fn usize_index()
 860 {
 861     let mut gr = Graph::<_, _, Directed, usize>::with_capacity(0, 0);
 862     let a = gr.add_node(0);
 863     let b = gr.add_node(1);
 864     let e = gr.add_edge(a, b, 1.2);
 865     let mut dfs = Dfs::new(&gr, a);
 866     while let Some(nx) = dfs.next(&gr) {
 867         gr[nx] += 1;
 868     }
 869     assert_eq!(gr[a], 1);
 870     assert_eq!(gr[b], 2);
 871     assert_eq!(gr[e], 1.2);
 872 }
 873
 874 #[test]
 875 fn u8_index()
 876 {
 877     let mut gr = Graph::<_, (), Undirected, u8>::with_capacity(0, 0);
 878     for _ in 0..255 {
 879         gr.add_node(());
 880     }
 881 }
 882
 883 #[should_panic]
 884 #[test]
 885 fn u8_index_overflow()
 886 {
 887     let mut gr = Graph::<_, (), Undirected, u8>::with_capacity(0, 0);
 888     for _ in 0..256 {
 889         gr.add_node(());
 890     }
 891 }
 892
 893 #[should_panic]
 894 #[test]
 895 fn u8_index_overflow_edges()
 896 {
 897     let mut gr = Graph::<_, (), Undirected, u8>::with_capacity(0, 0);
 898     let a = gr.add_node('a');
 899     let b = gr.add_node('b');
 900     for _ in 0..256 {
 901         gr.add_edge(a, b, ());
 902     }
 903 }
 904
 905 #[test]
 906 fn test_weight_iterators() {
 907     let mut gr = Graph::<_,_>::new();
 908     let a = gr.add_node("A");
 909     let b = gr.add_node("B");
 910     let c = gr.add_node("C");
 911     let d = gr.add_node("D");
 912     let e = gr.add_node("E");
 913     let f = gr.add_node("F");
 914     let g = gr.add_node("G");
 915     gr.add_edge(a, b, 7.0);
 916     gr.add_edge(a, d, 5.);
 917     gr.add_edge(d, b, 9.);
 918     gr.add_edge(b, c, 8.);
 919     gr.add_edge(b, e, 7.);
 920     gr.add_edge(c, e, 5.);
 921     gr.add_edge(d, e, 15.);
 922     gr.add_edge(d, f, 6.);
 923     gr.add_edge(f, e, 8.);
 924     gr.add_edge(f, g, 11.);
 925     gr.add_edge(e, g, 9.);
 926
 927     assert_eq!(gr.node_weights_mut().count(), gr.node_count());
 928     assert_eq!(gr.edge_weights_mut().count(), gr.edge_count());
 929
 930     // add a disjoint part
 931     let h = gr.add_node("H");
 932     let i = gr.add_node("I");
 933     let j = gr.add_node("J");
 934     gr.add_edge(h, i, 1.);
 935     gr.add_edge(h, j, 3.);
 936     gr.add_edge(i, j, 1.);
 937
 938     assert_eq!(gr.node_weights_mut().count(), gr.node_count());
 939     assert_eq!(gr.edge_weights_mut().count(), gr.edge_count());
 940
 941     for nw in gr.node_weights_mut() {
 942         *nw = "x";
 943     }
 944     for node in gr.raw_nodes() {
 945         assert_eq!(node.weight, "x");
 946     }
 947
 948     let old = gr.clone();
 949     for (index, ew) in gr.edge_weights_mut().enumerate() {
 950         assert_eq!(old[EdgeIndex::new(index)], *ew);
 951         *ew = - *ew;
 952     }
 953     for (index, edge) in gr.raw_edges().iter().enumerate() {
 954         assert_eq!(edge.weight, -1. * old[EdgeIndex::new(index)]);
 955     }
 956 }
 957
 958 #[test]
 959 fn walk_edges() {
 960     let mut gr = Graph::<_,_>::new();
 961     let a = gr.add_node(0.);
 962     let b = gr.add_node(1.);
 963     let c = gr.add_node(2.);
 964     let d = gr.add_node(3.);
 965     let e0 = gr.add_edge(a, b, 0.);
 966     let e1 = gr.add_edge(a, d, 0.);
 967     let e2 = gr.add_edge(b, c, 0.);
 968     let e3 = gr.add_edge(c, a, 0.);
 969
 970     // Set edge weights to difference: target - source.
 971     let mut dfs = Dfs::new(&gr, a);
 972     while let Some(source) = dfs.next(&gr) {
 973         let mut edges = gr.neighbors_directed(source, Outgoing).detach();
 974         while let Some((edge, target)) = edges.next(&gr) {
 975             gr[edge] = gr[target] - gr[source];
 976         }
 977     }
 978     assert_eq!(gr[e0], 1.);
 979     assert_eq!(gr[e1], 3.);
 980     assert_eq!(gr[e2], 1.);
 981     assert_eq!(gr[e3], -2.);
 982
 983     let mut nedges = 0;
 984     let mut dfs = Dfs::new(&gr, a);
 985     while let Some(node) = dfs.next(&gr) {
 986         let mut edges = gr.neighbors_directed(node, Incoming).detach();
 987         while let Some((edge, source)) = edges.next(&gr) {
 988             assert_eq!(gr.find_edge(source, node), Some(edge));
 989             nedges += 1;
 990         }
 991
 992         let mut edges = gr.neighbors_directed(node, Outgoing).detach();
 993         while let Some((edge, target)) = edges.next(&gr) {
 994             assert_eq!(gr.find_edge(node, target), Some(edge));
 995             nedges += 1;
 996         }
 997     }
 998     assert_eq!(nedges, 8);
 999 }
1000
1001 #[test]
1002 fn index_twice_mut() {
1003     let mut gr = Graph::<_,_>::new();
1004     let a = gr.add_node(0.);
1005     let b = gr.add_node(0.);
1006     let c = gr.add_node(0.);
1007     let d = gr.add_node(0.);
1008     let e = gr.add_node(0.);
1009     let f = gr.add_node(0.);
1010     let g = gr.add_node(0.);
1011     gr.add_edge(a, b, 7.0);
1012     gr.add_edge(a, d, 5.);
1013     gr.add_edge(d, b, 9.);
1014     gr.add_edge(b, c, 8.);
1015     gr.add_edge(b, e, 7.);
1016     gr.add_edge(c, e, 5.);
1017     gr.add_edge(d, e, 15.);
1018     gr.add_edge(d, f, 6.);
1019     gr.add_edge(f, e, 8.);
1020     gr.add_edge(f, g, 11.);
1021     gr.add_edge(e, g, 9.);
1022
1023     for dir in &[Incoming, Outgoing] {
1024         for nw in gr.node_weights_mut() { *nw = 0.; }
1025
1026         // walk the graph and sum incoming edges
1027         let mut dfs = Dfs::new(&gr, a);
1028         while let Some(node) = dfs.next(&gr) {
1029             let mut edges = gr.neighbors_directed(node, *dir).detach();
1030             while let Some(edge) = edges.next_edge(&gr) {
1031                 let (nw, ew) = gr.index_twice_mut(node, edge);
1032                 *nw += *ew;
1033             }
1034         }
1035
1036         // check the sums
1037         for i in 0..gr.node_count() {
1038             let ni = NodeIndex::new(i);
1039             let s = gr.edges_directed(ni, *dir).map(|e| *e.weight()).fold(0., |a, b| a + b);
1040             assert_eq!(s, gr[ni]);
1041         }
1042         println!("Sum {:?}: {:?}", dir, gr);
1043     }
1044 }
1045
1046 #[test]
1047 fn toposort_generic() {
1048     // This is a DAG, visit it in order
1049     let mut gr = Graph::<_,_>::new();
1050     let b = gr.add_node(("B", 0.));
1051     let a = gr.add_node(("A", 0.));
1052     let c = gr.add_node(("C", 0.));
1053     let d = gr.add_node(("D", 0.));
1054     let e = gr.add_node(("E", 0.));
1055     let f = gr.add_node(("F", 0.));
1056     let g = gr.add_node(("G", 0.));
1057     gr.add_edge(a, b, 7.0);
1058     gr.add_edge(a, d, 5.);
1059     gr.add_edge(d, b, 9.);
1060     gr.add_edge(b, c, 8.);
1061     gr.add_edge(b, e, 7.);
1062     gr.add_edge(c, e, 5.);
1063     gr.add_edge(d, e, 15.);
1064     gr.add_edge(d, f, 6.);
1065     gr.add_edge(f, e, 8.);
1066     gr.add_edge(f, g, 11.);
1067     gr.add_edge(e, g, 9.);
1068
1069     assert!(!pg::algo::is_cyclic_directed(&gr));
1070     let mut index = 0.;
1071     let mut topo = Topo::new(&gr);
1072     while let Some(nx) = topo.next(&gr) {
1073         gr[nx].1 = index;
1074         index += 1.;
1075     }
1076
1077     let mut order = Vec::new();
1078     index = 0.;
1079     let mut topo = Topo::new(&gr);
1080     while let Some(nx) = topo.next(&gr) {
1081         order.push(nx);
1082         assert_eq!(gr[nx].1, index);
1083         index += 1.;
1084     }
1085     println!("{:?}", gr);
1086     assert_is_topo_order(&gr, &order);
1087
1088     {
1089         order.clear();
1090         let mut topo = Topo::new(&gr);
1091         while let Some(nx) = topo.next(&gr) {
1092             order.push(nx);
1093         }
1094         println!("{:?}", gr);
1095         assert_is_topo_order(&gr, &order);
1096     }
1097     let mut gr2 = gr.clone();
1098     gr.add_edge(e, d, -1.);
1099     assert!(pg::algo::is_cyclic_directed(&gr));
1100     assert!(pg::algo::toposort(&gr, None).is_err());
1101     gr2.add_edge(d, d, 0.);
1102     assert!(pg::algo::is_cyclic_directed(&gr2));
1103     assert!(pg::algo::toposort(&gr2, None).is_err());
1104 }
1105
1106 #[test]
1107 fn test_has_path() {
1108     // This is a DAG, visit it in order
1109     let mut gr = Graph::<_,_>::new();
1110     let b = gr.add_node(("B", 0.));
1111     let a = gr.add_node(("A", 0.));
1112     let c = gr.add_node(("C", 0.));
1113     let d = gr.add_node(("D", 0.));
1114     let e = gr.add_node(("E", 0.));
1115     let f = gr.add_node(("F", 0.));
1116     let g = gr.add_node(("G", 0.));
1117     gr.add_edge(a, b, 7.0);
1118     gr.add_edge(a, d, 5.);
1119     gr.add_edge(d, b, 9.);
1120     gr.add_edge(b, c, 8.);
1121     gr.add_edge(b, e, 7.);
1122     gr.add_edge(c, e, 5.);
1123     gr.add_edge(d, e, 15.);
1124     gr.add_edge(d, f, 6.);
1125     gr.add_edge(f, e, 8.);
1126     gr.add_edge(f, g, 11.);
1127     gr.add_edge(e, g, 9.);
1128     // disconnected island
1129
1130     let h = gr.add_node(("H", 0.));
1131     let i = gr.add_node(("I", 0.));
1132     gr.add_edge(h, i, 2.);
1133     gr.add_edge(i, h, -2.);
1134
1135     let mut state = DfsSpace::default();
1136
1137     gr.add_edge(b, a, 99.);
1138
1139     assert!(has_path_connecting(&gr, c, c, None));
1140
1141     for edge in gr.edge_references() {
1142         assert!(has_path_connecting(&gr, edge.source(), edge.target(), None));
1143     }
1144     assert!(has_path_connecting(&gr, a, g, Some(&mut state)));
1145     assert!(!has_path_connecting(&gr, a, h, Some(&mut state)));
1146     assert!(has_path_connecting(&gr, a, c, None));
1147     assert!(has_path_connecting(&gr, a, c, Some(&mut state)));
1148     assert!(!has_path_connecting(&gr, h, a, Some(&mut state)));
1149 }
1150
1151 #[test]
1152 fn map_filter_map() {
1153     let mut g = Graph::new_undirected();
1154     let a = g.add_node("A");
1155     let b = g.add_node("B");
1156     let c = g.add_node("C");
1157     let d = g.add_node("D");
1158     let e = g.add_node("E");
1159     let f = g.add_node("F");
1160     g.add_edge(a, b, 7);
1161     g.add_edge(c, a, 9);
1162     g.add_edge(a, d, 14);
1163     g.add_edge(b, c, 10);
1164     g.add_edge(d, c, 2);
1165     g.add_edge(d, e, 9);
1166     g.add_edge(b, f, 15);
1167     g.add_edge(c, f, 11);
1168     g.add_edge(e, f, 6);
1169     println!("{:?}", g);
1170
1171     let g2 = g.filter_map(|_, name| Some(*name), |_, &weight| if weight >= 10 {
1172         Some(weight)
1173     } else { None });
1174     assert_eq!(g2.edge_count(), 4);
1175     for edge in g2.raw_edges() {
1176         assert!(edge.weight >= 10);
1177     }
1178
1179     let g3 = g.filter_map(|i, &name| if i == a || i == e { None } else { Some(name) },
1180                           |i, &weight| {
1181                               let (source, target) = g.edge_endpoints(i).unwrap();
1182                               // don't map edges from a removed node
1183                               assert!(source != a);
1184                               assert!(target != a);
1185                               assert!(source != e);
1186                               assert!(target != e);
1187                               Some(weight)
1188                           });
1189     assert_eq!(g3.node_count(), g.node_count() - 2);
1190     assert_eq!(g3.edge_count(), g.edge_count() - 5);
1191     assert_graph_consistent(&g3);
1192
1193     let mut g4 = g.clone();
1194     g4.retain_edges(|gr, i| {
1195         let (s, t) = gr.edge_endpoints(i).unwrap();
1196         !(s == a || s == e || t == a || t == e)
1197     });
1198     assert_eq!(g4.edge_count(), g.edge_count() - 5);
1199     assert_graph_consistent(&g4);
1200 }
1201
1202 #[test]
1203 fn from_edges() {
1204     let n = NodeIndex::new;
1205     let gr = Graph::<(), (), Undirected>::from_edges(&[
1206         (0, 1), (0, 2), (0, 3),
1207         (1, 2), (1, 3),
1208         (2, 3),
1209     ]);
1210     assert_eq!(gr.node_count(), 4);
1211     assert_eq!(gr.edge_count(), 6);
1212     assert_eq!(gr.neighbors(n(0)).count(), 3);
1213     assert_eq!(gr.neighbors(n(1)).count(), 3);
1214     assert_eq!(gr.neighbors(n(2)).count(), 3);
1215     assert_eq!(gr.neighbors(n(3)).count(), 3);
1216     assert_graph_consistent(&gr);
1217 }
1218
1219 #[test]
1220 fn retain() {
1221     let mut gr = Graph::<i32, i32, Undirected>::from_edges(&[
1222         (0, 1, 2),
1223         (1, 1, 1),
1224         (0, 2, 0),
1225         (1, 2, 3),
1226         (2, 3, 3),
1227     ]);
1228     gr.retain_edges(|mut gr, i| {
1229         if gr[i] <= 0 { false }
1230         else {
1231             gr[i] -= 1;
1232             let (s, t) = gr.edge_endpoints(i).unwrap();
1233             gr[s] += 1;
1234             gr[t] += 1;
1235
1236             gr[i] > 0
1237         }
1238     });
1239
1240     assert_eq!(gr.edge_count(), 3);
1241     assert_eq!(gr[n(0)], 1);
1242     assert_eq!(gr[n(1)], 4);
1243     assert_eq!(gr[n(2)], 2);
1244     assert_eq!(gr[n(3)], 1);
1245     assert!(gr.find_edge(n(1), n(1)).is_none());
1246     assert!(gr.find_edge(n(0), n(2)).is_none());
1247     assert_graph_consistent(&gr);
1248 }
1249
1250 fn assert_graph_consistent<N, E, Ty, Ix>(g: &Graph<N, E, Ty, Ix>)
1251     where Ty: EdgeType,
1252           Ix: IndexType,
1253 {
1254     assert_eq!(g.node_count(), g.node_indices().count());
1255     assert_eq!(g.edge_count(), g.edge_indices().count());
1256     for edge in g.raw_edges() {
1257         assert!(g.find_edge(edge.source(), edge.target()).is_some(),
1258                 "Edge not in graph! {:?} to {:?}", edge.source(), edge.target());
1259     }
1260 }
1261
1262 #[test]
1263 fn neighbors_selfloops() {
1264     // Directed graph
1265     let mut gr = Graph::<_ ,()>::new();
1266     let a = gr.add_node("a");
1267     let b = gr.add_node("b");
1268     let c = gr.add_node("c");
1269     gr.extend_with_edges(&[
1270         (a, a),
1271         (a, b),
1272         (c, a),
1273         (a, a),
1274     ]);
1275
1276     let out_edges = [a, a, b];
1277     let in_edges = [a, a, c];
1278     let undir_edges = [a, a, b, c];
1279     let mut seen_out = gr.neighbors(a).collect::<Vec<_>>();
1280     seen_out.sort();
1281     assert_eq!(&seen_out, &out_edges);
1282     let mut seen_in = gr.neighbors_directed(a, Incoming).collect::<Vec<_>>();
1283     seen_in.sort();
1284     assert_eq!(&seen_in, &in_edges);
1285
1286     let mut seen_undir = gr.neighbors_undirected(a).collect::<Vec<_>>();
1287     seen_undir.sort();
1288     assert_eq!(&seen_undir, &undir_edges);
1289
1290     let mut seen_out = gr.edges(a).map(|e| e.target()).collect::<Vec<_>>();
1291     seen_out.sort();
1292     assert_eq!(&seen_out, &out_edges);
1293
1294     let mut seen_walk = Vec::new();
1295     let mut walk = gr.neighbors(a).detach();
1296     while let Some(n) = walk.next_node(&gr) { seen_walk.push(n); }
1297     seen_walk.sort();
1298     assert_eq!(&seen_walk, &out_edges);
1299
1300     seen_walk.clear();
1301     let mut walk = gr.neighbors_directed(a, Incoming).detach();
1302     while let Some(n) = walk.next_node(&gr) { seen_walk.push(n); }
1303     seen_walk.sort();
1304     assert_eq!(&seen_walk, &in_edges);
1305
1306     seen_walk.clear();
1307     let mut walk = gr.neighbors_undirected(a).detach();
1308     while let Some(n) = walk.next_node(&gr) { seen_walk.push(n); }
1309     seen_walk.sort();
1310     assert_eq!(&seen_walk, &undir_edges);
1311
1312     // Undirected graph
1313     let mut gr: Graph<_, (), _> = Graph::new_undirected();
1314     let a = gr.add_node("a");
1315     let b = gr.add_node("b");
1316     let c = gr.add_node("c");
1317     gr.extend_with_edges(&[
1318         (a, a),
1319         (a, b),
1320         (c, a),
1321     ]);
1322
1323     let out_edges = [a, b, c];
1324     let in_edges = [a, b, c];
1325     let undir_edges = [a, b, c];
1326     let mut seen_out = gr.neighbors(a).collect::<Vec<_>>();
1327     seen_out.sort();
1328     assert_eq!(&seen_out, &out_edges);
1329
1330     let mut seen_out = gr.edges(a).map(|e| e.target()).collect::<Vec<_>>();
1331     seen_out.sort();
1332     assert_eq!(&seen_out, &out_edges);
1333
1334     let mut seen_in = gr.neighbors_directed(a, Incoming).collect::<Vec<_>>();
1335     seen_in.sort();
1336     assert_eq!(&seen_in, &in_edges);
1337
1338     let mut seen_undir = gr.neighbors_undirected(a).collect::<Vec<_>>();
1339     seen_undir.sort();
1340     assert_eq!(&seen_undir, &undir_edges);
1341 }
1342
1343
1344 fn degree<'a, G>(g: G, node: G::NodeId) -> usize
1345     where G: IntoNeighbors,
1346           G::NodeId: PartialEq,
1347 {
1348     // self loops count twice
1349     let original_node = node.clone();
1350     let mut degree = 0;
1351     for v in g.neighbors(node) {
1352         degree += if v == original_node { 2 } else { 1 };
1353     }
1354     degree
1355 }
1356
1357 #[cfg(feature = "graphmap")]
1358 #[test]
1359 fn degree_sequence() {
1360     let mut gr = Graph::<usize, (), Undirected>::from_edges(&[
1361         (0, 1),
1362         (1, 2), (1, 3),
1363         (2, 4), (3, 4),
1364         (4, 4),
1365         (4, 5), (3, 5),
1366     ]);
1367     gr.add_node(0); // add isolated node
1368     let mut degree_sequence = gr.node_indices()
1369                                 .map(|i| degree(&gr, i))
1370                                 .collect::<Vec<_>>();
1371
1372     degree_sequence.sort_by(|x, y| Ord::cmp(y, x));
1373     assert_eq!(&degree_sequence, &[5, 3, 3, 2, 2, 1, 0]);
1374
1375     let mut gr = GraphMap::<_, (), Undirected>::from_edges(&[
1376         (0, 1),
1377         (1, 2), (1, 3),
1378         (2, 4), (3, 4),
1379         (4, 4),
1380         (4, 5), (3, 5),
1381     ]);
1382     gr.add_node(6); // add isolated node
1383     let mut degree_sequence = gr.nodes()
1384                                 .map(|i| degree(&gr, i))
1385                                 .collect::<Vec<_>>();
1386
1387     degree_sequence.sort_by(|x, y| Ord::cmp(y, x));
1388     assert_eq!(&degree_sequence, &[5, 3, 3, 2, 2, 1, 0]);
1389 }
1390
1391 #[test]
1392 fn neighbor_order() {
1393     let mut gr = Graph::new();
1394     let a = gr.add_node("a");
1395     let b = gr.add_node("b");
1396     let c = gr.add_node("c");
1397     gr.add_edge(a, b, 0);
1398     gr.add_edge(a, a, 1);
1399
1400     gr.add_edge(c, a, 2);
1401
1402     gr.add_edge(a, c, 3);
1403
1404     gr.add_edge(c, a, 4);
1405     gr.add_edge(b, a, 5);
1406
1407     // neighbors (edges) are in lifo order, if it's a directed graph
1408     assert_eq!(gr.neighbors(a).collect::<Vec<_>>(),
1409                vec![c, a, b]);
1410     assert_eq!(gr.neighbors_directed(a, Incoming).collect::<Vec<_>>(),
1411                vec![b, c, c, a]);
1412 }
1413
1414 #[test]
1415 fn dot() {
1416     // test alternate formatting
1417     #[derive(Debug)]
1418     struct Record {
1419         a: i32,
1420         b: &'static str,
1421     };
1422     let mut gr = Graph::new();
1423     let a = gr.add_node(Record { a: 1, b: "abc" });
1424     gr.add_edge(a, a, (1, 2));
1425     let dot_output = format!("{:#?}", Dot::new(&gr));
1426     assert_eq!(dot_output,
1427 r#"digraph {
1428     0 [label="Record {\l    a: 1,\l    b: \"abc\"\l}\l"]
1429     0 -> 0 [label="(\l    1,\l    2\l)\l"]
1430 }
1431 "#);
1432 }
1433
1434 #[test]
1435 fn filtered() {
1436     let mut g = Graph::new();
1437     let a = g.add_node("A");
1438     let b = g.add_node("B");
1439     let c = g.add_node("C");
1440     let d = g.add_node("D");
1441     let e = g.add_node("E");
1442     let f = g.add_node("F");
1443     g.add_edge(a, b, 7);
1444     g.add_edge(c, a, 9);
1445     g.add_edge(a, d, 14);
1446     g.add_edge(b, c, 10);
1447     g.add_edge(d, c, 2);
1448     g.add_edge(d, e, 9);
1449     g.add_edge(b, f, 15);
1450     g.add_edge(c, f, 11);
1451     g.add_edge(e, f, 6);
1452     println!("{:?}", g);
1453
1454     let filt = NodeFiltered(&g, |n: NodeIndex| n != c && n != e);
1455
1456     let mut dfs = DfsPostOrder::new(&filt, a);
1457     let mut po = Vec::new();
1458     while let Some(nx) = dfs.next(&filt) {
1459         println!("Next: {:?}", nx);
1460         po.push(nx);
1461     }
1462     assert_eq!(set(po), set(g.node_identifiers().filter(|n| (filt.1)(*n))));
1463 }
1464
1465
1466
1467 #[test]
1468 fn dfs_visit() {
1469     use petgraph::visit::{Visitable, VisitMap};
1470     use petgraph::visit::DfsEvent::*;
1471     use petgraph::visit::{Time, depth_first_search};
1472     use petgraph::visit::Control;
1473     let gr: Graph<(), ()> = Graph::from_edges(&[
1474         (0, 5), (0, 2), (0, 3), (0, 1),
1475         (1, 3),
1476         (2, 3), (2, 4),
1477         (4, 0), (4, 5),
1478     ]);
1479
1480     let invalid_time = Time(!0);
1481     let mut discover_time = vec![invalid_time; gr.node_count()];
1482     let mut finish_time = vec![invalid_time; gr.node_count()];
1483     let mut has_tree_edge = gr.visit_map();
1484     let mut edges = HashSet::new();
1485     depth_first_search(&gr, Some(n(0)), |evt| {
1486         println!("Event: {:?}", evt);
1487         match evt {
1488             Discover(n, t) => discover_time[n.index()] = t,
1489             Finish(n, t) => finish_time[n.index()] = t,
1490             TreeEdge(u, v) => {
1491                 // v is an ancestor of u
1492                 assert!(has_tree_edge.visit(v), "Two tree edges to {:?}!", v);
1493                 assert!(discover_time[v.index()] == invalid_time);
1494                 assert!(discover_time[u.index()] != invalid_time);
1495                 assert!(finish_time[u.index()] == invalid_time);
1496                 edges.insert((u, v));
1497             }
1498             BackEdge(u, v) => {
1499                 // u is an ancestor of v
1500                 assert!(discover_time[v.index()] != invalid_time);
1501                 assert!(finish_time[v.index()] == invalid_time);
1502                 edges.insert((u, v));
1503             }
1504             CrossForwardEdge(u, v) => {
1505                 edges.insert((u, v));
1506             }
1507         }
1508     });
1509     assert!(discover_time.iter().all(|x| *x != invalid_time));
1510     assert!(finish_time.iter().all(|x| *x != invalid_time));
1511     assert_eq!(edges.len(), gr.edge_count());
1512     assert_eq!(edges, set(gr.edge_references().map(|e| (e.source(), e.target()))));
1513     println!("{:?}", discover_time);
1514     println!("{:?}", finish_time);
1515
1516     // find path from 0 to 4
1517     let mut predecessor = vec![NodeIndex::end(); gr.node_count()];
1518     let start = n(0);
1519     let goal = n(4);
1520     let ret = depth_first_search(&gr, Some(start), |event| {
1521         if let TreeEdge(u, v) = event {
1522             predecessor[v.index()] = u;
1523             if v == goal {
1524                 return Control::Break(u);
1525             }
1526         }
1527         Control::Continue
1528     });
1529     // assert we did terminate early
1530     assert!(ret.break_value().is_some());
1531     assert!(predecessor.iter().any(|x| *x == NodeIndex::end()));
1532
1533     let mut next = goal;
1534     let mut path = vec![next];
1535     while next != start {
1536         let pred = predecessor[next.index()];
1537         path.push(pred);
1538         next = pred;
1539     }
1540     path.reverse();
1541     assert_eq!(&path, &[n(0), n(2), n(4)]);
1542 }
1543
1544
1545 #[test]
1546 fn filtered_post_order() {
1547     use petgraph::visit::NodeFiltered;
1548
1549     let mut gr: Graph<(), ()> = Graph::from_edges(&[
1550         (0, 2),
1551         (1, 2),
1552         (0, 3),
1553         (1, 4),
1554         (2, 4),
1555         (4, 5),
1556         (3, 5),
1557     ]);
1558     // map reachable nodes
1559     let mut dfs = Dfs::new(&gr, n(0));
1560     while let Some(_) = dfs.next(&gr) { }
1561
1562     let map = dfs.discovered;
1563     gr.add_edge(n(0), n(1), ());
1564     let mut po = Vec::new();
1565     let mut dfs = DfsPostOrder::new(&gr, n(0));
1566     let f = NodeFiltered(&gr, map);
1567     while let Some(n) = dfs.next(&f) {
1568         po.push(n);
1569     }
1570     assert!(!po.contains(&n(1)));
1571 }
1572
1573 #[test]
1574 fn filter_elements() {
1575     use petgraph::data::Element::{Node, Edge};
1576     use petgraph::data::FromElements;
1577     use petgraph::data::ElementIterator;
1578     let elements = vec![
1579         Node { weight: "A"},
1580         Node { weight: "B"},
1581         Node { weight: "C"},
1582         Node { weight: "D"},
1583         Node { weight: "E"},
1584         Node { weight: "F"},
1585
1586         Edge { source: 0, target: 1, weight: 7 },
1587         Edge { source: 2, target: 0, weight: 9 },
1588         Edge { source: 0, target: 3, weight: 14 },
1589         Edge { source: 1, target: 2, weight: 10 },
1590         Edge { source: 3, target: 2, weight: 2 },
1591         Edge { source: 3, target: 4, weight: 9 },
1592         Edge { source: 1, target: 5, weight: 15 },
1593         Edge { source: 2, target: 5, weight: 11 },
1594         Edge { source: 4, target: 5, weight: 6 },
1595     ];
1596     let mut g = DiGraph::<_, _>::from_elements(elements.iter().cloned());
1597     println!("{:#?}", g);
1598     assert!(g.contains_edge(n(1), n(5)));
1599     let g2 = DiGraph::<_, _>::from_elements(elements.iter().cloned().filter_elements(|elt| {
1600         match elt {
1601             Node { ref weight } if **weight == "B" => false,
1602             _ => true,
1603         }
1604     }));
1605     println!("{:#?}", g2);
1606     g.remove_node(n(1));
1607     assert!(is_isomorphic_matching(&g, &g2, PartialEq::eq, PartialEq::eq));
1608 }
1609
1610 #[test]
1611 fn test_edge_filtered() {
1612     use petgraph::algo::connected_components;
1613     use petgraph::visit::EdgeFiltered;
1614     use petgraph::visit::IntoEdgeReferences;
1615
1616     let gr = UnGraph::<(), _>::from_edges(&[
1617             // cycle
1618             (0, 1, 7),
1619             (1, 2, 9),
1620             (2, 1, 14),
1621
1622             // cycle
1623             (3, 4, 10),
1624             (4, 5, 2),
1625             (5, 3, 9),
1626
1627             // cross edges
1628             (0, 3, -1),
1629             (1, 4, -2),
1630             (2, 5, -3),
1631     ]);
1632     assert_eq!(connected_components(&gr), 1);
1633     let positive_edges = EdgeFiltered::from_fn(&gr, |edge| *edge.weight() >= 0);
1634     assert_eq!(positive_edges.edge_references().count(), 6);
1635     assert!(positive_edges.edge_references().all(|edge| *edge.weight() >= 0));
1636     assert_eq!(connected_components(&positive_edges), 2);
1637
1638     let mut dfs = DfsPostOrder::new(&positive_edges, n(0));
1639     while let Some(_) = dfs.next(&positive_edges) { }
1640
1641     let n = n::<u32>;
1642     for node in &[n(0), n(1), n(2)] {
1643         assert!(dfs.discovered.is_visited(node));
1644     }
1645     for node in &[n(3), n(4), n(5)] {
1646         assert!(!dfs.discovered.is_visited(node));
1647     }
1648 }
1649
1650 #[test]
1651 fn test_dominators_simple_fast() {
1652     // Construct the following graph:
1653     //
1654     //                                  .-----.
1655     //                                  |     <--------------------------------.
1656     //          .--------+--------------|  r  |--------------.                 |
1657     //          |        |              |     |              |                 |
1658     //          |        |              '-----'              |                 |
1659     //          |     .--V--.                             .--V--.              |
1660     //          |     |     |                             |     |              |
1661     //          |     |  b  |                             |  c  |--------.     |
1662     //          |     |     |                             |     |        |     |
1663     //          |     '-----'                             '-----'        |     |
1664     //       .--V--.     |                                   |        .--V--.  |
1665     //       |     |     |                                   |        |     |  |
1666     //       |  a  <-----+                                   |   .----|  g  |  |
1667     //       |     |     |                              .----'   |    |     |  |
1668     //       '-----'     |                              |        |    '-----'  |
1669     //          |        |                              |        |       |     |
1670     //       .--V--.     |    .-----.                .--V--.     |       |     |
1671     //       |     |     |    |     |                |     |     |       |     |
1672     //       |  d  <-----+---->  e  <----.           |  f  |     |       |     |
1673     //       |     |          |     |    |           |     |     |       |     |
1674     //       '-----'          '-----'    |           '-----'     |       |     |
1675     //          |     .-----.    |       |              |        |    .--V--.  |
1676     //          |     |     |    |       |              |      .-'    |     |  |
1677     //          '----->  l  |    |       |              |      |      |  j  |  |
1678     //                |     |    '--.    |              |      |      |     |  |
1679     //                '-----'       |    |              |      |      '-----'  |
1680     //                   |       .--V--. |              |   .--V--.      |     |
1681     //                   |       |     | |              |   |     |      |     |
1682     //                   '------->  h  |-'              '--->  i  <------'     |
1683     //                           |     |          .--------->     |            |
1684     //                           '-----'          |         '-----'            |
1685     //                              |          .-----.         |               |
1686     //                              |          |     |         |               |
1687     //                              '---------->  k  <---------'               |
1688     //                                         |     |                         |
1689     //                                         '-----'                         |
1690     //                                            |                            |
1691     //                                            '----------------------------'
1692     //
1693     // This graph has the following dominator tree:
1694     //
1695     //     r
1696     //     |-- a
1697     //     |-- b
1698     //     |-- c
1699     //     |   |-- f
1700     //     |   `-- g
1701     //     |       `-- j
1702     //     |-- d
1703     //     |   `-- l
1704     //     |-- e
1705     //     |-- i
1706     //     |-- k
1707     //     `-- h
1708     //
1709     // This graph and dominator tree are taken from figures 1 and 2 of "A Fast
1710     // Algorithm for Finding Dominators in a Flowgraph" by Lengauer et al:
1711     // http://www.cs.princeton.edu/courses/archive/spr03/cs423/download/dominators.pdf.
1712
1713     let mut graph = DiGraph::<_, _>::new();
1714
1715     let r = graph.add_node("r");
1716     let a = graph.add_node("a");
1717     let b = graph.add_node("b");
1718     let c = graph.add_node("c");
1719     let d = graph.add_node("d");
1720     let e = graph.add_node("e");
1721     let f = graph.add_node("f");
1722     let g = graph.add_node("g");
1723     let h = graph.add_node("h");
1724     let i = graph.add_node("i");
1725     let j = graph.add_node("j");
1726     let k = graph.add_node("k");
1727     let l = graph.add_node("l");
1728
1729     graph.add_edge(r, a, ());
1730     graph.add_edge(r, b, ());
1731     graph.add_edge(r, c, ());
1732     graph.add_edge(a, d, ());
1733     graph.add_edge(b, a, ());
1734     graph.add_edge(b, d, ());
1735     graph.add_edge(b, e, ());
1736     graph.add_edge(c, f, ());
1737     graph.add_edge(c, g, ());
1738     graph.add_edge(d, l, ());
1739     graph.add_edge(e, h, ());
1740     graph.add_edge(f, i, ());
1741     graph.add_edge(g, i, ());
1742     graph.add_edge(g, j, ());
1743     graph.add_edge(h, e, ());
1744     graph.add_edge(h, k, ());
1745     graph.add_edge(i, k, ());
1746     graph.add_edge(j, i, ());
1747     graph.add_edge(k, r, ());
1748     graph.add_edge(k, i, ());
1749     graph.add_edge(l, h, ());
1750
1751     let doms = dominators::simple_fast(&graph, r);
1752
1753     assert_eq!(doms.root(), r);
1754     assert_eq!(doms.immediate_dominator(r), None,
1755                "The root node has no idom");
1756
1757     assert_eq!(doms.immediate_dominator(a), Some(r),
1758                "r is the immediate dominator of a");
1759     assert_eq!(doms.immediate_dominator(b), Some(r),
1760                "r is the immediate dominator of b");
1761     assert_eq!(doms.immediate_dominator(c), Some(r),
1762                "r is the immediate dominator of c");
1763     assert_eq!(doms.immediate_dominator(f), Some(c),
1764                "c is the immediate dominator of f");
1765     assert_eq!(doms.immediate_dominator(g), Some(c),
1766                "c is the immediate dominator of g");
1767     assert_eq!(doms.immediate_dominator(j), Some(g),
1768                "g is the immediate dominator of j");
1769     assert_eq!(doms.immediate_dominator(d), Some(r),
1770                "r is the immediate dominator of d");
1771     assert_eq!(doms.immediate_dominator(l), Some(d),
1772                "d is the immediate dominator of l");
1773     assert_eq!(doms.immediate_dominator(e), Some(r),
1774                "r is the immediate dominator of e");
1775     assert_eq!(doms.immediate_dominator(i), Some(r),
1776                "r is the immediate dominator of i");
1777     assert_eq!(doms.immediate_dominator(k), Some(r),
1778                "r is the immediate dominator of k");
1779     assert_eq!(doms.immediate_dominator(h), Some(r),
1780                "r is the immediate dominator of h");
1781
1782     let mut graph = graph.clone();
1783     let z = graph.add_node("z");
1784     let doms = dominators::simple_fast(&graph, r);
1785     assert_eq!(doms.immediate_dominator(z), None,
1786                "nodes that aren't reachable from the root do not have an idom");
1787 }