visit: implement IntoEdges and IntoEdgesDirected for Reversed
Thanks to the previous change, this will work correctly on both directed and
undirected graphs.
Closes #292.
diff --git a/src/visit/reversed.rs b/src/visit/reversed.rs
index 29c6d48..ee5c772 100644
--- a/src/visit/reversed.rs
+++ b/src/visit/reversed.rs
@@ -7,6 +7,8 @@
use crate::visit::{
GraphBase,
GraphRef,
+ IntoEdges,
+ IntoEdgesDirected,
IntoNodeIdentifiers,
IntoNodeReferences,
IntoNeighbors,
@@ -57,6 +59,28 @@
}
}
+impl<G> IntoEdges for Reversed<G>
+ where G: IntoEdgesDirected
+{
+ type Edges = ReversedEdges<G::EdgesDirected>;
+ fn edges(self, a: Self::NodeId) -> Self::Edges {
+ ReversedEdges {
+ iter: self.0.edges_directed(a, Incoming),
+ }
+ }
+}
+
+impl<G> IntoEdgesDirected for Reversed<G>
+ where G: IntoEdgesDirected
+{
+ type EdgesDirected = ReversedEdges<G::EdgesDirected>;
+ fn edges_directed(self, a: Self::NodeId, dir: Direction) -> Self::Edges {
+ ReversedEdges {
+ iter: self.0.edges_directed(a, dir.opposite()),
+ }
+ }
+}
+
impl<G: Visitable> Visitable for Reversed<G>
{
type Map = G::Map;
@@ -68,6 +92,19 @@
}
}
+/// A reversed edges iterator.
+pub struct ReversedEdges<I> {
+ iter: I,
+}
+
+impl<I> Iterator for ReversedEdges<I>
+ where I: Iterator, I::Item: EdgeRef
+{
+ type Item = ReversedEdgeReference<I::Item>;
+ fn next(&mut self) -> Option<Self::Item> {
+ self.iter.next().map(ReversedEdgeReference)
+ }
+}
/// A reversed edge reference
#[derive(Copy, Clone, Debug)]
diff --git a/tests/graph.rs b/tests/graph.rs
index 6eaf804..8cfbb49 100644
--- a/tests/graph.rs
+++ b/tests/graph.rs
@@ -24,6 +24,8 @@
};
use petgraph::visit::{
+ IntoEdges,
+ IntoEdgesDirected,
IntoNodeIdentifiers,
NodeFiltered,
Reversed,
@@ -1141,9 +1143,18 @@
itertools::assert_equal(
gr.edges_directed(i, Outgoing),
gr.edges(i));
+
+ // Reversed reverses edges, so target and source need to be reversed once more.
+ itertools::assert_equal(
+ gr.edges_directed(i, Outgoing).map(|edge| (edge.source(), edge.target())),
+ Reversed(&gr).edges_directed(i, Incoming).map(|edge| (edge.target(), edge.source())));
+
for edge in gr.edges_directed(i, Outgoing) {
assert_eq!(edge.source(), i, "outgoing edges should have a fixed source");
}
+ for edge in Reversed(&gr).edges_directed(i, Incoming) {
+ assert_eq!(edge.target(), i, "reversed incoming edges should have a fixed target");
+ }
}
let mut reversed_gr = gr.clone();
@@ -1151,12 +1162,22 @@
println!("{:#?}", gr);
for i in gr.node_indices() {
+ // Compare against reversed graphs two different ways: using .reverse() and Reversed.
itertools::assert_equal(
gr.edges_directed(i, Incoming),
reversed_gr.edges(i));
+
+ // Reversed reverses edges, so target and source need to be reversed once more.
+ itertools::assert_equal(
+ gr.edges_directed(i, Incoming).map(|edge| (edge.source(), edge.target())),
+ Reversed(&gr).edges(i).map(|edge| (edge.target(), edge.source())));
+
for edge in gr.edges_directed(i, Incoming) {
assert_eq!(edge.target(), i, "incoming edges should have a fixed target");
}
+ for edge in Reversed(&gr).edges_directed(i, Outgoing) {
+ assert_eq!(edge.source(), i, "reversed outgoing edges should have a fixed source");
+ }
}
}
@@ -1168,17 +1189,36 @@
itertools::assert_equal(
gr.edges_directed(i, Outgoing),
gr.edges(i));
+
+ // Reversed reverses edges, so target and source need to be reversed once more.
+ itertools::assert_equal(
+ gr.edges_directed(i, Outgoing).map(|edge| (edge.source(), edge.target())),
+ Reversed(&gr).edges_directed(i, Incoming).map(|edge| (edge.target(), edge.source())));
+
for edge in gr.edges_directed(i, Outgoing) {
assert_eq!(edge.source(), i, "outgoing edges should have a fixed source");
}
+ for edge in Reversed(&gr).edges_directed(i, Incoming) {
+ assert_eq!(edge.target(), i, "reversed incoming edges should have a fixed target");
+ }
}
+
for i in gr.node_indices() {
itertools::assert_equal(
gr.edges_directed(i, Incoming),
gr.edges(i));
+
+ // Reversed reverses edges, so target and source need to be reversed once more.
+ itertools::assert_equal(
+ gr.edges_directed(i, Incoming).map(|edge| (edge.source(), edge.target())),
+ Reversed(&gr).edges(i).map(|edge| (edge.target(), edge.source())));
+
for edge in gr.edges_directed(i, Incoming) {
assert_eq!(edge.target(), i, "incoming edges should have a fixed target");
}
+ for edge in Reversed(&gr).edges_directed(i, Outgoing) {
+ assert_eq!(edge.source(), i, "reversed outgoing edges should have a fixed source");
+ }
}
}
