graph_algo_ptas/utils/
min_vertex_cover.rs

1use arboretum_td::graph::{BaseGraph, HashMapGraph, MutableGraph};
2use std::collections::HashSet;
3
4pub fn is_vertex_cover(graph: &HashMapGraph, sol: &HashSet<usize>) -> bool {
5    let mut graph = graph.clone();
6
7    for v in sol {
8        graph.remove_vertex(*v);
9    }
10
11    let mut vertices = graph.vertices();
12
13    vertices.all(|v| graph.neighborhood_set(v).is_empty())
14}
15
16pub fn brute_force_min_vertex_cover(graph: &HashMapGraph) -> HashSet<usize> {
17    let n = graph.order();
18
19    for i in 0..n + 1 {
20        let mut sol = HashSet::new();
21        if brute_force_min_vertex_cover_rec(graph, &mut sol, i, 0) {
22            return sol;
23        }
24    }
25
26    panic!("should never happen")
27}
28
29fn brute_force_min_vertex_cover_rec(
30    graph: &HashMapGraph,
31    sol: &mut HashSet<usize>,
32    mio_size: usize,
33    current_vertex: usize,
34) -> bool {
35    if current_vertex == graph.order() {
36        if sol.len() != mio_size {
37            return false;
38        }
39
40        return is_vertex_cover(graph, sol);
41    }
42
43    sol.insert(current_vertex);
44    if brute_force_min_vertex_cover_rec(graph, sol, mio_size, current_vertex + 1) {
45        return true;
46    }
47
48    sol.remove(&current_vertex);
49    if brute_force_min_vertex_cover_rec(graph, sol, mio_size, current_vertex + 1) {
50        return true;
51    }
52
53    false
54}
55
56#[cfg(test)]
57mod tests {
58    use crate::{
59        generation::erdos_renyi::generate_hash_map_graph,
60        utils::min_vertex_cover::{brute_force_min_vertex_cover, is_vertex_cover},
61    };
62    use arboretum_td::graph::{HashMapGraph, MutableGraph};
63    use std::collections::HashSet;
64
65    #[test]
66    fn isolated() {
67        let sol = HashSet::new();
68
69        for n in 1..10 {
70            let graph = generate_hash_map_graph(n, 0.0, Some(n as u64));
71
72            assert!(is_vertex_cover(&graph, &sol));
73            assert!(is_vertex_cover(
74                &graph,
75                &brute_force_min_vertex_cover(&graph)
76            ))
77        }
78    }
79
80    #[test]
81    fn single_edge() {
82        let mut graph = HashMapGraph::new();
83        graph.add_vertex(0);
84        graph.add_vertex(1);
85        graph.add_edge(0, 1);
86
87        let mut sol = HashSet::new();
88
89        assert!(!is_vertex_cover(&graph, &sol));
90
91        sol.insert(0);
92        assert!(is_vertex_cover(&graph, &sol));
93
94        sol.insert(1);
95        assert!(is_vertex_cover(&graph, &sol));
96
97        assert!(is_vertex_cover(
98            &graph,
99            &brute_force_min_vertex_cover(&graph)
100        ))
101    }
102
103    #[test]
104    fn clique() {
105        let mut sol = HashSet::new();
106        sol.insert(0);
107
108        for n in 2..15 {
109            let graph = generate_hash_map_graph(n, 0.3, Some(n as u64));
110
111            assert!(is_vertex_cover(
112                &graph,
113                &brute_force_min_vertex_cover(&graph)
114            ))
115        }
116    }
117}
graph_algo_ptas/utils/min_vertex_cover.rs

graph_algo_ptas/utils/
min_vertex_cover.rs
