petgraph/tests/list.rs

extern crate itertools;
extern crate petgraph;
#[macro_use]
extern crate defmac;

use petgraph::adj::DefaultIx;
use petgraph::adj::IndexType;
use petgraph::adj::{List, UnweightedList};
use petgraph::algo::tarjan_scc;
use petgraph::data::{DataMap, DataMapMut};
use petgraph::dot::Dot;
use petgraph::prelude::*;
use petgraph::visit::{
    IntoEdgeReferences, IntoEdges, IntoNeighbors, IntoNodeReferences, NodeCount, NodeIndexable,
};

use itertools::assert_equal;

fn n(x: u32) -> DefaultIx {
    DefaultIx::new(x as _)
}

#[test]
fn node_indices() {
    let mut g = List::<()>::new();
    let a = g.add_node();
    let b = g.add_node();
    let c = g.add_node();
    let mut iter = g.node_indices();
    assert_eq!(iter.next(), Some(a));
    assert_eq!(iter.next(), Some(b));
    assert_eq!(iter.next(), Some(c));
    assert_eq!(iter.next(), None);
}

fn test_node_count<E>(g: &List<E>, n: usize) {
    assert_eq!(n, g.node_count());
    assert_eq!(g.node_bound(), n);
    assert_eq!(g.node_indices().count(), n);
    assert_eq!(g.node_indices().len(), n);
    assert_eq!(g.node_references().count(), n);
    assert_eq!(g.node_references().len(), n);
}

#[test]
fn node_bound() {
    let mut g = List::<()>::new();
    test_node_count(&g, 0);
    for i in 0..10 {
        g.add_node();
        test_node_count(&g, i + 1);
    }
    g.clear();
    test_node_count(&g, 0);
}

fn assert_sccs_eq<Ix: IndexType>(mut res: Vec<Vec<Ix>>, normalized: Vec<Vec<Ix>>) {
    // normalize the result and compare with the answer.
    for scc in &mut res {
        scc.sort();
    }
    // sort by minimum element
    res.sort_by(|v, w| v[0].cmp(&w[0]));
    assert_eq!(res, normalized);
}

fn scc_graph() -> UnweightedList<DefaultIx> {
    let mut gr = List::new();
    for _ in 0..9 {
        gr.add_node();
    }
    for (a, b) in &[
        (6, 0),
        (0, 3),
        (3, 6),
        (8, 6),
        (8, 2),
        (2, 5),
        (5, 8),
        (7, 5),
        (1, 7),
    ] {
        gr.add_edge(n(*a), n(*b), ());
    }
    // make an identical replacement of n(4) and leave a hole
    let x = gr.add_node();
    gr.add_edge(n(7), x, ());
    gr.add_edge(x, n(1), ());
    gr
}

#[test]
fn test_tarjan_scc() {
    let gr = scc_graph();

    let x = n(gr.node_bound() as u32 - 1);
    assert_sccs_eq(
        tarjan_scc(&gr),
        vec![
            vec![n(0), n(3), n(6)],
            vec![n(1), n(7), x],
            vec![n(2), n(5), n(8)],
            vec![n(4)],
        ],
    );
}

fn make_graph() -> List<i32> {
    let mut gr = List::new();
    let mut c = 0..;
    let mut e = || -> i32 { c.next().unwrap() };
    for _ in 0..=9 {
        gr.add_node();
    }
    for &(from, to) in &[
        (6, 0),
        (0, 3),
        (3, 6),
        (8, 6),
        (8, 2),
        (2, 5),
        (5, 8),
        (7, 5),
        (1, 7),
        (7, 9),
        (8, 6), // parallel edge
        (9, 1),
        (9, 9),
        (9, 9),
    ] {
        gr.add_edge(n(from), n(to), e());
    }
    gr
}

defmac!(edges ref gr, x => gr.edges(x).map(|r| (r.target(), *r.weight())));

#[test]
fn test_edges_directed() {
    let gr = make_graph();
    dbg!(&gr);
    let x = n(9);
    assert_equal(edges!(&gr, x), vec![(1, 11), (x, 12), (x, 13)]);
    assert_equal(edges!(&gr, n(0)), vec![(n(3), 1)]);
    //assert_equal(edges!(&gr, n(4)), vec![]);
}

#[test]
fn test_edge_references() {
    let mut gr = make_graph();
    assert_eq!(gr.edge_count(), gr.edge_references().count());
    for i in gr.edge_references() {
        assert_eq!(gr.edge_endpoints(i.id()), Some((i.source(), i.target())));
        assert_eq!(gr.edge_weight(i.id()), Some(i.weight()));
    }
    for n in gr.node_indices() {
        for e in gr.edge_indices_from(n) {
            match gr.edge_weight_mut(e) {
                None => {}
                Some(r) => {
                    *r = 1;
                }
            }
        }
    }
    for i in gr.edge_references() {
        assert_eq!(*i.weight(), 1);
    }
}

#[test]
fn test_edge_iterators() {
    let gr = make_graph();
    for i in gr.node_indices() {
        itertools::assert_equal(
            gr.neighbors(n(i)),
            gr.edges(n(i)).map(|r| {
                assert_eq!(r.source(), n(i));
                r.target()
            }),
        );
    }
}

#[test]
#[should_panic(expected = "is not a valid node")]
fn add_edge_vacant() {
    let mut g = List::new();
    let a: DefaultIx = g.add_node();
    let b = g.add_node();
    let _ = g.add_node();
    g.clear();
    g.add_edge(a, b, 1);
}

#[test]
#[should_panic(expected = "is not a valid node")]
fn add_edge_oob() {
    let mut g = List::new();
    let a = g.add_node();
    let _ = g.add_node();
    let _ = g.add_node();
    g.add_edge(a, n(4), 1);
}

#[test]
#[should_panic(expected = "index out of bounds")]
fn add_edge_oob_2() {
    let mut g = List::new();
    let a = g.add_node();
    let _ = g.add_node();
    let _ = g.add_node();
    g.add_edge(n(4), a, 1);
}

#[test]
fn test_node_references() {
    let gr = scc_graph();

    itertools::assert_equal(gr.node_references(), gr.node_indices());
}

#[test]
fn iterators_undir() {
    let mut g = List::with_capacity(2);
    let a = g.add_node();
    let b = g.add_node();
    let c = g.add_node();
    let d = g.add_node();
    for &(from, to, w) in &[(a, b, 1), (a, c, 2), (b, c, 3), (c, c, 4), (a, d, 5)] {
        g.add_edge(n(from), n(to), w);
    }

    itertools::assert_equal(g.neighbors(a), vec![b, c, d]);
    itertools::assert_equal(g.neighbors(c), vec![c]);
    itertools::assert_equal(g.neighbors(d), vec![]);

    itertools::assert_equal(g.neighbors(b), vec![c]);
}

#[test]
fn dot() {
    let mut gr = List::new();
    let a: DefaultIx = gr.add_node();
    let b = gr.add_node();
    gr.add_edge(a, a, 10u8);
    gr.add_edge(a, b, 20);
    let dot_output = format!("{:?}", Dot::new(&gr));
    assert_eq!(
        dot_output,
        r#"digraph {
    0 [ label = "()" ]
    1 [ label = "()" ]
    0 -> 0 [ label = "10" ]
    0 -> 1 [ label = "20" ]
}
"#
    );
}