Function rs_graph::algorithms::components

pub fn components<G>(g: &G) -> (usize, Vec<usize>)where
    G: IndexGraph,

Determines all components of a graph.

The function numbers all components and assigns each node the number its containing component. The number of components is returned.

The empty graph has 0 components.

Example

use rs_graph::LinkedListGraph;
use rs_graph::builder::{Buildable, Builder};
use rs_graph::traits::*;
use rs_graph::{algorithms, classes};

let mut g: LinkedListGraph = classes::cycle(5);
{
    let (ncomps, comps) = algorithms::components(&g);
    assert_eq!(ncomps, 1);
    for u in g.nodes() { assert_eq!(comps[g.node_id(u)], 0); }
}

let mut v = None;
let g = LinkedListGraph::<usize>::new_with(|b| {
    let nodes = b.add_nodes(5);
    for i in 0..5 {
        b.add_edge(nodes[i], nodes[(i + 1) % 5]);
    }
    v = Some(b.add_node());
});

{
    let v = v.unwrap();
    let (ncomps, comps) = algorithms::components(&g);
    assert_eq!(ncomps, 2);
    for u in g.nodes() { assert_eq!(comps[g.node_id(u)], if u == v { 1 } else { 0 }); }
}