graph_algo_ptas/utils/
single_face.rs

1use crate::data_structure::{
2    graph_dcel::GraphDCEL,
3    link_graph::{LinkGraph, LinkVertex},
4};
5
6pub fn generate_single_face(n: usize) -> LinkGraph {
7    assert!(n >= 3);
8
9    let mut lg = LinkGraph::new();
10    let nodes: Vec<LinkVertex> = (0..n).map(|_| lg.new_vertex()).collect();
11
12    let mut prev = None;
13    let mut prev_twin = None;
14    let mut inner_face = None;
15    let mut outter_face = None;
16
17    for i in 0..n {
18        let node = nodes.get(i % n).unwrap();
19        let next = nodes.get((i + 1) % n).unwrap();
20        let mut next_dart = None;
21        let mut next_dart_twin = None;
22        if i == n - 1 {
23            let mut dart_iter = lg.get_darts();
24
25            next_dart = dart_iter.next();
26            next_dart_twin = dart_iter.next();
27        }
28        let ld = lg.new_dart(
29            node.clone(),
30            next.clone(),
31            prev.clone(),
32            next_dart,
33            None,
34            inner_face.clone(),
35        );
36        let lt = lg.new_dart(
37            next.clone(),
38            node.clone(),
39            next_dart_twin,
40            prev_twin,
41            Some(ld.clone()),
42            outter_face.clone(),
43        );
44
45        if inner_face.is_none() {
46            inner_face = Some(lg.new_face(ld.clone()))
47        }
48        if outter_face.is_none() {
49            outter_face = Some(lg.new_face(lt.clone()))
50        }
51
52        prev = Some(ld);
53        prev_twin = Some(lt);
54    }
55
56    lg
57}
58
59#[cfg(test)]
60mod tests {
61    use super::generate_single_face;
62    use crate::data_structure::graph_dcel::GraphDCEL;
63
64    #[test]
65    fn test() {
66        let n = 10;
67        let cg = generate_single_face(n);
68        let sv = cg.get_vertexes().next().unwrap();
69        let sd = cg.dart_vertex(&sv);
70        let mut cd = sd.clone();
71        for _i in 0..n - 1 {
72            cd = cg.next(&cd);
73        }
74        let tv = cg.dart_target(&cd);
75        assert_eq!(sv, tv);
76        cd = sd.clone();
77        for _i in 0..n + 1 {
78            cd = cg.prev(&cd);
79        }
80        let tv = cg.dart_target(&cd);
81        assert_eq!(sv, tv);
82        cd = cg.twin(&sd);
83        for _i in 0..n {
84            cd = cg.next(&cd);
85        }
86        let tv = cg.dart_target(&cd);
87        assert_eq!(sv, tv);
88        cd = cg.twin(&sd);
89        for _i in 0..n {
90            cd = cg.prev(&cd);
91        }
92        let tv = cg.dart_target(&cd);
93        assert_eq!(sv, tv);
94    }
95
96    #[test]
97    fn darts() {
98        for x in 3..100 {
99            let cg = generate_single_face(x);
100            assert_eq!(cg.get_darts().count(), x * 2);
101        }
102    }
103}
graph_algo_ptas/utils/single_face.rs

graph_algo_ptas/utils/
single_face.rs
