@antv/algorithm - npm Package Compare versions

Comparing version 0.0.3 to 0.0.4

dist/index.js

 (function (global, factory) {
   typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports) :
   typeof define === 'function' && define.amd ? define(['exports'], factory) :
-  (global = typeof globalThis !== 'undefined' ? globalThis : global || self, factory(global.graphLgorithm = {}));
+  (global = typeof globalThis !== 'undefined' ? globalThis : global || self, factory(global.algorithm = {}));
 }(this, (function (exports) { 'use strict';
@@ -496,3 +496,5 @@
    */
-  var getNeighbors = function getNeighbors(nodeId, edges, type) {
+  var getNeighbors = function getNeighbors(nodeId) {
+    var edges = arguments.length > 1 && arguments[1] !== undefined ? arguments[1] : [];
+    var type = arguments.length > 2 ? arguments[2] : undefined;
     var currentEdges = edges.filter(function (edge) {
@@ -562,44 +564,3 @@ return edge.source === nodeId || edge.target === nodeId;
   };
-  /**
-   * get adjacency matrix
-   * @param data graph data
-   * @param directed whether it's a directed graph
-   */
 
-  var getAdjMatrix = function getAdjMatrix(graphData, directed) {
-    var nodes = graphData.nodes,
-        edges = graphData.edges;
-    var matrix = []; // map node with index in data.nodes
-
-    var nodeMap = {};
-
-    if (!nodes) {
-      throw new Error('invalid nodes data!');
-    }
-
-    if (nodes) {
-      nodes.forEach(function (node, i) {
-        nodeMap[node.id] = i;
-        var row = [];
-        matrix.push(row);
-      });
-    }
-
-    if (edges) {
-      edges.forEach(function (e) {
-        var source = e.source,
-            target = e.target;
-        var sIndex = nodeMap[source];
-        var tIndex = nodeMap[target];
-        matrix[sIndex][tIndex] = 1;
-
-        if (!directed) {
-          matrix[tIndex][sIndex] = 1;
-        }
-      });
-    }
-
-    return matrix;
-  };
-
   /**
@@ -650,3 +611,4 @@ *
     var nodeQueue = new Queue();
-    var edges = graphData.edges; // 初始化队列元素
+    var _graphData$edges = graphData.edges,
+        edges = _graphData$edges === void 0 ? [] : _graphData$edges; // 初始化队列元素
 
@@ -690,5 +652,7 @@ nodeQueue.enqueue(startNodeId);
 
-  function detectConnectedComponents(graphData) {
-    var nodes = graphData.nodes,
-        edges = graphData.edges;
+  var detectConnectedComponents = function detectConnectedComponents(graphData) {
+    var _graphData$nodes = graphData.nodes,
+        nodes = _graphData$nodes === void 0 ? [] : _graphData$nodes,
+        _graphData$edges = graphData.edges,
+        edges = _graphData$edges === void 0 ? [] : _graphData$edges;
     var allComponents = [];
@@ -739,3 +703,3 @@ var visited = {};
     return allComponents;
-  }
+  };
   /**
@@ -750,5 +714,7 @@ * Tarjan's Algorithm 复杂度  O(|V|+|E|)
 
-  function detectStrongConnectComponents(graphData) {
-    var nodes = graphData.nodes,
-        edges = graphData.edges;
+  var detectStrongConnectComponents = function detectStrongConnectComponents(graphData) {
+    var _graphData$nodes2 = graphData.nodes,
+        nodes = _graphData$nodes2 === void 0 ? [] : _graphData$nodes2,
+        _graphData$edges2 = graphData.edges,
+        edges = _graphData$edges2 === void 0 ? [] : _graphData$edges2;
     var nodeStack = [];
@@ -835,3 +801,3 @@ var inStack = {}; // 辅助判断是否已经在stack中，减少查找开销
     return allComponents;
-  }
+  };
   function getConnectedComponents(graphData, directed) {
@@ -844,4 +810,6 @@ if (directed) return detectStrongConnectComponents(graphData);
     var degrees = {};
-    var nodes = graphData.nodes,
-        edges = graphData.edges;
+    var _graphData$nodes = graphData.nodes,
+        nodes = _graphData$nodes === void 0 ? [] : _graphData$nodes,
+        _graphData$edges = graphData.edges,
+        edges = _graphData$edges === void 0 ? [] : _graphData$edges;
     nodes.forEach(function (node) {
@@ -931,3 +899,5 @@ degrees[node.id] = {
     });
-    getNeighbors(currentNode, graphData.edges, 'target').forEach(function (nextNode) {
+    var _graphData$edges = graphData.edges,
+        edges = _graphData$edges === void 0 ? [] : _graphData$edges;
+    getNeighbors(currentNode, edges, 'target').forEach(function (nextNode) {
       if (callbacks.allowTraversal({
@@ -960,3 +930,4 @@ previous: previousNode,
     var cycle = null;
-    var nodes = graphData.nodes;
+    var _graphData$nodes = graphData.nodes,
+        nodes = _graphData$nodes === void 0 ? [] : _graphData$nodes;
     var dfsParentMap = {}; // 所有没有被访问的节点集合
@@ -1046,4 +1017,6 @@
   var dijkstra = function dijkstra(graphData, source, directed, weightPropertyName) {
-    var nodes = graphData.nodes,
-        edges = graphData.edges;
+    var _graphData$nodes = graphData.nodes,
+        nodes = _graphData$nodes === void 0 ? [] : _graphData$nodes,
+        _graphData$edges = graphData.edges,
+        edges = _graphData$edges === void 0 ? [] : _graphData$edges;
     var marks = {};
@@ -1118,3 +1091,4 @@ var D = {};
     if (start === end) return [[start]];
-    var edges = graphData.edges;
+    var _graphData$edges = graphData.edges,
+        edges = _graphData$edges === void 0 ? [] : _graphData$edges;
     var visited = [start];
@@ -1213,4 +1187,6 @@
     // the origin data
-    var nodes = graphData.nodes,
-        edges = graphData.edges;
+    var _graphData$nodes = graphData.nodes,
+        nodes = _graphData$nodes === void 0 ? [] : _graphData$nodes,
+        _graphData$edges = graphData.edges,
+        edges = _graphData$edges === void 0 ? [] : _graphData$edges;
     var clusters = {};
@@ -1232,3 +1208,3 @@ var nodeMap = {}; // init the clusters and nodeMap
 
-    var adjMatrix = getAdjMatrix(graphData, directed); // the sum of each row in adjacent matrix
+    var adjMatrix$1 = adjMatrix(graphData, directed); // the sum of each row in adjacent matrix
     /**
@@ -1243,3 +1219,3 @@ * neighbor nodes (id for key and weight for value) for each node
     var neighbors = {};
-    adjMatrix.forEach(function (row, i) {
+    adjMatrix$1.forEach(function (row, i) {
       var iid = nodes[i].id;
@@ -1376,4 +1352,6 @@ neighbors[iid] = {};
     // the origin data
-    var nodes = graphData.nodes,
-        edges = graphData.edges;
+    var _graphData$nodes = graphData.nodes,
+        nodes = _graphData$nodes === void 0 ? [] : _graphData$nodes,
+        _graphData$edges = graphData.edges,
+        edges = _graphData$edges === void 0 ? [] : _graphData$edges;
     var clusters = {};
@@ -1395,3 +1373,3 @@ var nodeMap = {}; // init the clusters and nodeMap
 
-    var adjMatrix = getAdjMatrix(graphData, directed); // the sum of each row in adjacent matrix
+    var adjMatrix$1 = adjMatrix(graphData, directed); // the sum of each row in adjacent matrix
 
@@ -1410,3 +1388,3 @@ var ks = [];
     var m = 0;
-    adjMatrix.forEach(function (row, i) {
+    adjMatrix$1.forEach(function (row, i) {
       var k = 0;
@@ -1431,3 +1409,3 @@ var iid = nodes[i].id;
       // whether to terminate the iterations
-      totalModularity = getModularity(nodes, adjMatrix, ks, m);
+      totalModularity = getModularity(nodes, adjMatrix$1, ks, m);
       if (Math.abs(totalModularity - previousModularity) < threshold || iter > 100) break;
@@ -1463,3 +1441,3 @@ previousModularity = totalModularity;
           var scNodeIdx = nodeMap[scNode.id].idx;
-          kiin += adjMatrix[i][scNodeIdx] || 0;
+          kiin += adjMatrix$1[i][scNodeIdx] || 0;
         }); // the modurarity for **removing** the node i from the origin cluster of node i
@@ -1483,3 +1461,3 @@
             var cNodeIdx = nodeMap[cNode.id].idx;
-            neighborClusterKiin += adjMatrix[i][cNodeIdx] || 0;
+            neighborClusterKiin += adjMatrix$1[i][cNodeIdx] || 0;
           }); // modurarity for **adding** node i into this neighbor cluster
@@ -1752,4 +1730,6 @@
     var selectedEdges = [];
-    var nodes = graphData.nodes,
-        edges = graphData.edges;
+    var _graphData$nodes = graphData.nodes,
+        nodes = _graphData$nodes === void 0 ? [] : _graphData$nodes,
+        _graphData$edges = graphData.edges,
+        edges = _graphData$edges === void 0 ? [] : _graphData$edges;
 
@@ -1814,3 +1794,6 @@ if (nodes.length === 0) {
     var selectedEdges = [];
-    var nodes = graphData.nodes;
+    var _graphData$nodes2 = graphData.nodes,
+        nodes = _graphData$nodes2 === void 0 ? [] : _graphData$nodes2,
+        _graphData$edges2 = graphData.edges,
+        edges = _graphData$edges2 === void 0 ? [] : _graphData$edges2;
 
@@ -1822,3 +1805,3 @@ if (nodes.length === 0) {
 
-    var edges = graphData.edges.map(function (edge) {
+    var weightEdges = edges.map(function (edge) {
       return edge;
@@ -1828,3 +1811,3 @@ });
     if (weight) {
-      edges.sort(function (a, b) {
+      weightEdges.sort(function (a, b) {
         return a.weight - b.weight;
@@ -1839,4 +1822,4 @@ });
 
-    while (edges.length > 0) {
-      var curEdge = edges.shift();
+    while (weightEdges.length > 0) {
+      var curEdge = weightEdges.shift();
       var source = curEdge.source;
@@ -1886,4 +1869,6 @@ var target = curEdge.target;
     var maxIterations = 1000;
-    var nodes = graphData.nodes,
-        edges = graphData.edges;
+    var _graphData$nodes = graphData.nodes,
+        nodes = _graphData$nodes === void 0 ? [] : _graphData$nodes,
+        _graphData$edges = graphData.edges,
+        edges = _graphData$edges === void 0 ? [] : _graphData$edges;
     var nodesCount = nodes.length;
@@ -1944,3 +1929,84 @@ var currentRank;
 
-  exports.adjacentMatrix = adjMatrix;
+  var Stack = /*#__PURE__*/function () {
+    function Stack() {
+      var maxStep = arguments.length > 0 && arguments[0] !== undefined ? arguments[0] : 10;
+
+      _classCallCheck(this, Stack);
+
+      this.linkedList = new LinkedList();
+      this.maxStep = maxStep;
+    }
+
+    _createClass(Stack, [{
+      key: "isEmpty",
+
+      /**
+       * 判断栈是否为空，如果链表中没有头部元素，则栈为空
+       */
+      value: function isEmpty() {
+        return !this.linkedList.head;
+      }
+      /**
+       * 是否到定义的栈的最大长度，如果达到最大长度后，不再允许入栈
+       */
+
+    }, {
+      key: "isMaxStack",
+      value: function isMaxStack() {
+        return this.toArray().length >= this.maxStep;
+      }
+      /**
+       * 访问顶端元素
+       */
+
+    }, {
+      key: "peek",
+      value: function peek() {
+        if (this.isEmpty()) {
+          return null;
+        } // 返回头部元素，不删除元素
+
+
+        return this.linkedList.head.value;
+      }
+    }, {
+      key: "push",
+      value: function push(value) {
+        this.linkedList.prepend(value);
+
+        if (this.length > this.maxStep) {
+          this.linkedList.deleteTail();
+        }
+      }
+    }, {
+      key: "pop",
+      value: function pop() {
+        var removeHead = this.linkedList.deleteHead();
+        return removeHead ? removeHead.value : null;
+      }
+    }, {
+      key: "toArray",
+      value: function toArray() {
+        return this.linkedList.toArray().map(function (node) {
+          return node.value;
+        });
+      }
+    }, {
+      key: "clear",
+      value: function clear() {
+        while (!this.isEmpty()) {
+          this.pop();
+        }
+      }
+    }, {
+      key: "length",
+      get: function get() {
+        return this.linkedList.toArray().length;
+      }
+    }]);
+
+    return Stack;
+  }();
+
+  exports.Stack = Stack;
   exports.breadthFirstSearch = breadthFirstSearch;
@@ -1954,2 +2020,3 @@ exports.connectedComponent = getConnectedComponents;
   exports.floydWarshall = floydWarshall;
+  exports.getAdjMatrix = adjMatrix;
   exports.getDegree = degree;
@@ -1956,0 +2023,0 @@ exports.getInDegree = getInDegree;

dist/index.min.js

@@ -1,1 +0,1 @@
-!function(e,t){"object"==typeof exports&&"undefined"!=typeof module?t(exports):"function"==typeof define&&define.amd?define(["exports"],t):t((e="undefined"!=typeof globalThis?globalThis:e||self).graphLgorithm={})}(this,(function(e){"use strict";var t=function(e,t){var n=e.nodes,r=e.edges,i=[],o={};if(!n)throw Error("invalid nodes data!");return n&&n.forEach((function(e,t){o[e.id]=t;i.push([])})),r&&r.forEach((function(e){var n=o[e.source],r=o[e.target];i[n][r]=1,t||(i[r][n]=1)})),i};function n(e,t){if(!(e instanceof t))throw new TypeError("Cannot call a class as a function")}function r(e,t){for(var n=0;t.length>n;n++){var r=t[n];r.enumerable=r.enumerable||!1,r.configurable=!0,"value"in r&&(r.writable=!0),Object.defineProperty(e,r.key,r)}}function i(e,t,n){return t&&r(e.prototype,t),n&&r(e,n),e}function o(e,t){(null==t||t>e.length)&&(t=e.length);for(var n=0,r=Array(t);t>n;n++)r[n]=e[n];return r}function a(e,t){var n;if("undefined"==typeof Symbol||null==e[Symbol.iterator]){if(Array.isArray(e)||(n=function(e,t){if(e){if("string"==typeof e)return o(e,t);var n=Object.prototype.toString.call(e).slice(8,-1);return"Object"===n&&e.constructor&&(n=e.constructor.name),"Map"===n||"Set"===n?Array.from(e):"Arguments"===n||/^(?:Ui|I)nt(?:8|16|32)(?:Clamped)?Array$/.test(n)?o(e,t):void 0}}(e))||t&&e&&"number"==typeof e.length){n&&(e=n);var r=0,i=function(){};return{s:i,n:function(){return e.length>r?{done:!1,value:e[r++]}:{done:!0}},e:function(e){throw e},f:i}}throw new TypeError("Invalid attempt to iterate non-iterable instance.\nIn order to be iterable, non-array objects must have a [Symbol.iterator]() method.")}var a,u=!0,s=!1;return{s:function(){n=e[Symbol.iterator]()},n:function(){var e=n.next();return u=e.done,e},e:function(e){s=!0,a=e},f:function(){try{u||null==n.return||n.return()}finally{if(s)throw a}}}}var u=function(e,t){return e===t},s=function(){function e(t){var r=arguments.length>1&&void 0!==arguments[1]?arguments[1]:null;n(this,e),this.value=t,this.next=r}return i(e,[{key:"toString",value:function(e){return e?e(this.value):"".concat(this.value)}}]),e}(),f=function(){function e(){var t=arguments.length>0&&void 0!==arguments[0]?arguments[0]:u;n(this,e),this.head=null,this.tail=null,this.compare=t}return i(e,[{key:"prepend",value:function(e){var t=new s(e,this.head);return this.head=t,this.tail||(this.tail=t),this}},{key:"append",value:function(e){var t=new s(e);return this.head?(this.tail.next=t,this.tail=t,this):(this.head=t,this.tail=t,this)}},{key:"delete",value:function(e){if(!this.head)return null;for(var t=null;this.head&&this.compare(this.head.value,e);)t=this.head,this.head=this.head.next;var n=this.head;if(null!==n)for(;n.next;)this.compare(n.next.value,e)?(t=n.next,n.next=n.next.next):n=n.next;return this.compare(this.tail.value,e)&&(this.tail=n),t}},{key:"find",value:function(e){var t=e.value,n=void 0===t?void 0:t,r=e.callback,i=void 0===r?void 0:r;if(!this.head)return null;for(var o=this.head;o;){if(i&&i(o.value))return o;if(void 0!==n&&this.compare(o.value,n))return o;o=o.next}return null}},{key:"deleteTail",value:function(){var e=this.tail;if(this.head===this.tail)return this.head=null,this.tail=null,e;for(var t=this.head;t.next;)t.next.next?t=t.next:t.next=null;return this.tail=t,e}},{key:"deleteHead",value:function(){if(!this.head)return null;var e=this.head;return this.head.next?this.head=this.head.next:(this.head=null,this.tail=null),e}},{key:"fromArray",value:function(e){var t=this;return e.forEach((function(e){return t.append(e)})),this}},{key:"toArray",value:function(){for(var e=[],t=this.head;t;)e.push(t),t=t.next;return e}},{key:"reverse",value:function(){for(var e=this.head,t=null,n=null;e;)n=e.next,e.next=t,t=e,e=n;this.tail=this.head,this.head=t}},{key:"toString",value:function(){var e=arguments.length>0&&void 0!==arguments[0]?arguments[0]:void 0;return""+this.toArray().map((function(t){return t.toString(e)}))}}]),e}(),l=function(){function e(){n(this,e),this.linkedList=new f}return i(e,[{key:"isEmpty",value:function(){return!this.linkedList.head}},{key:"peek",value:function(){return this.linkedList.head?this.linkedList.head.value:null}},{key:"enqueue",value:function(e){this.linkedList.append(e)}},{key:"dequeue",value:function(){var e=this.linkedList.deleteHead();return e?e.value:null}},{key:"toString",value:function(e){return this.linkedList.toString(e)}}]),e}(),c=function(e,t,n){var r=t.filter((function(t){return t.source===e||t.target===e}));if("target"===n){return r.filter((function(t){return t.source===e})).map((function(e){return e.target}))}if("source"===n){return r.filter((function(t){return t.target===e})).map((function(e){return e.source}))}return r.map((function(t){return t.source===e?t.target:t.source}))},h=function(e,t){return t.filter((function(t){return t.source===e||t.target===e}))},d=function(){var e=arguments.length>0&&void 0!==arguments[0]?arguments[0]:0;return"".concat(e,"_").concat((new Date).getTime())},v=function(e,t){var n=e.nodes,r=e.edges,i=[],o={};if(!n)throw Error("invalid nodes data!");return n&&n.forEach((function(e,t){o[e.id]=t;i.push([])})),r&&r.forEach((function(e){var n=o[e.source],r=o[e.target];i[n][r]=1,t||(i[r][n]=1)})),i};var g=function(e){var t={},n=e.edges;return e.nodes.forEach((function(e){t[e.id]={degree:0,inDegree:0,outDegree:0}})),n.forEach((function(e){t[e.source].degree++,t[e.source].outDegree++,t[e.target].degree++,t[e.target].inDegree++})),t};function p(e,t,n,r){r.enter({current:t,previous:n}),c(t,e.edges,"target").forEach((function(i){r.allowTraversal({previous:n,current:t,next:i})&&p(e,i,t,r)})),r.leave({current:t,previous:n})}function y(e,t,n){p(e,t,"",function(){var e,t=arguments.length>0&&void 0!==arguments[0]?arguments[0]:{},n=t,r=function(){},i=(e={},function(t){var n=t.next;return!e[n]&&(e[n]=!0,!0)});return n.allowTraversal=t.allowTraversal||i,n.enter=t.enter||r,n.leave=t.leave||r,n}(n))}var m=function(e,t,n,r){var i=e.nodes,o=e.edges,a={},u={},s={};i.forEach((function(e,n){var r=e.id;u[r]=1/0,r===t&&(u[r]=0)}));for(var f=i.length,l=function(e){var t=function(e,t,n){for(var r,i=1/0,o=0;t.length>o;o++){var a=t[o].id;n[a]||e[a]>i||(i=e[a],r=t[o])}return r}(u,i,a),f=t.id;if(a[f]=!0,u[f]===1/0)return"continue";(n?function(e,t){return t.filter((function(t){return t.source===e}))}(f,o):h(f,o)).forEach((function(e){var n=e.target,i=n===f?e.source:n,o=r&&e[r]?e[r]:1;u[i]>u[t.id]+o&&(u[i]=u[t.id]+o,s[i]=t.id)}))},c=0;f>c;c++)l();var d={};for(var v in u){d[v]=[v];for(var g=s[v];void 0!==g;)d[v].unshift(g),g=s[g]}return{length:u,path:d}},k=function(e,t,n,r){for(var i=t.length,o=2*r,a=0,u=0;i>u;u++)for(var s=e[u].clusterId,f=0;i>f;f++){if(s===e[f].clusterId)a+=(t[u][f]||0)-(n[u]||0)*(n[f]||0)/o}return a*=1/o},E=function(){function e(t){n(this,e),this.count=t.length,this.parent={};var r,i=a(t);try{for(i.s();!(r=i.n()).done;){var o=r.value;this.parent[o]=o}}catch(e){i.e(e)}finally{i.f()}}return i(e,[{key:"find",value:function(e){for(;this.parent[e]!==e;)e=this.parent[e];return e}},{key:"union",value:function(e,t){var n=this.find(e),r=this.find(t);n!==r&&(r>n?(this.parent[t]!==t&&this.union(this.parent[t],e),this.parent[t]=this.parent[e]):(this.parent[e]!==e&&this.union(this.parent[e],t),this.parent[e]=this.parent[t]))}},{key:"connected",value:function(e,t){return this.find(e)===this.find(t)}}]),e}(),b=function(e,t){return e-t},x=function(){function e(){var t=arguments.length>0&&void 0!==arguments[0]?arguments[0]:b;n(this,e),this.compareFn=t,this.list=[]}return i(e,[{key:"getLeft",value:function(e){return 2*e+1}},{key:"getRight",value:function(e){return 2*e+2}},{key:"getParent",value:function(e){return 0===e?null:Math.floor((e-1)/2)}},{key:"isEmpty",value:function(){return 0>=this.list.length}},{key:"top",value:function(){return this.isEmpty()?void 0:this.list[0]}},{key:"delMin",value:function(){var e=this.top(),t=this.list.pop();return this.list.length>0&&(this.list[0]=t,this.moveDown(0)),e}},{key:"insert",value:function(e){return null!==e&&(this.list.push(e),this.moveUp(this.list.length-1),!0)}},{key:"moveUp",value:function(e){for(var t=this.getParent(e);e&&e>0&&this.compareFn(this.list[t],this.list[e])>0;){var n=this.list[t];this.list[t]=this.list[e],this.list[e]=n,t=this.getParent(e=t)}}},{key:"moveDown",value:function(e){var t=e,n=this.getLeft(e),r=this.getRight(e),i=this.list.length;if(null!==n&&i>n&&this.compareFn(this.list[t],this.list[n])>0?t=n:null!==r&&i>r&&this.compareFn(this.list[t],this.list[r])>0&&(t=r),e!==t){var o=[this.list[t],this.list[e]];this.list[e]=o[0],this.list[t]=o[1],this.moveDown(t)}}}]),e}(),w=function(e,t){var n=[],r=e.nodes,i=e.edges;if(0===r.length)return n;var o=r[0],a=new Set;a.add(o);var u=new x((function(e,n){return t?e.weight-n.weight:0}));for(h(o.id,i).forEach((function(e){u.insert(e)}));!u.isEmpty();){var s=u.delMin(),f=s.source,l=s.target;a.has(f)&&a.has(l)||(n.push(s),a.has(f)||(a.add(f),h(f,i).forEach((function(e){u.insert(e)}))),a.has(l)||(a.add(l),h(l,i).forEach((function(e){u.insert(e)}))))}return n},I=function(e,t){var n=[],r=e.nodes;if(0===r.length)return n;var i=e.edges.map((function(e){return e}));t&&i.sort((function(e,t){return e.weight-t.weight}));for(var o=new E(r.map((function(e){return e.id})));i.length>0;){var a=i.shift(),u=a.source,s=a.target;o.connected(u,s)||(n.push(a),o.union(u,s))}return n};e.adjacentMatrix=t,e.breadthFirstSearch=function(e,t,n){var r=function(){var e,t=arguments.length>0&&void 0!==arguments[0]?arguments[0]:{},n=t,r=function(){},i=(e={},function(t){var n=t.next;return!e[n]&&(e[n]=!0,!0)});return n.allowTraversal=t.allowTraversal||i,n.enter=t.enter||r,n.leave=t.leave||r,n}(n),i=new l,o=e.edges;i.enqueue(t);for(var a="",u=function(){var e=i.dequeue();r.enter({current:e,previous:a}),c(e,o,"target").forEach((function(t){r.allowTraversal({previous:a,current:e,next:t})&&i.enqueue(t)})),r.leave({current:e,previous:a}),a=e};!i.isEmpty();)u()},e.connectedComponent=function(e,t){return t?function(e){var t,n=e.nodes,r=e.edges,i=[],o={},u={},s={},f=[],l=0,h=function e(t){u[t.id]=l,s[t.id]=l,l+=1,i.push(t),o[t.id]=!0;for(var a=c(t.id,r,"target").filter((function(e){return n.map((function(e){return e.id})).indexOf(e)>-1})),h=function(r){var i=a[r];if(u[i]||0===u[i])o[i]&&(s[t.id]=Math.min(s[t.id],u[i]));else{var f=n.filter((function(e){return e.id===i}));f.length>0&&e(f[0]),s[t.id]=Math.min(s[t.id],s[i])}},d=0;a.length>d;d++)h(d);if(s[t.id]===u[t.id]){for(var v=[];i.length>0;){var g=i.pop();if(o[g.id]=!1,v.push(g),g===t)break}v.length>0&&f.push(v)}},d=a(n);try{for(d.s();!(t=d.n()).done;){var v=t.value;u[v.id]||0===u[v.id]||h(v)}}catch(e){d.e(e)}finally{d.f()}return f}(e):function(e){for(var t=e.nodes,n=e.edges,r=[],i={},o=[],a=function e(r){o.push(r),i[r.id]=!0;for(var a=c(r.id,n),u=function(n){var r=a[n];if(!i[r]){var o=t.filter((function(e){return e.id===r}));o.length>0&&e(o[0])}},s=0;a.length>s;++s)u(s)},u=0;t.length>u;u++){var s=t[u];if(!i[s.id]){a(s);for(var f=[];o.length>0;)f.push(o.pop());r.push(f)}}return r}(e)},e.depthFirstSearch=y,e.detectCycle=function(e){var t=null,n={},r={},i={},o={};e.nodes.forEach((function(e){r[e.id]=e}));for(var a={enter:function(e){var o=e.current,a=e.previous;if(i[o]){t={};for(var u=o,s=a;s!==o;)t[u]=s,u=s,s=n[s];t[u]=s}else i[o]=o,delete r[o],n[o]=a},leave:function(e){var t=e.current;o[t]=t,delete i[t]},allowTraversal:function(e){return!t&&!o[e.next]}};Object.keys(r).length;){y(e,Object.keys(r)[0],a)}return t},e.dijkstra=m,e.findAllPath=function(e,t,n,r){if(t===n)return[[t]];var i,o,a,u=e.edges,s=[t],f=(a=!0,(o=t)in(i={})?Object.defineProperty(i,o,{value:a,enumerable:!0,configurable:!0,writable:!0}):i[o]=a,i),l=[],h=[],d=r?c(t,u,"target"):c(t,u);for(l.push(d);s.length>0&&l.length>0;){var v=l[l.length-1];if(v.length){var g=v.shift();if(g&&(s.push(g),f[g]=!0,d=r?c(g,u,"target"):c(g,u),l.push(d.filter((function(e){return!f[e]})))),s[s.length-1]===n){var p=s.map((function(e){return e}));h.push(p);var y=s.pop();f[y]=!1,l.pop()}}else{var m=s.pop();f[m]=!1,l.pop()}}return h},e.findShortestPath=function(e,t,n,r,i){var o=m(e,t,r,i);return{length:o.length[n],path:o.path[n]}},e.floydWarshall=function(e,n){for(var r=t(e,n),i=[],o=r.length,a=0;o>a;a+=1){i[a]=[];for(var u=0;o>u;u+=1)i[a][u]=a===u?0:0!==r[a][u]&&r[a][u]?r[a][u]:1/0}for(var s=0;o>s;s+=1)for(var f=0;o>f;f+=1)for(var l=0;o>l;l+=1)i[f][l]>i[f][s]+i[s][l]&&(i[f][l]=i[f][s]+i[s][l]);return i},e.getDegree=g,e.getInDegree=function(e,t){return g(e)[t]?g(e)[t].inDegree:0},e.getNeighbors=c,e.getOutDegree=function(e,t){return g(e)[t]?g(e)[t].outDegree:0},e.labelPropagation=function(e){var t=arguments.length>1&&void 0!==arguments[1]&&arguments[1],n=arguments.length>2&&void 0!==arguments[2]?arguments[2]:"weight",r=arguments.length>3&&void 0!==arguments[3]?arguments[3]:1e3,i=e.nodes,o=e.edges,a={},u={};i.forEach((function(e,t){var n=d();e.clusterId=n,a[n]={id:n,nodes:[e]},u[e.id]={node:e,idx:t}}));var s=v(e,t),f={};s.forEach((function(e,t){var n=i[t].id;f[n]={},e.forEach((function(e,t){e&&(f[n][i[t].id]=e)}))}));for(var l=0;r>l;){var c=!1;if(i.forEach((function(e){var t={};Object.keys(f[e.id]).forEach((function(n){var r=f[e.id][n],i=u[n].node.clusterId;t[i]||(t[i]=0),t[i]+=r}));var n=-1/0,r=[];if(Object.keys(t).forEach((function(e){t[e]>n?(n=t[e],r=[e]):n===t[e]&&r.push(e)})),1!==r.length||r[0]!==e.clusterId){var i=r.indexOf(e.clusterId);if(0>i||r.splice(i,1),r&&r.length){c=!0;var o=a[e.clusterId],s=o.nodes.indexOf(e);o.nodes.splice(s,1);var l=Math.floor(Math.random()*r.length),h=a[r[l]];h.nodes.push(e),e.clusterId=h.id}}})),!c)break;l++}Object.keys(a).forEach((function(e){var t=a[e];t.nodes&&t.nodes.length||delete a[e]}));var h=[],g={};o.forEach((function(e){var t=e[n]||1,r=u[e.source].node.clusterId,i=u[e.target].node.clusterId,o="".concat(r,"---").concat(i);if(g[o])g[o].weight+=t,g[o].count++;else{var a={source:r,target:i,weight:t,count:1};g[o]=a,h.push(a)}}));var p=[];return Object.keys(a).forEach((function(e){p.push(a[e])})),{clusters:p,clusterEdges:h}},e.louvain=function(e){var t=arguments.length>1&&void 0!==arguments[1]&&arguments[1],n=arguments.length>2&&void 0!==arguments[2]?arguments[2]:"weight",r=arguments.length>3&&void 0!==arguments[3]?arguments[3]:1e-4,i=e.nodes,o=e.edges,a={},u={};i.forEach((function(e,t){var n=d();e.clusterId=n,a[n]={id:n,nodes:[e]},u[e.id]={node:e,idx:t}}));var s=v(e,t),f=[],l={},c=0;s.forEach((function(e,t){var n=0,r=i[t].id;l[r]={},e.forEach((function(e,t){e&&(n+=e,l[r][i[t].id]=e,c+=e)})),f.push(n)})),c/=2;for(var h=1/0,g=1/0,p=0;h=k(i,s,f,c),Math.abs(h-g)>=r&&100>=p;)g=h,p++,Object.keys(a).forEach((function(e){var t=0;o.forEach((function(r){var i=u[r.source].node.clusterId,o=u[r.target].node.clusterId;(i===e&&o!==e||o===e&&i!==e)&&(t+=r[n]||1)})),a[e].sumTot=t})),i.forEach((function(e,t){var r,i=a[e.clusterId],h=0,d=f[t]/(2*c),v=0;i.nodes.forEach((function(e){v+=s[t][u[e.id].idx]||0}));var g=v-i.sumTot*d;if(Object.keys(l[e.id]).forEach((function(n){var i=u[n].node.clusterId;if(i!==e.clusterId){var o=a[i],f=o.nodes;if(f&&f.length){var l=0;f.forEach((function(e){l+=s[t][u[e.id].idx]||0}));var c=l-o.sumTot*d-g;c>h&&(h=c,r=o)}}})),h>0){r.nodes.push(e);var p=e.clusterId;e.clusterId=r.id;var y=i.nodes.indexOf(e);i.nodes.splice(y,1);var m=0,k=0;o.forEach((function(e){var t=u[e.source].node.clusterId,i=u[e.target].node.clusterId;(t===r.id&&i!==r.id||i===r.id&&t!==r.id)&&(m+=e[n]||1),(t===p&&i!==p||i===p&&t!==p)&&(k+=e[n]||1)})),r.sumTot=m,i.sumTot=k}}));Object.keys(a).forEach((function(e){var t=a[e];t.nodes&&t.nodes.length||delete a[e]}));var y=[],m={};o.forEach((function(e){var t=e[n]||1,r=u[e.source].node.clusterId,i=u[e.target].node.clusterId,o="".concat(r,"---").concat(i);if(m[o])m[o].weight+=t,m[o].count++;else{var a={source:r,target:i,weight:t,count:1};m[o]=a,y.push(a)}}));var E=[];return Object.keys(a).forEach((function(e){E.push(a[e])})),{clusters:E,clusterEdges:y}},e.minimumSpanningTree=function(e,t,n){return n?{prim:w,kruskal:I}[n](e,t):I(e,t)},e.pageRank=function(e,t,n){"number"!=typeof t&&(t=1e-6),"number"!=typeof n&&(n=.85);for(var r,i=1,o=0,a=1e3,u=e.nodes,s=e.edges,f=u.length,l={},h={},d=0;f>d;++d){var v=u[d].id;l[v]=1/f,h[v]=1/f}for(var p=g(e);a>0&&i>t;){o=0;for(var y=0;f>y;++y){var m=u[y],k=m.id;if(r=0,0===p[m.id].inDegree)l[k]=0;else{for(var E=c(k,s,"source"),b=0;E.length>b;++b){var x=E[b],w=p[x].outDegree;w>0&&(r+=h[x]/w)}l[k]=n*r,o+=l[k]}}o=(1-o)/f,i=0;for(var I=0;f>I;++I){var O=u[I].id;i+=Math.abs((r=l[O]+o)-h[O]),h[O]=r}a-=1}return h},Object.defineProperty(e,"__esModule",{value:!0})}));
+!function(t,e){"object"==typeof exports&&"undefined"!=typeof module?e(exports):"function"==typeof define&&define.amd?define(["exports"],e):e((t="undefined"!=typeof globalThis?globalThis:t||self).algorithm={})}(this,(function(t){"use strict";var e=function(t,e){var n=t.nodes,r=t.edges,i=[],o={};if(!n)throw Error("invalid nodes data!");return n&&n.forEach((function(t,e){o[t.id]=e;i.push([])})),r&&r.forEach((function(t){var n=o[t.source],r=o[t.target];i[n][r]=1,e||(i[r][n]=1)})),i};function n(t,e){if(!(t instanceof e))throw new TypeError("Cannot call a class as a function")}function r(t,e){for(var n=0;e.length>n;n++){var r=e[n];r.enumerable=r.enumerable||!1,r.configurable=!0,"value"in r&&(r.writable=!0),Object.defineProperty(t,r.key,r)}}function i(t,e,n){return e&&r(t.prototype,e),n&&r(t,n),t}function o(t,e){(null==e||e>t.length)&&(e=t.length);for(var n=0,r=Array(e);e>n;n++)r[n]=t[n];return r}function u(t,e){var n;if("undefined"==typeof Symbol||null==t[Symbol.iterator]){if(Array.isArray(t)||(n=function(t,e){if(t){if("string"==typeof t)return o(t,e);var n=Object.prototype.toString.call(t).slice(8,-1);return"Object"===n&&t.constructor&&(n=t.constructor.name),"Map"===n||"Set"===n?Array.from(t):"Arguments"===n||/^(?:Ui|I)nt(?:8|16|32)(?:Clamped)?Array$/.test(n)?o(t,e):void 0}}(t))||e&&t&&"number"==typeof t.length){n&&(t=n);var r=0,i=function(){};return{s:i,n:function(){return t.length>r?{done:!1,value:t[r++]}:{done:!0}},e:function(t){throw t},f:i}}throw new TypeError("Invalid attempt to iterate non-iterable instance.\nIn order to be iterable, non-array objects must have a [Symbol.iterator]() method.")}var u,a=!0,s=!1;return{s:function(){n=t[Symbol.iterator]()},n:function(){var t=n.next();return a=t.done,t},e:function(t){s=!0,u=t},f:function(){try{a||null==n.return||n.return()}finally{if(s)throw u}}}}var a=function(t,e){return t===e},s=function(){function t(e){var r=arguments.length>1&&void 0!==arguments[1]?arguments[1]:null;n(this,t),this.value=e,this.next=r}return i(t,[{key:"toString",value:function(t){return t?t(this.value):"".concat(this.value)}}]),t}(),l=function(){function t(){var e=arguments.length>0&&void 0!==arguments[0]?arguments[0]:a;n(this,t),this.head=null,this.tail=null,this.compare=e}return i(t,[{key:"prepend",value:function(t){var e=new s(t,this.head);return this.head=e,this.tail||(this.tail=e),this}},{key:"append",value:function(t){var e=new s(t);return this.head?(this.tail.next=e,this.tail=e,this):(this.head=e,this.tail=e,this)}},{key:"delete",value:function(t){if(!this.head)return null;for(var e=null;this.head&&this.compare(this.head.value,t);)e=this.head,this.head=this.head.next;var n=this.head;if(null!==n)for(;n.next;)this.compare(n.next.value,t)?(e=n.next,n.next=n.next.next):n=n.next;return this.compare(this.tail.value,t)&&(this.tail=n),e}},{key:"find",value:function(t){var e=t.value,n=void 0===e?void 0:e,r=t.callback,i=void 0===r?void 0:r;if(!this.head)return null;for(var o=this.head;o;){if(i&&i(o.value))return o;if(void 0!==n&&this.compare(o.value,n))return o;o=o.next}return null}},{key:"deleteTail",value:function(){var t=this.tail;if(this.head===this.tail)return this.head=null,this.tail=null,t;for(var e=this.head;e.next;)e.next.next?e=e.next:e.next=null;return this.tail=e,t}},{key:"deleteHead",value:function(){if(!this.head)return null;var t=this.head;return this.head.next?this.head=this.head.next:(this.head=null,this.tail=null),t}},{key:"fromArray",value:function(t){var e=this;return t.forEach((function(t){return e.append(t)})),this}},{key:"toArray",value:function(){for(var t=[],e=this.head;e;)t.push(e),e=e.next;return t}},{key:"reverse",value:function(){for(var t=this.head,e=null,n=null;t;)n=t.next,t.next=e,e=t,t=n;this.tail=this.head,this.head=e}},{key:"toString",value:function(){var t=arguments.length>0&&void 0!==arguments[0]?arguments[0]:void 0;return""+this.toArray().map((function(e){return e.toString(t)}))}}]),t}(),h=function(){function t(){n(this,t),this.linkedList=new l}return i(t,[{key:"isEmpty",value:function(){return!this.linkedList.head}},{key:"peek",value:function(){return this.linkedList.head?this.linkedList.head.value:null}},{key:"enqueue",value:function(t){this.linkedList.append(t)}},{key:"dequeue",value:function(){var t=this.linkedList.deleteHead();return t?t.value:null}},{key:"toString",value:function(t){return this.linkedList.toString(t)}}]),t}(),f=function(t){var e=arguments.length>1&&void 0!==arguments[1]?arguments[1]:[],n=arguments.length>2?arguments[2]:void 0,r=e.filter((function(e){return e.source===t||e.target===t}));if("target"===n){var i=function(e){return e.source===t};return r.filter(i).map((function(t){return t.target}))}if("source"===n){var o=function(e){return e.target===t};return r.filter(o).map((function(t){return t.source}))}var u=function(e){return e.source===t?e.target:e.source};return r.map(u)},c=function(t,e){return e.filter((function(e){return e.source===t||e.target===t}))},d=function(){var t=arguments.length>0&&void 0!==arguments[0]?arguments[0]:0;return"".concat(t,"_").concat((new Date).getTime())};var v=function(t){var e={},n=t.nodes,r=t.edges,i=void 0===r?[]:r;return(void 0===n?[]:n).forEach((function(t){e[t.id]={degree:0,inDegree:0,outDegree:0}})),i.forEach((function(t){e[t.source].degree++,e[t.source].outDegree++,e[t.target].degree++,e[t.target].inDegree++})),e};function g(t,e,n,r){r.enter({current:e,previous:n});var i=t.edges;f(e,void 0===i?[]:i,"target").forEach((function(i){r.allowTraversal({previous:n,current:e,next:i})&&g(t,i,e,r)})),r.leave({current:e,previous:n})}function p(t,e,n){g(t,e,"",function(){var t,e=arguments.length>0&&void 0!==arguments[0]?arguments[0]:{},n=e,r=function(){},i=(t={},function(e){var n=e.next;return!t[n]&&(t[n]=!0,!0)});return n.allowTraversal=e.allowTraversal||i,n.enter=e.enter||r,n.leave=e.leave||r,n}(n))}var y=function(t,e,n,r){var i=t.nodes,o=void 0===i?[]:i,u=t.edges,a=void 0===u?[]:u,s={},l={},h={};o.forEach((function(t,n){var r=t.id;l[r]=1/0,r===e&&(l[r]=0)}));for(var f=o.length,d=function(t){var e=function(t,e,n){for(var r,i=1/0,o=0;e.length>o;o++){var u=e[o].id;n[u]||t[u]>i||(i=t[u],r=e[o])}return r}(l,o,s),i=e.id;if(s[i]=!0,l[i]===1/0)return"continue";(n?function(t,e){return e.filter((function(e){return e.source===t}))}(i,a):c(i,a)).forEach((function(t){var n=t.target,o=n===i?t.source:n,u=r&&t[r]?t[r]:1;l[o]>l[e.id]+u&&(l[o]=l[e.id]+u,h[o]=e.id)}))},v=0;f>v;v++)d();var g={};for(var p in l){g[p]=[p];for(var y=h[p];void 0!==y;)g[p].unshift(y),y=h[y]}return{length:l,path:g}},k=function(t,e,n,r){for(var i=e.length,o=2*r,u=0,a=0;i>a;a++)for(var s=t[a].clusterId,l=0;i>l;l++){if(s===t[l].clusterId)u+=(e[a][l]||0)-(n[a]||0)*(n[l]||0)/o}return u*=1/o},m=function(){function t(e){n(this,t),this.count=e.length,this.parent={};var r,i=u(e);try{for(i.s();!(r=i.n()).done;){var o=r.value;this.parent[o]=o}}catch(t){i.e(t)}finally{i.f()}}return i(t,[{key:"find",value:function(t){for(;this.parent[t]!==t;)t=this.parent[t];return t}},{key:"union",value:function(t,e){var n=this.find(t),r=this.find(e);n!==r&&(r>n?(this.parent[e]!==e&&this.union(this.parent[e],t),this.parent[e]=this.parent[t]):(this.parent[t]!==t&&this.union(this.parent[t],e),this.parent[t]=this.parent[e]))}},{key:"connected",value:function(t,e){return this.find(t)===this.find(e)}}]),t}(),E=function(t,e){return t-e},b=function(){function t(){var e=arguments.length>0&&void 0!==arguments[0]?arguments[0]:E;n(this,t),this.compareFn=e,this.list=[]}return i(t,[{key:"getLeft",value:function(t){return 2*t+1}},{key:"getRight",value:function(t){return 2*t+2}},{key:"getParent",value:function(t){return 0===t?null:Math.floor((t-1)/2)}},{key:"isEmpty",value:function(){return 0>=this.list.length}},{key:"top",value:function(){return this.isEmpty()?void 0:this.list[0]}},{key:"delMin",value:function(){var t=this.top(),e=this.list.pop();return this.list.length>0&&(this.list[0]=e,this.moveDown(0)),t}},{key:"insert",value:function(t){return null!==t&&(this.list.push(t),this.moveUp(this.list.length-1),!0)}},{key:"moveUp",value:function(t){for(var e=this.getParent(t);t&&t>0&&this.compareFn(this.list[e],this.list[t])>0;){var n=this.list[e];this.list[e]=this.list[t],this.list[t]=n,e=this.getParent(t=e)}}},{key:"moveDown",value:function(t){var e=t,n=this.getLeft(t),r=this.getRight(t),i=this.list.length;if(null!==n&&i>n&&this.compareFn(this.list[e],this.list[n])>0?e=n:null!==r&&i>r&&this.compareFn(this.list[e],this.list[r])>0&&(e=r),t!==e){var o=[this.list[e],this.list[t]];this.list[t]=o[0],this.list[e]=o[1],this.moveDown(e)}}}]),t}(),x=function(t,e){var n=[],r=t.nodes,i=void 0===r?[]:r,o=t.edges,u=void 0===o?[]:o;if(0===i.length)return n;var a=i[0],s=new Set;s.add(a);var l=new b((function(t,n){return e?t.weight-n.weight:0}));for(c(a.id,u).forEach((function(t){l.insert(t)}));!l.isEmpty();){var h=l.delMin(),f=h.source,d=h.target;s.has(f)&&s.has(d)||(n.push(h),s.has(f)||(s.add(f),c(f,u).forEach((function(t){l.insert(t)}))),s.has(d)||(s.add(d),c(d,u).forEach((function(t){l.insert(t)}))))}return n},w=function(t,e){var n=[],r=t.nodes,i=void 0===r?[]:r,o=t.edges;if(0===i.length)return n;var u=(void 0===o?[]:o).map((function(t){return t}));e&&u.sort((function(t,e){return t.weight-e.weight}));for(var a=new m(i.map((function(t){return t.id})));u.length>0;){var s=u.shift(),l=s.source,h=s.target;a.connected(l,h)||(n.push(s),a.union(l,h))}return n};t.Stack=function(){function t(){var e=arguments.length>0&&void 0!==arguments[0]?arguments[0]:10;n(this,t),this.linkedList=new l,this.maxStep=e}return i(t,[{key:"isEmpty",value:function(){return!this.linkedList.head}},{key:"isMaxStack",value:function(){return this.toArray().length>=this.maxStep}},{key:"peek",value:function(){return this.isEmpty()?null:this.linkedList.head.value}},{key:"push",value:function(t){this.linkedList.prepend(t),this.length>this.maxStep&&this.linkedList.deleteTail()}},{key:"pop",value:function(){var t=this.linkedList.deleteHead();return t?t.value:null}},{key:"toArray",value:function(){return this.linkedList.toArray().map((function(t){return t.value}))}},{key:"clear",value:function(){for(;!this.isEmpty();)this.pop()}},{key:"length",get:function(){return this.linkedList.toArray().length}}]),t}(),t.breadthFirstSearch=function(t,e,n){var r=function(){var t,e=arguments.length>0&&void 0!==arguments[0]?arguments[0]:{},n=e,r=function(){},i=(t={},function(e){var n=e.next;return!t[n]&&(t[n]=!0,!0)});return n.allowTraversal=e.allowTraversal||i,n.enter=e.enter||r,n.leave=e.leave||r,n}(n),i=new h,o=t.edges,u=void 0===o?[]:o;i.enqueue(e);for(var a="",s=function(){var t=i.dequeue();r.enter({current:t,previous:a}),f(t,u,"target").forEach((function(e){r.allowTraversal({previous:a,current:t,next:e})&&i.enqueue(e)})),r.leave({current:t,previous:a}),a=t};!i.isEmpty();)s()},t.connectedComponent=function(t,e){return e?function(t){var e,n=t.nodes,r=void 0===n?[]:n,i=t.edges,o=void 0===i?[]:i,a=[],s={},l={},h={},c=[],d=0,v=function t(e){l[e.id]=d,h[e.id]=d,d+=1,a.push(e),s[e.id]=!0;for(var n=f(e.id,o,"target").filter((function(t){return r.map((function(t){return t.id})).indexOf(t)>-1})),i=function(i){var o=n[i];if(l[o]||0===l[o])s[o]&&(h[e.id]=Math.min(h[e.id],l[o]));else{var u=r.filter((function(t){return t.id===o}));u.length>0&&t(u[0]),h[e.id]=Math.min(h[e.id],h[o])}},u=0;n.length>u;u++)i(u);if(h[e.id]===l[e.id]){for(var v=[];a.length>0;){var g=a.pop();if(s[g.id]=!1,v.push(g),g===e)break}v.length>0&&c.push(v)}},g=u(r);try{for(g.s();!(e=g.n()).done;){var p=e.value;l[p.id]||0===l[p.id]||v(p)}}catch(t){g.e(t)}finally{g.f()}return c}(t):function(t){for(var e=t.nodes,n=void 0===e?[]:e,r=t.edges,i=void 0===r?[]:r,o=[],u={},a=[],s=function t(e){a.push(e),u[e.id]=!0;for(var r=f(e.id,i),o=function(e){var i=r[e];if(!u[i]){var o=n.filter((function(t){return t.id===i}));o.length>0&&t(o[0])}},s=0;r.length>s;++s)o(s)},l=0;n.length>l;l++){var h=n[l];if(!u[h.id]){s(h);for(var c=[];a.length>0;)c.push(a.pop());o.push(c)}}return o}(t)},t.depthFirstSearch=p,t.detectCycle=function(t){var e=null,n=t.nodes,r={},i={},o={},u={};(void 0===n?[]:n).forEach((function(t){i[t.id]=t}));for(var a={enter:function(t){var n=t.current,u=t.previous;if(o[n]){e={};for(var a=n,s=u;s!==n;)e[a]=s,a=s,s=r[s];e[a]=s}else o[n]=n,delete i[n],r[n]=u},leave:function(t){var e=t.current;u[e]=e,delete o[e]},allowTraversal:function(t){return!e&&!u[t.next]}};Object.keys(i).length;){p(t,Object.keys(i)[0],a)}return e},t.dijkstra=y,t.findAllPath=function(t,e,n,r){if(e===n)return[[e]];var i,o,u,a=t.edges,s=void 0===a?[]:a,l=[e],h=(u=!0,(o=e)in(i={})?Object.defineProperty(i,o,{value:u,enumerable:!0,configurable:!0,writable:!0}):i[o]=u,i),c=[],d=[],v=r?f(e,s,"target"):f(e,s);for(c.push(v);l.length>0&&c.length>0;){var g=c[c.length-1];if(g.length){var p=g.shift();if(p&&(l.push(p),h[p]=!0,v=r?f(p,s,"target"):f(p,s),c.push(v.filter((function(t){return!h[t]})))),l[l.length-1]===n){var y=l.map((function(t){return t}));d.push(y);var k=l.pop();h[k]=!1,c.pop()}}else{var m=l.pop();h[m]=!1,c.pop()}}return d},t.findShortestPath=function(t,e,n,r,i){var o=y(t,e,r,i);return{length:o.length[n],path:o.path[n]}},t.floydWarshall=function(t,n){for(var r=e(t,n),i=[],o=r.length,u=0;o>u;u+=1){i[u]=[];for(var a=0;o>a;a+=1)i[u][a]=u===a?0:0!==r[u][a]&&r[u][a]?r[u][a]:1/0}for(var s=0;o>s;s+=1)for(var l=0;o>l;l+=1)for(var h=0;o>h;h+=1)i[l][h]>i[l][s]+i[s][h]&&(i[l][h]=i[l][s]+i[s][h]);return i},t.getAdjMatrix=e,t.getDegree=v,t.getInDegree=function(t,e){return v(t)[e]?v(t)[e].inDegree:0},t.getNeighbors=f,t.getOutDegree=function(t,e){return v(t)[e]?v(t)[e].outDegree:0},t.labelPropagation=function(t){var n=arguments.length>1&&void 0!==arguments[1]&&arguments[1],r=arguments.length>2&&void 0!==arguments[2]?arguments[2]:"weight",i=arguments.length>3&&void 0!==arguments[3]?arguments[3]:1e3,o=t.nodes,u=void 0===o?[]:o,a=t.edges,s=void 0===a?[]:a,l={},h={};u.forEach((function(t,e){var n=d();t.clusterId=n,l[n]={id:n,nodes:[t]},h[t.id]={node:t,idx:e}}));var f=e(t,n),c={};f.forEach((function(t,e){var n=u[e].id;c[n]={},t.forEach((function(t,e){t&&(c[n][u[e].id]=t)}))}));for(var v=0;i>v;){var g=!1;if(u.forEach((function(t){var e={};Object.keys(c[t.id]).forEach((function(n){var r=c[t.id][n],i=h[n].node.clusterId;e[i]||(e[i]=0),e[i]+=r}));var n=-1/0,r=[];if(Object.keys(e).forEach((function(t){e[t]>n?(n=e[t],r=[t]):n===e[t]&&r.push(t)})),1!==r.length||r[0]!==t.clusterId){var i=r.indexOf(t.clusterId);if(0>i||r.splice(i,1),r&&r.length){g=!0;var o=l[t.clusterId],u=o.nodes.indexOf(t);o.nodes.splice(u,1);var a=Math.floor(Math.random()*r.length),s=l[r[a]];s.nodes.push(t),t.clusterId=s.id}}})),!g)break;v++}Object.keys(l).forEach((function(t){var e=l[t];e.nodes&&e.nodes.length||delete l[t]}));var p=[],y={};s.forEach((function(t){var e=t[r]||1,n=h[t.source].node.clusterId,i=h[t.target].node.clusterId,o="".concat(n,"---").concat(i);if(y[o])y[o].weight+=e,y[o].count++;else{var u={source:n,target:i,weight:e,count:1};y[o]=u,p.push(u)}}));var k=[];return Object.keys(l).forEach((function(t){k.push(l[t])})),{clusters:k,clusterEdges:p}},t.louvain=function(t){var n=arguments.length>1&&void 0!==arguments[1]&&arguments[1],r=arguments.length>2&&void 0!==arguments[2]?arguments[2]:"weight",i=arguments.length>3&&void 0!==arguments[3]?arguments[3]:1e-4,o=t.nodes,u=void 0===o?[]:o,a=t.edges,s=void 0===a?[]:a,l={},h={};u.forEach((function(t,e){var n=d();t.clusterId=n,l[n]={id:n,nodes:[t]},h[t.id]={node:t,idx:e}}));var f=e(t,n),c=[],v={},g=0;f.forEach((function(t,e){var n=0,r=u[e].id;v[r]={},t.forEach((function(t,e){t&&(n+=t,v[r][u[e].id]=t,g+=t)})),c.push(n)})),g/=2;for(var p=1/0,y=1/0,m=0;p=k(u,f,c,g),Math.abs(p-y)>=i&&100>=m;)y=p,m++,Object.keys(l).forEach((function(t){var e=0;s.forEach((function(n){var i=h[n.source].node.clusterId,o=h[n.target].node.clusterId;(i===t&&o!==t||o===t&&i!==t)&&(e+=n[r]||1)})),l[t].sumTot=e})),u.forEach((function(t,e){var n,i=l[t.clusterId],o=0,u=c[e]/(2*g),a=0;i.nodes.forEach((function(t){a+=f[e][h[t.id].idx]||0}));var d=a-i.sumTot*u;if(Object.keys(v[t.id]).forEach((function(r){var i=h[r].node.clusterId;if(i!==t.clusterId){var a=l[i],s=a.nodes;if(s&&s.length){var c=0;s.forEach((function(t){c+=f[e][h[t.id].idx]||0}));var v=c-a.sumTot*u-d;v>o&&(o=v,n=a)}}})),o>0){n.nodes.push(t);var p=t.clusterId;t.clusterId=n.id;var y=i.nodes.indexOf(t);i.nodes.splice(y,1);var k=0,m=0;s.forEach((function(t){var e=h[t.source].node.clusterId,i=h[t.target].node.clusterId;(e===n.id&&i!==n.id||i===n.id&&e!==n.id)&&(k+=t[r]||1),(e===p&&i!==p||i===p&&e!==p)&&(m+=t[r]||1)})),n.sumTot=k,i.sumTot=m}}));Object.keys(l).forEach((function(t){var e=l[t];e.nodes&&e.nodes.length||delete l[t]}));var E=[],b={};s.forEach((function(t){var e=t[r]||1,n=h[t.source].node.clusterId,i=h[t.target].node.clusterId,o="".concat(n,"---").concat(i);if(b[o])b[o].weight+=e,b[o].count++;else{var u={source:n,target:i,weight:e,count:1};b[o]=u,E.push(u)}}));var x=[];return Object.keys(l).forEach((function(t){x.push(l[t])})),{clusters:x,clusterEdges:E}},t.minimumSpanningTree=function(t,e,n){return n?{prim:x,kruskal:w}[n](t,e):w(t,e)},t.pageRank=function(t,e,n){"number"!=typeof e&&(e=1e-6),"number"!=typeof n&&(n=.85);for(var r,i=1,o=0,u=1e3,a=t.nodes,s=void 0===a?[]:a,l=t.edges,h=void 0===l?[]:l,c=s.length,d={},g={},p=0;c>p;++p){var y=s[p].id;d[y]=1/c,g[y]=1/c}for(var k=v(t);u>0&&i>e;){o=0;for(var m=0;c>m;++m){var E=s[m],b=E.id;if(r=0,0===k[E.id].inDegree)d[b]=0;else{for(var x=f(b,h,"source"),w=0;x.length>w;++w){var I=x[w],S=k[I].outDegree;S>0&&(r+=g[I]/S)}d[b]=n*r,o+=d[b]}}o=(1-o)/c,i=0;for(var O=0;c>O;++O){var T=s[O].id;i+=Math.abs((r=d[T]+o)-g[T]),g[T]=r}u-=1}return g},Object.defineProperty(t,"__esModule",{value:!0})}));

dist/src/connected-component.d.ts

@@ -6,3 +6,3 @@ import { GraphData, NodeConfig } from "./types";
  */
-export declare function detectConnectedComponents(graphData: GraphData): NodeConfig[][];
+export declare const detectConnectedComponents: (graphData: GraphData) => NodeConfig[][];
 /**
@@ -16,3 +16,3 @@ * Tarjan's Algorithm 复杂度  O(|V|+|E|)
  */
-export declare function detectStrongConnectComponents(graphData: GraphData): NodeConfig[][];
+export declare const detectStrongConnectComponents: (graphData: GraphData) => NodeConfig[][];
 export default function getConnectedComponents(graphData: GraphData, directed?: boolean): NodeConfig[][];

dist/src/index.d.ts

@@ -1,2 +0,2 @@
-export { default as adjacentMatrix } from './adjacent-matrix';
+export { default as getAdjMatrix } from './adjacent-matrix';
 export { default as breadthFirstSearch } from './bfs';
@@ -16,1 +16,2 @@ export { default as connectedComponent } from './connected-component';
 export { getNeighbors } from './util';
+export { default as Stack } from './structs/stack';

dist/src/types.d.ts

@@ -12,4 +12,4 @@ export declare type Matrix = number[];
 export interface GraphData {
-    nodes: NodeConfig[];
-    edges: EdgeConfig[];
+    nodes?: NodeConfig[];
+    edges?: EdgeConfig[];
 }
@@ -16,0 +16,0 @@ export interface Cluster {

dist/src/util.d.ts

@@ -1,2 +0,2 @@
-import { EdgeConfig, GraphData, Matrix } from './types';
+import { EdgeConfig } from './types';
 /**
@@ -8,3 +8,3 @@ * 获取指定节点的所有邻居
  */
-export declare const getNeighbors: (nodeId: string, edges: EdgeConfig[], type?: 'target' | 'source' | undefined) => string[];
+export declare const getNeighbors: (nodeId: string, edges?: EdgeConfig[], type?: 'target' | 'source' | undefined) => string[];
 /**
@@ -27,7 +27,1 @@ * 获取指定节点的出边
 export declare const uniqueId: (index?: number) => string;
-/**
- * get adjacency matrix
- * @param data graph data
- * @param directed whether it's a directed graph
- */
-export declare const getAdjMatrix: (graphData: GraphData, directed?: boolean) => Matrix[];

es/bfs.js

@@ -51,3 +51,4 @@ import Queue from './structs/queue';
   var nodeQueue = new Queue();
-  var edges = graphData.edges; // 初始化队列元素
+  var _a = graphData.edges,
+      edges = _a === void 0 ? [] : _a; // 初始化队列元素
 
@@ -54,0 +55,0 @@ nodeQueue.enqueue(startNodeId);

es/connected-component.d.ts

@@ -6,3 +6,3 @@ import { GraphData, NodeConfig } from "./types";
  */
-export declare function detectConnectedComponents(graphData: GraphData): NodeConfig[][];
+export declare const detectConnectedComponents: (graphData: GraphData) => NodeConfig[][];
 /**
@@ -16,3 +16,3 @@ * Tarjan's Algorithm 复杂度  O(|V|+|E|)
  */
-export declare function detectStrongConnectComponents(graphData: GraphData): NodeConfig[][];
+export declare const detectStrongConnectComponents: (graphData: GraphData) => NodeConfig[][];
 export default function getConnectedComponents(graphData: GraphData, directed?: boolean): NodeConfig[][];

es/connected-component.js

@@ -7,5 +7,7 @@ import { getNeighbors } from "./util";
 
-export function detectConnectedComponents(graphData) {
-  var nodes = graphData.nodes,
-      edges = graphData.edges;
+export var detectConnectedComponents = function detectConnectedComponents(graphData) {
+  var _a = graphData.nodes,
+      nodes = _a === void 0 ? [] : _a,
+      _b = graphData.edges,
+      edges = _b === void 0 ? [] : _b;
   var allComponents = [];
@@ -56,3 +58,3 @@ var visited = {};
   return allComponents;
-}
+};
 /**
@@ -67,5 +69,7 @@ * Tarjan's Algorithm 复杂度  O(|V|+|E|)
 
-export function detectStrongConnectComponents(graphData) {
-  var nodes = graphData.nodes,
-      edges = graphData.edges;
+export var detectStrongConnectComponents = function detectStrongConnectComponents(graphData) {
+  var _a = graphData.nodes,
+      nodes = _a === void 0 ? [] : _a,
+      _b = graphData.edges,
+      edges = _b === void 0 ? [] : _b;
   var nodeStack = [];
@@ -143,3 +147,3 @@ var inStack = {}; // 辅助判断是否已经在stack中，减少查找开销
   return allComponents;
-}
+};
 export default function getConnectedComponents(graphData, directed) {
@@ -146,0 +150,0 @@ if (directed) return detectStrongConnectComponents(graphData);

es/degree.js

 var degree = function degree(graphData) {
   var degrees = {};
-  var nodes = graphData.nodes,
-      edges = graphData.edges;
+  var _a = graphData.nodes,
+      nodes = _a === void 0 ? [] : _a,
+      _b = graphData.edges,
+      edges = _b === void 0 ? [] : _b;
   nodes.forEach(function (node) {
@@ -6,0 +8,0 @@ degrees[node.id] = {

es/detect-cycle.js

@@ -7,3 +7,4 @@ import dfs from './dfs';
   var cycle = null;
-  var nodes = graphData.nodes;
+  var _a = graphData.nodes,
+      nodes = _a === void 0 ? [] : _a;
   var dfsParentMap = {}; // 所有没有被访问的节点集合
@@ -268,3 +269,4 @@
 
-  var nodes = graphData.nodes; // Johnson's algorithm 要求给节点赋顺序，先按节点在数组中的顺序
+  var _a = graphData.nodes,
+      nodes = _a === void 0 ? [] : _a; // Johnson's algorithm 要求给节点赋顺序，先按节点在数组中的顺序
 
@@ -271,0 +273,0 @@ for (var i = 0; i < nodes.length; i += 1) {

es/dfs.js

@@ -44,3 +44,5 @@ import { getNeighbors } from './util';
   });
-  getNeighbors(currentNode, graphData.edges, 'target').forEach(function (nextNode) {
+  var _a = graphData.edges,
+      edges = _a === void 0 ? [] : _a;
+  getNeighbors(currentNode, edges, 'target').forEach(function (nextNode) {
     if (callbacks.allowTraversal({
@@ -47,0 +49,0 @@ previous: previousNode,

es/dijkstra.js

@@ -21,4 +21,6 @@ import { getOutEdgesNodeId, getEdgesByNodeId } from "./util";
 var dijkstra = function dijkstra(graphData, source, directed, weightPropertyName) {
-  var nodes = graphData.nodes,
-      edges = graphData.edges;
+  var _a = graphData.nodes,
+      nodes = _a === void 0 ? [] : _a,
+      _b = graphData.edges,
+      edges = _b === void 0 ? [] : _b;
   var nodeIds = [];
@@ -25,0 +27,0 @@ var marks = {};

es/find-path.js

@@ -17,3 +17,4 @@ import dijkstra from './dijkstra';
   if (start === end) return [[start]];
-  var edges = graphData.edges;
+  var _b = graphData.edges,
+      edges = _b === void 0 ? [] : _b;
   var visited = [start];
@@ -20,0 +21,0 @@ var isVisited = (_a = {}, _a[start] = true, _a);

es/floydWarshall.js

@@ -1,5 +0,5 @@
-import adjMatrix from './adjacent-matrix';
+import getAdjMatrix from './adjacent-matrix';
 
 var floydWarshall = function floydWarshall(graphData, directed) {
-  var adjacentMatrix = adjMatrix(graphData, directed);
+  var adjacentMatrix = getAdjMatrix(graphData, directed);
   ;
@@ -6,0 +6,0 @@ var dist = [];

es/index.d.ts

@@ -1,2 +0,2 @@
-export { default as adjacentMatrix } from './adjacent-matrix';
+export { default as getAdjMatrix } from './adjacent-matrix';
 export { default as breadthFirstSearch } from './bfs';
@@ -16,1 +16,2 @@ export { default as connectedComponent } from './connected-component';
 export { getNeighbors } from './util';
+export { default as Stack } from './structs/stack';

es/index.js

@@ -1,2 +0,2 @@
-export { default as adjacentMatrix } from './adjacent-matrix';
+export { default as getAdjMatrix } from './adjacent-matrix';
 export { default as breadthFirstSearch } from './bfs';
@@ -15,2 +15,3 @@ export { default as connectedComponent } from './connected-component';
 export { default as pageRank } from './pageRank';
-export { getNeighbors } from './util';
+export { getNeighbors } from './util';
+export { default as Stack } from './structs/stack';

es/label-propagation.js

@@ -1,2 +0,3 @@
-import { getAdjMatrix, uniqueId } from './util';
+import getAdjMatrix from './adjacent-matrix';
+import { uniqueId } from './util';
 /**
@@ -24,4 +25,6 @@ * 标签传播算法
 
-  var nodes = graphData.nodes,
-      edges = graphData.edges;
+  var _a = graphData.nodes,
+      nodes = _a === void 0 ? [] : _a,
+      _b = graphData.edges,
+      edges = _b === void 0 ? [] : _b;
   var clusters = {};
@@ -28,0 +31,0 @@ var nodeMap = {}; // init the clusters and nodeMap

es/louvain.js

@@ -1,2 +0,3 @@
-import { getAdjMatrix, uniqueId } from './util';
+import getAdjMatrix from './adjacent-matrix';
+import { uniqueId } from './util';
 
@@ -47,4 +48,6 @@ var getModularity = function getModularity(nodes, adjMatrix, ks, m) {
 
-  var nodes = graphData.nodes,
-      edges = graphData.edges;
+  var _a = graphData.nodes,
+      nodes = _a === void 0 ? [] : _a,
+      _b = graphData.edges,
+      edges = _b === void 0 ? [] : _b;
   var clusters = {};
@@ -51,0 +54,0 @@ var nodeMap = {}; // init the clusters and nodeMap

es/mts.js

@@ -13,4 +13,6 @@ import UnionFind from './structs/union-find';
   var selectedEdges = [];
-  var nodes = graphData.nodes,
-      edges = graphData.edges;
+  var _a = graphData.nodes,
+      nodes = _a === void 0 ? [] : _a,
+      _b = graphData.edges,
+      edges = _b === void 0 ? [] : _b;
 
@@ -75,3 +77,6 @@ if (nodes.length === 0) {
   var selectedEdges = [];
-  var nodes = graphData.nodes;
+  var _a = graphData.nodes,
+      nodes = _a === void 0 ? [] : _a,
+      _b = graphData.edges,
+      edges = _b === void 0 ? [] : _b;
 
@@ -83,3 +88,3 @@ if (nodes.length === 0) {
 
-  var edges = graphData.edges.map(function (edge) {
+  var weightEdges = edges.map(function (edge) {
     return edge;
@@ -89,3 +94,3 @@ });
   if (weight) {
-    edges.sort(function (a, b) {
+    weightEdges.sort(function (a, b) {
       return a.weight - b.weight;
@@ -100,4 +105,4 @@ });
 
-  while (edges.length > 0) {
-    var curEdge = edges.shift();
+  while (weightEdges.length > 0) {
+    var curEdge = weightEdges.shift();
     var source = curEdge.source;
@@ -104,0 +109,0 @@ var target = curEdge.target;

es/pageRank.js

@@ -17,4 +17,6 @@ import degree from './degree';
   var maxIterations = 1000;
-  var nodes = graphData.nodes,
-      edges = graphData.edges;
+  var _a = graphData.nodes,
+      nodes = _a === void 0 ? [] : _a,
+      _b = graphData.edges,
+      edges = _b === void 0 ? [] : _b;
   var nodesCount = nodes.length;
@@ -21,0 +23,0 @@ var currentRank;

es/types.d.ts

@@ -12,4 +12,4 @@ export declare type Matrix = number[];
 export interface GraphData {
-    nodes: NodeConfig[];
-    edges: EdgeConfig[];
+    nodes?: NodeConfig[];
+    edges?: EdgeConfig[];
 }
@@ -16,0 +16,0 @@ export interface Cluster {

es/util.d.ts

@@ -1,2 +0,2 @@
-import { EdgeConfig, GraphData, Matrix } from './types';
+import { EdgeConfig } from './types';
 /**
@@ -8,3 +8,3 @@ * 获取指定节点的所有邻居
  */
-export declare const getNeighbors: (nodeId: string, edges: EdgeConfig[], type?: 'target' | 'source' | undefined) => string[];
+export declare const getNeighbors: (nodeId: string, edges?: EdgeConfig[], type?: 'target' | 'source' | undefined) => string[];
 /**
@@ -27,7 +27,1 @@ * 获取指定节点的出边
 export declare const uniqueId: (index?: number) => string;
-/**
- * get adjacency matrix
- * @param data graph data
- * @param directed whether it's a directed graph
- */
-export declare const getAdjMatrix: (graphData: GraphData, directed?: boolean) => Matrix[];

es/util.js

@@ -8,2 +8,6 @@ /**
 export var getNeighbors = function getNeighbors(nodeId, edges, type) {
+  if (edges === void 0) {
+    edges = [];
+  }
+
   var currentEdges = edges.filter(function (edge) {
@@ -75,43 +79,2 @@ return edge.source === nodeId || edge.target === nodeId;
   return index + "_" + new Date().getTime();
-};
-/**
- * get adjacency matrix
- * @param data graph data
- * @param directed whether it's a directed graph
- */
-
-export var getAdjMatrix = function getAdjMatrix(graphData, directed) {
-  var nodes = graphData.nodes,
-      edges = graphData.edges;
-  var matrix = []; // map node with index in data.nodes
-
-  var nodeMap = {};
-
-  if (!nodes) {
-    throw new Error('invalid nodes data!');
-  }
-
-  if (nodes) {
-    nodes.forEach(function (node, i) {
-      nodeMap[node.id] = i;
-      var row = [];
-      matrix.push(row);
-    });
-  }
-
-  if (edges) {
-    edges.forEach(function (e) {
-      var source = e.source,
-          target = e.target;
-      var sIndex = nodeMap[source];
-      var tIndex = nodeMap[target];
-      matrix[sIndex][tIndex] = 1;
-
-      if (!directed) {
-        matrix[tIndex][sIndex] = 1;
-      }
-    });
-  }
-
-  return matrix;
 };

lib/bfs.js

@@ -61,3 +61,4 @@ "use strict";
   var nodeQueue = new _queue["default"]();
-  var edges = graphData.edges; // 初始化队列元素
+  var _a = graphData.edges,
+      edges = _a === void 0 ? [] : _a; // 初始化队列元素
 
@@ -64,0 +65,0 @@ nodeQueue.enqueue(startNodeId);

lib/connected-component.d.ts

@@ -6,3 +6,3 @@ import { GraphData, NodeConfig } from "./types";
  */
-export declare function detectConnectedComponents(graphData: GraphData): NodeConfig[][];
+export declare const detectConnectedComponents: (graphData: GraphData) => NodeConfig[][];
 /**
@@ -16,3 +16,3 @@ * Tarjan's Algorithm 复杂度  O(|V|+|E|)
  */
-export declare function detectStrongConnectComponents(graphData: GraphData): NodeConfig[][];
+export declare const detectStrongConnectComponents: (graphData: GraphData) => NodeConfig[][];
 export default function getConnectedComponents(graphData: GraphData, directed?: boolean): NodeConfig[][];

lib/connected-component.js

@@ -6,5 +6,4 @@ "use strict";
 });
-exports.detectConnectedComponents = detectConnectedComponents;
-exports.detectStrongConnectComponents = detectStrongConnectComponents;
 exports["default"] = getConnectedComponents;
+exports.detectStrongConnectComponents = exports.detectConnectedComponents = void 0;
 
@@ -17,5 +16,7 @@ var _util = require("./util");
  */
-function detectConnectedComponents(graphData) {
-  var nodes = graphData.nodes,
-      edges = graphData.edges;
+var detectConnectedComponents = function detectConnectedComponents(graphData) {
+  var _a = graphData.nodes,
+      nodes = _a === void 0 ? [] : _a,
+      _b = graphData.edges,
+      edges = _b === void 0 ? [] : _b;
   var allComponents = [];
@@ -66,3 +67,3 @@ var visited = {};
   return allComponents;
-}
+};
 /**
@@ -78,5 +79,9 @@ * Tarjan's Algorithm 复杂度  O(|V|+|E|)
 
-function detectStrongConnectComponents(graphData) {
-  var nodes = graphData.nodes,
-      edges = graphData.edges;
+exports.detectConnectedComponents = detectConnectedComponents;
+
+var detectStrongConnectComponents = function detectStrongConnectComponents(graphData) {
+  var _a = graphData.nodes,
+      nodes = _a === void 0 ? [] : _a,
+      _b = graphData.edges,
+      edges = _b === void 0 ? [] : _b;
   var nodeStack = [];
@@ -154,4 +159,6 @@ var inStack = {}; // 辅助判断是否已经在stack中，减少查找开销
   return allComponents;
-}
+};
 
+exports.detectStrongConnectComponents = detectStrongConnectComponents;
+
 function getConnectedComponents(graphData, directed) {
@@ -158,0 +165,0 @@ if (directed) return detectStrongConnectComponents(graphData);

lib/degree.js

@@ -10,4 +10,6 @@ "use strict";
   var degrees = {};
-  var nodes = graphData.nodes,
-      edges = graphData.edges;
+  var _a = graphData.nodes,
+      nodes = _a === void 0 ? [] : _a,
+      _b = graphData.edges,
+      edges = _b === void 0 ? [] : _b;
   nodes.forEach(function (node) {
@@ -14,0 +16,0 @@ degrees[node.id] = {

lib/detect-cycle.js

@@ -24,3 +24,4 @@ "use strict";
   var cycle = null;
-  var nodes = graphData.nodes;
+  var _a = graphData.nodes,
+      nodes = _a === void 0 ? [] : _a;
   var dfsParentMap = {}; // 所有没有被访问的节点集合
@@ -288,3 +289,4 @@
 
-  var nodes = graphData.nodes; // Johnson's algorithm 要求给节点赋顺序，先按节点在数组中的顺序
+  var _a = graphData.nodes,
+      nodes = _a === void 0 ? [] : _a; // Johnson's algorithm 要求给节点赋顺序，先按节点在数组中的顺序
 
@@ -291,0 +293,0 @@ for (var i = 0; i < nodes.length; i += 1) {

lib/dfs.js

@@ -51,3 +51,5 @@ "use strict";
   });
-  (0, _util.getNeighbors)(currentNode, graphData.edges, 'target').forEach(function (nextNode) {
+  var _a = graphData.edges,
+      edges = _a === void 0 ? [] : _a;
+  (0, _util.getNeighbors)(currentNode, edges, 'target').forEach(function (nextNode) {
     if (callbacks.allowTraversal({
@@ -54,0 +56,0 @@ previous: previousNode,

lib/dijkstra.js

@@ -28,4 +28,6 @@ "use strict";
 var dijkstra = function dijkstra(graphData, source, directed, weightPropertyName) {
-  var nodes = graphData.nodes,
-      edges = graphData.edges;
+  var _a = graphData.nodes,
+      nodes = _a === void 0 ? [] : _a,
+      _b = graphData.edges,
+      edges = _b === void 0 ? [] : _b;
   var nodeIds = [];
@@ -32,0 +34,0 @@ var marks = {};

lib/find-path.js

@@ -31,3 +31,4 @@ "use strict";
   if (start === end) return [[start]];
-  var edges = graphData.edges;
+  var _b = graphData.edges,
+      edges = _b === void 0 ? [] : _b;
   var visited = [start];
@@ -34,0 +35,0 @@ var isVisited = (_a = {}, _a[start] = true, _a);

lib/index.d.ts

@@ -1,2 +0,2 @@
-export { default as adjacentMatrix } from './adjacent-matrix';
+export { default as getAdjMatrix } from './adjacent-matrix';
 export { default as breadthFirstSearch } from './bfs';
@@ -16,1 +16,2 @@ export { default as connectedComponent } from './connected-component';
 export { getNeighbors } from './util';
+export { default as Stack } from './structs/stack';

lib/index.js

@@ -8,3 +8,3 @@ "use strict";
 });
-Object.defineProperty(exports, "adjacentMatrix", {
+Object.defineProperty(exports, "getAdjMatrix", {
   enumerable: true,
@@ -111,2 +111,8 @@ get: function get() {
 });
+Object.defineProperty(exports, "Stack", {
+  enumerable: true,
+  get: function get() {
+    return _stack["default"];
+  }
+});
 
@@ -141,2 +147,4 @@ var _adjacentMatrix = _interopRequireDefault(require("./adjacent-matrix"));
 
+var _stack = _interopRequireDefault(require("./structs/stack"));
+
 function _getRequireWildcardCache() { if (typeof WeakMap !== "function") return null; var cache = new WeakMap(); _getRequireWildcardCache = function _getRequireWildcardCache() { return cache; }; return cache; }
@@ -143,0 +151,0 @@

lib/label-propagation.js

@@ -8,4 +8,8 @@ "use strict";
 
+var _adjacentMatrix = _interopRequireDefault(require("./adjacent-matrix"));
+
 var _util = require("./util");
 
+function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { "default": obj }; }
+
 /**
@@ -32,4 +36,6 @@ * 标签传播算法
 
-  var nodes = graphData.nodes,
-      edges = graphData.edges;
+  var _a = graphData.nodes,
+      nodes = _a === void 0 ? [] : _a,
+      _b = graphData.edges,
+      edges = _b === void 0 ? [] : _b;
   var clusters = {};
@@ -51,3 +57,3 @@ var nodeMap = {}; // init the clusters and nodeMap
 
-  var adjMatrix = (0, _util.getAdjMatrix)(graphData, directed); // the sum of each row in adjacent matrix
+  var adjMatrix = (0, _adjacentMatrix["default"])(graphData, directed); // the sum of each row in adjacent matrix
 
@@ -54,0 +60,0 @@ var ks = [];

lib/louvain.js

@@ -8,4 +8,8 @@ "use strict";
 
+var _adjacentMatrix = _interopRequireDefault(require("./adjacent-matrix"));
+
 var _util = require("./util");
 
+function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { "default": obj }; }
+
 var getModularity = function getModularity(nodes, adjMatrix, ks, m) {
@@ -55,4 +59,6 @@ var length = adjMatrix.length;
 
-  var nodes = graphData.nodes,
-      edges = graphData.edges;
+  var _a = graphData.nodes,
+      nodes = _a === void 0 ? [] : _a,
+      _b = graphData.edges,
+      edges = _b === void 0 ? [] : _b;
   var clusters = {};
@@ -74,3 +80,3 @@ var nodeMap = {}; // init the clusters and nodeMap
 
-  var adjMatrix = (0, _util.getAdjMatrix)(graphData, directed); // the sum of each row in adjacent matrix
+  var adjMatrix = (0, _adjacentMatrix["default"])(graphData, directed); // the sum of each row in adjacent matrix
 
@@ -77,0 +83,0 @@ var ks = [];

lib/mts.js

@@ -24,4 +24,6 @@ "use strict";
   var selectedEdges = [];
-  var nodes = graphData.nodes,
-      edges = graphData.edges;
+  var _a = graphData.nodes,
+      nodes = _a === void 0 ? [] : _a,
+      _b = graphData.edges,
+      edges = _b === void 0 ? [] : _b;
 
@@ -86,3 +88,6 @@ if (nodes.length === 0) {
   var selectedEdges = [];
-  var nodes = graphData.nodes;
+  var _a = graphData.nodes,
+      nodes = _a === void 0 ? [] : _a,
+      _b = graphData.edges,
+      edges = _b === void 0 ? [] : _b;
 
@@ -94,3 +99,3 @@ if (nodes.length === 0) {
 
-  var edges = graphData.edges.map(function (edge) {
+  var weightEdges = edges.map(function (edge) {
     return edge;
@@ -100,3 +105,3 @@ });
   if (weight) {
-    edges.sort(function (a, b) {
+    weightEdges.sort(function (a, b) {
       return a.weight - b.weight;
@@ -111,4 +116,4 @@ });
 
-  while (edges.length > 0) {
-    var curEdge = edges.shift();
+  while (weightEdges.length > 0) {
+    var curEdge = weightEdges.shift();
     var source = curEdge.source;
@@ -115,0 +120,0 @@ var target = curEdge.target;

lib/pageRank.js

@@ -27,4 +27,6 @@ "use strict";
   var maxIterations = 1000;
-  var nodes = graphData.nodes,
-      edges = graphData.edges;
+  var _a = graphData.nodes,
+      nodes = _a === void 0 ? [] : _a,
+      _b = graphData.edges,
+      edges = _b === void 0 ? [] : _b;
   var nodesCount = nodes.length;
@@ -31,0 +33,0 @@ var currentRank;

lib/types.d.ts

@@ -12,4 +12,4 @@ export declare type Matrix = number[];
 export interface GraphData {
-    nodes: NodeConfig[];
-    edges: EdgeConfig[];
+    nodes?: NodeConfig[];
+    edges?: EdgeConfig[];
 }
@@ -16,0 +16,0 @@ export interface Cluster {

lib/util.d.ts

@@ -1,2 +0,2 @@
-import { EdgeConfig, GraphData, Matrix } from './types';
+import { EdgeConfig } from './types';
 /**
@@ -8,3 +8,3 @@ * 获取指定节点的所有邻居
  */
-export declare const getNeighbors: (nodeId: string, edges: EdgeConfig[], type?: 'target' | 'source' | undefined) => string[];
+export declare const getNeighbors: (nodeId: string, edges?: EdgeConfig[], type?: 'target' | 'source' | undefined) => string[];
 /**
@@ -27,7 +27,1 @@ * 获取指定节点的出边
 export declare const uniqueId: (index?: number) => string;
-/**
- * get adjacency matrix
- * @param data graph data
- * @param directed whether it's a directed graph
- */
-export declare const getAdjMatrix: (graphData: GraphData, directed?: boolean) => Matrix[];

lib/util.js

@@ -6,3 +6,3 @@ "use strict";
 });
-exports.getAdjMatrix = exports.uniqueId = exports.getEdgesByNodeId = exports.getOutEdgesNodeId = exports.getNeighbors = void 0;
+exports.uniqueId = exports.getEdgesByNodeId = exports.getOutEdgesNodeId = exports.getNeighbors = void 0;
 
@@ -16,2 +16,6 @@ /**
 var getNeighbors = function getNeighbors(nodeId, edges, type) {
+  if (edges === void 0) {
+    edges = [];
+  }
+
   var currentEdges = edges.filter(function (edge) {
@@ -93,47 +97,3 @@ return edge.source === nodeId || edge.target === nodeId;
 };
-/**
- * get adjacency matrix
- * @param data graph data
- * @param directed whether it's a directed graph
- */
 
-
-exports.uniqueId = uniqueId;
-
-var getAdjMatrix = function getAdjMatrix(graphData, directed) {
-  var nodes = graphData.nodes,
-      edges = graphData.edges;
-  var matrix = []; // map node with index in data.nodes
-
-  var nodeMap = {};
-
-  if (!nodes) {
-    throw new Error('invalid nodes data!');
-  }
-
-  if (nodes) {
-    nodes.forEach(function (node, i) {
-      nodeMap[node.id] = i;
-      var row = [];
-      matrix.push(row);
-    });
-  }
-
-  if (edges) {
-    edges.forEach(function (e) {
-      var source = e.source,
-          target = e.target;
-      var sIndex = nodeMap[source];
-      var tIndex = nodeMap[target];
-      matrix[sIndex][tIndex] = 1;
-
-      if (!directed) {
-        matrix[tIndex][sIndex] = 1;
-      }
-    });
-  }
-
-  return matrix;
-};
-
-exports.getAdjMatrix = getAdjMatrix;
+exports.uniqueId = uniqueId;

package.json

 {
   "name": "@antv/algorithm",
-  "version": "0.0.3",
+  "version": "0.0.4",
   "description": "graph algorithm",
@@ -5,0 +5,0 @@ "keywords": [

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

247932

increased by1.94%

Lines of code

6688

increased by0.83%

No dependency changes