Fixup algorithms

webpro-patch · Sep 24, 2014 · 3938a75 · 3938a75
1 parent 7b60947
commit 3938a75
Show file tree

Hide file tree

Showing 16 changed files with 141 additions and 141 deletions.
diff --git a/lib/alg/greedy-fas.js b/lib/alg/greedy-fas.js
@@ -48,8 +48,8 @@ function removeNode(g, buckets, zeroIdx, entry, collectPredecessors) {
   var results = collectPredecessors ? [] : undefined;
 
   _.each(g.inEdges(entry.v), function(edge) {
-    var weight = g.edge(edge).weight,
-        uEntry = g.node(edge.v);
+    var weight = g.getEdge(edge),
+        uEntry = g.getNode(edge.v);
 
     if (collectPredecessors) {
       results.push({ v: edge.v, w: edge.w });
@@ -60,9 +60,9 @@ function removeNode(g, buckets, zeroIdx, entry, collectPredecessors) {
   });
 
   _.each(g.outEdges(entry.v), function(edge) {
-    var weight = g.edge(edge).weight,
+    var weight = g.getEdge(edge),
         w = edge.w,
-        wEntry = g.node(w);
+        wEntry = g.getNode(w);
     wEntry.in -= weight;
     assignBucket(buckets, zeroIdx, wEntry);
   });
@@ -78,21 +78,21 @@ function buildState(g, weightFn) {
       maxOut = 0;
 
   _.each(g.nodes(), function(v) {
-    _.merge(fasGraph.node(v), { v: v, in: 0, out: 0 });
+    fasGraph.setNode(v, { v: v, in: 0, out: 0 });
   });
 
   _.each(g.edges(), function(edge) {
     var weight = weightFn(edge);
-    fasGraph.edge(edge.v, edge.w).weight = weight;
-    maxOut = Math.max(maxOut, fasGraph.node(edge.v).out += weight);
-    maxIn  = Math.max(maxIn,  fasGraph.node(edge.w).in  += weight);
+    fasGraph.setEdge(edge, weight);
+    maxOut = Math.max(maxOut, fasGraph.getNode(edge.v).out += weight);
+    maxIn  = Math.max(maxIn,  fasGraph.getNode(edge.w).in  += weight);
   });
 
   var buckets = _.range(maxOut + maxIn + 3).map(function() { return new List(); });
   var zeroIdx = maxIn + 1;
 
   _.each(fasGraph.nodes(), function(v) {
-    assignBucket(buckets, zeroIdx, fasGraph.node(v));
+    assignBucket(buckets, zeroIdx, fasGraph.getNode(v));
   });
 
   return { graph: fasGraph, buckets: buckets, zeroIdx: zeroIdx };

diff --git a/lib/alg/prim.js b/lib/alg/prim.js
@@ -28,7 +28,7 @@ function prim(g, weightFunc) {
 
   _.each(g.nodes(), function(v) {
     pq.add(v, Number.POSITIVE_INFINITY);
-    result.node(v);
+    result.setNode(v);
   });
 
   // Start from an arbitrary node
@@ -38,7 +38,7 @@ function prim(g, weightFunc) {
   while (pq.size() > 0) {
     v = pq.removeMin();
     if (_.has(parents, v)) {
-      result.edge(v, parents[v]);
+      result.setEdge(v, parents[v]);
     } else if (init) {
       throw new Error("Input graph is not connected: " + g);
     } else {

diff --git a/test/alg/all-shortest-paths-test.js b/test/alg/all-shortest-paths-test.js
@@ -7,14 +7,14 @@ function tests(sp) {
   describe("allShortestPaths", function() {
     it("returns 0 for the node itself", function() {
       var g = new Graph();
-      g.node("a");
+      g.setNode("a");
       expect(sp(g)).to.eql({ a: { a: { distance: 0 } }});
     });
 
     it("returns the distance and path from all nodes to other nodes", function() {
       var g = new Graph();
-      g.edge("a", "b");
-      g.edge("b", "c");
+      g.setEdge("a", "b");
+      g.setEdge("b", "c");
       expect(sp(g)).to.eql({
         a: {
           a: { distance: 0 },
@@ -36,8 +36,8 @@ function tests(sp) {
 
     it("uses an optionally supplied weight function", function() {
       var g = new Graph();
-      g.edge("a", "b").weight = 2;
-      g.edge("b", "c").weight = 3;
+      g.setEdge("a", "b", 2);
+      g.setEdge("b", "c", 3);
 
       expect(sp(g, weightFn(g))).to.eql({
         a: {
@@ -60,8 +60,8 @@ function tests(sp) {
 
     it("uses an optionally supplied incident function", function() {
       var g = new Graph();
-      g.edge("a", "b");
-      g.edge("b", "c");
+      g.setEdge("a", "b");
+      g.setEdge("b", "c");
 
       expect(sp(g, undefined, function(v) { return g.inEdges(v); })).to.eql({
         a: {
@@ -84,10 +84,10 @@ function tests(sp) {
 
     it("works with undirected graphs", function() {
       var g = new Graph({ directed: false });
-      g.edge("a", "b").weight = 1;
-      g.edge("b", "c").weight = 2;
-      g.edge("c", "a").weight = 4;
-      g.edge("b", "d").weight = 6;
+      g.setEdge("a", "b", 1);
+      g.setEdge("b", "c", 2);
+      g.setEdge("c", "a", 4);
+      g.setEdge("b", "d", 6);
 
       expect(sp(g, weightFn(g), g.nodeEdges.bind(g))).to.eql({
         a: {
@@ -121,6 +121,6 @@ function tests(sp) {
 
 function weightFn(g) {
   return function(e) {
-    return g.edge(e).weight;
+    return g.getEdge(e);
   };
 }
diff --git a/test/alg/components-test.js b/test/alg/components-test.js
@@ -10,27 +10,27 @@ describe("alg.components", function() {
 
   it("returns singleton lists for unconnected nodes", function() {
     var g = new Graph({ directed: false });
-    g.node("a");
-    g.node("b");
+    g.setNode("a");
+    g.setNode("b");
 
     var result = _.sortBy(components(g), function(arr) { return _.min(arr); });
     expect(result).to.eql([["a"], ["b"]]);
   });
 
   it("returns a list of nodes in a component", function() {
     var g = new Graph({ directed: false });
-    g.edge("a", "b");
-    g.edge("b", "c");
+    g.setEdge("a", "b");
+    g.setEdge("b", "c");
 
     var result = _.map(components(g), function(xs) { return _.sortBy(xs); });
     expect(result).to.eql([["a", "b", "c"]]);
   });
 
   it("returns nodes connected by a neighbor relationship in a digraph", function() {
     var g = new Graph();
-    g.path("a", "b", "c", "a");
-    g.edge("d", "c");
-    g.edge("e", "f");
+    g.setPath(["a", "b", "c", "a"]);
+    g.setEdge("d", "c");
+    g.setEdge("e", "f");
 
     var result = _.sortBy(_.map(components(g), function(xs) { return _.sortBy(xs); }),
                           "0");

diff --git a/test/alg/dijkstra-all-test.js b/test/alg/dijkstra-all-test.js
@@ -8,17 +8,17 @@ describe("alg.dijkstraAll", function() {
 
   it("throws an Error if it encounters a negative edge weight", function() {
     var g = new Graph();
-    g.edge("a", "b").weight =  1;
-    g.edge("a", "c").weight = -2;
-    g.edge("b", "d").weight =  3;
-    g.edge("c", "d").weight =  3;
+    g.setEdge("a", "b",  1);
+    g.setEdge("a", "c", -2);
+    g.setEdge("b", "d",  3);
+    g.setEdge("c", "d",  3);
 
     expect(function() { dijkstraAll(g, weight(g)); }).to.throw();
   });
 });
 
 function weight(g) {
   return function(e) {
-    return g.edge(e).weight;
+    return g.getEdge(e);
   };
 }
diff --git a/test/alg/dijkstra-test.js b/test/alg/dijkstra-test.js
@@ -6,14 +6,14 @@ var Graph = require("../..").Graph,
 describe("alg.dijkstra", function() {
   it("assigns distance 0 for the source node", function() {
     var g = new Graph();
-    g.node("source");
+    g.setNode("source");
     expect(dijkstra(g, "source")).to.eql({ source: { distance: 0 } });
   });
 
   it("returns Number.POSITIVE_INFINITY for unconnected nodes", function() {
     var g = new Graph();
-    g.node("a");
-    g.node("b");
+    g.setNode("a");
+    g.setNode("b");
     expect(dijkstra(g, "a")).to.eql({
       a: { distance: 0 },
       b: { distance: Number.POSITIVE_INFINITY }
@@ -22,8 +22,8 @@ describe("alg.dijkstra", function() {
 
   it("returns the distance and path from the source node to other nodes", function() {
     var g = new Graph();
-    g.path("a", "b", "c");
-    g.edge("b", "d");
+    g.setPath(["a", "b", "c"]);
+    g.setEdge("b", "d");
     expect(dijkstra(g, "a")).to.eql({
       a: { distance: 0 },
       b: { distance: 1, predecessor: "a" },
@@ -34,8 +34,8 @@ describe("alg.dijkstra", function() {
 
   it("works for undirected graphs", function() {
     var g = new Graph({ directed: false });
-    g.path("a", "b", "c");
-    g.edge("b", "d");
+    g.setPath(["a", "b", "c"]);
+    g.setEdge("b", "d");
     expect(dijkstra(g, "a")).to.eql({
       a: { distance: 0 },
       b: { distance: 1, predecessor: "a" },
@@ -46,10 +46,10 @@ describe("alg.dijkstra", function() {
 
   it("uses an optionally supplied weight function", function() {
     var g = new Graph();
-    g.edge("a", "b").weight = 1;
-    g.edge("a", "c").weight = 2;
-    g.edge("b", "d").weight = 3;
-    g.edge("c", "d").weight = 3;
+    g.setEdge("a", "b", 1);
+    g.setEdge("a", "c", 2);
+    g.setEdge("b", "d", 3);
+    g.setEdge("c", "d", 3);
 
     expect(dijkstra(g, "a", weightFn(g))).to.eql({
       a: { distance: 0 },
@@ -61,8 +61,8 @@ describe("alg.dijkstra", function() {
 
   it("uses an optionally supplied edge function", function() {
     var g = new Graph();
-    g.path("a", "c", "d");
-    g.edge("b", "c");
+    g.setPath(["a", "c", "d"]);
+    g.setEdge("b", "c");
 
     expect(dijkstra(g, "d", undefined, function(e) { return g.inEdges(e); }), {
       a: { distance: 2, predecessor: "c" },
@@ -74,17 +74,17 @@ describe("alg.dijkstra", function() {
 
   it("throws an Error if it encounters a negative edge weight", function() {
     var g = new Graph();
-    g.edge("a", "b").weight =  1;
-    g.edge("a", "c").weight = -2;
-    g.edge("b", "d").weight =  3;
-    g.edge("c", "d").weight =  3;
+    g.setEdge("a", "b",  1);
+    g.setEdge("a", "c", -2);
+    g.setEdge("b", "d",  3);
+    g.setEdge("c", "d",  3);
 
     expect(function() { dijkstra(g, "a", weightFn(g)); }).to.throw();
   });
 });
 
 function weightFn(g) {
   return function(e) {
-    return g.edge(e).weight;
+    return g.getEdge(e);
   };
 }
diff --git a/test/alg/find-cycles-test.js b/test/alg/find-cycles-test.js
@@ -10,27 +10,27 @@ describe("alg.findCycles", function() {
 
   it("returns an empty array if the graph has no cycles", function() {
     var g = new Graph();
-    g.path("a", "b", "c");
+    g.setPath(["a", "b", "c"]);
     expect(findCycles(g)).to.eql([]);
   });
 
   it("returns a single entry for a cycle of 1 edge", function() {
     var g = new Graph();
-    g.path("a", "b", "a");
+    g.setPath(["a", "b", "a"]);
     expect(sort(findCycles(g))).to.eql([["a", "b"]]);
   });
 
   it("returns a single entry for a triangle", function() {
     var g = new Graph();
-    g.path("a", "b", "c", "a");
+    g.setPath(["a", "b", "c", "a"]);
     expect(sort(findCycles(g))).to.eql([["a", "b", "c"]]);
   });
 
   it("returns multiple entries for multiple cycles", function() {
     var g = new Graph();
-    g.path("a", "b", "a");
-    g.path("c", "d", "e", "c");
-    g.node("f");
+    g.setPath(["a", "b", "a"]);
+    g.setPath(["c", "d", "e", "c"]);
+    g.setNode("f");
     expect(sort(findCycles(g))).to.eql([["a", "b"], ["c", "d", "e"]]);
   });
 });

diff --git a/test/alg/floyd-warshall-test.js b/test/alg/floyd-warshall-test.js
@@ -8,10 +8,10 @@ describe("alg.floydWarshall", function() {
 
   it("handles negative weights", function() {
     var g = new Graph();
-    g.edge("a", "b").weight =  1;
-    g.edge("a", "c").weight = -2;
-    g.edge("b", "d").weight =  3;
-    g.edge("c", "d").weight =  3;
+    g.setEdge("a", "b",  1);
+    g.setEdge("a", "c", -2);
+    g.setEdge("b", "d",  3);
+    g.setEdge("c", "d",  3);
 
     expect(floydWarshall(g, weightFn(g))).to.eql({
       a: {
@@ -43,7 +43,7 @@ describe("alg.floydWarshall", function() {
 
   it("does include negative weight self edges", function() {
     var g = new Graph();
-    g.edge("a", "a").weight = -1;
+    g.setEdge("a", "a", -1);
 
     // In the case of a negative cycle the distance is not well-defined beyond
     // having a negative value along the diagonal.
@@ -57,6 +57,6 @@ describe("alg.floydWarshall", function() {
 
 function weightFn(g) {
   return function(edge) {
-    return g.edge(edge).weight;
+    return g.getEdge(edge);
   };
 }