rust_igraph/algorithms/properties/
is_regular.rs

1//! Regularity check (ALGO-PR-070).
2//!
3//! A graph is *k-regular* if every vertex has the same degree *k*.
4//! For directed graphs, a graph is regular if every vertex has the
5//! same out-degree AND the same in-degree (not necessarily equal to
6//! each other).
7
8use crate::algorithms::properties::degree::{DegreeMode, degree_sequence};
9use crate::core::{Graph, IgraphResult};
10
11/// Check whether a graph is regular.
12///
13/// A graph is regular if every vertex has the same degree. For
14/// directed graphs, this checks that all out-degrees are equal AND
15/// all in-degrees are equal.
16///
17/// An empty graph (0 vertices) is considered regular.
18/// A graph with one vertex is regular (degree may be nonzero due to
19/// self-loops).
20///
21/// # Examples
22///
23/// ```
24/// use rust_igraph::{Graph, is_regular};
25///
26/// // Cycle C4 is 2-regular
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_regular(&g).unwrap());
33///
34/// // Path P3 is not regular (endpoints have degree 1, middle has 2)
35/// let mut g = Graph::with_vertices(3);
36/// g.add_edge(0, 1).unwrap();
37/// g.add_edge(1, 2).unwrap();
38/// assert!(!is_regular(&g).unwrap());
39/// ```
40pub fn is_regular(graph: &Graph) -> IgraphResult<bool> {
41    let n = graph.vcount();
42    if n <= 1 {
43        return Ok(true);
44    }
45
46    let out_deg = degree_sequence(graph, DegreeMode::Out)?;
47    if out_deg.windows(2).any(|w| w[0] != w[1]) {
48        return Ok(false);
49    }
50
51    if graph.is_directed() {
52        let in_deg = degree_sequence(graph, DegreeMode::In)?;
53        if in_deg.windows(2).any(|w| w[0] != w[1]) {
54            return Ok(false);
55        }
56    }
57
58    Ok(true)
59}
60
61/// Return the regularity degree of the graph, or `None` if the graph
62/// is not regular.
63///
64/// For undirected graphs, returns the common degree. For directed
65/// graphs, returns the common out-degree (which equals the common
66/// in-degree in a regular directed graph where out-degree == in-degree
67/// for all vertices; if out-degrees are all equal and in-degrees are
68/// all equal but differ from each other, returns `None` since such a
69/// graph is not considered regular in the standard sense for simple
70/// regularity queries).
71///
72/// An empty graph returns `None` (no vertices, no degree).
73///
74/// # Examples
75///
76/// ```
77/// use rust_igraph::{Graph, regularity};
78///
79/// // K3 is 2-regular
80/// let mut g = Graph::with_vertices(3);
81/// g.add_edge(0, 1).unwrap();
82/// g.add_edge(1, 2).unwrap();
83/// g.add_edge(2, 0).unwrap();
84/// assert_eq!(regularity(&g).unwrap(), Some(2));
85///
86/// // Star graph is not regular
87/// let mut g = Graph::with_vertices(4);
88/// g.add_edge(0, 1).unwrap();
89/// g.add_edge(0, 2).unwrap();
90/// g.add_edge(0, 3).unwrap();
91/// assert_eq!(regularity(&g).unwrap(), None);
92/// ```
93pub fn regularity(graph: &Graph) -> IgraphResult<Option<u32>> {
94    let n = graph.vcount();
95    if n == 0 {
96        return Ok(None);
97    }
98
99    let out_deg = degree_sequence(graph, DegreeMode::Out)?;
100    if out_deg.windows(2).any(|w| w[0] != w[1]) {
101        return Ok(None);
102    }
103
104    if graph.is_directed() {
105        let in_deg = degree_sequence(graph, DegreeMode::In)?;
106        if in_deg.windows(2).any(|w| w[0] != w[1]) {
107            return Ok(None);
108        }
109        if out_deg[0] != in_deg[0] {
110            return Ok(None);
111        }
112    }
113
114    Ok(Some(out_deg[0]))
115}
116
117#[cfg(test)]
118mod tests {
119    use super::*;
120
121    #[test]
122    fn empty_graph_is_regular() {
123        let g = Graph::with_vertices(0);
124        assert!(is_regular(&g).unwrap());
125    }
126
127    #[test]
128    fn empty_graph_regularity_none() {
129        let g = Graph::with_vertices(0);
130        assert_eq!(regularity(&g).unwrap(), None);
131    }
132
133    #[test]
134    fn single_vertex_no_edges() {
135        let g = Graph::with_vertices(1);
136        assert!(is_regular(&g).unwrap());
137        assert_eq!(regularity(&g).unwrap(), Some(0));
138    }
139
140    #[test]
141    fn single_vertex_self_loop() {
142        let mut g = Graph::with_vertices(1);
143        g.add_edge(0, 0).unwrap();
144        assert!(is_regular(&g).unwrap());
145    }
146
147    #[test]
148    fn two_vertices_no_edges() {
149        let g = Graph::with_vertices(2);
150        assert!(is_regular(&g).unwrap());
151        assert_eq!(regularity(&g).unwrap(), Some(0));
152    }
153
154    #[test]
155    fn single_edge() {
156        let mut g = Graph::with_vertices(2);
157        g.add_edge(0, 1).unwrap();
158        assert!(is_regular(&g).unwrap());
159        assert_eq!(regularity(&g).unwrap(), Some(1));
160    }
161
162    #[test]
163    fn path_3_not_regular() {
164        let mut g = Graph::with_vertices(3);
165        g.add_edge(0, 1).unwrap();
166        g.add_edge(1, 2).unwrap();
167        assert!(!is_regular(&g).unwrap());
168        assert_eq!(regularity(&g).unwrap(), None);
169    }
170
171    #[test]
172    fn triangle_is_2_regular() {
173        let mut g = Graph::with_vertices(3);
174        g.add_edge(0, 1).unwrap();
175        g.add_edge(1, 2).unwrap();
176        g.add_edge(2, 0).unwrap();
177        assert!(is_regular(&g).unwrap());
178        assert_eq!(regularity(&g).unwrap(), Some(2));
179    }
180
181    #[test]
182    fn cycle_4_is_2_regular() {
183        let mut g = Graph::with_vertices(4);
184        g.add_edge(0, 1).unwrap();
185        g.add_edge(1, 2).unwrap();
186        g.add_edge(2, 3).unwrap();
187        g.add_edge(3, 0).unwrap();
188        assert!(is_regular(&g).unwrap());
189        assert_eq!(regularity(&g).unwrap(), Some(2));
190    }
191
192    #[test]
193    fn complete_k4_is_3_regular() {
194        let mut g = Graph::with_vertices(4);
195        for u in 0..4u32 {
196            for v in (u + 1)..4 {
197                g.add_edge(u, v).unwrap();
198            }
199        }
200        assert!(is_regular(&g).unwrap());
201        assert_eq!(regularity(&g).unwrap(), Some(3));
202    }
203
204    #[test]
205    fn star_not_regular() {
206        let mut g = Graph::with_vertices(5);
207        for i in 1..5u32 {
208            g.add_edge(0, i).unwrap();
209        }
210        assert!(!is_regular(&g).unwrap());
211        assert_eq!(regularity(&g).unwrap(), None);
212    }
213
214    #[test]
215    fn petersen_is_3_regular() {
216        let mut g = Graph::with_vertices(10);
217        let edges = [
218            (0, 1),
219            (1, 2),
220            (2, 3),
221            (3, 4),
222            (4, 0),
223            (5, 7),
224            (7, 9),
225            (9, 6),
226            (6, 8),
227            (8, 5),
228            (0, 5),
229            (1, 6),
230            (2, 7),
231            (3, 8),
232            (4, 9),
233        ];
234        for (u, v) in edges {
235            g.add_edge(u, v).unwrap();
236        }
237        assert!(is_regular(&g).unwrap());
238        assert_eq!(regularity(&g).unwrap(), Some(3));
239    }
240
241    #[test]
242    fn directed_cycle_is_regular() {
243        let mut g = Graph::new(3, true).unwrap();
244        g.add_edge(0, 1).unwrap();
245        g.add_edge(1, 2).unwrap();
246        g.add_edge(2, 0).unwrap();
247        assert!(is_regular(&g).unwrap());
248        assert_eq!(regularity(&g).unwrap(), Some(1));
249    }
250
251    #[test]
252    fn directed_unequal_in_out_not_regular() {
253        let mut g = Graph::new(3, true).unwrap();
254        g.add_edge(0, 1).unwrap();
255        g.add_edge(0, 2).unwrap();
256        g.add_edge(1, 2).unwrap();
257        assert!(!is_regular(&g).unwrap());
258        assert_eq!(regularity(&g).unwrap(), None);
259    }
260
261    #[test]
262    fn parallel_edges_regular() {
263        let mut g = Graph::with_vertices(2);
264        g.add_edge(0, 1).unwrap();
265        g.add_edge(0, 1).unwrap();
266        assert!(is_regular(&g).unwrap());
267        assert_eq!(regularity(&g).unwrap(), Some(2));
268    }
269
270    #[test]
271    fn bipartite_k22_is_2_regular() {
272        let mut g = Graph::with_vertices(4);
273        g.add_edge(0, 2).unwrap();
274        g.add_edge(0, 3).unwrap();
275        g.add_edge(1, 2).unwrap();
276        g.add_edge(1, 3).unwrap();
277        assert!(is_regular(&g).unwrap());
278        assert_eq!(regularity(&g).unwrap(), Some(2));
279    }
280}
rust_igraph/algorithms/properties/is_regular.rs

rust_igraph/algorithms/properties/
is_regular.rs
