dagre - npm Package Compare versions

Comparing version 0.3.8 to 0.3.9

CHANGELOG.md

@@ -0,1 +1,6 @@
+v0.3.9
+======
+
+* Some fixes to how self loops and sideways edges are handled.
+
 v0.3.8
@@ -2,0 +7,0 @@ ======

lib/layout.js

 var util = require('./util'),
     rank = require('./rank'),
-    acyclic = require('./acyclic'),
     order = require('./order'),
@@ -118,3 +117,3 @@ CGraph = require('graphlib').CGraph,
       // above nodes of higher rank.
-      util.time('rank', rank)(g, config.rankSimplex);
+      util.time('rank.run', rank.run)(g, config.rankSimplex);
 
@@ -139,4 +138,5 @@ // Normalize the graph by ensuring that every edge is proper (each edge has
 
-      // Reverse edges that were revered previously to get an acyclic graph.
-      util.time('acyclic.undo', acyclic.undo)(g);
+      // Restore delete edges and reverse edges that were reversed in the rank
+      // phase.
+      util.time('rank.restoreEdges', rank.restoreEdges)(g);
 
@@ -233,4 +233,6 @@ // Construct final result graph and return it
     g.eachNode(function(u, value) {
-      maxX = Math.max(maxX, value.x + value.width / 2);
-      maxY = Math.max(maxY, value.y + value.height / 2);
+      if (!g.children(u).length) {
+        maxX = Math.max(maxX, value.x + value.width / 2);
+        maxY = Math.max(maxY, value.y + value.height / 2);
+      }
     });
@@ -237,0 +239,0 @@ g.eachEdge(function(e, u, v, value) {

lib/order.js

@@ -1,6 +0,6 @@
-var util = require("./util"),
-    crossCount = require("./order/crossCount"),
-    initLayerGraphs = require("./order/initLayerGraphs"),
-    initOrder = require("./order/initOrder"),
-    sortLayer = require("./order/sortLayer");
+var util = require('./util'),
+    crossCount = require('./order/crossCount'),
+    initLayerGraphs = require('./order/initLayerGraphs'),
+    initOrder = require('./order/initOrder'),
+    sortLayer = require('./order/sortLayer');
 
@@ -31,3 +31,3 @@ module.exports = order;
 
-  util.log(2, "Order phase start cross count: " + g.graph().orderInitCC);
+  util.log(2, 'Order phase start cross count: ' + g.graph().orderInitCC);
 
@@ -40,3 +40,3 @@ var i, lastBest;
     }
-    util.log(3, "Order phase iter " + i + " cross count: " + g.graph().orderCC);
+    util.log(3, 'Order phase iter ' + i + ' cross count: ' + g.graph().orderCC);
   }
@@ -46,4 +46,4 @@
 
-  util.log(2, "Order iterations: " + i);
-  util.log(2, "Order phase best cross count: " + g.graph().orderCC);
+  util.log(2, 'Order iterations: ' + i);
+  util.log(2, 'Order phase best cross count: ' + g.graph().orderCC);
 }
@@ -107,7 +107,7 @@
   var cc = crossCount(g);
