rust_igraph/algorithms/properties/
is_unicyclic.rs

1//! Unicyclic graph predicate (ALGO-PR-093).
2//!
3//! A unicyclic graph is a connected graph containing exactly one
4//! cycle. Equivalently, a connected graph with n vertices and n edges.
5//!
6//! For directed graphs, the function returns `false`.
7
8use crate::algorithms::connectivity::{ConnectednessMode, is_connected};
9use crate::core::{Graph, IgraphResult};
10
11/// Check whether a graph is unicyclic.
12///
13/// A unicyclic graph is connected and has exactly as many edges as
14/// vertices (n vertices, n edges), which means it contains exactly
15/// one cycle.
16///
17/// Returns `false` for directed graphs, disconnected graphs, trees
18/// (n-1 edges), and graphs with more than one cycle.
19///
20/// # Examples
21///
22/// ```
23/// use rust_igraph::{Graph, is_unicyclic};
24///
25/// // Triangle with a tail: 0-1-2-0, 2-3
26/// let mut g = Graph::with_vertices(4);
27/// g.add_edge(0, 1).unwrap();
28/// g.add_edge(1, 2).unwrap();
29/// g.add_edge(2, 0).unwrap();
30/// g.add_edge(2, 3).unwrap();
31/// assert!(is_unicyclic(&g).unwrap());
32///
33/// // Path is NOT unicyclic (no cycle)
34/// let mut g = Graph::with_vertices(3);
35/// g.add_edge(0, 1).unwrap();
36/// g.add_edge(1, 2).unwrap();
37/// assert!(!is_unicyclic(&g).unwrap());
38/// ```
39pub fn is_unicyclic(graph: &Graph) -> IgraphResult<bool> {
40    if graph.is_directed() {
41        return Ok(false);
42    }
43
44    let n = graph.vcount();
45    if n == 0 {
46        return Ok(false);
47    }
48
49    // A connected graph with n edges has exactly one cycle.
50    if graph.ecount() != n as usize {
51        return Ok(false);
52    }
53
54    is_connected(graph, ConnectednessMode::Weak)
55}
56
57#[cfg(test)]
58mod tests {
59    use super::*;
60
61    #[test]
62    fn empty_graph() {
63        let g = Graph::with_vertices(0);
64        assert!(!is_unicyclic(&g).unwrap());
65    }
66
67    #[test]
68    fn single_vertex() {
69        let g = Graph::with_vertices(1);
70        assert!(!is_unicyclic(&g).unwrap());
71    }
72
73    #[test]
74    fn single_edge() {
75        let mut g = Graph::with_vertices(2);
76        g.add_edge(0, 1).unwrap();
77        assert!(!is_unicyclic(&g).unwrap());
78    }
79
80    #[test]
81    fn triangle() {
82        let mut g = Graph::with_vertices(3);
83        g.add_edge(0, 1).unwrap();
84        g.add_edge(1, 2).unwrap();
85        g.add_edge(2, 0).unwrap();
86        assert!(is_unicyclic(&g).unwrap());
87    }
88
89    #[test]
90    fn c5() {
91        let mut g = Graph::with_vertices(5);
92        g.add_edge(0, 1).unwrap();
93        g.add_edge(1, 2).unwrap();
94        g.add_edge(2, 3).unwrap();
95        g.add_edge(3, 4).unwrap();
96        g.add_edge(4, 0).unwrap();
97        assert!(is_unicyclic(&g).unwrap());
98    }
99
100    #[test]
101    fn triangle_with_tail() {
102        // 0-1-2-0, 2-3
103        let mut g = Graph::with_vertices(4);
104        g.add_edge(0, 1).unwrap();
105        g.add_edge(1, 2).unwrap();
106        g.add_edge(2, 0).unwrap();
107        g.add_edge(2, 3).unwrap();
108        assert!(is_unicyclic(&g).unwrap());
109    }
110
111    #[test]
112    fn path_not_unicyclic() {
113        let mut g = Graph::with_vertices(4);
114        g.add_edge(0, 1).unwrap();
115        g.add_edge(1, 2).unwrap();
116        g.add_edge(2, 3).unwrap();
117        assert!(!is_unicyclic(&g).unwrap());
118    }
119
120    #[test]
121    fn k4_not_unicyclic() {
122        // K4 has 6 edges, 4 vertices — multiple cycles
123        let mut g = Graph::with_vertices(4);
124        g.add_edge(0, 1).unwrap();
125        g.add_edge(0, 2).unwrap();
126        g.add_edge(0, 3).unwrap();
127        g.add_edge(1, 2).unwrap();
128        g.add_edge(1, 3).unwrap();
129        g.add_edge(2, 3).unwrap();
130        assert!(!is_unicyclic(&g).unwrap());
131    }
132
133    #[test]
134    fn two_triangles_disconnected() {
135        // Two triangles, each unicyclic, but disconnected
136        let mut g = Graph::with_vertices(6);
137        g.add_edge(0, 1).unwrap();
138        g.add_edge(1, 2).unwrap();
139        g.add_edge(2, 0).unwrap();
140        g.add_edge(3, 4).unwrap();
141        g.add_edge(4, 5).unwrap();
142        g.add_edge(5, 3).unwrap();
143        assert!(!is_unicyclic(&g).unwrap());
144    }
145
146    #[test]
147    fn theta_graph_not_unicyclic() {
148        // Theta: two paths between same endpoints → 2 cycles
149        // 0-1-2-3, 0-4-3: 5 vertices, 5 edges, connected
150        // Wait: 5 vertices, 5 edges, connected → exactly 1 cycle!
151        // Actually no: 0-1-2-3, 0-4-3, 0-3 would be theta.
152        // Let me make a proper graph with 2 cycles:
153        // Triangle 0-1-2 + triangle 0-2-3: 4 vertices, 5 edges
154        let mut g = Graph::with_vertices(4);
155        g.add_edge(0, 1).unwrap();
156        g.add_edge(1, 2).unwrap();
157        g.add_edge(2, 0).unwrap();
158        g.add_edge(0, 3).unwrap();
159        g.add_edge(3, 2).unwrap();
160        // 4 vertices, 5 edges → not unicyclic
161        assert!(!is_unicyclic(&g).unwrap());
162    }
163
164    #[test]
165    fn directed_returns_false() {
166        let mut g = Graph::new(3, true).unwrap();
167        g.add_edge(0, 1).unwrap();
168        g.add_edge(1, 2).unwrap();
169        g.add_edge(2, 0).unwrap();
170        assert!(!is_unicyclic(&g).unwrap());
171    }
172
173    #[test]
174    fn star_not_unicyclic() {
175        let mut g = Graph::with_vertices(4);
176        g.add_edge(0, 1).unwrap();
177        g.add_edge(0, 2).unwrap();
178        g.add_edge(0, 3).unwrap();
179        assert!(!is_unicyclic(&g).unwrap());
180    }
181
182    #[test]
183    fn lollipop() {
184        // Triangle 0-1-2-0 with a path tail 2-3-4
185        let mut g = Graph::with_vertices(5);
186        g.add_edge(0, 1).unwrap();
187        g.add_edge(1, 2).unwrap();
188        g.add_edge(2, 0).unwrap();
189        g.add_edge(2, 3).unwrap();
190        g.add_edge(3, 4).unwrap();
191        assert!(is_unicyclic(&g).unwrap());
192    }
193}
rust_igraph/algorithms/properties/is_unicyclic.rs

rust_igraph/algorithms/properties/
is_unicyclic.rs
