graph_algo_ptas/algorithm/
spantree.rs

1//! Contains implementation of a span tree
2use crate::data_structure::{
3    graph_dcel::GraphDCEL,
4    link_graph::{LinkDart, LinkFace, LinkGraphIter, LinkVertex},
5};
6use std::collections::{HashMap, HashSet, VecDeque};
7
8/// The structure containing the span tree (downwards from root to leaves and upwards from leaf to root)
9pub struct Span<T> {
10    /// Root of the tree
11    pub root: T,
12    /// Maps a node to its children
13    pub downwards: HashMap<T, HashSet<T>>,
14    /// Maps a node to its parents
15    pub upwards: HashMap<T, T>,
16}
17
18impl Span<LinkVertex> {
19    /// Returns a span tree beginning with root
20    pub fn compute(
21        g: &impl GraphDCEL<
22            LinkVertex,
23            LinkDart,
24            LinkFace,
25            LinkGraphIter<LinkVertex>,
26            LinkGraphIter<LinkDart>,
27            LinkGraphIter<LinkFace>,
28        >,
29        root: LinkVertex,
30    ) -> Self {
31        assert!(g.get_vertexes().count() > 1);
32        let mut queue = VecDeque::new();
33        let mut upwards = HashMap::new();
34        let mut downwards = HashMap::new();
35        let mut visited = HashSet::new();
36        downwards.insert(root.clone(), HashSet::new());
37        queue.push_back(root.clone());
38
39        while !queue.is_empty() {
40            let u = queue.pop_front().unwrap();
41            visited.insert(u.clone());
42            for n in g.neighbors(&u) {
43                if visited.insert(n.clone()) {
44                    queue.push_back(n.clone());
45                    upwards.insert(n.clone(), u.clone());
46                    if downwards.get(&u).is_none() {
47                        downwards.insert(u.clone(), HashSet::new());
48                    }
49                    downwards.get_mut(&u).unwrap().insert(n);
50                }
51            }
52        }
53        Span {
54            root,
55            downwards,
56            upwards,
57        }
58    }
59}
60
61#[cfg(test)]
62mod tests {
63    use crate::algorithm::spantree::Span;
64    use crate::data_structure::graph_dcel::GraphDCEL;
65    use crate::data_structure::link_graph::LinkGraph;
66    use crate::embedding::{index::Embedding, maximal_planar::index::MaximalPlanar};
67    use crate::utils::convert::UndirectedGraph;
68    use petgraph::stable_graph::StableGraph;
69    use std::collections::HashMap;
70
71    #[test]
72    #[should_panic]
73    fn single_vertex() {
74        let mut lg = LinkGraph::new();
75        let lv1 = lg.new_vertex();
76
77        let edges = Span::compute(&lg, lv1).upwards;
78
79        println!("[RESULT]: {:?}", edges);
80        assert_eq!(edges, HashMap::new());
81    }
82
83    #[test]
84    fn single_edge() {
85        let mut lg = LinkGraph::new();
86        let lv1 = lg.new_vertex();
87        let lv2 = lg.new_vertex();
88
89        let ld1 = lg.new_dart(lv1.clone(), lv2.clone(), None, None, None, None);
90        let lf = lg.new_face(ld1.clone());
91        lg.new_dart(
92            lv2.clone(),
93            lv1.clone(),
94            Some(ld1.clone()),
95            Some(ld1.clone()),
96            Some(ld1),
97            Some(lf),
98        );
99
100        let edges = Span::compute(&lg, lv1.clone()).upwards;
101
102        println!("[RESULT]: {:?}", edges);
103        assert_eq!(edges.len(), 1);
104        assert_eq!(edges.get(&lv2), Some(&lv1))
105    }
106
107    #[test]
108    fn triangle() {
109        let sg: UndirectedGraph = StableGraph::from_edges(&[(0, 1), (1, 2), (2, 0)]);
110
111        let lg = MaximalPlanar::embed(sg);
112        assert_eq!(lg.vertex_count(), 3);
113        let lv0 = lg.vertex_by_id(0).unwrap();
114        let lv1 = lg.vertex_by_id(1).unwrap();
115        let lv2 = lg.vertex_by_id(2).unwrap();
116
117        let edges = Span::compute(&lg, lv1.clone()).upwards;
118
119        println!("[RESULT]: {:?}", edges);
120        assert_eq!(edges.len(), 2);
121        assert_eq!(edges.get(&lv2), Some(&lv1));
122        assert_eq!(edges.get(&lv0), Some(&lv1));
123    }
124
125    #[test]
126    fn quad() {
127        let sg: UndirectedGraph =
128            StableGraph::from_edges(&[(0, 1), (1, 2), (2, 3), (3, 0), (0, 2), (1, 3)]);
129
130        let lg = MaximalPlanar::embed(sg);
131        assert_eq!(lg.vertex_count(), 4);
132        let lv0 = lg.vertex_by_id(0).unwrap();
133        let lv1 = lg.vertex_by_id(1).unwrap();
134        let lv2 = lg.vertex_by_id(2).unwrap();
135        let lv3 = lg.vertex_by_id(3).unwrap();
136
137        let edges = Span::compute(&lg, lv0.clone()).upwards;
138
139        println!("[RESULT]: {:?}", edges);
140        assert_eq!(edges.len(), 3);
141        assert_eq!(edges.get(&lv2), Some(&lv0));
142        assert_eq!(edges.get(&lv1), Some(&lv0));
143        assert_eq!(edges.get(&lv3), Some(&lv0));
144    }
145}
graph_algo_ptas/algorithm/spantree.rs

graph_algo_ptas/algorithm/
spantree.rs
