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_cyclic_undirected,
    min_spanning_tree,
    is_isomorphic_matching,
};

use petgraph::graph::node_index as n;
use petgraph::graph::{
    IndexType,
};

use petgraph::visit::{
    IntoNodeIdentifiers,
    NodeFiltered,
    Reversed,
    Topo,
    IntoNeighbors,
    VisitMap,
    Walker,
};
use petgraph::algo::{
    DfsSpace,
    dijkstra,
    astar,
};

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 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 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);
    }
}

#[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::{Visitable, VisitMap};
    use petgraph::visit::DfsEvent::*;
    use petgraph::visit::{Time, depth_first_search};
    use petgraph::visit::Control;
    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::{Node, Edge};
    use petgraph::data::FromElements;
    use petgraph::data::ElementIterator;
    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");
    assert_eq!(doms.immediate_dominator(k), Some(r),
               "r is the immediate dominator of k");
    assert_eq!(doms.immediate_dominator(h), Some(r),
               "r is the immediate dominator of h");

    let mut graph = graph.clone();
    let z = graph.add_node("z");
    let doms = dominators::simple_fast(&graph, r);
    assert_eq!(doms.immediate_dominator(z), None,
               "nodes that aren't reachable from the root do not have an idom");
}