rust_igraph/algorithms/properties/
is_p5_free.rs

1//! `P_5`-free graph predicate (ALGO-PR-109).
2//!
3//! A graph is `P_5`-free if it contains no induced path on 5 vertices.
4//! `P_5`-free graphs generalize cographs (which are `P_4`-free) and
5//! appear in results on well-quasi-ordering and efficient algorithms.
6//!
7//! For directed graphs, the function returns `false`.
8
9use crate::core::{Graph, IgraphResult};
10
11/// Check whether a graph is `P_5`-free (no induced path on 5 vertices).
12///
13/// An induced `P_5` is 5 distinct vertices a-b-c-d-e forming a path
14/// with edges {a-b, b-c, c-d, d-e} and no other edges among them.
15///
16/// Returns `false` for directed graphs.
17///
18/// # Examples
19///
20/// ```
21/// use rust_igraph::{Graph, is_p5_free};
22///
23/// // `P_4` is `P_5`-free
24/// let mut g = Graph::with_vertices(4);
25/// g.add_edge(0, 1).unwrap();
26/// g.add_edge(1, 2).unwrap();
27/// g.add_edge(2, 3).unwrap();
28/// assert!(is_p5_free(&g).unwrap());
29///
30/// // `P_5` is NOT `P_5`-free
31/// let mut g = Graph::with_vertices(5);
32/// g.add_edge(0, 1).unwrap();
33/// g.add_edge(1, 2).unwrap();
34/// g.add_edge(2, 3).unwrap();
35/// g.add_edge(3, 4).unwrap();
36/// assert!(!is_p5_free(&g).unwrap());
37/// ```
38pub fn is_p5_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 P_5: a-b-c-d-e with edges a-b, b-c, c-d, d-e and
61    // no other edges among {a,b,c,d,e}:
62    //   a-c, a-d, a-e, b-d, b-e, c-e all absent.
63    //
64    // Strategy: for each edge (b,c), find a adjacent to b but not c,
65    // then d adjacent to c but not a or b, then e adjacent to d but
66    // not a, b, or c.
67    for b in 0..n {
68        let bi = b as usize;
69        for &c in &nbrs_list[bi] {
70            let ci = c as usize;
71            for &a in &nbrs_list[bi] {
72                if a == c {
73                    continue;
74                }
75                let ai = a as usize;
76                if adj[ai][ci] {
77                    continue;
78                }
79                // a-b edge, a not adj to c
80                for &d in &nbrs_list[ci] {
81                    if d == b {
82                        continue;
83                    }
84                    let di = d as usize;
85                    if adj[ai][di] || adj[bi][di] {
86                        continue;
87                    }
88                    // c-d edge, d not adj to a or b
89                    for &e in &nbrs_list[di] {
90                        if e == c || e == b || e == a {
91                            continue;
92                        }
93                        let ei = e as usize;
94                        if !adj[ai][ei] && !adj[bi][ei] && !adj[ci][ei] {
95                            return Ok(false);
96                        }
97                    }
98                }
99            }
100        }
101    }
102
103    Ok(true)
104}
105
106#[cfg(test)]
107mod tests {
108    use super::*;
109
110    #[test]
111    fn empty_graph() {
112        let g = Graph::with_vertices(0);
113        assert!(is_p5_free(&g).unwrap());
114    }
115
116    #[test]
117    fn small_graphs() {
118        let g = Graph::with_vertices(4);
119        assert!(is_p5_free(&g).unwrap());
120    }
121
122    #[test]
123    fn triangle() {
124        let mut g = Graph::with_vertices(3);
125        g.add_edge(0, 1).unwrap();
126        g.add_edge(1, 2).unwrap();
127        g.add_edge(2, 0).unwrap();
128        assert!(is_p5_free(&g).unwrap());
129    }
130
131    #[test]
132    fn p4_is_p5_free() {
133        let mut g = Graph::with_vertices(4);
134        g.add_edge(0, 1).unwrap();
135        g.add_edge(1, 2).unwrap();
136        g.add_edge(2, 3).unwrap();
137        assert!(is_p5_free(&g).unwrap());
138    }
139
140    #[test]
141    fn p5() {
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        assert!(!is_p5_free(&g).unwrap());
148    }
149
150    #[test]
151    fn c5_not_p5_free() {
152        // `C_5`: 0-1-2-3-4-0. The subpath 0-1-2-3-4 would be `P_5`
153        // if 0-4 were absent. But 0-4 IS present → induced subgraph
154        // on {0,1,2,3,4} has edge 0-4. Try {1,2,3,4,0}: edges 1-2,
155        // 2-3, 3-4, 4-0. Is 1-0 present? No (edge is 0-1, yes it is).
156        // So we have edges 1-2, 2-3, 3-4, 4-0, 0-1 → `C_5`, not `P_5`.
157        // Any 5-vertex subset of `C_5` is `C_5` itself. So `C_5` is `P_5`-free.
158        let mut g = Graph::with_vertices(5);
159        g.add_edge(0, 1).unwrap();
160        g.add_edge(1, 2).unwrap();
161        g.add_edge(2, 3).unwrap();
162        g.add_edge(3, 4).unwrap();
163        g.add_edge(4, 0).unwrap();
164        assert!(is_p5_free(&g).unwrap());
165    }
166
167    #[test]
168    fn c6_not_p5_free() {
169        // `C_6`: any 5 consecutive vertices form an induced `P_5`
170        // e.g., {0,1,2,3,4} has edges 0-1, 1-2, 2-3, 3-4 and no
171        // chord (0-4 absent in `C_6`).
172        let mut g = Graph::with_vertices(6);
173        g.add_edge(0, 1).unwrap();
174        g.add_edge(1, 2).unwrap();
175        g.add_edge(2, 3).unwrap();
176        g.add_edge(3, 4).unwrap();
177        g.add_edge(4, 5).unwrap();
178        g.add_edge(5, 0).unwrap();
179        assert!(!is_p5_free(&g).unwrap());
180    }
181
182    #[test]
183    fn k5_p5_free() {
184        // `K_5`: every pair is adjacent → no induced path of length > 1
185        let mut g = Graph::with_vertices(5);
186        for i in 0..5u32 {
187            for j in (i + 1)..5 {
188                g.add_edge(i, j).unwrap();
189            }
190        }
191        assert!(is_p5_free(&g).unwrap());
192    }
193
194    #[test]
195    fn star_p5_free() {
196        // Star: every path through the center has length 2. No `P_5`.
197        let mut g = Graph::with_vertices(6);
198        g.add_edge(0, 1).unwrap();
199        g.add_edge(0, 2).unwrap();
200        g.add_edge(0, 3).unwrap();
201        g.add_edge(0, 4).unwrap();
202        g.add_edge(0, 5).unwrap();
203        assert!(is_p5_free(&g).unwrap());
204    }
205
206    #[test]
207    fn directed_returns_false() {
208        let mut g = Graph::new(3, true).unwrap();
209        g.add_edge(0, 1).unwrap();
210        g.add_edge(1, 2).unwrap();
211        g.add_edge(2, 0).unwrap();
212        assert!(!is_p5_free(&g).unwrap());
213    }
214
215    #[test]
216    fn cograph_is_p5_free() {
217        // `K_2` union `K_3`: {0,1} complete, {2,3,4} complete, no edges between.
218        // Cographs are `P_4`-free, hence also `P_5`-free.
219        let mut g = Graph::with_vertices(5);
220        g.add_edge(0, 1).unwrap();
221        g.add_edge(2, 3).unwrap();
222        g.add_edge(3, 4).unwrap();
223        g.add_edge(2, 4).unwrap();
224        assert!(is_p5_free(&g).unwrap());
225    }
226
227    #[test]
228    fn bull_not_p5_free() {
229        // Bull: triangle {0,1,2} + pendants 1-3, 2-4.
230        // Path 3-1-0-2-4: edges 3-1, 1-0, 0-2, 2-4. Chords: 1-2 present!
231        // So {3,1,0,2,4} is not an induced `P_5` (has chord 1-2).
232        // Try another path: 3-1-2-0-? No pendant from 0. So bull is `P_5`-free.
233        let mut g = Graph::with_vertices(5);
234        g.add_edge(0, 1).unwrap();
235        g.add_edge(0, 2).unwrap();
236        g.add_edge(1, 2).unwrap();
237        g.add_edge(1, 3).unwrap();
238        g.add_edge(2, 4).unwrap();
239        assert!(is_p5_free(&g).unwrap());
240    }
241
242    #[test]
243    fn petersen_not_p5_free() {
244        // Petersen graph: diameter 2, every pair at distance ≤ 2.
245        // But it has induced `P_5` (e.g., any path through two
246        // non-adjacent vertices on the outer and inner pentagons).
247        let mut g = Graph::with_vertices(10);
248        g.add_edge(0, 1).unwrap();
249        g.add_edge(1, 2).unwrap();
250        g.add_edge(2, 3).unwrap();
251        g.add_edge(3, 4).unwrap();
252        g.add_edge(4, 0).unwrap();
253        g.add_edge(5, 7).unwrap();
254        g.add_edge(7, 9).unwrap();
255        g.add_edge(9, 6).unwrap();
256        g.add_edge(6, 8).unwrap();
257        g.add_edge(8, 5).unwrap();
258        g.add_edge(0, 5).unwrap();
259        g.add_edge(1, 6).unwrap();
260        g.add_edge(2, 7).unwrap();
261        g.add_edge(3, 8).unwrap();
262        g.add_edge(4, 9).unwrap();
263        assert!(!is_p5_free(&g).unwrap());
264    }
265
266    #[test]
267    fn two_disjoint_edges_p5_free() {
268        let mut g = Graph::with_vertices(4);
269        g.add_edge(0, 1).unwrap();
270        g.add_edge(2, 3).unwrap();
271        assert!(is_p5_free(&g).unwrap());
272    }
273}
rust_igraph/algorithms/properties/is_p5_free.rs

rust_igraph/algorithms/properties/
is_p5_free.rs
