Implement greedyFAS algorithm

kkowar · Sep 24, 2014 · a457644 · a457644
1 parent c577e0d
commit a457644
Show file tree

Hide file tree

Showing 4 changed files with 208 additions and 0 deletions.
diff --git a/lib/alg/greedy-fas.js b/lib/alg/greedy-fas.js
@@ -0,0 +1,120 @@
+var _ = require("lodash"),
+    Digraph = require("../digraph"),
+    List = require("../data/List");
+
+/*
+ * A greedy heuristic for finding a feedback arc set for a graph. A feedback
+ * arc set is a set of edges that can be removed to make a graph acyclic.
+ * The algorithm comes from: P. Eades, X. Lin, and W. F. Smyth, "A fast and
+ * effective heuristic for the feedback arc set problem." This implementation
+ * adjusts that from the paper to allow for weighted edges.
+ */
+module.exports = greedyFAS;
+
+var DEFAULT_WEIGHT_FN = _.constant(1);
+
+function greedyFAS(g, weightFn) {
+  if (g.nodeCount() <= 1) {
+    return [];
+  }
+  return doGreedyFAS(buildGraph(g, weightFn || DEFAULT_WEIGHT_FN));
+}
+
+function doGreedyFAS(g) {
+  var results = [],
+      graphObj = g.getGraph(),
+      buckets = graphObj.buckets,
+      sources = buckets[buckets.length - 1],
+      sinks = buckets[0];
+
+  var node;
+  while (g.nodeCount()) {
+    while ((node = sinks.dequeue()))   { removeNode(g, node); }
+    while ((node = sources.dequeue())) { removeNode(g, node); }
+    if (g.nodeCount()) {
+      for (var i = buckets.length - 2; i > 0; --i) {
+        node = buckets[i].dequeue();
+        if (node) {
+          results = results.concat(removeNode(g, node, true));
+          break;
+        }
+      }
+    }
+  }
+
+  return results;
+}
+
+function removeNode(g, node, collectPredecessors) {
+  var results = collectPredecessors ? [] : undefined,
+      v = node.v;
+
+  _.each(g.inEdges(v), function(edge) {
+    var weight = edge.label,
+        uCtx = g.getNode(edge.v);
+
+    if (collectPredecessors) {
+      results.push({ v: edge.v, w: edge.w });
+    }
+
+    uCtx.out -= weight;
+    assignBucket(g.getGraph(), uCtx);
+  });
+
+  _.each(g.outEdges(v), function(edge) {
+    var weight = edge.label,
+        wCtx = g.getNode(edge.w);
+    wCtx.in -= weight;
+    assignBucket(g.getGraph(), wCtx);
+  });
+
+  g.removeNode(v);
+
+  return results;
+}
+
+function buildGraph(g, weightFn) {
+  var fasGraph = new Digraph(),
+      graphObj = {},
+      maxIn = 0,
+      maxOut = 0;
+
+  fasGraph.setGraph(graphObj);
+
+  _.each(g.nodeIds(), function(v) {
+    fasGraph.setNode(v, { v: v, in: 0, out: 0 });
+  });
+
+  _.each(g.edges(), function(edge) {
+    var weight = weightFn(edge);
+    fasGraph.setEdge(edge.v, edge.w, weight);
+    fasGraph.updateNode(edge.v, function(label) {
+      label.out += weight;
+      maxOut = Math.max(maxOut, label.out);
+      return label;
+    });
+    fasGraph.updateNode(edge.w, function(label) {
+      label.in += weight;
+      maxIn = Math.max(maxIn, label.in);
+      return label;
+    });
+  });
+
+  graphObj.buckets = _.range(maxOut + maxIn + 3).map(function() { return new List(); });
+  graphObj.zeroIdx = maxIn + 1;
+
+  _.each(fasGraph.nodes(), function(node) { assignBucket(graphObj, node.label); });
+
+  return fasGraph;
+}
+
+function assignBucket(graphState, node) {
+  var buckets = graphState.buckets;
+  if (!node.out) {
+    buckets[0].enqueue(node);
+  } else if (!node.in) {
+    buckets[buckets.length - 1].enqueue(node);
+  } else {
+    buckets[node.out - node.in + graphState.zeroIdx].enqueue(node);
+  }
+}
diff --git a/lib/alg/index.js b/lib/alg/index.js
@@ -4,6 +4,7 @@ module.exports = {
   dijkstraAll: require("./dijkstra-all"),
   findCycles: require("./find-cycles"),
   floydWarshall: require("./floyd-warshall"),
+  greedyFAS: require("./greedy-fas"),
   isAcyclic: require("./is-acyclic"),
   postorder: require("./postorder"),
   preorder: require("./preorder"),

diff --git a/src/bench.js b/src/bench.js
@@ -171,6 +171,10 @@ NODE_SIZES.forEach(function(size) {
     alg.dijkstraAll(g);
   });
 
+  runBenchmark("greedyFAS" + nameSuffix, function() {
+    alg.greedyFAS(g);
+  });
+
   runBenchmark("copy" + nameSuffix, function() {
     g.copy();
   });

diff --git a/test/alg/greedy-fas-test.js b/test/alg/greedy-fas-test.js
@@ -0,0 +1,83 @@
+var _ = require("lodash"),
+    expect = require("../chai").expect,
+    Digraph = require("../..").Digraph,
+    greedyFAS = require("../..").alg.greedyFAS,
+    findCycles = require("../..").alg.findCycles,
+    util = require("../../lib/util");
+
+describe("alg.greedyFAS", function() {
+  it("returns the empty set for empty and single-node graphs", function() {
+    expect(greedyFAS(new Digraph())).to.eql([]);
+    expect(greedyFAS(new Digraph().setNode("n1"))).to.eql([]);
+  });
+
+  it("returns an empty set if the input graph is acyclic", function() {
+    var g = new Digraph();
+    g.setEdge("n1", "n2");
+    g.setEdge("n2", "n3");
+    g.setEdge("n2", "n4");
+    g.setEdge("n1", "n5");
+    expect(greedyFAS(g)).to.eql([]);
+  });
+
+  it("returns a single edge with a simple cycle", function() {
+    var g = new Digraph();
+    g.setEdge("n1", "n2");
+    g.setEdge("n2", "n1");
+    checkFAS(g, greedyFAS(g));
+  });
+
+  it("returns a single edge in a 4-node cycle", function() {
+    var g = new Digraph();
+    g.setEdge("n1", "n2");
+    g.setPath(["n2", "n3", "n4", "n5", "n2"]);
+    g.setEdge("n3", "n5");
+    g.setEdge("n4", "n2");
+    g.setEdge("n4", "n6");
+    checkFAS(g, greedyFAS(g));
+  });
+
+  it("returns two edges for two 4-node cycles", function() {
+    var g = new Digraph();
+    g.setEdge("n1", "n2");
+    g.setPath(["n2", "n3", "n4", "n5", "n2"]);
+    g.setEdge("n3", "n5");
+    g.setEdge("n4", "n2");
+    g.setEdge("n4", "n6");
+    g.setPath(["n6", "n7", "n8", "n9", "n6"]);
+    g.setEdge("n7", "n9");
+    g.setEdge("n8", "n6");
+    g.setEdge("n8", "n10");
+    checkFAS(g, greedyFAS(g));
+  });
+
+  it("works with arbitrarily weighted edges", function() {
+    // Our algorithm should also work for graphs with multi-edges, a graph
+    // where more than one edge can be pointing in the same direction between
+    // the same pair of incident nodes. We try this by assigning weights to
+    // our edges representing the number of edges from one node to the other.
+
+    var g1 = new Digraph();
+    g1.setEdge("n1", "n2", 2);
+    g1.setEdge("n2", "n1", 1);
+    expect(greedyFAS(g1, util.LABEL_WEIGHT_FUNC)).to.eql([{v: "n2", w: "n1"}]);
+
+    var g2 = new Digraph();
+    g2.setEdge("n1", "n2", 1);
+    g2.setEdge("n2", "n1", 2);
+    expect(greedyFAS(g2, util.LABEL_WEIGHT_FUNC)).to.eql([{v: "n1", w: "n2"}]);
+  });
+});
+
+function checkFAS(g, fas) {
+  var n = g.nodeCount(),
+      m = g.edgeCount();
+  _.each(fas, function(edge) {
+    g.removeEdge(edge.v, edge.w);
+  });
+  expect(findCycles(g)).to.eql([]);
+  // The more direct m/2 - n/6 fails for the simple cycle A <-> B, where one
+  // edge must be reversed, but the performance bound implies that only 2/3rds
+  // of an edge can be reversed. I'm using floors to acount for this.
+  expect(fas.length).to.be.lte(Math.floor(m/2) - Math.floor(n/6));
+}