rust_igraph/algorithms/connectivity/
is_biconnected.rs

1//! `is_biconnected` (ALGO-CC-013).
2//!
3//! Counterpart of `igraph_is_biconnected()` from
4//! `references/igraph/src/connectivity/components.c:1254-1379`.
5//!
6//! A graph is **biconnected** if removing any single vertex (and its
7//! incident edges) does not disconnect it. Per upstream's
8//! documentation:
9//!
10//! - The null graph (n = 0) and singleton graph (n = 1) are NOT
11//!   biconnected.
12//! - The two-vertex graph with at least one connecting edge IS
13//!   biconnected (igraph's convention).
14//! - For n ≥ 3, biconnectedness ≡ weakly connected ∧ no articulation
15//!   points.
16//!
17//! Phase-1 minimal slice delegates to the existing
18//! [`crate::algorithms::connectivity::components::connected_components`]
19//! and [`crate::algorithms::connectivity::articulation::articulation_points`]
20//! primitives for n ≥ 3. Upstream's bespoke single-DFS-with-early-exit
21//! (faster on large graphs that aren't biconnected) ships in a future
22//! perf pass.
23
24use crate::core::{Graph, IgraphResult};
25
26/// Check whether `graph` is biconnected.
27///
28/// On directed graphs the input is treated as undirected (matches
29/// upstream `IGRAPH_ALL` mode default at `components.c:1292`).
30///
31/// # Examples
32///
33/// ```
34/// use rust_igraph::{Graph, is_biconnected};
35///
36/// // Triangle: biconnected.
37/// let mut g = Graph::with_vertices(3);
38/// g.add_edge(0, 1).unwrap();
39/// g.add_edge(1, 2).unwrap();
40/// g.add_edge(2, 0).unwrap();
41/// assert!(is_biconnected(&g).unwrap());
42///
43/// // Path 0-1-2: vertex 1 is an articulation point → not biconnected.
44/// let mut g = Graph::with_vertices(3);
45/// g.add_edge(0, 1).unwrap();
46/// g.add_edge(1, 2).unwrap();
47/// assert!(!is_biconnected(&g).unwrap());
48/// ```
49pub fn is_biconnected(graph: &Graph) -> IgraphResult<bool> {
50    let n = graph.vcount();
51    // Null graph + singleton are NOT biconnected (upstream
52    // components.c:1263-1268).
53    if n < 2 {
54        return Ok(false);
55    }
56    // Two-vertex special case: biconnected iff there's at least one
57    // edge between them. Self-loops alone don't count (upstream uses
58    // IGRAPH_NO_LOOPS in its lazy adjlist).
59    if n == 2 {
60        let nbrs = graph.neighbors(0)?;
61        return Ok(nbrs.contains(&1));
62    }
63    // n ≥ 3: must be weakly connected AND have no articulation points.
64    let cc = super::components::connected_components(graph)?;
65    if cc.count != 1 {
66        return Ok(false);
67    }
68    let aps = super::articulation::articulation_points(graph)?;
69    Ok(aps.is_empty())
70}
71
72#[cfg(test)]
73mod tests {
74    use super::*;
75
76    #[test]
77    fn empty_graph_is_not_biconnected() {
78        let g = Graph::with_vertices(0);
79        assert!(!is_biconnected(&g).unwrap());
80    }
81
82    #[test]
83    fn singleton_is_not_biconnected() {
84        let g = Graph::with_vertices(1);
85        assert!(!is_biconnected(&g).unwrap());
86    }
87
88    #[test]
89    fn two_vertices_no_edge_is_not_biconnected() {
90        let g = Graph::with_vertices(2);
91        assert!(!is_biconnected(&g).unwrap());
92    }
93
94    #[test]
95    fn two_vertices_one_edge_is_biconnected() {
96        let mut g = Graph::with_vertices(2);
97        g.add_edge(0, 1).unwrap();
98        assert!(is_biconnected(&g).unwrap());
99    }
100
101    #[test]
102    fn triangle_is_biconnected() {
103        let mut g = Graph::with_vertices(3);
104        g.add_edge(0, 1).unwrap();
105        g.add_edge(1, 2).unwrap();
106        g.add_edge(2, 0).unwrap();
107        assert!(is_biconnected(&g).unwrap());
108    }
109
110    #[test]
111    fn path_3_is_not_biconnected() {
112        // Vertex 1 is an articulation point.
113        let mut g = Graph::with_vertices(3);
114        g.add_edge(0, 1).unwrap();
115        g.add_edge(1, 2).unwrap();
116        assert!(!is_biconnected(&g).unwrap());
117    }
118
119    #[test]
120    fn cycle_4_is_biconnected() {
121        let mut g = Graph::with_vertices(4);
122        for i in 0..4u32 {
123            g.add_edge(i, (i + 1) % 4).unwrap();
124        }
125        assert!(is_biconnected(&g).unwrap());
126    }
127
128    #[test]
129    fn k4_complete_is_biconnected() {
130        let mut g = Graph::with_vertices(4);
131        for u in 0..4u32 {
132            for v in (u + 1)..4 {
133                g.add_edge(u, v).unwrap();
134            }
135        }
136        assert!(is_biconnected(&g).unwrap());
137    }
138
139    #[test]
140    fn disconnected_graph_is_not_biconnected() {
141        let mut g = Graph::with_vertices(4);
142        g.add_edge(0, 1).unwrap();
143        g.add_edge(2, 3).unwrap();
144        assert!(!is_biconnected(&g).unwrap());
145    }
146
147    #[test]
148    fn star_is_not_biconnected() {
149        // Centre is articulation.
150        let mut g = Graph::with_vertices(4);
151        for v in 1..4 {
152            g.add_edge(0, v).unwrap();
153        }
154        assert!(!is_biconnected(&g).unwrap());
155    }
156
157    #[test]
158    fn cycle_with_pendant_is_not_biconnected() {
159        // Triangle 0-1-2-0 + pendant 2-3: vertex 2 is articulation.
160        let mut g = Graph::with_vertices(4);
161        g.add_edge(0, 1).unwrap();
162        g.add_edge(1, 2).unwrap();
163        g.add_edge(2, 0).unwrap();
164        g.add_edge(2, 3).unwrap();
165        assert!(!is_biconnected(&g).unwrap());
166    }
167
168    #[test]
169    fn isolated_extra_vertex_breaks_biconnected() {
170        // Triangle plus an isolated vertex 3: not connected → not biconnected.
171        let mut g = Graph::with_vertices(4);
172        g.add_edge(0, 1).unwrap();
173        g.add_edge(1, 2).unwrap();
174        g.add_edge(2, 0).unwrap();
175        assert!(!is_biconnected(&g).unwrap());
176    }
177}
rust_igraph/algorithms/connectivity/is_biconnected.rs

rust_igraph/algorithms/connectivity/
is_biconnected.rs
