rust_igraph/algorithms/properties/
is_house_free.rs

1//! House-free graph predicate (ALGO-PR-105).
2//!
3//! A graph is house-free if it contains no induced house graph. The
4//! house is a `C_5` with one chord: 5 vertices {a, b, c, d, e} with
5//! edges {a-b, b-c, c-d, d-e, e-a, a-c} (the chord a-c turns the
6//! pentagon into a triangle {a, b, c} topped by a path d-e).
7//! Equivalently: a triangle with a `P_3` extension completing a 5-cycle
8//! through one of its edges. 6 edges total.
9//!
10//! For directed graphs, the function returns `false`.
11
12use crate::core::{Graph, IgraphResult};
13
14/// Check whether a graph is house-free (no induced house graph).
15///
16/// The house is `C_5` plus one chord: a triangle {a, b, c} and two
17/// extra vertices d, e where c-d, d-e, e-a are edges and a-d, b-d,
18/// b-e, c-e are all absent.
19///
20/// Returns `false` for directed graphs.
21///
22/// # Examples
23///
24/// ```
25/// use rust_igraph::{Graph, is_house_free};
26///
27/// // Triangle is house-free
28/// let mut g = Graph::with_vertices(3);
29/// g.add_edge(0, 1).unwrap();
30/// g.add_edge(1, 2).unwrap();
31/// g.add_edge(2, 0).unwrap();
32/// assert!(is_house_free(&g).unwrap());
33///
34/// // House: triangle {0,1,2}, path 2-3-4-0
35/// let mut g = Graph::with_vertices(5);
36/// g.add_edge(0, 1).unwrap();
37/// g.add_edge(1, 2).unwrap();
38/// g.add_edge(2, 0).unwrap();
39/// g.add_edge(2, 3).unwrap();
40/// g.add_edge(3, 4).unwrap();
41/// g.add_edge(4, 0).unwrap();
42/// assert!(!is_house_free(&g).unwrap());
43/// ```
44pub fn is_house_free(graph: &Graph) -> IgraphResult<bool> {
45    if graph.is_directed() {
46        return Ok(false);
47    }
48
49    let n = graph.vcount();
50    if n < 5 {
51        return Ok(true);
52    }
53
54    let n_usize = n as usize;
55    let mut adj = vec![vec![false; n_usize]; n_usize];
56    let mut nbrs_list: Vec<Vec<u32>> = Vec::with_capacity(n_usize);
57
58    for v in 0..n {
59        let nbrs = graph.neighbors(v)?;
60        for &w in &nbrs {
61            adj[v as usize][w as usize] = true;
62        }
63        nbrs_list.push(nbrs);
64    }
65
66    // House: triangle {a, b, c} with chord a-c on the "base". The "roof"
67    // vertices d, e satisfy: c-d, d-e, e-a edges; a-d, b-d, b-e, c-e absent.
68    //
69    // For each triangle {a, b, c}, try each edge as the base (the edge
70    // that gets the chord). The remaining vertex is the "top" of the triangle.
71    // Then find d adjacent to c (but not a, b) and e adjacent to both d and a
72    // (but not b, c). Also d-e must be non-adjacent to b and c/a respectively.
73    for a in 0..n {
74        let ai = a as usize;
75        for b in (a + 1)..n {
76            let bi = b as usize;
77            if !adj[ai][bi] {
78                continue;
79            }
80            for c in (b + 1)..n {
81                let ci = c as usize;
82                if !adj[ai][ci] || !adj[bi][ci] {
83                    continue;
84                }
85
86                // Triangle {a, b, c}. The chord is one of the 3 edges.
87                // We try all 3 orientations of the house.
88                // House with chord a-b (top=c): find d adj to c not a,b;
89                //   e adj to d and a, not b,c
90                if check_house_roof(&adj, &nbrs_list, ai, bi, ci) {
91                    return Ok(false);
92                }
93                // chord a-b (top=c), but roof goes c-d-e-b:
94                if check_house_roof(&adj, &nbrs_list, bi, ai, ci) {
95                    return Ok(false);
96                }
97                // chord a-c (top=b): roof b-d-e-a → no, roof b-d-e-c
98                if check_house_roof(&adj, &nbrs_list, ai, ci, bi) {
99                    return Ok(false);
100                }
101                if check_house_roof(&adj, &nbrs_list, ci, ai, bi) {
102                    return Ok(false);
103                }
104                // chord b-c (top=a): roof a-d-e-b, a-d-e-c
105                if check_house_roof(&adj, &nbrs_list, bi, ci, ai) {
106                    return Ok(false);
107                }
108                if check_house_roof(&adj, &nbrs_list, ci, bi, ai) {
109                    return Ok(false);
110                }
111            }
112        }
113    }
114
115    Ok(true)
116}
117
118/// Check for a house with triangle base edge (base1, base2) and top vertex.
119/// Look for d adjacent to top (not base1, base2) and e adjacent to d and base1
120/// (not base2, top). Also d must not be adjacent to base1, e must not be
121/// adjacent to top.
122fn check_house_roof(
123    adj: &[Vec<bool>],
124    nbrs_list: &[Vec<u32>],
125    base1: usize,
126    base2: usize,
127    top: usize,
128) -> bool {
129    // d: adjacent to top, not adjacent to base1 or base2
130    for &d_u32 in &nbrs_list[top] {
131        let d = d_u32 as usize;
132        if d == base1 || d == base2 {
133            continue;
134        }
135        if adj[base1][d] || adj[base2][d] {
136            continue;
137        }
138        // e: adjacent to d and base1, not adjacent to base2 or top
139        for &e_u32 in &nbrs_list[d] {
140            let e = e_u32 as usize;
141            if e == top || e == base1 || e == base2 || e == d {
142                continue;
143            }
144            if adj[base1][e] && !adj[base2][e] && !adj[top][e] {
145                return true;
146            }
147        }
148    }
149    false
150}
151
152#[cfg(test)]
153mod tests {
154    use super::*;
155
156    #[test]
157    fn empty_graph() {
158        let g = Graph::with_vertices(0);
159        assert!(is_house_free(&g).unwrap());
160    }
161
162    #[test]
163    fn small_graphs() {
164        let g = Graph::with_vertices(4);
165        assert!(is_house_free(&g).unwrap());
166    }
167
168    #[test]
169    fn triangle() {
170        let mut g = Graph::with_vertices(3);
171        g.add_edge(0, 1).unwrap();
172        g.add_edge(1, 2).unwrap();
173        g.add_edge(2, 0).unwrap();
174        assert!(is_house_free(&g).unwrap());
175    }
176
177    #[test]
178    fn house() {
179        // Triangle {0,1,2}, path 2-3-4-0
180        let mut g = Graph::with_vertices(5);
181        g.add_edge(0, 1).unwrap();
182        g.add_edge(1, 2).unwrap();
183        g.add_edge(2, 0).unwrap();
184        g.add_edge(2, 3).unwrap();
185        g.add_edge(3, 4).unwrap();
186        g.add_edge(4, 0).unwrap();
187        assert!(!is_house_free(&g).unwrap());
188    }
189
190    #[test]
191    fn c5_not_house() {
192        // `C_5` has no chord → not a house
193        let mut g = Graph::with_vertices(5);
194        g.add_edge(0, 1).unwrap();
195        g.add_edge(1, 2).unwrap();
196        g.add_edge(2, 3).unwrap();
197        g.add_edge(3, 4).unwrap();
198        g.add_edge(4, 0).unwrap();
199        assert!(is_house_free(&g).unwrap());
200    }
201
202    #[test]
203    fn k5_house_free() {
204        // `K_5`: every 5-vertex subgraph is `K_5` with 10 edges, not 6
205        let mut g = Graph::with_vertices(5);
206        for i in 0..5u32 {
207            for j in (i + 1)..5 {
208                g.add_edge(i, j).unwrap();
209            }
210        }
211        assert!(is_house_free(&g).unwrap());
212    }
213
214    #[test]
215    fn c4_house_free() {
216        let mut g = Graph::with_vertices(4);
217        g.add_edge(0, 1).unwrap();
218        g.add_edge(1, 2).unwrap();
219        g.add_edge(2, 3).unwrap();
220        g.add_edge(3, 0).unwrap();
221        assert!(is_house_free(&g).unwrap());
222    }
223
224    #[test]
225    fn diamond_house_free() {
226        let mut g = Graph::with_vertices(4);
227        g.add_edge(0, 1).unwrap();
228        g.add_edge(0, 2).unwrap();
229        g.add_edge(0, 3).unwrap();
230        g.add_edge(1, 2).unwrap();
231        g.add_edge(1, 3).unwrap();
232        assert!(is_house_free(&g).unwrap());
233    }
234
235    #[test]
236    fn path_house_free() {
237        let mut g = Graph::with_vertices(5);
238        g.add_edge(0, 1).unwrap();
239        g.add_edge(1, 2).unwrap();
240        g.add_edge(2, 3).unwrap();
241        g.add_edge(3, 4).unwrap();
242        assert!(is_house_free(&g).unwrap());
243    }
244
245    #[test]
246    fn star_house_free() {
247        let mut g = Graph::with_vertices(6);
248        g.add_edge(0, 1).unwrap();
249        g.add_edge(0, 2).unwrap();
250        g.add_edge(0, 3).unwrap();
251        g.add_edge(0, 4).unwrap();
252        g.add_edge(0, 5).unwrap();
253        assert!(is_house_free(&g).unwrap());
254    }
255
256    #[test]
257    fn directed_returns_false() {
258        let mut g = Graph::new(3, true).unwrap();
259        g.add_edge(0, 1).unwrap();
260        g.add_edge(1, 2).unwrap();
261        g.add_edge(2, 0).unwrap();
262        assert!(!is_house_free(&g).unwrap());
263    }
264
265    #[test]
266    fn house_with_extra_chord_not_house() {
267        // House + extra chord → not an induced house
268        // Triangle {0,1,2}, path 2-3-4-0, plus chord 1-3
269        let mut g = Graph::with_vertices(5);
270        g.add_edge(0, 1).unwrap();
271        g.add_edge(1, 2).unwrap();
272        g.add_edge(2, 0).unwrap();
273        g.add_edge(2, 3).unwrap();
274        g.add_edge(3, 4).unwrap();
275        g.add_edge(4, 0).unwrap();
276        g.add_edge(1, 3).unwrap();
277        assert!(is_house_free(&g).unwrap());
278    }
279
280    #[test]
281    fn gem_not_house() {
282        // Gem: `P_4` + universal vertex. Not a house.
283        // Vertices 1-2-3-4 form P_4, vertex 0 adjacent to all.
284        let mut g = Graph::with_vertices(5);
285        g.add_edge(0, 1).unwrap();
286        g.add_edge(0, 2).unwrap();
287        g.add_edge(0, 3).unwrap();
288        g.add_edge(0, 4).unwrap();
289        g.add_edge(1, 2).unwrap();
290        g.add_edge(2, 3).unwrap();
291        g.add_edge(3, 4).unwrap();
292        // Check: triangle {0,1,2}, roof vertex 3 adj to 2 not 0,1 → 3 is d.
293        // e adj to 3 and 1? e=4: adj to 3 yes, adj to 1? No (no edge 1-4).
294        // Actually 0 is adj to 4, so e=4 is adj to top=0, so it fails the
295        // "not adjacent to top" check.
296        // No house found because 0 is adjacent to everything.
297        assert!(is_house_free(&g).unwrap());
298    }
299
300    #[test]
301    fn petersen_not_house_free() {
302        // Petersen graph: girth 5, 3-regular. Check if it has an induced house.
303        // House = C_5 + chord. Petersen has many C_5 (girth=5). Any C_5
304        // plus a chord from outside? Petersen is triangle-free, so adding
305        // a chord to C_5 would create a triangle → no house in Petersen.
306        let mut g = Graph::with_vertices(10);
307        g.add_edge(0, 1).unwrap();
308        g.add_edge(1, 2).unwrap();
309        g.add_edge(2, 3).unwrap();
310        g.add_edge(3, 4).unwrap();
311        g.add_edge(4, 0).unwrap();
312        g.add_edge(5, 7).unwrap();
313        g.add_edge(7, 9).unwrap();
314        g.add_edge(9, 6).unwrap();
315        g.add_edge(6, 8).unwrap();
316        g.add_edge(8, 5).unwrap();
317        g.add_edge(0, 5).unwrap();
318        g.add_edge(1, 6).unwrap();
319        g.add_edge(2, 7).unwrap();
320        g.add_edge(3, 8).unwrap();
321        g.add_edge(4, 9).unwrap();
322        assert!(is_house_free(&g).unwrap());
323    }
324}
rust_igraph/algorithms/properties/is_house_free.rs

rust_igraph/algorithms/properties/
is_house_free.rs
