graph_algo_ptas/algorithm/
nice_tree_decomposition.rs

1//! Contains a data structure for nice tree decompositions and an algorithm to generate them.
2
3use arboretum_td::tree_decomposition::TreeDecomposition;
4use fxhash::FxHashSet;
5
6/// Represents one of the four possible node types of a nice tree decomposition.
7#[derive(Debug, Clone, Copy, Eq, PartialEq)]
8pub enum NiceTdNodeType {
9    /// Join node
10    Join,
11    /// Introduce node (with introduced vertex)
12    Introduce(usize),
13    /// Forget node (with forgotten vertex)
14    Forget(usize),
15    /// Leaf
16    Leaf,
17}
18
19/// Represents a nice tree decomposition.
20///
21/// In a nice tree decomposition, each node is either a Leaf, Join, Forget or Introduce node.
22pub struct NiceTreeDecomposition {
23    /// Is guaranteed to have the properties of a nice tree decomposition.
24    pub td: TreeDecomposition,
25    /// Maps nodes to their `NiceTdNodeType`.
26    pub mapping: Vec<NiceTdNodeType>,
27}
28
29impl NiceTreeDecomposition {
30    /// Create a nice tree decomposition.
31    pub fn new(mut td: TreeDecomposition) -> Self {
32        let root = td.root.unwrap_or(0);
33        td.root = Some(root);
34
35        Self::nicify_multi_child_nodes(root, &td.bags()[root].neighbors.clone(), &mut td);
36        Self::nicify_double_child_nodes(root, &td.bags()[root].neighbors.clone(), &mut td);
37        Self::nicify_single_child_nodes(root, &td.bags()[root].neighbors.clone(), &mut td);
38        Self::nicify_leaf_nodes(root, &td.bags()[root].neighbors.clone(), &mut td);
39
40        let mut mapping: Vec<Option<NiceTdNodeType>> = vec![None; td.bags().len()];
41
42        assert!(Self::is_nice_td(
43            &td,
44            root,
45            &td.bags()[root].neighbors.clone(),
46            &mut mapping
47        ));
48        assert!(mapping.iter().all(|node_type| { node_type.is_some() }));
49
50        Self {
51            td: td.to_owned(),
52            mapping: mapping.iter().map(|node_type| node_type.unwrap()).collect(),
53        }
54    }
55
56    fn nicify_multi_child_nodes(
57        id: usize,
58        children: &FxHashSet<usize>,
59        td: &mut TreeDecomposition,
60    ) {
61        if children.len() <= 2 {
62            for child_id in children {
63                Self::nicify_multi_child_nodes(*child_id, &get_children(td, *child_id, id), td);
64            }
65
66            return;
67        }
68
69        let vertex_set: FxHashSet<usize> = td.bags()[id].vertex_set.clone();
70        let left_child_id = td.add_bag(vertex_set);
71        td.add_edge(id, left_child_id);
72        let mut it = children.iter();
73        let right_child_id = *it.next().unwrap();
74
75        for child_id in it {
76            Self::remove_edge(td, id, *child_id);
77            td.add_edge(left_child_id, *child_id);
78        }
79
80        Self::nicify_multi_child_nodes(left_child_id, &get_children(td, left_child_id, id), td);
81
82        Self::nicify_multi_child_nodes(right_child_id, &get_children(td, right_child_id, id), td);
83    }
84
85    fn nicify_double_child_nodes(
86        id: usize,
87        children: &FxHashSet<usize>,
88        td: &mut TreeDecomposition,
89    ) {
90        if children.len() != 2 {
91            for child_id in children {
92                Self::nicify_double_child_nodes(*child_id, &get_children(td, *child_id, id), td);
93            }
94
95            return;
96        }
97
98        let mut it = children.iter();
99        let left_child_id = *it.next().unwrap();
100        let right_child_id = *it.next().unwrap();
101        let vertex_set: FxHashSet<usize> = td.bags()[id].vertex_set.clone();
102        let new_left_child_id = td.add_bag(vertex_set.clone());
103        let new_right_child_id = td.add_bag(vertex_set);
104
105        Self::remove_edge(td, id, left_child_id);
106        Self::remove_edge(td, id, right_child_id);
107        td.add_edge(id, new_left_child_id);
108        td.add_edge(id, new_right_child_id);
109        td.add_edge(new_left_child_id, left_child_id);
110        td.add_edge(new_right_child_id, right_child_id);
111
112        Self::nicify_double_child_nodes(
113            left_child_id,
114            &get_children(td, left_child_id, new_left_child_id),
115            td,
116        );
117
118        Self::nicify_double_child_nodes(
119            right_child_id,
120            &get_children(td, right_child_id, new_right_child_id),
121            td,
122        );
123    }
124
125    fn nicify_single_child_nodes(
126        id: usize,
127        children: &FxHashSet<usize>,
128        td: &mut TreeDecomposition,
129    ) {
130        if children.len() != 1 {
131            for child_id in children {
132                Self::nicify_single_child_nodes(*child_id, &get_children(td, *child_id, id), td);
133            }
134
135            return;
136        }
137
138        let mut vertex_set: FxHashSet<usize> = td.bags()[id].vertex_set.clone();
139        let child_id = *children.iter().next().unwrap();
140        let child_vertex_set: FxHashSet<usize> = td.bags()[child_id].vertex_set.clone();
141
142        if vertex_set.eq(&child_vertex_set.clone()) {
143            Self::remove_edge(td, id, child_id);
144
145            for grandchild_id in get_children(td, child_id, id) {
146                td.add_edge(id, grandchild_id);
147                Self::remove_edge(td, child_id, grandchild_id);
148                Self::nicify_single_child_nodes(
149                    grandchild_id,
150                    &get_children(td, grandchild_id, id),
151                    td,
152                );
153            }
154
155            Self::remove_bag(td, child_id);
156
157            return;
158        }
159
160        let mut parent_id = id;
161
162        for v in vertex_set.clone().difference(&child_vertex_set) {
163            vertex_set.remove(v);
164
165            if vertex_set.eq(&child_vertex_set) {
166                break;
167            }
168
169            let new_child_id = td.add_bag(vertex_set.clone());
170            Self::remove_edge(td, parent_id, child_id);
171            td.add_edge(parent_id, new_child_id);
172            td.add_edge(new_child_id, child_id);
173            parent_id = new_child_id;
174        }
175
176        for v in child_vertex_set.difference(&vertex_set.clone()) {
177            vertex_set.insert(*v);
178
179            if vertex_set.eq(&child_vertex_set) {
180                break;
181            }
182
183            let new_child_id = td.add_bag(vertex_set.clone());
184            Self::remove_edge(td, parent_id, child_id);
185            td.add_edge(parent_id, new_child_id);
186            td.add_edge(new_child_id, child_id);
187            parent_id = new_child_id;
188        }
189
190        Self::nicify_single_child_nodes(child_id, &get_children(td, child_id, parent_id), td);
191    }
192
193    fn nicify_leaf_nodes(id: usize, children: &FxHashSet<usize>, td: &mut TreeDecomposition) {
194        if !children.is_empty() {
195            for child_id in children {
196                Self::nicify_leaf_nodes(*child_id, &get_children(td, *child_id, id), td);
197            }
198
199            return;
200        }
201
202        let bag = &td.bags()[id];
203        let mut vertex_set = bag.vertex_set.clone();
204        let mut parent_id = id;
205
206        while vertex_set.len() > 1 {
207            let v = *vertex_set.iter().next().unwrap();
208            vertex_set.remove(&v);
209            let new_child_id = td.add_bag(vertex_set.clone());
210            td.add_edge(parent_id, new_child_id);
211            parent_id = new_child_id;
212        }
213    }
214
215    fn is_nice_td(
216        td: &TreeDecomposition,
217        id: usize,
218        children: &FxHashSet<usize>,
219        mapping: &mut Vec<Option<NiceTdNodeType>>,
220    ) -> bool {
221        match Self::get_nice_td_node_type(td, id, children) {
222            Some(node_type) => {
223                mapping[id] = Some(node_type);
224                children.iter().all(|child_id| {
225                    Self::is_nice_td(td, *child_id, &get_children(td, *child_id, id), mapping)
226                })
227            }
228            None => false,
229        }
230    }
231
232    fn get_nice_td_node_type(
233        td: &TreeDecomposition,
234        id: usize,
235        children: &FxHashSet<usize>,
236    ) -> Option<NiceTdNodeType> {
237        if Self::is_nice_td_join(td, id, children) {
238            return Some(NiceTdNodeType::Join);
239        } else if let Some(v) = Self::is_nice_td_intro(td, id, children) {
240            return Some(NiceTdNodeType::Introduce(v));
241        } else if let Some(v) = Self::is_nice_td_forget(td, id, children) {
242            return Some(NiceTdNodeType::Forget(v));
243        } else if Self::is_nice_td_leaf(td, id, children) {
244            return Some(NiceTdNodeType::Leaf);
245        }
246
247        None
248    }
249
250    fn is_nice_td_join(td: &TreeDecomposition, id: usize, children: &FxHashSet<usize>) -> bool {
251        let mut it = children.iter();
252        let left = it.next();
253        let right = it.next();
254        let none = it.next();
255
256        match (left, right, none) {
257            (Some(left), Some(right), None) => {
258                let vertex_set: &FxHashSet<usize> = &td.bags()[id].vertex_set;
259                let left_vertex_set: &FxHashSet<usize> = &td.bags()[*left].vertex_set;
260                let right_vertex_set: &FxHashSet<usize> = &td.bags()[*right].vertex_set;
261                vertex_set == left_vertex_set && vertex_set == right_vertex_set
262            }
263            _ => false,
264        }
265    }
266
267    fn is_nice_td_intro(
268        td: &TreeDecomposition,
269        id: usize,
270        children: &FxHashSet<usize>,
271    ) -> Option<usize> {
272        let mut it = children.iter();
273        let child = it.next();
274        let none = it.next();
275
276        match (child, none) {
277            (Some(child), None) => {
278                let vertex_set: &FxHashSet<usize> = &td.bags()[id].vertex_set;
279                let child_vertex_set: &FxHashSet<usize> = &td.bags()[*child].vertex_set;
280
281                if !vertex_set.is_superset(child_vertex_set)
282                    || vertex_set.len() != child_vertex_set.len() + 1
283                {
284                    return None;
285                }
286
287                Some(*vertex_set.difference(child_vertex_set).next().unwrap())
288            }
289            _ => None,
290        }
291    }
292
293    fn is_nice_td_forget(
294        td: &TreeDecomposition,
295        id: usize,
296        children: &FxHashSet<usize>,
297    ) -> Option<usize> {
298        let mut it = children.iter();
299        let child = it.next();
300
301        if it.next().is_some() {
302            return None;
303        }
304
305        match child {
306            Some(child) => {
307                let vertex_set: &FxHashSet<usize> = &td.bags()[id].vertex_set;
308                let child_vertex_set: &FxHashSet<usize> = &td.bags()[*child].vertex_set;
309
310                if !vertex_set.is_subset(child_vertex_set)
311                    || vertex_set.len() + 1 != child_vertex_set.len()
312                {
313                    return None;
314                }
315
316                Some(*child_vertex_set.difference(vertex_set).next().unwrap())
317            }
318            None => None,
319        }
320    }
321
322    fn is_nice_td_leaf(td: &TreeDecomposition, id: usize, children: &FxHashSet<usize>) -> bool {
323        let vertex_set = &td.bags()[id].vertex_set;
324
325        children.is_empty() && vertex_set.len() == 1
326    }
327
328    fn remove_edge(td: &mut TreeDecomposition, b1: usize, b2: usize) {
329        assert!(b1 < td.bags.len());
330        assert!(b2 < td.bags.len());
331        assert_ne!(b1, b2);
332        td.bags[b1].neighbors.remove(&b2);
333        td.bags[b2].neighbors.remove(&b1);
334    }
335
336    // taken from https://github.com/jmeintrup/arboretum/blob/master/src/tree_decomposition.rs
337    fn remove_bag(td: &mut TreeDecomposition, id: usize) {
338        assert!(td.bags[id].neighbors.is_empty());
339        if id == td.bags.len() - 1 {
340            td.bags.pop();
341        } else {
342            let old_last = td.bags.swap_remove(id);
343            assert!(old_last.neighbors.is_empty());
344            td.bags[id].id = id;
345            let old_last = td.bags.len();
346
347            for neighbor in td.bags[id].neighbors.clone() {
348                assert!(td.bags[neighbor].neighbors.remove(&old_last));
349                assert!(td.bags[neighbor].neighbors.insert(id));
350            }
351        }
352    }
353}
354
355/// Return the children of a bag (children = neighbors \ {parent_id}).
356pub fn get_children(td: &TreeDecomposition, id: usize, parent_id: usize) -> FxHashSet<usize> {
357    let mut children = td.bags()[id].neighbors.clone();
358    children.remove(&parent_id);
359
360    children
361}
362
363#[cfg(test)]
364mod tests {
365    use super::NiceTreeDecomposition;
366    use crate::{
367        algorithm::nice_tree_decomposition::get_children,
368        generation::erdos_renyi::generate_hash_map_graph,
369    };
370    use arboretum_td::{solver::Solver, tree_decomposition::TreeDecomposition};
371    use fxhash::FxHashSet;
372    use rand::{rngs::StdRng, Rng, SeedableRng};
373
374    #[test]
375    fn single_bag_with_1_vertex() {
376        let mut td = TreeDecomposition::default();
377        let mut vertex_set = FxHashSet::default();
378        vertex_set.insert(1);
379        td.add_bag(vertex_set);
380
381        let nice_td = NiceTreeDecomposition::new(td.clone());
382        assert!(nice_td.td.bags().len() == td.bags().len());
383        assert!(nice_td.td.bags()[0].vertex_set == td.bags()[0].vertex_set);
384    }
385
386    #[test]
387    fn single_bag_with_multiple_vertices() {
388        let mut td = TreeDecomposition::default();
389        let mut vertex_set = FxHashSet::default();
390        vertex_set.insert(1);
391        vertex_set.insert(2);
392        vertex_set.insert(3);
393        let id = td.add_bag(vertex_set);
394
395        let nice_td = NiceTreeDecomposition::new(td.clone());
396        let bag = &nice_td.td.bags()[id];
397        let child_id = *bag.neighbors.iter().next().unwrap();
398        let grandchild_id = get_child_bag_id(&nice_td.td, child_id, id).unwrap();
399
400        assert!(nice_td.td.bags().len() == 3);
401        assert!(bag.vertex_set.len() == 3);
402        assert!(
403            NiceTreeDecomposition::is_nice_td_intro(&nice_td.td, id, &bag.neighbors.clone())
404                .is_some()
405        );
406        assert!(NiceTreeDecomposition::is_nice_td_intro(
407            &nice_td.td,
408            child_id,
409            &get_children(&nice_td.td, child_id, id)
410        )
411        .is_some());
412        assert!(NiceTreeDecomposition::is_nice_td_leaf(
413            &nice_td.td,
414            grandchild_id,
415            &get_children(&nice_td.td, grandchild_id, child_id)
416        ));
417    }
418
419    #[test]
420    fn two_bags_with_multiple_vertices() {
421        let mut td = TreeDecomposition::default();
422        let mut vertex_set_1 = FxHashSet::default();
423        vertex_set_1.insert(1);
424        vertex_set_1.insert(2);
425        let mut vertex_set_2 = FxHashSet::default();
426        vertex_set_2.insert(2);
427        vertex_set_2.insert(3);
428
429        let id_1 = td.add_bag(vertex_set_1);
430        let id_2 = td.add_bag(vertex_set_2);
431        td.add_edge(id_1, id_2);
432
433        let nice_td = NiceTreeDecomposition::new(td.clone());
434        let bag = &nice_td.td.bags()[id_1];
435        let child_id = *bag.neighbors.iter().next().unwrap();
436        let grandchild_id = get_child_bag_id(&nice_td.td, child_id, id_1).unwrap();
437        let grandgrandchild_id = get_child_bag_id(&nice_td.td, grandchild_id, child_id).unwrap();
438
439        assert!(nice_td.td.bags().len() == 4);
440        assert_eq!(
441            NiceTreeDecomposition::is_nice_td_intro(&nice_td.td, id_1, &bag.neighbors.clone()),
442            Some(1)
443        );
444        assert_eq!(
445            NiceTreeDecomposition::is_nice_td_forget(
446                &nice_td.td,
447                child_id,
448                &get_children(&nice_td.td, child_id, id_1)
449            ),
450            Some(3)
451        );
452        assert!(NiceTreeDecomposition::is_nice_td_intro(
453            &nice_td.td,
454            grandchild_id,
455            &get_children(&nice_td.td, grandchild_id, child_id)
456        )
457        .is_some());
458        assert!(NiceTreeDecomposition::is_nice_td_leaf(
459            &nice_td.td,
460            grandgrandchild_id,
461            &get_children(&nice_td.td, grandgrandchild_id, grandchild_id)
462        ));
463    }
464
465    #[test]
466    fn random() {
467        let mut rng = StdRng::seed_from_u64(1);
468
469        for i in 0..100 {
470            let graph = generate_hash_map_graph(
471                rng.gen_range(1..30),
472                rng.gen_range(0.05..0.1),
473                Some(i as u64),
474            );
475            let td = Solver::default().solve(&graph);
476            let nice_td = NiceTreeDecomposition::new(td);
477            assert!(nice_td.td.verify(&graph).is_ok());
478        }
479    }
480
481    fn get_child_bag_id(td: &TreeDecomposition, id: usize, parent_id: usize) -> Option<usize> {
482        get_children(td, id, parent_id).iter().copied().next()
483    }
484}
graph_algo_ptas/algorithm/nice_tree_decomposition.rs

graph_algo_ptas/algorithm/
nice_tree_decomposition.rs
