rust_igraph/algorithms/properties/
is_bowtie_free.rs

1//! Bowtie-free graph predicate (ALGO-PR-103).
2//!
3//! A graph is bowtie-free if it contains no induced bowtie (also called
4//! butterfly or hourglass). The bowtie consists of two triangles sharing
5//! exactly one vertex (the "center"), with 5 vertices and 6 edges total.
6//!
7//! For directed graphs, the function returns `false`.
8
9use crate::core::{Graph, IgraphResult};
10
11/// Check whether a graph is bowtie-free (no induced bowtie / butterfly).
12///
13/// The bowtie is two triangles sharing a single vertex. It has 5 vertices
14/// {a, b, c, d, e} where c is the center: edges {a-b, a-c, b-c, c-d,
15/// c-e, d-e}, and no other edges among these 5 vertices.
16///
17/// Returns `false` for directed graphs.
18///
19/// # Examples
20///
21/// ```
22/// use rust_igraph::{Graph, is_bowtie_free};
23///
24/// // Triangle is bowtie-free
25/// let mut g = Graph::with_vertices(3);
26/// g.add_edge(0, 1).unwrap();
27/// g.add_edge(1, 2).unwrap();
28/// g.add_edge(2, 0).unwrap();
29/// assert!(is_bowtie_free(&g).unwrap());
30///
31/// // Bowtie: triangles {0,1,2} and {2,3,4} sharing vertex 2
32/// let mut g = Graph::with_vertices(5);
33/// g.add_edge(0, 1).unwrap();
34/// g.add_edge(0, 2).unwrap();
35/// g.add_edge(1, 2).unwrap();
36/// g.add_edge(2, 3).unwrap();
37/// g.add_edge(2, 4).unwrap();
38/// g.add_edge(3, 4).unwrap();
39/// assert!(!is_bowtie_free(&g).unwrap());
40/// ```
41pub fn is_bowtie_free(graph: &Graph) -> IgraphResult<bool> {
42    if graph.is_directed() {
43        return Ok(false);
44    }
45
46    let n = graph.vcount();
47    if n < 5 {
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    // A bowtie has center c with two triangles: {a, b, c} and {d, e, c}
64    // where {a, b} and {d, e} are disjoint and no cross-edges exist
65    // (a-d, a-e, b-d, b-e all absent).
66    //
67    // Strategy: for each vertex c, find all edges among its neighbors
68    // (pairs that form a triangle with c). If c participates in ≥ 2
69    // triangles, check if any two triangles are vertex-disjoint
70    // (excluding c) with no cross-edges.
71    for c in 0..n {
72        let ci = c as usize;
73        let cn = &nbrs_list[ci];
74
75        // Collect triangle-partner pairs among neighbors of c
76        let mut triangle_edges: Vec<(usize, usize)> = Vec::new();
77        for (idx, &u) in cn.iter().enumerate() {
78            let ui = u as usize;
79            for &v in &cn[(idx + 1)..] {
80                let vi = v as usize;
81                if adj[ui][vi] {
82                    triangle_edges.push((ui, vi));
83                }
84            }
85        }
86
87        if triangle_edges.len() < 2 {
88            continue;
89        }
90
91        // Check if any two triangle edges form an induced bowtie
92        for (i, &(a, b)) in triangle_edges.iter().enumerate() {
93            for &(d, e) in &triangle_edges[(i + 1)..] {
94                if a == d || a == e || b == d || b == e {
95                    continue;
96                }
97                if !adj[a][d] && !adj[a][e] && !adj[b][d] && !adj[b][e] {
98                    return Ok(false);
99                }
100            }
101        }
102    }
103
104    Ok(true)
105}
106
107#[cfg(test)]
108mod tests {
109    use super::*;
110
111    #[test]
112    fn empty_graph() {
113        let g = Graph::with_vertices(0);
114        assert!(is_bowtie_free(&g).unwrap());
115    }
116
117    #[test]
118    fn small_graphs() {
119        let g = Graph::with_vertices(4);
120        assert!(is_bowtie_free(&g).unwrap());
121    }
122
123    #[test]
124    fn triangle() {
125        let mut g = Graph::with_vertices(3);
126        g.add_edge(0, 1).unwrap();
127        g.add_edge(1, 2).unwrap();
128        g.add_edge(2, 0).unwrap();
129        assert!(is_bowtie_free(&g).unwrap());
130    }
131
132    #[test]
133    fn bowtie() {
134        // Two triangles sharing vertex 2
135        let mut g = Graph::with_vertices(5);
136        g.add_edge(0, 1).unwrap();
137        g.add_edge(0, 2).unwrap();
138        g.add_edge(1, 2).unwrap();
139        g.add_edge(2, 3).unwrap();
140        g.add_edge(2, 4).unwrap();
141        g.add_edge(3, 4).unwrap();
142        assert!(!is_bowtie_free(&g).unwrap());
143    }
144
145    #[test]
146    fn k4_bowtie_free() {
147        // `K_4`: any 5-vertex subset would need 5 vertices, but only 4 exist.
148        // Even considering all vertices, `K_4` has no bowtie since it only has 4 vertices.
149        let mut g = Graph::with_vertices(4);
150        for i in 0..4u32 {
151            for j in (i + 1)..4 {
152                g.add_edge(i, j).unwrap();
153            }
154        }
155        assert!(is_bowtie_free(&g).unwrap());
156    }
157
158    #[test]
159    fn k5_bowtie_free() {
160        // `K_5`: two triangles sharing a vertex exist, but cross-edges
161        // are also present → no *induced* bowtie
162        let mut g = Graph::with_vertices(5);
163        for i in 0..5u32 {
164            for j in (i + 1)..5 {
165                g.add_edge(i, j).unwrap();
166            }
167        }
168        assert!(is_bowtie_free(&g).unwrap());
169    }
170
171    #[test]
172    fn diamond_bowtie_free() {
173        // Diamond (`K_4` minus one edge): 4 vertices, not enough for bowtie
174        let mut g = Graph::with_vertices(4);
175        g.add_edge(0, 1).unwrap();
176        g.add_edge(0, 2).unwrap();
177        g.add_edge(0, 3).unwrap();
178        g.add_edge(1, 2).unwrap();
179        g.add_edge(1, 3).unwrap();
180        assert!(is_bowtie_free(&g).unwrap());
181    }
182
183    #[test]
184    fn two_disjoint_triangles_bowtie_free() {
185        // Two triangles that don't share any vertex → no bowtie
186        let mut g = Graph::with_vertices(6);
187        g.add_edge(0, 1).unwrap();
188        g.add_edge(1, 2).unwrap();
189        g.add_edge(2, 0).unwrap();
190        g.add_edge(3, 4).unwrap();
191        g.add_edge(4, 5).unwrap();
192        g.add_edge(5, 3).unwrap();
193        assert!(is_bowtie_free(&g).unwrap());
194    }
195
196    #[test]
197    fn two_triangles_sharing_edge_bowtie_free() {
198        // Two triangles sharing an edge (diamond with extra vertex): {0,1,2} and {0,1,3}
199        // Triangles share edge 0-1, not just a vertex → not a bowtie
200        let mut g = Graph::with_vertices(4);
201        g.add_edge(0, 1).unwrap();
202        g.add_edge(0, 2).unwrap();
203        g.add_edge(1, 2).unwrap();
204        g.add_edge(0, 3).unwrap();
205        g.add_edge(1, 3).unwrap();
206        assert!(is_bowtie_free(&g).unwrap());
207    }
208
209    #[test]
210    fn bowtie_with_extra_cross_edge() {
211        // Bowtie + one cross-edge: {0,1,2} and {2,3,4} but add 0-3
212        // Now the induced subgraph on {0,1,2,3,4} has 7 edges, not a bowtie
213        let mut g = Graph::with_vertices(5);
214        g.add_edge(0, 1).unwrap();
215        g.add_edge(0, 2).unwrap();
216        g.add_edge(1, 2).unwrap();
217        g.add_edge(2, 3).unwrap();
218        g.add_edge(2, 4).unwrap();
219        g.add_edge(3, 4).unwrap();
220        g.add_edge(0, 3).unwrap();
221        assert!(is_bowtie_free(&g).unwrap());
222    }
223
224    #[test]
225    fn directed_returns_false() {
226        let mut g = Graph::new(3, true).unwrap();
227        g.add_edge(0, 1).unwrap();
228        g.add_edge(1, 2).unwrap();
229        g.add_edge(2, 0).unwrap();
230        assert!(!is_bowtie_free(&g).unwrap());
231    }
232
233    #[test]
234    fn path_bowtie_free() {
235        let mut g = Graph::with_vertices(5);
236        g.add_edge(0, 1).unwrap();
237        g.add_edge(1, 2).unwrap();
238        g.add_edge(2, 3).unwrap();
239        g.add_edge(3, 4).unwrap();
240        assert!(is_bowtie_free(&g).unwrap());
241    }
242
243    #[test]
244    fn star_bowtie_free() {
245        let mut g = Graph::with_vertices(6);
246        g.add_edge(0, 1).unwrap();
247        g.add_edge(0, 2).unwrap();
248        g.add_edge(0, 3).unwrap();
249        g.add_edge(0, 4).unwrap();
250        g.add_edge(0, 5).unwrap();
251        assert!(is_bowtie_free(&g).unwrap());
252    }
253
254    #[test]
255    fn triple_bowtie() {
256        // Three triangles sharing vertex 0: {0,1,2}, {0,3,4}, {0,5,6}
257        // Multiple bowties present
258        let mut g = Graph::with_vertices(7);
259        g.add_edge(0, 1).unwrap();
260        g.add_edge(0, 2).unwrap();
261        g.add_edge(1, 2).unwrap();
262        g.add_edge(0, 3).unwrap();
263        g.add_edge(0, 4).unwrap();
264        g.add_edge(3, 4).unwrap();
265        g.add_edge(0, 5).unwrap();
266        g.add_edge(0, 6).unwrap();
267        g.add_edge(5, 6).unwrap();
268        assert!(!is_bowtie_free(&g).unwrap());
269    }
270}
rust_igraph/algorithms/properties/is_bowtie_free.rs

rust_igraph/algorithms/properties/
is_bowtie_free.rs
