@antv/algorithm - npm Package Compare versions

Comparing version 0.0.6 to 0.0.7

dist/index.js

@@ -80,2 +80,14 @@ (function (global, factory) {
 
+  function _toConsumableArray(arr) {
+    return _arrayWithoutHoles(arr) || _iterableToArray(arr) || _unsupportedIterableToArray(arr) || _nonIterableSpread();
+  }
+
+  function _arrayWithoutHoles(arr) {
+    if (Array.isArray(arr)) return _arrayLikeToArray(arr);
+  }
+
+  function _iterableToArray(iter) {
+    if (typeof Symbol !== "undefined" && Symbol.iterator in Object(iter)) return Array.from(iter);
+  }
+
   function _unsupportedIterableToArray(o, minLen) {
@@ -98,2 +110,6 @@ if (!o) return;
 
+  function _nonIterableSpread() {
+    throw new TypeError("Invalid attempt to spread non-iterable instance.\nIn order to be iterable, non-array objects must have a [Symbol.iterator]() method.");
+  }
+
   function _createForOfIteratorHelper(o, allowArrayLike) {
@@ -1029,12 +1045,12 @@ var it;
       var minNode = minVertex(D, nodes, marks);
-      var minNodId = minNode.id;
-      marks[minNodId] = true;
-      if (D[minNodId] === Infinity) return "continue"; // Unreachable vertices cannot be the intermediate point
+      var minNodeId = minNode.id;
+      marks[minNodeId] = true;
+      if (D[minNodeId] === Infinity) return "continue"; // Unreachable vertices cannot be the intermediate point
 
       var relatedEdges = [];
-      if (directed) relatedEdges = getOutEdgesNodeId(minNodId, edges);else relatedEdges = getEdgesByNodeId(minNodId, edges);
+      if (directed) relatedEdges = getOutEdgesNodeId(minNodeId, edges);else relatedEdges = getEdgesByNodeId(minNodeId, edges);
       relatedEdges.forEach(function (edge) {
         var edgeTarget = edge.target;
         var edgeSource = edge.source;
-        var w = edgeTarget === minNodId ? edgeSource : edgeTarget;
+        var w = edgeTarget === minNodeId ? edgeSource : edgeTarget;
         var weight = weightPropertyName && edge[weightPropertyName] ? edge[weightPropertyName] : 1;
@@ -1044,3 +1060,5 @@
           D[w] = D[minNode.id] + weight;
-          prevs[w] = minNode.id;
+          prevs[w] = [minNode.id];
+        } else if (D[w] === D[minNode.id] + weight) {
+          prevs[w].push(minNode.id);
         }
@@ -1056,12 +1074,17 @@ });
 
-    var path = {};
+    prevs[source] = [source]; // 每个节点存可能存在多条最短路径
 
+    var allPaths = {};
+
     for (var target in D) {
-      path[target] = [target];
-      var prev = prevs[target];
+      if (D[target] !== Infinity) {
+        findAllPaths(source, target, prevs, allPaths);
+      }
+    } // 兼容之前单路径
 
-      while (prev !== undefined) {
-        path[target].unshift(prev);
-        prev = prevs[prev];
-      }
+
+    var path = {};
+
+    for (var _target in allPaths) {
+      path[_target] = allPaths[_target][0];
     }
@@ -1071,14 +1094,60 @@
       length: D,
-      path: path
+      path: path,
+      allPaths: allPaths
     };
   };
 
+  function findAllPaths(source, target, prevs, findedPaths) {
+    if (source === target) {
+      return [source];
+    }
+
+    if (findedPaths[target]) {
+      return findedPaths[target];
+    }
+
+    var paths = [];
+
+    var _iterator = _createForOfIteratorHelper(prevs[target]),
+        _step;
+
+    try {
+      for (_iterator.s(); !(_step = _iterator.n()).done;) {
+        var prev = _step.value;
+        var prevPaths = findAllPaths(source, prev, prevs, findedPaths);
+
+        var _iterator2 = _createForOfIteratorHelper(prevPaths),
+            _step2;
+
+        try {
+          for (_iterator2.s(); !(_step2 = _iterator2.n()).done;) {
+            var prePath = _step2.value;
+            paths.push([].concat(_toConsumableArray(prePath), [target]));
+          }
+        } catch (err) {
+          _iterator2.e(err);
+        } finally {
+          _iterator2.f();
+        }
+      }
+    } catch (err) {
+      _iterator.e(err);
+    } finally {
+      _iterator.f();
+    }
+
+    findedPaths[target] = paths;
+    return;
+  }
+
   var findShortestPath = function findShortestPath(graphData, start, end, directed, weightPropertyName) {
     var _dijkstra = dijkstra(graphData, start, directed, weightPropertyName),
         length = _dijkstra.length,
-        path = _dijkstra.path;
+        path = _dijkstra.path,
+        allPaths = _dijkstra.allPaths;
 
     return {
       length: length[end],
-      path: path[end]
+      path: path[end],
+      allPath: allPaths[end]
     };
@@ -1085,0 +1154,0 @@ };

dist/index.min.js

@@ -1,1 +0,1 @@
-!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 a(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 a,u=!0,s=!1;return{s:function(){n=t[Symbol.iterator]()},n:function(){var t=n.next();return u=t.done,t},e:function(t){s=!0,a=t},f:function(){try{u||null==n.return||n.return()}finally{if(s)throw a}}}}var u=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]:u;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}(),c=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 a=function(e){return e.source===t?e.target:e.source};return r.map(a)},f=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,e="".concat(Math.random()).split(".")[1].substr(0,5),n="".concat(Math.random()).split(".")[1].substr(0,5);return"".concat(t,"-").concat(e).concat(n)};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;c(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,a=t.edges,u=void 0===a?[]:a,s={},l={},h={};o.forEach((function(t,n){var r=t.id;l[r]=1/0,r===e&&(l[r]=0)}));for(var c=o.length,d=function(t){var e=function(t,e,n){for(var r,i=1/0,o=0;e.length>o;o++){var a=e[o].id;n[a]||t[a]>i||(i=t[a],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,u):f(i,u)).forEach((function(t){var n=t.target,o=n===i?t.source:n,a=r&&t[r]?t[r]:1;l[o]>l[e.id]+a&&(l[o]=l[e.id]+a,h[o]=e.id)}))},v=0;c>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,a=0,u=0;i>u;u++)for(var s=t[u].clusterId,l=0;i>l;l++){if(s===t[l].clusterId)a+=(e[u][l]||0)-(n[u]||0)*(n[l]||0)/o}return a*=1/o},m=function(){function t(e){n(this,t),this.count=e.length,this.parent={};var r,i=a(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,a=void 0===o?[]:o;if(0===i.length)return n;var u=i[0],s=new Set;s.add(u);var l=new b((function(t,n){return e?t.weight-n.weight:0}));for(f(u.id,a).forEach((function(t){l.insert(t)}));!l.isEmpty();){var h=l.delMin(),c=h.source,d=h.target;s.has(c)&&s.has(d)||(n.push(h),s.has(c)||(s.add(c),f(c,a).forEach((function(t){l.insert(t)}))),s.has(d)||(s.add(d),f(d,a).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 a=(void 0===o?[]:o).map((function(t){return t}));e&&a.sort((function(t,e){return t.weight-e.weight}));for(var u=new m(i.map((function(t){return t.id})));a.length>0;){var s=a.shift(),l=s.source,h=s.target;u.connected(l,h)||(n.push(s),u.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,a=void 0===o?[]:o;i.enqueue(e);for(var u="",s=function(){var t=i.dequeue();r.enter({current:t,previous:u}),c(t,a,"target").forEach((function(e){r.allowTraversal({previous:u,current:t,next:e})&&i.enqueue(e)})),r.leave({current:t,previous:u}),u=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,u=[],s={},l={},h={},f=[],d=0,v=function t(e){l[e.id]=d,h[e.id]=d,d+=1,u.push(e),s[e.id]=!0;for(var n=c(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 a=r.filter((function(t){return t.id===o}));a.length>0&&t(a[0]),h[e.id]=Math.min(h[e.id],h[o])}},a=0;n.length>a;a++)i(a);if(h[e.id]===l[e.id]){for(var v=[];u.length>0;){var g=u.pop();if(s[g.id]=!1,v.push(g),g===e)break}v.length>0&&f.push(v)}},g=a(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 f}(t):function(t){for(var e=t.nodes,n=void 0===e?[]:e,r=t.edges,i=void 0===r?[]:r,o=[],a={},u=[],s=function t(e){u.push(e),a[e.id]=!0;for(var r=c(e.id,i),o=function(e){var i=r[e];if(!a[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(!a[h.id]){s(h);for(var f=[];u.length>0;)f.push(u.pop());o.push(f)}}return o}(t)},t.depthFirstSearch=p,t.detectCycle=function(t){var e=null,n=t.nodes,r={},i={},o={},a={};(void 0===n?[]:n).forEach((function(t){i[t.id]=t}));for(var u={enter:function(t){var n=t.current,a=t.previous;if(o[n]){e={};for(var u=n,s=a;s!==n;)e[u]=s,u=s,s=r[s];e[u]=s}else o[n]=n,delete i[n],r[n]=a},leave:function(t){var e=t.current;a[e]=e,delete o[e]},allowTraversal:function(t){return!e&&!a[t.next]}};Object.keys(i).length;){p(t,Object.keys(i)[0],u)}return e},t.dijkstra=y,t.findAllPath=function(t,e,n,r){if(e===n)return[[e]];var i,o,a,u=t.edges,s=void 0===u?[]:u,l=[e],h=(a=!0,(o=e)in(i={})?Object.defineProperty(i,o,{value:a,enumerable:!0,configurable:!0,writable:!0}):i[o]=a,i),f=[],d=[],v=r?c(e,s,"target"):c(e,s);for(f.push(v);l.length>0&&f.length>0;){var g=f[f.length-1];if(g.length){var p=g.shift();if(p&&(l.push(p),h[p]=!0,v=r?c(p,s,"target"):c(p,s),f.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,f.pop()}}else{var m=l.pop();h[m]=!1,f.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,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 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=c,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,a=void 0===o?[]:o,u=t.edges,s=void 0===u?[]:u,l={},h={};a.forEach((function(t,e){var n=d();t.clusterId=n,l[n]={id:n,nodes:[t]},h[t.id]={node:t,idx:e}}));var c=e(t,n),f={};c.forEach((function(t,e){var n=a[e].id;f[n]={},t.forEach((function(t,e){t&&(f[n][a[e].id]=t)}))}));for(var v=0;i>v;){var g=!1;if(a.forEach((function(t){var e={};Object.keys(f[t.id]).forEach((function(n){var r=f[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],a=o.nodes.indexOf(t);o.nodes.splice(a,1);var u=Math.floor(Math.random()*r.length),s=l[r[u]];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 a={source:n,target:i,weight:e,count:1};y[o]=a,p.push(a)}}));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,a=void 0===o?[]:o,u=t.edges,s=void 0===u?[]:u,l={},h={};a.forEach((function(t,e){var n=d();t.clusterId=n,l[n]={id:n,nodes:[t]},h[t.id]={node:t,idx:e}}));var c=e(t,n),f=[],v={},g=0;c.forEach((function(t,e){var n=0,r=a[e].id;v[r]={},t.forEach((function(t,e){t&&(n+=t,v[r][a[e].id]=t,g+=t)})),f.push(n)})),g/=2;for(var p=1/0,y=1/0,m=0;p=k(a,c,f,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})),a.forEach((function(t,e){var n,i=l[t.clusterId],o=0,a=f[e]/(2*g),u=0;i.nodes.forEach((function(t){u+=c[e][h[t.id].idx]||0}));var d=u-i.sumTot*a;if(Object.keys(v[t.id]).forEach((function(r){var i=h[r].node.clusterId;if(i!==t.clusterId){var u=l[i],s=u.nodes;if(s&&s.length){var f=0;s.forEach((function(t){f+=c[e][h[t.id].idx]||0}));var v=f-u.sumTot*a-d;v>o&&(o=v,n=u)}}})),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 a={source:n,target:i,weight:e,count:1};b[o]=a,E.push(a)}}));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,a=1e3,u=t.nodes,s=void 0===u?[]:u,l=t.edges,h=void 0===l?[]:l,f=s.length,d={},g={},p=0;f>p;++p){var y=s[p].id;d[y]=1/f,g[y]=1/f}for(var k=v(t);a>0&&i>e;){o=0;for(var m=0;f>m;++m){var E=s[m],b=E.id;if(r=0,0===k[E.id].inDegree)d[b]=0;else{for(var x=c(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)/f,i=0;for(var O=0;f>O;++O){var j=s[O].id;i+=Math.abs((r=d[j]+o)-g[j]),g[j]=r}a-=1}return g},Object.defineProperty(t,"__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){return function(t){if(Array.isArray(t))return u(t)}(t)||function(t){if("undefined"!=typeof Symbol&&Symbol.iterator in Object(t))return Array.from(t)}(t)||a(t)||function(){throw new TypeError("Invalid attempt to spread non-iterable instance.\nIn order to be iterable, non-array objects must have a [Symbol.iterator]() method.")}()}function a(t,e){if(t){if("string"==typeof t)return u(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)?u(t,e):void 0}}function u(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 s(t,e){var n;if("undefined"==typeof Symbol||null==t[Symbol.iterator]){if(Array.isArray(t)||(n=a(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 o,u=!0,s=!1;return{s:function(){n=t[Symbol.iterator]()},n:function(){var t=n.next();return u=t.done,t},e:function(t){s=!0,o=t},f:function(){try{u||null==n.return||n.return()}finally{if(s)throw o}}}}var l=function(t,e){return t===e},f=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}(),c=function(){function t(){var e=arguments.length>0&&void 0!==arguments[0]?arguments[0]:l;n(this,t),this.head=null,this.tail=null,this.compare=e}return i(t,[{key:"prepend",value:function(t){var e=new f(t,this.head);return this.head=e,this.tail||(this.tail=e),this}},{key:"append",value:function(t){var e=new f(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 c}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}(),d=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 a=function(e){return e.source===t?e.target:e.source};return r.map(a)},v=function(t,e){return e.filter((function(e){return e.source===t||e.target===t}))},g=function(){var t=arguments.length>0&&void 0!==arguments[0]?arguments[0]:0,e="".concat(Math.random()).split(".")[1].substr(0,5),n="".concat(Math.random()).split(".")[1].substr(0,5);return"".concat(t,"-").concat(e).concat(n)};var p=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 y(t,e,n,r){r.enter({current:e,previous:n});var i=t.edges;d(e,void 0===i?[]:i,"target").forEach((function(i){r.allowTraversal({previous:n,current:e,next:i})&&y(t,i,e,r)})),r.leave({current:e,previous:n})}function m(t,e,n){y(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 k=function(t,e,n,r){var i=t.nodes,o=void 0===i?[]:i,a=t.edges,u=void 0===a?[]:a,s={},l={},f={};o.forEach((function(t,n){var r=t.id;l[r]=1/0,r===e&&(l[r]=0)}));for(var c=o.length,h=function(t){var e=function(t,e,n){for(var r,i=1/0,o=0;e.length>o;o++){var a=e[o].id;n[a]||t[a]>i||(i=t[a],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,u):v(i,u)).forEach((function(t){var n=t.target,o=n===i?t.source:n,a=r&&t[r]?t[r]:1;l[o]>l[e.id]+a?(l[o]=l[e.id]+a,f[o]=[e.id]):l[o]===l[e.id]+a&&f[o].push(e.id)}))},d=0;c>d;d++)h();f[e]=[e];var g={};for(var p in l)l[p]!==1/0&&b(e,p,f,g);var y={};for(var m in g)y[m]=g[m][0];return{length:l,path:y,allPaths:g}};function b(t,e,n,r){if(t===e)return[t];if(r[e])return r[e];var i,a=[],u=s(n[e]);try{for(u.s();!(i=u.n()).done;){var l,f=s(b(t,i.value,n,r));try{for(f.s();!(l=f.n()).done;){a.push([].concat(o(l.value),[e]))}}catch(t){f.e(t)}finally{f.f()}}}catch(t){u.e(t)}finally{u.f()}r[e]=a}var E=function(t,e,n,r){for(var i=e.length,o=2*r,a=0,u=0;i>u;u++)for(var s=t[u].clusterId,l=0;i>l;l++){if(s===t[l].clusterId)a+=(e[u][l]||0)-(n[u]||0)*(n[l]||0)/o}return a*=1/o},x=function(){function t(e){n(this,t),this.count=e.length,this.parent={};var r,i=s(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}(),w=function(t,e){return t-e},I=function(){function t(){var e=arguments.length>0&&void 0!==arguments[0]?arguments[0]:w;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}(),S=function(t,e){var n=[],r=t.nodes,i=void 0===r?[]:r,o=t.edges,a=void 0===o?[]:o;if(0===i.length)return n;var u=i[0],s=new Set;s.add(u);var l=new I((function(t,n){return e?t.weight-n.weight:0}));for(v(u.id,a).forEach((function(t){l.insert(t)}));!l.isEmpty();){var f=l.delMin(),c=f.source,h=f.target;s.has(c)&&s.has(h)||(n.push(f),s.has(c)||(s.add(c),v(c,a).forEach((function(t){l.insert(t)}))),s.has(h)||(s.add(h),v(h,a).forEach((function(t){l.insert(t)}))))}return n},j=function(t,e){var n=[],r=t.nodes,i=void 0===r?[]:r,o=t.edges;if(0===i.length)return n;var a=(void 0===o?[]:o).map((function(t){return t}));e&&a.sort((function(t,e){return t.weight-e.weight}));for(var u=new x(i.map((function(t){return t.id})));a.length>0;){var s=a.shift(),l=s.source,f=s.target;u.connected(l,f)||(n.push(s),u.union(l,f))}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 c,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,a=void 0===o?[]:o;i.enqueue(e);for(var u="",s=function(){var t=i.dequeue();r.enter({current:t,previous:u}),d(t,a,"target").forEach((function(e){r.allowTraversal({previous:u,current:t,next:e})&&i.enqueue(e)})),r.leave({current:t,previous:u}),u=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=[],u={},l={},f={},c=[],h=0,v=function t(e){l[e.id]=h,f[e.id]=h,h+=1,a.push(e),u[e.id]=!0;for(var n=d(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])u[o]&&(f[e.id]=Math.min(f[e.id],l[o]));else{var a=r.filter((function(t){return t.id===o}));a.length>0&&t(a[0]),f[e.id]=Math.min(f[e.id],f[o])}},s=0;n.length>s;s++)i(s);if(f[e.id]===l[e.id]){for(var v=[];a.length>0;){var g=a.pop();if(u[g.id]=!1,v.push(g),g===e)break}v.length>0&&c.push(v)}},g=s(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=[],a={},u=[],s=function t(e){u.push(e),a[e.id]=!0;for(var r=d(e.id,i),o=function(e){var i=r[e];if(!a[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 f=n[l];if(!a[f.id]){s(f);for(var c=[];u.length>0;)c.push(u.pop());o.push(c)}}return o}(t)},t.depthFirstSearch=m,t.detectCycle=function(t){var e=null,n=t.nodes,r={},i={},o={},a={};(void 0===n?[]:n).forEach((function(t){i[t.id]=t}));for(var u={enter:function(t){var n=t.current,a=t.previous;if(o[n]){e={};for(var u=n,s=a;s!==n;)e[u]=s,u=s,s=r[s];e[u]=s}else o[n]=n,delete i[n],r[n]=a},leave:function(t){var e=t.current;a[e]=e,delete o[e]},allowTraversal:function(t){return!e&&!a[t.next]}};Object.keys(i).length;){m(t,Object.keys(i)[0],u)}return e},t.dijkstra=k,t.findAllPath=function(t,e,n,r){if(e===n)return[[e]];var i,o,a,u=t.edges,s=void 0===u?[]:u,l=[e],f=(a=!0,(o=e)in(i={})?Object.defineProperty(i,o,{value:a,enumerable:!0,configurable:!0,writable:!0}):i[o]=a,i),c=[],h=[],v=r?d(e,s,"target"):d(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),f[p]=!0,v=r?d(p,s,"target"):d(p,s),c.push(v.filter((function(t){return!f[t]})))),l[l.length-1]===n){var y=l.map((function(t){return t}));h.push(y);var m=l.pop();f[m]=!1,c.pop()}}else{var k=l.pop();f[k]=!1,c.pop()}}return h},t.findShortestPath=function(t,e,n,r,i){var o=k(t,e,r,i);return{length:o.length[n],path:o.path[n],allPath:o.allPaths[n]}},t.floydWarshall=function(t,n){for(var r=e(t,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 l=0;o>l;l+=1)for(var f=0;o>f;f+=1)i[l][f]>i[l][s]+i[s][f]&&(i[l][f]=i[l][s]+i[s][f]);return i},t.getAdjMatrix=e,t.getDegree=p,t.getInDegree=function(t,e){return p(t)[e]?p(t)[e].inDegree:0},t.getNeighbors=d,t.getOutDegree=function(t,e){return p(t)[e]?p(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,a=void 0===o?[]:o,u=t.edges,s=void 0===u?[]:u,l={},f={};a.forEach((function(t,e){var n=g();t.clusterId=n,l[n]={id:n,nodes:[t]},f[t.id]={node:t,idx:e}}));var c=e(t,n),h={};c.forEach((function(t,e){var n=a[e].id;h[n]={},t.forEach((function(t,e){t&&(h[n][a[e].id]=t)}))}));for(var d=0;i>d;){var v=!1;if(a.forEach((function(t){var e={};Object.keys(h[t.id]).forEach((function(n){var r=h[t.id][n],i=f[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){v=!0;var o=l[t.clusterId],a=o.nodes.indexOf(t);o.nodes.splice(a,1);var u=Math.floor(Math.random()*r.length),s=l[r[u]];s.nodes.push(t),t.clusterId=s.id}}})),!v)break;d++}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=f[t.source].node.clusterId,i=f[t.target].node.clusterId,o="".concat(n,"---").concat(i);if(y[o])y[o].weight+=e,y[o].count++;else{var a={source:n,target:i,weight:e,count:1};y[o]=a,p.push(a)}}));var m=[];return Object.keys(l).forEach((function(t){m.push(l[t])})),{clusters:m,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,a=void 0===o?[]:o,u=t.edges,s=void 0===u?[]:u,l={},f={};a.forEach((function(t,e){var n=g();t.clusterId=n,l[n]={id:n,nodes:[t]},f[t.id]={node:t,idx:e}}));var c=e(t,n),h=[],d={},v=0;c.forEach((function(t,e){var n=0,r=a[e].id;d[r]={},t.forEach((function(t,e){t&&(n+=t,d[r][a[e].id]=t,v+=t)})),h.push(n)})),v/=2;for(var p=1/0,y=1/0,m=0;p=E(a,c,h,v),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=f[n.source].node.clusterId,o=f[n.target].node.clusterId;(i===t&&o!==t||o===t&&i!==t)&&(e+=n[r]||1)})),l[t].sumTot=e})),a.forEach((function(t,e){var n,i=l[t.clusterId],o=0,a=h[e]/(2*v),u=0;i.nodes.forEach((function(t){u+=c[e][f[t.id].idx]||0}));var g=u-i.sumTot*a;if(Object.keys(d[t.id]).forEach((function(r){var i=f[r].node.clusterId;if(i!==t.clusterId){var u=l[i],s=u.nodes;if(s&&s.length){var h=0;s.forEach((function(t){h+=c[e][f[t.id].idx]||0}));var d=h-u.sumTot*a-g;d>o&&(o=d,n=u)}}})),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 m=0,k=0;s.forEach((function(t){var e=f[t.source].node.clusterId,i=f[t.target].node.clusterId;(e===n.id&&i!==n.id||i===n.id&&e!==n.id)&&(m+=t[r]||1),(e===p&&i!==p||i===p&&e!==p)&&(k+=t[r]||1)})),n.sumTot=m,i.sumTot=k}}));Object.keys(l).forEach((function(t){var e=l[t];e.nodes&&e.nodes.length||delete l[t]}));var k=[],b={};s.forEach((function(t){var e=t[r]||1,n=f[t.source].node.clusterId,i=f[t.target].node.clusterId,o="".concat(n,"---").concat(i);if(b[o])b[o].weight+=e,b[o].count++;else{var a={source:n,target:i,weight:e,count:1};b[o]=a,k.push(a)}}));var x=[];return Object.keys(l).forEach((function(t){x.push(l[t])})),{clusters:x,clusterEdges:k}},t.minimumSpanningTree=function(t,e,n){return n?{prim:S,kruskal:j}[n](t,e):j(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,a=1e3,u=t.nodes,s=void 0===u?[]:u,l=t.edges,f=void 0===l?[]:l,c=s.length,h={},v={},g=0;c>g;++g){var y=s[g].id;h[y]=1/c,v[y]=1/c}for(var m=p(t);a>0&&i>e;){o=0;for(var k=0;c>k;++k){var b=s[k],E=b.id;if(r=0,0===m[b.id].inDegree)h[E]=0;else{for(var x=d(E,f,"source"),w=0;x.length>w;++w){var I=x[w],S=m[I].outDegree;S>0&&(r+=v[I]/S)}h[E]=n*r,o+=h[E]}}o=(1-o)/c,i=0;for(var j=0;c>j;++j){var O=s[j].id;i+=Math.abs((r=h[O]+o)-v[O]),v[O]=r}a-=1}return v},Object.defineProperty(t,"__esModule",{value:!0})}));

dist/src/dijkstra.d.ts

@@ -1,6 +0,7 @@
-import { GraphData } from "./types";
+import { GraphData } from './types';
 declare const dijkstra: (graphData: GraphData, source: string, directed?: boolean, weightPropertyName?: string) => {
     length: {};
     path: {};
+    allPaths: {};
 };
 export default dijkstra;

dist/src/find-path.d.ts

@@ -5,3 +5,4 @@ import { GraphData } from './types';
     path: any;
+    allPath: any;
 };
 export declare const findAllPath: (graphData: GraphData, start: string, end: string, directed?: boolean) => any[];

es/dijkstra.d.ts

@@ -1,6 +0,7 @@
-import { GraphData } from "./types";
+import { GraphData } from './types';
 declare const dijkstra: (graphData: GraphData, source: string, directed?: boolean, weightPropertyName?: string) => {
     length: {};
     path: {};
+    allPaths: {};
 };
 export default dijkstra;

es/dijkstra.js

@@ -1,2 +0,3 @@
-import { getOutEdgesNodeId, getEdgesByNodeId } from "./util";
+import { __spreadArrays } from "tslib";
+import { getOutEdgesNodeId, getEdgesByNodeId } from './util';
 
@@ -41,12 +42,12 @@ var minVertex = function minVertex(D, nodes, marks) {
     var minNode = minVertex(D, nodes, marks);
-    var minNodId = minNode.id;
-    marks[minNodId] = true;
-    if (D[minNodId] === Infinity) return "continue"; // Unreachable vertices cannot be the intermediate point
+    var minNodeId = minNode.id;
+    marks[minNodeId] = true;
+    if (D[minNodeId] === Infinity) return "continue"; // Unreachable vertices cannot be the intermediate point
 
     var relatedEdges = [];
-    if (directed) relatedEdges = getOutEdgesNodeId(minNodId, edges);else relatedEdges = getEdgesByNodeId(minNodId, edges);
+    if (directed) relatedEdges = getOutEdgesNodeId(minNodeId, edges);else relatedEdges = getEdgesByNodeId(minNodeId, edges);
     relatedEdges.forEach(function (edge) {
       var edgeTarget = edge.target;
       var edgeSource = edge.source;
-      var w = edgeTarget === minNodId ? edgeSource : edgeTarget;
+      var w = edgeTarget === minNodeId ? edgeSource : edgeTarget;
       var weight = weightPropertyName && edge[weightPropertyName] ? edge[weightPropertyName] : 1;
@@ -56,3 +57,5 @@
         D[w] = D[minNode.id] + weight;
-        prevs[w] = minNode.id;
+        prevs[w] = [minNode.id];
+      } else if (D[w] === D[minNode.id] + weight) {
+        prevs[w].push(minNode.id);
       }
@@ -66,12 +69,17 @@ });
 
-  var path = {};
+  prevs[source] = [source]; // 每个节点存可能存在多条最短路径
 
+  var allPaths = {};
+
   for (var target in D) {
-    path[target] = [target];
-    var prev = prevs[target];
+    if (D[target] !== Infinity) {
+      findAllPaths(source, target, prevs, allPaths);
+    }
+  } // 兼容之前单路径
 
-    while (prev !== undefined) {
-      path[target].unshift(prev);
-      prev = prevs[prev];
-    }
+
+  var path = {};
+
+  for (var target in allPaths) {
+    path[target] = allPaths[target][0];
   }
@@ -81,6 +89,32 @@
     length: D,
-    path: path
+    path: path,
+    allPaths: allPaths
   };
 };
 
-export default dijkstra;
+export default dijkstra;
+
+function findAllPaths(source, target, prevs, findedPaths) {
+  if (source === target) {
+    return [source];
+  }
+
+  if (findedPaths[target]) {
+    return findedPaths[target];
+  }
+
+  var paths = [];
+
+  for (var _i = 0, _a = prevs[target]; _i < _a.length; _i++) {
+    var prev = _a[_i];
+    var prevPaths = findAllPaths(source, prev, prevs, findedPaths);
+
+    for (var _b = 0, prevPaths_1 = prevPaths; _b < prevPaths_1.length; _b++) {
+      var prePath = prevPaths_1[_b];
+      paths.push(__spreadArrays(prePath, [target]));
+    }
+  }
+
+  findedPaths[target] = paths;
+  return;
+}

es/find-path.d.ts

@@ -5,3 +5,4 @@ import { GraphData } from './types';
     path: any;
+    allPath: any;
 };
 export declare const findAllPath: (graphData: GraphData, start: string, end: string, directed?: boolean) => any[];

es/find-path.js

@@ -6,7 +6,9 @@ import dijkstra from './dijkstra';
       length = _a.length,
-      path = _a.path;
+      path = _a.path,
+      allPaths = _a.allPaths;
 
   return {
     length: length[end],
-    path: path[end]
+    path: path[end],
+    allPath: allPaths[end]
   };
@@ -13,0 +15,0 @@ };

lib/dijkstra.d.ts

@@ -1,6 +0,7 @@
-import { GraphData } from "./types";
+import { GraphData } from './types';
 declare const dijkstra: (graphData: GraphData, source: string, directed?: boolean, weightPropertyName?: string) => {
     length: {};
     path: {};
+    allPaths: {};
 };
 export default dijkstra;

lib/dijkstra.js

@@ -8,2 +8,4 @@ "use strict";
 
+var _tslib = require("tslib");
+
 var _util = require("./util");
@@ -49,12 +51,12 @@
     var minNode = minVertex(D, nodes, marks);
-    var minNodId = minNode.id;
-    marks[minNodId] = true;
-    if (D[minNodId] === Infinity) return "continue"; // Unreachable vertices cannot be the intermediate point
+    var minNodeId = minNode.id;
+    marks[minNodeId] = true;
+    if (D[minNodeId] === Infinity) return "continue"; // Unreachable vertices cannot be the intermediate point
 
     var relatedEdges = [];
-    if (directed) relatedEdges = (0, _util.getOutEdgesNodeId)(minNodId, edges);else relatedEdges = (0, _util.getEdgesByNodeId)(minNodId, edges);
+    if (directed) relatedEdges = (0, _util.getOutEdgesNodeId)(minNodeId, edges);else relatedEdges = (0, _util.getEdgesByNodeId)(minNodeId, edges);
     relatedEdges.forEach(function (edge) {
       var edgeTarget = edge.target;
       var edgeSource = edge.source;
-      var w = edgeTarget === minNodId ? edgeSource : edgeTarget;
+      var w = edgeTarget === minNodeId ? edgeSource : edgeTarget;
       var weight = weightPropertyName && edge[weightPropertyName] ? edge[weightPropertyName] : 1;
@@ -64,3 +66,5 @@
         D[w] = D[minNode.id] + weight;
-        prevs[w] = minNode.id;
+        prevs[w] = [minNode.id];
+      } else if (D[w] === D[minNode.id] + weight) {
+        prevs[w].push(minNode.id);
       }
@@ -74,12 +78,17 @@ });
 
-  var path = {};
+  prevs[source] = [source]; // 每个节点存可能存在多条最短路径
 
+  var allPaths = {};
+
   for (var target in D) {
-    path[target] = [target];
-    var prev = prevs[target];
+    if (D[target] !== Infinity) {
+      findAllPaths(source, target, prevs, allPaths);
+    }
+  } // 兼容之前单路径
 
-    while (prev !== undefined) {
-      path[target].unshift(prev);
-      prev = prevs[prev];
-    }
+
+  var path = {};
+
+  for (var target in allPaths) {
+    path[target] = allPaths[target][0];
   }
@@ -89,3 +98,4 @@
     length: D,
-    path: path
+    path: path,
+    allPaths: allPaths
   };
@@ -95,2 +105,27 @@ };
 var _default = dijkstra;
-exports["default"] = _default;
+exports["default"] = _default;
+
+function findAllPaths(source, target, prevs, findedPaths) {
+  if (source === target) {
+    return [source];
+  }
+
+  if (findedPaths[target]) {
+    return findedPaths[target];
+  }
+
+  var paths = [];
+
+  for (var _i = 0, _a = prevs[target]; _i < _a.length; _i++) {
+    var prev = _a[_i];
+    var prevPaths = findAllPaths(source, prev, prevs, findedPaths);
+
+    for (var _b = 0, prevPaths_1 = prevPaths; _b < prevPaths_1.length; _b++) {
+      var prePath = prevPaths_1[_b];
+      paths.push((0, _tslib.__spreadArrays)(prePath, [target]));
+    }
+  }
+
+  findedPaths[target] = paths;
+  return;
+}

lib/find-path.d.ts

@@ -5,3 +5,4 @@ import { GraphData } from './types';
     path: any;
+    allPath: any;
 };
 export declare const findAllPath: (graphData: GraphData, start: string, end: string, directed?: boolean) => any[];

lib/find-path.js

@@ -17,7 +17,9 @@ "use strict";
       length = _a.length,
-      path = _a.path;
+      path = _a.path,
+      allPaths = _a.allPaths;
 
   return {
     length: length[end],
-    path: path[end]
+    path: path[end],
+    allPath: allPaths[end]
   };
@@ -24,0 +26,0 @@ };

package.json

 {
   "name": "@antv/algorithm",
-  "version": "0.0.6",
+  "version": "0.0.7",
   "description": "graph algorithm",
@@ -31,3 +31,3 @@ "keywords": [
     "test": "jest",
-    "test-live": "DEBUG_MODE=1 jest --watch  ./tests/unit/louvain-spec.ts",
+    "test-live": "DEBUG_MODE=1 jest --watch  ./tests/unit/find-path-spec.ts",
     "lint-staged:js": "eslint --ext .js,.jsx,.ts,.tsx"
@@ -34,0 +34,0 @@ },

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

Major refactor

Supply chain risk

Package has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

253072

increased by1.87%

Lines of code

6811

increased by1.75%

Number of medium supply chain risk alerts

0

decreased by-100%

No dependency changes