Merge pull request #237 from manuelmauro/master
Implement an edges_connecting(a, b) iterator for Graph
diff --git a/src/algo/dominators.rs b/src/algo/dominators.rs
index e6b22f4..5cbf281 100644
--- a/src/algo/dominators.rs
+++ b/src/algo/dominators.rs
@@ -46,7 +46,7 @@
}
}
- /// Iterate over the given node's that strict dominators.
+ /// Iterate over the given node's strict dominators.
///
/// If the given node is not reachable from the root, then `None` is
/// returned.
diff --git a/src/graph_impl/mod.rs b/src/graph_impl/mod.rs
index 43bea08..1e8d1d6 100644
--- a/src/graph_impl/mod.rs
+++ b/src/graph_impl/mod.rs
@@ -851,6 +851,21 @@
}
}
+ /// Return an iterator over all the edges connecting `a` and `b`.
+ ///
+ /// - `Directed`: Outgoing edges from `a`.
+ /// - `Undirected`: All edges connected to `a`.
+ ///
+ /// Iterator element type is `EdgeReference<E, Ix>`.
+ pub fn edges_connecting(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> EdgesConnecting<E, Ty, Ix>
+ {
+ EdgesConnecting {
+ target_node: b,
+ edges: self.edges_directed(a, Direction::Outgoing),
+ ty: PhantomData,
+ }
+ }
+
/// Lookup if there is an edge from `a` to `b`.
///
/// Computes in **O(e')** time, where **e'** is the number of edges
@@ -1281,7 +1296,7 @@
weight: node_map(NodeIndex::new(i), &node.weight),
next: node.next,
}));
- g.edges.extend(enumerate(&self.edges).map(|(i, edge)|
+ g.edges.extend(enumerate(&self.edges).map(|(i, edge)|
Edge {
weight: edge_map(EdgeIndex::new(i), &edge.weight),
next: edge.next,
@@ -1600,6 +1615,34 @@
}
}
+/// Iterator over the multiple directed edges connecting a source node to a target node
+pub struct EdgesConnecting<'a, E: 'a, Ty, Ix: 'a = DefaultIx>
+ where Ty: EdgeType,
+ Ix: IndexType,
+{
+ target_node: NodeIndex<Ix>,
+ edges: Edges<'a, E, Ty, Ix>,
+ ty: PhantomData<Ty>,
+}
+
+impl<'a, E, Ty, Ix> Iterator for EdgesConnecting<'a, E, Ty, Ix>
+ where Ty: EdgeType,
+ Ix: IndexType,
+{
+ type Item = EdgeReference<'a, E, Ix>;
+
+ fn next(&mut self) -> Option<EdgeReference<'a, E, Ix>> {
+ while let Some(edge) = self.edges.next() {
+ if edge.node[1] == self.target_node {
+ return Some(edge);
+ }
+ }
+
+ None
+ }
+}
+
+
fn swap_pair<T>(mut x: [T; 2]) -> [T; 2] {
x.swap(0, 1);
x
@@ -1937,7 +1980,7 @@
type Item = (NodeIndex<Ix>, &'a N);
fn next(&mut self) -> Option<Self::Item> {
- self.iter.next().map(|(i, node)|
+ self.iter.next().map(|(i, node)|
(node_index(i), &node.weight)
)
}
@@ -1996,7 +2039,7 @@
type Item = EdgeReference<'a, E, Ix>;
fn next(&mut self) -> Option<Self::Item> {
- self.iter.next().map(|(i, edge)|
+ self.iter.next().map(|(i, edge)|
EdgeReference {
index: edge_index(i),
node: edge.node,
@@ -2044,4 +2087,3 @@
/// See indexing implementations and the traits `Data` and `DataMap`
/// for read-write access to the graph's weights.
pub struct Frozen<'a, G: 'a>(&'a mut G);
-
diff --git a/tests/graph.rs b/tests/graph.rs
index 2dceb1a..8bdc077 100644
--- a/tests/graph.rs
+++ b/tests/graph.rs
@@ -283,6 +283,71 @@
assert_eq!(gr.edge_count(), 2);
}
+
+#[test]
+fn iter_multi_edges() {
+ let mut gr = Graph::new();
+ let a = gr.add_node("a");
+ let b = gr.add_node("b");
+ let c = gr.add_node("c");
+
+ let mut connecting_edges = HashSet::new();
+
+ gr.add_edge(a, a, ());
+ connecting_edges.insert(gr.add_edge(a, b, ()));
+ gr.add_edge(a, c, ());
+ gr.add_edge(c, b, ());
+ connecting_edges.insert(gr.add_edge(a, b, ()));
+ gr.add_edge(b, a, ());
+
+ let mut iter = gr.edges_connecting(a, b);
+
+ let edge_id = iter.next().unwrap().id();
+ assert!(connecting_edges.contains(&edge_id));
+ connecting_edges.remove(&edge_id);
+
+ let edge_id = iter.next().unwrap().id();
+ assert!(connecting_edges.contains(&edge_id));
+ connecting_edges.remove(&edge_id);
+
+ assert_eq!(None, iter.next());
+ assert!(connecting_edges.is_empty());
+}
+
+#[test]
+fn iter_multi_undirected_edges() {
+ let mut gr = Graph::new_undirected();
+ let a = gr.add_node("a");
+ let b = gr.add_node("b");
+ let c = gr.add_node("c");
+
+ let mut connecting_edges = HashSet::new();
+
+ gr.add_edge(a, a, ());
+ connecting_edges.insert(gr.add_edge(a, b, ()));
+ gr.add_edge(a, c, ());
+ gr.add_edge(c, b, ());
+ connecting_edges.insert(gr.add_edge(a, b, ()));
+ connecting_edges.insert(gr.add_edge(b, a, ()));
+
+ let mut iter = gr.edges_connecting(a, b);
+
+ let edge_id = iter.next().unwrap().id();
+ assert!(connecting_edges.contains(&edge_id));
+ connecting_edges.remove(&edge_id);
+
+ let edge_id = iter.next().unwrap().id();
+ assert!(connecting_edges.contains(&edge_id));
+ connecting_edges.remove(&edge_id);
+
+ let edge_id = iter.next().unwrap().id();
+ assert!(connecting_edges.contains(&edge_id));
+ connecting_edges.remove(&edge_id);
+
+ assert_eq!(None, iter.next());
+ assert!(connecting_edges.is_empty());
+}
+
#[test]
fn update_edge()
{
@@ -1565,7 +1630,7 @@
assert_eq!(set(po), set(vec![c, d]));
// Now let's test the same graph but undirected
-
+
let mut g = Graph::new_undirected();
let a = g.add_node("A");
let b = g.add_node("B");
