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

use super::{
    solve::{DpTable, DpTableEntry},
    utils::{bit_vec_powerset, immutable_bit_vec_update, init_bit_vec, to_bit_vec},
};
use arboretum_td::graph::{BaseGraph, HashMapGraph};
use fxhash::FxHashSet;
use itertools::Itertools;

pub fn handle_leaf_node(graph: &HashMapGraph, id: usize, tables: &mut [DpTable], vertex: usize) {
    tables[id].insert(init_bit_vec(graph.order()), DpTableEntry::new_leaf(0, None));
    tables[id].insert(
        immutable_bit_vec_update(&init_bit_vec(graph.order()), vertex),
        DpTableEntry::new_leaf(1, Some(vertex)),
    );
}

pub fn handle_join_node(
    graph: &HashMapGraph,
    id: usize,
    left_child_id: usize,
    right_child_id: usize,
    tables: &mut [DpTable],
    vertex_set: &FxHashSet<usize>,
) {
    for subset_vec in vertex_set.iter().powerset() {
        let subset = to_bit_vec(subset_vec.iter().copied(), graph.order());
        let left_val = tables[left_child_id].get(&subset).unwrap().val;
        let right_val = tables[right_child_id].get(&subset).unwrap().val;
        let new_val = if left_val == i32::min_value() || right_val == i32::min_value() {
            i32::min_value()
        } else {
            left_val + right_val - subset_vec.len() as i32
        };

        tables[id].insert(
            subset.clone(),
            DpTableEntry::new_join(new_val, left_child_id, right_child_id, subset),
        );
    }
}

pub fn handle_forget_node(
    graph: &HashMapGraph,
    id: usize,
    child_id: usize,
    tables: &mut [DpTable],
    vertex_set: &FxHashSet<usize>,
    forgotten_vertex: usize,
) {
    for subset in bit_vec_powerset(vertex_set, graph.order()) {
        let val = tables[child_id].get(&subset).unwrap().val;
        let subset_with_v = immutable_bit_vec_update(&subset, forgotten_vertex);
        let val_with_v = tables[child_id].get(&subset_with_v).unwrap().val;
        let (new_val, subset_used) = if val > val_with_v {
            (val, subset.clone())
        } else {
            (val_with_v, subset_with_v)
        };
        tables[id].insert(
            subset,
            DpTableEntry::new_forget(new_val, child_id, subset_used),
        );
    }
}

pub fn handle_introduce_node(
    graph: &HashMapGraph,
    id: usize,
    child_id: usize,
    tables: &mut [DpTable],
    _: &FxHashSet<usize>,
    child_vertex_set: &FxHashSet<usize>,
    introduced_vertex: usize,
) {
    for subset_vec in child_vertex_set.iter().powerset() {
        let subset = to_bit_vec(subset_vec.iter().copied(), graph.order());
        let val = tables[child_id].get(&subset).unwrap().val;
        tables[id].insert(
            subset.clone(),
            DpTableEntry::new_intro(val, child_id, subset.clone(), None),
        );

        let has_edge = subset_vec
            .iter()
            .any(|w| graph.has_edge(introduced_vertex, **w));

        let (new_val, node_used) = if has_edge {
            (i32::min_value(), None)
        } else {
            (
                if val == i32::min_value() {
                    i32::min_value()
                } else {
                    val + 1
                },
                Some(introduced_vertex),
            )
        };
        let subset_with_v = immutable_bit_vec_update(&subset, introduced_vertex);
        tables[id].insert(
            subset_with_v,
            DpTableEntry::new_intro(new_val, child_id, subset, node_used),
        );
    }
}