rust_igraph/algorithms/properties/
is_banner_free.rs

1//! Banner-free graph predicate (ALGO-PR-106).
2//!
3//! A graph is banner-free if it contains no induced banner. The banner
4//! (also called flag) is a `C_4` (4-cycle) with one pendant edge:
5//! 5 vertices {a, b, c, d, e} with edges {a-b, b-c, c-d, d-a, a-e}
6//! and no diagonals or other edges. 5 edges total.
7//!
8//! For directed graphs, the function returns `false`.
9
10use crate::core::{Graph, IgraphResult};
11
12/// Check whether a graph is banner-free (no induced banner / flag).
13///
14/// The banner is a `C_4` plus one pendant edge from a cycle vertex.
15///
16/// Returns `false` for directed graphs.
17///
18/// # Examples
19///
20/// ```
21/// use rust_igraph::{Graph, is_banner_free};
22///
23/// // `C_4` is banner-free (no pendant)
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/// g.add_edge(3, 0).unwrap();
29/// assert!(is_banner_free(&g).unwrap());
30///
31/// // Banner: `C_4` {0,1,2,3} + pendant 0-4
32/// let mut g = Graph::with_vertices(5);
33/// g.add_edge(0, 1).unwrap();
34/// g.add_edge(1, 2).unwrap();
35/// g.add_edge(2, 3).unwrap();
36/// g.add_edge(3, 0).unwrap();
37/// g.add_edge(0, 4).unwrap();
38/// assert!(!is_banner_free(&g).unwrap());
39/// ```
40pub fn is_banner_free(graph: &Graph) -> IgraphResult<bool> {
41    if graph.is_directed() {
42        return Ok(false);
43    }
44
45    let n = graph.vcount();
46    if n < 5 {
47        return Ok(true);
48    }
49
50    let n_usize = n as usize;
51    let mut adj = vec![vec![false; n_usize]; n_usize];
52    let mut nbrs_list: Vec<Vec<u32>> = Vec::with_capacity(n_usize);
53
54    for v in 0..n {
55        let nbrs = graph.neighbors(v)?;
56        for &w in &nbrs {
57            adj[v as usize][w as usize] = true;
58        }
59        nbrs_list.push(nbrs);
60    }
61
62    // Induced banner: C_4 {a,b,c,d} with edges a-b, b-c, c-d, d-a
63    // (no diagonals a-c, b-d) plus pendant e adjacent to exactly one
64    // cycle vertex, say a, and not adjacent to b, c, d.
65    //
66    // Strategy: find each induced C_4 (a-b-c-d-a with no diagonals),
67    // then check if any cycle vertex has a neighbor outside the cycle
68    // that is not adjacent to the other 3 cycle vertices.
69    for a in 0..n {
70        let ai = a as usize;
71        for &b in &nbrs_list[ai] {
72            if b <= a {
73                continue;
74            }
75            let bi = b as usize;
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                // a-b-c path, a and c not adjacent
85                for &d in &nbrs_list[ci] {
86                    if d == b || d == a {
87                        continue;
88                    }
89                    let di = d as usize;
90                    if !adj[ai][di] || adj[bi][di] {
91                        continue;
92                    }
93                    // Induced C_4: a-b-c-d-a (diags a-c and b-d absent)
94                    // Check each cycle vertex for a pendant
95                    if has_pendant(&adj, &nbrs_list, ai, bi, ci, di) {
96                        return Ok(false);
97                    }
98                    if has_pendant(&adj, &nbrs_list, bi, ai, ci, di) {
99                        return Ok(false);
100                    }
101                    if has_pendant(&adj, &nbrs_list, ci, ai, bi, di) {
102                        return Ok(false);
103                    }
104                    if has_pendant(&adj, &nbrs_list, di, ai, bi, ci) {
105                        return Ok(false);
106                    }
107                }
108            }
109        }
110    }
111
112    Ok(true)
113}
114
115/// Check if vertex `v` has a neighbor outside {v, o1, o2, o3} that is
116/// not adjacent to o1, o2, or o3.
117fn has_pendant(
118    adj: &[Vec<bool>],
119    nbrs_list: &[Vec<u32>],
120    v: usize,
121    o1: usize,
122    o2: usize,
123    o3: usize,
124) -> bool {
125    for &e_u32 in &nbrs_list[v] {
126        let e = e_u32 as usize;
127        if e == o1 || e == o2 || e == o3 {
128            continue;
129        }
130        if !adj[o1][e] && !adj[o2][e] && !adj[o3][e] {
131            return true;
132        }
133    }
134    false
135}
136
137#[cfg(test)]
138mod tests {
139    use super::*;
140
141    #[test]
142    fn empty_graph() {
143        let g = Graph::with_vertices(0);
144        assert!(is_banner_free(&g).unwrap());
145    }
146
147    #[test]
148    fn small_graphs() {
149        let g = Graph::with_vertices(4);
150        assert!(is_banner_free(&g).unwrap());
151    }
152
153    #[test]
154    fn triangle() {
155        let mut g = Graph::with_vertices(3);
156        g.add_edge(0, 1).unwrap();
157        g.add_edge(1, 2).unwrap();
158        g.add_edge(2, 0).unwrap();
159        assert!(is_banner_free(&g).unwrap());
160    }
161
162    #[test]
163    fn c4_banner_free() {
164        let mut g = Graph::with_vertices(4);
165        g.add_edge(0, 1).unwrap();
166        g.add_edge(1, 2).unwrap();
167        g.add_edge(2, 3).unwrap();
168        g.add_edge(3, 0).unwrap();
169        assert!(is_banner_free(&g).unwrap());
170    }
171
172    #[test]
173    fn banner() {
174        // `C_4` {0,1,2,3} + pendant 0-4
175        let mut g = Graph::with_vertices(5);
176        g.add_edge(0, 1).unwrap();
177        g.add_edge(1, 2).unwrap();
178        g.add_edge(2, 3).unwrap();
179        g.add_edge(3, 0).unwrap();
180        g.add_edge(0, 4).unwrap();
181        assert!(!is_banner_free(&g).unwrap());
182    }
183
184    #[test]
185    fn k5_banner_free() {
186        // `K_5`: no induced `C_4` (every 4-cycle has a chord)
187        let mut g = Graph::with_vertices(5);
188        for i in 0..5u32 {
189            for j in (i + 1)..5 {
190                g.add_edge(i, j).unwrap();
191            }
192        }
193        assert!(is_banner_free(&g).unwrap());
194    }
195
196    #[test]
197    fn path_banner_free() {
198        let mut g = Graph::with_vertices(5);
199        g.add_edge(0, 1).unwrap();
200        g.add_edge(1, 2).unwrap();
201        g.add_edge(2, 3).unwrap();
202        g.add_edge(3, 4).unwrap();
203        assert!(is_banner_free(&g).unwrap());
204    }
205
206    #[test]
207    fn star_banner_free() {
208        let mut g = Graph::with_vertices(6);
209        g.add_edge(0, 1).unwrap();
210        g.add_edge(0, 2).unwrap();
211        g.add_edge(0, 3).unwrap();
212        g.add_edge(0, 4).unwrap();
213        g.add_edge(0, 5).unwrap();
214        assert!(is_banner_free(&g).unwrap());
215    }
216
217    #[test]
218    fn c5_banner_free() {
219        // `C_5` has no induced `C_4` → banner-free
220        let mut g = Graph::with_vertices(5);
221        g.add_edge(0, 1).unwrap();
222        g.add_edge(1, 2).unwrap();
223        g.add_edge(2, 3).unwrap();
224        g.add_edge(3, 4).unwrap();
225        g.add_edge(4, 0).unwrap();
226        assert!(is_banner_free(&g).unwrap());
227    }
228
229    #[test]
230    fn directed_returns_false() {
231        let mut g = Graph::new(3, true).unwrap();
232        g.add_edge(0, 1).unwrap();
233        g.add_edge(1, 2).unwrap();
234        g.add_edge(2, 0).unwrap();
235        assert!(!is_banner_free(&g).unwrap());
236    }
237
238    #[test]
239    fn pendant_connected_to_non_cycle_vertex() {
240        // `C_4` + pendant but pendant also connects to another cycle vertex
241        // → not an induced banner
242        let mut g = Graph::with_vertices(5);
243        g.add_edge(0, 1).unwrap();
244        g.add_edge(1, 2).unwrap();
245        g.add_edge(2, 3).unwrap();
246        g.add_edge(3, 0).unwrap();
247        g.add_edge(0, 4).unwrap();
248        g.add_edge(1, 4).unwrap();
249        assert!(is_banner_free(&g).unwrap());
250    }
251
252    #[test]
253    fn cube_not_banner_free() {
254        // Cube `Q_3` has induced `C_4`. Each `C_4` vertex has a neighbor
255        // outside the cycle → likely has an induced banner.
256        let mut g = Graph::with_vertices(8);
257        g.add_edge(0, 1).unwrap();
258        g.add_edge(0, 2).unwrap();
259        g.add_edge(0, 4).unwrap();
260        g.add_edge(1, 3).unwrap();
261        g.add_edge(1, 5).unwrap();
262        g.add_edge(2, 3).unwrap();
263        g.add_edge(2, 6).unwrap();
264        g.add_edge(3, 7).unwrap();
265        g.add_edge(4, 5).unwrap();
266        g.add_edge(4, 6).unwrap();
267        g.add_edge(5, 7).unwrap();
268        g.add_edge(6, 7).unwrap();
269        assert!(!is_banner_free(&g).unwrap());
270    }
271
272    #[test]
273    fn k33_banner_free() {
274        // `K_{3,3}`: has induced `C_4` but every outside vertex connects
275        // to exactly 2 cycle vertices, never just 1 → banner-free
276        let mut g = Graph::with_vertices(6);
277        for i in 0..3u32 {
278            for j in 3..6u32 {
279                g.add_edge(i, j).unwrap();
280            }
281        }
282        assert!(is_banner_free(&g).unwrap());
283    }
284
285    #[test]
286    fn c4_with_isolated_pendant_not_banner_free() {
287        // `C_4` {0,1,2,3} + pendant 3-4 (4 adj to 3 only)
288        let mut g = Graph::with_vertices(5);
289        g.add_edge(0, 1).unwrap();
290        g.add_edge(1, 2).unwrap();
291        g.add_edge(2, 3).unwrap();
292        g.add_edge(3, 0).unwrap();
293        g.add_edge(3, 4).unwrap();
294        assert!(!is_banner_free(&g).unwrap());
295    }
296}
rust_igraph/algorithms/properties/is_banner_free.rs

rust_igraph/algorithms/properties/
is_banner_free.rs
