| 1 |
- import{c as t}from"./exceljs.DLSZe_6I.js";import{r as e,a as n,b as r,c as i,d as s,e as o,f as u,g as a,h,i as c,j as d,k as f,l as p,m as _,n as l,o as v}from"./lodash.D-BGNLlY.js";var y,g,m,w,E,k,N,b,C,I,L,j,D,F,O,M,P,U,S,T,x,z,G,A,V,Y,W,B,K,Q,$,q,H,J,R,X,Z,tt,et,nt;function rt(){if(g)return y;var m;if(g=1,"function"==typeof t)try{m={clone:v(),constant:l(),each:_(),filter:p(),has:f(),isArray:d(),isEmpty:c(),isFunction:h(),isUndefined:a(),keys:u(),map:o(),reduce:s(),size:i(),transform:r(),union:n(),values:e()}}catch(w){}return m||(m=window._),y=m}function it(){if(w)return m;w=1;var t=rt();m=n;var e="\0";function n(n){this._isDirected=!t.has(n,"directed")||n.directed,this._isMultigraph=!!t.has(n,"multigraph")&&n.multigraph,this._isCompound=!!t.has(n,"compound")&&n.compound,this._label=void 0,this._defaultNodeLabelFn=t.constant(void 0),this._defaultEdgeLabelFn=t.constant(void 0),this._nodes={},this._isCompound&&(this._parent={},this._children={},this._children[e]={}),this._in={},this._preds={},this._out={},this._sucs={},this._edgeObjs={},this._edgeLabels={}}function r(t,e){t[e]?t[e]++:t[e]=1}function i(t,e){--t[e]||delete t[e]}function s(e,n,r,i){var s=""+n,o=""+r;if(!e&&s>o){var u=s;s=o,o=u}return s+""+o+""+(t.isUndefined(i)?"\0":i)}function o(t,e){return s(t,e.v,e.w,e.name)}return n.prototype._nodeCount=0,n.prototype._edgeCount=0,n.prototype.isDirected=function(){return this._isDirected},n.prototype.isMultigraph=function(){return this._isMultigraph},n.prototype.isCompound=function(){return this._isCompound},n.prototype.setGraph=function(t){return this._label=t,this},n.prototype.graph=function(){return this._label},n.prototype.setDefaultNodeLabel=function(e){return t.isFunction(e)||(e=t.constant(e)),this._defaultNodeLabelFn=e,this},n.prototype.nodeCount=function(){return this._nodeCount},n.prototype.nodes=function(){return t.keys(this._nodes)},n.prototype.sources=function(){var e=this;return t.filter(this.nodes(),function(n){return t.isEmpty(e._in[n])})},n.prototype.sinks=function(){var e=this;return t.filter(this.nodes(),function(n){return t.isEmpty(e._out[n])})},n.prototype.setNodes=function(e,n){var r=arguments,i=this;return t.each(e,function(t){r.length>1?i.setNode(t,n):i.setNode(t)}),this},n.prototype.setNode=function(n,r){return t.has(this._nodes,n)?(arguments.length>1&&(this._nodes[n]=r),this):(this._nodes[n]=arguments.length>1?r:this._defaultNodeLabelFn(n),this._isCompound&&(this._parent[n]=e,this._children[n]={},this._children[e][n]=!0),this._in[n]={},this._preds[n]={},this._out[n]={},this._sucs[n]={},++this._nodeCount,this)},n.prototype.node=function(t){return this._nodes[t]},n.prototype.hasNode=function(e){return t.has(this._nodes,e)},n.prototype.removeNode=function(e){var n=this;if(t.has(this._nodes,e)){var r=function(t){n.removeEdge(n._edgeObjs[t])};delete this._nodes[e],this._isCompound&&(this._removeFromParentsChildList(e),delete this._parent[e],t.each(this.children(e),function(t){n.setParent(t)}),delete this._children[e]),t.each(t.keys(this._in[e]),r),delete this._in[e],delete this._preds[e],t.each(t.keys(this._out[e]),r),delete this._out[e],delete this._sucs[e],--this._nodeCount}return this},n.prototype.setParent=function(n,r){if(!this._isCompound)throw new Error("Cannot set parent in a non-compound graph");if(t.isUndefined(r))r=e;else{for(var i=r+="";!t.isUndefined(i);i=this.parent(i))if(i===n)throw new Error("Setting "+r+" as parent of "+n+" would create a cycle");this.setNode(r)}return this.setNode(n),this._removeFromParentsChildList(n),this._parent[n]=r,this._children[r][n]=!0,this},n.prototype._removeFromParentsChildList=function(t){delete this._children[this._parent[t]][t]},n.prototype.parent=function(t){if(this._isCompound){var n=this._parent[t];if(n!==e)return n}},n.prototype.children=function(n){if(t.isUndefined(n)&&(n=e),this._isCompound){var r=this._children[n];if(r)return t.keys(r)}else{if(n===e)return this.nodes();if(this.hasNode(n))return[]}},n.prototype.predecessors=function(e){var n=this._preds[e];if(n)return t.keys(n)},n.prototype.successors=function(e){var n=this._sucs[e];if(n)return t.keys(n)},n.prototype.neighbors=function(e){var n=this.predecessors(e);if(n)return t.union(n,this.successors(e))},n.prototype.isLeaf=function(t){return 0===(this.isDirected()?this.successors(t):this.neighbors(t)).length},n.prototype.filterNodes=function(e){var n=new this.constructor({directed:this._isDirected,multigraph:this._isMultigraph,compound:this._isCompound});n.setGraph(this.graph());var r=this;t.each(this._nodes,function(t,r){e(r)&&n.setNode(r,t)}),t.each(this._edgeObjs,function(t){n.hasNode(t.v)&&n.hasNode(t.w)&&n.setEdge(t,r.edge(t))});var i={};function s(t){var e=r.parent(t);return void 0===e||n.hasNode(e)?(i[t]=e,e):e in i?i[e]:s(e)}return this._isCompound&&t.each(n.nodes(),function(t){n.setParent(t,s(t))}),n},n.prototype.setDefaultEdgeLabel=function(e){return t.isFunction(e)||(e=t.constant(e)),this._defaultEdgeLabelFn=e,this},n.prototype.edgeCount=function(){return this._edgeCount},n.prototype.edges=function(){return t.values(this._edgeObjs)},n.prototype.setPath=function(e,n){var r=this,i=arguments;return t.reduce(e,function(t,e){return i.length>1?r.setEdge(t,e,n):r.setEdge(t,e),e}),this},n.prototype.setEdge=function(){var e,n,i,o,u=!1,a=arguments[0];"object"==typeof a&&null!==a&&"v"in a?(e=a.v,n=a.w,i=a.name,2===arguments.length&&(o=arguments[1],u=!0)):(e=a,n=arguments[1],i=arguments[3],arguments.length>2&&(o=arguments[2],u=!0)),e=""+e,n=""+n,t.isUndefined(i)||(i=""+i);var h=s(this._isDirected,e,n,i);if(t.has(this._edgeLabels,h))return u&&(this._edgeLabels[h]=o),this;if(!t.isUndefined(i)&&!this._isMultigraph)throw new Error("Cannot set a named edge when isMultigraph = false");this.setNode(e),this.setNode(n),this._edgeLabels[h]=u?o:this._defaultEdgeLabelFn(e,n,i);var c=function(t,e,n,r){var i=""+e,s=""+n;if(!t&&i>s){var o=i;i=s,s=o}var u={v:i,w:s};r&&(u.name=r);return u}(this._isDirected,e,n,i);return e=c.v,n=c.w,Object.freeze(c),this._edgeObjs[h]=c,r(this._preds[n],e),r(this._sucs[e],n),this._in[n][h]=c,this._out[e][h]=c,this._edgeCount++,this},n.prototype.edge=function(t,e,n){var r=1===arguments.length?o(this._isDirected,arguments[0]):s(this._isDirected,t,e,n);return this._edgeLabels[r]},n.prototype.hasEdge=function(e,n,r){var i=1===arguments.length?o(this._isDirected,arguments[0]):s(this._isDirected,e,n,r);return t.has(this._edgeLabels,i)},n.prototype.removeEdge=function(t,e,n){var r=1===arguments.length?o(this._isDirected,arguments[0]):s(this._isDirected,t,e,n),u=this._edgeObjs[r];return u&&(t=u.v,e=u.w,delete this._edgeLabels[r],delete this._edgeObjs[r],i(this._preds[e],t),i(this._sucs[t],e),delete this._in[e][r],delete this._out[t][r],this._edgeCount--),this},n.prototype.inEdges=function(e,n){var r=this._in[e];if(r){var i=t.values(r);return n?t.filter(i,function(t){return t.v===n}):i}},n.prototype.outEdges=function(e,n){var r=this._out[e];if(r){var i=t.values(r);return n?t.filter(i,function(t){return t.w===n}):i}},n.prototype.nodeEdges=function(t,e){var n=this.inEdges(t,e);if(n)return n.concat(this.outEdges(t,e))},m}function st(){if(I)return C;I=1;var t=rt(),e=it();function n(e){return t.map(e.nodes(),function(n){var r=e.node(n),i=e.parent(n),s={v:n};return t.isUndefined(r)||(s.value=r),t.isUndefined(i)||(s.parent=i),s})}function r(e){return t.map(e.edges(),function(n){var r=e.edge(n),i={v:n.v,w:n.w};return t.isUndefined(n.name)||(i.name=n.name),t.isUndefined(r)||(i.value=r),i})}return C={write:function(e){var i={options:{directed:e.isDirected(),multigraph:e.isMultigraph(),compound:e.isCompound()},nodes:n(e),edges:r(e)};t.isUndefined(e.graph())||(i.value=t.clone(e.graph()));return i},read:function(n){var r=new e(n.options).setGraph(n.value);return t.each(n.nodes,function(t){r.setNode(t.v,t.value),t.parent&&r.setParent(t.v,t.parent)}),t.each(n.edges,function(t){r.setEdge({v:t.v,w:t.w,name:t.name},t.value)}),r}}}function ot(){if(j)return L;j=1;var t=rt();return L=function(e){var n,r={},i=[];function s(i){t.has(r,i)||(r[i]=!0,n.push(i),t.each(e.successors(i),s),t.each(e.predecessors(i),s))}return t.each(e.nodes(),function(t){n=[],s(t),n.length&&i.push(n)}),i}}function ut(){if(F)return D;F=1;var t=rt();function e(){this._arr=[],this._keyIndices={}}return D=e,e.prototype.size=function(){return this._arr.length},e.prototype.keys=function(){return this._arr.map(function(t){return t.key})},e.prototype.has=function(e){return t.has(this._keyIndices,e)},e.prototype.priority=function(t){var e=this._keyIndices[t];if(void 0!==e)return this._arr[e].priority},e.prototype.min=function(){if(0===this.size())throw new Error("Queue underflow");return this._arr[0].key},e.prototype.add=function(e,n){var r=this._keyIndices;if(e=String(e),!t.has(r,e)){var i=this._arr,s=i.length;return r[e]=s,i.push({key:e,priority:n}),this._decrease(s),!0}return!1},e.prototype.removeMin=function(){this._swap(0,this._arr.length-1);var t=this._arr.pop();return delete this._keyIndices[t.key],this._heapify(0),t.key},e.prototype.decrease=function(t,e){var n=this._keyIndices[t];if(e>this._arr[n].priority)throw new Error("New priority is greater than current priority. Key: "+t+" Old: "+this._arr[n].priority+" New: "+e);this._arr[n].priority=e,this._decrease(n)},e.prototype._heapify=function(t){var e=this._arr,n=2*t,r=n+1,i=t;n<e.length&&(i=e[n].priority<e[i].priority?n:i,r<e.length&&(i=e[r].priority<e[i].priority?r:i),i!==t&&(this._swap(t,i),this._heapify(i)))},e.prototype._decrease=function(t){for(var e,n=this._arr,r=n[t].priority;0!==t&&!(n[e=t>>1].priority<r);)this._swap(t,e),t=e},e.prototype._swap=function(t,e){var n=this._arr,r=this._keyIndices,i=n[t],s=n[e];n[t]=s,n[e]=i,r[s.key]=t,r[i.key]=e},D}function at(){if(M)return O;M=1;var t=rt(),e=ut();O=function(t,r,i,s){return function(t,n,r,i){var s,o,u={},a=new e,h=function(t){var e=t.v!==s?t.v:t.w,n=u[e],i=r(t),h=o.distance+i;if(i<0)throw new Error("dijkstra does not allow negative edge weights. Bad edge: "+t+" Weight: "+i);h<n.distance&&(n.distance=h,n.predecessor=s,a.decrease(e,h))};t.nodes().forEach(function(t){var e=t===n?0:Number.POSITIVE_INFINITY;u[t]={distance:e},a.add(t,e)});for(;a.size()>0&&(s=a.removeMin(),(o=u[s]).distance!==Number.POSITIVE_INFINITY);)i(s).forEach(h);return u}(t,String(r),i||n,s||function(e){return t.outEdges(e)})};var n=t.constant(1);return O}function ht(){if(U)return P;U=1;var t=at(),e=rt();return P=function(n,r,i){return e.transform(n.nodes(),function(e,s){e[s]=t(n,s,r,i)},{})}}function ct(){if(T)return S;T=1;var t=rt();return S=function(e){var n=0,r=[],i={},s=[];function o(u){var a=i[u]={onStack:!0,lowlink:n,index:n++};if(r.push(u),e.successors(u).forEach(function(e){t.has(i,e)?i[e].onStack&&(a.lowlink=Math.min(a.lowlink,i[e].index)):(o(e),a.lowlink=Math.min(a.lowlink,i[e].lowlink))}),a.lowlink===a.index){var h,c=[];do{h=r.pop(),i[h].onStack=!1,c.push(h)}while(u!==h);s.push(c)}}return e.nodes().forEach(function(e){t.has(i,e)||o(e)}),s}}function dt(){if(z)return x;z=1;var t=rt(),e=ct();return x=function(n){return t.filter(e(n),function(t){return t.length>1||1===t.length&&n.hasEdge(t[0],t[0])})}}function ft(){if(A)return G;A=1;var t=rt();G=function(t,n,r){return function(t,e,n){var r={},i=t.nodes();return i.forEach(function(t){r[t]={},r[t][t]={distance:0},i.forEach(function(e){t!==e&&(r[t][e]={distance:Number.POSITIVE_INFINITY})}),n(t).forEach(function(n){var i=n.v===t?n.w:n.v,s=e(n);r[t][i]={distance:s,predecessor:t}})}),i.forEach(function(t){var e=r[t];i.forEach(function(n){var s=r[n];i.forEach(function(n){var r=s[t],i=e[n],o=s[n],u=r.distance+i.distance;u<o.distance&&(o.distance=u,o.predecessor=i.predecessor)})})}),r}(t,n||e,r||function(e){return t.outEdges(e)})};var e=t.constant(1);return G}function pt(){if(Y)return V;Y=1;var t=rt();function e(e){var r={},i={},s=[];if(t.each(e.sinks(),function o(u){if(t.has(i,u))throw new n;t.has(r,u)||(i[u]=!0,r[u]=!0,t.each(e.predecessors(u),o),delete i[u],s.push(u))}),t.size(r)!==e.nodeCount())throw new n;return s}function n(){}return V=e,e.CycleException=n,n.prototype=new Error,V}function _t(){if(B)return W;B=1;var t=pt();return W=function(e){try{t(e)}catch(n){if(n instanceof t.CycleException)return!1;throw n}return!0}}function lt(){if(Q)return K;Q=1;var t=rt();function e(n,r,i,s,o,u){t.has(s,r)||(s[r]=!0,i||u.push(r),t.each(o(r),function(t){e(n,t,i,s,o,u)}),i&&u.push(r))}return K=function(n,r,i){t.isArray(r)||(r=[r]);var s=(n.isDirected()?n.successors:n.neighbors).bind(n),o=[],u={};return t.each(r,function(t){if(!n.hasNode(t))throw new Error("Graph does not have node: "+t);e(n,t,"post"===i,u,s,o)}),o}}function vt(){if(q)return $;q=1;var t=lt();return $=function(e,n){return t(e,n,"post")}}function yt(){if(J)return H;J=1;var t=lt();return H=function(e,n){return t(e,n,"pre")}}function gt(){if(X)return R;X=1;var t=rt(),e=it(),n=ut();return R=function(r,i){var s,o=new e,u={},a=new n;function h(t){var e=t.v===s?t.w:t.v,n=a.priority(e);if(void 0!==n){var r=i(t);r<n&&(u[e]=s,a.decrease(e,r))}}if(0===r.nodeCount())return o;t.each(r.nodes(),function(t){a.add(t,Number.POSITIVE_INFINITY),o.setNode(t)}),a.decrease(r.nodes()[0],0);var c=!1;for(;a.size()>0;){if(s=a.removeMin(),t.has(u,s))o.setEdge(s,u[s]);else{if(c)throw new Error("Input graph is not connected: "+r);c=!0}r.nodeEdges(s).forEach(h)}return o}}function mt(){if(nt)return et;nt=1;var t=b?N:(b=1,N={Graph:it(),version:k?E:(k=1,E="2.1.8")});return et={Graph:t.Graph,json:st(),alg:tt?Z:(tt=1,Z={components:ot(),dijkstra:at(),dijkstraAll:ht(),findCycles:dt(),floydWarshall:ft(),isAcyclic:_t(),postorder:vt(),preorder:yt(),prim:gt(),tarjan:ct(),topsort:pt()}),version:t.version}}export{mt as r};
|
