Function petgraph::algo::connected_components
source · pub fn connected_components<G>(g: G) -> usizewhere
G: NodeCompactIndexable + IntoEdgeReferences,
Expand description
[Generic] Return the number of connected components of the graph.
For a directed graph, this is the weakly connected components.
§Example
use petgraph::Graph;
use petgraph::algo::connected_components;
use petgraph::prelude::*;
let mut graph : Graph<(),(),Directed>= Graph::new();
let a = graph.add_node(()); // node with no weight
let b = graph.add_node(());
let c = graph.add_node(());
let d = graph.add_node(());
let e = graph.add_node(());
let f = graph.add_node(());
let g = graph.add_node(());
let h = graph.add_node(());
graph.extend_with_edges(&[
(a, b),
(b, c),
(c, d),
(d, a),
(e, f),
(f, g),
(g, h),
(h, e)
]);
// a ----> b e ----> f
// ^ | ^ |
// | v | v
// d <---- c h <---- g
assert_eq!(connected_components(&graph),2);
graph.add_edge(b,e,());
assert_eq!(connected_components(&graph),1);