graph_algo_ptas/algorithm/
dualgraph.rs

1//! Contains the dual_graph function
2use crate::algorithm::spantree::Span;
3use crate::data_structure::{
4    graph_dcel::GraphDCEL,
5    link_graph::{LinkDart, LinkFace, LinkGraphIter, LinkVertex},
6};
7use std::collections::{HashMap, HashSet};
8
9/// Returns the dual graph that doesn't cross the edges of the span (face tree)
10pub fn dual_graph(
11    g: &impl GraphDCEL<
12        LinkVertex,
13        LinkDart,
14        LinkFace,
15        LinkGraphIter<LinkVertex>,
16        LinkGraphIter<LinkDart>,
17        LinkGraphIter<LinkFace>,
18    >,
19    span: &Span<LinkVertex>,
20) -> HashMap<LinkFace, HashSet<LinkFace>> {
21    let mut result = HashMap::new();
22    let mut visited = HashSet::new();
23    if g.get_vertexes().count() <= 2 {
24        let outer_face = g.get_faces().next();
25        if let Some(face) = outer_face {
26            result.insert(face, Default::default());
27        }
28        return result;
29    }
30    for face in g.get_faces() {
31        visited.insert(face.clone());
32        let first = g.dart_face(&face);
33        let mut current_dart = first.clone();
34        loop {
35            let next_dart = g.next(&current_dart);
36            if first == next_dart {
37                break;
38            }
39            let next_face = g.face(&g.twin(&current_dart));
40
41            if visited.insert(next_face.clone())
42                && (span.upwards.get(&g.dart_target(&current_dart))
43                    == Some(&g.dart_target(&g.twin(&current_dart)))
44                    || span.upwards.get(&g.dart_target(&g.twin(&current_dart)))
45                        == Some(&g.dart_target(&current_dart)))
46            {
47                match result.get_mut(&face) {
48                    None => {
49                        let mut set = HashSet::new();
50                        set.insert(next_face.clone());
51                        result.insert(face.clone(), set);
52                    }
53                    Some(set) => {
54                        set.insert(next_face.clone());
55                    }
56                }
57            }
58            current_dart = next_dart;
59        }
60    }
61    result
62}
63
64#[allow(dead_code)]
65fn dart_as_tuple(
66    g: &impl GraphDCEL<
67        LinkVertex,
68        LinkDart,
69        LinkFace,
70        LinkGraphIter<LinkVertex>,
71        LinkGraphIter<LinkDart>,
72        LinkGraphIter<LinkFace>,
73    >,
74    d: &LinkDart,
75) -> (LinkVertex, LinkVertex) {
76    (g.dart_target(d), g.dart_target(&g.twin(d)))
77}
78
79#[cfg(test)]
80mod tests {
81    use crate::algorithm::dualgraph::dual_graph;
82    use crate::algorithm::spantree::Span;
83    use crate::data_structure::graph_dcel::GraphDCEL;
84    use crate::data_structure::link_graph::LinkGraph;
85    use crate::embedding::{index::Embedding, maximal_planar::index::MaximalPlanar};
86    use crate::utils::convert::UndirectedGraph;
87    use petgraph::stable_graph::StableGraph;
88    use std::collections::HashSet;
89
90    #[test]
91    fn single_edge() {
92        let mut lg = LinkGraph::new();
93        let lv1 = lg.new_vertex();
94        let lv2 = lg.new_vertex();
95
96        let ld1 = lg.new_dart(lv1.clone(), lv2.clone(), None, None, None, None);
97        let lf = lg.new_face(ld1.clone());
98        lg.new_dart(
99            lv2,
100            lv1.clone(),
101            Some(ld1.clone()),
102            Some(ld1.clone()),
103            Some(ld1),
104            Some(lf.clone()),
105        );
106
107        let span = Span::compute(&lg, lv1);
108        let dual = dual_graph(&lg, &span);
109
110        println!("[RESULT]: {:?}", dual);
111        assert_eq!(dual.len(), 1);
112        assert_eq!(dual.get(&lf), Some(&HashSet::new()));
113    }
114
115    #[test]
116    fn triangle() {
117        let sg: UndirectedGraph = StableGraph::from_edges(&[(0, 1), (1, 2), (2, 0)]);
118
119        let lg = MaximalPlanar::embed(sg);
120        assert_eq!(lg.vertex_count(), 3);
121        let lv0 = lg.vertex_by_id(0).unwrap();
122        let lv1 = lg.vertex_by_id(1).unwrap();
123        let ld1 = lg.get_dart(&lv1, &lv0).unwrap();
124        let lf = lg.face(&ld1);
125        let lof = lg.face(&lg.twin(&ld1));
126
127        let span = Span::compute(&lg, lv1);
128        let dual = dual_graph(&lg, &span);
129
130        println!("[RESULT]: {:?}", dual);
131        assert_eq!(dual.len(), 1);
132        assert!(dual.get(&lof).unwrap_or(&HashSet::new()).contains(&lf));
133    }
134}
graph_algo_ptas/algorithm/dualgraph.rs

graph_algo_ptas/algorithm/
dualgraph.rs
