Merge pull request #304 from crgl/iterative-dfs-bug
Fix bug in order of iterative DFS
diff --git a/src/visit/traversal.rs b/src/visit/traversal.rs
index 3a40e7c..672a688 100644
--- a/src/visit/traversal.rs
+++ b/src/visit/traversal.rs
@@ -86,7 +86,6 @@
/// the dfs from a particular node.
pub fn move_to(&mut self, start: N)
{
- self.discovered.visit(start);
self.stack.clear();
self.stack.push(start);
}
@@ -95,14 +94,15 @@
pub fn next<G>(&mut self, graph: G) -> Option<N>
where G: IntoNeighbors<NodeId=N>,
{
- if let Some(node) = self.stack.pop() {
- for succ in graph.neighbors(node) {
- if self.discovered.visit(succ) {
- self.stack.push(succ);
+ while let Some(node) = self.stack.pop() {
+ if self.discovered.visit(node) {
+ for succ in graph.neighbors(node) {
+ if !self.discovered.is_visited(&succ) {
+ self.stack.push(succ);
+ }
}
+ return Some(node);
}
-
- return Some(node);
}
None
}
diff --git a/tests/graph.rs b/tests/graph.rs
index 8cfbb49..758007d 100644
--- a/tests/graph.rs
+++ b/tests/graph.rs
@@ -118,6 +118,35 @@
assert_eq!(Dfs::new(&gr, i).iter(&gr).count(), 3);
}
+#[test]
+fn dfs_order() {
+ let mut gr = Graph::new();
+ let h = gr.add_node("H");
+ let i = gr.add_node("I");
+ let j = gr.add_node("J");
+ let k = gr.add_node("K");
+ gr.add_edge(h, i, ());
+ gr.add_edge(h, j, ());
+ gr.add_edge(h, k, ());
+ gr.add_edge(i, k, ());
+ gr.add_edge(k, i, ());
+
+ // H
+ // / | \
+ // I J K
+ // \___/
+ //
+ // J cannot be visited between I and K in a depth-first search from H
+
+ let mut seen_i = false;
+ let mut seen_k = false;
+ for node in Dfs::new(&gr, h).iter(&gr) {
+ seen_i |= i == node;
+ seen_k |= k == node;
+ assert!(!(j == node && (seen_i ^ seen_k)), "Invalid DFS order");
+ }
+}
+
#[test]
fn bfs() {
