rust_igraph/algorithms/properties/
independent_set.rs

1//! Independent set heuristics and ratios (ALGO-TR-029).
2//!
3//! Complements the exact `maximum_independent_set` and
4//! `independence_number` in `crate::algorithms::independent_set` /
5//! `crate::algorithms::cliques` with:
6//!
7//! - **Independence ratio**: `α(G) / n`.
8//! - **Greedy independent set**: a maximal (not necessarily maximum)
9//!   independent set found by greedily picking smallest-degree vertices.
10
11#![allow(
12    clippy::cast_possible_truncation,
13    clippy::cast_precision_loss,
14    clippy::many_single_char_names,
15    clippy::needless_range_loop,
16    clippy::too_many_lines
17)]
18
19use crate::core::{Graph, IgraphResult};
20
21/// Compute the independence ratio `α(G) / n`.
22///
23/// Uses the exact `independence_number` from the cliques module.
24///
25/// # Examples
26///
27/// ```
28/// use rust_igraph::{Graph, independence_ratio};
29///
30/// // K_3: α = 1, ratio = 1/3
31/// let g = Graph::from_edges(&[(0,1),(1,2),(0,2)], false, Some(3)).unwrap();
32/// let r = independence_ratio(&g).unwrap();
33/// assert!((r - 1.0/3.0).abs() < 0.01);
34/// ```
35pub fn independence_ratio(graph: &Graph) -> IgraphResult<f64> {
36    let n = graph.vcount() as usize;
37    if n == 0 {
38        return Ok(0.0);
39    }
40    let alpha = crate::algorithms::cliques::independence_number(graph)?;
41    Ok(f64::from(alpha) / n as f64)
42}
43
44/// Find a maximal independent set using a greedy heuristic.
45///
46/// Iteratively picks the vertex with the smallest degree among
47/// remaining candidates, adds it to the independent set, and removes
48/// it and all its neighbours from the candidate pool.
49///
50/// The result is maximal (no vertex can be added without breaking
51/// independence) but not necessarily maximum.
52///
53/// # Examples
54///
55/// ```
56/// use rust_igraph::{Graph, greedy_independent_set, is_independent_vertex_set};
57///
58/// let g = Graph::from_edges(
59///     &[(0,1),(1,2),(2,3),(3,4),(4,0)], false, Some(5)
60/// ).unwrap();
61/// let ind = greedy_independent_set(&g).unwrap();
62/// assert!(is_independent_vertex_set(&g, &ind).unwrap());
63/// assert!(ind.len() >= 2);
64/// ```
65pub fn greedy_independent_set(graph: &Graph) -> IgraphResult<Vec<u32>> {
66    let n = graph.vcount() as usize;
67    if n == 0 {
68        return Ok(Vec::new());
69    }
70
71    let mut available = vec![true; n];
72    let mut result = Vec::new();
73
74    loop {
75        let mut best_v = None;
76        let mut best_deg = usize::MAX;
77
78        for v in 0..n {
79            if !available[v] {
80                continue;
81            }
82            let deg = graph
83                .neighbors(v as u32)?
84                .iter()
85                .filter(|&&u| available[u as usize])
86                .count();
87            if deg < best_deg {
88                best_deg = deg;
89                best_v = Some(v as u32);
90            }
91        }
92
93        let Some(v) = best_v else { break };
94
95        result.push(v);
96        available[v as usize] = false;
97
98        let nbrs = graph.neighbors(v)?;
99        for &u in &nbrs {
100            available[u as usize] = false;
101        }
102    }
103
104    result.sort_unstable();
105    Ok(result)
106}
107
108#[cfg(test)]
109mod tests {
110    fn is_ind(graph: &Graph, vertices: &[u32]) -> bool {
111        crate::algorithms::properties::is_clique::is_independent_vertex_set(graph, vertices)
112            .unwrap_or(false)
113    }
114
115    use super::*;
116
117    fn path4() -> Graph {
118        Graph::from_edges(&[(0, 1), (1, 2), (2, 3)], false, Some(4)).unwrap()
119    }
120
121    fn k3() -> Graph {
122        Graph::from_edges(&[(0, 1), (1, 2), (0, 2)], false, Some(3)).unwrap()
123    }
124
125    fn k4() -> Graph {
126        Graph::from_edges(
127            &[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)],
128            false,
129            Some(4),
130        )
131        .unwrap()
132    }
133
134    fn cycle5() -> Graph {
135        Graph::from_edges(&[(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)], false, Some(5)).unwrap()
136    }
137
138    fn star5() -> Graph {
139        Graph::from_edges(&[(0, 1), (0, 2), (0, 3), (0, 4)], false, Some(5)).unwrap()
140    }
141
142    fn petersen() -> Graph {
143        Graph::from_edges(
144            &[
145                (0, 1),
146                (1, 2),
147                (2, 3),
148                (3, 4),
149                (4, 0),
150                (0, 5),
151                (1, 6),
152                (2, 7),
153                (3, 8),
154                (4, 9),
155                (5, 7),
156                (7, 9),
157                (9, 6),
158                (6, 8),
159                (8, 5),
160            ],
161            false,
162            Some(10),
163        )
164        .unwrap()
165    }
166
167    // --- independence_ratio ---
168
169    #[test]
170    fn ir_k3() {
171        let r = independence_ratio(&k3()).unwrap();
172        assert!((r - 1.0 / 3.0).abs() < 0.01);
173    }
174
175    #[test]
176    fn ir_k4() {
177        let r = independence_ratio(&k4()).unwrap();
178        assert!((r - 0.25).abs() < 0.01);
179    }
180
181    #[test]
182    fn ir_path4() {
183        let r = independence_ratio(&path4()).unwrap();
184        assert!((r - 0.5).abs() < 0.01);
185    }
186
187    #[test]
188    fn ir_cycle5() {
189        let r = independence_ratio(&cycle5()).unwrap();
190        assert!((r - 0.4).abs() < 0.01);
191    }
192
193    #[test]
194    fn ir_isolated() {
195        let g = Graph::with_vertices(5);
196        let r = independence_ratio(&g).unwrap();
197        assert!((r - 1.0).abs() < 0.01);
198    }
199
200    #[test]
201    fn ir_empty() {
202        let g = Graph::with_vertices(0);
203        let r = independence_ratio(&g).unwrap();
204        assert!(r.abs() < 1e-10);
205    }
206
207    #[test]
208    fn ir_star5() {
209        let r = independence_ratio(&star5()).unwrap();
210        assert!((r - 0.8).abs() < 0.01);
211    }
212
213    // --- greedy_independent_set ---
214
215    #[test]
216    fn gis_empty() {
217        let g = Graph::with_vertices(0);
218        assert!(greedy_independent_set(&g).unwrap().is_empty());
219    }
220
221    #[test]
222    fn gis_isolated() {
223        let g = Graph::with_vertices(4);
224        let ind = greedy_independent_set(&g).unwrap();
225        assert_eq!(ind.len(), 4);
226    }
227
228    #[test]
229    fn gis_path4() {
230        let g = path4();
231        let ind = greedy_independent_set(&g).unwrap();
232        assert!(is_ind(&g, &ind));
233        assert!(ind.len() >= 2);
234    }
235
236    #[test]
237    fn gis_k4() {
238        let g = k4();
239        let ind = greedy_independent_set(&g).unwrap();
240        assert_eq!(ind.len(), 1);
241        assert!(is_ind(&g, &ind));
242    }
243
244    #[test]
245    fn gis_cycle5() {
246        let g = cycle5();
247        let ind = greedy_independent_set(&g).unwrap();
248        assert!(is_ind(&g, &ind));
249        assert!(ind.len() >= 2);
250    }
251
252    #[test]
253    fn gis_star5() {
254        let g = star5();
255        let ind = greedy_independent_set(&g).unwrap();
256        assert!(is_ind(&g, &ind));
257        assert!(ind.len() >= 2);
258    }
259
260    #[test]
261    fn gis_petersen() {
262        let g = petersen();
263        let ind = greedy_independent_set(&g).unwrap();
264        assert!(is_ind(&g, &ind));
265        assert!(ind.len() >= 2);
266    }
267
268    #[test]
269    fn gis_is_maximal() {
270        let g = petersen();
271        let ind = greedy_independent_set(&g).unwrap();
272        assert!(is_ind(&g, &ind));
273        let n = g.vcount() as usize;
274        let mut in_set = vec![false; n];
275        for &v in &ind {
276            in_set[v as usize] = true;
277        }
278        for v in 0..g.vcount() {
279            if in_set[v as usize] {
280                continue;
281            }
282            let nbrs = g.neighbors(v).unwrap();
283            let has_neighbor_in_set = nbrs.iter().any(|&u| in_set[u as usize]);
284            assert!(
285                has_neighbor_in_set,
286                "vertex {v} could be added — not maximal"
287            );
288        }
289    }
290
291    // --- cross-consistency ---
292
293    #[test]
294    fn greedy_at_least_one_for_nonempty() {
295        for n in 1_u32..=5 {
296            let g = Graph::with_vertices(n);
297            let ind = greedy_independent_set(&g).unwrap();
298            assert!(!ind.is_empty());
299        }
300    }
301
302    #[test]
303    fn ratio_between_zero_and_one() {
304        for g in &[path4(), k3(), k4(), cycle5(), star5()] {
305            let r = independence_ratio(g).unwrap();
306            assert!((0.0..=1.0).contains(&r));
307        }
308    }
309
310    #[test]
311    fn greedy_at_most_alpha() {
312        for g in &[path4(), k3(), cycle5()] {
313            let alpha = crate::algorithms::cliques::independence_number(g).unwrap();
314            let ind = greedy_independent_set(g).unwrap();
315            assert!(ind.len() as u32 <= alpha);
316        }
317    }
318}
rust_igraph/algorithms/properties/independent_set.rs

rust_igraph/algorithms/properties/
independent_set.rs
