Bug fix to dfs

Prior to this fix it was possible to visit nodes more than once when using an array of nodes as roots.
kkowar · Sep 24, 2014 · 8a5efef · 8a5efef
1 parent 27e7ee7
commit 8a5efef
Show file tree

Hide file tree

Showing 2 changed files with 26 additions and 12 deletions.
diff --git a/lib/alg/dfs.js b/lib/alg/dfs.js
@@ -32,31 +32,32 @@ function dfs(g, vs, order, fn, successors) {
     vs = [vs];
   }
 
-  var acc = [];
+  var acc = [],
+      visited = {};
   _.each(vs, function(v) {
     if (!g.hasNode(v)) {
       throw new Error("Graph does not have node: " + v);
     }
 
-    doDfs(v, order, fn, successors, {}, acc);
+    doDfs(v, order, fn, successors, visited, acc);
   });
   return acc;
 }
 
 function doDfs(v, order, fn, successors, visited, acc) {
-  visited[v] = true;
+  if (!_.has(visited, v)) {
+    visited[v] = true;
 
-  var result = fn(v);
-  if (result === false) { return false; }
-  if (result === null) { return null; }
+    var result = fn(v);
+    if (result === false) { return false; }
+    if (result === null) { return null; }
 
-  if (order === "pre") { acc.push(v); }
-  _.each(successors(v), function(w) {
-    if (!_.has(visited, w)) {
+    if (order === "pre") { acc.push(v); }
+    _.each(successors(v), function(w) {
       if (doDfs(w, order, fn, successors, visited, acc) === false) {
         return false;
       }
-    }
-  });
-  if (order === "post") { acc.push(v); }
+    });
+    if (order === "post") { acc.push(v); }
+  }
 }
diff --git a/test/alg/postorder-test.js b/test/alg/postorder-test.js
@@ -75,6 +75,19 @@ describe("alg.postorder", function() {
     expect(nodes.indexOf("d")).to.be.lt(nodes.indexOf("c"));
   });
 
+  it("works for an array of roots with an undirected graph", function() {
+    var g = new Graph();
+    g.setEdge("a", "b");
+    g.setEdge("c", "d");
+    g.setNode("e");
+    g.setNode("f");
+
+    var nodes = postorder(g, ["a", "b", "c", "e"]);
+    expect(_.sortBy(nodes)).to.eql(["a", "b", "c", "d", "e"]);
+    expect(nodes.indexOf("b")).to.be.lt(nodes.indexOf("a"));
+    expect(nodes.indexOf("d")).to.be.lt(nodes.indexOf("c"));
+  });
+
   it("finishes early if the callback returns false", function() {
     var g = new Digraph();
     g.setPath(["a", "b", "c", "d"]);