Dfs should use successors

webpro-patch · Nov 19, 2015 · ffcc1a1 · ffcc1a1
1 parent bbc3346
commit ffcc1a1
Show file tree

Hide file tree

Showing 2 changed files with 14 additions and 1 deletion.
diff --git a/lib/alg/dfs.js b/lib/alg/dfs.js
@@ -31,7 +31,7 @@ function doDfs(g, v, postorder, visited, acc) {
     visited[v] = true;
 
     if (!postorder) { acc.push(v); }
-    _.each(g.neighbors(v), function(w) {
+    _.each(g.successors(v), function(w) {
       doDfs(g, w, postorder, visited, acc);
     });
     if (postorder) { acc.push(v); }

diff --git a/test/alg/postorder-test.js b/test/alg/postorder-test.js
@@ -46,6 +46,19 @@ describe("alg.postorder", function() {
     expect(nodes.indexOf("d")).to.be.lt(nodes.indexOf("c"));
   });
 
+  it("works for multiple connected roots", function() {
+    var g = new Graph();
+    g.setEdge("a", "b");
+    g.setEdge("a", "c");
+    g.setEdge("d", "c");
+
+    var nodes = postorder(g, ["a", "d"]);
+    expect(_.sortBy(nodes)).to.eql(["a", "b", "c", "d"]);
+    expect(nodes.indexOf("b")).to.be.lt(nodes.indexOf("a"));
+    expect(nodes.indexOf("c")).to.be.lt(nodes.indexOf("a"));
+    expect(nodes.indexOf("c")).to.be.lt(nodes.indexOf("d"));
+  });
+
   it("fails if root is not in the graph", function() {
     var g = new Graph();
     g.setNode("a");