rust_igraph/algorithms/properties/
is_c5_free.rs

1//! `C_5`-free graph predicate (ALGO-PR-102).
2//!
3//! A graph is `C_5`-free if it contains no induced 5-cycle (chordless
4//! pentagon).
5//!
6//! For directed graphs, the function returns `false`.
7
8use crate::core::{Graph, IgraphResult};
9
10/// Check whether a graph is `C_5`-free (no induced 5-cycle).
11///
12/// An induced `C_5` is a set of 5 vertices forming a cycle with
13/// exactly 5 edges and no chords (diagonals).
14///
15/// Returns `false` for directed graphs.
16///
17/// # Examples
18///
19/// ```
20/// use rust_igraph::{Graph, is_c5_free};
21///
22/// // Triangle is `C_5`-free
23/// let mut g = Graph::with_vertices(3);
24/// g.add_edge(0, 1).unwrap();
25/// g.add_edge(1, 2).unwrap();
26/// g.add_edge(2, 0).unwrap();
27/// assert!(is_c5_free(&g).unwrap());
28///
29/// // 5-cycle is NOT `C_5`-free
30/// let mut g = Graph::with_vertices(5);
31/// g.add_edge(0, 1).unwrap();
32/// g.add_edge(1, 2).unwrap();
33/// g.add_edge(2, 3).unwrap();
34/// g.add_edge(3, 4).unwrap();
35/// g.add_edge(4, 0).unwrap();
36/// assert!(!is_c5_free(&g).unwrap());
37/// ```
38pub fn is_c5_free(graph: &Graph) -> IgraphResult<bool> {
39    if graph.is_directed() {
40        return Ok(false);
41    }
42
43    let n = graph.vcount();
44    if n < 5 {
45        return Ok(true);
46    }
47
48    let n_usize = n as usize;
49    let mut adj = vec![vec![false; n_usize]; n_usize];
50    let mut nbrs_list: Vec<Vec<u32>> = Vec::with_capacity(n_usize);
51
52    for v in 0..n {
53        let nbrs = graph.neighbors(v)?;
54        for &w in &nbrs {
55            adj[v as usize][w as usize] = true;
56        }
57        nbrs_list.push(nbrs);
58    }
59
60    // Induced C_5: a-b-c-d-e-a with exactly these 5 edges and no
61    // chords (a-c, a-d, b-d, b-e, c-e all absent).
62    // Strategy: for each edge (a,b), find c adjacent to b but not a,
63    // then d adjacent to c but not a or b, then e adjacent to both d
64    // and a but not b or c.
65    for a in 0..n {
66        let ai = a as usize;
67        for &b in &nbrs_list[ai] {
68            if b <= a {
69                continue;
70            }
71            let bi = b as usize;
72            for &c in &nbrs_list[bi] {
73                if c == a {
74                    continue;
75                }
76                let ci = c as usize;
77                if adj[ai][ci] {
78                    continue;
79                }
80                for &d in &nbrs_list[ci] {
81                    if d == a || d == b {
82                        continue;
83                    }
84                    let di = d as usize;
85                    if adj[ai][di] || adj[bi][di] {
86                        continue;
87                    }
88                    for &e in &nbrs_list[di] {
89                        if e == a || e == b || e == c {
90                            continue;
91                        }
92                        let ei = e as usize;
93                        if adj[ai][ei] && !adj[bi][ei] && !adj[ci][ei] {
94                            return Ok(false);
95                        }
96                    }
97                }
98            }
99        }
100    }
101
102    Ok(true)
103}
104
105#[cfg(test)]
106mod tests {
107    use super::*;
108
109    #[test]
110    fn empty_graph() {
111        let g = Graph::with_vertices(0);
112        assert!(is_c5_free(&g).unwrap());
113    }
114
115    #[test]
116    fn small_graphs() {
117        let g = Graph::with_vertices(4);
118        assert!(is_c5_free(&g).unwrap());
119    }
120
121    #[test]
122    fn triangle() {
123        let mut g = Graph::with_vertices(3);
124        g.add_edge(0, 1).unwrap();
125        g.add_edge(1, 2).unwrap();
126        g.add_edge(2, 0).unwrap();
127        assert!(is_c5_free(&g).unwrap());
128    }
129
130    #[test]
131    fn c4_is_c5_free() {
132        let mut g = Graph::with_vertices(4);
133        g.add_edge(0, 1).unwrap();
134        g.add_edge(1, 2).unwrap();
135        g.add_edge(2, 3).unwrap();
136        g.add_edge(3, 0).unwrap();
137        assert!(is_c5_free(&g).unwrap());
138    }
139
140    #[test]
141    fn c5() {
142        let mut g = Graph::with_vertices(5);
143        g.add_edge(0, 1).unwrap();
144        g.add_edge(1, 2).unwrap();
145        g.add_edge(2, 3).unwrap();
146        g.add_edge(3, 4).unwrap();
147        g.add_edge(4, 0).unwrap();
148        assert!(!is_c5_free(&g).unwrap());
149    }
150
151    #[test]
152    fn k5_is_c5_free() {
153        // `K_5` has 5-cycles as subgraphs but no INDUCED `C_5` (all have chords)
154        let mut g = Graph::with_vertices(5);
155        for i in 0..5u32 {
156            for j in (i + 1)..5 {
157                g.add_edge(i, j).unwrap();
158            }
159        }
160        assert!(is_c5_free(&g).unwrap());
161    }
162
163    #[test]
164    fn c6_not_c5_free() {
165        // `C_6` has no induced `C_5` (any 5 vertices of `C_6` induce at most `P_5`)
166        let mut g = Graph::with_vertices(6);
167        g.add_edge(0, 1).unwrap();
168        g.add_edge(1, 2).unwrap();
169        g.add_edge(2, 3).unwrap();
170        g.add_edge(3, 4).unwrap();
171        g.add_edge(4, 5).unwrap();
172        g.add_edge(5, 0).unwrap();
173        assert!(is_c5_free(&g).unwrap());
174    }
175
176    #[test]
177    fn path_c5_free() {
178        let mut g = Graph::with_vertices(6);
179        g.add_edge(0, 1).unwrap();
180        g.add_edge(1, 2).unwrap();
181        g.add_edge(2, 3).unwrap();
182        g.add_edge(3, 4).unwrap();
183        g.add_edge(4, 5).unwrap();
184        assert!(is_c5_free(&g).unwrap());
185    }
186
187    #[test]
188    fn star_c5_free() {
189        let mut g = Graph::with_vertices(6);
190        g.add_edge(0, 1).unwrap();
191        g.add_edge(0, 2).unwrap();
192        g.add_edge(0, 3).unwrap();
193        g.add_edge(0, 4).unwrap();
194        g.add_edge(0, 5).unwrap();
195        assert!(is_c5_free(&g).unwrap());
196    }
197
198    #[test]
199    fn petersen_not_c5_free() {
200        // Petersen graph has girth 5, so it contains induced `C_5`
201        let mut g = Graph::with_vertices(10);
202        g.add_edge(0, 1).unwrap();
203        g.add_edge(1, 2).unwrap();
204        g.add_edge(2, 3).unwrap();
205        g.add_edge(3, 4).unwrap();
206        g.add_edge(4, 0).unwrap();
207        g.add_edge(5, 7).unwrap();
208        g.add_edge(7, 9).unwrap();
209        g.add_edge(9, 6).unwrap();
210        g.add_edge(6, 8).unwrap();
211        g.add_edge(8, 5).unwrap();
212        g.add_edge(0, 5).unwrap();
213        g.add_edge(1, 6).unwrap();
214        g.add_edge(2, 7).unwrap();
215        g.add_edge(3, 8).unwrap();
216        g.add_edge(4, 9).unwrap();
217        assert!(!is_c5_free(&g).unwrap());
218    }
219
220    #[test]
221    fn directed_returns_false() {
222        let mut g = Graph::new(3, true).unwrap();
223        g.add_edge(0, 1).unwrap();
224        g.add_edge(1, 2).unwrap();
225        g.add_edge(2, 0).unwrap();
226        assert!(!is_c5_free(&g).unwrap());
227    }
228
229    #[test]
230    fn cube_not_c5_free() {
231        // Cube `Q_3` (8 vertices, bipartite, girth 4) has no odd cycles
232        // so no induced `C_5`
233        let mut g = Graph::with_vertices(8);
234        g.add_edge(0, 1).unwrap();
235        g.add_edge(0, 2).unwrap();
236        g.add_edge(0, 4).unwrap();
237        g.add_edge(1, 3).unwrap();
238        g.add_edge(1, 5).unwrap();
239        g.add_edge(2, 3).unwrap();
240        g.add_edge(2, 6).unwrap();
241        g.add_edge(3, 7).unwrap();
242        g.add_edge(4, 5).unwrap();
243        g.add_edge(4, 6).unwrap();
244        g.add_edge(5, 7).unwrap();
245        g.add_edge(6, 7).unwrap();
246        assert!(is_c5_free(&g).unwrap());
247    }
248
249    #[test]
250    fn wheel5_c5_free() {
251        // Wheel W_5: hub 0 + cycle 1-2-3-4-5. The outer cycle is C_5
252        // but hub 0 is adjacent to all cycle vertices, adding chords.
253        // Any 5-vertex subset including the hub can't form C_5 (hub
254        // connects to everything). 5-vertex subset without hub is the
255        // outer C_5 itself → NOT `C_5`-free.
256        let mut g = Graph::with_vertices(6);
257        g.add_edge(0, 1).unwrap();
258        g.add_edge(0, 2).unwrap();
259        g.add_edge(0, 3).unwrap();
260        g.add_edge(0, 4).unwrap();
261        g.add_edge(0, 5).unwrap();
262        g.add_edge(1, 2).unwrap();
263        g.add_edge(2, 3).unwrap();
264        g.add_edge(3, 4).unwrap();
265        g.add_edge(4, 5).unwrap();
266        g.add_edge(5, 1).unwrap();
267        assert!(!is_c5_free(&g).unwrap());
268    }
269
270    #[test]
271    fn c5_plus_pendant_not_c5_free() {
272        // `C_5` with a pendant edge: still contains `C_5` on {0..4}
273        let mut g = Graph::with_vertices(6);
274        g.add_edge(0, 1).unwrap();
275        g.add_edge(1, 2).unwrap();
276        g.add_edge(2, 3).unwrap();
277        g.add_edge(3, 4).unwrap();
278        g.add_edge(4, 0).unwrap();
279        g.add_edge(0, 5).unwrap();
280        assert!(!is_c5_free(&g).unwrap());
281    }
282}
rust_igraph/algorithms/properties/is_c5_free.rs

rust_igraph/algorithms/properties/
is_c5_free.rs
