rust_igraph/algorithms/connectivity/
articulation.rs

1//! Articulation points (ALGO-CC-010).
2//!
3//! Counterpart of `igraph_articulation_points()` from
4//! `references/igraph/src/connectivity/components.c:969-972`, which is
5//! itself the
6//! `igraph_biconnected_components(_, NULL, NULL, NULL, NULL, &result)`
7//! reduction. We port the same iterative DFS with low-link tracking
8//! (lines 1085-1209) but emit only the articulation-point vector.
9//!
10//! Phase-1 minimal slice — full `biconnected_components` (component
11//! vertex sets, component edges, spanning-tree edges) lands in CC-011.
12//!
13//! An *articulation point* is a vertex whose removal increases the
14//! number of (weakly) connected components. The graph is treated as
15//! undirected.
16
17use crate::core::graph::EdgeId;
18use crate::core::{Graph, IgraphError, IgraphResult, VertexId};
19
20/// Articulation points of `graph` (returns vertices in upstream's
21/// DFS-discovery order).
22///
23/// On directed graphs the input is treated as undirected (matching
24/// upstream igraph's `IGRAPH_ALL` mode default at
25/// `components.c:1060`).
26///
27/// # Examples
28///
29/// ```
30/// use rust_igraph::{Graph, articulation_points};
31///
32/// // Cycle 0-1-2-0 plus pendant 2-3-4: vertices 2 and 3 are articulation points.
33/// let mut g = Graph::with_vertices(5);
34/// g.add_edge(0, 1).unwrap();
35/// g.add_edge(1, 2).unwrap();
36/// g.add_edge(2, 0).unwrap();
37/// g.add_edge(2, 3).unwrap();
38/// g.add_edge(3, 4).unwrap();
39/// let mut ap = articulation_points(&g).unwrap();
40/// ap.sort_unstable();
41/// assert_eq!(ap, vec![2, 3]);
42/// ```
43pub fn articulation_points(graph: &Graph) -> IgraphResult<Vec<VertexId>> {
44    let n = graph.vcount();
45    if n == 0 {
46        return Ok(Vec::new());
47    }
48    let n_us = n as usize;
49
50    // `num[v]` = DFS pre-order index, 1-based; 0 means "unvisited".
51    // `low[v]` = lowest `num` reachable from v's DFS subtree using at
52    // most one back-edge. Initialised to 0 = unvisited.
53    let mut num: Vec<u32> = vec![0; n_us];
54    let mut low: Vec<u32> = vec![0; n_us];
55    // `nextptr[v]` = next index into v's incident-edge list to visit.
56    let mut nextptr: Vec<usize> = vec![0; n_us];
57    // dedup ART points (a non-root vertex may be an articulation parent
58    // of multiple DFS-tree children; we want one entry).
59    let mut found: Vec<bool> = vec![false; n_us];
60    // Active DFS path (stack of vertices).
61    let mut path: Vec<VertexId> = Vec::new();
62    // Output, in upstream's DFS-discovery order.
63    let mut articulation: Vec<VertexId> = Vec::new();
64    let mut counter: u32 = 1;
65
66    // Pre-cache incident-edge lists once. Memory parity with upstream's
67    // `igraph_inclist_init(graph, &inclist, IGRAPH_ALL, IGRAPH_LOOPS_TWICE)`.
68    let mut inc: Vec<Vec<EdgeId>> = Vec::with_capacity(n_us);
69    for v in 0..n {
70        inc.push(graph.incident(v)?);
71    }
72
73    for i in 0..n {
74        if low[i as usize] != 0 {
75            continue; // already part of an earlier DFS tree
76        }
77        path.push(i);
78        let mut rootdfs: u32 = 0;
79        num[i as usize] = counter;
80        low[i as usize] = counter;
81        counter = counter
82            .checked_add(1)
83            .ok_or(IgraphError::Internal("DFS counter overflow"))?;
84
85        while let Some(&act) = path.last() {
86            let act_us = act as usize;
87            let nbrs = &inc[act_us];
88            let actnext = nextptr[act_us];
89
90            if actnext < nbrs.len() {
91                // Step DOWN if neighbour is unvisited; else update low via back-edge.
92                let edge = nbrs[actnext];
93                let nei = graph.edge_other(edge, act)?;
94                if low[nei as usize] == 0 {
95                    if act == i {
96                        rootdfs = rootdfs.saturating_add(1);
97                    }
98                    path.push(nei);
99                    num[nei as usize] = counter;
100                    low[nei as usize] = counter;
101                    counter = counter
102                        .checked_add(1)
103                        .ok_or(IgraphError::Internal("DFS counter overflow"))?;
104                } else if num[nei as usize] < low[act_us] {
105                    low[act_us] = num[nei as usize];
106                }
107                nextptr[act_us] += 1;
108            } else {
109                // Step UP — record articulation if applicable.
110                path.pop();
111                if let Some(&prev) = path.last() {
112                    let prev_us = prev as usize;
113                    if low[act_us] < low[prev_us] {
114                        low[prev_us] = low[act_us];
115                    }
116                    if low[act_us] >= num[prev_us] && !found[prev_us] && prev != i {
117                        articulation.push(prev);
118                        found[prev_us] = true;
119                    }
120                }
121            }
122        }
123
124        if rootdfs >= 2 {
125            articulation.push(i);
126            // No `found` dedup needed — each root is processed once.
127        }
128    }
129
130    Ok(articulation)
131}
132
133#[cfg(test)]
134mod tests {
135    use super::*;
136
137    fn ap_sorted(g: &Graph) -> Vec<VertexId> {
138        let mut ap = articulation_points(g).unwrap();
139        ap.sort_unstable();
140        ap
141    }
142
143    #[test]
144    fn empty_graph_has_no_articulation_points() {
145        let g = Graph::with_vertices(0);
146        assert!(articulation_points(&g).unwrap().is_empty());
147    }
148
149    #[test]
150    fn isolated_vertices_have_no_articulation_points() {
151        let g = Graph::with_vertices(5);
152        assert!(articulation_points(&g).unwrap().is_empty());
153    }
154
155    #[test]
156    fn cycle_has_no_articulation_points() {
157        // 4-cycle: every vertex is on a cycle, none can disconnect the rest.
158        let mut g = Graph::with_vertices(4);
159        g.add_edge(0, 1).unwrap();
160        g.add_edge(1, 2).unwrap();
161        g.add_edge(2, 3).unwrap();
162        g.add_edge(3, 0).unwrap();
163        assert!(articulation_points(&g).unwrap().is_empty());
164    }
165
166    #[test]
167    fn path_endpoints_are_not_articulation_points() {
168        // Path 0-1-2-3-4: only the internal vertices 1, 2, 3 are articulation.
169        let mut g = Graph::with_vertices(5);
170        for i in 0..4 {
171            g.add_edge(i, i + 1).unwrap();
172        }
173        assert_eq!(ap_sorted(&g), vec![1, 2, 3]);
174    }
175
176    #[test]
177    fn star_centre_is_only_articulation_point() {
178        // Star with centre 0 and 4 leaves: removing 0 disconnects all leaves.
179        let mut g = Graph::with_vertices(5);
180        for v in 1..5 {
181            g.add_edge(0, v).unwrap();
182        }
183        assert_eq!(ap_sorted(&g), vec![0]);
184    }
185
186    #[test]
187    fn cycle_with_pendant_has_attachment_and_internal_pendant_as_aps() {
188        // Cycle 0-1-2-0 plus pendant 2-3-4 → 2 and 3 are articulation.
189        let mut g = Graph::with_vertices(5);
190        g.add_edge(0, 1).unwrap();
191        g.add_edge(1, 2).unwrap();
192        g.add_edge(2, 0).unwrap();
193        g.add_edge(2, 3).unwrap();
194        g.add_edge(3, 4).unwrap();
195        assert_eq!(ap_sorted(&g), vec![2, 3]);
196    }
197
198    #[test]
199    fn multiple_components_each_contributes_independently() {
200        // Two paths 0-1-2 and 3-4-5: 1 and 4 are articulation points.
201        let mut g = Graph::with_vertices(6);
202        g.add_edge(0, 1).unwrap();
203        g.add_edge(1, 2).unwrap();
204        g.add_edge(3, 4).unwrap();
205        g.add_edge(4, 5).unwrap();
206        assert_eq!(ap_sorted(&g), vec![1, 4]);
207    }
208
209    #[test]
210    fn upstream_biconnected_test_fixture_yields_5_and_2() {
211        // From references/igraph/tests/unit/igraph_biconnected_components.c
212        // Edges: 0-1, 1-2, 2-3, 3-0, 2-4, 4-5, 5-2, 5-6, 7-8 (vertex 9 isolated).
213        // Expected articulation points (per .out): {5, 2}.
214        let mut g = Graph::with_vertices(10);
215        for &(u, v) in &[
216            (0, 1),
217            (1, 2),
218            (2, 3),
219            (3, 0),
220            (2, 4),
221            (4, 5),
222            (5, 2),
223            (5, 6),
224            (7, 8),
225        ] {
226            g.add_edge(u, v).unwrap();
227        }
228        assert_eq!(ap_sorted(&g), vec![2, 5]);
229    }
230
231    #[test]
232    fn self_loop_does_not_create_articulation() {
233        // Triangle plus a self-loop on 0: still no articulation points.
234        let mut g = Graph::with_vertices(3);
235        g.add_edge(0, 0).unwrap();
236        g.add_edge(0, 1).unwrap();
237        g.add_edge(1, 2).unwrap();
238        g.add_edge(2, 0).unwrap();
239        assert!(articulation_points(&g).unwrap().is_empty());
240    }
241
242    #[test]
243    fn parallel_edges_collapse_to_single_link_for_articulation() {
244        // 0-1 with three parallel edges plus 1-2: vertex 1 is still
245        // articulation (removing it disconnects 2 from 0).
246        let mut g = Graph::with_vertices(3);
247        g.add_edge(0, 1).unwrap();
248        g.add_edge(0, 1).unwrap();
249        g.add_edge(0, 1).unwrap();
250        g.add_edge(1, 2).unwrap();
251        assert_eq!(ap_sorted(&g), vec![1]);
252    }
253
254    #[test]
255    fn two_triangles_sharing_a_vertex_make_that_vertex_articulation() {
256        // 0-1-2-0 and 2-3-4-2: vertex 2 is the only articulation point.
257        let mut g = Graph::with_vertices(5);
258        g.add_edge(0, 1).unwrap();
259        g.add_edge(1, 2).unwrap();
260        g.add_edge(2, 0).unwrap();
261        g.add_edge(2, 3).unwrap();
262        g.add_edge(3, 4).unwrap();
263        g.add_edge(4, 2).unwrap();
264        assert_eq!(ap_sorted(&g), vec![2]);
265    }
266}
rust_igraph/algorithms/connectivity/articulation.rs

rust_igraph/algorithms/connectivity/
articulation.rs
