graph_algo_ptas/algorithm/
tree_decomposition.rs

1//! Contains the tree_decomposition function
2use arboretum_td::tree_decomposition::TreeDecomposition;
3use fxhash::FxHashSet;
4
5use std::collections::{HashMap, HashSet};
6
7use crate::algorithm::spantree::Span;
8use crate::data_structure::{
9    graph_dcel::GraphDCEL,
10    link_graph::{LinkDart, LinkFace, LinkGraphIter, LinkVertex},
11};
12
13fn tree_decomposition(
14    graph: &impl GraphDCEL<
15        LinkVertex,
16        LinkDart,
17        LinkFace,
18        LinkGraphIter<LinkVertex>,
19        LinkGraphIter<LinkDart>,
20        LinkGraphIter<LinkFace>,
21    >,
22    dual_graph: HashMap<LinkFace, HashSet<LinkFace>>,
23    spantree: &Span<LinkVertex>,
24    root_vertex: LinkFace,
25) -> TreeDecomposition {
26    let mut tree: TreeDecomposition = Default::default();
27
28    add_bags(root_vertex, 0, &mut tree, spantree, &dual_graph, graph);
29
30    tree
31}
32
33fn add_bags(
34    vertex: LinkFace,
35    parent: usize,
36    tree: &mut TreeDecomposition,
37    spantree: &Span<LinkVertex>,
38    dual_graph: &HashMap<LinkFace, HashSet<LinkFace>>,
39    graph: &impl GraphDCEL<
40        LinkVertex,
41        LinkDart,
42        LinkFace,
43        LinkGraphIter<LinkVertex>,
44        LinkGraphIter<LinkDart>,
45        LinkGraphIter<LinkFace>,
46    >,
47) {
48    let face_dart = graph.dart_face(&vertex);
49
50    let face_vertices = get_face_vertices(graph, face_dart);
51
52    let bag = create_bag(face_vertices, &spantree);
53
54    if parent == 0 {
55        tree.add_bag(bag);
56    } else {
57        tree.add_child_bags(parent, vec![bag]);
58    }
59
60    for c in dual_graph.get(&vertex).unwrap_or(&HashSet::new()) {
61        add_bags(
62            c.clone(),
63            vertex.get_id(),
64            tree,
65            spantree,
66            dual_graph,
67            graph,
68        );
69    }
70}
71
72fn create_bag(
73    face_vertices: HashSet<LinkVertex>,
74    spantree: &&Span<LinkVertex>,
75) -> FxHashSet<usize> {
76    let mut vertices: FxHashSet<usize> = FxHashSet::default();
77
78    for v in face_vertices {
79        let mut node = v;
80
81        vertices.insert(node.get_id());
82
83        while spantree.upwards.get(&node).is_some() {
84            node = spantree.upwards.get(&node).unwrap().clone();
85            vertices.insert(node.get_id());
86        }
87    }
88    vertices
89}
90
91fn get_face_vertices(
92    graph: &impl GraphDCEL<
93        LinkVertex,
94        LinkDart,
95        LinkFace,
96        LinkGraphIter<LinkVertex>,
97        LinkGraphIter<LinkDart>,
98        LinkGraphIter<LinkFace>,
99    >,
100    mut dart: LinkDart,
101) -> HashSet<LinkVertex> {
102    let mut result: HashSet<LinkVertex> = HashSet::new();
103
104    while result.insert(graph.dart_target(&dart)) {
105        dart = graph.next(&dart);
106    }
107    result
108}
109
110#[cfg(test)]
111mod tests {
112    use crate::algorithm::dualgraph::dual_graph;
113    use crate::algorithm::spantree::Span;
114    use crate::algorithm::tree_decomposition::tree_decomposition;
115    use crate::data_structure::graph_dcel::GraphDCEL;
116    use crate::data_structure::link_graph::LinkGraph;
117    use crate::embedding::{index::Embedding, maximal_planar::index::MaximalPlanar};
118    use crate::utils::convert::UndirectedGraph;
119    use fxhash::FxHashSet;
120    use petgraph::stable_graph::StableGraph;
121
122    #[test]
123    fn single_edge() {
124        let mut lg = LinkGraph::new();
125        let lv1 = lg.new_vertex();
126        let lv2 = lg.new_vertex();
127
128        let ld1 = lg.new_dart(lv1.clone(), lv2.clone(), None, None, None, None);
129        let lf = lg.new_face(ld1.clone());
130        lg.new_dart(
131            lv2.clone(),
132            lv1.clone(),
133            Some(ld1.clone()),
134            Some(ld1.clone()),
135            Some(ld1),
136            Some(lf.clone()),
137        );
138        let span = Span::compute(&lg, lv1.clone());
139        let td = tree_decomposition(&lg, dual_graph(&lg, &span), &span, lf);
140
141        println!("[RESULT]: {:?}", td);
142
143        assert_eq!(td.bags.len(), 1);
144        assert_eq!(td.max_bag_size, 2);
145        assert_eq!(td.bags[0].vertex_set.len(), 2);
146        let mut cb = FxHashSet::default();
147        cb.insert(lv1.get_id());
148        cb.insert(lv2.get_id());
149        assert_eq!(td.bags[0].vertex_set, cb)
150    }
151
152    #[test]
153    fn triangle() {
154        let sg: UndirectedGraph = StableGraph::from_edges(&[(0, 1), (1, 2), (2, 0)]);
155
156        let lg = MaximalPlanar::embed(sg);
157        assert_eq!(lg.vertex_count(), 3);
158        let lv0 = lg.vertex_by_id(0).unwrap();
159        let lv1 = lg.vertex_by_id(1).unwrap();
160        let lv2 = lg.vertex_by_id(2).unwrap();
161        let lof = lg.face(&lg.get_dart(&lv1, &lv0).unwrap());
162
163        let span = Span::compute(&lg, lv1.clone());
164        let td = tree_decomposition(&lg, dual_graph(&lg, &span), &span, lof);
165
166        println!("[RESULT]: {:?}", td);
167
168        assert_eq!(td.bags.len(), 1);
169        assert_eq!(td.max_bag_size, 3);
170        assert_eq!(td.bags[0].vertex_set.len(), 3);
171        let mut cb = FxHashSet::default();
172        cb.insert(lv1.get_id());
173        cb.insert(lv0.get_id());
174        cb.insert(lv2.get_id());
175        assert_eq!(td.bags[0].vertex_set, cb)
176    }
177}
graph_algo_ptas/algorithm/tree_decomposition.rs

graph_algo_ptas/algorithm/
tree_decomposition.rs
