gamma 0.9.0

Graph primitives and traversals for Rust.
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145

use std::collections::{ HashMap, HashSet };
use std::collections::hash_map::Entry::{ Occupied, Vacant };

pub struct Marker {
    nodes: HashSet<usize>,
    edges: HashMap<usize, Vec<usize>>
}

impl Marker {
    pub fn new() -> Self {
        Self {
            nodes: HashSet::new(),
            edges: HashMap::new()
        }
    }

    pub fn mark_node(&mut self, id: usize) {
        if !self.nodes.insert(id) {
            panic!("node marked twice: {}", id)
        }
    }

    pub fn has_node(&self, id: usize) -> bool {
        self.nodes.contains(&id)
    }

    pub fn mark_edge(&mut self, sid: usize, tid: usize) {
        match self.edges.entry(sid) {
            Occupied(mut entry) => {
                if entry.get().contains(&tid) {
                    panic!("edge marked twice: ({},{})", sid, tid)
                } else {
                    entry.get_mut().push(tid)
                }
            },
            Vacant(entry) => {
                entry.insert(vec![ tid ]);
            }
        }

        match self.edges.entry(tid) {
            Occupied(mut entry) => {
                entry.get_mut().push(sid)
            },
            Vacant(entry) => {
                entry.insert(vec![ sid ]);
            }
        }
    }

    pub fn has_edge(&self, sid: usize, tid: usize) -> bool {
        match self.edges.get(&sid) {
            None => false,
            Some(neighbors) => neighbors.contains(&tid)
        }
    }
}

#[cfg(test)]
mod mark_node {
    use super::*;

    #[test]
    #[should_panic(expected="node marked twice: 0")]
    fn duplicate() {
        let mut marker = Marker::new();

        marker.mark_node(0);
        marker.mark_node(0);
    }
}

#[cfg(test)]
mod mark_edge {
    use super::*;

    #[test]
    #[should_panic(expected="edge marked twice: (0,1)")]
    fn duplicate() {
        let mut marker = Marker::new();

        marker.mark_edge(0, 1);
        marker.mark_edge(0, 1);
    }

    #[test]
    #[should_panic(expected="edge marked twice: (1,0)")]
    fn duplicate_reverse() {
        let mut marker = Marker::new();

        marker.mark_edge(0, 1);
        marker.mark_edge(1, 0);
    }
}

#[cfg(test)]
mod has_node {
    use super::*;

    #[test]
    fn outside() {
        let marker = Marker::new();

        assert_eq!(marker.has_node(0), false)
    }

    #[test]
    fn inside() {
        let mut marker = Marker::new();

        marker.mark_node(0);

        assert_eq!(marker.has_node(0), true)
    }
}

#[cfg(test)]
mod has_edge {
    use super::*;

    #[test]
    fn outside() {
        let marker = Marker::new();

        assert_eq!(marker.has_edge(0, 1), false);
    }

    #[test]
    fn inside() {
        let mut marker = Marker::new();

        marker.mark_edge(0, 1);

        assert_eq!(marker.has_edge(0, 1), true);
    }

    #[test]
    fn inside_reverse() {
        let mut marker = Marker::new();

        marker.mark_edge(0, 1);

        assert_eq!(marker.has_edge(1, 0), true);
    }
}