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

use std::hash::Hash;
use std::collections::HashSet;

use crate::traversal::{ depth_first, to_adjacency };
use crate::graph::{ HashGraph, Graph };

pub fn components<'a, N: 'a+Clone+Hash+Eq, G: Graph<'a, N>>(
    graph: &'a G
) -> Components<N, G> {
    Components {
        visited: HashSet::new(),
        iter: graph.nodes(),
        graph: graph
    }
}

pub struct Components<'a, N: 'a, G: Graph<'a, N>> {
    visited: HashSet<&'a N>,
    iter: <G as Graph<'a, N>>::NodeIterator,
    graph: &'a G
}

impl<'a, N: Hash+Eq, G: Graph<'a, N>> Iterator for Components<'a, N, G> {
    type Item = HashGraph<&'a N>;

    fn next(&mut self) -> Option<Self::Item> {
        let root = loop {
            match self.iter.next() {
                Some(root) => {
                    if self.visited.contains(root) {
                        continue;
                    } else {
                        break Some(root);
                    }
                },
                None => break None
            }
        };

        match root {
            Some(root) => {
                let traversal = depth_first(self.graph, root).unwrap();
                let adjacency = to_adjacency(traversal).unwrap();
                let subgraph = HashGraph::build(adjacency).unwrap();

                for node in subgraph.nodes() {
                    self.visited.insert(node);
                }

                Some(subgraph)
            },
            None => None
        }
    }
}

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

    #[test]
    fn p1() {
        let graph = IndexGraph::build(vec![
            vec![ ]
        ]).unwrap();
        let components = components(&graph).collect::<Vec<_>>();
        
        assert_eq!(components.len(), 1);
    }

    #[test]
    fn p1_p1() {
        let graph = IndexGraph::build(vec![
            vec![ ],
            vec![ ]
        ]).unwrap();
        let components = components(&graph).collect::<Vec<_>>();

        assert_eq!(components.len(), 2);
    }

    #[test]
    fn p2() {
        let graph = IndexGraph::build(vec![
            vec![ 1 ],
            vec![ 0 ]
        ]).unwrap();
        let components = components(&graph).collect::<Vec<_>>();
        
        assert_eq!(components.len(), 1);
    }

    #[test]
    fn p2_p1() {
        let graph = IndexGraph::build(vec![
            vec![ 1 ],
            vec![ 0 ],
            vec![ ],
        ]).unwrap();
        let components = components(&graph).collect::<Vec<_>>();
        
        assert_eq!(components.len(), 2);
    }

    #[test]
    fn p2_p2_p2() {
        let graph = IndexGraph::build(vec![
            vec![ 1 ],
            vec![ 0 ],
            vec![ 3 ],
            vec![ 2 ],
            vec![ 5 ],
            vec![ 4 ]
        ]).unwrap();
        let components = components(&graph).collect::<Vec<_>>();
        
        assert_eq!(components.len(), 3);
    }
}