rust_igraph/algorithms/connectivity/
subcomponent.rs

1//! Subcomponent extraction (ALGO-CC-051).
2//!
3//! Finds all vertices reachable from a given source vertex.
4//! Counterpart of `igraph_subcomponent`.
5
6use crate::core::{Graph, IgraphError, IgraphResult, VertexId};
7
8/// Direction mode for subcomponent search.
9#[derive(Debug, Clone, Copy, PartialEq, Eq)]
10pub enum SubcomponentMode {
11    /// Follow edges in the outgoing direction (for directed graphs).
12    Out,
13    /// Follow edges in the incoming direction (for directed graphs).
14    In,
15    /// Follow edges in both directions (ignore direction).
16    All,
17}
18
19/// Returns all vertices reachable from `source` following edges in the
20/// specified `mode`.
21///
22/// For undirected graphs, `mode` is ignored (all modes are equivalent).
23///
24/// The result always includes `source` itself. Vertices are returned
25/// in BFS discovery order.
26///
27/// # Errors
28///
29/// Returns `VertexOutOfRange` if `source >= vcount`.
30///
31/// # Examples
32///
33/// ```
34/// use rust_igraph::{Graph, subcomponent, SubcomponentMode};
35///
36/// let mut g = Graph::new(5, true).unwrap();
37/// g.add_edge(0, 1).unwrap();
38/// g.add_edge(1, 2).unwrap();
39/// g.add_edge(3, 4).unwrap();
40///
41/// // From vertex 0, following OUT edges: reach 0, 1, 2
42/// let reach = subcomponent(&g, 0, SubcomponentMode::Out).unwrap();
43/// assert_eq!(reach, vec![0, 1, 2]);
44///
45/// // From vertex 2, following OUT edges: only 2 (no outgoing)
46/// let reach = subcomponent(&g, 2, SubcomponentMode::Out).unwrap();
47/// assert_eq!(reach, vec![2]);
48///
49/// // From vertex 2, following IN edges: reach 2, 1, 0
50/// let reach = subcomponent(&g, 2, SubcomponentMode::In).unwrap();
51/// assert_eq!(reach, vec![2, 1, 0]);
52///
53/// // Following ALL: reach 0, 1, 2 (component of 0-1-2)
54/// let reach = subcomponent(&g, 1, SubcomponentMode::All).unwrap();
55/// assert_eq!(reach.len(), 3);
56/// ```
57pub fn subcomponent(
58    graph: &Graph,
59    source: VertexId,
60    mode: SubcomponentMode,
61) -> IgraphResult<Vec<VertexId>> {
62    let n = graph.vcount();
63    if source >= n {
64        return Err(IgraphError::VertexOutOfRange { id: source, n });
65    }
66
67    if n == 0 {
68        return Ok(Vec::new());
69    }
70
71    // Build adjacency based on mode
72    let adj = build_adj(graph, mode)?;
73
74    // BFS from source
75    let mut visited = vec![false; n as usize];
76    let mut result = Vec::new();
77    let mut queue = std::collections::VecDeque::new();
78
79    visited[source as usize] = true;
80    queue.push_back(source);
81
82    while let Some(v) = queue.pop_front() {
83        result.push(v);
84        for &nb in &adj[v as usize] {
85            if !visited[nb as usize] {
86                visited[nb as usize] = true;
87                queue.push_back(nb);
88            }
89        }
90    }
91
92    Ok(result)
93}
94
95fn build_adj(graph: &Graph, mode: SubcomponentMode) -> IgraphResult<Vec<Vec<VertexId>>> {
96    let n = graph.vcount() as usize;
97    let ecount = graph.ecount();
98    let mut adj: Vec<Vec<VertexId>> = vec![Vec::new(); n];
99
100    for eid in 0..ecount {
101        #[allow(clippy::cast_possible_truncation)]
102        let (src, tgt) = graph.edge(eid as u32)?;
103        if src == tgt {
104            continue;
105        }
106
107        if !graph.is_directed() || mode == SubcomponentMode::All {
108            adj[src as usize].push(tgt);
109            adj[tgt as usize].push(src);
110        } else if mode == SubcomponentMode::Out {
111            adj[src as usize].push(tgt);
112        } else {
113            // In mode
114            adj[tgt as usize].push(src);
115        }
116    }
117
118    Ok(adj)
119}
120
121#[cfg(test)]
122mod tests {
123    use super::*;
124
125    #[test]
126    fn test_out_of_range() {
127        let g = Graph::with_vertices(3);
128        assert!(subcomponent(&g, 5, SubcomponentMode::All).is_err());
129    }
130
131    #[test]
132    fn test_single_vertex() {
133        let g = Graph::with_vertices(1);
134        let r = subcomponent(&g, 0, SubcomponentMode::All).unwrap();
135        assert_eq!(r, vec![0]);
136    }
137
138    #[test]
139    fn test_disconnected_undirected() {
140        let mut g = Graph::with_vertices(4);
141        g.add_edge(0, 1).unwrap();
142        g.add_edge(2, 3).unwrap();
143        let r = subcomponent(&g, 0, SubcomponentMode::All).unwrap();
144        assert_eq!(r.len(), 2);
145        assert!(r.contains(&0));
146        assert!(r.contains(&1));
147    }
148
149    #[test]
150    fn test_connected_undirected() {
151        let mut g = Graph::with_vertices(4);
152        g.add_edge(0, 1).unwrap();
153        g.add_edge(1, 2).unwrap();
154        g.add_edge(2, 3).unwrap();
155        let r = subcomponent(&g, 0, SubcomponentMode::All).unwrap();
156        assert_eq!(r.len(), 4);
157    }
158
159    #[test]
160    fn test_directed_out() {
161        let mut g = Graph::new(4, true).unwrap();
162        g.add_edge(0, 1).unwrap();
163        g.add_edge(1, 2).unwrap();
164        g.add_edge(3, 0).unwrap();
165        let r = subcomponent(&g, 0, SubcomponentMode::Out).unwrap();
166        assert_eq!(r, vec![0, 1, 2]);
167    }
168
169    #[test]
170    fn test_directed_in() {
171        let mut g = Graph::new(4, true).unwrap();
172        g.add_edge(0, 1).unwrap();
173        g.add_edge(1, 2).unwrap();
174        g.add_edge(3, 0).unwrap();
175        let r = subcomponent(&g, 2, SubcomponentMode::In).unwrap();
176        assert_eq!(r, vec![2, 1, 0, 3]);
177    }
178
179    #[test]
180    fn test_directed_all() {
181        let mut g = Graph::new(5, true).unwrap();
182        g.add_edge(0, 1).unwrap();
183        g.add_edge(2, 1).unwrap();
184        g.add_edge(3, 4).unwrap();
185        let r = subcomponent(&g, 0, SubcomponentMode::All).unwrap();
186        assert_eq!(r.len(), 3);
187        assert!(r.contains(&0));
188        assert!(r.contains(&1));
189        assert!(r.contains(&2));
190    }
191
192    #[test]
193    fn test_isolated_vertex() {
194        let g = Graph::with_vertices(5);
195        let r = subcomponent(&g, 3, SubcomponentMode::All).unwrap();
196        assert_eq!(r, vec![3]);
197    }
198
199    #[test]
200    fn test_self_loop_ignored() {
201        let mut g = Graph::new(3, true).unwrap();
202        g.add_edge(0, 0).unwrap();
203        g.add_edge(0, 1).unwrap();
204        let r = subcomponent(&g, 0, SubcomponentMode::Out).unwrap();
205        assert_eq!(r, vec![0, 1]);
206    }
207
208    #[test]
209    fn test_cycle_directed_out() {
210        let mut g = Graph::new(3, true).unwrap();
211        g.add_edge(0, 1).unwrap();
212        g.add_edge(1, 2).unwrap();
213        g.add_edge(2, 0).unwrap();
214        let r = subcomponent(&g, 0, SubcomponentMode::Out).unwrap();
215        assert_eq!(r.len(), 3);
216    }
217
218    #[test]
219    fn test_bfs_order() {
220        let mut g = Graph::new(4, true).unwrap();
221        g.add_edge(0, 1).unwrap();
222        g.add_edge(0, 2).unwrap();
223        g.add_edge(1, 3).unwrap();
224        let r = subcomponent(&g, 0, SubcomponentMode::Out).unwrap();
225        assert_eq!(r[0], 0);
226        // 1 and 2 are BFS-level 1 (order depends on edge iteration)
227        assert!(r[1] == 1 || r[1] == 2);
228    }
229
230    #[test]
231    fn test_undirected_mode_ignored() {
232        let mut g = Graph::with_vertices(3);
233        g.add_edge(0, 1).unwrap();
234        g.add_edge(1, 2).unwrap();
235        // All three modes should produce the same result for undirected
236        let out = subcomponent(&g, 0, SubcomponentMode::Out).unwrap();
237        let in_ = subcomponent(&g, 0, SubcomponentMode::In).unwrap();
238        let all = subcomponent(&g, 0, SubcomponentMode::All).unwrap();
239        assert_eq!(out.len(), 3);
240        assert_eq!(in_.len(), 3);
241        assert_eq!(all.len(), 3);
242    }
243}
rust_igraph/algorithms/connectivity/subcomponent.rs

rust_igraph/algorithms/connectivity/
subcomponent.rs
