Function rs_graph::bfs::undirected

pub fn undirected<'g, G>(
    g: &'g G,
    u: G::Node
) -> IndexNodeVec<'g, G, Option<G::Edge>>where
    G: IndexGraph<'g>,

Do a breath-first-search on an undirected graph starting in u.

The function returns the incoming edge of each node.

Example

use rs_graph::{LinkedListGraph, Graph, IndexGraph, classes, bfs};

let g: LinkedListGraph = classes::peterson();
let u = g.id2node(0);
let tree = bfs::undirected(&g, u);

let dist = |mut v| {
    let mut d = 0;
    while let Some(e) = tree[v] {
        let (x,y) = g.enodes(e);
        d += 1;
        v = if x == v { y } else { x };
    }
    d
};
let dists: Vec<_> = g.nodes().map(|v| dist(v)).collect();
assert!(tree[u].is_none());
assert_eq!(dists.iter().filter(|&&d| d == 0).count(), 1);
assert_eq!(dists.iter().filter(|&&d| d == 1).count(), 3);
assert_eq!(dists.iter().filter(|&&d| d == 2).count(), 6);