dagre - npm Package Compare versions

Comparing version 0.4.1 to 0.4.2

CHANGELOG.md

@@ -0,1 +1,7 @@
+v0.4.2
+======
+
+* More fixes to ranker.
+* Introduce experimental orderRestarts feature, which yields reduce crossing counts. See 72128a71d4ece45d4932da44e07ba692b0da5a1c for details.
+
 v0.4.1
@@ -2,0 +8,0 @@ ======

lib/layout.js

@@ -98,3 +98,4 @@ var util = require('./util'),
     g.graph({
-      rankDir: graphValue.rankDir || config.rankDir
+      rankDir: graphValue.rankDir || config.rankDir,
+      orderRestarts: graphValue.orderRestarts
     });
@@ -101,0 +102,0 @@

lib/order.js

@@ -23,2 +23,4 @@ var util = require('./util'),
 
+  var restarts = g.graph().orderRestarts || 0;
+
   var layerGraphs = initLayerGraphs(g);
@@ -30,18 +32,41 @@ // TODO: remove this when we add back support for ordering clusters
 
-  initOrder(g);
+  var iters = 0,
+      currentBestCC,
+      allTimeBestCC = Number.MAX_VALUE,
+      allTimeBest = {};
 
-  util.log(2, 'Order phase start cross count: ' + g.graph().orderInitCC);
+  function saveAllTimeBest() {
+    g.eachNode(function(u, value) { allTimeBest[u] = value.order; });
+  }
 
-  var i, lastBest;
-  for (i = 0, lastBest = 0; lastBest < 4 && i < maxSweeps; ++i, ++lastBest) {
-    sweep(g, layerGraphs, i);
-    if (saveBest(g)) {
-      lastBest = 0;
+  for (var j = 0; j < Number(restarts) + 1 && allTimeBestCC !== 0; ++j) {
+    currentBestCC = Number.MAX_VALUE;
+    initOrder(g, restarts > 0);
+
+    util.log(2, 'Order phase start cross count: ' + g.graph().orderInitCC);
+
+    var i, lastBest, cc;
+    for (i = 0, lastBest = 0; lastBest < 4 && i < maxSweeps && currentBestCC > 0; ++i, ++lastBest, ++iters) {
+      sweep(g, layerGraphs, i);
+      cc = crossCount(g);
+      if (cc < currentBestCC) {
+        lastBest = 0;
+        currentBestCC = cc;
+        if (cc < allTimeBestCC) {
+          saveAllTimeBest();
+          allTimeBestCC = cc;
+        }
+      }
+      util.log(3, 'Order phase start ' + j + ' iter ' + i + ' cross count: ' + cc);
     }
-    util.log(3, 'Order phase iter ' + i + ' cross count: ' + g.graph().orderCC);
   }
 
-  restoreBest(g);
+  Object.keys(allTimeBest).forEach(function(u) {
+    if (!g.children || !g.children(u).length) {
+      g.node(u).order = allTimeBest[u];
+    }
+  });
+  g.graph().orderCC = allTimeBestCC;
 
-  util.log(2, 'Order iterations: ' + i);
+  util.log(2, 'Order iterations: ' + iters);
   util.log(2, 'Order phase best cross count: ' + g.graph().orderCC);
@@ -91,37 +116,1 @@ }
 }
-
-/*
- * Checks if the current ordering of the graph has a lower cross count than the
- * current best. If so, saves the ordering of the current nodes and the new
- * best cross count. This can be used with restoreBest to restore the last best
- * ordering.
- *
- * If this is the first time running the function the current ordering will be
- * assumed as the best.
- *
- * Returns `true` if this layout represents a new best.
- */
-function saveBest(g) {
-  var graph = g.graph();
-  var cc = crossCount(g);
-  if (!('orderCC' in graph) || graph.orderCC > cc) {
-    graph.orderCC = cc;
-    graph.order = {};
-    g.eachNode(function(u, value) {
-      if ('order' in value) {
-        graph.order[u] = value.order;
-      }
-    });
-    return true;
-  }
-  return false;
-}
-
-function restoreBest(g) {
-  var order = g.graph().order;
-  g.eachNode(function(u, value) {
-    if ('order' in value) {
-      value.order = order[u];
-    }
-  });
-}

lib/order/initOrder.js

@@ -1,2 +0,3 @@
-var crossCount = require('./crossCount');
+var crossCount = require('./crossCount'),
+    util = require('../util');
 
