import{a as b}from"./chunk-6IOWLTMD.js";import{D as E,E as F,F as y,G as L,H as G,J as V,K as x,L as R,N as Er,P as I,T as B,U as Q,d as g,f as vr,h as K,i as _r,k as j,n as f,p as N,q as Y,s as v,u as wr,v as br,x as W,z as O}from"./chunk-WYMAA4MH.js";import{O as M,T as D,z as mr}from"./chunk-24JW6VB3.js";function k(r,e,n,t){var o;do o=B(t);while(r.hasNode(o));return n.dummy=e,r.setNode(o,n),o}function yr(r){var e=new b().setGraph(r.graph());return f(r.nodes(),function(n){e.setNode(n,r.node(n))}),f(r.edges(),function(n){var t=e.edge(n.v,n.w)||{weight:0,minlen:1},o=r.edge(n);e.setEdge(n.v,n.w,{weight:t.weight+o.weight,minlen:Math.max(t.minlen,o.minlen)})}),e}function q(r){var e=new b({multigraph:r.isMultigraph()}).setGraph(r.graph());return f(r.nodes(),function(n){r.children(n).length||e.setNode(n,r.node(n))}),f(r.edges(),function(n){e.setEdge(n,r.edge(n))}),e}function Z(r,e){var n=r.x,t=r.y,o=e.x-n,a=e.y-t,i=r.width/2,s=r.height/2;if(!o&&!a)throw new Error("Not possible to find intersection inside of the rectangle");var u,d;return Math.abs(a)*i>Math.abs(o)*s?(a<0&&(s=-s),u=s*o/a,d=s):(o<0&&(i=-i),u=i,d=i*a/o),{x:n+u,y:t+d}}function P(r){var e=v(x(rr(r)+1),function(){return[]});return f(r.nodes(),function(n){var t=r.node(n),o=t.rank;E(o)||(e[o][t.order]=n)}),e}function xr(r){var e=L(v(r.nodes(),function(n){return r.node(n).rank}));f(r.nodes(),function(n){var t=r.node(n);W(t,"rank")&&(t.rank-=e)})}function kr(r){var e=L(v(r.nodes(),function(a){return r.node(a).rank})),n=[];f(r.nodes(),function(a){var i=r.node(a).rank-e;n[i]||(n[i]=[]),n[i].push(a)});var t=0,o=r.graph().nodeRankFactor;f(n,function(a,i){E(a)&&i%o!==0?--t:t&&f(a,function(s){r.node(s).rank+=t})})}function $(r,e,n,t){var o={width:0,height:0};return arguments.length>=4&&(o.rank=n,o.order=t),k(r,"border",o,e)}function rr(r){return y(v(r.nodes(),function(e){var n=r.node(e).rank;if(!E(n))return n}))}function gr(r,e){var n={lhs:[],rhs:[]};return f(r,function(t){e(t)?n.lhs.push(t):n.rhs.push(t)}),n}function Nr(r,e){var n=K();try{return e()}finally{console.log(r+" time: "+(K()-n)+"ms")}}function Ir(r,e){return e()}function Lr(r){function e(n){var t=r.children(n),o=r.node(n);if(t.length&&f(t,e),Object.prototype.hasOwnProperty.call(o,"minRank")){o.borderLeft=[],o.borderRight=[];for(var a=o.minRank,i=o.maxRank+1;a<i;++a)Or(r,"borderLeft","_bl",n,o,a),Or(r,"borderRight","_br",n,o,a)}}f(r.children(),e)}function Or(r,e,n,t,o,a){var i={width:0,height:0,rank:a,borderType:e},s=o[e][a-1],u=k(r,"border",i,n);o[e][a]=u,r.setParent(u,t),s&&r.setEdge(s,u,{weight:1})}function Cr(r){var e=r.graph().rankdir.toLowerCase();(e==="lr"||e==="rl")&&jr(r)}function Tr(r){var e=r.graph().rankdir.toLowerCase();(e==="bt"||e==="rl")&&le(r),(e==="lr"||e==="rl")&&(pe(r),jr(r))}function jr(r){f(r.nodes(),function(e){Pr(r.node(e))}),f(r.edges(),function(e){Pr(r.edge(e))})}function Pr(r){var e=r.width;r.width=r.height,r.height=e}function le(r){f(r.nodes(),function(e){er(r.node(e))}),f(r.edges(),function(e){var n=r.edge(e);f(n.points,er),Object.prototype.hasOwnProperty.call(n,"y")&&er(n)})}function er(r){r.y=-r.y}function pe(r){f(r.nodes(),function(e){nr(r.node(e))}),f(r.edges(),function(e){var n=r.edge(e);f(n.points,nr),Object.prototype.hasOwnProperty.call(n,"x")&&nr(n)})}function nr(r){var e=r.x;r.x=r.y,r.y=e}var X=class{constructor(){var e={};e._next=e._prev=e,this._sentinel=e}dequeue(){var e=this._sentinel,n=e._prev;if(n!==e)return Rr(n),n}enqueue(e){var n=this._sentinel;e._prev&&e._next&&Rr(e),e._next=n._next,n._next._prev=e,n._next=e,e._prev=n}toString(){for(var e=[],n=this._sentinel,t=n._prev;t!==n;)e.push(JSON.stringify(t,ve)),t=t._prev;return"["+e.join(", ")+"]"}};function Rr(r){r._prev._next=r._next,r._next._prev=r._prev,delete r._next,delete r._prev}function ve(r,e){if(r!=="_next"&&r!=="_prev")return e}var _e=M(1);function Sr(r,e){if(r.nodeCount()<=1)return[];var n=be(r,e||_e),t=we(n.graph,n.buckets,n.zeroIdx);return g(v(t,function(o){return r.outEdges(o.v,o.w)}))}function we(r,e,n){for(var t=[],o=e[e.length-1],a=e[0],i;r.nodeCount();){for(;i=a.dequeue();)tr(r,e,n,i);for(;i=o.dequeue();)tr(r,e,n,i);if(r.nodeCount()){for(var s=e.length-2;s>0;--s)if(i=e[s].dequeue(),i){t=t.concat(tr(r,e,n,i,!0));break}}}return t}function tr(r,e,n,t,o){var a=o?[]:void 0;return f(r.inEdges(t.v),function(i){var s=r.edge(i),u=r.node(i.v);o&&a.push({v:i.v,w:i.w}),u.out-=s,or(e,n,u)}),f(r.outEdges(t.v),function(i){var s=r.edge(i),u=i.w,d=r.node(u);d.in-=s,or(e,n,d)}),r.removeNode(t.v),a}function be(r,e){var n=new b,t=0,o=0;f(r.nodes(),function(s){n.setNode(s,{v:s,in:0,out:0})}),f(r.edges(),function(s){var u=n.edge(s.v,s.w)||0,d=e(s),c=u+d;n.setEdge(s.v,s.w,c),o=Math.max(o,n.node(s.v).out+=d),t=Math.max(t,n.node(s.w).in+=d)});var a=x(o+t+3).map(function(){return new X}),i=t+1;return f(n.nodes(),function(s){or(a,i,n.node(s))}),{graph:n,buckets:a,zeroIdx:i}}function or(r,e,n){n.out?n.in?r[n.out-n.in+e].enqueue(n):r[r.length-1].enqueue(n):r[0].enqueue(n)}function Mr(r){var e=r.graph().acyclicer==="greedy"?Sr(r,n(r)):Ee(r);f(e,function(t){var o=r.edge(t);r.removeEdge(t),o.forwardName=t.name,o.reversed=!0,r.setEdge(t.w,t.v,o,B("rev"))});function n(t){return function(o){return t.edge(o).weight}}}function Ee(r){var e=[],n={},t={};function o(a){Object.prototype.hasOwnProperty.call(t,a)||(t[a]=!0,n[a]=!0,f(r.outEdges(a),function(i){Object.prototype.hasOwnProperty.call(n,i.w)?e.push(i):o(i.w)}),delete n[a])}return f(r.nodes(),o),e}function Fr(r){f(r.edges(),function(e){var n=r.edge(e);if(n.reversed){r.removeEdge(e);var t=n.forwardName;delete n.reversed,delete n.forwardName,r.setEdge(e.w,e.v,n,t)}})}function Vr(r){r.graph().dummyChains=[],f(r.edges(),function(e){ye(r,e)})}function ye(r,e){var n=e.v,t=r.node(n).rank,o=e.w,a=r.node(o).rank,i=e.name,s=r.edge(e),u=s.labelRank;if(a!==t+1){r.removeEdge(e);var d=void 0,c,h;for(h=0,++t;t<a;++h,++t)s.points=[],d={width:0,height:0,edgeLabel:s,edgeObj:e,rank:t},c=k(r,"edge",d,"_d"),t===u&&(d.width=s.width,d.height=s.height,d.dummy="edge-label",d.labelpos=s.labelpos),r.setEdge(n,c,{weight:s.weight},i),h===0&&r.graph().dummyChains.push(c),n=c;r.setEdge(n,o,{weight:s.weight},i)}}function Br(r){f(r.graph().dummyChains,function(e){var n=r.node(e),t=n.edgeLabel,o;for(r.setEdge(n.edgeObj,t);n.dummy;)o=r.successors(e)[0],r.removeNode(e),t.points.push({x:n.x,y:n.y}),n.dummy==="edge-label"&&(t.x=n.x,t.y=n.y,t.width=n.width,t.height=n.height),e=o,n=r.node(e)})}function z(r){var e={};function n(t){var o=r.node(t);if(Object.prototype.hasOwnProperty.call(e,t))return o.rank;e[t]=!0;var a=L(v(r.outEdges(t),function(i){return n(i.w)-r.edge(i).minlen}));return(a===Number.POSITIVE_INFINITY||a===void 0||a===null)&&(a=0),o.rank=a}f(r.sources(),n)}function S(r,e){return r.node(e.w).rank-r.node(e.v).rank-r.edge(e).minlen}function H(r){var e=new b({directed:!1}),n=r.nodes()[0],t=r.nodeCount();e.setNode(n,{});for(var o,a;xe(e,r)<t;)o=ke(e,r),a=e.hasNode(o.v)?S(r,o):-S(r,o),ge(e,r,a);return e}function xe(r,e){function n(t){f(e.nodeEdges(t),function(o){var a=o.v,i=t===a?o.w:a;!r.hasNode(i)&&!S(e,o)&&(r.setNode(i,{}),r.setEdge(t,i,{}),n(i))})}return f(r.nodes(),n),r.nodeCount()}function ke(r,e){return G(e.edges(),function(n){if(r.hasNode(n.v)!==r.hasNode(n.w))return S(e,n)})}function ge(r,e,n){f(r.nodes(),function(t){e.node(t).rank+=n})}var Wn=M(1);var Zn=M(1);ar.CycleException=U;function ar(r){var e={},n={},t=[];function o(a){if(Object.prototype.hasOwnProperty.call(n,a))throw new U;Object.prototype.hasOwnProperty.call(e,a)||(n[a]=!0,e[a]=!0,f(r.predecessors(a),o),delete n[a],t.push(a))}if(f(r.sinks(),o),Er(e)!==r.nodeCount())throw new U;return t}function U(){}U.prototype=new Error;function J(r,e,n){mr(e)||(e=[e]);var t=(r.isDirected()?r.successors:r.neighbors).bind(r),o=[],a={};return f(e,function(i){if(!r.hasNode(i))throw new Error("Graph does not have node: "+i);Dr(r,i,n==="post",a,t,o)}),o}function Dr(r,e,n,t,o,a){Object.prototype.hasOwnProperty.call(t,e)||(t[e]=!0,n||a.push(e),f(o(e),function(i){Dr(r,i,n,t,o,a)}),n&&a.push(e))}function ir(r,e){return J(r,e,"post")}function sr(r,e){return J(r,e,"pre")}T.initLowLimValues=ur;T.initCutValues=fr;T.calcCutValue=zr;T.leaveEdge=Wr;T.enterEdge=qr;T.exchangeEdges=Xr;function T(r){r=yr(r),z(r);var e=H(r);ur(e),fr(e,r);for(var n,t;n=Wr(e);)t=qr(e,r,n),Xr(e,r,n,t)}function fr(r,e){var n=ir(r,r.nodes());n=n.slice(0,n.length-1),f(n,function(t){Pe(r,e,t)})}function Pe(r,e,n){var t=r.node(n),o=t.parent;r.edge(n,o).cutvalue=zr(r,e,n)}function zr(r,e,n){var t=r.node(n),o=t.parent,a=!0,i=e.edge(n,o),s=0;return i||(a=!1,i=e.edge(o,n)),s=i.weight,f(e.nodeEdges(n),function(u){var d=u.v===n,c=d?u.w:u.v;if(c!==o){var h=d===a,l=e.edge(u).weight;if(s+=h?l:-l,Te(r,n,c)){var p=r.edge(n,c).cutvalue;s+=h?-p:p}}}),s}function ur(r,e){arguments.length<2&&(e=r.nodes()[0]),Ur(r,{},1,e)}function Ur(r,e,n,t,o){var a=n,i=r.node(t);return e[t]=!0,f(r.neighbors(t),function(s){Object.prototype.hasOwnProperty.call(e,s)||(n=Ur(r,e,n,s,t))}),i.low=a,i.lim=n++,o?i.parent=o:delete i.parent,n}function Wr(r){return Y(r.edges(),function(e){return r.edge(e).cutvalue<0})}function qr(r,e,n){var t=n.v,o=n.w;e.hasEdge(t,o)||(t=n.w,o=n.v);var a=r.node(t),i=r.node(o),s=a,u=!1;a.lim>i.lim&&(s=i,u=!0);var d=N(e.edges(),function(c){return u===Yr(r,r.node(c.v),s)&&u!==Yr(r,r.node(c.w),s)});return G(d,function(c){return S(e,c)})}function Xr(r,e,n,t){var o=n.v,a=n.w;r.removeEdge(o,a),r.setEdge(t.v,t.w,{}),ur(r),fr(r,e),Ce(r,e)}function Ce(r,e){var n=Y(r.nodes(),function(o){return!e.node(o).parent}),t=sr(r,n);t=t.slice(1),f(t,function(o){var a=r.node(o).parent,i=e.edge(o,a),s=!1;i||(i=e.edge(a,o),s=!0),e.node(o).rank=e.node(a).rank+(s?i.minlen:-i.minlen)})}function Te(r,e,n){return r.hasEdge(e,n)}function Yr(r,e,n){return n.low<=e.lim&&e.lim<=n.lim}function dr(r){switch(r.graph().ranker){case"network-simplex":Hr(r);break;case"tight-tree":Re(r);break;case"longest-path":je(r);break;default:Hr(r)}}var je=z;function Re(r){z(r),H(r)}function Hr(r){T(r)}function Jr(r){var e=k(r,"root",{},"_root"),n=Se(r),t=y(O(n))-1,o=2*t+1;r.graph().nestingRoot=e,f(r.edges(),function(i){r.edge(i).minlen*=o});var a=Me(r)+1;f(r.children(),function(i){Kr(r,e,o,a,t,n,i)}),r.graph().nodeRankFactor=o}function Kr(r,e,n,t,o,a,i){var s=r.children(i);if(!s.length){i!==e&&r.setEdge(e,i,{weight:0,minlen:n});return}var u=$(r,"_bt"),d=$(r,"_bb"),c=r.node(i);r.setParent(u,i),c.borderTop=u,r.setParent(d,i),c.borderBottom=d,f(s,function(h){Kr(r,e,n,t,o,a,h);var l=r.node(h),p=l.borderTop?l.borderTop:h,m=l.borderBottom?l.borderBottom:h,w=l.borderTop?t:2*t,A=p!==m?1:o-a[i]+1;r.setEdge(u,p,{weight:w,minlen:A,nestingEdge:!0}),r.setEdge(m,d,{weight:w,minlen:A,nestingEdge:!0})}),r.parent(i)||r.setEdge(e,u,{weight:0,minlen:o+a[i]})}function Se(r){var e={};function n(t,o){var a=r.children(t);a&&a.length&&f(a,function(i){n(i,o+1)}),e[t]=o}return f(r.children(),function(t){n(t,1)}),e}function Me(r){return R(r.edges(),function(e,n){return e+r.edge(n).weight},0)}function Qr(r){var e=r.graph();r.removeNode(e.nestingRoot),delete e.nestingRoot,f(r.edges(),function(n){var t=r.edge(n);t.nestingEdge&&r.removeEdge(n)})}function Zr(r,e,n){var t={},o;f(n,function(a){for(var i=r.parent(a),s,u;i;){if(s=r.parent(i),s?(u=t[s],t[s]=i):(u=o,o=i),u&&u!==i){e.setEdge(u,i);return}i=s}})}function $r(r,e,n){var t=Ge(r),o=new b({compound:!0}).setGraph({root:t}).setDefaultNodeLabel(function(a){return r.node(a)});return f(r.nodes(),function(a){var i=r.node(a),s=r.parent(a);(i.rank===e||i.minRank<=e&&e<=i.maxRank)&&(o.setNode(a),o.setParent(a,s||t),f(r[n](a),function(u){var d=u.v===a?u.w:u.v,c=o.edge(d,a),h=E(c)?0:c.weight;o.setEdge(d,a,{weight:r.edge(u).weight+h})}),Object.prototype.hasOwnProperty.call(i,"minRank")&&o.setNode(a,{borderLeft:i.borderLeft[e],borderRight:i.borderRight[e]}))}),o}function Ge(r){for(var e;r.hasNode(e=B("_root")););return e}function re(r,e){for(var n=0,t=1;t<e.length;++t)n+=Ve(r,e[t-1],e[t]);return n}function Ve(r,e,n){for(var t=Q(n,v(n,function(d,c){return c})),o=g(v(e,function(d){return I(v(r.outEdges(d),function(c){return{pos:t[c.w],weight:r.edge(c).weight}}),"pos")})),a=1;a<n.length;)a<<=1;var i=2*a-1;a-=1;var s=v(new Array(i),function(){return 0}),u=0;return f(o.forEach(function(d){var c=d.pos+a;s[c]+=d.weight;for(var h=0;c>0;)c%2&&(h+=s[c+1]),c=c-1>>1,s[c]+=d.weight;u+=d.weight*h})),u}function ee(r){var e={},n=N(r.nodes(),function(s){return!r.children(s).length}),t=y(v(n,function(s){return r.node(s).rank})),o=v(x(t+1),function(){return[]});function a(s){if(!W(e,s)){e[s]=!0;var u=r.node(s);o[u.rank].push(s),f(r.successors(s),a)}}var i=I(n,function(s){return r.node(s).rank});return f(i,a),o}function ne(r,e){return v(e,function(n){var t=r.inEdges(n);if(t.length){var o=R(t,function(a,i){var s=r.edge(i),u=r.node(i.v);return{sum:a.sum+s.weight*u.order,weight:a.weight+s.weight}},{sum:0,weight:0});return{v:n,barycenter:o.sum/o.weight,weight:o.weight}}else return{v:n}})}function te(r,e){var n={};f(r,function(o,a){var i=n[o.v]={indegree:0,in:[],out:[],vs:[o.v],i:a};E(o.barycenter)||(i.barycenter=o.barycenter,i.weight=o.weight)}),f(e.edges(),function(o){var a=n[o.v],i=n[o.w];!E(a)&&!E(i)&&(i.indegree++,a.out.push(n[o.w]))});var t=N(n,function(o){return!o.indegree});return Be(t)}function Be(r){var e=[];function n(a){return function(i){i.merged||(E(i.barycenter)||E(a.barycenter)||i.barycenter>=a.barycenter)&&Ae(a,i)}}function t(a){return function(i){i.in.push(a),--i.indegree===0&&r.push(i)}}for(;r.length;){var o=r.pop();e.push(o),f(o.in.reverse(),n(o)),f(o.out,t(o))}return v(N(e,function(a){return!a.merged}),function(a){return V(a,["vs","i","barycenter","weight"])})}function Ae(r,e){var n=0,t=0;r.weight&&(n+=r.barycenter*r.weight,t+=r.weight),e.weight&&(n+=e.barycenter*e.weight,t+=e.weight),r.vs=e.vs.concat(r.vs),r.barycenter=n/t,r.weight=t,r.i=Math.min(e.i,r.i),e.merged=!0}function ae(r,e){var n=gr(r,function(c){return Object.prototype.hasOwnProperty.call(c,"barycenter")}),t=n.lhs,o=I(n.rhs,function(c){return-c.i}),a=[],i=0,s=0,u=0;t.sort(De(!!e)),u=oe(a,o,u),f(t,function(c){u+=c.vs.length,a.push(c.vs),i+=c.barycenter*c.weight,s+=c.weight,u=oe(a,o,u)});var d={vs:g(a)};return s&&(d.barycenter=i/s,d.weight=s),d}function oe(r,e,n){for(var t;e.length&&(t=j(e)).i<=n;)e.pop(),r.push(t.vs),n++;return n}function De(r){return function(e,n){return e.barycenter<n.barycenter?-1:e.barycenter>n.barycenter?1:r?n.i-e.i:e.i-n.i}}function cr(r,e,n,t){var o=r.children(e),a=r.node(e),i=a?a.borderLeft:void 0,s=a?a.borderRight:void 0,u={};i&&(o=N(o,function(m){return m!==i&&m!==s}));var d=ne(r,o);f(d,function(m){if(r.children(m.v).length){var w=cr(r,m.v,n,t);u[m.v]=w,Object.prototype.hasOwnProperty.call(w,"barycenter")&&ze(m,w)}});var c=te(d,n);Ye(c,u);var h=ae(c,t);if(i&&(h.vs=g([i,h.vs,s]),r.predecessors(i).length)){var l=r.node(r.predecessors(i)[0]),p=r.node(r.predecessors(s)[0]);Object.prototype.hasOwnProperty.call(h,"barycenter")||(h.barycenter=0,h.weight=0),h.barycenter=(h.barycenter*h.weight+l.order+p.order)/(h.weight+2),h.weight+=2}return h}function Ye(r,e){f(r,function(n){n.vs=g(n.vs.map(function(t){return e[t]?e[t].vs:t}))})}function ze(r,e){E(r.barycenter)?(r.barycenter=e.barycenter,r.weight=e.weight):(r.barycenter=(r.barycenter*r.weight+e.barycenter*e.weight)/(r.weight+e.weight),r.weight+=e.weight)}function fe(r){var e=rr(r),n=ie(r,x(1,e+1),"inEdges"),t=ie(r,x(e-1,-1,-1),"outEdges"),o=ee(r);se(r,o);for(var a=Number.POSITIVE_INFINITY,i,s=0,u=0;u<4;++s,++u){Ue(s%2?n:t,s%4>=2),o=P(r);var d=re(r,o);d<a&&(u=0,i=vr(o),a=d)}se(r,i)}function ie(r,e,n){return v(e,function(t){return $r(r,t,n)})}function Ue(r,e){var n=new b;f(r,function(t){var o=t.graph().root,a=cr(t,o,n,e);f(a.vs,function(i,s){t.node(i).order=s}),Zr(t,n,a.vs)})}function se(r,e){f(e,function(n){f(n,function(t,o){r.node(t).order=o})})}function ue(r){var e=qe(r);f(r.graph().dummyChains,function(n){for(var t=r.node(n),o=t.edgeObj,a=We(r,e,o.v,o.w),i=a.path,s=a.lca,u=0,d=i[u],c=!0;n!==o.w;){if(t=r.node(n),c){for(;(d=i[u])!==s&&r.node(d).maxRank<t.rank;)u++;d===s&&(c=!1)}if(!c){for(;u<i.length-1&&r.node(d=i[u+1]).minRank<=t.rank;)u++;d=i[u]}r.setParent(n,d),n=r.successors(n)[0]}})}function We(r,e,n,t){var o=[],a=[],i=Math.min(e[n].low,e[t].low),s=Math.max(e[n].lim,e[t].lim),u,d;u=n;do u=r.parent(u),o.push(u);while(u&&(e[u].low>i||s>e[u].lim));for(d=u,u=t;(u=r.parent(u))!==d;)a.push(u);return{path:o.concat(a.reverse()),lca:d}}function qe(r){var e={},n=0;function t(o){var a=n;f(r.children(o),t),e[o]={low:a,lim:n++}}return f(r.children(),t),e}function Xe(r,e){var n={};function t(o,a){var i=0,s=0,u=o.length,d=j(a);return f(a,function(c,h){var l=Je(r,c),p=l?r.node(l).order:u;(l||c===d)&&(f(a.slice(s,h+1),function(m){f(r.predecessors(m),function(w){var A=r.node(w),pr=A.order;(pr<i||p<pr)&&!(A.dummy&&r.node(m).dummy)&&de(n,w,m)})}),s=h+1,i=p)}),a}return R(e,t),n}function He(r,e){var n={};function t(a,i,s,u,d){var c;f(x(i,s),function(h){c=a[h],r.node(c).dummy&&f(r.predecessors(c),function(l){var p=r.node(l);p.dummy&&(p.order<u||p.order>d)&&de(n,l,c)})})}function o(a,i){var s=-1,u,d=0;return f(i,function(c,h){if(r.node(c).dummy==="border"){var l=r.predecessors(c);l.length&&(u=r.node(l[0]).order,t(i,d,h,s,u),d=h,s=u)}t(i,d,i.length,u,a.length)}),i}return R(e,o),n}function Je(r,e){if(r.node(e).dummy)return Y(r.predecessors(e),function(n){return r.node(n).dummy})}function de(r,e,n){if(e>n){var t=e;e=n,n=t}var o=r[e];o||(r[e]=o={}),o[n]=!0}function Ke(r,e,n){if(e>n){var t=e;e=n,n=t}return!!r[e]&&Object.prototype.hasOwnProperty.call(r[e],n)}function Qe(r,e,n,t){var o={},a={},i={};return f(e,function(s){f(s,function(u,d){o[u]=u,a[u]=u,i[u]=d})}),f(e,function(s){var u=-1;f(s,function(d){var c=t(d);if(c.length){c=I(c,function(w){return i[w]});for(var h=(c.length-1)/2,l=Math.floor(h),p=Math.ceil(h);l<=p;++l){var m=c[l];a[d]===d&&u<i[m]&&!Ke(n,d,m)&&(a[m]=d,a[d]=o[d]=o[m],u=i[m])}}})}),{root:o,align:a}}function Ze(r,e,n,t,o){var a={},i=$e(r,e,n,o),s=o?"borderLeft":"borderRight";function u(h,l){for(var p=i.nodes(),m=p.pop(),w={};m;)w[m]?h(m):(w[m]=!0,p.push(m),p=p.concat(l(m))),m=p.pop()}function d(h){a[h]=i.inEdges(h).reduce(function(l,p){return Math.max(l,a[p.v]+i.edge(p))},0)}function c(h){var l=i.outEdges(h).reduce(function(m,w){return Math.min(m,a[w.w]-i.edge(w))},Number.POSITIVE_INFINITY),p=r.node(h);l!==Number.POSITIVE_INFINITY&&p.borderType!==s&&(a[h]=Math.max(a[h],l))}return u(d,i.predecessors.bind(i)),u(c,i.successors.bind(i)),f(t,function(h){a[h]=a[n[h]]}),a}function $e(r,e,n,t){var o=new b,a=r.graph(),i=tn(a.nodesep,a.edgesep,t);return f(e,function(s){var u;f(s,function(d){var c=n[d];if(o.setNode(c),u){var h=n[u],l=o.edge(h,c);o.setEdge(h,c,Math.max(i(r,d,u),l||0))}u=d})}),o}function rn(r,e){return G(O(e),function(n){var t=Number.NEGATIVE_INFINITY,o=Number.POSITIVE_INFINITY;return wr(n,function(a,i){var s=on(r,i)/2;t=Math.max(a+s,t),o=Math.min(a-s,o)}),t-o})}function en(r,e){var n=O(e),t=L(n),o=y(n);f(["u","d"],function(a){f(["l","r"],function(i){var s=a+i,u=r[s],d;if(u!==e){var c=O(u);d=i==="l"?t-L(c):o-y(c),d&&(r[s]=F(u,function(h){return h+d}))}})})}function nn(r,e){return F(r.ul,function(n,t){if(e)return r[e.toLowerCase()][t];var o=I(v(r,t));return(o[1]+o[2])/2})}function ce(r){var e=P(r),n=D(Xe(r,e),He(r,e)),t={},o;f(["u","d"],function(i){o=i==="u"?e:O(e).reverse(),f(["l","r"],function(s){s==="r"&&(o=v(o,function(h){return O(h).reverse()}));var u=(i==="u"?r.predecessors:r.successors).bind(r),d=Qe(r,o,n,u),c=Ze(r,o,d.root,d.align,s==="r");s==="r"&&(c=F(c,function(h){return-h})),t[i+s]=c})});var a=rn(r,t);return en(t,a),nn(t,r.graph().align)}function tn(r,e,n){return function(t,o,a){var i=t.node(o),s=t.node(a),u=0,d;if(u+=i.width/2,Object.prototype.hasOwnProperty.call(i,"labelpos"))switch(i.labelpos.toLowerCase()){case"l":d=-i.width/2;break;case"r":d=i.width/2;break}if(d&&(u+=n?d:-d),d=0,u+=(i.dummy?e:r)/2,u+=(s.dummy?e:r)/2,u+=s.width/2,Object.prototype.hasOwnProperty.call(s,"labelpos"))switch(s.labelpos.toLowerCase()){case"l":d=s.width/2;break;case"r":d=-s.width/2;break}return d&&(u+=n?d:-d),d=0,u}}function on(r,e){return r.node(e).width}function he(r){r=q(r),an(r),br(ce(r),function(e,n){r.node(n).x=e})}function an(r){var e=P(r),n=r.graph().ranksep,t=0;f(e,function(o){var a=y(v(o,function(i){return r.node(i).height}));f(o,function(i){r.node(i).y=t+a/2}),t+=a+n})}function sn(r,e){var n=e&&e.debugTiming?Nr:Ir;n("layout",()=>{var t=n("  buildLayoutGraph",()=>wn(r));n("  runLayout",()=>fn(t,n)),n("  updateInputGraph",()=>un(r,t))})}function fn(r,e){e("    makeSpaceForEdgeLabels",()=>bn(r)),e("    removeSelfEdges",()=>Ln(r)),e("    acyclic",()=>Mr(r)),e("    nestingGraph.run",()=>Jr(r)),e("    rank",()=>dr(q(r))),e("    injectEdgeLabelProxies",()=>En(r)),e("    removeEmptyRanks",()=>kr(r)),e("    nestingGraph.cleanup",()=>Qr(r)),e("    normalizeRanks",()=>xr(r)),e("    assignRankMinMax",()=>yn(r)),e("    removeEdgeLabelProxies",()=>xn(r)),e("    normalize.run",()=>Vr(r)),e("    parentDummyChains",()=>ue(r)),e("    addBorderSegments",()=>Lr(r)),e("    order",()=>fe(r)),e("    insertSelfEdges",()=>Pn(r)),e("    adjustCoordinateSystem",()=>Cr(r)),e("    position",()=>he(r)),e("    positionSelfEdges",()=>Cn(r)),e("    removeBorderNodes",()=>On(r)),e("    normalize.undo",()=>Br(r)),e("    fixupEdgeLabelCoords",()=>Nn(r)),e("    undoCoordinateSystem",()=>Tr(r)),e("    translateGraph",()=>kn(r)),e("    assignNodeIntersects",()=>gn(r)),e("    reversePoints",()=>In(r)),e("    acyclic.undo",()=>Fr(r))}function un(r,e){f(r.nodes(),function(n){var t=r.node(n),o=e.node(n);t&&(t.x=o.x,t.y=o.y,e.children(n).length&&(t.width=o.width,t.height=o.height))}),f(r.edges(),function(n){var t=r.edge(n),o=e.edge(n);t.points=o.points,Object.prototype.hasOwnProperty.call(o,"x")&&(t.x=o.x,t.y=o.y)}),r.graph().width=e.graph().width,r.graph().height=e.graph().height}var dn=["nodesep","edgesep","ranksep","marginx","marginy"],cn={ranksep:50,edgesep:20,nodesep:50,rankdir:"tb"},hn=["acyclicer","ranker","rankdir","align"],ln=["width","height"],pn={width:0,height:0},mn=["minlen","weight","width","height","labeloffset"],vn={minlen:1,weight:1,width:0,height:0,labeloffset:10,labelpos:"r"},_n=["labelpos"];function wn(r){var e=new b({multigraph:!0,compound:!0}),n=lr(r.graph());return e.setGraph(D({},cn,hr(n,dn),V(n,hn))),f(r.nodes(),function(t){var o=lr(r.node(t));e.setNode(t,_r(hr(o,ln),pn)),e.setParent(t,r.parent(t))}),f(r.edges(),function(t){var o=lr(r.edge(t));e.setEdge(t,D({},vn,hr(o,mn),V(o,_n)))}),e}function bn(r){var e=r.graph();e.ranksep/=2,f(r.edges(),function(n){var t=r.edge(n);t.minlen*=2,t.labelpos.toLowerCase()!=="c"&&(e.rankdir==="TB"||e.rankdir==="BT"?t.width+=t.labeloffset:t.height+=t.labeloffset)})}function En(r){f(r.edges(),function(e){var n=r.edge(e);if(n.width&&n.height){var t=r.node(e.v),o=r.node(e.w),a={rank:(o.rank-t.rank)/2+t.rank,e};k(r,"edge-proxy",a,"_ep")}})}function yn(r){var e=0;f(r.nodes(),function(n){var t=r.node(n);t.borderTop&&(t.minRank=r.node(t.borderTop).rank,t.maxRank=r.node(t.borderBottom).rank,e=y(e,t.maxRank))}),r.graph().maxRank=e}function xn(r){f(r.nodes(),function(e){var n=r.node(e);n.dummy==="edge-proxy"&&(r.edge(n.e).labelRank=n.rank,r.removeNode(e))})}function kn(r){var e=Number.POSITIVE_INFINITY,n=0,t=Number.POSITIVE_INFINITY,o=0,a=r.graph(),i=a.marginx||0,s=a.marginy||0;function u(d){var c=d.x,h=d.y,l=d.width,p=d.height;e=Math.min(e,c-l/2),n=Math.max(n,c+l/2),t=Math.min(t,h-p/2),o=Math.max(o,h+p/2)}f(r.nodes(),function(d){u(r.node(d))}),f(r.edges(),function(d){var c=r.edge(d);Object.prototype.hasOwnProperty.call(c,"x")&&u(c)}),e-=i,t-=s,f(r.nodes(),function(d){var c=r.node(d);c.x-=e,c.y-=t}),f(r.edges(),function(d){var c=r.edge(d);f(c.points,function(h){h.x-=e,h.y-=t}),Object.prototype.hasOwnProperty.call(c,"x")&&(c.x-=e),Object.prototype.hasOwnProperty.call(c,"y")&&(c.y-=t)}),a.width=n-e+i,a.height=o-t+s}function gn(r){f(r.edges(),function(e){var n=r.edge(e),t=r.node(e.v),o=r.node(e.w),a,i;n.points?(a=n.points[0],i=n.points[n.points.length-1]):(n.points=[],a=o,i=t),n.points.unshift(Z(t,a)),n.points.push(Z(o,i))})}function Nn(r){f(r.edges(),function(e){var n=r.edge(e);if(Object.prototype.hasOwnProperty.call(n,"x"))switch((n.labelpos==="l"||n.labelpos==="r")&&(n.width-=n.labeloffset),n.labelpos){case"l":n.x-=n.width/2+n.labeloffset;break;case"r":n.x+=n.width/2+n.labeloffset;break}})}function In(r){f(r.edges(),function(e){var n=r.edge(e);n.reversed&&n.points.reverse()})}function On(r){f(r.nodes(),function(e){if(r.children(e).length){var n=r.node(e),t=r.node(n.borderTop),o=r.node(n.borderBottom),a=r.node(j(n.borderLeft)),i=r.node(j(n.borderRight));n.width=Math.abs(i.x-a.x),n.height=Math.abs(o.y-t.y),n.x=a.x+n.width/2,n.y=t.y+n.height/2}}),f(r.nodes(),function(e){r.node(e).dummy==="border"&&r.removeNode(e)})}function Ln(r){f(r.edges(),function(e){if(e.v===e.w){var n=r.node(e.v);n.selfEdges||(n.selfEdges=[]),n.selfEdges.push({e,label:r.edge(e)}),r.removeEdge(e)}})}function Pn(r){var e=P(r);f(e,function(n){var t=0;f(n,function(o,a){var i=r.node(o);i.order=a+t,f(i.selfEdges,function(s){k(r,"selfedge",{width:s.label.width,height:s.label.height,rank:i.rank,order:a+ ++t,e:s.e,label:s.label},"_se")}),delete i.selfEdges})})}function Cn(r){f(r.nodes(),function(e){var n=r.node(e);if(n.dummy==="selfedge"){var t=r.node(n.e.v),o=t.x+t.width/2,a=t.y,i=n.x-o,s=t.height/2;r.setEdge(n.e,n.label),r.removeNode(e),n.label.points=[{x:o+2*i/3,y:a-s},{x:o+5*i/6,y:a-s},{x:o+i,y:a},{x:o+5*i/6,y:a+s},{x:o+2*i/3,y:a+s}],n.label.x=n.x,n.label.y=n.y}})}function hr(r,e){return F(V(r,e),Number)}function lr(r){var e={};return f(r,function(n,t){e[t.toLowerCase()]=n}),e}export{sn as a};