graph_rs/
vec.rs

1use self::super::DirectedWeightedGraph;
2use std::slice::{Iter, IterMut};
3
4impl<'g, N, W> DirectedWeightedGraph<'g, N, W> for Vec<(N, N, W)>
5where
6    N: Eq + 'g,
7    W: 'g,
8{
9    type AllWeightedEdges = AllWeightedEdges<'g, N, W>;
10    type AllWeightedEdgesMut = AllWeightedEdgesMut<'g, N, W>;
11
12    fn all_edges(&'g self) -> Self::AllWeightedEdges {
13        AllWeightedEdges { iter: self.iter() }
14    }
15
16    fn all_edges_mut(&'g mut self) -> Self::AllWeightedEdgesMut {
17        AllWeightedEdgesMut {
18            iter: self.iter_mut(),
19        }
20    }
21
22    /// Adds an edge to the graph.
23    ///
24    /// # Complexity
25    /// This implementation runs in O(|E|) time. Running in linear time would risk this graph of
26    /// becoming a multigraph, where there can be multiple edges between the same nodes.
27    fn add_edge(&'g mut self, source: N, sink: N, weight: W) -> Option<(N, N, W)> {
28        if let Some(old_weight) = self.edge_weight_mut(&source, &sink) {
29            return Some((source, sink, ::std::mem::replace(old_weight, weight)));
30        }
31
32        self.push((source, sink, weight));
33        None
34    }
35
36    fn remove_edge(&'g mut self, source: &N, sink: &N) -> Option<(N, N, W)> {
37        for index in 0..self.len() {
38            {
39                let &(ref current_source, ref current_sink, _) = &self[index];
40                if current_source != source || current_sink != sink {
41                    continue;
42                }
43            }
44            return Some(self.remove(index));
45        }
46
47        None
48    }
49}
50
51#[derive(Debug, Clone)]
52pub struct AllWeightedEdges<'g, N, W>
53where
54    N: 'g,
55    W: 'g,
56{
57    iter: Iter<'g, (N, N, W)>,
58}
59
60impl<'g, N, W> Iterator for AllWeightedEdges<'g, N, W> {
61    type Item = (&'g N, &'g N, &'g W);
62
63    fn next(&mut self) -> Option<Self::Item> {
64        self.iter
65            .next()
66            .map(|&(ref source, ref sink, ref weight)| (source, sink, weight))
67    }
68
69    fn size_hint(&self) -> (usize, Option<usize>) {
70        self.iter.size_hint()
71    }
72}
73
74impl<'g, N, W> ExactSizeIterator for AllWeightedEdges<'g, N, W> {
75    fn len(&self) -> usize {
76        self.iter.len()
77    }
78}
79
80#[derive(Debug)]
81pub struct AllWeightedEdgesMut<'g, N, W>
82where
83    N: 'g,
84    W: 'g,
85{
86    iter: IterMut<'g, (N, N, W)>,
87}
88
89impl<'g, N, W> Iterator for AllWeightedEdgesMut<'g, N, W> {
90    type Item = (&'g N, &'g N, &'g mut W);
91
92    fn next(&mut self) -> Option<Self::Item> {
93        self.iter
94            .next()
95            .map(|&mut (ref source, ref sink, ref mut weight)| {
96                (source, sink, weight)
97            })
98    }
99
100    fn size_hint(&self) -> (usize, Option<usize>) {
101        self.iter.size_hint()
102    }
103}
104
105#[cfg(test)]
106mod tests {
107    use DirectedWeightedGraph;
108
109    #[test]
110    fn test_add_edge() {
111        let mut graph = Vec::new();
112
113        graph.add_edge(0, 1, 1.0);
114        graph.add_edge(1, 1, 2.0);
115        graph.add_edge(1, 2, 3.0);
116
117        assert!(graph.has_edge(&0, &1));
118        assert!(graph.has_edge(&1, &1));
119        assert!(graph.has_edge(&1, &2));
120        assert!(!graph.has_edge(&0, &0));
121        assert!(!graph.has_edge(&0, &2));
122        assert!(!graph.has_edge(&1, &0));
123        assert!(!graph.has_edge(&1, &4));
124
125        assert_eq!(graph.edge_weight(&0, &1), Some(&1.0));
126        assert_eq!(graph.edge_weight(&1, &1), Some(&2.0));
127        assert_eq!(graph.edge_weight(&1, &2), Some(&3.0));
128
129        assert_eq!(graph.all_edges().len(), 3);
130    }
131}
graph_rs/vec.rs

graph_rs/
vec.rs
