dagre - npm Package Compare versions

Comparing version 0.3.2 to 0.3.3

CHANGELOG.md

@@ -0,1 +1,6 @@
+v0.3.3
+======
+
+* Temporarily disable cluster orderer, yielding much better ordering results.
+
 v0.3.2
@@ -2,0 +7,0 @@ ======

lib/layout.js

@@ -16,3 +16,5 @@ var util = require("./util"),
     // Max number of sweeps to perform in order phase
-    orderMaxSweeps: order.DEFAULT_MAX_SWEEPS
+    orderMaxSweeps: order.DEFAULT_MAX_SWEEPS,
+    // Use network simplex algorithm in ranking
+    rankSimplex: false
   };
@@ -28,2 +30,4 @@
 
+  self.rankSimplex = util.propertyAccessor(self, config, "rankSimplex");
+
   self.nodeSep = delegateProperty(position.nodeSep);
@@ -136,3 +140,3 @@ self.edgeSep = delegateProperty(position.edgeSep);
       // above nodes of higher rank.
-      util.time(rank)(g);
+      util.time(rank)(g, config.rankSimplex);
 
@@ -139,0 +143,0 @@ // Normalize the graph by ensuring that every edge is proper (each edge has

lib/order.js

@@ -24,2 +24,7 @@ var util = require("./util"),
   var layerGraphs = initLayerGraphs(g);
+  // TODO: remove this when we add back support for ordering clusters
+  layerGraphs.forEach(function(lg) {
+    lg = lg.filterNodes(function(u) { return !g.children(u).length; });
+  });
+
   initOrder(g);
@@ -26,0 +31,0 @@

lib/order/sortLayer.js

@@ -1,8 +0,11 @@
-var util = require("../util"),
+var util = require("../util");
+/*
     Digraph = require("graphlib").Digraph,
     topsort = require("graphlib").alg.topsort,
     nodesFromList = require("graphlib").filter.nodesFromList;
+*/
 
 module.exports = sortLayer;
 
+/*
 function sortLayer(g, cg, weights) {
@@ -15,3 +18,30 @@ var result = sortLayerSubgraph(g, null, cg, weights);
 }
+*/
 
+function sortLayer(g, cg, weights) {
+  var ordering = [];
+  var bs = {};
+  g.eachNode(function(u, value) {
+    ordering[value.order] = u;
+    var ws = weights[u];
+    if (ws.length) {
+      bs[u] = util.sum(ws) / ws.length;
+    }
+  });
+
+  var toSort = g.nodes().filter(function(u) { return bs[u] !== undefined; });
+  toSort.sort(function(x, y) {
+    return bs[x] - bs[y] || g.node(x).order - g.node(y).order;
+  });
+
+  for (var i = 0, j = 0, jl = toSort.length; j < jl; ++i) {
+    if (bs[ordering[i]] !== undefined) {
+      g.node(toSort[j++]).order = i;
+    }
+  }
+}
+
+// TOOD: re-enable constrained sorting once we have a strategy for handling
+// undefined barycenters.
+/*
 function sortLayerSubgraph(g, sg, cg, weights) {
@@ -48,2 +78,3 @@ cg = cg ? cg.filterNodes(nodesFromList(g.children(sg))) : new Digraph();
 
+/*
 function mergeNodeData(g, lhs, rhs) {
@@ -134,1 +165,2 @@ var cg = mergeDigraphs(lhs.constraintGraph, rhs.constraintGraph);
 }
+*/

lib/rank.js

@@ -1,12 +0,22 @@
-/* jshint -W079 */
 var util = require("./util"),
     acyclic = require("./acyclic"),
+    initRank = require("./rank/initRank"),
+    feasibleTree = require("./rank/feasibleTree"),
+    simplex = require("./rank/simplex"),
     components = require("graphlib").alg.components,
-    filter = require("graphlib").filter,
-    PriorityQueue = require("cp-data").PriorityQueue,
-    Set = require("cp-data").Set;
+    filter = require("graphlib").filter;
 
 module.exports = rank;
 
