graph_algo_ptas/algorithm/dynamic_programming/
min_vertex_cover.rs

1use super::{
2    solve::{DpTable, DpTableEntry},
3    utils::{bit_vec_powerset, immutable_bit_vec_update, init_bit_vec, to_bit_vec},
4};
5use arboretum_td::graph::{BaseGraph, HashMapGraph};
6use fxhash::FxHashSet;
7use itertools::Itertools;
8use std::collections::HashSet;
9
10pub fn handle_leaf_node(graph: &HashMapGraph, id: usize, tables: &mut [DpTable], vertex: usize) {
11    tables[id].insert(init_bit_vec(graph.order()), DpTableEntry::new_leaf(0, None));
12    tables[id].insert(
13        immutable_bit_vec_update(&init_bit_vec(graph.order()), vertex),
14        DpTableEntry::new_leaf(1, Some(vertex)),
15    );
16}
17
18pub fn handle_join_node(
19    graph: &HashMapGraph,
20    id: usize,
21    left_child_id: usize,
22    right_child_id: usize,
23    tables: &mut [DpTable],
24    vertex_set: &FxHashSet<usize>,
25) {
26    for subset_vec in vertex_set.iter().powerset() {
27        let subset = to_bit_vec(subset_vec.iter().copied(), graph.order());
28        let left_val = tables[left_child_id].get(&subset).unwrap().val;
29        let right_val = tables[right_child_id].get(&subset).unwrap().val;
30
31        let new_val = if left_val == i32::max_value() || right_val == i32::max_value() {
32            i32::max_value()
33        } else {
34            left_val + right_val - subset_vec.len() as i32
35        };
36
37        tables[id].insert(
38            subset.clone(),
39            DpTableEntry::new_join(new_val, left_child_id, right_child_id, subset),
40        );
41    }
42}
43
44pub fn handle_forget_node(
45    graph: &HashMapGraph,
46    id: usize,
47    child_id: usize,
48    tables: &mut [DpTable],
49    vertex_set: &FxHashSet<usize>,
50    forgotten_vertex: usize,
51) {
52    for subset in bit_vec_powerset(vertex_set, graph.order()) {
53        let val = tables[child_id].get(&subset).unwrap().val;
54        let subset_with_v = immutable_bit_vec_update(&subset, forgotten_vertex);
55        let val_with_v = tables[child_id].get(&subset_with_v).unwrap().val;
56        let (min_val, subset_used) = if val < val_with_v {
57            (val, subset.clone())
58        } else {
59            (val_with_v, subset_with_v)
60        };
61        tables[id].insert(
62            subset,
63            DpTableEntry::new_forget(min_val, child_id, subset_used),
64        );
65    }
66}
67
68pub fn handle_introduce_node(
69    graph: &HashMapGraph,
70    id: usize,
71    child_id: usize,
72    tables: &mut [DpTable],
73    _: &FxHashSet<usize>,
74    child_vertex_set: &FxHashSet<usize>,
75    introduced_vertex: usize,
76) {
77    for subset_vec in child_vertex_set.iter().powerset() {
78        let subset = to_bit_vec(subset_vec.iter().copied(), graph.order());
79        let neighbors = graph
80            .neighborhood_set(introduced_vertex)
81            .iter()
82            .filter(|w| child_vertex_set.contains(w));
83
84        let mut is_covered = true;
85        for w in neighbors {
86            if !subset_vec.contains(&w) {
87                is_covered = false;
88                break;
89            }
90        }
91
92        let val = if is_covered {
93            tables[child_id].get(&subset).unwrap().val
94        } else {
95            i32::max_value()
96        };
97        let mut children = HashSet::new();
98        children.insert((child_id, subset.clone()));
99        tables[id].insert(
100            subset.clone(),
101            DpTableEntry {
102                val,
103                children: children.clone(),
104                vertex_used: None,
105            },
106        );
107
108        let child_val = tables[child_id].get(&subset).unwrap().val;
109        let val = if child_val < i32::max_value() {
110            child_val + 1
111        } else {
112            child_val
113        };
114        tables[id].insert(
115            immutable_bit_vec_update(&subset, introduced_vertex),
116            DpTableEntry {
117                val,
118                children,
119                vertex_used: Some(introduced_vertex),
120            },
121        );
122    }
123}
graph_algo_ptas/algorithm/dynamic_programming/min_vertex_cover.rs

graph_algo_ptas/algorithm/dynamic_programming/
min_vertex_cover.rs
