graph-algo-ptas 0.1.0

PTAS on planars and other graph classes
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

use crate::data_structure::{
    graph_dcel::GraphDCEL,
    link_graph::{LinkGraph, LinkVertex},
};

pub fn generate_single_face(n: usize) -> LinkGraph {
    assert!(n >= 3);

    let mut lg = LinkGraph::new();
    let nodes: Vec<LinkVertex> = (0..n).map(|_| lg.new_vertex()).collect();

    let mut prev = None;
    let mut prev_twin = None;
    let mut inner_face = None;
    let mut outter_face = None;

    for i in 0..n {
        let node = nodes.get(i % n).unwrap();
        let next = nodes.get((i + 1) % n).unwrap();
        let mut next_dart = None;
        let mut next_dart_twin = None;
        if i == n - 1 {
            let mut dart_iter = lg.get_darts();

            next_dart = dart_iter.next();
            next_dart_twin = dart_iter.next();
        }
        let ld = lg.new_dart(
            node.clone(),
            next.clone(),
            prev.clone(),
            next_dart,
            None,
            inner_face.clone(),
        );
        let lt = lg.new_dart(
            next.clone(),
            node.clone(),
            next_dart_twin,
            prev_twin,
            Some(ld.clone()),
            outter_face.clone(),
        );

        if inner_face.is_none() {
            inner_face = Some(lg.new_face(ld.clone()))
        }
        if outter_face.is_none() {
            outter_face = Some(lg.new_face(lt.clone()))
        }

        prev = Some(ld);
        prev_twin = Some(lt);
    }

    lg
}

#[cfg(test)]
mod tests {
    use super::generate_single_face;
    use crate::data_structure::graph_dcel::GraphDCEL;

    #[test]
    fn test() {
        let n = 10;
        let cg = generate_single_face(n);
        let sv = cg.get_vertexes().next().unwrap();
        let sd = cg.dart_vertex(&sv);
        let mut cd = sd.clone();
        for _i in 0..n - 1 {
            cd = cg.next(&cd);
        }
        let tv = cg.dart_target(&cd);
        assert_eq!(sv, tv);
        cd = sd.clone();
        for _i in 0..n + 1 {
            cd = cg.prev(&cd);
        }
        let tv = cg.dart_target(&cd);
        assert_eq!(sv, tv);
        cd = cg.twin(&sd);
        for _i in 0..n {
            cd = cg.next(&cd);
        }
        let tv = cg.dart_target(&cd);
        assert_eq!(sv, tv);
        cd = cg.twin(&sd);
        for _i in 0..n {
            cd = cg.prev(&cd);
        }
        let tv = cg.dart_target(&cd);
        assert_eq!(sv, tv);
    }

    #[test]
    fn darts() {
        for x in 3..100 {
            let cg = generate_single_face(x);
            assert_eq!(cg.get_darts().count(), x * 2);
        }
    }
}