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