graphrust_algos/
wcc.rs

1//! Weakly Connected Components (WCC) algorithm implementation.
2//!
3//! Finds connected components in undirected graphs or weakly connected components in directed graphs.
4
5use graphrust_core::{Graph, NodeId};
6use std::collections::{HashMap, VecDeque};
7
8/// Returns all connected components in the graph.
9///
10/// # Arguments
11/// * `graph` - The graph
12///
13/// # Returns
14/// Vector of components, where each component is a vector of node IDs
15pub fn connected_components(graph: &Graph) -> Vec<Vec<NodeId>> {
16    let n = graph.num_nodes() as usize;
17    let mut visited = vec![false; n];
18    let mut components = Vec::new();
19
20    for start_node in graph.nodes() {
21        if visited[start_node.as_usize()] {
22            continue;
23        }
24
25        let component = bfs_component(graph, start_node, &mut visited);
26        components.push(component);
27    }
28
29    components
30}
31
32/// Returns the number of connected components.
33///
34/// # Arguments
35/// * `graph` - The graph
36///
37/// # Returns
38/// Count of connected components
39pub fn component_count(graph: &Graph) -> usize {
40    let n = graph.num_nodes() as usize;
41    let mut visited = vec![false; n];
42    let mut count = 0;
43
44    for start_node in graph.nodes() {
45        if visited[start_node.as_usize()] {
46            continue;
47        }
48
49        bfs_mark(graph, start_node, &mut visited);
50        count += 1;
51    }
52
53    count
54}
55
56/// Returns a map from each node to its component ID.
57///
58/// # Arguments
59/// * `graph` - The graph
60///
61/// # Returns
62/// HashMap mapping each node to its component index
63pub fn node_component_map(graph: &Graph) -> HashMap<NodeId, usize> {
64    let n = graph.num_nodes() as usize;
65    let mut visited = vec![false; n];
66    let mut component_map = HashMap::new();
67    let mut component_id = 0;
68
69    for start_node in graph.nodes() {
70        if visited[start_node.as_usize()] {
71            continue;
72        }
73
74        bfs_component_assign(graph, start_node, &mut visited, component_id, &mut component_map);
75        component_id += 1;
76    }
77
78    component_map
79}
80
81/// BFS to find a single component starting from a node.
82fn bfs_component(graph: &Graph, start: NodeId, visited: &mut Vec<bool>) -> Vec<NodeId> {
83    let mut component = Vec::new();
84    let mut queue = VecDeque::new();
85
86    queue.push_back(start);
87    visited[start.as_usize()] = true;
88
89    while let Some(node) = queue.pop_front() {
90        component.push(node);
91
92        for &neighbor in graph.neighbors(node) {
93            if !visited[neighbor.as_usize()] {
94                visited[neighbor.as_usize()] = true;
95                queue.push_back(neighbor);
96            }
97        }
98    }
99
100    component
101}
102
103/// BFS to mark all nodes in a component as visited.
104fn bfs_mark(graph: &Graph, start: NodeId, visited: &mut Vec<bool>) {
105    let mut queue = VecDeque::new();
106
107    queue.push_back(start);
108    visited[start.as_usize()] = true;
109
110    while let Some(node) = queue.pop_front() {
111        for &neighbor in graph.neighbors(node) {
112            if !visited[neighbor.as_usize()] {
113                visited[neighbor.as_usize()] = true;
114                queue.push_back(neighbor);
115            }
116        }
117    }
118}
119
120/// BFS to assign component IDs to nodes in a component.
121fn bfs_component_assign(
122    graph: &Graph,
123    start: NodeId,
124    visited: &mut Vec<bool>,
125    component_id: usize,
126    component_map: &mut HashMap<NodeId, usize>,
127) {
128    let mut queue = VecDeque::new();
129
130    queue.push_back(start);
131    visited[start.as_usize()] = true;
132    component_map.insert(start, component_id);
133
134    while let Some(node) = queue.pop_front() {
135        for &neighbor in graph.neighbors(node) {
136            if !visited[neighbor.as_usize()] {
137                visited[neighbor.as_usize()] = true;
138                component_map.insert(neighbor, component_id);
139                queue.push_back(neighbor);
140            }
141        }
142    }
143}
144
145#[cfg(test)]
146mod tests {
147    use super::*;
148    use graphrust_core::GraphBuilder;
149
150    fn create_disconnected_graph() -> Graph {
151        // Create two components: {0,1,2} and {3}
152        GraphBuilder::new(4)
153            .add_edge(NodeId(0), NodeId(1))
154            .add_edge(NodeId(1), NodeId(2))
155            .build()
156    }
157
158    #[test]
159    fn test_connected_components() {
160        let graph = create_disconnected_graph();
161        let components = connected_components(&graph);
162
163        assert_eq!(components.len(), 2); // Two components
164        let sizes: Vec<usize> = components.iter().map(|c| c.len()).collect();
165        assert!(sizes.contains(&3));
166        assert!(sizes.contains(&1));
167    }
168
169    #[test]
170    fn test_component_count() {
171        let graph = create_disconnected_graph();
172        assert_eq!(component_count(&graph), 2);
173    }
174
175    #[test]
176    fn test_node_component_map() {
177        let graph = create_disconnected_graph();
178        let map = node_component_map(&graph);
179
180        assert_eq!(map.len(), 4);
181
182        // Nodes 0, 1, 2 should be in the same component
183        let c0 = map.get(&NodeId(0)).copied();
184        assert_eq!(map.get(&NodeId(1)).copied(), c0);
185        assert_eq!(map.get(&NodeId(2)).copied(), c0);
186
187        // Node 3 should be in a different component
188        assert_ne!(map.get(&NodeId(3)).copied(), c0);
189    }
190}
graphrust_algos/wcc.rs

graphrust_algos/
wcc.rs
