rust_igraph/algorithms/properties/
is_cycle.rs

1//! Cycle graph predicate (ALGO-PR-089).
2//!
3//! A cycle graph `C_n` is a connected 2-regular graph on n ≥ 3 vertices.
4//! Every vertex has exactly degree 2, forming a single closed loop.
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 a cycle graph.
12///
13/// A cycle graph `C_n` has n ≥ 3 vertices, each with degree exactly 2,
14/// forming a single Hamiltonian cycle. The graph must be connected
15/// and simple.
16///
17/// Returns `false` for directed graphs, graphs with fewer than 3
18/// vertices, disconnected graphs, and graphs with any vertex not
19/// having degree 2.
20///
21/// # Examples
22///
23/// ```
24/// use rust_igraph::{Graph, is_cycle};
25///
26/// // C_4: 0-1-2-3-0
27/// let mut g = Graph::with_vertices(4);
28/// g.add_edge(0, 1).unwrap();
29/// g.add_edge(1, 2).unwrap();
30/// g.add_edge(2, 3).unwrap();
31/// g.add_edge(3, 0).unwrap();
32/// assert!(is_cycle(&g).unwrap());
33///
34/// // P_4 is NOT a cycle (endpoints have degree 1)
35/// let mut g = Graph::with_vertices(4);
36/// g.add_edge(0, 1).unwrap();
37/// g.add_edge(1, 2).unwrap();
38/// g.add_edge(2, 3).unwrap();
39/// assert!(!is_cycle(&g).unwrap());
40/// ```
41pub fn is_cycle(graph: &Graph) -> IgraphResult<bool> {
42    if graph.is_directed() {
43        return Ok(false);
44    }
45
46    let n = graph.vcount();
47    if n < 3 {
48        return Ok(false);
49    }
50
51    // A cycle on n vertices has exactly n edges.
52    if graph.ecount() != n as usize {
53        return Ok(false);
54    }
55
56    // Every vertex must have degree exactly 2.
57    for v in 0..n {
58        if graph.degree(v)? != 2 {
59            return Ok(false);
60        }
61    }
62
63    // Connected + n edges + all degree 2 → single cycle.
64    is_connected(graph, ConnectednessMode::Weak)
65}
66
67#[cfg(test)]
68mod tests {
69    use super::*;
70
71    #[test]
72    fn empty_graph() {
73        let g = Graph::with_vertices(0);
74        assert!(!is_cycle(&g).unwrap());
75    }
76
77    #[test]
78    fn single_vertex() {
79        let g = Graph::with_vertices(1);
80        assert!(!is_cycle(&g).unwrap());
81    }
82
83    #[test]
84    fn two_vertices_edge() {
85        let mut g = Graph::with_vertices(2);
86        g.add_edge(0, 1).unwrap();
87        assert!(!is_cycle(&g).unwrap());
88    }
89
90    #[test]
91    fn triangle() {
92        let mut g = Graph::with_vertices(3);
93        g.add_edge(0, 1).unwrap();
94        g.add_edge(1, 2).unwrap();
95        g.add_edge(2, 0).unwrap();
96        assert!(is_cycle(&g).unwrap());
97    }
98
99    #[test]
100    fn c4() {
101        let mut g = Graph::with_vertices(4);
102        g.add_edge(0, 1).unwrap();
103        g.add_edge(1, 2).unwrap();
104        g.add_edge(2, 3).unwrap();
105        g.add_edge(3, 0).unwrap();
106        assert!(is_cycle(&g).unwrap());
107    }
108
109    #[test]
110    fn c5() {
111        let mut g = Graph::with_vertices(5);
112        g.add_edge(0, 1).unwrap();
113        g.add_edge(1, 2).unwrap();
114        g.add_edge(2, 3).unwrap();
115        g.add_edge(3, 4).unwrap();
116        g.add_edge(4, 0).unwrap();
117        assert!(is_cycle(&g).unwrap());
118    }
119
120    #[test]
121    fn path_not_cycle() {
122        let mut g = Graph::with_vertices(4);
123        g.add_edge(0, 1).unwrap();
124        g.add_edge(1, 2).unwrap();
125        g.add_edge(2, 3).unwrap();
126        assert!(!is_cycle(&g).unwrap());
127    }
128
129    #[test]
130    fn star_not_cycle() {
131        let mut g = Graph::with_vertices(4);
132        g.add_edge(0, 1).unwrap();
133        g.add_edge(0, 2).unwrap();
134        g.add_edge(0, 3).unwrap();
135        assert!(!is_cycle(&g).unwrap());
136    }
137
138    #[test]
139    fn complete_k4_not_cycle() {
140        let mut g = Graph::with_vertices(4);
141        g.add_edge(0, 1).unwrap();
142        g.add_edge(0, 2).unwrap();
143        g.add_edge(0, 3).unwrap();
144        g.add_edge(1, 2).unwrap();
145        g.add_edge(1, 3).unwrap();
146        g.add_edge(2, 3).unwrap();
147        assert!(!is_cycle(&g).unwrap());
148    }
149
150    #[test]
151    fn two_disjoint_triangles_not_cycle() {
152        let mut g = Graph::with_vertices(6);
153        g.add_edge(0, 1).unwrap();
154        g.add_edge(1, 2).unwrap();
155        g.add_edge(2, 0).unwrap();
156        g.add_edge(3, 4).unwrap();
157        g.add_edge(4, 5).unwrap();
158        g.add_edge(5, 3).unwrap();
159        assert!(!is_cycle(&g).unwrap());
160    }
161
162    #[test]
163    fn directed_returns_false() {
164        let mut g = Graph::new(3, true).unwrap();
165        g.add_edge(0, 1).unwrap();
166        g.add_edge(1, 2).unwrap();
167        g.add_edge(2, 0).unwrap();
168        assert!(!is_cycle(&g).unwrap());
169    }
170
171    #[test]
172    fn wheel_not_cycle() {
173        let mut g = Graph::with_vertices(5);
174        g.add_edge(0, 1).unwrap();
175        g.add_edge(0, 2).unwrap();
176        g.add_edge(0, 3).unwrap();
177        g.add_edge(0, 4).unwrap();
178        g.add_edge(1, 2).unwrap();
179        g.add_edge(2, 3).unwrap();
180        g.add_edge(3, 4).unwrap();
181        g.add_edge(4, 1).unwrap();
182        assert!(!is_cycle(&g).unwrap());
183    }
184
185    #[test]
186    fn c6_non_sequential() {
187        // Cycle with non-sequential edge order
188        let mut g = Graph::with_vertices(6);
189        g.add_edge(0, 3).unwrap();
190        g.add_edge(3, 1).unwrap();
191        g.add_edge(1, 4).unwrap();
192        g.add_edge(4, 2).unwrap();
193        g.add_edge(2, 5).unwrap();
194        g.add_edge(5, 0).unwrap();
195        assert!(is_cycle(&g).unwrap());
196    }
197}
rust_igraph/algorithms/properties/is_cycle.rs

rust_igraph/algorithms/properties/
is_cycle.rs
