graph_algo_ptas/algorithm/dynamic_programming/
min_vertex_cover.rs1use 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}