cytoscape-fcose - npm Package Compare versions

Comparing version 1.0.0 to 1.1.0

bower.json

 {
   "name": "cytoscape-fcose",
-  "description": "",
+  "description": "The fCoSE layout for Cytoscape.js by Bilkent with fast compound node placement",
   "main": "cytoscape-fcose.js",
   "dependencies": {
-    "cytoscape": "^3.2.0"
+    "cytoscape": "^3.2.0",
+    "numeric": "1.2.6",
+    "cose-base": "^1.0.0"
   },
@@ -8,0 +10,0 @@ "repository": {

cytoscape-fcose.js

@@ -92,2 +92,309 @@ (function webpackUniversalModuleDefinition(root, factory) {
 
+/*
+ * Auxiliary functions
+ */
+
+var LinkedList = __webpack_require__(0).layoutBase.LinkedList;
+
+var auxiliary = {};
+
+auxiliary.multMat = function (array1, array2) {
+  var result = [];
+
+  for (var i = 0; i < array1.length; i++) {
+    result[i] = [];
+    for (var j = 0; j < array2[0].length; j++) {
+      result[i][j] = 0;
+      for (var k = 0; k < array1[0].length; k++) {
+        result[i][j] += array1[i][k] * array2[k][j];
+      }
+    }
+  }
+  return result;
+};
+
+auxiliary.multGamma = function (array) {
+  var result = [];
+  var sum = 0;
+
+  for (var i = 0; i < array.length; i++) {
+    sum += array[i];
+  }
+
+  sum *= -1 / array.length;
+
+  for (var _i = 0; _i < array.length; _i++) {
+    result[_i] = sum + array[_i];
+  }
+  return result;
+};
+
+auxiliary.multL = function (array, C, INV) {
+  var result = [];
+  var temp1 = [];
+  var temp2 = [];
+
+  // multiply by C^T
+  for (var i = 0; i < C[0].length; i++) {
+    var sum = 0;
+    for (var j = 0; j < C.length; j++) {
+      sum += -0.5 * C[j][i] * array[j];
+    }
+    temp1[i] = sum;
+  }
+  // multiply the result by INV
+  for (var _i2 = 0; _i2 < INV.length; _i2++) {
+    var _sum = 0;
+    for (var _j = 0; _j < INV.length; _j++) {
+      _sum += INV[_i2][_j] * temp1[_j];
+    }
+    temp2[_i2] = _sum;
+  }
+  // multiply the result by C
+  for (var _i3 = 0; _i3 < C.length; _i3++) {
+    var _sum2 = 0;
+    for (var _j2 = 0; _j2 < C[0].length; _j2++) {
+      _sum2 += C[_i3][_j2] * temp2[_j2];
+    }
+    result[_i3] = _sum2;
+  }
+
+  return result;
+};
+
+auxiliary.multCons = function (array, constant) {
+  var result = [];
+
+  for (var i = 0; i < array.length; i++) {
+    result[i] = array[i] * constant;
+  }
+
+  return result;
+};
+
+// assumes arrays have same size
+auxiliary.minusOp = function (array1, array2) {
+  var result = [];
+
+  for (var i = 0; i < array1.length; i++) {
+    result[i] = array1[i] - array2[i];
+  }
+
+  return result;
+};
+
+// assumes arrays have same size
+auxiliary.dotProduct = function (array1, array2) {
+  var product = 0;
+
+  for (var i = 0; i < array1.length; i++) {
+    product += array1[i] * array2[i];
+  }
+
+  return product;
+};
+
+auxiliary.mag = function (array) {
+  return Math.sqrt(this.dotProduct(array, array));
+};
+
+auxiliary.normalize = function (array) {
+  var result = [];
+  var magnitude = this.mag(array);
+
+  for (var i = 0; i < array.length; i++) {
+    result[i] = array[i] / magnitude;
+  }
+
+  return result;
+};
+
+// get the top most nodes
+auxiliary.getTopMostNodes = function (nodes) {
+  var nodesMap = {};
+  for (var i = 0; i < nodes.length; i++) {
+    nodesMap[nodes[i].id()] = true;
+  }
+  var roots = nodes.filter(function (ele, i) {
+    if (typeof ele === "number") {
+      ele = i;
+    }
+    var parent = ele.parent()[0];
+    while (parent != null) {
+      if (nodesMap[parent.id()]) {
+        return false;
+      }
+      parent = parent.parent()[0];
+    }
+    return true;
+  });
+
+  return roots;
+};
+
+// find disconnected components and create dummy nodes that connect them
+auxiliary.connectComponents = function (cy, eles, topMostNodes, dummyNodes) {
+  var queue = new LinkedList();
+  var visited = new Set();
+  var visitedTopMostNodes = [];
+  var currentNeighbor = void 0;
+  var minDegreeNode = void 0;
+  var minDegree = void 0;
+
+  var isConnected = false;
+  var count = 1;
+  var nodesConnectedToDummy = [];
+  var components = [];
+
+  var _loop = function _loop() {
+    var cmpt = cy.collection();
+    components.push(cmpt);
+
+    var currentNode = topMostNodes[0];
+    var childrenOfCurrentNode = cy.collection();
+    childrenOfCurrentNode.merge(currentNode).merge(currentNode.descendants());
+    visitedTopMostNodes.push(currentNode);
+
+    childrenOfCurrentNode.forEach(function (node) {
+      queue.push(node);
+      visited.add(node);
+      cmpt.merge(node);
+    });
+
+    var _loop2 = function _loop2() {
+      currentNode = queue.shift();
+
+      // Traverse all neighbors of this node
+      var neighborNodes = cy.collection();
+      currentNode.neighborhood().nodes().forEach(function (node) {
+        if (eles.contains(currentNode.edgesWith(node))) {
+          neighborNodes.merge(node);
+        }
+      });
+
+      for (var i = 0; i < neighborNodes.length; i++) {
+        var neighborNode = neighborNodes[i];
+        currentNeighbor = topMostNodes.intersection(neighborNode.union(neighborNode.ancestors()));
+        if (currentNeighbor != null && !visited.has(currentNeighbor[0])) {
+          var childrenOfNeighbor = currentNeighbor.union(currentNeighbor.descendants());
+
+          childrenOfNeighbor.forEach(function (node) {
+            queue.push(node);
+            visited.add(node);
+            cmpt.merge(node);
+            if (topMostNodes.has(node)) {
+              visitedTopMostNodes.push(node);
+            }
+          });
+        }
+      }
+    };
+
+    while (queue.length != 0) {
+      _loop2();
+    }
+
+    cmpt.forEach(function (node) {
+      node.connectedEdges().forEach(function (e) {
+        // connectedEdges() usually cached
+        if (cmpt.has(e.source()) && cmpt.has(e.target())) {
+          // has() is cheap
+          cmpt.merge(e); // forEach() only considers nodes -- sets N at call time
+        }
+      });
+    });
+
+    if (visitedTopMostNodes.length == topMostNodes.length) {
+      isConnected = true;
+    }
+
+    if (!isConnected || isConnected && count > 1) {
+      minDegreeNode = visitedTopMostNodes[0];
+      minDegree = minDegreeNode.connectedEdges().length;
+      visitedTopMostNodes.forEach(function (node) {
+        if (node.connectedEdges().length < minDegree) {
+          minDegree = node.connectedEdges().length;
+          minDegreeNode = node;
+        }
+      });
+      nodesConnectedToDummy.push(minDegreeNode.id());
+      // TO DO: Check efficiency of this part
+      var temp = cy.collection();
+      temp.merge(visitedTopMostNodes[0]);
+      visitedTopMostNodes.forEach(function (node) {
+        temp.merge(node);
+      });
+      visitedTopMostNodes = [];
+      topMostNodes = topMostNodes.difference(temp);
+      count++;
+    }
+  };
+
+  do {
+    _loop();
+  } while (!isConnected);
+
+  if (dummyNodes) {
+    if (nodesConnectedToDummy.length > 0) {
+      dummyNodes.set('dummy' + (dummyNodes.size + 1), nodesConnectedToDummy);
+    }
+  }
+  return components;
+};
+
+auxiliary.calcBoundingBox = function (parentNode, xCoords, yCoords, nodeIndexes) {
+  // calculate bounds
+  var left = Number.MAX_VALUE;
+  var right = Number.MIN_VALUE;
+  var top = Number.MAX_VALUE;
+  var bottom = Number.MIN_VALUE;
+  var nodeLeft = void 0;
+  var nodeRight = void 0;
+  var nodeTop = void 0;
+  var nodeBottom = void 0;
+
+  var nodes = parentNode.descendants().not(":parent");
+  var s = nodes.length;
+  for (var i = 0; i < s; i++) {
+    var node = nodes[i];
+
+    nodeLeft = xCoords[nodeIndexes.get(node.id())] - node.width() / 2;
+    nodeRight = xCoords[nodeIndexes.get(node.id())] + node.width() / 2;
+    nodeTop = yCoords[nodeIndexes.get(node.id())] - node.height() / 2;
+    nodeBottom = yCoords[nodeIndexes.get(node.id())] + node.height() / 2;
+
+    if (left > nodeLeft) {
+      left = nodeLeft;
+    }
+
+    if (right < nodeRight) {
+      right = nodeRight;
+    }
+
+    if (top > nodeTop) {
+      top = nodeTop;
+    }
+
+    if (bottom < nodeBottom) {
+      bottom = nodeBottom;
+    }
+  }
+
+  var boundingBox = {};
+  boundingBox.topLeftX = left;
+  boundingBox.topLeftY = top;
+  boundingBox.width = right - left;
+  boundingBox.height = bottom - top;
+  return boundingBox;
+};
+
+module.exports = auxiliary;
+
+/***/ }),
+/* 2 */
+/***/ (function(module, exports, __webpack_require__) {
+
+"use strict";
+
+
 var _createClass = function () { function defineProperties(target, props) { for (var i = 0; i < props.length; i++) { var descriptor = props[i]; descriptor.enumerable = descriptor.enumerable || false; descriptor.configurable = true; if ("value" in descriptor) descriptor.writable = true; Object.defineProperty(target, descriptor.key, descriptor); } } return function (Constructor, protoProps, staticProps) { if (protoProps) defineProperties(Constructor.prototype, protoProps); if (staticProps) defineProperties(Constructor, staticProps); return Constructor; }; }();
@@ -101,3 +408,4 @@
 
-var assign = __webpack_require__(2);
+var assign = __webpack_require__(3);
+var aux = __webpack_require__(1);
 
@@ -132,2 +440,4 @@ var _require = __webpack_require__(5),
   nodeDimensionsIncludeLabels: false,
+  // whether to pack disconnected components - valid only if randomize: true
+  packComponents: true,
 
@@ -160,3 +470,3 @@ /* spectral layout options */
   // For enabling tiling
-  tile: false,
+  tile: true,
   // Represents the amount of the vertical space to put between the zero degree members during the tiling operation(can also be a function)
@@ -192,40 +502,197 @@ tilingPaddingVertical: 10,
       var options = this.options;
+      var cy = options.cy;
       var eles = options.eles;
 
-      var spectralResult = void 0;
+      var spectralResult = [];
       var xCoords = void 0;
       var yCoords = void 0;
-      var coseResult = void 0;
+      var coseResult = [];
+      var components = void 0;
 
-      // If number of nodes is 1 or 2, either SVD or powerIteration causes problem
-      // So direct the graph to cose layout
-      if (options.randomize && eles.nodes().length > 2) {
-        // Apply spectral layout
-        spectralResult = spectralLayout(options);
-        xCoords = spectralResult["xCoords"];
-        yCoords = spectralResult["yCoords"];
+      var layUtil = void 0;
+      var packingEnabled = false;
+      if (cy.layoutUtilities && options.packComponents && options.randomize) {
+        layUtil = cy.layoutUtilities("get");
+        if (!layUtil) layUtil = cy.layoutUtilities();
+        packingEnabled = true;
       }
 
-      if (options.quality == "default" || options.quality == "proof" || eles.nodes().length <= 2) {
-        // Apply cose layout as postprocessing
-        coseResult = coseLayout(options, spectralResult);
+      if (options.eles.length == 0) return;
+
+      if (options.eles.length != options.cy.elements().length) {
+        var prevNodes = eles.nodes();
+        eles = eles.union(eles.descendants());
+
+        eles.forEach(function (ele) {
+          if (ele.isNode()) {
+            var connectedEdges = ele.connectedEdges();
+            connectedEdges.forEach(function (edge) {
+              if (eles.contains(edge.source()) && eles.contains(edge.target()) && !prevNodes.contains(edge.source().union(edge.target()))) {
+                eles = eles.union(edge);
+              }
+            });
+          }
+        });
+
+        options.eles = eles;
       }
 
+      if (packingEnabled) {
+        var topMostNodes = aux.getTopMostNodes(options.eles.nodes());
+        components = aux.connectComponents(cy, options.eles, topMostNodes);
+      }
+
+      if (options.randomize) {
+        if (packingEnabled) {
+          components.forEach(function (component) {
+            options.eles = component;
+            spectralResult.push(spectralLayout(options));
+          });
+        } else {
+          // Apply spectral layout
+          spectralResult.push(spectralLayout(options));
+          if (spectralResult[0]) {
+            xCoords = spectralResult[0]["xCoords"];
+            yCoords = spectralResult[0]["yCoords"];
+          }
+        }
+      }
+
+      if (options.quality == "default" || options.quality == "proof" || spectralResult.includes(false)) {
+        if (packingEnabled) {
+          if (options.quality == "draft" && spectralResult.includes(false)) {
+            spectralResult.forEach(function (value, index) {
+              if (!value) {
+                options.eles = components[index];
+                var tempResult = coseLayout(options, spectralResult[index]);
+                var nodeIndexes = new Map();
+                var _xCoords = [];
+                var _yCoords = [];
+                var count = 0;
+                Object.keys(tempResult).forEach(function (item) {
+                  nodeIndexes.set(item, count++);
+                  _xCoords.push(tempResult[item].getCenterX());
+                  _yCoords.push(tempResult[item].getCenterY());
+                });
+                spectralResult[index] = { nodeIndexes: nodeIndexes, xCoords: _xCoords, yCoords: _yCoords };
+              }
+            });
+          } else {
+            var toBeTiledNodes = cy.collection();
+            if (options.tile) {
+              var nodeIndexes = new Map();
+              var _xCoords2 = [];
+              var _yCoords2 = [];
+              var count = 0;
+              var tempSpectralResult = { nodeIndexes: nodeIndexes, xCoords: _xCoords2, yCoords: _yCoords2 };
+              var indexesToBeDeleted = [];
+              components.forEach(function (component, index) {
+                if (component.edges().length == 0) {
+                  component.nodes().forEach(function (node, i) {
+                    toBeTiledNodes.merge(component.nodes()[i]);
+                    if (!node.isParent()) {
+                      tempSpectralResult.nodeIndexes.set(component.nodes()[i].id(), count++);
+                      tempSpectralResult.xCoords.push(component.nodes()[0].position().x);
+                      tempSpectralResult.yCoords.push(component.nodes()[0].position().y);
+                    }
+                  });
+                  indexesToBeDeleted.push(index);
+                }
+              });
+              if (toBeTiledNodes.length > 1) {
+                components.push(toBeTiledNodes);
+                for (var i = indexesToBeDeleted.length - 1; i >= 0; i--) {
+                  components.splice(indexesToBeDeleted[i], 1);
+                  spectralResult.splice(indexesToBeDeleted[i], 1);
+                };
+                spectralResult.push(tempSpectralResult);
+              }
+            }
+            components.forEach(function (component, index) {
+              options.eles = component;
+              coseResult.push(coseLayout(options, spectralResult[index]));
+            });
+          }
+        } else {
+          // Apply cose layout as postprocessing
+          coseResult.push(coseLayout(options, spectralResult[0]));
+        }
+      }
+
+      if (packingEnabled) {
+        var subgraphs = [];
+        components.forEach(function (component, index) {
+          var nodeIndexes = void 0;
+          if (options.quality == "draft") {
+            nodeIndexes = spectralResult[index].nodeIndexes;
+          }
+          var subgraph = {};
+          subgraph.nodes = [];
+          subgraph.edges = [];
+          var nodeIndex = void 0;
+          component.nodes().forEach(function (node) {
+            if (options.quality == "draft") {
+              if (!node.isParent()) {
+                nodeIndex = nodeIndexes.get(node.id());
+                subgraph.nodes.push({ x: spectralResult[index].xCoords[nodeIndex] - node.bb().w / 2, y: spectralResult[index].yCoords[nodeIndex] - node.bb().h / 2, width: node.bb().w, height: node.bb().h });
+              } else {
+                var parentInfo = aux.calcBoundingBox(node, spectralResult[index].xCoords, spectralResult[index].yCoords, nodeIndexes);
+                subgraph.nodes.push({ x: parentInfo.topLeftX, y: parentInfo.topLeftY, width: parentInfo.width, height: parentInfo.height });
+              }
+            } else {
+              subgraph.nodes.push({ x: coseResult[index][node.id()].getLeft(), y: coseResult[index][node.id()].getTop(), width: coseResult[index][node.id()].getWidth(), height: coseResult[index][node.id()].getHeight() });
+            }
+          });
+          subgraphs.push(subgraph);
+        });
+        var shiftResult = layUtil.packComponents(subgraphs).shifts;
+        if (options.quality == "draft") {
+          spectralResult.forEach(function (result, index) {
+            var newXCoords = result.xCoords.map(function (x) {
+              return x + shiftResult[index].dx;
+            });
+            var newYCoords = result.yCoords.map(function (y) {
+              return y + shiftResult[index].dy;
+            });
+            result.xCoords = newXCoords;
+            result.yCoords = newYCoords;
+          });
+        } else {
+          coseResult.forEach(function (result, index) {
+            Object.keys(result).forEach(function (item) {
+              var nodeRectangle = result[item];
+              nodeRectangle.setCenter(nodeRectangle.getCenterX() + shiftResult[index].dx, nodeRectangle.getCenterY() + shiftResult[index].dy);
+            });
+          });
+        }
+      }
+
       // get each element's calculated position
       var getPositions = function getPositions(ele, i) {
-        if (options.quality == "default" || options.quality == "proof") {
+        if (options.quality == "default" || options.quality == "proof" || options.quality == "proof" && !packingEnabled && spectralResult.includes(false)) {
           if (typeof ele === "number") {
             ele = i;
           }
+          var pos = void 0;
           var theId = ele.data('id');
-          var lNode = coseResult[theId];
-
+          coseResult.forEach(function (result) {
+            if (theId in result) {
+              pos = { x: result[theId].getRect().getCenterX(), y: result[theId].getRect().getCenterY() };
+            }
+          });
           return {
-            x: lNode.getRect().getCenterX(),
-            y: lNode.getRect().getCenterY()
+            x: pos.x,
+            y: pos.y
           };
         } else {
+          var _pos = void 0;
+          spectralResult.forEach(function (result) {
+            var index = result.nodeIndexes.get(ele.id());
+            if (index != undefined) {
+              _pos = { x: result.xCoords[index], y: result.yCoords[index] };
+            };
+          });
           return {
-            x: xCoords[i],
-            y: yCoords[i]
+            x: _pos.x,
+            y: _pos.y
           };
@@ -238,2 +705,3 @@ }
         // transfer calculated positions to nodes (positions of only simple nodes are evaluated, compounds are positioned automatically)
+        options.eles = eles;
         eles.nodes().not(":parent").layoutPositions(layout, options, getPositions);
@@ -252,3 +720,3 @@ } else {
 /***/ }),
-/* 2 */
+/* 3 */
 /***/ (function(module, exports, __webpack_require__) {
@@ -276,128 +744,2 @@
 /***/ }),
-/* 3 */
-/***/ (function(module, exports, __webpack_require__) {
-
-"use strict";
-
-
-/*
- * Auxiliary functions used in spectral layout (especially in power iteration)
- */
-
-var auxiliary = {};
-
-auxiliary.multMat = function (array1, array2) {
-  var result = [];
-
-  for (var i = 0; i < array1.length; i++) {
-    result[i] = [];
-    for (var j = 0; j < array2[0].length; j++) {
-      result[i][j] = 0;
-      for (var k = 0; k < array1[0].length; k++) {
-        result[i][j] += array1[i][k] * array2[k][j];
-      }
-    }
-  }
-  return result;
-};
-
-auxiliary.multGamma = function (array) {
-  var result = [];
-  var sum = 0;
-
-  for (var i = 0; i < array.length; i++) {
-    sum += array[i];
-  }
-
-  sum *= -1 / array.length;
-
-  for (var _i = 0; _i < array.length; _i++) {
-    result[_i] = sum + array[_i];
-  }
-  return result;
-};
-
-auxiliary.multL = function (array, C, INV) {
-  var result = [];
-  var temp1 = [];
-  var temp2 = [];
-
-  // multiply by C^T
-  for (var i = 0; i < C[0].length; i++) {
-    var sum = 0;
-    for (var j = 0; j < C.length; j++) {
-      sum += -0.5 * C[j][i] * array[j];
-    }
-    temp1[i] = sum;
-  }
-  // multiply the result by INV
-  for (var _i2 = 0; _i2 < INV.length; _i2++) {
-    var _sum = 0;
-    for (var _j = 0; _j < INV.length; _j++) {
-      _sum += INV[_i2][_j] * temp1[_j];
-    }
-    temp2[_i2] = _sum;
-  }
-  // multiply the result by C
-  for (var _i3 = 0; _i3 < C.length; _i3++) {
-    var _sum2 = 0;
-    for (var _j2 = 0; _j2 < C[0].length; _j2++) {
-      _sum2 += C[_i3][_j2] * temp2[_j2];
-    }
-    result[_i3] = _sum2;
-  }
-
-  return result;
-};
-
-auxiliary.multCons = function (array, constant) {
-  var result = [];
-
-  for (var i = 0; i < array.length; i++) {
-    result[i] = array[i] * constant;
-  }
-
-  return result;
-};
-
-// assumes arrays have same size
-auxiliary.minusOp = function (array1, array2) {
-  var result = [];
-
-  for (var i = 0; i < array1.length; i++) {
-    result[i] = array1[i] - array2[i];
-  }
-
-  return result;
-};
-
-// assumes arrays have same size
-auxiliary.dotProduct = function (array1, array2) {
-  var product = 0;
-
-  for (var i = 0; i < array1.length; i++) {
-    product += array1[i] * array2[i];
-  }
-
-  return product;
-};
-
-auxiliary.mag = function (array) {
-  return Math.sqrt(this.dotProduct(array, array));
-};
-
-auxiliary.normalize = function (array) {
-  var result = [];
-  var magnitude = this.mag(array);
-
-  for (var i = 0; i < array.length; i++) {
-    result[i] = array[i] / magnitude;
-  }
-
-  return result;
-};
-
-module.exports = auxiliary;
-
-/***/ }),
 /* 4 */
@@ -413,2 +755,3 @@ /***/ (function(module, exports, __webpack_require__) {
 
+var aux = __webpack_require__(1);
 var CoSELayout = __webpack_require__(0).CoSELayout;
@@ -434,3 +777,3 @@ var CoSENode = __webpack_require__(0).CoSENode;
 
-  if (options.randomize && nodes.length > 2) {
+  if (options.randomize && spectralResult) {
     nodeIndexes = spectralResult["nodeIndexes"];
@@ -443,25 +786,2 @@ xCoords = spectralResult["xCoords"];
 
-  // get the top most nodes
-  var getTopMostNodes = function getTopMostNodes(nodes) {
-    var nodesMap = {};
-    for (var i = 0; i < nodes.length; i++) {
-      nodesMap[nodes[i].id()] = true;
-    }
-    var roots = nodes.filter(function (ele, i) {
-      if (typeof ele === "number") {
-        ele = i;
-      }
-      var parent = ele.parent()[0];
-      while (parent != null) {
-        if (nodesMap[parent.id()]) {
-          return false;
-        }
-        parent = parent.parent()[0];
-      }
-      return true;
-    });
-
-    return roots;
-  };
-
   // transfer cytoscape nodes to cose nodes
@@ -480,7 +800,7 @@ var processChildrenList = function processChildrenList(parent, children, layout, options) {
       if (theChild.outerWidth() != null && theChild.outerHeight() != null) {
-        if (options.randomize && nodes.length > 2) {
+        if (options.randomize && spectralResult) {
           if (!theChild.isParent()) {
             theNode = parent.add(new CoSENode(layout.graphManager, new PointD(xCoords[nodeIndexes.get(theChild.id())] - dimensions.w / 2, yCoords[nodeIndexes.get(theChild.id())] - dimensions.h / 2), new DimensionD(parseFloat(dimensions.w), parseFloat(dimensions.h))));
           } else {
-            var parentInfo = calcBoundingBox(theChild);
+            var parentInfo = aux.calcBoundingBox(theChild, xCoords, yCoords, nodeIndexes);
             theNode = parent.add(new CoSENode(layout.graphManager, new PointD(parentInfo.topLeftX, parentInfo.topLeftY), new DimensionD(parentInfo.width, parentInfo.height)));
@@ -531,47 +851,2 @@ }
     }
-    function calcBoundingBox(parentNode) {
-      // calculate bounds
-      var left = Number.MAX_VALUE;
-      var right = Number.MIN_VALUE;
-      var top = Number.MAX_VALUE;
-      var bottom = Number.MIN_VALUE;
-      var nodeLeft = void 0;
-      var nodeRight = void 0;
-      var nodeTop = void 0;
-      var nodeBottom = void 0;
-
-      var nodes = parentNode.descendants().not(":parent");
-      var s = nodes.length;
-      for (var _i = 0; _i < s; _i++) {
-        var node = nodes[_i];
-
-        nodeLeft = xCoords[nodeIndexes.get(node.id())] - node.width() / 2;
-        nodeRight = xCoords[nodeIndexes.get(node.id())] + node.width() / 2;
-        nodeTop = yCoords[nodeIndexes.get(node.id())] - node.height() / 2;
-        nodeBottom = yCoords[nodeIndexes.get(node.id())] + node.height() / 2;
-
-        if (left > nodeLeft) {
-          left = nodeLeft;
-        }
-
-        if (right < nodeRight) {
-          right = nodeRight;
-        }
-
-        if (top > nodeTop) {
-          top = nodeTop;
-        }
-
-        if (bottom < nodeBottom) {
-          bottom = nodeBottom;
-        }
-      }
-
-      var boundingBox = {};
-      boundingBox.topLeftX = left;
-      boundingBox.topLeftY = top;
-      boundingBox.width = right - left;
-      boundingBox.height = top - bottom;
-      return boundingBox;
-    }
   };
@@ -619,3 +894,3 @@
 
-  processChildrenList(gm.addRoot(), getTopMostNodes(nodes), coseLayout, options);
+  processChildrenList(gm.addRoot(), aux.getTopMostNodes(nodes), coseLayout, options);
 
@@ -642,5 +917,4 @@ processEdges(coseLayout, gm, edges);
 
-var aux = __webpack_require__(3);
+var aux = __webpack_require__(1);
 var numeric = __webpack_require__(7);
-var LinkedList = __webpack_require__(0).layoutBase.LinkedList;
 
@@ -653,2 +927,3 @@ // main function that spectral layout is processed
   var nodes = eles.nodes();
+  var parentNodes = eles.nodes(":parent");
 
@@ -681,102 +956,2 @@ var dummyNodes = new Map(); // map to keep dummy nodes and their neighbors
 
-  // get the top most nodes
-  var getTopMostNodes = function getTopMostNodes(nodes) {
-    var nodesMap = {};
-    for (var i = 0; i < nodes.length; i++) {
-      nodesMap[nodes[i].id()] = true;
-    }
-    var roots = nodes.filter(function (ele, i) {
-      if (typeof ele === "number") {
-        ele = i;
-      }
-      var parent = ele.parent()[0];
-      while (parent != null) {
-        if (nodesMap[parent.id()]) {
-          return false;
-        }
-        parent = parent.parent()[0];
-      }
-      return true;
-    });
-
-    return roots;
-  };
-
-  // find disconnected components and create dummy nodes that connect them
-  var connectComponents = function connectComponents(topMostNodes) {
-    var queue = new LinkedList();
-    var visited = new Set();
-    var visitedTopMostNodes = [];
-    var currentNeighbor = void 0;
-    var minDegreeNode = void 0;
-    var minDegree = void 0;
-
-    var isConnected = false;
-    var count = 1;
-    var nodesConnectedToDummy = [];
-
-    do {
-      var currentNode = topMostNodes[0];
-      var childrenOfCurrentNode = currentNode.union(currentNode.descendants());
-      visitedTopMostNodes.push(currentNode);
-
-      childrenOfCurrentNode.forEach(function (node) {
-        queue.push(node);
-        visited.add(node);
-      });
-
-      while (queue.length != 0) {
-        currentNode = queue.shift();
-
-        // Traverse all neighbors of this node
-        var neighborNodes = currentNode.neighborhood().nodes();
-        for (var i = 0; i < neighborNodes.length; i++) {
-          var neighborNode = neighborNodes[i];
-          currentNeighbor = topMostNodes.intersection(neighborNode.union(neighborNode.ancestors()));
-          if (currentNeighbor != null && !visited.has(currentNeighbor[0])) {
-            var childrenOfNeighbor = currentNeighbor.union(currentNeighbor.descendants());
-
-            childrenOfNeighbor.forEach(function (node) {
-              queue.push(node);
-              visited.add(node);
-              if (topMostNodes.has(node)) {
-                visitedTopMostNodes.push(node);
-              }
-            });
-          }
-        }
-      }
-
-      if (visitedTopMostNodes.length == topMostNodes.length) {
-        isConnected = true;
-      }
-
-      if (!isConnected || isConnected && count > 1) {
-        (function () {
-          minDegreeNode = visitedTopMostNodes[0];
-          minDegree = minDegreeNode.connectedEdges().length;
-          visitedTopMostNodes.forEach(function (node) {
-            if (node.connectedEdges().length < minDegree) {
-              minDegree = node.connectedEdges().length;
-              minDegreeNode = node;
-            }
-          });
-          nodesConnectedToDummy.push(minDegreeNode.id());
-          // TO DO: Check efficiency of this part
-          var temp = visitedTopMostNodes[0];
-          visitedTopMostNodes.forEach(function (node) {
-            temp = temp.union(node);
-          });
-          visitedTopMostNodes = [];
-          topMostNodes = topMostNodes.difference(temp);
-          count++;
-        })();
-      }
-    } while (!isConnected);
-
-    if (nodesConnectedToDummy.length > 0) {
-      dummyNodes.set('dummy' + (dummyNodes.size + 1), nodesConnectedToDummy);
-    }
-  };
-
   /**** Spectral layout functions ****/
@@ -1025,6 +1200,6 @@
   // connect disconnected components (first top level, then inside of each compound node)
-  connectComponents(getTopMostNodes(nodes));
+  aux.connectComponents(cy, eles, aux.getTopMostNodes(nodes), dummyNodes);
 
-  cy.nodes(":parent").forEach(function (ele) {
-    connectComponents(getTopMostNodes(ele.descendants()));
+  parentNodes.forEach(function (ele) {
+    aux.connectComponents(cy, eles, aux.getTopMostNodes(ele.descendants()), dummyNodes);
   });
@@ -1072,3 +1247,3 @@
   // form a parent-child map to keep representative node of each compound node  
-  cy.nodes(":parent").forEach(function (ele) {
+  parentNodes.forEach(function (ele) {
     var children = ele.children();
@@ -1095,3 +1270,3 @@
   // add neighborhood relations (first real, then dummy nodes)
-  cy.nodes().forEach(function (ele) {
+  nodes.forEach(function (ele) {
     var eleIndex = void 0;
@@ -1102,3 +1277,5 @@
     ele.neighborhood().nodes().forEach(function (node) {
-      if (node.isParent()) allNodesNeighborhood[eleIndex].push(parentChildMap.get(node.id()));else allNodesNeighborhood[eleIndex].push(node.id());
+      if (eles.contains(ele.edgesWith(node))) {
+        if (node.isParent()) allNodesNeighborhood[eleIndex].push(parentChildMap.get(node.id()));else allNodesNeighborhood[eleIndex].push(node.id());
+      }
     });
@@ -1146,22 +1323,32 @@ });
   nodeSize = nodeIndexes.size;
-  // if # of nodes in transformed graph is smaller than sample size,
-  // then use # of nodes as sample size
-  sampleSize = nodeSize < options.sampleSize ? nodeSize : options.sampleSize;
 
-  // instantiates the partial matrices that will be used in spectral layout
-  for (var _i14 = 0; _i14 < nodeSize; _i14++) {
-    C[_i14] = [];
-  }
-  for (var _i15 = 0; _i15 < sampleSize; _i15++) {
-    INV[_i15] = [];
-  }
+  var spectralResult = void 0;
 
-  /**** Apply spectral layout ****/
+  // If number of nodes in transformed graph is 1 or 2, either SVD or powerIteration causes problem
+  // So skip spectral and layout the graph with cose
+  if (nodeSize > 2) {
+    // if # of nodes in transformed graph is smaller than sample size,
+    // then use # of nodes as sample size
+    sampleSize = nodeSize < options.sampleSize ? nodeSize : options.sampleSize;
 
-  allBFS(samplingType);
-  sample();
-  powerIteration();
+    // instantiates the partial matrices that will be used in spectral layout
+    for (var _i14 = 0; _i14 < nodeSize; _i14++) {
+      C[_i14] = [];
+    }
+    for (var _i15 = 0; _i15 < sampleSize; _i15++) {
+      INV[_i15] = [];
+    }
 
-  var spectralResult = { nodeIndexes: nodeIndexes, xCoords: xCoords, yCoords: yCoords };
-  return spectralResult;
+    /**** Apply spectral layout ****/
+
+    allBFS(samplingType);
+    sample();
+    powerIteration();
+
+    spectralResult = { nodeIndexes: nodeIndexes, xCoords: xCoords, yCoords: yCoords };
+    return spectralResult;
+  } else {
+    spectralResult = false;
+    return spectralResult;
+  }
 };
@@ -1178,3 +1365,3 @@
 
-var impl = __webpack_require__(1);
+var impl = __webpack_require__(2);
 
@@ -1181,0 +1368,0 @@ // registers the extension on a cytoscape lib ref

package.json

 {
   "name": "cytoscape-fcose",
-  "version": "1.0.0",
+  "version": "1.1.0",
   "description": "The fCoSE layout for Cytoscape.js by Bilkent with fast compound node placement",
@@ -5,0 +5,0 @@ "main": "cytoscape-fcose.js",

README.md

@@ -15,2 +15,4 @@ cytoscape-fcose
 
+A. Civril, M. Magdon-Ismail, and E. Bocek-Rivele, "[SSDE: Fast Graph Drawing Using Sampled Spectral Distance Embedding](https://link.springer.com/chapter/10.1007/978-3-540-70904-6_5)", International Symposium on Graph Drawing, pp. 30-41, 2006.
+
 ## Dependencies
@@ -21,2 +23,3 @@
  * cose-base ^1.0.0
+ * cytoscape-layout-utilities.js (optional for packing disconnected components) ^1.0.0
 
@@ -59,5 +62,12 @@
 
-Plain HTML/JS has the extension registered for you automatically, because no `require()` is needed.
+Plain HTML/JS has the extension registered for you automatically, because no `require()` is needed. Just add the following files:
 
+```
+<script src="https://unpkg.com/numeric/numeric-1.2.6.js"></script>
+<script src="https://unpkg.com/layout-base/layout-base.js"></script>
+<script src="https://unpkg.com/cose-base/cose-base.js"></script>
+<script src="cytoscape-fcose.js"></script>
+```
 
+
 ## API
@@ -90,2 +100,4 @@
   nodeDimensionsIncludeLabels: false,
+  // whether to pack disconnected components - valid only if randomize: true
+  packComponents: true,
   
@@ -118,3 +130,3 @@ /* spectral layout options */
   // For enabling tiling
-  tile: false,  
+  tile: true,  
   // Represents the amount of the vertical space to put between the zero degree members during the tiling operation(can also be a function)
@@ -121,0 +133,0 @@ tilingPaddingVertical: 10,

src/fcose/auxiliary.js

 /*
- * Auxiliary functions used in spectral layout (especially in power iteration)
+ * Auxiliary functions
  */
 
+const LinkedList = require('cose-base').layoutBase.LinkedList;
+
 let auxiliary = {};
@@ -118,2 +120,179 @@
 
+// get the top most nodes
+auxiliary.getTopMostNodes = function(nodes) {
+  let nodesMap = {};
+  for (let i = 0; i < nodes.length; i++) {
+      nodesMap[nodes[i].id()] = true;
+  }
+  let roots = nodes.filter(function (ele, i) {
+      if(typeof ele === "number") {
+        ele = i;
+      }
+      let parent = ele.parent()[0];
+      while(parent != null){
+        if(nodesMap[parent.id()]){
+          return false;
+        }
+        parent = parent.parent()[0];
+      }
+      return true;
+  });
+
+  return roots;
+};
+
+// find disconnected components and create dummy nodes that connect them
+auxiliary.connectComponents = function(cy, eles, topMostNodes, dummyNodes){      
+  let queue = new LinkedList();
+  let visited = new Set();
+  let visitedTopMostNodes = [];
+  let currentNeighbor;
+  let minDegreeNode;
+  let minDegree;
+
+  let isConnected = false;
+  let count = 1;
+  let nodesConnectedToDummy = [];
+  let components = [];
+
+  do{
+    let cmpt = cy.collection();
+    components.push(cmpt);
+    
+    let currentNode = topMostNodes[0];
+    let childrenOfCurrentNode = cy.collection();
+    childrenOfCurrentNode.merge(currentNode).merge(currentNode.descendants());
+    visitedTopMostNodes.push(currentNode);
+
+    childrenOfCurrentNode.forEach(function(node) {
+      queue.push(node);
+      visited.add(node);
+      cmpt.merge(node);
+    });
+
+    while(queue.length != 0){
+      currentNode = queue.shift();
+
+      // Traverse all neighbors of this node
+      let neighborNodes = cy.collection();
+      currentNode.neighborhood().nodes().forEach(function(node){
+        if(eles.contains(currentNode.edgesWith(node))){
+          neighborNodes.merge(node);
+        }
+      });
+
+      for(let i = 0; i < neighborNodes.length; i++){
+        let neighborNode = neighborNodes[i];
+        currentNeighbor = topMostNodes.intersection(neighborNode.union(neighborNode.ancestors()));
+        if(currentNeighbor != null && !visited.has(currentNeighbor[0])){
+          let childrenOfNeighbor = currentNeighbor.union(currentNeighbor.descendants());
+
+          childrenOfNeighbor.forEach(function(node){
+            queue.push(node);
+            visited.add(node);
+            cmpt.merge(node);
+            if(topMostNodes.has(node)){
+              visitedTopMostNodes.push(node);
+            }
+          });
+
+        }
+      }
+    }
+    
+    cmpt.forEach(node => {
+      node.connectedEdges().forEach(e => { // connectedEdges() usually cached
+        if( cmpt.has(e.source()) && cmpt.has(e.target()) ){ // has() is cheap
+          cmpt.merge(e); // forEach() only considers nodes -- sets N at call time
+        }
+      });
+    });    
+
+    if(visitedTopMostNodes.length == topMostNodes.length){
+      isConnected = true;
+    }
+
+    if(!isConnected || (isConnected && count > 1)){
+      minDegreeNode = visitedTopMostNodes[0];
+      minDegree = minDegreeNode.connectedEdges().length;
+      visitedTopMostNodes.forEach(function(node){
+        if(node.connectedEdges().length < minDegree){
+          minDegree = node.connectedEdges().length;
+          minDegreeNode = node;
+        }
+      });
+      nodesConnectedToDummy.push(minDegreeNode.id());
+      // TO DO: Check efficiency of this part
+      let temp = cy.collection();
+      temp.merge(visitedTopMostNodes[0]);
+      visitedTopMostNodes.forEach(function(node){
+        temp.merge(node);
+      });
+      visitedTopMostNodes = [];
+      topMostNodes = topMostNodes.difference(temp);
+      count++;
+    }
+
+  }
+  while(!isConnected);
+
+  if(dummyNodes){
+    if(nodesConnectedToDummy.length > 0 ){
+        dummyNodes.set('dummy'+(dummyNodes.size+1), nodesConnectedToDummy);
+    }
+  }
+  return components;
+};
+
+auxiliary.calcBoundingBox = function(parentNode, xCoords, yCoords, nodeIndexes){
+    // calculate bounds
+    let left = Number.MAX_VALUE;
+    let right = Number.MIN_VALUE;
+    let top = Number.MAX_VALUE;
+    let bottom = Number.MIN_VALUE;
+    let nodeLeft;
+    let nodeRight;
+    let nodeTop;
+    let nodeBottom;
+
+    let nodes = parentNode.descendants().not(":parent");
+    let s = nodes.length;
+    for (let i = 0; i < s; i++)
+    {
+      let node = nodes[i];
+
+      nodeLeft = xCoords[nodeIndexes.get(node.id())] - node.width()/2;
+      nodeRight = xCoords[nodeIndexes.get(node.id())] + node.width()/2;
+      nodeTop = yCoords[nodeIndexes.get(node.id())] - node.height()/2;
+      nodeBottom = yCoords[nodeIndexes.get(node.id())] + node.height()/2;
+
+      if (left > nodeLeft)
+      {
+        left = nodeLeft;
+      }
+
+      if (right < nodeRight)
+      {
+        right = nodeRight;
+      }
+
+      if (top > nodeTop)
+      {
+        top = nodeTop;
+      }
+
+      if (bottom < nodeBottom)
+      {
+        bottom = nodeBottom;
+      }
+    }
+
+    let boundingBox = {};
+    boundingBox.topLeftX = left;
+    boundingBox.topLeftY = top;
+    boundingBox.width = right - left;
+    boundingBox.height = bottom - top;
+    return boundingBox;
+};
+
 module.exports = auxiliary;

src/fcose/cose.js

@@ -5,2 +5,3 @@ /**
 
+const aux = require('./auxiliary');
 const CoSELayout = require('cose-base').CoSELayout;
@@ -26,3 +27,3 @@ const CoSENode = require('cose-base').CoSENode;
   
-  if(options.randomize && nodes.length > 2){
+  if(options.randomize && spectralResult){
     nodeIndexes = spectralResult["nodeIndexes"];
@@ -35,25 +36,2 @@ xCoords = spectralResult["xCoords"];
 
-  // get the top most nodes
-  let getTopMostNodes = function(nodes) {
-    let nodesMap = {};
-    for (let i = 0; i < nodes.length; i++) {
-        nodesMap[nodes[i].id()] = true;
-    }
-    let roots = nodes.filter(function (ele, i) {
-        if(typeof ele === "number") {
-          ele = i;
-        }
-        let parent = ele.parent()[0];
-        while(parent != null){
-          if(nodesMap[parent.id()]){
-            return false;
-          }
-          parent = parent.parent()[0];
-        }
-        return true;
-    });
-
-    return roots;
-  };
-
   // transfer cytoscape nodes to cose nodes
@@ -73,3 +51,3 @@ let processChildrenList = function (parent, children, layout, options) {
               && theChild.outerHeight() != null) {
-        if(options.randomize && nodes.length > 2){
+        if(options.randomize && spectralResult){
           if(!theChild.isParent()){
@@ -81,3 +59,3 @@ theNode = parent.add(new CoSENode(layout.graphManager,
           else{
-            let parentInfo = calcBoundingBox(theChild);
+            let parentInfo = aux.calcBoundingBox(theChild, xCoords, yCoords, nodeIndexes);
             theNode = parent.add(new CoSENode(layout.graphManager,
@@ -134,52 +112,2 @@ new PointD(parentInfo.topLeftX, parentInfo.topLeftY),
     }
-    function calcBoundingBox(parentNode){
-        // calculate bounds
-        let left = Number.MAX_VALUE;
-        let right = Number.MIN_VALUE;
-        let top = Number.MAX_VALUE;
-        let bottom = Number.MIN_VALUE;
-        let nodeLeft;
-        let nodeRight;
-        let nodeTop;
-        let nodeBottom;
-
-        let nodes = parentNode.descendants().not(":parent");
-        let s = nodes.length;
-        for (let i = 0; i < s; i++)
-        {
-          let node = nodes[i];
-
-          nodeLeft = xCoords[nodeIndexes.get(node.id())] - node.width()/2;
-          nodeRight = xCoords[nodeIndexes.get(node.id())] + node.width()/2;
-          nodeTop = yCoords[nodeIndexes.get(node.id())] - node.height()/2;
-          nodeBottom = yCoords[nodeIndexes.get(node.id())] + node.height()/2;
-
-          if (left > nodeLeft)
-          {
-            left = nodeLeft;
-          }
-
-          if (right < nodeRight)
-          {
-            right = nodeRight;
-          }
-
-          if (top > nodeTop)
-          {
-            top = nodeTop;
-          }
-
-          if (bottom < nodeBottom)
-          {
-            bottom = nodeBottom;
-          }
-        }
-
-        let boundingBox = {};
-        boundingBox.topLeftX = left;
-        boundingBox.topLeftY = top;
-        boundingBox.width = right - left;
-        boundingBox.height = top - bottom;
-        return boundingBox;
-    }
   };   
@@ -243,3 +171,3 @@
 
-  processChildrenList(gm.addRoot(), getTopMostNodes(nodes), coseLayout, options);
+  processChildrenList(gm.addRoot(), aux.getTopMostNodes(nodes), coseLayout, options);
 
@@ -246,0 +174,0 @@ processEdges(coseLayout, gm, edges);

src/fcose/index.js

@@ -6,4 +6,5 @@ /**
 const assign = require('../assign');
-const { spectralLayout }= require('./spectral');
-const { coseLayout }= require('./cose');
+const aux = require('./auxiliary');
+const { spectralLayout } = require('./spectral');
+const { coseLayout } = require('./cose');
 
@@ -32,2 +33,4 @@ const defaults = Object.freeze({
   nodeDimensionsIncludeLabels: false,
+  // whether to pack disconnected components - valid only if randomize: true
+  packComponents: true,
   
@@ -60,3 +63,3 @@ /* spectral layout options */
   // For enabling tiling
-  tile: false,  
+  tile: true,  
   // Represents the amount of the vertical space to put between the zero degree members during the tiling operation(can also be a function)
@@ -88,21 +91,171 @@ tilingPaddingVertical: 10,
     let options = this.options;
+    let cy = options.cy;
     let eles = options.eles;
    
-    let spectralResult;
+    let spectralResult = [];
     let xCoords;
     let yCoords;
-    let coseResult;
+    let coseResult = [];
+    let components;
+
+    let layUtil;
+    let packingEnabled = false;
+    if(cy.layoutUtilities && options.packComponents && options.randomize){
+      layUtil = cy.layoutUtilities("get");
+      if(!layUtil)
+        layUtil = cy.layoutUtilities();
+      packingEnabled = true;
+    }
+
+    if(options.eles.length == 0)
+      return;
+
+    if(options.eles.length != options.cy.elements().length){
+      let prevNodes = eles.nodes();
+      eles = eles.union(eles.descendants());
+      
+      eles.forEach(function(ele){
+        if(ele.isNode()){
+          let connectedEdges = ele.connectedEdges();
+          connectedEdges.forEach(function(edge){
+            if(eles.contains(edge.source()) && eles.contains(edge.target()) && !prevNodes.contains(edge.source().union(edge.target()))){
+              eles = eles.union(edge);
+            }
+          });
+        }
+      });
+
+      options.eles = eles;
+    }
+
+    if(packingEnabled){
+      let topMostNodes = aux.getTopMostNodes(options.eles.nodes());
+      components = aux.connectComponents(cy, options.eles, topMostNodes);      
+    }
+      
+    if(options.randomize){
+      if(packingEnabled){
+        components.forEach(function(component){
+          options.eles = component;
+          spectralResult.push(spectralLayout(options));
+        });
+      }
+      else{
+        // Apply spectral layout
+        spectralResult.push(spectralLayout(options));
+        if(spectralResult[0]){
+          xCoords = spectralResult[0]["xCoords"];
+          yCoords = spectralResult[0]["yCoords"];
+        }
+      }     
+    }
     
-    // If number of nodes is 1 or 2, either SVD or powerIteration causes problem
-    // So direct the graph to cose layout
-    if(options.randomize && eles.nodes().length > 2){
-      // Apply spectral layout
-      spectralResult = spectralLayout(options);
-      xCoords = spectralResult["xCoords"];
-      yCoords = spectralResult["yCoords"];
+    if(options.quality == "default" || options.quality == "proof" || spectralResult.includes(false)){  
+      if(packingEnabled){
+        if(options.quality == "draft" && spectralResult.includes(false)){
+          spectralResult.forEach(function(value, index){
+            if(!value){
+              options.eles = components[index];
+              let tempResult = coseLayout(options, spectralResult[index]);
+              let nodeIndexes = new Map();
+              let xCoords = [];
+              let yCoords = [];
+              let count = 0;
+              Object.keys(tempResult).forEach(function (item) {
+                nodeIndexes.set(item, count++);
+                xCoords.push(tempResult[item].getCenterX());
+                yCoords.push(tempResult[item].getCenterY());
+              });
+              spectralResult[index] = {nodeIndexes: nodeIndexes, xCoords: xCoords, yCoords: yCoords};
+            }
+          });
+        }
+        else{
+          let toBeTiledNodes = cy.collection();
+          if(options.tile){
+            let nodeIndexes = new Map();
+            let xCoords = [];
+            let yCoords = [];
+            let count = 0;
+            let tempSpectralResult = {nodeIndexes: nodeIndexes, xCoords: xCoords, yCoords: yCoords};
+            let indexesToBeDeleted = [];
+            components.forEach(function(component, index){
+                if(component.edges().length == 0){
+                  component.nodes().forEach(function(node, i){
+                    toBeTiledNodes.merge(component.nodes()[i]);
+                    if(!node.isParent()){
+                      tempSpectralResult.nodeIndexes.set(component.nodes()[i].id(), count++);
+                      tempSpectralResult.xCoords.push(component.nodes()[0].position().x);
+                      tempSpectralResult.yCoords.push(component.nodes()[0].position().y);
+                    }
+                  });
+                  indexesToBeDeleted.push(index);
+                }              
+            });
+            if(toBeTiledNodes.length > 1){
+              components.push(toBeTiledNodes);
+              for(let i = indexesToBeDeleted.length-1; i >= 0; i--){
+                components.splice(indexesToBeDeleted[i], 1);
+                spectralResult.splice(indexesToBeDeleted[i], 1);
+              };
+              spectralResult.push(tempSpectralResult);
+            }
+          }
+          components.forEach(function(component, index){
+            options.eles = component;
+            coseResult.push(coseLayout(options, spectralResult[index]));
+          });
+        }
+      }
+      else{
+        // Apply cose layout as postprocessing
+        coseResult.push(coseLayout(options, spectralResult[0]));
+      }
     }
     
-    if(options.quality == "default" || options.quality == "proof" || eles.nodes().length <= 2){  
-      // Apply cose layout as postprocessing
-      coseResult = coseLayout(options, spectralResult);
+    if(packingEnabled){
+      let subgraphs = [];  
+      components.forEach(function(component, index){
+        let nodeIndexes;
+        if(options.quality == "draft"){
+          nodeIndexes = spectralResult[index].nodeIndexes;
+        }
+        let subgraph = {};
+        subgraph.nodes = [];
+        subgraph.edges = [];
+        let nodeIndex;
+        component.nodes().forEach(function (node) {
+          if(options.quality == "draft"){
+            if(!node.isParent()){
+              nodeIndex = nodeIndexes.get(node.id());
+              subgraph.nodes.push({x: spectralResult[index].xCoords[nodeIndex] - node.bb().w/2, y: spectralResult[index].yCoords[nodeIndex] - node.bb().h/2, width: node.bb().w, height: node.bb().h});              
+            }
+            else{
+              let parentInfo = aux.calcBoundingBox(node, spectralResult[index].xCoords, spectralResult[index].yCoords, nodeIndexes);
+              subgraph.nodes.push({x: parentInfo.topLeftX, y: parentInfo.topLeftY, width: parentInfo.width, height: parentInfo.height}); 
+            }   
+          }
+          else{
+            subgraph.nodes.push({x: coseResult[index][node.id()].getLeft(), y: coseResult[index][node.id()].getTop(), width: coseResult[index][node.id()].getWidth(), height: coseResult[index][node.id()].getHeight()});
+          }
+        });
+        subgraphs.push(subgraph);
+      });
+      let shiftResult = layUtil.packComponents(subgraphs).shifts;
+      if(options.quality == "draft"){
+        spectralResult.forEach(function(result, index){
+          let newXCoords = result.xCoords.map(x => x + shiftResult[index].dx);
+          let newYCoords = result.yCoords.map(y => y + shiftResult[index].dy);
+          result.xCoords = newXCoords;
+          result.yCoords = newYCoords;
+        });
+      }
+      else{
+        coseResult.forEach(function(result, index){
+          Object.keys(result).forEach(function (item) {
+            let nodeRectangle = result[item];
+            nodeRectangle.setCenter(nodeRectangle.getCenterX() + shiftResult[index].dx, nodeRectangle.getCenterY() + shiftResult[index].dy);
+          });
+        });        
+      }
     }
@@ -112,18 +265,29 @@
     let getPositions = function(ele, i ){
-      if(options.quality == "default" || options.quality == "proof") {
+      if(options.quality == "default" || options.quality == "proof" || (options.quality == "proof" && !packingEnabled && spectralResult.includes(false))) {
         if(typeof ele === "number") {
           ele = i;
         }
+        let pos;
         let theId = ele.data('id');
-        let lNode = coseResult[theId];
-
+        coseResult.forEach(function(result){
+          if (theId in result){
+            pos = {x: result[theId].getRect().getCenterX(), y: result[theId].getRect().getCenterY()};
+          }
+        });
         return {
-          x: lNode.getRect().getCenterX(),
-          y: lNode.getRect().getCenterY()
+          x: pos.x,
+          y: pos.y
         };
       }
       else{
+        let pos;
+        spectralResult.forEach(function(result){
+          let index = result.nodeIndexes.get(ele.id());
+          if(index != undefined){
+            pos = {x: result.xCoords[index], y: result.yCoords[index]};
+          };
+        });
         return {
-          x: xCoords[i],
-          y: yCoords[i]
+          x: pos.x,
+          y: pos.y
         };
@@ -136,2 +300,3 @@ }
       // transfer calculated positions to nodes (positions of only simple nodes are evaluated, compounds are positioned automatically)
+      options.eles = eles;
       eles.nodes().not(":parent").layoutPositions(layout, options, getPositions); 
@@ -138,0 +303,0 @@ }

src/fcose/spectral.js

@@ -7,3 +7,2 @@ /**
 const numeric = require('numeric');
-const LinkedList = require('cose-base').layoutBase.LinkedList;
 
@@ -15,4 +14,5 @@ // main function that spectral layout is processed
   let eles = options.eles;
-  let nodes = eles.nodes();  
-
+  let nodes = eles.nodes();
+  let parentNodes = eles.nodes(":parent");
+  
   let dummyNodes = new Map();  // map to keep dummy nodes and their neighbors
@@ -44,103 +44,2 @@ let nodeIndexes = new Map();  // map to keep indexes to nodes
 
-  // get the top most nodes
-  let getTopMostNodes = function(nodes) {
-    let nodesMap = {};
-    for (let i = 0; i < nodes.length; i++) {
-        nodesMap[nodes[i].id()] = true;
-    }
-    let roots = nodes.filter(function (ele, i) {
-        if(typeof ele === "number") {
-          ele = i;
-        }
-        let parent = ele.parent()[0];
-        while(parent != null){
-          if(nodesMap[parent.id()]){
-            return false;
-          }
-          parent = parent.parent()[0];
-        }
-        return true;
-    });
-
-    return roots;
-  };  
-
-  // find disconnected components and create dummy nodes that connect them
-  let connectComponents = function(topMostNodes){      
-    let queue = new LinkedList();
-    let visited = new Set();
-    let visitedTopMostNodes = [];
-    let currentNeighbor;
-    let minDegreeNode;
-    let minDegree;
-
-    let isConnected = false;
-    let count = 1;
-    let nodesConnectedToDummy = [];
-
-    do{
-      let currentNode = topMostNodes[0];
-      let childrenOfCurrentNode = currentNode.union(currentNode.descendants());
-      visitedTopMostNodes.push(currentNode);
-
-      childrenOfCurrentNode.forEach(function(node) {
-        queue.push(node);
-        visited.add(node);
-      });
-
-      while(queue.length != 0){
-        currentNode = queue.shift();
-
-        // Traverse all neighbors of this node
-        let neighborNodes = currentNode.neighborhood().nodes();
-        for(let i = 0; i < neighborNodes.length; i++){
-          let neighborNode = neighborNodes[i];
-          currentNeighbor = topMostNodes.intersection(neighborNode.union(neighborNode.ancestors()));
-          if(currentNeighbor != null && !visited.has(currentNeighbor[0])){
-            let childrenOfNeighbor = currentNeighbor.union(currentNeighbor.descendants());
-
-            childrenOfNeighbor.forEach(function(node){
-              queue.push(node);
-              visited.add(node);
-              if(topMostNodes.has(node)){
-                visitedTopMostNodes.push(node);
-              }
-            });
-
-          }
-        }
-      }
-
-      if(visitedTopMostNodes.length == topMostNodes.length){
-        isConnected = true;
-      }
-
-      if(!isConnected || (isConnected && count > 1)){
-        minDegreeNode = visitedTopMostNodes[0];
-        minDegree = minDegreeNode.connectedEdges().length;
-        visitedTopMostNodes.forEach(function(node){
-          if(node.connectedEdges().length < minDegree){
-            minDegree = node.connectedEdges().length;
-            minDegreeNode = node;
-          }
-        });
-        nodesConnectedToDummy.push(minDegreeNode.id());
-        // TO DO: Check efficiency of this part
-        let temp = visitedTopMostNodes[0];
-        visitedTopMostNodes.forEach(function(node){
-          temp = temp.union(node);
-        });
-        visitedTopMostNodes = [];
-        topMostNodes = topMostNodes.difference(temp);
-        count++;
-      }
-
-    }
-    while(!isConnected);
-
-    if(nodesConnectedToDummy.length > 0 ){
-        dummyNodes.set('dummy'+(dummyNodes.size+1), nodesConnectedToDummy);
-    }
-  };
-
   /**** Spectral layout functions ****/
@@ -396,6 +295,6 @@
   // connect disconnected components (first top level, then inside of each compound node)
-  connectComponents(getTopMostNodes(nodes));
+  aux.connectComponents(cy, eles, aux.getTopMostNodes(nodes), dummyNodes);
 
-  cy.nodes(":parent").forEach(function( ele ){
-    connectComponents(getTopMostNodes(ele.descendants()));
+  parentNodes.forEach(function( ele ){
+    aux.connectComponents(cy, eles, aux.getTopMostNodes(ele.descendants()), dummyNodes);
   });
@@ -421,25 +320,25 @@
   // form a parent-child map to keep representative node of each compound node  
-  cy.nodes(":parent").forEach(function( ele ){
-    let children = ele.children();
+  parentNodes.forEach(function( ele ){
+      let children = ele.children();
 
-//      let random = 0;
-    while(children.nodes(":childless").length == 0){
-//        random = Math.floor(Math.random() * children.nodes().length); // if all children are compound then proceed randomly
-      children = children.nodes()[0].children();
-    }
-    //  select the representative node - we can apply different methods here
-//      random = Math.floor(Math.random() * children.nodes(":childless").length);
-    let index = 0;
-    let min = children.nodes(":childless")[0].connectedEdges().length;
-    children.nodes(":childless").forEach(function(ele2, i){
-      if(ele2.connectedEdges().length < min){
-        min = ele2.connectedEdges().length;
-        index = i;
+  //      let random = 0;
+      while(children.nodes(":childless").length == 0){
+  //        random = Math.floor(Math.random() * children.nodes().length); // if all children are compound then proceed randomly
+        children = children.nodes()[0].children();
       }
-    });
-    parentChildMap.set(ele.id(), children.nodes(":childless")[index].id());
+      //  select the representative node - we can apply different methods here
+  //      random = Math.floor(Math.random() * children.nodes(":childless").length);
+      let index = 0;
+      let min = children.nodes(":childless")[0].connectedEdges().length;
+      children.nodes(":childless").forEach(function(ele2, i){
+        if(ele2.connectedEdges().length < min){
+          min = ele2.connectedEdges().length;
+          index = i;
+        }
+      });
+      parentChildMap.set(ele.id(), children.nodes(":childless")[index].id());
   }); 
 
   // add neighborhood relations (first real, then dummy nodes)
-  cy.nodes().forEach(function( ele ){
+  nodes.forEach(function( ele ){
     let eleIndex;
@@ -453,6 +352,8 @@
     ele.neighborhood().nodes().forEach(function(node){
-      if(node.isParent())
-        allNodesNeighborhood[eleIndex].push(parentChildMap.get(node.id()));       
-      else
-        allNodesNeighborhood[eleIndex].push(node.id());          
+      if(eles.contains(ele.edgesWith(node))){
+        if(node.isParent())
+          allNodesNeighborhood[eleIndex].push(parentChildMap.get(node.id()));       
+        else
+          allNodesNeighborhood[eleIndex].push(node.id()); 
+      }
     });
@@ -477,24 +378,35 @@ });
   nodeSize = nodeIndexes.size;
-  // if # of nodes in transformed graph is smaller than sample size,
-  // then use # of nodes as sample size
-  sampleSize = nodeSize < options.sampleSize ? nodeSize : options.sampleSize;
+  
+  let spectralResult;
+  
+  // If number of nodes in transformed graph is 1 or 2, either SVD or powerIteration causes problem
+  // So skip spectral and layout the graph with cose
+  if(nodeSize > 2) {
+    // if # of nodes in transformed graph is smaller than sample size,
+    // then use # of nodes as sample size
+    sampleSize = nodeSize < options.sampleSize ? nodeSize : options.sampleSize;
 
-  // instantiates the partial matrices that will be used in spectral layout
-  for(let i = 0; i < nodeSize; i++){
-    C[i] = [];
-  }
-  for(let i = 0; i < sampleSize; i++){
-    INV[i] = [];
-  } 
+    // instantiates the partial matrices that will be used in spectral layout
+    for(let i = 0; i < nodeSize; i++){
+      C[i] = [];
+    }
+    for(let i = 0; i < sampleSize; i++){
+      INV[i] = [];
+    } 
 
-  /**** Apply spectral layout ****/
+    /**** Apply spectral layout ****/
 
-  allBFS(samplingType);  
-  sample();
-  powerIteration();
+    allBFS(samplingType);  
+    sample();
+    powerIteration();
 
-  let spectralResult = { nodeIndexes: nodeIndexes, xCoords: xCoords, yCoords: yCoords };
-  return spectralResult;
+    spectralResult = { nodeIndexes: nodeIndexes, xCoords: xCoords, yCoords: yCoords };
+    return spectralResult;
+  }
+  else {
+    spectralResult = false;
+    return spectralResult;
+  }
 };
 
 module.exports = { spectralLayout };

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

137552

increased by13.92%

Lines of code

2226

increased by18.59%

Number of lines in readme file

173

increased by7.45%

No dependency changes