Merge pull request #304 from crgl/iterative-dfs-bug
Fix bug in order of iterative DFS
diff --git a/src/algo/mod.rs b/src/algo/mod.rs
index d1771f9..8d42c9b 100644
--- a/src/algo/mod.rs
+++ b/src/algo/mod.rs
@@ -6,7 +6,7 @@
pub mod dominators;
-use std::collections::BinaryHeap;
+use std::collections::{BinaryHeap, HashMap};
use std::cmp::min;
use crate::prelude::*;
@@ -578,6 +578,8 @@
node_ids: Some(g.node_references()),
subgraphs: subgraphs,
sort_edges: sort_edges,
+ node_map: HashMap::new(),
+ node_count: 0,
}
}
@@ -590,6 +592,8 @@
node_ids: Option<G::NodeReferences>,
subgraphs: UnionFind<usize>,
sort_edges: BinaryHeap<MinScored<G::EdgeWeight, (G::NodeId, G::NodeId)>>,
+ node_map: HashMap<usize, usize>,
+ node_count: usize,
}
@@ -601,8 +605,11 @@
type Item = Element<G::NodeWeight, G::EdgeWeight>;
fn next(&mut self) -> Option<Self::Item> {
+ let g = self.graph;
if let Some(ref mut iter) = self.node_ids {
if let Some(node) = iter.next() {
+ self.node_map.insert(g.to_index(node.id()), self.node_count);
+ self.node_count += 1;
return Some(Element::Node { weight: node.weight().clone() });
}
}
@@ -618,12 +625,17 @@
// b. If the edge connects two disjoint trees in the pre-MST,
// add the edge.
while let Some(MinScored(score, (a, b))) = self.sort_edges.pop() {
- let g = self.graph;
// check if the edge would connect two disjoint parts
- if self.subgraphs.union(g.to_index(a), g.to_index(b)) {
+ let (a_index, b_index) = (g.to_index(a), g.to_index(b));
+ if self.subgraphs.union(a_index, b_index) {
+ let (&a_order, &b_order) = match (self.node_map.get(&a_index),
+ self.node_map.get(&b_index)) {
+ (Some(a_id), Some(b_id)) => (a_id, b_id),
+ _ => panic!("Edge references unknown node"),
+ };
return Some(Element::Edge {
- source: g.to_index(a),
- target: g.to_index(b),
+ source: a_order,
+ target: b_order,
weight: score,
});
}
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/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 fe57de2..758007d 100644
--- a/tests/graph.rs
+++ b/tests/graph.rs
@@ -24,6 +24,8 @@
};
use petgraph::visit::{
+ IntoEdges,
+ IntoEdgesDirected,
IntoNodeIdentifiers,
NodeFiltered,
Reversed,
@@ -1137,6 +1139,118 @@
}
}
+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));
+
+ // 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();
+ reversed_gr.reverse();
+
+ 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");
+ }
+ }
+}
+
+#[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));
+
+ // 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");
+ }
+ }
+}
+
#[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..7d05669 100644
--- a/tests/stable_graph.rs
+++ b/tests/stable_graph.rs
@@ -7,14 +7,13 @@
use petgraph::prelude::*;
use petgraph::stable_graph::node_index as n;
use petgraph::EdgeType;
-use petgraph::algo::{kosaraju_scc, tarjan_scc};
+use petgraph::algo::{kosaraju_scc, tarjan_scc, min_spanning_tree};
use petgraph::visit::{
NodeIndexable,
IntoNodeReferences,
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");
+ }
}
}
@@ -343,3 +354,23 @@
assert!(edgew_eq!(gr5, ans));
assert!(edges_eq!(gr5, ans));
}
+
+use petgraph::stable_graph::StableGraph;
+use petgraph::data::FromElements;
+
+#[test]
+fn from_min_spanning_tree() {
+ let mut g = StableGraph::new();
+ let mut nodes = Vec::new();
+ for _ in 0..6 {
+ nodes.push(g.add_node(()));
+ }
+ let es = [(4, 5), (3, 4), (3, 5)];
+ for &(a, b) in es.iter() {
+ g.add_edge(NodeIndex::new(a), NodeIndex::new(b), ());
+ }
+ for i in 0..3 {
+ let _ = g.remove_node(nodes[i]);
+ }
+ let _ = StableGraph::<(),(),Undirected,usize>::from_elements(min_spanning_tree(&g));
+}
