dagre - npm Package Compare versions

Comparing version 0.4.5 to 0.4.6

lib/debug.js

+'use strict';
+
+var util = require('./util');
+
+/**
+ * Renders a graph in a stringified DOT format that indicates the ordering of
+ * nodes by layer. Circles represent normal nodes. Diamons represent dummy
+ * nodes. While we try to put nodes in clusters, it appears that graphviz
+ * does not respect this because we're later using subgraphs for ordering nodes
+ * in each layer.
+ */
+exports.dotOrdering = function(g) {
+  var ordering = util.ordering(g.filterNodes(util.filterNonSubgraphs(g)));
+  var result = 'digraph {';
+
+  function dfs(u) {
+    var children = g.children(u);
+    if (children.length) {
+      result += 'subgraph cluster_' + u + ' {';
+      result += 'label="' + u + '";';
+      children.forEach(function(v) {
+        dfs(v);
+      });
+      result += '}';
+    } else {
+      result += u;
+      if (g.node(u).dummy) {
+        result += ' [shape=diamond]';
+      }
+      result += ';';
+    }
+  }
+
+  g.children(null).forEach(dfs);
+
+  ordering.forEach(function(layer) {
+    result += 'subgraph { rank=same; edge [style="invis"];';
+    result += layer.join('->');
+    result += '}';
+  });
+
+  g.eachEdge(function(e, u, v) {
+    result += u + '->' + v + ';';
+  });
+
+  result += '}';
+
+  return result;
+};

.jshintrc

@@ -7,3 +7,4 @@ {
     "trailing": true,
-    "laxbreak": true
+    "laxbreak": true,
+    "node": true
 }

.travis.yml

@@ -6,2 +6,2 @@ language: node_js
 script: make test
-before_script: npm install -g grunt-cli
+before_install: npm update -g npm

CHANGELOG.md

@@ -0,1 +1,6 @@
+v0.4.6
+======
+
+* Bug fixes
+
 v0.4.5
@@ -2,0 +7,0 @@ ======

index.js

@@ -26,1 +26,2 @@ /*
 exports.version = require("./lib/version");
+exports.debug = require("./lib/debug");

lib/layout.js

@@ -0,1 +1,3 @@
+'use strict';
+
 var util = require('./util'),
@@ -2,0 +4,0 @@ rank = require('./rank'),

lib/order.js

@@ -0,1 +1,3 @@
+'use strict';
+
 var util = require('./util'),
@@ -103,3 +105,3 @@ crossCount = require('./order/crossCount'),
   var cg;
-  for (i = 1; i < layerGraphs.length; ++i) {
+  for (var i = 1; i < layerGraphs.length; ++i) {
     cg = sortLayer(layerGraphs[i], cg, predecessorWeights(g, layerGraphs[i].nodes()));
@@ -111,5 +113,5 @@ }
   var cg;
-  for (i = layerGraphs.length - 2; i >= 0; --i) {
+  for (var i = layerGraphs.length - 2; i >= 0; --i) {
     sortLayer(layerGraphs[i], cg, successorWeights(g, layerGraphs[i].nodes()));
   }
 }

lib/order/crossCount.js

@@ -0,1 +1,3 @@
+'use strict';
+
 var util = require('../util');
@@ -2,0 +4,0 @@

lib/order/initLayerGraphs.js

@@ -0,1 +1,3 @@
+'use strict';
+
 var nodesFromList = require('graphlib').filter.nodesFromList,
@@ -2,0 +4,0 @@ /* jshint -W079 */

lib/order/initOrder.js

@@ -0,1 +1,3 @@
+'use strict';
+
 var crossCount = require('./crossCount'),
@@ -2,0 +4,0 @@ util = require('../util');

lib/order/sortLayer.js

@@ -1,13 +0,14 @@
-var util = require('../util');
-/*
+'use strict';
+
+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) {
+  weights = adjustWeights(g, weights);
   var result = sortLayerSubgraph(g, null, cg, weights);
+
   result.list.forEach(function(u, i) {
@@ -18,30 +19,3 @@ g.node(u).order = i;
 }
-*/
 
-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) {
@@ -60,3 +34,5 @@ cg = cg ? cg.filterNodes(nodesFromList(g.children(sg))) : new Digraph();
         degree: ws.length,
-        barycenter: ws.length > 0 ? util.sum(ws) / ws.length : 0,
+        barycenter: util.sum(ws) / ws.length,
+        order: g.node(u).order,
+        orderCount: 1,
         list: [u]
@@ -71,3 +47,4 @@ };
   keys.sort(function(x, y) {
-    return nodeData[x].barycenter - nodeData[y].barycenter;
+    return nodeData[x].barycenter - nodeData[y].barycenter ||
+           nodeData[x].order - nodeData[y].order;
   });
@@ -80,3 +57,2 @@
 
