dagre - npm Package Compare versions

Comparing version 0.3.3 to 0.3.4

CHANGELOG.md

@@ -0,1 +1,10 @@
+v0.3.4
+======
+
+* Fix a bug in instrumentation that caused dagre to throw an exception when
+  used with IE.
+* Rank constraint values may be one of 'min', 'max', or a value that starts
+  with 'same\_'. The latter groups all nodes with the same value into the same
+  rank.
+
 v0.3.3
@@ -2,0 +11,0 @@ ======

lib/acyclic.js

@@ -6,3 +6,3 @@ var util = require("./util");
 
-function acyclic(g, saveSelfLoops) {
+function acyclic(g) {
   var onStack = {},
@@ -17,7 +17,5 @@ visited = {},
 
-  if (saveSelfLoops) {
-    selfLoops = g.graph()._acyclicSelfLoops;
-    if (selfLoops === undefined) {
-      selfLoops = g.graph()._acyclicSelfLoops = [];
-    }
+  selfLoops = g.graph()._acyclicSelfLoops;
+  if (selfLoops === undefined) {
+    selfLoops = g.graph()._acyclicSelfLoops = [];
   }
@@ -33,5 +31,3 @@
       if (u === t) {
-        if (saveSelfLoops) {
-          selfLoops.push({ e: e, u: u, v: t, value: g.edge(e) });
-        }
+        selfLoops.push({ e: e, u: u, v: t, value: g.edge(e) });
         g.delEdge(e);
@@ -38,0 +34,0 @@ } else if (t in onStack) {

lib/layout.js

@@ -1,9 +0,7 @@
-var util = require("./util"),
-    rank = require("./rank"),
-    acyclic = require("./acyclic"),
-    order = require("./order"),
-    CGraph = require("graphlib").CGraph,
-    CDigraph = require("graphlib").CDigraph,
-    /* jshint -W079 */
-    Set = require("cp-data").Set;
+var util = require('./util'),
+    rank = require('./rank'),
+    acyclic = require('./acyclic'),
+    order = require('./order'),
+    CGraph = require('graphlib').CGraph,
+    CDigraph = require('graphlib').CDigraph;
 
@@ -22,3 +20,3 @@ module.exports = function() {
   // Phase functions
-  var position = require("./position")();
+  var position = require('./position')();
 
@@ -28,5 +26,5 @@ // This layout object
 
-  self.orderIters = util.propertyAccessor(self, config, "orderMaxSweeps");
+  self.orderIters = util.propertyAccessor(self, config, 'orderMaxSweeps');
 
-  self.rankSimplex = util.propertyAccessor(self, config, "rankSimplex");
+  self.rankSimplex = util.propertyAccessor(self, config, 'rankSimplex');
 
@@ -40,3 +38,3 @@ self.nodeSep = delegateProperty(position.nodeSep);
 
-  self.debugLevel = util.propertyAccessor(self, config, "debugLevel", function(x) {
+  self.debugLevel = util.propertyAccessor(self, config, 'debugLevel', function(x) {
     util.log.level = x;
@@ -46,3 +44,3 @@ position.debugLevel(x);
 
-  self.run = util.time("Total layout", run);
+  self.run = util.time('Total layout', run);
 
@@ -75,3 +73,3 @@ self._normalize = normalize;
       });
-      if (value.hasOwnProperty("rank")) {
+      if (value.hasOwnProperty('rank')) {
         g.node(u).prefRank = value.rank;
@@ -99,8 +97,2 @@ }
       g.addEdge(null, u, v, newValue);
-
-      // If input graph is not directed, we create also add a reverse edge.
-      // After we've run the acyclic algorithm we'll remove one of these edges.
-      if (!inputGraph.isDirected()) {
-        g.addEdge(null, v, u, newValue);
-      }
     });
@@ -118,3 +110,3 @@
       // Build internal graph
-      g = util.time(initLayoutGraph)(inputGraph);
+      g = util.time('initLayoutGraph', initLayoutGraph)(inputGraph);
 
@@ -131,17 +123,5 @@ if (g.order() === 0) {
 
-      // Reverse edges to get an acyclic graph, we keep the graph in an acyclic
-      // state until the very end.
-      util.time(acyclic)(g);
-
-      // Our intermediate graph is always directed. However, the input graph
-      // may be undirected, so we create duplicate edges in opposite directions
-      // in the initLayoutGraph function. At this point one of each pair of
-      // edges was reversed, so we remove the redundant edge.
-      if (!inputGraph.isDirected()) {
-        removeDupEdges(g);
-      }
-
       // Determine the rank for each node. Nodes with a lower rank will appear
       // above nodes of higher rank.
-      util.time(rank)(g, config.rankSimplex);
+      util.time('rank', rank)(g, config.rankSimplex);
 
@@ -151,22 +131,22 @@ // Normalize the graph by ensuring that every edge is proper (each edge has
       // thus shortening them.
-      util.time(normalize)(g);
+      util.time('normalize', normalize)(g);
 
       // Order the nodes so that edge crossings are minimized.
-      util.time(order)(g, config.orderMaxSweeps);
+      util.time('order', order)(g, config.orderMaxSweeps);
 
       // Find the x and y coordinates for every node in the graph.
-      util.time("position", position.run)(g);
+      util.time('position', position.run)(g);
 
       // De-normalize the graph by removing dummy nodes and augmenting the
       // original long edges with coordinate information.
-      util.time(undoNormalize)(g);
+      util.time('undoNormalize', undoNormalize)(g);
 
       // Reverses points for edges that are in a reversed state.
-      util.time(fixupEdgePoints)(g);
+      util.time('fixupEdgePoints', fixupEdgePoints)(g);
 
       // Reverse edges that were revered previously to get an acyclic graph.
-      util.time("acyclic.undo", acyclic.undo)(g);
+      util.time('acyclic.undo', acyclic.undo)(g);
 
       // Construct final result graph and return it
-      return util.time(createFinalGraph)(g, inputGraph.isDirected());
+      return util.time('createFinalGraph', createFinalGraph)(g, inputGraph.isDirected());
     } finally {
@@ -177,14 +157,4 @@ self.rankSep(rankSep);
 
-  function removeDupEdges(g) {
-    var visited = new Set();
-    g.eachEdge(function(e, u, v, value) {
-      if (visited.has(value.e)) {
-        g.delEdge(e);
-      }
-      visited.add(value.e);
-    });
-  }
-
   /*
-   * This function is responsible for "normalizing" the graph. The process of
+   * This function is responsible for 'normalizing' the graph. The process of
    * normalization ensures that no edge in the graph has spans more than one
@@ -204,3 +174,3 @@ * rank. To do this it inserts dummy nodes as needed and links them by adding
         for (var u = s, rank = sourceRank + 1, i = 0; rank < targetRank; ++rank, ++i) {
-          var v = "_D" + (++dummyCount);
+          var v = '_D' + (++dummyCount);
           var node = {
@@ -233,3 +203,3 @@ width: a.width,
    * Reconstructs the graph as it was before normalization. The positions of
-   * dummy nodes are used to build an array of points for the original "long"
+   * dummy nodes are used to build an array of points for the original 'long'
    * edge. Dummy nodes and edges are removed.
@@ -239,3 +209,3 @@ */
     g.eachNode(function(u, a) {
-      if (a.dummy && "index" in a) {
+      if (a.dummy && 'index' in a) {
         var edge = a.edge;
@@ -266,4 +236,3 @@ if (!g.hasEdge(edge.id)) {
     g.eachEdge(function(e, u, v, value) {
-      out.addEdge("e" in value ? value.e : e, u, v, value);
-      delete value.e;
+      out.addEdge(e, u, v, value);
     });
@@ -270,0 +239,0 @@ return out;

lib/rank.js

@@ -1,8 +0,8 @@
-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;
+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;
 
@@ -22,33 +22,35 @@ module.exports = rank;
 function rank(g, useSimplex) {
-  var reduced = combineRanks(g.filterNodes(util.filterNonSubgraphs(g)));
+  // If there are rank constraints on nodes, then build a new graph that
+  // encodes the constraints.
+  var constrainedGraph = util.time('constrainRanks', constrainRanks)(g.filterNodes(util.filterNonSubgraphs(g)));
 
-  initRank(reduced);
+  // Reverse edges to get an acyclic graph, we keep the graph in an acyclic
+  // state until the very end.
+  util.time('acyclic', acyclic)(constrainedGraph);
 
-  components(reduced).forEach(function(cmpt) {
-    var subgraph = reduced.filterNodes(filter.nodesFromList(cmpt));
-    var spanningTree = feasibleTree(subgraph);
+  // Assign an initial ranking using DFS.
+  initRank(constrainedGraph);
 
-    if (useSimplex) {
-      util.log(1, "Using network simplex for ranking");
-      simplex(subgraph, spanningTree);
-    }
-    normalize(subgraph);
+  // For each component improve the assigned ranks.
+  components(constrainedGraph).forEach(function(cmpt) {
+    var subgraph = constrainedGraph.filterNodes(filter.nodesFromList(cmpt));
+    rankComponent(subgraph, useSimplex);
   });
 
-  expandRanks(reduced, g);
+  // Update the layout graph with rakn information from the constrained graph.
+  util.time('applyConstrainedGraph', applyConstrainedGraph)(constrainedGraph, g);
 
-  orientEdges(g);
+  // When handling nodes with constrained ranks it is possible to end up with
+  // edges that point to previous ranks. Most of the subsequent algorithms assume
+  // that edges are pointing to successive ranks only. Here we reverse any "back
+  // edges" and mark them as such. The acyclic algorithm will reverse them as a
+  // post processing step.
+  util.time('reorientEdges', reorientEdges)(g);
 }
 
-/*
- * If there are rank constraints on nodes, then build a condensed graph,
- * with one node per rank set.  Modify edges to that the minimum rank
- * will be ranked before any others and the maximum rank will be ranked
- * after any others.
- */
-function combineRanks(g) {
+function constrainRanks(g) {
   var needsReduction = false,
       nodes = g.nodes();
   for (var i = 0, il = nodes.length; i < il; ++i) {
-    if ("prefRank" in g.node(nodes[i])) {
+    if ('prefRank' in g.node(nodes[i])) {
       needsReduction = true;
@@ -71,2 +73,6 @@ break;
     if (rank !== undefined) {
+      if (!checkSupportedPrefRank(rank)) {
+        return;
+      }
+
       newU = prefRankToNode[rank];
@@ -81,3 +87,3 @@ if (newU === undefined) {
         var value = { minLen: g.edge(e).minLen };
-        if (rank === "min") {
+        if (rank === 'min') {
           // Ensure that all edges to min are reversed
@@ -92,3 +98,3 @@ g.addEdge(null, newU, g.source(e), value);
         var value = { minLen: g.edge(e).minLen };
-        if (rank === "max") {
+        if (rank === 'max') {
           // Ensure that all edges from max are reversed
@@ -118,16 +124,17 @@ g.addEdge(null, g.target(e), newU, value);
 
-  acyclic(g, false);
-
   return g;
 }
 
-/*
- * If the argument graph was a reduced version of some original graph
- * then copy assigned ranks from it to the original.  Otherwise, the
- * ranks are already assigned.
- */
-function expandRanks(g, original) {
-  if (g.graph().compoundNodes) {
-    g.graph().compoundNodes.forEach(function(u) {
-      var value = g.node(u);
+function checkSupportedPrefRank(prefRank) {
+  if (prefRank !== 'min' && prefRank !== 'max' && prefRank.indexOf('same_') !== 0) {
+    console.error('Unsupported rank type: ' + prefRank);
+    return false;
+  }
+  return true;
+}
+
+function applyConstrainedGraph(constrained, original) {
+  if (constrained.graph().compoundNodes) {
+    constrained.graph().compoundNodes.forEach(function(u) {
+      var value = constrained.node(u);
       value.originalNodes.forEach(function(v) {
@@ -140,10 +147,3 @@ original.node(v).rank = value.rank;
 
-/*
- * When handling nodes with constrained ranks it is possible to end up with
- * edges that point to previous ranks. Most of the subsequent algorithms assume
- * that edges are pointing to successive ranks only. Here we reverse any "back
- * edges" and mark them as such. The acyclic algorithm will reverse them as a
- * post processing step.
- */
-function orientEdges(g) {
+function reorientEdges(g) {
   g.eachEdge(function(e, u, v, value) {
@@ -158,2 +158,12 @@ if (g.node(u).rank > g.node(v).rank) {
 
+function rankComponent(subgraph, useSimplex) {
+  var spanningTree = feasibleTree(subgraph);
+
+  if (useSimplex) {
+    util.log(1, 'Using network simplex for ranking');
+    simplex(subgraph, spanningTree);
+  }
+  normalize(subgraph);
+}
+
 function normalize(g) {
@@ -160,0 +170,0 @@ var m = util.min(g.nodes().map(function(u) { return g.node(u).rank; }));

lib/util.js

@@ -79,4 +79,3 @@ /*
  * Returns a new function that wraps `func` with a timer. The wrapper logs the
- * time it takes to execute the function. `name` may optionally be supplied. If
- * it is not, the name is derived from `func.name`.
+ * time it takes to execute the function.
  *
@@ -86,9 +85,2 @@ * The timer will be enabled provided `log.level >= 1`.
 function time(name, func) {
-  if (arguments.length === 1) {
-    func = name;
-    name = func.name;
-    if (name.length === 0) {
-      name = "unnamed";
-    }
-  }
   return function() {
@@ -95,0 +87,0 @@ var start = new Date().getTime();

lib/version.js

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

package.json

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

README.md

 # dagre - Graph layout for JavaScript
 
-[![Build Status](https://secure.travis-ci.org/cpettitt/dagre.png)](http://travis-ci.org/cpettitt/dagre)
+[![Build Status](https://secure.travis-ci.org/cpettitt/dagre.png?branch=master)](http://travis-ci.org/cpettitt/dagre)
 
@@ -5,0 +5,0 @@ Dagre is a JavaScript library that makes it easy to lay out directed graphs on

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

Worsened metrics

Total package byte prevSize

71027

decreased by-0.59%

Lines of code

1721

decreased by-1.83%

No dependency changes