rust_igraph/algorithms/properties/
is_c4_free.rs

1//! `C_4`-free graph predicate (ALGO-PR-101).
2//!
3//! A graph is `C_4`-free if it contains no induced 4-cycle (also
4//! called a chordless 4-cycle or induced square).
5//!
6//! Note: this checks for *induced* `C_4`, not just any 4-cycle as a
7//! subgraph. A `K_4` contains 4-cycles as subgraphs but no
8//! *induced* `C_4` (every 4-cycle in `K_4` has a chord).
9//!
10//! For directed graphs, the function returns `false`.
11
12use crate::core::{Graph, IgraphResult};
13
14/// Check whether a graph is `C_4`-free (no induced 4-cycle).
15///
16/// An induced `C_4` is a set of 4 vertices {a, b, c, d} with edges
17/// {ab, bc, cd, da} and no diagonals (ac, bd both absent).
18///
19/// Returns `false` for directed graphs.
20///
21/// # Examples
22///
23/// ```
24/// use rust_igraph::{Graph, is_c4_free};
25///
26/// // Triangle is `C_4`-free
27/// let mut g = Graph::with_vertices(3);
28/// g.add_edge(0, 1).unwrap();
29/// g.add_edge(1, 2).unwrap();
30/// g.add_edge(2, 0).unwrap();
31/// assert!(is_c4_free(&g).unwrap());
32///
33/// // 4-cycle is NOT `C_4`-free
34/// let mut g = Graph::with_vertices(4);
35/// g.add_edge(0, 1).unwrap();
36/// g.add_edge(1, 2).unwrap();
37/// g.add_edge(2, 3).unwrap();
38/// g.add_edge(3, 0).unwrap();
39/// assert!(!is_c4_free(&g).unwrap());
40/// ```
41pub fn is_c4_free(graph: &Graph) -> IgraphResult<bool> {
42    if graph.is_directed() {
43        return Ok(false);
44    }
45
46    let n = graph.vcount();
47    if n < 4 {
48        return Ok(true);
49    }
50
51    let n_usize = n as usize;
52    let mut adj = vec![vec![false; n_usize]; n_usize];
53    let mut nbrs_list: Vec<Vec<u32>> = Vec::with_capacity(n_usize);
54
55    for v in 0..n {
56        let nbrs = graph.neighbors(v)?;
57        for &w in &nbrs {
58            adj[v as usize][w as usize] = true;
59        }
60        nbrs_list.push(nbrs);
61    }
62
63    // An induced C_4 is {a, b, c, d} with edges ab, bc, cd, da and
64    // NO edges ac or bd.
65    // Strategy: for each pair (a, b) that are adjacent, and each pair
66    // (c, d) where c is adjacent to b but not a, d is adjacent to a
67    // and c but not b → induced C_4: a-b-c-d-a.
68    for a in 0..n {
69        let ai = a as usize;
70        for &b in &nbrs_list[ai] {
71            if b <= a {
72                continue;
73            }
74            let bi = b as usize;
75            // Find c: adjacent to b, not adjacent to a, c > a (avoid double-counting)
76            for &c in &nbrs_list[bi] {
77                if c == a {
78                    continue;
79                }
80                let ci = c as usize;
81                if adj[ai][ci] {
82                    continue;
83                }
84                // Find d: adjacent to both c and a, not adjacent to b,
85                // d != b, d != c, d > b (avoid double-counting)
86                for &d in &nbrs_list[ci] {
87                    if d == b || d == c || d == a {
88                        continue;
89                    }
90                    let di = d as usize;
91                    if adj[ai][di] && !adj[bi][di] {
92                        return Ok(false);
93                    }
94                }
95            }
96        }
97    }
98
99    Ok(true)
100}
101
102#[cfg(test)]
103mod tests {
104    use super::*;
105
106    #[test]
107    fn empty_graph() {
108        let g = Graph::with_vertices(0);
109        assert!(is_c4_free(&g).unwrap());
110    }
111
112    #[test]
113    fn small_graphs() {
114        let g = Graph::with_vertices(3);
115        assert!(is_c4_free(&g).unwrap());
116    }
117
118    #[test]
119    fn triangle() {
120        let mut g = Graph::with_vertices(3);
121        g.add_edge(0, 1).unwrap();
122        g.add_edge(1, 2).unwrap();
123        g.add_edge(2, 0).unwrap();
124        assert!(is_c4_free(&g).unwrap());
125    }
126
127    #[test]
128    fn c4() {
129        let mut g = Graph::with_vertices(4);
130        g.add_edge(0, 1).unwrap();
131        g.add_edge(1, 2).unwrap();
132        g.add_edge(2, 3).unwrap();
133        g.add_edge(3, 0).unwrap();
134        assert!(!is_c4_free(&g).unwrap());
135    }
136
137    #[test]
138    fn k4_is_c4_free() {
139        // K_4 has 4-cycles as subgraphs but no INDUCED C_4 (all have chords)
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_c4_free(&g).unwrap());
148    }
149
150    #[test]
151    fn c5_not_c4_free() {
152        // C_5: 0-1-2-3-4-0. Vertices {0,1,2,4}: edges 0-1, 1-2, 4-0.
153        // Missing: 2-4 and 0-2 and 1-4. That's only 3 edges, not a C_4.
154        // Actually C_5 has no induced C_4 (any 4 vertices of C_5 induce
155        // at most a P_4, not a C_4).
156        let mut g = Graph::with_vertices(5);
157        g.add_edge(0, 1).unwrap();
158        g.add_edge(1, 2).unwrap();
159        g.add_edge(2, 3).unwrap();
160        g.add_edge(3, 4).unwrap();
161        g.add_edge(4, 0).unwrap();
162        assert!(is_c4_free(&g).unwrap());
163    }
164
165    #[test]
166    fn c6_not_c4_free() {
167        // C_6: 0-1-2-3-4-5-0. Vertices {0,1,3,4}: edges 0-1, 3-4.
168        // Missing 0-3, 0-4, 1-3, 1-4. Only 2 edges, not C_4.
169        // Actually, {0,1,2,3}: edges 0-1, 1-2, 2-3. Missing 0-3. P_4 not C_4.
170        // C_6 has no induced C_4 either.
171        let mut g = Graph::with_vertices(6);
172        g.add_edge(0, 1).unwrap();
173        g.add_edge(1, 2).unwrap();
174        g.add_edge(2, 3).unwrap();
175        g.add_edge(3, 4).unwrap();
176        g.add_edge(4, 5).unwrap();
177        g.add_edge(5, 0).unwrap();
178        assert!(is_c4_free(&g).unwrap());
179    }
180
181    #[test]
182    fn path_c4_free() {
183        let mut g = Graph::with_vertices(5);
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, 4).unwrap();
188        assert!(is_c4_free(&g).unwrap());
189    }
190
191    #[test]
192    fn star_c4_free() {
193        let mut g = Graph::with_vertices(5);
194        g.add_edge(0, 1).unwrap();
195        g.add_edge(0, 2).unwrap();
196        g.add_edge(0, 3).unwrap();
197        g.add_edge(0, 4).unwrap();
198        assert!(is_c4_free(&g).unwrap());
199    }
200
201    #[test]
202    fn cube_not_c4_free() {
203        // Cube graph Q_3: 8 vertices, bipartite, contains many C_4s
204        let mut g = Graph::with_vertices(8);
205        g.add_edge(0, 1).unwrap();
206        g.add_edge(0, 2).unwrap();
207        g.add_edge(0, 4).unwrap();
208        g.add_edge(1, 3).unwrap();
209        g.add_edge(1, 5).unwrap();
210        g.add_edge(2, 3).unwrap();
211        g.add_edge(2, 6).unwrap();
212        g.add_edge(3, 7).unwrap();
213        g.add_edge(4, 5).unwrap();
214        g.add_edge(4, 6).unwrap();
215        g.add_edge(5, 7).unwrap();
216        g.add_edge(6, 7).unwrap();
217        assert!(!is_c4_free(&g).unwrap());
218    }
219
220    #[test]
221    fn k33_not_c4_free() {
222        // K_{3,3}: complete bipartite, full of C_4s
223        let mut g = Graph::with_vertices(6);
224        for i in 0..3u32 {
225            for j in 3..6u32 {
226                g.add_edge(i, j).unwrap();
227            }
228        }
229        assert!(!is_c4_free(&g).unwrap());
230    }
231
232    #[test]
233    fn directed_returns_false() {
234        let mut g = Graph::new(3, true).unwrap();
235        g.add_edge(0, 1).unwrap();
236        g.add_edge(1, 2).unwrap();
237        g.add_edge(2, 0).unwrap();
238        assert!(!is_c4_free(&g).unwrap());
239    }
240
241    #[test]
242    fn diamond_c4_free() {
243        // Diamond: K_4 minus edge 2-3. No induced C_4.
244        let mut g = Graph::with_vertices(4);
245        g.add_edge(0, 1).unwrap();
246        g.add_edge(0, 2).unwrap();
247        g.add_edge(0, 3).unwrap();
248        g.add_edge(1, 2).unwrap();
249        g.add_edge(1, 3).unwrap();
250        assert!(is_c4_free(&g).unwrap());
251    }
252
253    #[test]
254    fn petersen_not_c4_free() {
255        // Petersen graph contains induced C_4? No — Petersen is
256        // triangle-free and has girth 5, so no C_3 or C_4.
257        // Actually girth 5 means shortest cycle is 5, so no C_4.
258        let mut g = Graph::with_vertices(10);
259        g.add_edge(0, 1).unwrap();
260        g.add_edge(1, 2).unwrap();
261        g.add_edge(2, 3).unwrap();
262        g.add_edge(3, 4).unwrap();
263        g.add_edge(4, 0).unwrap();
264        g.add_edge(5, 7).unwrap();
265        g.add_edge(7, 9).unwrap();
266        g.add_edge(9, 6).unwrap();
267        g.add_edge(6, 8).unwrap();
268        g.add_edge(8, 5).unwrap();
269        g.add_edge(0, 5).unwrap();
270        g.add_edge(1, 6).unwrap();
271        g.add_edge(2, 7).unwrap();
272        g.add_edge(3, 8).unwrap();
273        g.add_edge(4, 9).unwrap();
274        assert!(is_c4_free(&g).unwrap());
275    }
276}
rust_igraph/algorithms/properties/is_c4_free.rs

rust_igraph/algorithms/properties/
is_c4_free.rs