@@ -11,15 +12,23 @@ module.exports = initOrder;
  */
-function initOrder(g) {
-  var orderCount = [];
+function initOrder(g, random) {
+  var layers = [];
 
-  function addNode(u, value) {
-    if ('order' in value) return;
+  g.eachNode(function(u, value) {
+    var layer = layers[value.rank];
     if (g.children && g.children(u).length > 0) return;
-    if (!(value.rank in orderCount)) {
-      orderCount[value.rank] = 0;
+    if (!layer) {
+      layer = layers[value.rank] = [];
     }
-    value.order = orderCount[value.rank]++;
-  }
+    layer.push(u);
+  });
 
-  g.eachNode(function(u, value) { addNode(u, value); });
+  layers.forEach(function(layer) {
+    if (random) {
+      util.shuffle(layer);
+    }
+    layer.forEach(function(u, i) {
+      g.node(u).order = i;
+    });
+  });
+
   var cc = crossCount(g);
@@ -26,0 +35,0 @@ g.graph().orderInitCC = cc;

lib/rank/feasibleTree.js

@@ -45,4 +45,5 @@ /* jshint -W079 */
   function addTightEdges(v) {
+    var continueToScan = true;
     g.predecessors(v).forEach(function(u) {
-      if (remaining.has(u) && slack(g, u, v) === 0) {
+      if (remaining.has(u) && !slack(g, u, v)) {
         if (remaining.has(v)) {
@@ -58,2 +59,3 @@ tree.addNode(v, {});
         addTightEdges(u);
+        continueToScan = false;
       }
@@ -63,3 +65,3 @@ });
     g.successors(v).forEach(function(w)  {
-      if (remaining.has(w) && slack(g, v, w) === 0) {
+      if (remaining.has(w) && !slack(g, v, w)) {
         if (remaining.has(v)) {
@@ -75,4 +77,6 @@ tree.addNode(v, {});
         addTightEdges(w);
+        continueToScan = false;
       }
     });
+    return continueToScan;
   }
@@ -84,5 +88,7 @@
       g.predecessors(v).forEach(function(u) {
-        var edgeSlack = slack(g, u, v);
-        if (Math.abs(edgeSlack) < Math.abs(minSlack)) {
-          minSlack = -edgeSlack;
+        if (!remaining.has(u)) {
+          var edgeSlack = slack(g, u, v);
+          if (Math.abs(edgeSlack) < Math.abs(minSlack)) {
+            minSlack = -edgeSlack;
+          }
         }
@@ -92,5 +98,7 @@ });
       g.successors(v).forEach(function(w) {
-        var edgeSlack = slack(g, v, w);
-        if (Math.abs(edgeSlack) < Math.abs(minSlack)) {
-          minSlack = edgeSlack;
+        if (!remaining.has(w)) {
+          var edgeSlack = slack(g, v, w);
+          if (Math.abs(edgeSlack) < Math.abs(minSlack)) {
+            minSlack = edgeSlack;
+          }
         }
@@ -105,3 +113,5 @@ });
     var nodesToSearch = !tree.order() ? remaining.keys() : tree.nodes();
-    nodesToSearch.forEach(addTightEdges);
+    for (var i = 0, il = nodesToSearch.length;
+         i < il && addTightEdges(nodesToSearch[i]);
+         ++i);
     if (remaining.size()) {
@@ -108,0 +118,0 @@ createTightEdge();

lib/util.js

@@ -43,2 +43,11 @@ /*
 
+exports.shuffle = function(array) {
+  for (i = array.length - 1; i > 0; --i) {
+    var j = Math.floor(Math.random() * (i + 1));
+    var aj = array[j];
+    array[j] = array[i];
+    array[i] = aj;
+  }
+};
+
 exports.propertyAccessor = function(self, config, field, setHook) {
@@ -45,0 +54,0 @@ return function(x) {

lib/version.js

@@ -1,1 +0,1 @@
-module.exports = '0.4.1';
+module.exports = '0.4.2';

package.json

 {
   "name": "dagre",
-  "version": "0.4.1",
+  "version": "0.4.2",
   "description": "Graph layout for JavaScript",
@@ -5,0 +5,0 @@ "main": "index.js",

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

77092

increased by0.9%

Lines of code

1847

increased by0.82%

No dependency changes