rust_igraph/algorithms/connectivity/
components.rs

1//! Weakly connected components (ALGO-CC-001).
2//!
3//! Counterpart of `igraph_connected_components()` from
4//! `references/igraph/src/connectivity/components.c:82-180` in the
5//! `IGRAPH_WEAK` (or undirected) branch.
6//!
7//! Phase 1 minimum: returns one membership entry per vertex plus the
8//! component count. Strongly-connected components (Tarjan) and
9//! component-size vector are follow-up AWUs (CC-002, CC-003).
10
11use std::collections::VecDeque;
12
13use crate::core::{Graph, IgraphResult, VertexId};
14
15/// Result of a weak connected-components scan.
16#[derive(Debug, Clone, PartialEq, Eq)]
17pub struct ConnectedComponents {
18    /// `membership[v]` == component id of vertex `v` (0-indexed).
19    pub membership: Vec<u32>,
20    /// Total number of components.
21    pub count: u32,
22}
23
24/// Compute the weak connected components of `graph`.
25///
26/// Counterpart of `igraph_connected_components(_, _, _, _, IGRAPH_WEAK)`.
27/// On undirected graphs this is just "the connected components"; on
28/// directed graphs it ignores edge direction (each edge counts as both
29/// ways).
30///
31/// # Examples
32///
33/// ```
34/// use rust_igraph::{Graph, connected_components};
35///
36/// // Two components: {0, 1, 2} and {3, 4}.
37/// let mut g = Graph::with_vertices(5);
38/// g.add_edge(0, 1).unwrap();
39/// g.add_edge(1, 2).unwrap();
40/// g.add_edge(3, 4).unwrap();
41///
42/// let cc = connected_components(&g).unwrap();
43/// assert_eq!(cc.count, 2);
44/// assert_eq!(cc.membership[0], cc.membership[1]);
45/// assert_eq!(cc.membership[1], cc.membership[2]);
46/// assert_eq!(cc.membership[3], cc.membership[4]);
47/// assert_ne!(cc.membership[0], cc.membership[3]);
48/// ```
49pub fn connected_components(graph: &Graph) -> IgraphResult<ConnectedComponents> {
50    let n = graph.vcount();
51    if n == 0 {
52        return Ok(ConnectedComponents {
53            membership: Vec::new(),
54            count: 0,
55        });
56    }
57
58    let mut membership = vec![u32::MAX; n as usize];
59    let mut count: u32 = 0;
60    let mut queue: VecDeque<VertexId> = VecDeque::new();
61
62    for start in 0..n {
63        if membership[start as usize] != u32::MAX {
64            continue;
65        }
66        let component_id = count;
67        count = count
68            .checked_add(1)
69            .ok_or(crate::core::IgraphError::Internal("too many components"))?;
70
71        membership[start as usize] = component_id;
72        queue.clear();
73        queue.push_back(start);
74        while let Some(v) = queue.pop_front() {
75            for w in graph.neighbors_iter(v)? {
76                if membership[w as usize] == u32::MAX {
77                    membership[w as usize] = component_id;
78                    queue.push_back(w);
79                }
80            }
81        }
82    }
83
84    Ok(ConnectedComponents { membership, count })
85}
86
87#[cfg(test)]
88mod tests {
89    use super::*;
90
91    #[test]
92    fn empty_graph() {
93        let g = Graph::with_vertices(0);
94        let cc = connected_components(&g).unwrap();
95        assert_eq!(cc.count, 0);
96        assert!(cc.membership.is_empty());
97    }
98
99    #[test]
100    fn n_isolated_vertices_yields_n_components() {
101        let g = Graph::with_vertices(5);
102        let cc = connected_components(&g).unwrap();
103        assert_eq!(cc.count, 5);
104        // Each vertex in its own component, ids 0..5 in order.
105        assert_eq!(cc.membership, vec![0, 1, 2, 3, 4]);
106    }
107
108    #[test]
109    fn single_path_is_one_component() {
110        let mut g = Graph::with_vertices(4);
111        g.add_edge(0, 1).unwrap();
112        g.add_edge(1, 2).unwrap();
113        g.add_edge(2, 3).unwrap();
114        let cc = connected_components(&g).unwrap();
115        assert_eq!(cc.count, 1);
116        assert_eq!(cc.membership, vec![0, 0, 0, 0]);
117    }
118
119    #[test]
120    fn two_disjoint_components_are_distinct() {
121        let mut g = Graph::with_vertices(5);
122        g.add_edge(0, 1).unwrap();
123        g.add_edge(1, 2).unwrap();
124        g.add_edge(3, 4).unwrap();
125        let cc = connected_components(&g).unwrap();
126        assert_eq!(cc.count, 2);
127        // Component ids assigned in vertex-id order: {0,1,2} → 0; {3,4} → 1.
128        assert_eq!(cc.membership, vec![0, 0, 0, 1, 1]);
129    }
130
131    #[test]
132    fn self_loop_does_not_split_component() {
133        let mut g = Graph::with_vertices(3);
134        g.add_edge(0, 0).unwrap();
135        g.add_edge(0, 1).unwrap();
136        g.add_edge(1, 2).unwrap();
137        let cc = connected_components(&g).unwrap();
138        assert_eq!(cc.count, 1);
139        assert_eq!(cc.membership, vec![0, 0, 0]);
140    }
141
142    #[test]
143    fn directed_graph_uses_weak_connectivity() {
144        // 0 -> 1 -> 2: weakly connected even though no path back.
145        let mut g = Graph::new(3, true).unwrap();
146        g.add_edge(0, 1).unwrap();
147        g.add_edge(1, 2).unwrap();
148        let cc = connected_components(&g).unwrap();
149        assert_eq!(cc.count, 1);
150        assert_eq!(cc.membership, vec![0, 0, 0]);
151    }
152
153    #[test]
154    fn membership_ids_are_dense() {
155        // Components 0..k must use exactly the ids 0..k (no gaps).
156        let mut g = Graph::with_vertices(6);
157        g.add_edge(0, 1).unwrap();
158        g.add_edge(2, 3).unwrap();
159        g.add_edge(4, 5).unwrap();
160        let cc = connected_components(&g).unwrap();
161        assert_eq!(cc.count, 3);
162        let mut seen: Vec<u32> = cc.membership.clone();
163        seen.sort_unstable();
164        seen.dedup();
165        assert_eq!(seen, vec![0, 1, 2]);
166    }
167}
rust_igraph/algorithms/connectivity/components.rs

rust_igraph/algorithms/connectivity/
components.rs
