Function rs_graph::bfs::undirected
[−]
[src]
pub fn undirected<'g, G>(
g: &'g G,
u: G::Node
) -> NodeVec<'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);