-/*
 function mergeNodeData(g, lhs, rhs) {
@@ -98,2 +74,5 @@ var cg = mergeDigraphs(lhs.constraintGraph, rhs.constraintGraph);
                 (lhs.degree + rhs.degree),
+    order: (lhs.order * lhs.orderCount + rhs.order * rhs.orderCount) /
+           (lhs.orderCount + rhs.orderCount),
+    orderCount: lhs.orderCount + rhs.orderCount,
     list: lhs.list.concat(rhs.list),
@@ -168,2 +147,39 @@ firstSG: lhs.firstSG !== undefined ? lhs.firstSG : rhs.firstSG,
 }
-*/
+
+// Adjust weights so that they fall in the range of 0..|N|-1. If a node has no
+// weight assigned then set its adjusted weight to its current position. This
+// allows us to better retain the origiinal position of nodes without neighbors.
+function adjustWeights(g, weights) {
+  var minW = Number.MAX_VALUE,
+      maxW = 0,
+      adjusted = {};
+  g.eachNode(function(u) {
+    if (g.children(u).length) return;
+
+    var ws = weights[u];
+    if (ws.length) {
+      minW = Math.min(minW, util.min(ws));
+      maxW = Math.max(maxW, util.max(ws));
+    }
+  });
+
+  var rangeW = (maxW - minW);
+  g.eachNode(function(u) {
+    if (g.children(u).length) return;
+
+    var ws = weights[u];
+    if (!ws.length) {
+      adjusted[u] = [g.node(u).order];
+    } else {
+      adjusted[u] = ws.map(function(w) {
+        if (rangeW) {
+          return (w - minW) * (g.order() - 1) / rangeW;
+        } else {
+          return g.order() - 1 / 2;
+        }
+      });
+    }
+  });
+
+  return adjusted;
+}

lib/position.js

@@ -0,1 +1,3 @@
+'use strict';
+
 var util = require('./util');
@@ -2,0 +4,0 @@

lib/rank.js

@@ -0,1 +1,3 @@
+'use strict';
+
 var util = require('./util'),
@@ -2,0 +4,0 @@ acyclic = require('./rank/acyclic'),

lib/rank/acyclic.js

@@ -0,1 +1,3 @@
+'use strict';
+
 var util = require('../util');
@@ -2,0 +4,0 @@

lib/rank/buildWeightGraph.js

@@ -0,1 +1,3 @@
+'use strict';
+
 var Digraph = require('graphlib').Digraph;
@@ -2,0 +4,0 @@

lib/rank/constraints.js

@@ -0,1 +1,3 @@
+'use strict';
+
 exports.apply = function(g) {
@@ -2,0 +4,0 @@ function dfs(sg) {

lib/rank/feasibleTree.js

@@ -0,1 +1,3 @@
+'use strict';
+
 /* jshint -W079 */
@@ -2,0 +4,0 @@ var Set = require('cp-data').Set,

lib/rank/initRank.js

@@ -0,1 +1,3 @@
+'use strict';
+
 var util = require('../util'),
@@ -2,0 +4,0 @@ topsort = require('graphlib').alg.topsort;

lib/rank/rankUtil.js

@@ -0,1 +1,3 @@
+'use strict';
+
 module.exports = {
@@ -2,0 +4,0 @@ slack: slack

lib/rank/simplex.js

@@ -0,1 +1,3 @@
+'use strict';
+
 var util = require('../util'),
@@ -2,0 +4,0 @@ rankUtil = require('./rankUtil');

lib/util.js

@@ -0,1 +1,3 @@
+'use strict';
+
 /*
@@ -44,3 +46,3 @@ * Returns the smallest value in the array.
 exports.shuffle = function(array) {
-  for (i = array.length - 1; i > 0; --i) {
+  for (var i = array.length - 1; i > 0; --i) {
     var j = Math.floor(Math.random() * (i + 1));
@@ -47,0 +49,0 @@ var aj = array[j];

lib/version.js

@@ -1,1 +0,1 @@
-module.exports = '0.4.5';
+module.exports = '0.4.6';

package.json

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

README.md

@@ -260,3 +260,3 @@ # dagre - Graph layout for JavaScript
 Dagre has been included as a part of some very cool projects. Here are just a
-couple that stand out:
+few that stand out:
 
@@ -273,2 +273,6 @@ [JointJS][] has a plugin that uses dagre for layout. JointJS focuses on
 
+[nomnoml](http://www.nomnoml.com/) is a tool for drawing UML diagrams in a
+browser. It uses a custom renderer with dagre to draw the diagrams in an
+HTML5 canvas.
+
 ## License
@@ -275,0 +279,0 @@

New alerts

Long strings

Supply chain risk

Contains long string literals, which may be a sign of obfuscated or packed code.

Found 1 instance in 1 package

Fixed alerts

Long strings

Supply chain risk

Contains long string literals, which may be a sign of obfuscated or packed code.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

80427

2.92%

Number of package files

26

4%

Lines of code

1945

3.68%

Number of lines in readme file

284

1.43%

No dependency changes