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