mirror of
https://github.com/anvaka/ngraph.path.git
synced 2026-01-18 15:13:12 +00:00
3 lines
7.5 KiB
JavaScript
3 lines
7.5 KiB
JavaScript
(function(Y,E){typeof exports=="object"&&typeof module<"u"?E(exports):typeof define=="function"&&define.amd?define(["exports"],E):(Y=typeof globalThis<"u"?globalThis:Y||self,E(Y.ngraphPath={}))})(this,(function(Y){"use strict";function E(e,t){if(!new.target)return new E(e,t);if(Array.isArray(e)||(t=e,e=[]),t=t||{},this.data=e||[],this.length=this.data.length,this.compare=t.compare||U,this.setNodeId=t.setNodeId||Q,this.length>0)for(var n=this.length>>1;n>=0;n--)this._down(n);if(t.setNodeId)for(var n=0;n<this.length;++n)this.setNodeId(this.data[n],n)}function Q(){}function U(e,t){return e-t}E.prototype={push:function(e){this.data.push(e),this.setNodeId(e,this.length),this.length++,this._up(this.length-1)},pop:function(){if(this.length!==0){var e=this.data[0];return this.length--,this.length>0&&(this.data[0]=this.data[this.length],this.setNodeId(this.data[0],0),this._down(0)),this.data.pop(),e}},peek:function(){return this.data[0]},updateItem:function(e){this._down(e),this._up(e)},_up:function(e){for(var t=this.data,n=this.compare,d=this.setNodeId,o=t[e];e>0;){var r=e-1>>1,s=t[r];if(n(o,s)>=0)break;t[e]=s,d(s,e),e=r}t[e]=o,d(o,e)},_down:function(e){for(var t=this.data,n=this.compare,d=this.length>>1,o=t[e],r=this.setNodeId;e<d;){var s=(e<<1)+1,w=s+1,N=t[s];if(w<this.length&&n(t[w],N)<0&&(s=w,N=t[w]),n(N,o)>=0)break;t[e]=N,r(N,e),e=s}t[e]=o,r(o,e)}};function W(e){this.node=e,this.parent=null,this.closed=!1,this.open=0,this.distanceToSource=Number.POSITIVE_INFINITY,this.fScore=Number.POSITIVE_INFINITY,this.heapIndex=-1}function J(){var e=0,t=[];return{createNewState:d,reset:n};function n(){e=0}function d(o){var r=t[e];return r?(r.node=o,r.parent=null,r.closed=!1,r.open=0,r.distanceToSource=Number.POSITIVE_INFINITY,r.fScore=Number.POSITIVE_INFINITY,r.heapIndex=-1):(r=new W(o),t[e]=r),e++,r}}function L(e,t){var n=e.x-t.x,d=e.y-t.y;return Math.sqrt(n*n+d*d)}function $(e,t){var n=e.x-t.x,d=e.y-t.y;return Math.abs(n)+Math.abs(d)}const K=[];typeof Object.freeze=="function"&&Object.freeze(K);const u={heuristic:X,distance:Z,blocked:ee,compareFScore:te,NO_PATH:K,setHeapIndex:re,setH1:ae,setH2:oe,compareF1Score:ne,compareF2Score:ie};function X(){return 0}function Z(){return 1}function ee(){return!1}function te(e,t){var n=e.fScore-t.fScore;return n}function re(e,t){e.heapIndex=t}function ne(e,t){return e.f1-t.f1}function ie(e,t){return e.f2-t.f2}function ae(e,t){e.h1=t}function oe(e,t){e.h2=t}var de=u.NO_PATH;function D(e,t){t=t||{};var n=t.oriented,d=t.blocked;d||(d=u.blocked);var o=t.heuristic;o||(o=u.heuristic);var r=t.distance;r||(r=u.distance);var s=J();return{find:w};function w(N,y){var g=e.getNode(N);if(!g)throw new Error("fromId is not defined in this graph: "+N);var I=e.getNode(y);if(!I)throw new Error("toId is not defined in this graph: "+y);s.reset();var H=new Map,V=new E({compare:u.compareFScore,setNodeId:u.setHeapIndex}),m=s.createNewState(g);H.set(N,m),m.fScore=o(g,I),m.distanceToSource=0,V.push(m),m.open=1;for(var h;V.length>0;){if(h=V.pop(),ce(h,I))return fe(h);h.closed=!0,e.forEachLinkedNode(h.node.id,S,n)}return de;function S(v,b){var c=H.get(v.id);if(c||(c=s.createNewState(v),H.set(v.id,c)),!c.closed&&(c.open===0&&(V.push(c),c.open=1),!d(v,h.node,b))){var _=h.distanceToSource+r(v,h.node,b);_>=c.distanceToSource||(c.parent=h,c.distanceToSource=_,c.fScore=_+o(c.node,I),V.updateItem(c.heapIndex))}}}}D.l2=L,D.l1=$;function ce(e,t){return e.node===t}function fe(e){for(var t=[e.node],n=e.parent;n;)t.push(n.node),n=n.parent;return t}var B=1,q=2,ue=u.NO_PATH;function C(e,t){t=t||{};var n=t.oriented,d=t.blocked;d||(d=u.blocked);var o=t.heuristic;o||(o=u.heuristic);var r=t.distance;r||(r=u.distance);var s=J();return{find:w};function w(N,y){var g=e.getNode(N);if(!g)throw new Error("fromId is not defined in this graph: "+N);var I=e.getNode(y);if(!I)throw new Error("toId is not defined in this graph: "+y);if(g===I)return[g];s.reset();var H=n?z:f,V=new Map,m=new E({compare:u.compareFScore,setNodeId:u.setHeapIndex}),h=new E({compare:u.compareFScore,setNodeId:u.setHeapIndex}),S=s.createNewState(g);V.set(N,S),S.fScore=o(g,I),S.distanceToSource=0,m.push(S),S.open=B;var v=s.createNewState(I);v.fScore=o(I,g),v.distanceToSource=0,h.push(v),v.open=q;for(var b=Number.POSITIVE_INFINITY,c,_,x=m,O=B;m.length>0&&h.length>0;){m.length<h.length?(O=B,x=m):(O=q,x=h);var P=x.pop();if(P.closed=!0,!(P.distanceToSource>b)&&(e.forEachLinkedNode(P.node.id,H),c&&_))return R(c,_)}return ue;function f(T,p){return M(T,p,P)}function z(T,p){if(O===B){if(p.fromId===P.node.id)return M(T,p,P)}else if(O===q&&p.toId===P.node.id)return M(T,p,P)}function G(T){var p=T.open;return!!(p&&p!==O)}function R(T,p){for(var F=[],i=T;i;)F.push(i.node),i=i.parent;for(var l=p;l;)F.unshift(l.node),l=l.parent;return F}function M(T,p,F){var i=V.get(T.id);if(i||(i=s.createNewState(T),V.set(T.id,i)),!i.closed&&!d(i.node,F.node,p)){if(G(i)){var l=i.distanceToSource+F.distanceToSource;l<b&&(c=i,_=F,b=l);return}var a=F.distanceToSource+r(i.node,F.node,p);if(!(a>=i.distanceToSource)){var k=O===B?I:g,A=a+o(i.node,k);A>=b||(i.fScore=A,i.open===0&&(x.push(i),x.updateItem(i.heapIndex),i.open=O),i.parent=F,i.distanceToSource=a)}}}}}C.l2=L,C.l1=$;function se(e){this.node=e,this.p1=null,this.p2=null,this.closed=!1,this.g1=Number.POSITIVE_INFINITY,this.g2=Number.POSITIVE_INFINITY,this.f1=Number.POSITIVE_INFINITY,this.f2=Number.POSITIVE_INFINITY,this.h1=-1,this.h2=-1}function he(){var e=0,t=[];return{createNewState:d,reset:n};function n(){e=0}function d(o){var r=t[e];return r?(r.node=o,r.p1=null,r.p2=null,r.closed=!1,r.g1=Number.POSITIVE_INFINITY,r.g2=Number.POSITIVE_INFINITY,r.f1=Number.POSITIVE_INFINITY,r.f2=Number.POSITIVE_INFINITY,r.h1=-1,r.h2=-1):(r=new se(o),t[e]=r),e++,r}}var ve=u.NO_PATH;function j(e,t){t=t||{};var n=t.oriented,d=t.quitFast,o=t.blocked;o||(o=u.blocked);var r=t.heuristic;r||(r=u.heuristic);var s=t.distance;s||(s=u.distance);var w=he();return{find:N};function N(y,g){var I=e.getNode(y);if(!I)throw new Error("fromId is not defined in this graph: "+y);var H=e.getNode(g);if(!H)throw new Error("toId is not defined in this graph: "+g);w.reset();var V=n?F:M,m=n?p:T,h=new Map,S=new E({compare:u.compareF1Score,setNodeId:u.setH1}),v=new E({compare:u.compareF2Score,setNodeId:u.setH2}),b,c=Number.POSITIVE_INFINITY,_=w.createNewState(I);h.set(y,_),_.g1=0;var x=r(I,H);_.f1=x,S.push(_);var O=w.createNewState(H);h.set(g,O),O.g2=0;var P=x;O.f2=P,v.push(O);for(var f;v.length&&S.length&&(S.length<v.length?G():R(),!(d&&b)););var z=le(b);return z;function G(){f=S.pop(),!f.closed&&(f.closed=!0,f.f1<c&&f.g1+P-r(I,f.node)<c&&e.forEachLinkedNode(f.node.id,V),S.length>0&&(x=S.peek().f1))}function R(){f=v.pop(),!f.closed&&(f.closed=!0,f.f2<c&&f.g2+x-r(f.node,H)<c&&e.forEachLinkedNode(f.node.id,m),v.length>0&&(P=v.peek().f2))}function M(i,l){var a=h.get(i.id);if(a||(a=w.createNewState(i),h.set(i.id,a)),!a.closed&&!o(f.node,i,l)){var k=f.g1+s(f.node,i,l);k<a.g1&&(a.g1=k,a.f1=k+r(a.node,H),a.p1=f,a.h1<0?S.push(a):S.updateItem(a.h1));var A=a.g1+a.g2;A<c&&(c=A,b=a)}}function T(i,l){var a=h.get(i.id);if(a||(a=w.createNewState(i),h.set(i.id,a)),!a.closed&&!o(f.node,i,l)){var k=f.g2+s(f.node,i,l);k<a.g2&&(a.g2=k,a.f2=k+r(I,a.node),a.p2=f,a.h2<0?v.push(a):v.updateItem(a.h2));var A=a.g1+a.g2;A<c&&(c=A,b=a)}}function p(i,l){if(l.toId===f.node.id)return T(i,l)}function F(i,l){if(l.fromId===f.node.id)return M(i,l)}}}j.l2=L,j.l1=$;function le(e){if(!e)return ve;for(var t=[e.node],n=e.p1;n;)t.push(n.node),n=n.p1;for(var d=e.p2;d;)t.unshift(d.node),d=d.p2;return t}const Ie={aStar:D,aGreedy:C,nba:j};Y.aGreedy=C,Y.aStar=D,Y.default=Ie,Y.nba=j,Object.defineProperties(Y,{__esModule:{value:!0},[Symbol.toStringTag]:{value:"Module"}})}));
|
|
//# sourceMappingURL=ngraph.path.umd.js.map
|