Add postorder + fix uses of sort

kkowar · Sep 24, 2014 · 0c510b1 · 0c510b1
1 parent 63d8bc2
commit 0c510b1
Show file tree

Hide file tree

Showing 9 changed files with 109 additions and 23 deletions.
diff --git a/index.js b/index.js
@@ -40,6 +40,7 @@ module.exports = {
     dijkstraAll: require("./lib/alg/dijkstra-all"),
     findCycles: require("./lib/alg/find-cycles"),
     isAcyclic: require("./lib/alg/is-acyclic"),
+    postorder: require("./lib/alg/postorder"),
     preorder: require("./lib/alg/preorder"),
     tarjan: require("./lib/alg/tarjan"),
     topsort: require("./lib/alg/topsort")

diff --git a/lib/alg/postorder.js b/lib/alg/postorder.js
@@ -0,0 +1,25 @@
+var _ = require("lodash");
+
+module.exports = postorder;
+
+function postorder(g, root) {
+  var visited = {},
+      results = [];
+
+  dfs(g, root, undefined, visited, results);
+
+  return results;
+}
+
+function dfs(g, v, prev, visited, results) {
+  if (_.has(visited, v)) {
+    throw new Error("The input graph is not a tree: " + g);
+  }
+  visited[v] = true;
+  g.successors(v).forEach(function(w) {
+    if (g.isDirected() || w !== prev) {
+      dfs(g, w, v, visited, results);
+    }
+  });
+  results.push(v);
+}
diff --git a/test/alg/postorder-test.js b/test/alg/postorder-test.js
@@ -0,0 +1,60 @@
+var _ = require("lodash"),
+    expect = require("../chai").expect,
+    Graph = require("../..").Graph,
+    Digraph = require("../..").Digraph,
+    postorder = require("../..").alg.postorder;
+
+describe("alg.postorder", function() {
+  it("returns the root for a singleton graph", function() {
+    var g = new Graph();
+    g.setNode("a");
+    expect(postorder(g, "a")).to.eql(["a"]);
+  });
+
+  it("works for an undirected tree", function() {
+    var g = new Graph();
+    g.setEdge("a", "b");
+    g.setPath(["a", "c", "d"]);
+    g.setEdge("c", "e");
+
+    var result = postorder(g, "a");
+    expect(_.sortBy(result)).to.eql(["a", "b", "c", "d", "e"]);
+    expect(result.indexOf("b")).to.be.lt(result.indexOf("a"));
+    expect(result.indexOf("c")).to.be.lt(result.indexOf("a"));
+    expect(result.indexOf("d")).to.be.lt(result.indexOf("c"));
+    expect(result.indexOf("e")).to.be.lt(result.indexOf("c"));
+  });
+
+  it("fails for an undirected graph that is not a tree", function() {
+    var g = new Graph();
+    g.setPath(["a", "b", "c", "a"]);
+
+    expect(function() { postorder(g, "a"); }).to.throw();
+  });
+
+  it("works for a directed tree", function() {
+    var g = new Digraph();
+    g.setEdge("a", "b");
+    g.setPath(["a", "c", "d"]);
+    g.setEdge("c", "e");
+
+    var result = postorder(g, "a");
+    expect(_.sortBy(result)).to.eql(["a", "b", "c", "d", "e"]);
+    expect(result.indexOf("b")).to.be.lt(result.indexOf("a"));
+    expect(result.indexOf("c")).to.be.lt(result.indexOf("a"));
+    expect(result.indexOf("d")).to.be.lt(result.indexOf("c"));
+    expect(result.indexOf("e")).to.be.lt(result.indexOf("c"));
+  });
+
+  it("fails for a directed graph that is not a tree", function() {
+    var g = new Digraph();
+    g.setPath(["a", "b", "a"]);
+    expect(function() { postorder(g, "a"); }).to.throw();
+  });
+
+  it("fails if root is not in the graph", function() {
+    var g = new Graph();
+    g.setNode("a");
+    expect(function() { postorder(g, "b"); }).to.throw();
+  });
+});
diff --git a/test/alg/preorder-test.js b/test/alg/preorder-test.js
@@ -1,4 +1,5 @@
-var expect = require("../chai").expect,
+var _ = require("lodash"),
+    expect = require("../chai").expect,
     Graph = require("../..").Graph,
     Digraph = require("../..").Digraph,
     preorder = require("../..").alg.preorder;
@@ -17,7 +18,7 @@ describe("alg.preorder", function() {
     g.setEdge("c", "e");
 
     var result = preorder(g, "a");
-    expect(result.sort()).to.eql(["a", "b", "c", "d", "e"]);
+    expect(_.sortBy(result)).to.eql(["a", "b", "c", "d", "e"]);
     expect(result.indexOf("a")).to.be.lt(result.indexOf("b"));
     expect(result.indexOf("a")).to.be.lt(result.indexOf("c"));
     expect(result.indexOf("c")).to.be.lt(result.indexOf("d"));
@@ -38,7 +39,7 @@ describe("alg.preorder", function() {
     g.setEdge("c", "e");
 
     var result = preorder(g, "a");
-    expect(result.sort()).to.eql(["a", "b", "c", "d", "e"]);
+    expect(_.sortBy(result)).to.eql(["a", "b", "c", "d", "e"]);
     expect(result.indexOf("a")).to.be.lt(result.indexOf("b"));
     expect(result.indexOf("a")).to.be.lt(result.indexOf("c"));
     expect(result.indexOf("c")).to.be.lt(result.indexOf("d"));

diff --git a/test/alg/topsort-test.js b/test/alg/topsort-test.js
@@ -57,6 +57,6 @@ describe("alg.topsort", function() {
   it("returns unsorted nodes for an undirected graph with no edges", function() {
     var g = new Graph();
     g.setNodes(["a", "b", "c"]);
-    expect(topsort(g).sort()).to.eql(["a", "b", "c"]);
+    expect(_.sortBy(topsort(g))).to.eql(["a", "b", "c"]);
   });
 });
diff --git a/test/base-compound-graph-test.js b/test/base-compound-graph-test.js
@@ -1,4 +1,5 @@
-var expect = require("./chai").expect;
+var _ = require("lodash"),
+    expect = require("./chai").expect;
 
 exports.tests = tests;
 
@@ -30,8 +31,8 @@ function tests(GraphConstructor) {
       it("returns all sources for the root (undefined)", function() {
         g.setNode("n1");
         g.setNode("n2");
-        expect(g.getChildren().sort()).to.eql(["n1", "n2"]);
-        expect(g.getChildren(undefined).sort()).to.eql(["n1", "n2"]);
+        expect(_.sortBy(g.getChildren())).to.eql(["n1", "n2"]);
+        expect(_.sortBy(g.getChildren(undefined))).to.eql(["n1", "n2"]);
       });
     });
 
@@ -95,7 +96,7 @@ function tests(GraphConstructor) {
         g.setNode("n2");
 
         var nestingTree = g.getNestingTree();
-        expect(nestingTree.sources().sort()).to.eql(["n1", "n2"]);
+        expect(_.sortBy(nestingTree.sources())).to.eql(["n1", "n2"]);
       });
 
       it("returns the hierarchy for nested graphs", function() {
@@ -105,7 +106,7 @@ function tests(GraphConstructor) {
 
         var nestingTree = g.getNestingTree();
         expect(nestingTree.sources()).to.eql(["root"]);
-        expect(nestingTree.successors("root").sort()).to.eql(["n1-1", "n1-2"]);
+        expect(_.sortBy(nestingTree.successors("root"))).to.eql(["n1-1", "n1-2"]);
         expect(nestingTree.successors("n1-1")).to.eql(["n2"]);
       });
 

diff --git a/test/base-graph-test.js b/test/base-graph-test.js
@@ -193,7 +193,7 @@ exports.tests = function(GraphConstructor) {
         g.setEdge("n1", "n2");
         g.setEdge("n2", "n3");
         g.setEdge("n3", "n1");
-        expect(g.neighbors("n1").sort()).to.eql(["n1", "n2", "n3"]);
+        expect(_.sortBy(g.neighbors("n1"))).to.eql(["n1", "n2", "n3"]);
       });
 
       it("returns undefined if the node is not in the graph", function() {

diff --git a/test/digraph-test.js b/test/digraph-test.js
@@ -1,4 +1,5 @@
-var expect = require("./chai").expect,
+var _ = require("lodash"),
+    expect = require("./chai").expect,
     baseGraphTest = require("./base-graph-test");
 
 var Digraph = require("..").Digraph;
@@ -30,7 +31,7 @@ function tests(GraphConstructor) {
         g.setEdge("n2", "n3");
         g.setEdge("n4", "n3");
         g.setNode("n5");
-        expect(g.sources().sort()).to.eql(["n1", "n4", "n5"]);
+        expect(_.sortBy(g.sources())).to.eql(["n1", "n4", "n5"]);
       });
 
       it("recognizes a new source when in-edges are removed", function() {
@@ -49,7 +50,7 @@ function tests(GraphConstructor) {
         g.setEdge("n3", "n2");
         g.setEdge("n3", "n4");
         g.setNode("n5");
-        expect(g.sinks().sort()).to.eql(["n2", "n4", "n5"]);
+        expect(_.sortBy(g.sinks())).to.eql(["n2", "n4", "n5"]);
       });
 
       it("recognizes a new sink when out-edges are removed", function() {
@@ -68,7 +69,7 @@ function tests(GraphConstructor) {
         g.setEdge("n1", "n2");
         g.setEdge("n2", "n3");
         g.setEdge("n3", "n1");
-        expect(g.successors("n1").sort()).to.eql(["n1", "n2"]);
+        expect(_.sortBy(g.successors("n1"))).to.eql(["n1", "n2"]);
       });
     });
 
@@ -78,7 +79,7 @@ function tests(GraphConstructor) {
         g.setEdge("n1", "n2");
         g.setEdge("n2", "n3");
         g.setEdge("n3", "n1");
-        expect(g.predecessors("n1").sort()).to.eql(["n1", "n3"]);
+        expect(_.sortBy(g.predecessors("n1"))).to.eql(["n1", "n3"]);
       });
     });
 
@@ -145,9 +146,5 @@ function expectSingleEdgeGraph(g, v, w, label) {
 }
 
 function sortEdges(edges) {
-  return edges.sort(function(e1, e2) {
-    if (e1.v < e2.v) return -1;
-    if (e1.v > e2.v) return 1;
-    return 0;
-  });
+  return _.sortBy(edges, function(edge) { return edge.v; });
 }
diff --git a/test/graph-test.js b/test/graph-test.js
@@ -1,4 +1,5 @@
-var expect = require("./chai").expect,
+var _ = require("lodash"),
+    expect = require("./chai").expect,
     baseGraphTest = require("./base-graph-test");
 
 var Graph = require("..").Graph;
@@ -50,7 +51,7 @@ function tests(GraphConstructor) {
         g.setEdge("n2", "n3");
         g.setEdge("n3", "n1");
         g.setNode("n4");
-        expect(g.successors("n1").sort()).to.eql(["n1", "n2", "n3"]);
+        expect(_.sortBy(g.successors("n1"))).to.eql(["n1", "n2", "n3"]);
       });
     });
 
@@ -61,7 +62,7 @@ function tests(GraphConstructor) {
         g.setEdge("n2", "n3");
         g.setEdge("n3", "n1");
         g.setNode("n4");
-        expect(g.predecessors("n1").sort()).to.eql(["n1", "n2", "n3"]);
+        expect(_.sortBy(g.predecessors("n1"))).to.eql(["n1", "n2", "n3"]);
       });
     });
   });