gamma 0.5.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

use std::hash::Hash;
use std::collections::HashMap;

use crate::graph::Error;
use super::Step;

/// Returns an adjacency map given the result of a traversal represented
/// as an iterable sequence of Steps.
pub fn to_adjacency<N, I> (
    traversal: I
) -> Result<HashMap<N, Vec<N>>, Error>
where N: Hash+Eq+Clone, I: IntoIterator<Item=Step<N>> {
    let mut result = HashMap::new();

    for step in traversal {
        if result.is_empty() {
            result.insert(step.source.clone(), vec![ step.target.clone() ]);
            result.insert(step.target, vec![ step.source ]);
        } else {
            match result.get_mut(&step.source) {
                Some(targets) => {
                    targets.push(step.target.clone());
                },
                None => return Err(Error::UnknownNode)
            }

            if step.cut {
                match result.get_mut(&step.target) {
                    Some(targets) => {
                        targets.push(step.source);
                    },
                    None => return Err(Error::UnknownNode)
                }
            } else {
                result.insert(step.target, vec![ step.source.clone() ]);
            }
        }
    }

    Ok(result)
}

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

    macro_rules! map(
        { $($key:expr => $value:expr),+ } => {
            {
                let mut m = ::std::collections::HashMap::new();
                $(
                    m.insert($key, $value);
                )+
                m
            }
         };
    );

    #[test]
    fn empty() {
        let steps: Vec<Step<()>> = vec![ ];
        let result = to_adjacency(steps).unwrap();

        assert_eq!(result.is_empty(), true);
    }

    #[test]
    fn p2() {
        let edges = vec![
            Step::new(0, 1, false)
        ];
        let result = to_adjacency(edges).unwrap();

        assert_eq!(result, map!{
            0 => vec![ 1 ],
            1 => vec![ 0 ]
        });
    }

    #[test]
    fn p3() {
        let edges = vec![
            Step::new(0, 1, false),
            Step::new(1, 2, false)
        ];
        let result = to_adjacency(edges).unwrap();

        assert_eq!(result, map!{
            0 => vec![ 1 ],
            1 => vec![ 0, 2 ],
            2 => vec![ 1 ]
        });
    }

    #[test]
    fn c3() {
        let edges = vec![
            Step::new(0, 1, false),
            Step::new(1, 2, false),
            Step::new(2, 0, true)
        ];
        let result = to_adjacency(edges).unwrap();

        assert_eq!(result, map!{
            0 => vec![ 1, 2 ],
            1 => vec![ 0, 2 ],
            2 => vec![ 1, 0 ]
        });
    }

    #[test]
    fn s3() {
        let edges = vec![
            Step::new(0, 1, false),
            Step::new(1, 2, false),
            Step::new(1, 3, false)
        ].into_iter();
        let result = to_adjacency(edges).unwrap();

        assert_eq!(result, map!{
            0 => vec![ 1 ],
            1 => vec![ 0, 2, 3 ],
            2 => vec![ 1 ],
            3 => vec![ 1 ]
        });
    }
}