graph_algo_ptas/utils/
max_independent_set.rs

1use arboretum_td::graph::{BaseGraph, HashMapGraph};
2use std::collections::HashSet;
3
4pub fn is_independent_set(graph: &HashMapGraph, sol: &HashSet<usize>) -> bool {
5    let sol: Vec<usize> = sol.iter().copied().collect();
6
7    for i in 0..sol.len() {
8        let u = sol[i];
9
10        if !graph.has_vertex(u) {
11            continue;
12        }
13
14        #[allow(clippy::needless_range_loop)]
15        for j in i + 1..sol.len() {
16            let v = sol[j];
17
18            if !graph.has_vertex(v) {
19                continue;
20            }
21
22            if graph.has_edge(u, v) {
23                return false;
24            }
25        }
26    }
27
28    true
29}
30
31pub fn brute_force_max_independent_set(graph: &HashMapGraph) -> HashSet<usize> {
32    let n = graph.order();
33
34    for i in 0..n + 1 {
35        let mut sol = HashSet::new();
36        if brute_force_max_independent_set_rec(graph, &mut sol, n - i, 0) {
37            return sol;
38        }
39    }
40
41    panic!("should never happen")
42}
43
44fn brute_force_max_independent_set_rec(
45    graph: &HashMapGraph,
46    sol: &mut HashSet<usize>,
47    mio_size: usize,
48    current_vertex: usize,
49) -> bool {
50    if current_vertex == graph.order() {
51        if sol.len() != mio_size {
52            return false;
53        }
54
55        return is_independent_set(graph, sol);
56    }
57
58    sol.insert(current_vertex);
59    if brute_force_max_independent_set_rec(graph, sol, mio_size, current_vertex + 1) {
60        return true;
61    }
62
63    sol.remove(&current_vertex);
64    if brute_force_max_independent_set_rec(graph, sol, mio_size, current_vertex + 1) {
65        return true;
66    }
67
68    false
69}
70
71#[cfg(test)]
72mod tests {
73    use crate::{
74        generation::erdos_renyi::generate_hash_map_graph,
75        utils::max_independent_set::{brute_force_max_independent_set, is_independent_set},
76    };
77    use arboretum_td::graph::{HashMapGraph, MutableGraph};
78    use std::collections::HashSet;
79
80    #[test]
81    fn empty_set() {
82        let sol = HashSet::new();
83
84        for n in 1..10 {
85            let graph = generate_hash_map_graph(n, 0.3, Some(n as u64));
86
87            assert!(is_independent_set(&graph, &sol));
88            assert!(is_independent_set(
89                &graph,
90                &brute_force_max_independent_set(&graph)
91            ))
92        }
93    }
94
95    #[test]
96    fn isolated() {
97        let mut sol = HashSet::new();
98
99        for n in 1..10 {
100            let graph = generate_hash_map_graph(n, 0., Some(n as u64));
101            sol.insert(n - 1);
102
103            assert!(is_independent_set(&graph, &sol));
104            assert!(is_independent_set(
105                &graph,
106                &brute_force_max_independent_set(&graph)
107            ))
108        }
109    }
110
111    #[test]
112    fn single_edge() {
113        let mut graph = HashMapGraph::new();
114        graph.add_vertex(0);
115        graph.add_vertex(1);
116        graph.add_edge(0, 1);
117
118        let mut sol = HashSet::new();
119        sol.insert(0);
120        assert!(is_independent_set(&graph, &sol));
121
122        sol.insert(1);
123        assert!(!is_independent_set(&graph, &sol));
124
125        assert!(is_independent_set(
126            &graph,
127            &brute_force_max_independent_set(&graph)
128        ))
129    }
130
131    #[test]
132    fn clique() {
133        let mut sol = HashSet::new();
134        sol.insert(0);
135
136        for n in 2..15 {
137            let graph = generate_hash_map_graph(n, 1., Some(n as u64));
138
139            let v = n - 1;
140
141            sol.insert(v);
142            assert!(!is_independent_set(&graph, &sol));
143
144            sol.remove(&v);
145            assert!(is_independent_set(&graph, &sol));
146
147            assert!(is_independent_set(
148                &graph,
149                &brute_force_max_independent_set(&graph)
150            ))
151        }
152    }
153}
graph_algo_ptas/utils/max_independent_set.rs

graph_algo_ptas/utils/
max_independent_set.rs
