Add floydWarshall algorithm

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

Hide file tree

Showing 5 changed files with 237 additions and 35 deletions.
diff --git a/index.js b/index.js
@@ -39,6 +39,7 @@ module.exports = {
     dijkstra: require("./lib/alg/dijkstra"),
     dijkstraAll: require("./lib/alg/dijkstra-all"),
     findCycles: require("./lib/alg/find-cycles"),
+    floydWarshall: require("./lib/alg/floyd-warshall"),
     isAcyclic: require("./lib/alg/is-acyclic"),
     postorder: require("./lib/alg/postorder"),
     preorder: require("./lib/alg/preorder"),

diff --git a/lib/alg/floyd-warshall.js b/lib/alg/floyd-warshall.js
@@ -0,0 +1,50 @@
+var _ = require("lodash");
+
+module.exports = floydWarshall;
+
+var DEFAULT_WEIGHT_FUNC = _.constant(1);
+
+function floydWarshall(g, weightFunc, edgeFunc) {
+  return runFloydWarshall(g,
+                          weightFunc || DEFAULT_WEIGHT_FUNC,
+                          edgeFunc || function(v) { return g.outEdges(v); });
+}
+
+function runFloydWarshall(g, weightFunc, edgeFunc) {
+  var results = {},
+      nodes = g.nodeIds();
+
+  nodes.forEach(function(v) {
+    results[v] = {};
+    results[v][v] = { distance: 0 };
+    nodes.forEach(function(w) {
+      if (v !== w) {
+        results[v][w] = { distance: Number.POSITIVE_INFINITY };
+      }
+    });
+    edgeFunc(v).forEach(function(edge) {
+      var w = edge.v === v ? edge.w : edge.v,
+          d = weightFunc(edge);
+      results[v][w] = { distance: d, predecessor: v };
+    });
+  });
+
+  nodes.forEach(function(k) {
+    var rowK = results[k];
+    nodes.forEach(function(i) {
+      var rowI = results[i];
+      nodes.forEach(function(j) {
+        var ik = rowI[k];
+        var kj = rowK[j];
+        var ij = rowI[j];
+        var altDistance = ik.distance + kj.distance;
+        if (altDistance < ij.distance) {
+          ij.distance = altDistance;
+          ij.predecessor = kj.predecessor;
+        }
+      });
+    });
+  });
+
+  return results;
+}
diff --git a/test/alg/all-shortest-paths-test.js b/test/alg/all-shortest-paths-test.js
@@ -0,0 +1,124 @@
+var expect = require("../chai").expect,
+    util = require("../..").util,
+    Digraph = require("../..").Digraph,
+    Graph = require("../..").Graph;
+
+exports.tests = tests;
+
+function tests(sp) {
+  describe("allShortestPaths", function() {
+    it("returns 0 for the node itself", function() {
+      var g = new Digraph();
+      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 Digraph();
+      g.setEdge("a", "b");
+      g.setEdge("b", "c");
+      expect(sp(g)).to.eql({
+        a: {
+          a: { distance: 0 },
+          b: { distance: 1, predecessor: "a" },
+          c: { distance: 2, predecessor: "b" }
+        },
+        b: {
+          a: { distance: Number.POSITIVE_INFINITY },
+          b: { distance: 0 },
+          c: { distance: 1, predecessor: "b" }
+        },
+        c: {
+          a: { distance: Number.POSITIVE_INFINITY },
+          b: { distance: Number.POSITIVE_INFINITY },
+          c: { distance: 0 }
+        }
+      });
+    });
+
+    it("uses an optionally supplied weight function", function() {
+      var g = new Digraph();
+      g.setEdge("a", "b", 2);
+      g.setEdge("b", "c", 3);
+
+      expect(sp(g, util.LABEL_WEIGHT_FUNC)).to.eql({
+        a: {
+          a: { distance: 0 },
+          b: { distance: 2, predecessor: "a" },
+          c: { distance: 5, predecessor: "b" }
+        },
+        b: {
+          a: { distance: Number.POSITIVE_INFINITY },
+          b: { distance: 0 },
+          c: { distance: 3, predecessor: "b" }
+        },
+        c: {
+          a: { distance: Number.POSITIVE_INFINITY },
+          b: { distance: Number.POSITIVE_INFINITY },
+          c: { distance: 0 }
+        }
+      });
+    });
+
+    it("uses an optionally supplied incident function", function() {
+      var g = new Digraph();
+      g.setEdge("a", "b");
+      g.setEdge("b", "c");
+
+      expect(sp(g, undefined, function(v) { return g.inEdges(v); })).to.eql({
+        a: {
+          a: { distance: 0 },
+          b: { distance: Number.POSITIVE_INFINITY },
+          c: { distance: Number.POSITIVE_INFINITY }
+        },
+        b: {
+          a: { distance: 1, predecessor: "b" },
+          b: { distance: 0 },
+          c: { distance: Number.POSITIVE_INFINITY }
+        },
+        c: {
+          a: { distance: 2, predecessor: "b" },
+          b: { distance: 1, predecessor: "c" },
+          c: { distance: 0 }
+        }
+      });
+    });
+
+    it("works with undirected graphs", function() {
+      var g = new Graph();
+      g.setEdge("a", "b", 1);
+      g.setEdge("b", "c", 2);
+      g.setEdge("c", "a", 4);
+      g.setEdge("b", "d", 6);
+
+      function w(edge) { return edge.label; }
+
+      expect(sp(g, w)).to.eql({
+        a: {
+          a: { distance: 0 },
+          b: { distance: 1, predecessor: "a" },
+          c: { distance: 3, predecessor: "b" },
+          d: { distance: 7, predecessor: "b" },
+        },
+        b: {
+          a: { distance: 1, predecessor: "b" },
+          b: { distance: 0 },
+          c: { distance: 2, predecessor: "b" },
+          d: { distance: 6, predecessor: "b" },
+        },
+        c: {
+          a: { distance: 3, predecessor: "b" },
+          b: { distance: 2, predecessor: "c" },
+          c: { distance: 0 },
+          d: { distance: 8, predecessor: "b" },
+        },
+        d: {
+          a: { distance: 7, predecessor: "b" },
+          b: { distance: 6, predecessor: "d" },
+          c: { distance: 8, predecessor: "b" },
+          d: { distance: 0 },
+        }
+      });
+    });
+  });
+}
diff --git a/test/alg/dijkstra-all-test.js b/test/alg/dijkstra-all-test.js
@@ -1,41 +1,11 @@
-var expect = require("../chai").expect;
-
-var Digraph = require("../..").Digraph,
+var expect = require("../chai").expect,
+    Digraph = require("../..").Digraph,
+    dijkstraAll = require("../..").alg.dijkstraAll,
     util = require("../..").util,
-    dijkstraAll = require("../..").alg.dijkstraAll;
+    allShortestPathsTest = require("./all-shortest-paths-test");
 
 describe("alg.dijkstraAll", function() {
-  // Note: these tests are mostly for sanity. Since we delegate to dijkstra
-  // we already have pretty complete test coverage.
-
-  it("returns 0 for the node itself", function() {
-    var g = new Digraph();
-    g.setNode("a");
-    expect(dijkstraAll(g)).to.eql({ a: { a: { distance: 0 } }});
-  });
-
-  it("returns the distance and path from all nodes to other nodes", function() {
-    var g = new Digraph();
-    g.setEdge("a", "b");
-    g.setEdge("b", "c");
-    expect(dijkstraAll(g)).to.eql({
-      a: {
-        a: { distance: 0 },
-        b: { distance: 1, predecessor: "a" },
-        c: { distance: 2, predecessor: "b" }
-      },
-      b: {
-        a: { distance: Number.POSITIVE_INFINITY },
-        b: { distance: 0 },
-        c: { distance: 1, predecessor: "b" }
-      },
-      c: {
-        a: { distance: Number.POSITIVE_INFINITY },
-        b: { distance: Number.POSITIVE_INFINITY },
-        c: { distance: 0 }
-      }
-    });
-  });
+  allShortestPathsTest.tests(dijkstraAll);
 
   it("throws an Error if it encounters a negative edge weight", function() {
     var g = new Digraph();

diff --git a/test/alg/floyd-warshall-test.js b/test/alg/floyd-warshall-test.js
@@ -0,0 +1,57 @@
+var expect = require("../chai").expect,
+    Digraph = require("../..").Digraph,
+    util = require("../..").util,
+    floydWarshall = require("../..").alg.floydWarshall,
+    allShortestPathsTest = require("./all-shortest-paths-test");
+
+describe("alg.floydWarshall", function() {
+  allShortestPathsTest.tests(floydWarshall);
+
+  it("handles negative weights", function() {
+    var g = new Digraph();
+    g.setEdge("a", "b", 1);
+    g.setEdge("a", "c", -2);
+    g.setEdge("b", "d", 3);
+    g.setEdge("c", "d", 3);
+
+    expect(floydWarshall(g, util.LABEL_WEIGHT_FUNC)).to.eql({
+      a: {
+        a: { distance: 0 },
+        b: { distance: 1, predecessor: "a" },
+        c: { distance: -2, predecessor: "a" },
+        d: { distance: 1, predecessor: "c" }
+      },
+      b: {
+        a: { distance: Number.POSITIVE_INFINITY },
+        b: { distance: 0 },
+        c: { distance: Number.POSITIVE_INFINITY },
+        d: { distance: 3, predecessor: "b" }
+      },
+      c: {
+        a: { distance: Number.POSITIVE_INFINITY },
+        b: { distance: Number.POSITIVE_INFINITY },
+        c: { distance: 0 },
+        d: { distance: 3, predecessor: "c" }
+      },
+      d: {
+        a: { distance: Number.POSITIVE_INFINITY },
+        b: { distance: Number.POSITIVE_INFINITY },
+        c: { distance: Number.POSITIVE_INFINITY },
+        d: { distance: 0 }
+      }
+    });
+  });
+
+  it("does include negative weight self edges", function() {
+    var g = new Digraph();
+    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.
+    expect(floydWarshall(g, util.LABEL_WEIGHT_FUNC)).to.eql({
+      a: {
+        a: { distance: -2, predecessor: "a" }
+      }
+    });
+  });
+});