-function rank(g) {
+/*
+ * Heuristic function that assigns a rank to each node of the input graph with
+ * the intent of minimizing edge lengths, while respecting the `minLen`
+ * attribute of incident edges.
+ *
+ * Prerequisites:
+ *
+ *  * Input graph must be acyclic
+ *  * Each edge in the input graph must have an assigned 'minLen' attribute
+ */
+function rank(g, useSimplex) {
   var reduced = combineRanks(g.filterNodes(util.filterNonSubgraphs(g)));
@@ -18,3 +28,8 @@
     var subgraph = reduced.filterNodes(filter.nodesFromList(cmpt));
-    feasibleTree(subgraph);
+    var spanningTree = feasibleTree(subgraph);
+
+    if (useSimplex) {
+      util.log(1, "Using network simplex for ranking");
+      simplex(subgraph, spanningTree);
+    }
     normalize(subgraph);
@@ -64,7 +79,8 @@ });
       g.inEdges(u).forEach(function(e) {
+        var value = { minLen: g.edge(e).minLen };
         if (rank === "min") {
           // Ensure that all edges to min are reversed
-          g.addEdge(null, newU, g.source(e), { minLen: g.edge(e).minLen || 1 });
+          g.addEdge(null, newU, g.source(e), value);
         } else {
-          g.addEdge(null, g.source(e), newU, { minLen: g.edge(e).minLen || 1 });
+          g.addEdge(null, g.source(e), newU, value);
         }
@@ -74,7 +90,8 @@ g.delEdge(e);
       g.outEdges(u).forEach(function(e) {
+        var value = { minLen: g.edge(e).minLen };
         if (rank === "max") {
           // Ensure that all edges from max are reversed
-          g.addEdge(null, g.target(e), newU, { minLen: g.edge(e).minLen || 1 });
+          g.addEdge(null, g.target(e), newU, value);
         } else {
-          g.addEdge(null, newU, g.target(e), { minLen: g.edge(e).minLen || 1 });
+          g.addEdge(null, newU, g.target(e), value);
         }
@@ -121,84 +138,2 @@ g.delEdge(e);
 
-function initRank(g) {
-  var minRank = {};
-  var pq = new PriorityQueue();
-
-  g.eachNode(function(u) {
-    pq.add(u, g.inEdges(u).length);
-    minRank[u] = 0;
-  });
-
-  function updateTargetNode(e) {
-    var rank = g.node(g.source(e)).rank;
-    var target = g.target(e);
-    var value = g.edge(e);
-    var minLen = "minLen" in value ? value.minLen : 1;
-    minRank[target] = Math.max(minRank[target], rank + minLen);
-    pq.decrease(target, pq.priority(target) - 1);
-  }
-
-  while (pq.size() > 0) {
-    var minId = pq.min();
-    if (pq.priority(minId) > 0) {
-      throw new Error("Input graph is not acyclic: " + g.toString());
-    }
-    pq.removeMin();
-
-    var rank = minRank[minId];
-    g.node(minId).rank = rank;
-
-    g.outEdges(minId).forEach(updateTargetNode);
-  }
-}
-
-function feasibleTree(g) {
-  var remaining = new Set(g.nodes()),
-      minLen = []; // Array of {u, v, len}
-
-  // Collapse multi-edges and precompute the minLen, which will be the
-  // max value of minLen for any edge in the multi-edge.
-  var minLenMap = {};
-  g.eachEdge(function(e, u, v, edge) {
-    var id = incidenceId(u, v);
-    if (!(id in minLenMap)) {
-      minLen.push(minLenMap[id] = { u: u, v: v, len: 0 });
-    }
-    minLenMap[id].len = Math.max(minLenMap[id].len, ("minLen" in edge ? edge.minLen : 1));
-  });
-
-  function slack(mle /* minLen entry*/) {
-    return Math.abs(g.node(mle.u).rank - g.node(mle.v).rank) - mle.len;
-  }
-
-  // Remove arbitrary node - it is effectively the root of the spanning tree.
-  remaining.remove(g.nodes()[0]);
-
-  // Finds the next edge with the minimum slack.
-  function findMinSlack() {
-    var result,
-        eSlack = Number.POSITIVE_INFINITY;
-    minLen.forEach(function(mle /* minLen entry */) {
-      if (remaining.has(mle.u) !== remaining.has(mle.v)) {
-        var mleSlack = slack(mle);
-        if (mleSlack < eSlack) {
-          if (!remaining.has(mle.u)) {
-            result = { treeNode: mle.u, graphNode: mle.v, len: mle.len};
-          } else {
-            result = { treeNode: mle.v, graphNode: mle.u, len: -mle.len };
-          }
-          eSlack = mleSlack;
-        }
-      }
-    });
-
-    return result;
-  }
-
-  while (remaining.size() > 0) {
-    var result = findMinSlack();
-    remaining.remove(result.graphNode);
-    g.node(result.graphNode).rank = g.node(result.treeNode).rank + result.len;
-  }
-}
-
 /*
@@ -225,9 +160,1 @@ * When handling nodes with constrained ranks it is possible to end up with
 }
-
-/*
- * This id can be used to group (in an undirected manner) multi-edges
- * incident on the same two nodes.
- */
-function incidenceId(u, v) {
-  return u < v ?  u.length + ":" + u + "-" + v : v.length + ":" + v + "-" + u;
-}

lib/version.js

@@ -1,1 +0,1 @@
-module.exports = '0.3.2';
+module.exports = '0.3.3';

package.json

 {
   "name": "dagre",
-  "version": "0.3.2",
+  "version": "0.3.3",
   "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

71446

increased by24.37%

Number of package files

24

increased by26.32%

Lines of code

1753

increased by33.11%

No dependency changes