1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

use arboretum_td::graph::{BaseGraph, HashMapGraph, MutableGraph};
use std::collections::HashSet;

pub fn is_vertex_cover(graph: &HashMapGraph, sol: &HashSet<usize>) -> bool {
    let mut graph = graph.clone();

    for v in sol {
        graph.remove_vertex(*v);
    }

    let mut vertices = graph.vertices();

    vertices.all(|v| graph.neighborhood_set(v).is_empty())
}

pub fn brute_force_min_vertex_cover(graph: &HashMapGraph) -> HashSet<usize> {
    let n = graph.order();

    for i in 0..n + 1 {
        let mut sol = HashSet::new();
        if brute_force_min_vertex_cover_rec(graph, &mut sol, i, 0) {
            return sol;
        }
    }

    panic!("should never happen")
}

fn brute_force_min_vertex_cover_rec(
    graph: &HashMapGraph,
    sol: &mut HashSet<usize>,
    mio_size: usize,
    current_vertex: usize,
) -> bool {
    if current_vertex == graph.order() {
        if sol.len() != mio_size {
            return false;
        }

        return is_vertex_cover(graph, sol);
    }

    sol.insert(current_vertex);
    if brute_force_min_vertex_cover_rec(graph, sol, mio_size, current_vertex + 1) {
        return true;
    }

    sol.remove(&current_vertex);
    if brute_force_min_vertex_cover_rec(graph, sol, mio_size, current_vertex + 1) {
        return true;
    }

    false
}

#[cfg(test)]
mod tests {
    use crate::{
        generation::erdos_renyi::generate_hash_map_graph,
        utils::min_vertex_cover::{brute_force_min_vertex_cover, is_vertex_cover},
    };
    use arboretum_td::graph::{HashMapGraph, MutableGraph};
    use std::collections::HashSet;

    #[test]
    fn isolated() {
        let sol = HashSet::new();

        for n in 1..10 {
            let graph = generate_hash_map_graph(n, 0.0, Some(n as u64));

            assert!(is_vertex_cover(&graph, &sol));
            assert!(is_vertex_cover(
                &graph,
                &brute_force_min_vertex_cover(&graph)
            ))
        }
    }

    #[test]
    fn single_edge() {
        let mut graph = HashMapGraph::new();
        graph.add_vertex(0);
        graph.add_vertex(1);
        graph.add_edge(0, 1);

        let mut sol = HashSet::new();

        assert!(!is_vertex_cover(&graph, &sol));

        sol.insert(0);
        assert!(is_vertex_cover(&graph, &sol));

        sol.insert(1);
        assert!(is_vertex_cover(&graph, &sol));

        assert!(is_vertex_cover(
            &graph,
            &brute_force_min_vertex_cover(&graph)
        ))
    }

    #[test]
    fn clique() {
        let mut sol = HashSet::new();
        sol.insert(0);

        for n in 2..15 {
            let graph = generate_hash_map_graph(n, 0.3, Some(n as u64));

            assert!(is_vertex_cover(
                &graph,
                &brute_force_min_vertex_cover(&graph)
            ))
        }
    }
}