rust_igraph/algorithms/properties/
is_diamond_free.rs

1//! Diamond-free graph predicate (ALGO-PR-097).
2//!
3//! A graph is diamond-free if it contains no induced subgraph
4//! isomorphic to the diamond graph (`K_4` minus one edge, also
5//! denoted `K_4^-`). The diamond has 4 vertices and 5 edges.
6//!
7//! For directed graphs, the function returns `false`.
8
9use crate::core::{Graph, IgraphResult};
10
11/// Check whether a graph is diamond-free.
12///
13/// A diamond-free graph has no induced `K_4` minus one edge. The
14/// diamond has vertices {a, b, c, d} with edges {ab, ac, ad, bc, bd}
15/// (c and d not adjacent).
16///
17/// Returns `false` for directed graphs.
18///
19/// # Examples
20///
21/// ```
22/// use rust_igraph::{Graph, is_diamond_free};
23///
24/// // Triangle is diamond-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_diamond_free(&g).unwrap());
30///
31/// // Diamond: `K_4` minus edge 2-3
32/// let mut g = Graph::with_vertices(4);
33/// g.add_edge(0, 1).unwrap();
34/// g.add_edge(0, 2).unwrap();
35/// g.add_edge(0, 3).unwrap();
36/// g.add_edge(1, 2).unwrap();
37/// g.add_edge(1, 3).unwrap();
38/// assert!(!is_diamond_free(&g).unwrap());
39/// ```
40pub fn is_diamond_free(graph: &Graph) -> IgraphResult<bool> {
41    if graph.is_directed() {
42        return Ok(false);
43    }
44
45    let n = graph.vcount();
46    if n <= 3 {
47        return Ok(true);
48    }
49
50    // Build adjacency for fast pair lookup
51    let n_usize = n as usize;
52    let mut adj = vec![vec![false; n_usize]; n_usize];
53    for v in 0..n {
54        let nbrs = graph.neighbors(v)?;
55        for &w in &nbrs {
56            adj[v as usize][w as usize] = true;
57        }
58    }
59
60    // A diamond is formed when an edge (u, v) has two or more common
61    // neighbors c1, c2 such that c1 and c2 are NOT adjacent.
62    // If c1-c2 are adjacent, then {u, v, c1, c2} form K_4.
63    // If c1-c2 are non-adjacent, then {u, v, c1, c2} form a diamond.
64    //
65    // So: for each edge (u, v), find all common neighbors, and check
66    // if any pair among them is non-adjacent.
67    for u in 0..n {
68        let nbrs_u = graph.neighbors(u)?;
69        for &v in &nbrs_u {
70            if v <= u {
71                continue;
72            }
73
74            // Find common neighbors of u and v
75            let common: Vec<u32> = nbrs_u
76                .iter()
77                .filter(|&&w| w != v && adj[v as usize][w as usize])
78                .copied()
79                .collect();
80
81            // Check if any pair of common neighbors is non-adjacent
82            for i in 0..common.len() {
83                for j in (i + 1)..common.len() {
84                    if !adj[common[i] as usize][common[j] as usize] {
85                        return Ok(false);
86                    }
87                }
88            }
89        }
90    }
91
92    Ok(true)
93}
94
95#[cfg(test)]
96mod tests {
97    use super::*;
98
99    #[test]
100    fn empty_graph() {
101        let g = Graph::with_vertices(0);
102        assert!(is_diamond_free(&g).unwrap());
103    }
104
105    #[test]
106    fn single_vertex() {
107        let g = Graph::with_vertices(1);
108        assert!(is_diamond_free(&g).unwrap());
109    }
110
111    #[test]
112    fn single_edge() {
113        let mut g = Graph::with_vertices(2);
114        g.add_edge(0, 1).unwrap();
115        assert!(is_diamond_free(&g).unwrap());
116    }
117
118    #[test]
119    fn triangle() {
120        let mut g = Graph::with_vertices(3);
121        g.add_edge(0, 1).unwrap();
122        g.add_edge(1, 2).unwrap();
123        g.add_edge(2, 0).unwrap();
124        assert!(is_diamond_free(&g).unwrap());
125    }
126
127    #[test]
128    fn diamond() {
129        // K_4 minus edge 2-3: vertices {0,1,2,3}, edges {01,02,03,12,13}
130        let mut g = Graph::with_vertices(4);
131        g.add_edge(0, 1).unwrap();
132        g.add_edge(0, 2).unwrap();
133        g.add_edge(0, 3).unwrap();
134        g.add_edge(1, 2).unwrap();
135        g.add_edge(1, 3).unwrap();
136        assert!(!is_diamond_free(&g).unwrap());
137    }
138
139    #[test]
140    fn k4_is_diamond_free() {
141        // K_4 is diamond-free: any 4 vertices induce K_4 (6 edges),
142        // not a diamond (5 edges)
143        let mut g = Graph::with_vertices(4);
144        g.add_edge(0, 1).unwrap();
145        g.add_edge(0, 2).unwrap();
146        g.add_edge(0, 3).unwrap();
147        g.add_edge(1, 2).unwrap();
148        g.add_edge(1, 3).unwrap();
149        g.add_edge(2, 3).unwrap();
150        assert!(is_diamond_free(&g).unwrap());
151    }
152
153    #[test]
154    fn path_diamond_free() {
155        let mut g = Graph::with_vertices(5);
156        g.add_edge(0, 1).unwrap();
157        g.add_edge(1, 2).unwrap();
158        g.add_edge(2, 3).unwrap();
159        g.add_edge(3, 4).unwrap();
160        assert!(is_diamond_free(&g).unwrap());
161    }
162
163    #[test]
164    fn cycle_c5_diamond_free() {
165        let mut g = Graph::with_vertices(5);
166        g.add_edge(0, 1).unwrap();
167        g.add_edge(1, 2).unwrap();
168        g.add_edge(2, 3).unwrap();
169        g.add_edge(3, 4).unwrap();
170        g.add_edge(4, 0).unwrap();
171        assert!(is_diamond_free(&g).unwrap());
172    }
173
174    #[test]
175    fn star_diamond_free() {
176        let mut g = Graph::with_vertices(5);
177        g.add_edge(0, 1).unwrap();
178        g.add_edge(0, 2).unwrap();
179        g.add_edge(0, 3).unwrap();
180        g.add_edge(0, 4).unwrap();
181        assert!(is_diamond_free(&g).unwrap());
182    }
183
184    #[test]
185    fn two_triangles_sharing_vertex() {
186        // 0-1-2-0, 0-3-4-0
187        let mut g = Graph::with_vertices(5);
188        g.add_edge(0, 1).unwrap();
189        g.add_edge(1, 2).unwrap();
190        g.add_edge(2, 0).unwrap();
191        g.add_edge(0, 3).unwrap();
192        g.add_edge(3, 4).unwrap();
193        g.add_edge(4, 0).unwrap();
194        // Vertex 0 connects to 1,2,3,4. Common neighbors of edge 0-1:
195        // just 2. Common neighbors of edge 0-3: just 4. No diamond.
196        assert!(is_diamond_free(&g).unwrap());
197    }
198
199    #[test]
200    fn two_triangles_sharing_edge() {
201        // 0-1-2-0, 0-1-3
202        let mut g = Graph::with_vertices(4);
203        g.add_edge(0, 1).unwrap();
204        g.add_edge(1, 2).unwrap();
205        g.add_edge(2, 0).unwrap();
206        g.add_edge(0, 3).unwrap();
207        g.add_edge(1, 3).unwrap();
208        // Edge 0-1 has common neighbors 2 and 3.
209        // 2-3 not adjacent → diamond!
210        assert!(!is_diamond_free(&g).unwrap());
211    }
212
213    #[test]
214    fn directed_returns_false() {
215        let mut g = Graph::new(3, true).unwrap();
216        g.add_edge(0, 1).unwrap();
217        g.add_edge(1, 2).unwrap();
218        g.add_edge(2, 0).unwrap();
219        assert!(!is_diamond_free(&g).unwrap());
220    }
221
222    #[test]
223    fn isolated_vertices() {
224        let g = Graph::with_vertices(10);
225        assert!(is_diamond_free(&g).unwrap());
226    }
227
228    #[test]
229    fn wheel_w5_not_diamond_free() {
230        // W_5: hub 0 connected to cycle 1-2-3-4-5-1
231        let mut g = Graph::with_vertices(6);
232        g.add_edge(0, 1).unwrap();
233        g.add_edge(0, 2).unwrap();
234        g.add_edge(0, 3).unwrap();
235        g.add_edge(0, 4).unwrap();
236        g.add_edge(0, 5).unwrap();
237        g.add_edge(1, 2).unwrap();
238        g.add_edge(2, 3).unwrap();
239        g.add_edge(3, 4).unwrap();
240        g.add_edge(4, 5).unwrap();
241        g.add_edge(5, 1).unwrap();
242        // Edge 0-1 has common neighbors 2 and 5; 2-5 not adjacent → diamond
243        assert!(!is_diamond_free(&g).unwrap());
244    }
245}
rust_igraph/algorithms/properties/is_diamond_free.rs

rust_igraph/algorithms/properties/
is_diamond_free.rs
