Improve IntoEdgesDirected and edges_directed for undirected graphs
This aligns edges_directed for undirected and directed graphs: in particular,
for incoming edges, the provided node will always be the target.
The `Edges` iterator implementation wasn't well suited for this change, so I
ended up rewriting it in what should hopefully be a more understandable
fashion.
This is a breaking change -- third-party implementations of IntoEdgesDirected
may have to be updated.
This allows implementing `IntoEdges` and `IntoEdgesDirected` for reversed
graphs -- that will be done in the next commit.
diff --git a/src/graph_impl/mod.rs b/src/graph_impl/mod.rs
index 1e8d1d6..670a612 100644
--- a/src/graph_impl/mod.rs
+++ b/src/graph_impl/mod.rs
@@ -816,33 +816,19 @@
///
/// - `Directed`, `Outgoing`: All edges from `a`.
/// - `Directed`, `Incoming`: All edges to `a`.
- /// - `Undirected`: All edges connected to `a`.
+ /// - `Undirected`, `Outgoing`: All edges connected to `a`, with `a` being the source of each
+ /// edge.
+ /// - `Undirected`, `Incoming`: All edges connected to `a`, with `a` being the target of each
+ /// edge.
///
/// Produces an empty iterator if the node `a` doesn't exist.<br>
/// Iterator element type is `EdgeReference<E, Ix>`.
pub fn edges_directed(&self, a: NodeIndex<Ix>, dir: Direction) -> Edges<E, Ty, Ix>
{
- let mut iter = self.edges_undirected(a);
- if self.is_directed() {
- iter.direction = Some(dir);
- }
- if self.is_directed() && dir == Incoming {
- iter.next.swap(0, 1);
- }
- iter
- }
-
- /// Return an iterator over all edges connected to `a`.
- ///
- /// - `Directed` and `Undirected`: All edges connected to `a`.
- ///
- /// Produces an empty iterator if the node `a` doesn't exist.<br>
- /// Iterator element type is `EdgeReference<E, Ix>`.
- fn edges_undirected(&self, a: NodeIndex<Ix>) -> Edges<E, Ty, Ix> {
Edges {
skip_start: a,
edges: &self.edges,
- direction: None,
+ direction: dir,
next: match self.nodes.get(a.index()) {
None => [EdgeIndex::end(), EdgeIndex::end()],
Some(n) => n.next,
@@ -1558,13 +1544,11 @@
edges: &'a [Edge<E, Ix>],
/// Next edge to visit.
- /// If we are only following one direction, we only use `next[0]` regardless.
next: [EdgeIndex<Ix>; 2],
- /// Which direction to follow
- /// None: Both,
- /// Some(d): d if Directed, Both if Undirected
- direction: Option<Direction>,
+ /// For directed graphs: the direction to iterate in
+ /// For undirected graphs: the direction of edges
+ direction: Direction,
ty: PhantomData<Ty>,
}
@@ -1575,42 +1559,59 @@
type Item = EdgeReference<'a, E, Ix>;
fn next(&mut self) -> Option<Self::Item> {
- // First the outgoing or incoming edges (directionality)
- let k = self.direction.unwrap_or(Outgoing).index();
- let i = self.next[0].index();
- match self.edges.get(i) {
- None => {}
- Some(&Edge { ref node, ref weight, ref next }) => {
- self.next[0] = next[k];
- return Some(EdgeReference {
- index: edge_index(i),
- node: *node,
- weight: weight,
- });
- }
- }
- // Stop here if we only follow one direction
- if self.direction.is_some() {
- return None;
- }
- // Then incoming edges
- // For an "undirected" iterator (traverse both incoming
- // and outgoing edge lists), make sure we don't double
- // count selfloops by skipping them in the incoming list.
+ // type direction | iterate over reverse
+ // |
+ // Directed Outgoing | outgoing no
+ // Directed Incoming | incoming no
+ // Undirected Outgoing | both incoming
+ // Undirected Incoming | both outgoing
- // We reach here if self.direction was None or Outgoing.
- debug_assert_eq!(k, 0);
- while let Some(edge) = self.edges.get(self.next[1].index()) {
- let i = self.next[1].index();
- self.next[1] = edge.next[1];
- if edge.node[0] != self.skip_start {
+ // For iterate_over, "both" is represented as None.
+ // For reverse, "no" is represented as None.
+ let (iterate_over, reverse) = if Ty::is_directed() {
+ (Some(self.direction), None)
+ } else {
+ (None, Some(self.direction.opposite()))
+ };
+
+ if iterate_over.unwrap_or(Outgoing) == Outgoing {
+ let i = self.next[0].index();
+ if let Some(Edge { node, weight, next }) = self.edges.get(i) {
+ self.next[0] = next[0];
return Some(EdgeReference {
index: edge_index(i),
- node: swap_pair(edge.node),
- weight: &edge.weight,
+ node: if reverse == Some(Outgoing) {
+ swap_pair(*node)
+ } else {
+ *node
+ },
+ weight,
});
}
}
+
+ if iterate_over.unwrap_or(Incoming) == Incoming {
+ while let Some(Edge { node, weight, next }) = self.edges.get(self.next[1].index()) {
+ let edge_index = self.next[1];
+ self.next[1] = next[1];
+ // In any of the "both" situations, self-loops would be iterated over twice.
+ // Skip them here.
+ if iterate_over.is_none() && node[0] == self.skip_start {
+ continue;
+ }
+
+ return Some(EdgeReference {
+ index: edge_index,
+ node: if reverse == Some(Incoming) {
+ swap_pair(*node)
+ } else {
+ *node
+ },
+ weight,
+ })
+ }
+ }
+
None
}
}
diff --git a/src/graph_impl/stable_graph/mod.rs b/src/graph_impl/stable_graph/mod.rs
index c730336..f34d0ce 100644
--- a/src/graph_impl/stable_graph/mod.rs
+++ b/src/graph_impl/stable_graph/mod.rs
@@ -658,33 +658,19 @@
///
/// - `Directed`, `Outgoing`: All edges from `a`.
/// - `Directed`, `Incoming`: All edges to `a`.
- /// - `Undirected`: All edges connected to `a`.
+ /// - `Undirected`, `Outgoing`: All edges connected to `a`, with `a` being the source of each
+ /// edge.
+ /// - `Undirected`, `Incoming`: All edges connected to `a`, with `a` being the target of each
+ /// edge.
///
/// Produces an empty iterator if the node `a` doesn't exist.<br>
/// Iterator element type is `EdgeReference<E, Ix>`.
pub fn edges_directed(&self, a: NodeIndex<Ix>, dir: Direction) -> Edges<E, Ty, Ix>
{
- let mut iter = self.edges_undirected(a);
- if self.is_directed() {
- iter.direction = Some(dir);
- }
- if self.is_directed() && dir == Incoming {
- iter.next.swap(0, 1);
- }
- iter
- }
-
- /// Return an iterator over all edges connected to `a`.
- ///
- /// - `Directed` and `Undirected`: All edges connected to `a`.
- ///
- /// Produces an empty iterator if the node `a` doesn't exist.<br>
- /// Iterator element type is `EdgeReference<E, Ix>`.
- fn edges_undirected(&self, a: NodeIndex<Ix>) -> Edges<E, Ty, Ix> {
Edges {
skip_start: a,
edges: &self.g.edges,
- direction: None,
+ direction: dir,
next: match self.get_node(a) {
None => [EdgeIndex::end(), EdgeIndex::end()],
Some(n) => n.next,
@@ -1280,7 +1266,6 @@
}
}
-
/// Iterator over the edges of from or to a node
pub struct Edges<'a, E: 'a, Ty, Ix: 'a = DefaultIx>
where Ty: EdgeType,
@@ -1291,13 +1276,11 @@
edges: &'a [Edge<Option<E>, Ix>],
/// Next edge to visit.
- /// If we are only following one direction, we only use `next[0]` regardless.
next: [EdgeIndex<Ix>; 2],
- /// Which direction to follow
- /// None: Both,
- /// Some(d): d if Directed, Both if Undirected
- direction: Option<Direction>,
+ /// For directed graphs: the direction to iterate in
+ /// For undirected graphs: the direction of edges
+ direction: Direction,
ty: PhantomData<Ty>,
}
@@ -1308,44 +1291,60 @@
type Item = EdgeReference<'a, E, Ix>;
fn next(&mut self) -> Option<Self::Item> {
- // First the outgoing or incoming edges (directionality)
- let k = self.direction.unwrap_or(Outgoing).index();
- let i = self.next[0].index();
- match self.edges.get(i) {
- None => {}
- Some(&Edge { ref node, weight: Some(ref weight), ref next }) => {
- self.next[0] = next[k];
- return Some(EdgeReference {
- index: edge_index(i),
- node: *node,
- weight: weight,
- });
- }
- Some(_otherwise) => unreachable!(),
- }
- // Stop here if we only follow one direction
- if self.direction.is_some() {
- return None;
- }
- // Then incoming edges
- // For an "undirected" iterator (traverse both incoming
- // and outgoing edge lists), make sure we don't double
- // count selfloops by skipping them in the incoming list.
+ // type direction | iterate over reverse
+ // |
+ // Directed Outgoing | outgoing no
+ // Directed Incoming | incoming no
+ // Undirected Outgoing | both incoming
+ // Undirected Incoming | both outgoing
- // We reach here if self.direction was None or Outgoing.
- debug_assert_eq!(k, 0);
- while let Some(edge) = self.edges.get(self.next[1].index()) {
- debug_assert!(edge.weight.is_some());
- let i = self.next[1].index();
- self.next[1] = edge.next[1];
- if edge.node[0] != self.skip_start {
+ // For iterate_over, "both" is represented as None.
+ // For reverse, "no" is represented as None.
+ let (iterate_over, reverse) = if Ty::is_directed() {
+ (Some(self.direction), None)
+ } else {
+ (None, Some(self.direction.opposite()))
+ };
+
+ if iterate_over.unwrap_or(Outgoing) == Outgoing {
+ let i = self.next[0].index();
+ if let Some(Edge { node, weight: Some(weight), next }) = self.edges.get(i) {
+ self.next[0] = next[0];
return Some(EdgeReference {
index: edge_index(i),
- node: swap_pair(edge.node),
- weight: edge.weight.as_ref().unwrap(),
+ node: if reverse == Some(Outgoing) {
+ swap_pair(*node)
+ } else {
+ *node
+ },
+ weight,
});
}
}
+
+ if iterate_over.unwrap_or(Incoming) == Incoming {
+ while let Some(Edge { node, weight, next }) = self.edges.get(self.next[1].index()) {
+ debug_assert!(weight.is_some());
+ let edge_index = self.next[1];
+ self.next[1] = next[1];
+ // In any of the "both" situations, self-loops would be iterated over twice.
+ // Skip them here.
+ if iterate_over.is_none() && node[0] == self.skip_start {
+ continue;
+ }
+
+ return Some(EdgeReference {
+ index: edge_index,
+ node: if reverse == Some(Incoming) {
+ swap_pair(*node)
+ } else {
+ *node
+ },
+ weight: weight.as_ref().unwrap(),
+ })
+ }
+ }
+
None
}
}
diff --git a/src/matrix_graph.rs b/src/matrix_graph.rs
index 3d2bd8a..4c083f8 100644
--- a/src/matrix_graph.rs
+++ b/src/matrix_graph.rs
@@ -495,9 +495,8 @@
/// `a`, in the specified direction.
/// If the graph's edges are undirected, this is equivalent to *.neighbors(a)*.
///
- /// - `Directed`, `Outgoing`: All edges from `a`.
- /// - `Directed`, `Incoming`: All edges to `a`.
- /// - `Undirected`: All edges from or to `a`.
+ /// - `Outgoing`: All edges from `a`.
+ /// - `Incoming`: All edges to `a`.
///
/// Produces an empty iterator if the node doesn't exist.<br>
/// Iterator element type is [`NodeIndex<Ix>`](../graph/struct.NodeIndex.html).
@@ -511,9 +510,8 @@
/// Return an iterator of all edges of `a`, in the specified direction.
///
- /// - `Directed`, `Outgoing`: All edges from `a`.
- /// - `Directed`, `Incoming`: All edges to `a`.
- /// - `Undirected`: All edges connected to `a`.
+ /// - `Outgoing`: All edges from `a`.
+ /// - `Incoming`: All edges to `a`.
///
/// Produces an empty iterator if the node `a` doesn't exist.<br>
/// Iterator element type is [`EdgeReference<E, Ix>`](../graph/struct.EdgeReference.html).
diff --git a/src/visit/mod.rs b/src/visit/mod.rs
index d9351f9..739ab58 100644
--- a/src/visit/mod.rs
+++ b/src/visit/mod.rs
@@ -248,7 +248,8 @@
///
/// - `Directed`, `Outgoing`: All edges from `a`.
/// - `Directed`, `Incoming`: All edges to `a`.
-/// - `Undirected`: All edges connected to `a`.
+/// - `Undirected`, `Outgoing`: All edges connected to `a`, with `a` being the source of each edge.
+/// - `Undirected`, `Incoming`: All edges connected to `a`, with `a` being the target of each edge.
///
/// This is an extended version of the trait `IntoNeighborsDirected`; the former
/// only iterates over the target node identifiers, while this trait
diff --git a/tests/graph.rs b/tests/graph.rs
index 8bdc077..6eaf804 100644
--- a/tests/graph.rs
+++ b/tests/graph.rs
@@ -1108,6 +1108,80 @@
}
}
+fn make_edge_iterator_graph<Ty: EdgeType>() -> Graph<f64, f64, Ty> {
+ let mut gr = Graph::default();
+ let a = gr.add_node(0.);
+ let b = gr.add_node(0.);
+ let c = gr.add_node(0.);
+ let d = gr.add_node(0.);
+ let e = gr.add_node(0.);
+ let f = gr.add_node(0.);
+ let g = gr.add_node(0.);
+ gr.add_edge(a, b, 7.0);
+ gr.add_edge(a, d, 5.);
+ gr.add_edge(d, b, 9.);
+ gr.add_edge(b, c, 8.);
+ gr.add_edge(b, e, 7.);
+ gr.add_edge(c, c, 8.);
+ gr.add_edge(c, e, 5.);
+ gr.add_edge(d, e, 15.);
+ gr.add_edge(d, f, 6.);
+ gr.add_edge(f, e, 8.);
+ gr.add_edge(f, g, 11.);
+ gr.add_edge(e, g, 9.);
+
+ gr
+}
+
+#[test]
+fn test_edge_iterators_directed() {
+ let gr = make_edge_iterator_graph::<Directed>();
+
+ for i in gr.node_indices() {
+ itertools::assert_equal(
+ gr.edges_directed(i, Outgoing),
+ gr.edges(i));
+ for edge in gr.edges_directed(i, Outgoing) {
+ assert_eq!(edge.source(), i, "outgoing edges should have a fixed source");
+ }
+ }
+
+ let mut reversed_gr = gr.clone();
+ reversed_gr.reverse();
+
+ println!("{:#?}", gr);
+ for i in gr.node_indices() {
+ itertools::assert_equal(
+ gr.edges_directed(i, Incoming),
+ reversed_gr.edges(i));
+ for edge in gr.edges_directed(i, Incoming) {
+ assert_eq!(edge.target(), i, "incoming edges should have a fixed target");
+ }
+ }
+}
+
+#[test]
+fn test_edge_iterators_undir() {
+ let gr = make_edge_iterator_graph::<Undirected>();
+
+ for i in gr.node_indices() {
+ itertools::assert_equal(
+ gr.edges_directed(i, Outgoing),
+ gr.edges(i));
+ for edge in gr.edges_directed(i, Outgoing) {
+ assert_eq!(edge.source(), i, "outgoing edges should have a fixed source");
+ }
+ }
+ for i in gr.node_indices() {
+ itertools::assert_equal(
+ gr.edges_directed(i, Incoming),
+ gr.edges(i));
+ for edge in gr.edges_directed(i, Incoming) {
+ assert_eq!(edge.target(), i, "incoming edges should have a fixed target");
+ }
+ }
+}
+
#[test]
fn toposort_generic() {
// This is a DAG, visit it in order
diff --git a/tests/stable_graph.rs b/tests/stable_graph.rs
index bc6b034..21fbbe7 100644
--- a/tests/stable_graph.rs
+++ b/tests/stable_graph.rs
@@ -14,7 +14,6 @@
IntoEdgeReferences,
};
use petgraph::dot::Dot;
-
use itertools::assert_equal;
#[test]
@@ -177,6 +176,9 @@
itertools::assert_equal(
gr.edges_directed(i, Outgoing),
gr.edges(i));
+ for edge in gr.edges_directed(i, Outgoing) {
+ assert_eq!(edge.source(), i, "outgoing edges should have a fixed source");
+ }
}
let mut incoming = vec![Vec::new(); gr.node_bound()];
@@ -191,6 +193,9 @@
itertools::assert_equal(
gr.edges_directed(i, Incoming).map(|e| e.source()),
incoming[i.index()].iter().rev().cloned());
+ for edge in gr.edges_directed(i, Incoming) {
+ assert_eq!(edge.target(), i, "incoming edges should have a fixed target");
+ }
}
}
@@ -201,11 +206,17 @@
itertools::assert_equal(
gr.edges_directed(i, Outgoing),
gr.edges(i));
+ for edge in gr.edges_directed(i, Outgoing) {
+ assert_eq!(edge.source(), i, "outgoing edges should have a fixed source");
+ }
}
for i in gr.node_indices() {
itertools::assert_equal(
gr.edges_directed(i, Incoming),
gr.edges(i));
+ for edge in gr.edges_directed(i, Incoming) {
+ assert_eq!(edge.target(), i, "incoming edges should have a fixed target");
+ }
}
}
