dagre - npm Package Compare versions

Comparing version 0.4.4 to 0.4.5

CHANGELOG.md

@@ -0,1 +1,6 @@
+v0.4.5
+======
+
+* Add initial support for self-loops and sideways edges
+
 v0.4.4
@@ -2,0 +7,0 @@ ======

lib/position.js

@@ -140,3 +140,5 @@ var util = require('./util');
           var uPred = g.predecessors(u)[0];
-          if (g.node(uPred).dummy)
+          // Note: In the case of self loops and sideways edges it is possible
+          // for a dummy not to have a predecessor.
+          if (uPred !== undefined && g.node(uPred).dummy)
             k1 = pos[uPred];
@@ -143,0 +145,0 @@ }

lib/rank.js

@@ -23,3 +23,3 @@ var util = require('./util'),
 function run(g, useSimplex) {
-  var selfLoops = removeSelfLoops(g);
+  expandSelfLoops(g);
 
@@ -30,11 +30,3 @@ // If there are rank constraints on nodes, then build a new graph that
 
-  // 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;
-    });
+  expandSidewaysEdges(g);
 
@@ -66,18 +58,5 @@ // Reverse edges to get an acyclic graph, we keep the graph in an acyclic
   util.time('reorientEdges', reorientEdges)(g);
-
-  // Save removed edges so that they can be restored later
-  g.graph().rankRemovedEdges = selfLoops.concat(sidewaysEdges);
 }
 
 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);
-  });
-
   acyclic.undo(g);
@@ -87,16 +66,50 @@ }
 /*
- * Find any self loops and remove them from the input graph. Return the removed
- * edges in the form { e, u, v, value }.
+ * Expand self loops into three dummy nodes. One will sit above the incident
+ * node, one will be at the same level, and one below. The result looks like:
+ *
+ *         /--<--x--->--\
+ *     node              y
+ *         \--<--z--->--/
+ *
+ * Dummy nodes x, y, z give us the shape of a loop and node y is where we place
+ * the label.
+ *
+ * TODO: consolidate knowledge of dummy node construction.
+ * TODO: support minLen = 2
  */
-function removeSelfLoops(g) {
-  var selfLoops = [];
+function expandSelfLoops(g) {
+  g.eachEdge(function(e, u, v, a) {
+    if (u === v) {
+      var x = addDummyNode(g, e, u, v, a, 0, false),
+          y = addDummyNode(g, e, u, v, a, 1, true),
+          z = addDummyNode(g, e, u, v, a, 2, false);
+      g.addEdge(null, x, u, {minLen: 1, selfLoop: true});
+      g.addEdge(null, x, y, {minLen: 1, selfLoop: true});
+      g.addEdge(null, u, z, {minLen: 1, selfLoop: true});
+      g.addEdge(null, y, z, {minLen: 1, selfLoop: true});
+      g.delEdge(e);
+    }
+  });
+}
 
-  g.eachEdge(function(e, u, v, value) {
+function expandSidewaysEdges(g) {
+  g.eachEdge(function(e, u, v, a) {
     if (u === v) {
-      selfLoops.push({e: e, u: u, v: v, value: value});
+      var origEdge = a.originalEdge,
+          dummy = addDummyNode(g, origEdge.e, origEdge.u, origEdge.v, origEdge.value, 0, true);
+      g.addEdge(null, u, dummy, {minLen: 1});
+      g.addEdge(null, dummy, v, {minLen: 1});
       g.delEdge(e);
     }
   });
+}
 
-  return selfLoops;
+function addDummyNode(g, e, u, v, a, index, isLabel) {
+  return g.addNode(null, {
+    width: isLabel ? a.width : 0,
+    height: isLabel ? a.height : 0,
+    edge: { id: e, source: u, target: v, attrs: a },
+    dummy: true,
+    index: index
+  });
 }
@@ -103,0 +116,0 @@

lib/rank/constraints.js

@@ -63,2 +63,8 @@ exports.apply = function(g) {
     }
+
+    // Do not reverse edges for self-loops.
+    if (origValue.selfLoop) {
+      reverse = false;
+    }
+
     if (reverse) {
@@ -86,2 +92,8 @@ // Ensure that all edges to min are reversed
     }
+
+    // Do not reverse edges for self-loops.
+    if (origValue.selfLoop) {
+      reverse = false;
+    }
+
     if (reverse) {
@@ -100,3 +112,5 @@ // Ensure that all edges from max are reversed
     g.children(sg).forEach(function(u) {
-      if (u !== minNode && !g.outEdges(minNode, u).length) {
+      // The dummy check ensures we don't add an edge if the node is involved
+      // in a self loop or sideways edge.
+      if (u !== minNode && !g.outEdges(minNode, u).length && !g.node(u).dummy) {
         g.addEdge(null, minNode, u, { minLen: 0 });
@@ -111,3 +125,5 @@ }
     g.children(sg).forEach(function(u) {
-      if (u !== maxNode && !g.outEdges(u, maxNode).length) {
+      // The dummy check ensures we don't add an edge if the node is involved
+      // in a self loop or sideways edge.
+      if (u !== maxNode && !g.outEdges(u, maxNode).length && !g.node(u).dummy) {
         g.addEdge(null, u, maxNode, { minLen: 0 });
@@ -114,0 +130,0 @@ }

lib/version.js

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

package.json

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

78145

increased by1.21%

Lines of code

1876

increased by1.57%

No dependency changes