rust_igraph/algorithms/properties/
is_cubic.rs

1//! Cubic (3-regular) graph predicate (ALGO-PR-123).
2//!
3//! A graph is cubic if every vertex has degree exactly 3. Cubic
4//! graphs are also called 3-regular or trivalent graphs.
5//!
6//! The Petersen graph, `K_{3,3}`, and the prism graph are cubic.
7//! `K_4` is cubic (each of 4 vertices has degree 3).
8//!
9//! Directed graphs: returns `false` (degree is ambiguous for
10//! directed graphs without specifying in/out/all).
11
12use crate::core::{Graph, IgraphResult};
13
14/// Check whether a graph is cubic (3-regular).
15///
16/// A graph is cubic if every vertex has degree exactly 3.
17/// Returns `false` for directed graphs, empty graphs, or graphs
18/// with fewer than 4 vertices (need at least 4 vertices for a
19/// cubic graph).
20///
21/// # Examples
22///
23/// ```
24/// use rust_igraph::{Graph, is_cubic};
25///
26/// // `K_4` is cubic: each vertex has degree 3
27/// let mut g = Graph::with_vertices(4);
28/// for i in 0..4u32 {
29///     for j in (i+1)..4 {
30///         g.add_edge(i, j).unwrap();
31///     }
32/// }
33/// assert!(is_cubic(&g).unwrap());
34///
35/// // `C_4` is 2-regular, not cubic
36/// let mut g = Graph::with_vertices(4);
37/// g.add_edge(0, 1).unwrap();
38/// g.add_edge(1, 2).unwrap();
39/// g.add_edge(2, 3).unwrap();
40/// g.add_edge(3, 0).unwrap();
41/// assert!(!is_cubic(&g).unwrap());
42/// ```
43pub fn is_cubic(graph: &Graph) -> IgraphResult<bool> {
44    if graph.is_directed() {
45        return Ok(false);
46    }
47
48    let n = graph.vcount();
49    if n < 4 {
50        return Ok(false);
51    }
52
53    for v in 0..n {
54        if graph.degree(v)? != 3 {
55            return Ok(false);
56        }
57    }
58
59    Ok(true)
60}
61
62#[cfg(test)]
63mod tests {
64    use super::*;
65
66    #[test]
67    fn empty_graph() {
68        let g = Graph::with_vertices(0);
69        assert!(!is_cubic(&g).unwrap());
70    }
71
72    #[test]
73    fn single_vertex() {
74        let g = Graph::with_vertices(1);
75        assert!(!is_cubic(&g).unwrap());
76    }
77
78    #[test]
79    fn two_vertices() {
80        let mut g = Graph::with_vertices(2);
81        g.add_edge(0, 1).unwrap();
82        assert!(!is_cubic(&g).unwrap());
83    }
84
85    #[test]
86    fn triangle() {
87        // 2-regular, not cubic
88        let mut g = Graph::with_vertices(3);
89        g.add_edge(0, 1).unwrap();
90        g.add_edge(1, 2).unwrap();
91        g.add_edge(2, 0).unwrap();
92        assert!(!is_cubic(&g).unwrap());
93    }
94
95    #[test]
96    fn k4_cubic() {
97        let mut g = Graph::with_vertices(4);
98        for i in 0..4u32 {
99            for j in (i + 1)..4 {
100                g.add_edge(i, j).unwrap();
101            }
102        }
103        assert!(is_cubic(&g).unwrap());
104    }
105
106    #[test]
107    fn c4_not_cubic() {
108        // 2-regular
109        let mut g = Graph::with_vertices(4);
110        g.add_edge(0, 1).unwrap();
111        g.add_edge(1, 2).unwrap();
112        g.add_edge(2, 3).unwrap();
113        g.add_edge(3, 0).unwrap();
114        assert!(!is_cubic(&g).unwrap());
115    }
116
117    #[test]
118    fn k33_cubic() {
119        // K_{3,3}: each vertex has degree 3
120        let mut g = Graph::with_vertices(6);
121        for i in 0..3u32 {
122            for j in 3..6u32 {
123                g.add_edge(i, j).unwrap();
124            }
125        }
126        assert!(is_cubic(&g).unwrap());
127    }
128
129    #[test]
130    fn petersen_graph() {
131        // Petersen graph: 10 vertices, each degree 3
132        let mut g = Graph::with_vertices(10);
133        // Outer cycle
134        for i in 0..5u32 {
135            g.add_edge(i, (i + 1) % 5).unwrap();
136        }
137        // Inner pentagram
138        for i in 0..5u32 {
139            g.add_edge(i + 5, ((i + 2) % 5) + 5).unwrap();
140        }
141        // Spokes
142        for i in 0..5u32 {
143            g.add_edge(i, i + 5).unwrap();
144        }
145        assert!(is_cubic(&g).unwrap());
146    }
147
148    #[test]
149    fn prism_graph() {
150        // Prism (triangular prism): 6 vertices, each degree 3
151        let mut g = Graph::with_vertices(6);
152        // Two triangles
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        // Connecting edges
160        g.add_edge(0, 3).unwrap();
161        g.add_edge(1, 4).unwrap();
162        g.add_edge(2, 5).unwrap();
163        assert!(is_cubic(&g).unwrap());
164    }
165
166    #[test]
167    fn star_not_cubic() {
168        let mut g = Graph::with_vertices(5);
169        g.add_edge(0, 1).unwrap();
170        g.add_edge(0, 2).unwrap();
171        g.add_edge(0, 3).unwrap();
172        g.add_edge(0, 4).unwrap();
173        assert!(!is_cubic(&g).unwrap());
174    }
175
176    #[test]
177    fn k5_not_cubic() {
178        // K_5: 4-regular, not cubic
179        let mut g = Graph::with_vertices(5);
180        for i in 0..5u32 {
181            for j in (i + 1)..5 {
182                g.add_edge(i, j).unwrap();
183            }
184        }
185        assert!(!is_cubic(&g).unwrap());
186    }
187
188    #[test]
189    fn edgeless() {
190        let g = Graph::with_vertices(5);
191        assert!(!is_cubic(&g).unwrap());
192    }
193
194    #[test]
195    fn directed_returns_false() {
196        let mut g = Graph::new(4, true).unwrap();
197        for i in 0..4u32 {
198            for j in 0..4 {
199                if i != j {
200                    g.add_edge(i, j).unwrap();
201                }
202            }
203        }
204        assert!(!is_cubic(&g).unwrap());
205    }
206}
rust_igraph/algorithms/properties/is_cubic.rs

rust_igraph/algorithms/properties/
is_cubic.rs
