rust_igraph/algorithms/properties/
is_net_free.rs

1//! Net-free graph predicate (ALGO-PR-125).
2//!
3//! A graph is net-free if it contains no induced net subgraph.
4//! The net graph consists of a triangle with a pendant edge on
5//! each vertex (6 vertices, 6 edges). It is also called the
6//! 3-sun complement or `S_3`.
7//!
8//! Net-free graphs appear in structural graph theory: a graph
9//! is claw-free and net-free iff it is a proper circular-arc
10//! graph (Trotter and Moore, 1976).
11//!
12//! Directed graphs are treated as undirected.
13
14use crate::core::{Graph, IgraphResult};
15
16/// Check whether a graph is net-free (no induced net subgraph).
17///
18/// The net has 6 vertices: a triangle {a, b, c} plus pendants
19/// {d, e, f} where d-a, e-b, f-c are the pendant edges.
20/// The algorithm checks all 6-vertex subsets.
21///
22/// Directed graphs are treated as undirected.
23///
24/// # Examples
25///
26/// ```
27/// use rust_igraph::{Graph, is_net_free};
28///
29/// // Triangle: no induced net (too few vertices for net)
30/// let mut g = Graph::with_vertices(3);
31/// g.add_edge(0, 1).unwrap();
32/// g.add_edge(1, 2).unwrap();
33/// g.add_edge(2, 0).unwrap();
34/// assert!(is_net_free(&g).unwrap());
35///
36/// // Net graph itself: NOT net-free
37/// let mut g = Graph::with_vertices(6);
38/// // Triangle 0-1-2
39/// g.add_edge(0, 1).unwrap();
40/// g.add_edge(1, 2).unwrap();
41/// g.add_edge(2, 0).unwrap();
42/// // Pendants
43/// g.add_edge(0, 3).unwrap();
44/// g.add_edge(1, 4).unwrap();
45/// g.add_edge(2, 5).unwrap();
46/// assert!(!is_net_free(&g).unwrap());
47/// ```
48pub fn is_net_free(graph: &Graph) -> IgraphResult<bool> {
49    let n = graph.vcount();
50    if n < 6 {
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    for v in 0..n {
57        let nbrs = graph.neighbors(v)?;
58        for &w in &nbrs {
59            adj[v as usize][w as usize] = true;
60            adj[w as usize][v as usize] = true;
61        }
62    }
63
64    let verts: Vec<usize> = (0..n_usize).collect();
65    for (i0, &a) in verts.iter().enumerate() {
66        for (i1, &b) in verts.iter().enumerate().skip(i0 + 1) {
67            if !adj[a][b] {
68                continue;
69            }
70            for &c in &verts[(i1 + 1)..] {
71                if !adj[a][c] || !adj[b][c] {
72                    continue;
73                }
74                // a-b-c is a triangle. Look for 3 distinct pendants.
75                if has_net_pendants(&adj, a, b, c, n_usize) {
76                    return Ok(false);
77                }
78            }
79        }
80    }
81
82    Ok(true)
83}
84
85fn has_net_pendants(adj: &[Vec<bool>], a: usize, b: usize, c: usize, n: usize) -> bool {
86    let tri = [a, b, c];
87
88    let pend_a: Vec<usize> = (0..n)
89        .filter(|&v| !tri.contains(&v) && adj[v][a] && !adj[v][b] && !adj[v][c])
90        .collect();
91    let pend_b: Vec<usize> = (0..n)
92        .filter(|&v| !tri.contains(&v) && !adj[v][a] && adj[v][b] && !adj[v][c])
93        .collect();
94    let pend_c: Vec<usize> = (0..n)
95        .filter(|&v| !tri.contains(&v) && !adj[v][a] && !adj[v][b] && adj[v][c])
96        .collect();
97
98    for &da in &pend_a {
99        for &db in &pend_b {
100            if adj[da][db] {
101                continue;
102            }
103            for &dc in &pend_c {
104                if dc != da && dc != db && !adj[dc][da] && !adj[dc][db] {
105                    return true;
106                }
107            }
108        }
109    }
110    false
111}
112
113#[cfg(test)]
114mod tests {
115    use super::*;
116
117    #[test]
118    fn empty_graph() {
119        let g = Graph::with_vertices(0);
120        assert!(is_net_free(&g).unwrap());
121    }
122
123    #[test]
124    fn single_vertex() {
125        let g = Graph::with_vertices(1);
126        assert!(is_net_free(&g).unwrap());
127    }
128
129    #[test]
130    fn triangle() {
131        let mut g = Graph::with_vertices(3);
132        g.add_edge(0, 1).unwrap();
133        g.add_edge(1, 2).unwrap();
134        g.add_edge(2, 0).unwrap();
135        assert!(is_net_free(&g).unwrap());
136    }
137
138    #[test]
139    fn net_graph() {
140        let mut g = Graph::with_vertices(6);
141        g.add_edge(0, 1).unwrap();
142        g.add_edge(1, 2).unwrap();
143        g.add_edge(2, 0).unwrap();
144        g.add_edge(0, 3).unwrap();
145        g.add_edge(1, 4).unwrap();
146        g.add_edge(2, 5).unwrap();
147        assert!(!is_net_free(&g).unwrap());
148    }
149
150    #[test]
151    fn k4() {
152        let mut g = Graph::with_vertices(4);
153        for i in 0..4u32 {
154            for j in (i + 1)..4 {
155                g.add_edge(i, j).unwrap();
156            }
157        }
158        assert!(is_net_free(&g).unwrap());
159    }
160
161    #[test]
162    fn k5() {
163        let mut g = Graph::with_vertices(5);
164        for i in 0..5u32 {
165            for j in (i + 1)..5 {
166                g.add_edge(i, j).unwrap();
167            }
168        }
169        assert!(is_net_free(&g).unwrap());
170    }
171
172    #[test]
173    fn c5() {
174        let mut g = Graph::with_vertices(5);
175        g.add_edge(0, 1).unwrap();
176        g.add_edge(1, 2).unwrap();
177        g.add_edge(2, 3).unwrap();
178        g.add_edge(3, 4).unwrap();
179        g.add_edge(4, 0).unwrap();
180        assert!(is_net_free(&g).unwrap());
181    }
182
183    #[test]
184    fn star() {
185        let mut g = Graph::with_vertices(5);
186        g.add_edge(0, 1).unwrap();
187        g.add_edge(0, 2).unwrap();
188        g.add_edge(0, 3).unwrap();
189        g.add_edge(0, 4).unwrap();
190        assert!(is_net_free(&g).unwrap());
191    }
192
193    #[test]
194    fn path_p6() {
195        let mut g = Graph::with_vertices(6);
196        g.add_edge(0, 1).unwrap();
197        g.add_edge(1, 2).unwrap();
198        g.add_edge(2, 3).unwrap();
199        g.add_edge(3, 4).unwrap();
200        g.add_edge(4, 5).unwrap();
201        assert!(is_net_free(&g).unwrap());
202    }
203
204    #[test]
205    fn triangle_with_one_pendant() {
206        // Triangle 0-1-2 + pendant 0-3. Not a net (only 1 pendant).
207        let mut g = Graph::with_vertices(4);
208        g.add_edge(0, 1).unwrap();
209        g.add_edge(1, 2).unwrap();
210        g.add_edge(2, 0).unwrap();
211        g.add_edge(0, 3).unwrap();
212        assert!(is_net_free(&g).unwrap());
213    }
214
215    #[test]
216    fn triangle_with_two_pendants() {
217        // Triangle 0-1-2 + pendants 0-3, 1-4. Still not a net (need 3).
218        let mut g = Graph::with_vertices(5);
219        g.add_edge(0, 1).unwrap();
220        g.add_edge(1, 2).unwrap();
221        g.add_edge(2, 0).unwrap();
222        g.add_edge(0, 3).unwrap();
223        g.add_edge(1, 4).unwrap();
224        assert!(is_net_free(&g).unwrap());
225    }
226
227    #[test]
228    fn net_with_extra_edges() {
229        // Net + extra edge between pendants → no longer induced net
230        let mut g = Graph::with_vertices(6);
231        g.add_edge(0, 1).unwrap();
232        g.add_edge(1, 2).unwrap();
233        g.add_edge(2, 0).unwrap();
234        g.add_edge(0, 3).unwrap();
235        g.add_edge(1, 4).unwrap();
236        g.add_edge(2, 5).unwrap();
237        g.add_edge(3, 4).unwrap();
238        assert!(is_net_free(&g).unwrap());
239    }
240
241    #[test]
242    fn edgeless() {
243        let g = Graph::with_vertices(6);
244        assert!(is_net_free(&g).unwrap());
245    }
246
247    #[test]
248    fn directed_treated_as_undirected() {
249        let mut g = Graph::new(6, true).unwrap();
250        g.add_edge(0, 1).unwrap();
251        g.add_edge(1, 2).unwrap();
252        g.add_edge(2, 0).unwrap();
253        g.add_edge(0, 3).unwrap();
254        g.add_edge(1, 4).unwrap();
255        g.add_edge(2, 5).unwrap();
256        assert!(!is_net_free(&g).unwrap());
257    }
258}
rust_igraph/algorithms/properties/is_net_free.rs

rust_igraph/algorithms/properties/
is_net_free.rs
