graph_traversal/
components.rs

1use crate::bfs::bfs;
2use graph_core::{Graph, NodeId};
3use std::collections::HashSet;
4
5/// Returns all connected components of the graph as a `Vec<Vec<NodeId>>`.
6///
7/// Each inner `Vec` is one component — the set of nodes reachable from each
8/// other. For directed graphs, this treats edges as undirected (weak
9/// connectivity). Components are returned in the order their seed node was
10/// encountered during iteration.
11///
12/// # Examples
13///
14/// ```
15/// use graph_core::{AdjacencyList, Graph};
16/// use graph_traversal::connected_components;
17///
18/// let mut g: AdjacencyList<()> = AdjacencyList::undirected();
19/// let a = g.add_node(());
20/// let b = g.add_node(());
21/// let c = g.add_node(()); // isolated
22/// g.add_edge(a, b, 1.0).unwrap();
23///
24/// let comps = connected_components(&g);
25/// assert_eq!(comps.len(), 2);
26/// ```
27pub fn connected_components<G: Graph>(graph: &G) -> Vec<Vec<NodeId>> {
28    let mut visited: HashSet<NodeId> = HashSet::new();
29    let mut components: Vec<Vec<NodeId>> = Vec::new();
30
31    for node in graph.nodes() {
32        if !visited.contains(&node) {
33            // BFS from this seed discovers the whole component.
34            let dist = bfs(graph, node);
35            let component: Vec<NodeId> = dist.keys().copied().collect();
36            for &n in &component {
37                visited.insert(n);
38            }
39            components.push(component);
40        }
41    }
42
43    components
44}
graph_traversal/components.rs

graph_traversal/
components.rs
