rust_igraph/algorithms/properties/
is_cactus.rs

1//! Cactus graph predicate (ALGO-PR-071).
2//!
3//! A cactus graph (also called a Husimi tree) is a connected graph in
4//! which every biconnected component is either a single edge or a
5//! simple cycle. Equivalently, every edge belongs to at most one
6//! simple cycle.
7
8use crate::algorithms::connectivity::biconnected::biconnected_components;
9use crate::algorithms::connectivity::is_connected::{ConnectednessMode, is_connected};
10use crate::core::{Graph, IgraphResult};
11
12/// Check whether a graph is a cactus graph.
13///
14/// A cactus graph is a connected graph where every biconnected
15/// component is either a single edge (bridge) or a simple cycle.
16///
17/// An empty graph (0 vertices) is considered a cactus (vacuously).
18/// A single vertex with no edges is a cactus.
19/// A graph that is not connected is NOT a cactus.
20///
21/// For directed graphs, connectivity is checked as weak connectivity
22/// and edges are treated as undirected for the biconnected component
23/// decomposition.
24///
25/// # Examples
26///
27/// ```
28/// use rust_igraph::{Graph, is_cactus_graph};
29///
30/// // Triangle is a cactus (one cycle component)
31/// let mut g = Graph::with_vertices(3);
32/// g.add_edge(0, 1).unwrap();
33/// g.add_edge(1, 2).unwrap();
34/// g.add_edge(2, 0).unwrap();
35/// assert!(is_cactus_graph(&g).unwrap());
36///
37/// // K4 is NOT a cactus (biconnected component has too many edges)
38/// let mut g = Graph::with_vertices(4);
39/// for u in 0..4u32 {
40///     for v in (u + 1)..4 {
41///         g.add_edge(u, v).unwrap();
42///     }
43/// }
44/// assert!(!is_cactus_graph(&g).unwrap());
45/// ```
46pub fn is_cactus_graph(graph: &Graph) -> IgraphResult<bool> {
47    let n = graph.vcount();
48
49    if n <= 1 {
50        return Ok(true);
51    }
52
53    if !is_connected(graph, ConnectednessMode::Weak)? {
54        return Ok(false);
55    }
56
57    let bc = biconnected_components(graph)?;
58
59    for i in 0..bc.count as usize {
60        let n_verts = bc.components[i].len();
61        let n_edges = bc.component_edges[i].len();
62
63        if n_edges == 1 {
64            continue;
65        }
66
67        if n_edges != n_verts {
68            return Ok(false);
69        }
70    }
71
72    Ok(true)
73}
74
75#[cfg(test)]
76mod tests {
77    use super::*;
78
79    #[test]
80    fn empty_graph() {
81        let g = Graph::with_vertices(0);
82        assert!(is_cactus_graph(&g).unwrap());
83    }
84
85    #[test]
86    fn single_vertex() {
87        let g = Graph::with_vertices(1);
88        assert!(is_cactus_graph(&g).unwrap());
89    }
90
91    #[test]
92    fn single_edge() {
93        let mut g = Graph::with_vertices(2);
94        g.add_edge(0, 1).unwrap();
95        assert!(is_cactus_graph(&g).unwrap());
96    }
97
98    #[test]
99    fn path_3() {
100        let mut g = Graph::with_vertices(3);
101        g.add_edge(0, 1).unwrap();
102        g.add_edge(1, 2).unwrap();
103        assert!(is_cactus_graph(&g).unwrap());
104    }
105
106    #[test]
107    fn triangle() {
108        let mut g = Graph::with_vertices(3);
109        g.add_edge(0, 1).unwrap();
110        g.add_edge(1, 2).unwrap();
111        g.add_edge(2, 0).unwrap();
112        assert!(is_cactus_graph(&g).unwrap());
113    }
114
115    #[test]
116    fn two_cycles_sharing_vertex() {
117        // Two triangles sharing vertex 2: 0-1-2-0 and 2-3-4-2
118        let mut g = Graph::with_vertices(5);
119        g.add_edge(0, 1).unwrap();
120        g.add_edge(1, 2).unwrap();
121        g.add_edge(2, 0).unwrap();
122        g.add_edge(2, 3).unwrap();
123        g.add_edge(3, 4).unwrap();
124        g.add_edge(4, 2).unwrap();
125        assert!(is_cactus_graph(&g).unwrap());
126    }
127
128    #[test]
129    fn cycle_with_bridge() {
130        // Triangle 0-1-2-0 with bridge 2-3
131        let mut g = Graph::with_vertices(4);
132        g.add_edge(0, 1).unwrap();
133        g.add_edge(1, 2).unwrap();
134        g.add_edge(2, 0).unwrap();
135        g.add_edge(2, 3).unwrap();
136        assert!(is_cactus_graph(&g).unwrap());
137    }
138
139    #[test]
140    fn k4_not_cactus() {
141        let mut g = Graph::with_vertices(4);
142        for u in 0..4u32 {
143            for v in (u + 1)..4 {
144                g.add_edge(u, v).unwrap();
145            }
146        }
147        assert!(!is_cactus_graph(&g).unwrap());
148    }
149
150    #[test]
151    fn disconnected_not_cactus() {
152        let mut g = Graph::with_vertices(4);
153        g.add_edge(0, 1).unwrap();
154        g.add_edge(2, 3).unwrap();
155        assert!(!is_cactus_graph(&g).unwrap());
156    }
157
158    #[test]
159    fn cycle_4() {
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, 3).unwrap();
164        g.add_edge(3, 0).unwrap();
165        assert!(is_cactus_graph(&g).unwrap());
166    }
167
168    #[test]
169    fn cycle_4_with_diagonal_not_cactus() {
170        // C4 + diagonal: forms K4 minus one edge, which has a
171        // biconnected component with 4 vertices and 5 edges → not cactus
172        let mut g = Graph::with_vertices(4);
173        g.add_edge(0, 1).unwrap();
174        g.add_edge(1, 2).unwrap();
175        g.add_edge(2, 3).unwrap();
176        g.add_edge(3, 0).unwrap();
177        g.add_edge(0, 2).unwrap();
178        assert!(!is_cactus_graph(&g).unwrap());
179    }
180
181    #[test]
182    fn star_is_cactus() {
183        let mut g = Graph::with_vertices(5);
184        for i in 1..5u32 {
185            g.add_edge(0, i).unwrap();
186        }
187        assert!(is_cactus_graph(&g).unwrap());
188    }
189
190    #[test]
191    fn tree_is_cactus() {
192        // Any tree is a cactus
193        let mut g = Graph::with_vertices(7);
194        g.add_edge(0, 1).unwrap();
195        g.add_edge(0, 2).unwrap();
196        g.add_edge(1, 3).unwrap();
197        g.add_edge(1, 4).unwrap();
198        g.add_edge(2, 5).unwrap();
199        g.add_edge(2, 6).unwrap();
200        assert!(is_cactus_graph(&g).unwrap());
201    }
202
203    #[test]
204    fn self_loop_cactus() {
205        let mut g = Graph::with_vertices(2);
206        g.add_edge(0, 0).unwrap();
207        g.add_edge(0, 1).unwrap();
208        assert!(is_cactus_graph(&g).unwrap());
209    }
210
211    #[test]
212    fn directed_cycle_cactus() {
213        let mut g = Graph::new(3, true).unwrap();
214        g.add_edge(0, 1).unwrap();
215        g.add_edge(1, 2).unwrap();
216        g.add_edge(2, 0).unwrap();
217        assert!(is_cactus_graph(&g).unwrap());
218    }
219
220    #[test]
221    fn parallel_edges_not_cactus() {
222        // Two parallel edges between same vertices: biconnected
223        // component has 2 vertices, 2 edges → that's a 2-cycle, ok
224        let mut g = Graph::with_vertices(2);
225        g.add_edge(0, 1).unwrap();
226        g.add_edge(0, 1).unwrap();
227        // Actually: 2 vertices, 2 edges = a cycle of length 2 → cactus
228        assert!(is_cactus_graph(&g).unwrap());
229    }
230
231    #[test]
232    fn triple_parallel_not_cactus() {
233        // Three parallel edges: 2 verts, 3 edges → not a cycle
234        let mut g = Graph::with_vertices(2);
235        g.add_edge(0, 1).unwrap();
236        g.add_edge(0, 1).unwrap();
237        g.add_edge(0, 1).unwrap();
238        assert!(!is_cactus_graph(&g).unwrap());
239    }
240}
rust_igraph/algorithms/properties/is_cactus.rs

rust_igraph/algorithms/properties/
is_cactus.rs