-  if (!("orderCC" in graph) || graph.orderCC > cc) {
+  if (!('orderCC' in graph) || graph.orderCC > cc) {
     graph.orderCC = cc;
     graph.order = {};
     g.eachNode(function(u, value) {
-      if ("order" in value) {
+      if ('order' in value) {
         graph.order[u] = value.order;
@@ -124,3 +124,3 @@ }
   g.eachNode(function(u, value) {
-    if ("order" in value) {
+    if ('order' in value) {
       value.order = order[u];
@@ -127,0 +127,0 @@ }

lib/order/crossCount.js

@@ -1,2 +0,2 @@
-var util = require("../util");
+var util = require('../util');
 
@@ -3,0 +3,0 @@ module.exports = crossCount;

lib/order/initOrder.js

@@ -1,2 +0,2 @@
-var crossCount = require("./crossCount");
+var crossCount = require('./crossCount');
 
@@ -15,3 +15,3 @@ module.exports = initOrder;
   function addNode(u, value) {
-    if ("order" in value) return;
+    if ('order' in value) return;
     if (g.children && g.children(u).length > 0) return;
@@ -18,0 +18,0 @@ if (!(value.rank in orderCount)) {

lib/order/sortLayer.js

@@ -1,6 +0,6 @@
-var util = require("../util");
+var util = require('../util');
 /*
-    Digraph = require("graphlib").Digraph,
-    topsort = require("graphlib").alg.topsort,
-    nodesFromList = require("graphlib").filter.nodesFromList;
+    Digraph = require('graphlib').Digraph,
+    topsort = require('graphlib').alg.topsort,
+    nodesFromList = require('graphlib').filter.nodesFromList;
 */
@@ -7,0 +7,0 @@

lib/position.js

@@ -1,2 +0,2 @@
-var util = require("./util");
+var util = require('./util');
 
@@ -14,3 +14,3 @@ /*
     rankSep: 30,
-    rankDir: "TB"
+    rankDir: 'TB'
   };
@@ -20,11 +20,11 @@
 
-  self.nodeSep = util.propertyAccessor(self, config, "nodeSep");
-  self.edgeSep = util.propertyAccessor(self, config, "edgeSep");
+  self.nodeSep = util.propertyAccessor(self, config, 'nodeSep');
+  self.edgeSep = util.propertyAccessor(self, config, 'edgeSep');
   // If not null this separation value is used for all nodes and edges
   // regardless of their widths. `nodeSep` and `edgeSep` are ignored with this
   // option.
-  self.universalSep = util.propertyAccessor(self, config, "universalSep");
-  self.rankSep = util.propertyAccessor(self, config, "rankSep");
-  self.rankDir = util.propertyAccessor(self, config, "rankDir");
-  self.debugLevel = util.propertyAccessor(self, config, "debugLevel");
+  self.universalSep = util.propertyAccessor(self, config, 'universalSep');
+  self.rankSep = util.propertyAccessor(self, config, 'rankSep');
+  self.rankDir = util.propertyAccessor(self, config, 'rankDir');
+  self.debugLevel = util.propertyAccessor(self, config, 'debugLevel');
 
@@ -43,10 +43,10 @@ self.run = run;
     var xss = {};
-    ["u", "d"].forEach(function(vertDir) {
-      if (vertDir === "d") layering.reverse();
+    ['u', 'd'].forEach(function(vertDir) {
+      if (vertDir === 'd') layering.reverse();
 
-      ["l", "r"].forEach(function(horizDir) {
-        if (horizDir === "r") reverseInnerOrder(layering);
+      ['l', 'r'].forEach(function(horizDir) {
+        if (horizDir === 'r') reverseInnerOrder(layering);
 
         var dir = vertDir + horizDir;
-        var align = verticalAlignment(g, layering, conflicts, vertDir === "u" ? "predecessors" : "successors");
+        var align = verticalAlignment(g, layering, conflicts, vertDir === 'u' ? 'predecessors' : 'successors');
         xss[dir]= horizontalCompaction(g, layering, align.pos, align.root, align.align);
@@ -57,8 +57,8 @@
 
-        if (horizDir === "r") flipHorizontally(xss[dir]);
+        if (horizDir === 'r') flipHorizontally(xss[dir]);
 
-        if (horizDir === "r") reverseInnerOrder(layering);
+        if (horizDir === 'r') reverseInnerOrder(layering);
       });
 
-      if (vertDir === "d") layering.reverse();
+      if (vertDir === 'd') layering.reverse();
     });
@@ -97,4 +97,4 @@
     return u < v
-      ? u.toString().length + ":" + u + "-" + v
-      : v.toString().length + ":" + v + "-" + u;
+      ? u.toString().length + ':' + u + '-' + v
+      : v.toString().length + ':' + v + '-' + u;
   }
@@ -318,6 +318,6 @@
     // Determine how much to adjust positioning for each alignment
-    ["u", "d"].forEach(function(vertDir) {
-      ["l", "r"].forEach(function(horizDir) {
+    ['u', 'd'].forEach(function(vertDir) {
+      ['l', 'r'].forEach(function(horizDir) {
         var alignment = vertDir + horizDir;
-        shift[alignment] = horizDir === "l"
+        shift[alignment] = horizDir === 'l'
             ? min[smallestAlignment] - min[alignment]
@@ -348,3 +348,3 @@ : max[smallestAlignment] - max[alignment];
     switch (config.rankDir) {
-      case "LR": return g.node(u).height;
+      case 'LR': return g.node(u).height;
       default:   return g.node(u).width;
@@ -356,3 +356,3 @@ }
     switch(config.rankDir) {
-      case "LR": return g.node(u).width;
+      case 'LR': return g.node(u).width;
       default:   return g.node(u).height;
@@ -373,3 +373,3 @@ }
     switch (config.rankDir) {
-      case "LR":
+      case 'LR':
         if (arguments.length < 3) {
@@ -392,3 +392,3 @@ return g.node(u).y;
     switch (config.rankDir) {
-      case "LR":
+      case 'LR':
         if (arguments.length < 3) {
@@ -411,3 +411,3 @@ return g.node(u)[name];
     switch (config.rankDir) {
-      case "LR":
+      case 'LR':
         if (arguments.length < 3) {
@@ -436,4 +436,4 @@ return g.node(u).x;
           if (xV - xU < s)
-            console.log("Position phase: sep violation. Align: " + align + ". Layer: " + li + ". " +
-              "U: " + u + " V: " + v + ". Actual sep: " + (xV - xU) + " Expected sep: " + s);
+            console.log('Position phase: sep violation. Align: ' + align + '. Layer: ' + li + '. ' +
+              'U: ' + u + ' V: ' + v + '. Actual sep: ' + (xV - xU) + ' Expected sep: ' + s);
         }
@@ -440,0 +440,0 @@ u = v;

lib/rank.js

 var util = require('./util'),
-    acyclic = require('./acyclic'),
+    acyclic = require('./rank/acyclic'),
     initRank = require('./rank/initRank'),
     feasibleTree = require('./rank/feasibleTree'),
+    constraints = require('./rank/constraints'),
     simplex = require('./rank/simplex'),
@@ -9,3 +10,4 @@ components = require('graphlib').alg.components,
 
-module.exports = rank;
+exports.run = run;
+exports.restoreEdges = restoreEdges;
 
@@ -19,25 +21,39 @@ /*
  *
- *  * Input graph must be acyclic
  *  * Each edge in the input graph must have an assigned 'minLen' attribute
  */
-function rank(g, useSimplex) {
+function run(g, useSimplex) {
+  var selfLoops = removeSelfLoops(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)));
+  util.time('constraints.apply', constraints.apply)(g);
 
+  // Since we already removed self loops before applying rank constraints we
+  // know that self loops indicate sideways edges induced by rank constraints.
+  // Currently we do not have any support for sideways edges, so we remove
+  // them. Since the edges we remove are between collapsed nodes, we need to
+  // take care to save the original edge information.
+  var sidewaysEdges = removeSelfLoops(g)
+    .map(function(edge) {
+      return edge.value.originalEdge;
+    });
+
   // Reverse edges to get an acyclic graph, we keep the graph in an acyclic
   // state until the very end.
-  util.time('acyclic', acyclic)(constrainedGraph);
+  util.time('acyclic', acyclic)(g);
 
+  // Convert the graph into a flat graph for ranking
+  var flatGraph = g.filterNodes(util.filterNonSubgraphs(g));
+
   // Assign an initial ranking using DFS.
-  initRank(constrainedGraph);
+  initRank(flatGraph);
 
   // For each component improve the assigned ranks.
-  components(constrainedGraph).forEach(function(cmpt) {
-    var subgraph = constrainedGraph.filterNodes(filter.nodesFromList(cmpt));
+  components(flatGraph).forEach(function(cmpt) {
+    var subgraph = flatGraph.filterNodes(filter.nodesFromList(cmpt));
     rankComponent(subgraph, useSimplex);
   });
 
-  // Update the layout graph with rakn information from the constrained graph.
-  util.time('applyConstrainedGraph', applyConstrainedGraph)(constrainedGraph, g);
+  // Relax original constraints
+  util.time('constraints.relax', constraints.relax(g));
 
@@ -50,96 +66,38 @@ // When handling nodes with constrained ranks it is possible to end up with
   util.time('reorientEdges', reorientEdges)(g);
+
+  // Save removed edges so that they can be restored later
+  g.graph().rankRemovedEdges = selfLoops.concat(sidewaysEdges);
 }
 
-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])) {
-      needsReduction = true;
-      break;
+function restoreEdges(g) {
+  g.graph().rankRemovedEdges.forEach(function(edge) {
+    // It's possible that the removed edge collides with an auto-assigned id,
+    // so we check for and resolve such cases here.
+    if (g.hasEdge(edge.e)) {
+      g.addEdge(null, g.source(edge.e), g.target(edge.e), g.edge(edge.e));
+      g.delEdge(edge.e);
     }
-  }
+    g.addEdge(edge.e, edge.u, edge.v, edge.value);
+  });
 
-  if (!needsReduction) {
-    return g;
-  }
+  acyclic.undo(g);
+}
 
-  g.graph({ compoundNodes: [] });
+/*
+ * Find any self loops and remove them from the input graph. Return the removed
+ * edges in the form { e, u, v, value }.
+ */
+function removeSelfLoops(g) {
+  var selfLoops = [];
 
-  var prefRankToNode = {};
-  g.eachNode(function(u, value) {
-    var rank = value.prefRank,
-        newU;
-
-    if (rank !== undefined) {
-      if (!checkSupportedPrefRank(rank)) {
-        return;
-      }
-
-      newU = prefRankToNode[rank];
-      if (newU === undefined) {
-        newU = prefRankToNode[rank] = g.addNode(null, { originalNodes: [] });
-        g.graph().compoundNodes.push(newU);
-      }
-
-      // Fixup all edges to point to new compound node.
-      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), value);
-        } else {
-          g.addEdge(null, g.source(e), newU, value);
-        }
-        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, value);
-        } else {
-          g.addEdge(null, newU, g.target(e), value);
-        }
-        g.delEdge(e);
-      });
-
-      // Save original node and remove it from reduced graph
-      g.node(newU).originalNodes.push(u);
-      g.delNode(u);
+  g.eachEdge(function(e, u, v, value) {
+    if (u === v) {
+      selfLoops.push({e: e, u: u, v: v, value: value});
+      g.delEdge(e);
     }
   });
 
-  var minNode = prefRankToNode.min;
-  if (minNode !== undefined) {
-    g.nodes().forEach(function(u) { g.addEdge(null, minNode, u, { minLen: 0 }); });
-  }
-
-  var maxNode = prefRankToNode.max;
-  if (maxNode !== undefined) {
-    g.nodes().forEach(function(u) { g.addEdge(null, u, maxNode, { minLen: 0 }); });
-  }
-
-  return g;
+  return selfLoops;
 }
 
-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) {
-        original.node(v).rank = value.rank;
-      });
-    });
-  }
-}
-
 function reorientEdges(g) {
@@ -146,0 +104,0 @@ g.eachEdge(function(e, u, v, value) {

lib/util.js

@@ -89,3 +89,3 @@ /*
     } finally {
-      log(1, name + " time: " + (new Date().getTime() - start) + "ms");
+      log(1, name + ' time: ' + (new Date().getTime() - start) + 'ms');
     }
@@ -92,0 +92,0 @@ };

lib/version.js

@@ -1,1 +0,1 @@
-module.exports = '0.3.8';
+module.exports = '0.3.9';

package.json

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

75025

increased by4.24%

Number of package files

25

increased by4.17%

Lines of code

1827

increased by5.24%

No dependency changes