graph_algo_ptas/algorithm/dynamic_programming/
max_independent_set.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;
8
9pub fn handle_leaf_node(graph: &HashMapGraph, id: usize, tables: &mut [DpTable], vertex: usize) {
10    tables[id].insert(init_bit_vec(graph.order()), DpTableEntry::new_leaf(0, None));
11    tables[id].insert(
12        immutable_bit_vec_update(&init_bit_vec(graph.order()), vertex),
13        DpTableEntry::new_leaf(1, Some(vertex)),
14    );
15}
16
17pub fn handle_join_node(
18    graph: &HashMapGraph,
19    id: usize,
20    left_child_id: usize,
21    right_child_id: usize,
22    tables: &mut [DpTable],
23    vertex_set: &FxHashSet<usize>,
24) {
25    for subset_vec in vertex_set.iter().powerset() {
26        let subset = to_bit_vec(subset_vec.iter().copied(), graph.order());
27        let left_val = tables[left_child_id].get(&subset).unwrap().val;
28        let right_val = tables[right_child_id].get(&subset).unwrap().val;
29        let new_val = if left_val == i32::min_value() || right_val == i32::min_value() {
30            i32::min_value()
31        } else {
32            left_val + right_val - subset_vec.len() as i32
33        };
34
35        tables[id].insert(
36            subset.clone(),
37            DpTableEntry::new_join(new_val, left_child_id, right_child_id, subset),
38        );
39    }
40}
41
42pub fn handle_forget_node(
43    graph: &HashMapGraph,
44    id: usize,
45    child_id: usize,
46    tables: &mut [DpTable],
47    vertex_set: &FxHashSet<usize>,
48    forgotten_vertex: usize,
49) {
50    for subset in bit_vec_powerset(vertex_set, graph.order()) {
51        let val = tables[child_id].get(&subset).unwrap().val;
52        let subset_with_v = immutable_bit_vec_update(&subset, forgotten_vertex);
53        let val_with_v = tables[child_id].get(&subset_with_v).unwrap().val;
54        let (new_val, subset_used) = if val > val_with_v {
55            (val, subset.clone())
56        } else {
57            (val_with_v, subset_with_v)
58        };
59        tables[id].insert(
60            subset,
61            DpTableEntry::new_forget(new_val, child_id, subset_used),
62        );
63    }
64}
65
66pub fn handle_introduce_node(
67    graph: &HashMapGraph,
68    id: usize,
69    child_id: usize,
70    tables: &mut [DpTable],
71    _: &FxHashSet<usize>,
72    child_vertex_set: &FxHashSet<usize>,
73    introduced_vertex: usize,
74) {
75    for subset_vec in child_vertex_set.iter().powerset() {
76        let subset = to_bit_vec(subset_vec.iter().copied(), graph.order());
77        let val = tables[child_id].get(&subset).unwrap().val;
78        tables[id].insert(
79            subset.clone(),
80            DpTableEntry::new_intro(val, child_id, subset.clone(), None),
81        );
82
83        let has_edge = subset_vec
84            .iter()
85            .any(|w| graph.has_edge(introduced_vertex, **w));
86
87        let (new_val, node_used) = if has_edge {
88            (i32::min_value(), None)
89        } else {
90            (
91                if val == i32::min_value() {
92                    i32::min_value()
93                } else {
94                    val + 1
95                },
96                Some(introduced_vertex),
97            )
98        };
99        let subset_with_v = immutable_bit_vec_update(&subset, introduced_vertex);
100        tables[id].insert(
101            subset_with_v,
102            DpTableEntry::new_intro(new_val, child_id, subset, node_used),
103        );
104    }
105}
graph_algo_ptas/algorithm/dynamic_programming/max_independent_set.rs

graph_algo_ptas/algorithm/dynamic_programming/
max_independent_set.rs
