/*! third party licenses: js/vendor.LICENSE.txt */
import{G as m}from"./graph-DW1leGfv.chunk.mjs";import{a as s,i as b,f as P,v as x,r as M}from"./_baseUniq-CE6homwJ.chunk.mjs";import{f as j,m as p,g as _,h as D,l as T,e as xn}from"./_basePickBy-0DU--7tw.chunk.mjs";import{h as un}from"./has-DJswI7NS.chunk.mjs";import{r as E,u as A,m as k,a as J,z as En,s as R,p as L,c as Nn,b as C,f as On,d as _n}from"./zipObject-D21phg5E.chunk.mjs";import{n as In,J as Pn,a8 as Y}from"./isEmpty-nTVdZyYD.chunk.mjs";class jn{constructor(){var e={};e._next=e._prev=e,this._sentinel=e}dequeue(){var e=this._sentinel,r=e._prev;if(r!==e)return W(r),r}enqueue(e){var r=this._sentinel;e._prev&&e._next&&W(e),e._next=r._next,r._next._prev=e,r._next=e,e._prev=r}toString(){for(var e=[],r=this._sentinel,t=r._prev;t!==r;)e.push(JSON.stringify(t,Rn)),t=t._prev;return"["+e.join(", ")+"]"}}function W(n){n._prev._next=n._next,n._next._prev=n._prev,delete n._next,delete n._prev}function Rn(n,e){if(n!=="_next"&&n!=="_prev")return e}var Tn=In(1);function Ln(n,e){if(n.nodeCount()<=1)return[];var r=Cn(n,e||Tn),t=Mn(r.graph,r.buckets,r.zeroIdx);return j(p(t,function(o){return n.outEdges(o.v,o.w)}))}function Mn(n,e,r){for(var t=[],o=e[e.length-1],a=e[0],i;n.nodeCount();){for(;i=a.dequeue();)G(n,e,r,i);for(;i=o.dequeue();)G(n,e,r,i);if(n.nodeCount()){for(var u=e.length-2;u>0;--u)if(i=e[u].dequeue(),i){t=t.concat(G(n,e,r,i,!0));break}}}return t}function G(n,e,r,t,o){var a=o?[]:void 0;return s(n.inEdges(t.v),function(i){var u=n.edge(i),d=n.node(i.v);o&&a.push({v:i.v,w:i.w}),d.out-=u,z(e,r,d)}),s(n.outEdges(t.v),function(i){var u=n.edge(i),d=i.w,c=n.node(d);c.in-=u,z(e,r,c)}),n.removeNode(t.v),a}function Cn(n,e){var r=new m,t=0,o=0;s(n.nodes(),function(u){r.setNode(u,{v:u,in:0,out:0})}),s(n.edges(),function(u){var d=r.edge(u.v,u.w)||0,c=e(u),f=d+c;r.setEdge(u.v,u.w,f),o=Math.max(o,r.node(u.v).out+=c),t=Math.max(t,r.node(u.w).in+=c)});var a=E(o+t+3).map(function(){return new jn}),i=t+1;return s(r.nodes(),function(u){z(a,i,r.node(u))}),{graph:r,buckets:a,zeroIdx:i}}function z(n,e,r){r.out?r.in?n[r.out-r.in+e].enqueue(r):n[n.length-1].enqueue(r):n[0].enqueue(r)}function Sn(n){var e=n.graph().acyclicer==="greedy"?Ln(n,r(n)):Gn(n);s(e,function(t){var o=n.edge(t);n.removeEdge(t),o.forwardName=t.name,o.reversed=!0,n.setEdge(t.w,t.v,o,A("rev"))});function r(t){return function(o){return t.edge(o).weight}}}function Gn(n){var e=[],r={},t={};function o(a){Object.prototype.hasOwnProperty.call(t,a)||(t[a]=!0,r[a]=!0,s(n.outEdges(a),function(i){Object.prototype.hasOwnProperty.call(r,i.w)?e.push(i):o(i.w)}),delete r[a])}return s(n.nodes(),o),e}function Fn(n){s(n.edges(),function(e){var r=n.edge(e);if(r.reversed){n.removeEdge(e);var t=r.forwardName;delete r.reversed,delete r.forwardName,n.setEdge(e.w,e.v,r,t)}})}function N(n,e,r,t){var o;do o=A(t);while(n.hasNode(o));return r.dummy=e,n.setNode(o,r),o}function Vn(n){var e=new m().setGraph(n.graph());return s(n.nodes(),function(r){e.setNode(r,n.node(r))}),s(n.edges(),function(r){var t=e.edge(r.v,r.w)||{weight:0,minlen:1},o=n.edge(r);e.setEdge(r.v,r.w,{weight:t.weight+o.weight,minlen:Math.max(t.minlen,o.minlen)})}),e}function dn(n){var e=new m({multigraph:n.isMultigraph()}).setGraph(n.graph());return s(n.nodes(),function(r){n.children(r).length||e.setNode(r,n.node(r))}),s(n.edges(),function(r){e.setEdge(r,n.edge(r))}),e}function X(n,e){var r=n.x,t=n.y,o=e.x-r,a=e.y-t,i=n.width/2,u=n.height/2;if(!o&&!a)throw new Error("Not possible to find intersection inside of the rectangle");var d,c;return Math.abs(a)*i>Math.abs(o)*u?(a<0&&(u=-u),d=u*o/a,c=u):(o<0&&(i=-i),d=i,c=i*a/o),{x:r+d,y:t+c}}function S(n){var e=p(E(cn(n)+1),function(){return[]});return s(n.nodes(),function(r){var t=n.node(r),o=t.rank;b(o)||(e[o][t.order]=r)}),e}function Bn(n){var e=_(p(n.nodes(),function(r){return n.node(r).rank}));s(n.nodes(),function(r){var t=n.node(r);un(t,"rank")&&(t.rank-=e)})}function qn(n){var e=_(p(n.nodes(),function(a){return n.node(a).rank})),r=[];s(n.nodes(),function(a){var i=n.node(a).rank-e;r[i]||(r[i]=[]),r[i].push(a)});var t=0,o=n.graph().nodeRankFactor;s(r,function(a,i){b(a)&&i%o!==0?--t:t&&s(a,function(u){n.node(u).rank+=t})})}function Z(n,e,r,t){var o={width:0,height:0};return arguments.length>=4&&(o.rank=r,o.order=t),N(n,"border",o,e)}function cn(n){return k(p(n.nodes(),function(e){var r=n.node(e).rank;if(!b(r))return r}))}function Yn(n,e){var r={lhs:[],rhs:[]};return s(n,function(t){e(t)?r.lhs.push(t):r.rhs.push(t)}),r}function zn(n,e){return e()}function Dn(n){function e(r){var t=n.children(r),o=n.node(r);if(t.length&&s(t,e),Object.prototype.hasOwnProperty.call(o,"minRank")){o.borderLeft=[],o.borderRight=[];for(var a=o.minRank,i=o.maxRank+1;a<i;++a)$(n,"borderLeft","_bl",r,o,a),$(n,"borderRight","_br",r,o,a)}}s(n.children(),e)}function $(n,e,r,t,o,a){var i={width:0,height:0,rank:a,borderType:e},u=o[e][a-1],d=N(n,"border",i,r);o[e][a]=d,n.setParent(d,t),u&&n.setEdge(u,d,{weight:1})}function An(n){var e=n.graph().rankdir.toLowerCase();(e==="lr"||e==="rl")&&sn(n)}function Jn(n){var e=n.graph().rankdir.toLowerCase();(e==="bt"||e==="rl")&&Hn(n),(e==="lr"||e==="rl")&&(Kn(n),sn(n))}function sn(n){s(n.nodes(),function(e){nn(n.node(e))}),s(n.edges(),function(e){nn(n.edge(e))})}function nn(n){var e=n.width;n.width=n.height,n.height=e}function Hn(n){s(n.nodes(),function(e){F(n.node(e))}),s(n.edges(),function(e){var r=n.edge(e);s(r.points,F),Object.prototype.hasOwnProperty.call(r,"y")&&F(r)})}function F(n){n.y=-n.y}function Kn(n){s(n.nodes(),function(e){V(n.node(e))}),s(n.edges(),function(e){var r=n.edge(e);s(r.points,V),Object.prototype.hasOwnProperty.call(r,"x")&&V(r)})}function V(n){var e=n.x;n.x=n.y,n.y=e}function Qn(n){n.graph().dummyChains=[],s(n.edges(),function(e){Un(n,e)})}function Un(n,e){var r=e.v,t=n.node(r).rank,o=e.w,a=n.node(o).rank,i=e.name,u=n.edge(e),d=u.labelRank;if(a!==t+1){n.removeEdge(e);var c=void 0,f,h;for(h=0,++t;t<a;++h,++t)u.points=[],c={width:0,height:0,edgeLabel:u,edgeObj:e,rank:t},f=N(n,"edge",c,"_d"),t===d&&(c.width=u.width,c.height=u.height,c.dummy="edge-label",c.labelpos=u.labelpos),n.setEdge(r,f,{weight:u.weight},i),h===0&&n.graph().dummyChains.push(f),r=f;n.setEdge(r,o,{weight:u.weight},i)}}function Wn(n){s(n.graph().dummyChains,function(e){var r=n.node(e),t=r.edgeLabel,o;for(n.setEdge(r.edgeObj,t);r.dummy;)o=n.successors(e)[0],n.removeNode(e),t.points.push({x:r.x,y:r.y}),r.dummy==="edge-label"&&(t.x=r.x,t.y=r.y,t.width=r.width,t.height=r.height),e=o,r=n.node(e)})}function H(n){var e={};function r(t){var o=n.node(t);if(Object.prototype.hasOwnProperty.call(e,t))return o.rank;e[t]=!0;var a=_(p(n.outEdges(t),function(i){return r(i.w)-n.edge(i).minlen}));return(a===Number.POSITIVE_INFINITY||a===void 0||a===null)&&(a=0),o.rank=a}s(n.sources(),r)}function I(n,e){return n.node(e.w).rank-n.node(e.v).rank-n.edge(e).minlen}function fn(n){var e=new m({directed:!1}),r=n.nodes()[0],t=n.nodeCount();e.setNode(r,{});for(var o,a;Xn(e,n)<t;)o=Zn(e,n),a=e.hasNode(o.v)?I(n,o):-I(n,o),$n(e,n,a);return e}function Xn(n,e){function r(t){s(e.nodeEdges(t),function(o){var a=o.v,i=t===a?o.w:a;!n.hasNode(i)&&!I(e,o)&&(n.setNode(i,{}),n.setEdge(t,i,{}),r(i))})}return s(n.nodes(),r),n.nodeCount()}function Zn(n,e){return J(e.edges(),function(r){if(n.hasNode(r.v)!==n.hasNode(r.w))return I(e,r)})}function $n(n,e,r){s(n.nodes(),function(t){e.node(t).rank+=r})}function ne(){}ne.prototype=new Error;function hn(n,e,r){Pn(e)||(e=[e]);var t=(n.isDirected()?n.successors:n.neighbors).bind(n),o=[],a={};return s(e,function(i){if(!n.hasNode(i))throw new Error("Graph does not have node: "+i);gn(n,i,r==="post",a,t,o)}),o}function gn(n,e,r,t,o,a){Object.prototype.hasOwnProperty.call(t,e)||(t[e]=!0,r||a.push(e),s(o(e),function(i){gn(n,i,r,t,o,a)}),r&&a.push(e))}function ee(n,e){return hn(n,e,"post")}function re(n,e){return hn(n,e,"pre")}y.initLowLimValues=Q,y.initCutValues=K,y.calcCutValue=vn,y.leaveEdge=pn,y.enterEdge=wn,y.exchangeEdges=bn;function y(n){n=Vn(n),H(n);var e=fn(n);Q(e),K(e,n);for(var r,t;r=pn(e);)t=wn(e,n,r),bn(e,n,r,t)}function K(n,e){var r=ee(n,n.nodes());r=r.slice(0,r.length-1),s(r,function(t){te(n,e,t)})}function te(n,e,r){var t=n.node(r),o=t.parent;n.edge(r,o).cutvalue=vn(n,e,r)}function vn(n,e,r){var t=n.node(r),o=t.parent,a=!0,i=e.edge(r,o),u=0;return i||(a=!1,i=e.edge(o,r)),u=i.weight,s(e.nodeEdges(r),function(d){var c=d.v===r,f=c?d.w:d.v;if(f!==o){var h=c===a,g=e.edge(d).weight;if(u+=h?g:-g,ie(n,r,f)){var v=n.edge(r,f).cutvalue;u+=h?-v:v}}}),u}function Q(n,e){arguments.length<2&&(e=n.nodes()[0]),ln(n,{},1,e)}function ln(n,e,r,t,o){var a=r,i=n.node(t);return e[t]=!0,s(n.neighbors(t),function(u){Object.prototype.hasOwnProperty.call(e,u)||(r=ln(n,e,r,u,t))}),i.low=a,i.lim=r++,o?i.parent=o:delete i.parent,r}function pn(n){return D(n.edges(),function(e){return n.edge(e).cutvalue<0})}function wn(n,e,r){var t=r.v,o=r.w;e.hasEdge(t,o)||(t=r.w,o=r.v);var a=n.node(t),i=n.node(o),u=a,d=!1;a.lim>i.lim&&(u=i,d=!0);var c=P(e.edges(),function(f){return d===en(n,n.node(f.v),u)&&d!==en(n,n.node(f.w),u)});return J(c,function(f){return I(e,f)})}function bn(n,e,r,t){var o=r.v,a=r.w;n.removeEdge(o,a),n.setEdge(t.v,t.w,{}),Q(n),K(n,e),oe(n,e)}function oe(n,e){var r=D(n.nodes(),function(o){return!e.node(o).parent}),t=re(n,r);t=t.slice(1),s(t,function(o){var a=n.node(o).parent,i=e.edge(o,a),u=!1;i||(i=e.edge(a,o),u=!0),e.node(o).rank=e.node(a).rank+(u?i.minlen:-i.minlen)})}function ie(n,e,r){return n.hasEdge(e,r)}function en(n,e,r){return r.low<=e.lim&&e.lim<=r.lim}function ae(n){switch(n.graph().ranker){case"network-simplex":rn(n);break;case"tight-tree":de(n);break;case"longest-path":ue(n);break;default:rn(n)}}var ue=H;function de(n){H(n),fn(n)}function rn(n){y(n)}function ce(n){var e=N(n,"root",{},"_root"),r=se(n),t=k(x(r))-1,o=2*t+1;n.graph().nestingRoot=e,s(n.edges(),function(i){n.edge(i).minlen*=o});var a=fe(n)+1;s(n.children(),function(i){mn(n,e,o,a,t,r,i)}),n.graph().nodeRankFactor=o}function mn(n,e,r,t,o,a,i){var u=n.children(i);if(!u.length){i!==e&&n.setEdge(e,i,{weight:0,minlen:r});return}var d=Z(n,"_bt"),c=Z(n,"_bb"),f=n.node(i);n.setParent(d,i),f.borderTop=d,n.setParent(c,i),f.borderBottom=c,s(u,function(h){mn(n,e,r,t,o,a,h);var g=n.node(h),v=g.borderTop?g.borderTop:h,l=g.borderBottom?g.borderBottom:h,w=g.borderTop?t:2*t,O=v!==l?1:o-a[i]+1;n.setEdge(d,v,{weight:w,minlen:O,nestingEdge:!0}),n.setEdge(l,c,{weight:w,minlen:O,nestingEdge:!0})}),n.parent(i)||n.setEdge(e,d,{weight:0,minlen:o+a[i]})}function se(n){var e={};function r(t,o){var a=n.children(t);a&&a.length&&s(a,function(i){r(i,o+1)}),e[t]=o}return s(n.children(),function(t){r(t,1)}),e}function fe(n){return M(n.edges(),function(e,r){return e+n.edge(r).weight},0)}function he(n){var e=n.graph();n.removeNode(e.nestingRoot),delete e.nestingRoot,s(n.edges(),function(r){var t=n.edge(r);t.nestingEdge&&n.removeEdge(r)})}function ge(n,e,r){var t={},o;s(r,function(a){for(var i=n.parent(a),u,d;i;){if(u=n.parent(i),u?(d=t[u],t[u]=i):(d=o,o=i),d&&d!==i){e.setEdge(d,i);return}i=u}})}function ve(n,e,r){var t=le(n),o=new m({compound:!0}).setGraph({root:t}).setDefaultNodeLabel(function(a){return n.node(a)});return s(n.nodes(),function(a){var i=n.node(a),u=n.parent(a);(i.rank===e||i.minRank<=e&&e<=i.maxRank)&&(o.setNode(a),o.setParent(a,u||t),s(n[r](a),function(d){var c=d.v===a?d.w:d.v,f=o.edge(c,a),h=b(f)?0:f.weight;o.setEdge(c,a,{weight:n.edge(d).weight+h})}),Object.prototype.hasOwnProperty.call(i,"minRank")&&o.setNode(a,{borderLeft:i.borderLeft[e],borderRight:i.borderRight[e]}))}),o}function le(n){for(var e;n.hasNode(e=A("_root")););return e}function pe(n,e){for(var r=0,t=1;t<e.length;++t)r+=we(n,e[t-1],e[t]);return r}function we(n,e,r){for(var t=En(r,p(r,function(c,f){return f})),o=j(p(e,function(c){return R(p(n.outEdges(c),function(f){return{pos:t[f.w],weight:n.edge(f).weight}}),"pos")})),a=1;a<r.length;)a<<=1;var i=2*a-1;a-=1;var u=p(new Array(i),function(){return 0}),d=0;return s(o.forEach(function(c){var f=c.pos+a;u[f]+=c.weight;for(var h=0;f>0;)f%2&&(h+=u[f+1]),f=f-1>>1,u[f]+=c.weight;d+=c.weight*h})),d}function be(n){var e={},r=P(n.nodes(),function(u){return!n.children(u).length}),t=k(p(r,function(u){return n.node(u).rank})),o=p(E(t+1),function(){return[]});function a(u){if(!un(e,u)){e[u]=!0;var d=n.node(u);o[d.rank].push(u),s(n.successors(u),a)}}var i=R(r,function(u){return n.node(u).rank});return s(i,a),o}function me(n,e){return p(e,function(r){var t=n.inEdges(r);if(t.length){var o=M(t,function(a,i){var u=n.edge(i),d=n.node(i.v);return{sum:a.sum+u.weight*d.order,weight:a.weight+u.weight}},{sum:0,weight:0});return{v:r,barycenter:o.sum/o.weight,weight:o.weight}}else return{v:r}})}function ye(n,e){var r={};s(n,function(o,a){var i=r[o.v]={indegree:0,in:[],out:[],vs:[o.v],i:a};b(o.barycenter)||(i.barycenter=o.barycenter,i.weight=o.weight)}),s(e.edges(),function(o){var a=r[o.v],i=r[o.w];!b(a)&&!b(i)&&(i.indegree++,a.out.push(r[o.w]))});var t=P(r,function(o){return!o.indegree});return ke(t)}function ke(n){var e=[];function r(a){return function(i){i.merged||(b(i.barycenter)||b(a.barycenter)||i.barycenter>=a.barycenter)&&xe(a,i)}}function t(a){return function(i){i.in.push(a),--i.indegree===0&&n.push(i)}}for(;n.length;){var o=n.pop();e.push(o),s(o.in.reverse(),r(o)),s(o.out,t(o))}return p(P(e,function(a){return!a.merged}),function(a){return L(a,["vs","i","barycenter","weight"])})}function xe(n,e){var r=0,t=0;n.weight&&(r+=n.barycenter*n.weight,t+=n.weight),e.weight&&(r+=e.barycenter*e.weight,t+=e.weight),n.vs=e.vs.concat(n.vs),n.barycenter=r/t,n.weight=t,n.i=Math.min(e.i,n.i),e.merged=!0}function Ee(n,e){var r=Yn(n,function(f){return Object.prototype.hasOwnProperty.call(f,"barycenter")}),t=r.lhs,o=R(r.rhs,function(f){return-f.i}),a=[],i=0,u=0,d=0;t.sort(Ne(!!e)),d=tn(a,o,d),s(t,function(f){d+=f.vs.length,a.push(f.vs),i+=f.barycenter*f.weight,u+=f.weight,d=tn(a,o,d)});var c={vs:j(a)};return u&&(c.barycenter=i/u,c.weight=u),c}function tn(n,e,r){for(var t;e.length&&(t=T(e)).i<=r;)e.pop(),n.push(t.vs),r++;return r}function Ne(n){return function(e,r){return e.barycenter<r.barycenter?-1:e.barycenter>r.barycenter?1:n?r.i-e.i:e.i-r.i}}function yn(n,e,r,t){var o=n.children(e),a=n.node(e),i=a?a.borderLeft:void 0,u=a?a.borderRight:void 0,d={};i&&(o=P(o,function(l){return l!==i&&l!==u}));var c=me(n,o);s(c,function(l){if(n.children(l.v).length){var w=yn(n,l.v,r,t);d[l.v]=w,Object.prototype.hasOwnProperty.call(w,"barycenter")&&_e(l,w)}});var f=ye(c,r);Oe(f,d);var h=Ee(f,t);if(i&&(h.vs=j([i,h.vs,u]),n.predecessors(i).length)){var g=n.node(n.predecessors(i)[0]),v=n.node(n.predecessors(u)[0]);Object.prototype.hasOwnProperty.call(h,"barycenter")||(h.barycenter=0,h.weight=0),h.barycenter=(h.barycenter*h.weight+g.order+v.order)/(h.weight+2),h.weight+=2}return h}function Oe(n,e){s(n,function(r){r.vs=j(r.vs.map(function(t){return e[t]?e[t].vs:t}))})}function _e(n,e){b(n.barycenter)?(n.barycenter=e.barycenter,n.weight=e.weight):(n.barycenter=(n.barycenter*n.weight+e.barycenter*e.weight)/(n.weight+e.weight),n.weight+=e.weight)}function Ie(n){var e=cn(n),r=on(n,E(1,e+1),"inEdges"),t=on(n,E(e-1,-1,-1),"outEdges"),o=be(n);an(n,o);for(var a=Number.POSITIVE_INFINITY,i,u=0,d=0;d<4;++u,++d){Pe(u%2?r:t,u%4>=2),o=S(n);var c=pe(n,o);c<a&&(d=0,i=Nn(o),a=c)}an(n,i)}function on(n,e,r){return p(e,function(t){return ve(n,t,r)})}function Pe(n,e){var r=new m;s(n,function(t){var o=t.graph().root,a=yn(t,o,r,e);s(a.vs,function(i,u){t.node(i).order=u}),ge(t,r,a.vs)})}function an(n,e){s(e,function(r){s(r,function(t,o){n.node(t).order=o})})}function je(n){var e=Te(n);s(n.graph().dummyChains,function(r){for(var t=n.node(r),o=t.edgeObj,a=Re(n,e,o.v,o.w),i=a.path,u=a.lca,d=0,c=i[d],f=!0;r!==o.w;){if(t=n.node(r),f){for(;(c=i[d])!==u&&n.node(c).maxRank<t.rank;)d++;c===u&&(f=!1)}if(!f){for(;d<i.length-1&&n.node(c=i[d+1]).minRank<=t.rank;)d++;c=i[d]}n.setParent(r,c),r=n.successors(r)[0]}})}function Re(n,e,r,t){var o=[],a=[],i=Math.min(e[r].low,e[t].low),u=Math.max(e[r].lim,e[t].lim),d,c;d=r;do d=n.parent(d),o.push(d);while(d&&(e[d].low>i||u>e[d].lim));for(c=d,d=t;(d=n.parent(d))!==c;)a.push(d);return{path:o.concat(a.reverse()),lca:c}}function Te(n){var e={},r=0;function t(o){var a=r;s(n.children(o),t),e[o]={low:a,lim:r++}}return s(n.children(),t),e}function Le(n,e){var r={};function t(o,a){var i=0,u=0,d=o.length,c=T(a);return s(a,function(f,h){var g=Ce(n,f),v=g?n.node(g).order:d;(g||f===c)&&(s(a.slice(u,h+1),function(l){s(n.predecessors(l),function(w){var O=n.node(w),U=O.order;(U<i||v<U)&&!(O.dummy&&n.node(l).dummy)&&kn(r,w,l)})}),u=h+1,i=v)}),a}return M(e,t),r}function Me(n,e){var r={};function t(a,i,u,d,c){var f;s(E(i,u),function(h){f=a[h],n.node(f).dummy&&s(n.predecessors(f),function(g){var v=n.node(g);v.dummy&&(v.order<d||v.order>c)&&kn(r,g,f)})})}function o(a,i){var u=-1,d,c=0;return s(i,function(f,h){if(n.node(f).dummy==="border"){var g=n.predecessors(f);g.length&&(d=n.node(g[0]).order,t(i,c,h,u,d),c=h,u=d)}t(i,c,i.length,d,a.length)}),i}return M(e,o),r}function Ce(n,e){if(n.node(e).dummy)return D(n.predecessors(e),function(r){return n.node(r).dummy})}function kn(n,e,r){if(e>r){var t=e;e=r,r=t}Object.prototype.hasOwnProperty.call(n,e)||Object.defineProperty(n,e,{enumerable:!0,configurable:!0,value:{},writable:!0});var o=n[e];Object.defineProperty(o,r,{enumerable:!0,configurable:!0,value:!0,writable:!0})}function Se(n,e,r){if(e>r){var t=e;e=r,r=t}return!!n[e]&&Object.prototype.hasOwnProperty.call(n[e],r)}function Ge(n,e,r,t){var o={},a={},i={};return s(e,function(u){s(u,function(d,c){o[d]=d,a[d]=d,i[d]=c})}),s(e,function(u){var d=-1;s(u,function(c){var f=t(c);if(f.length){f=R(f,function(w){return i[w]});for(var h=(f.length-1)/2,g=Math.floor(h),v=Math.ceil(h);g<=v;++g){var l=f[g];a[c]===c&&d<i[l]&&!Se(r,c,l)&&(a[l]=c,a[c]=o[c]=o[l],d=i[l])}}})}),{root:o,align:a}}function Fe(n,e,r,t,o){var a={},i=Ve(n,e,r,o),u=o?"borderLeft":"borderRight";function d(h,g){for(var v=i.nodes(),l=v.pop(),w={};l;)w[l]?h(l):(w[l]=!0,v.push(l),v=v.concat(g(l))),l=v.pop()}function c(h){a[h]=i.inEdges(h).reduce(function(g,v){return Math.max(g,a[v.v]+i.edge(v))},0)}function f(h){var g=i.outEdges(h).reduce(function(l,w){return Math.min(l,a[w.w]-i.edge(w))},Number.POSITIVE_INFINITY),v=n.node(h);g!==Number.POSITIVE_INFINITY&&v.borderType!==u&&(a[h]=Math.max(a[h],g))}return d(c,i.predecessors.bind(i)),d(f,i.successors.bind(i)),s(t,function(h){a[h]=a[r[h]]}),a}function Ve(n,e,r,t){var o=new m,a=n.graph(),i=De(a.nodesep,a.edgesep,t);return s(e,function(u){var d;s(u,function(c){var f=r[c];if(o.setNode(f),d){var h=r[d],g=o.edge(h,f);o.setEdge(h,f,Math.max(i(n,c,d),g||0))}d=c})}),o}function Be(n,e){return J(x(e),function(r){var t=Number.NEGATIVE_INFINITY,o=Number.POSITIVE_INFINITY;return On(r,function(a,i){var u=Ae(n,i)/2;t=Math.max(a+u,t),o=Math.min(a-u,o)}),t-o})}function qe(n,e){var r=x(e),t=_(r),o=k(r);s(["u","d"],function(a){s(["l","r"],function(i){var u=a+i,d=n[u],c;if(d!==e){var f=x(d);c=i==="l"?t-_(f):o-k(f),c&&(n[u]=C(d,function(h){return h+c}))}})})}function Ye(n,e){return C(n.ul,function(r,t){if(e)return n[e.toLowerCase()][t];var o=R(p(n,t));return(o[1]+o[2])/2})}function ze(n){var e=S(n),r=Y(Le(n,e),Me(n,e)),t={},o;s(["u","d"],function(i){o=i==="u"?e:x(e).reverse(),s(["l","r"],function(u){u==="r"&&(o=p(o,function(h){return x(h).reverse()}));var d=(i==="u"?n.predecessors:n.successors).bind(n),c=Ge(n,o,r,d),f=Fe(n,o,c.root,c.align,u==="r");u==="r"&&(f=C(f,function(h){return-h})),t[i+u]=f})});var a=Be(n,t);return qe(t,a),Ye(t,n.graph().align)}function De(n,e,r){return function(t,o,a){var i=t.node(o),u=t.node(a),d=0,c;if(d+=i.width/2,Object.prototype.hasOwnProperty.call(i,"labelpos"))switch(i.labelpos.toLowerCase()){case"l":c=-i.width/2;break;case"r":c=i.width/2;break}if(c&&(d+=r?c:-c),c=0,d+=(i.dummy?e:n)/2,d+=(u.dummy?e:n)/2,d+=u.width/2,Object.prototype.hasOwnProperty.call(u,"labelpos"))switch(u.labelpos.toLowerCase()){case"l":c=u.width/2;break;case"r":c=-u.width/2;break}return c&&(d+=r?c:-c),c=0,d}}function Ae(n,e){return n.node(e).width}function Je(n){n=dn(n),He(n),_n(ze(n),function(e,r){n.node(r).x=e})}function He(n){var e=S(n),r=n.graph().ranksep,t=0;s(e,function(o){var a=k(p(o,function(i){return n.node(i).height}));s(o,function(i){n.node(i).y=t+a/2}),t+=a+r})}function xr(n,e){var r=zn;r("layout",()=>{var t=r("  buildLayoutGraph",()=>tr(n));r("  runLayout",()=>Ke(t,r)),r("  updateInputGraph",()=>Qe(n,t))})}function Ke(n,e){e("    makeSpaceForEdgeLabels",()=>or(n)),e("    removeSelfEdges",()=>gr(n)),e("    acyclic",()=>Sn(n)),e("    nestingGraph.run",()=>ce(n)),e("    rank",()=>ae(dn(n))),e("    injectEdgeLabelProxies",()=>ir(n)),e("    removeEmptyRanks",()=>qn(n)),e("    nestingGraph.cleanup",()=>he(n)),e("    normalizeRanks",()=>Bn(n)),e("    assignRankMinMax",()=>ar(n)),e("    removeEdgeLabelProxies",()=>ur(n)),e("    normalize.run",()=>Qn(n)),e("    parentDummyChains",()=>je(n)),e("    addBorderSegments",()=>Dn(n)),e("    order",()=>Ie(n)),e("    insertSelfEdges",()=>vr(n)),e("    adjustCoordinateSystem",()=>An(n)),e("    position",()=>Je(n)),e("    positionSelfEdges",()=>lr(n)),e("    removeBorderNodes",()=>hr(n)),e("    normalize.undo",()=>Wn(n)),e("    fixupEdgeLabelCoords",()=>sr(n)),e("    undoCoordinateSystem",()=>Jn(n)),e("    translateGraph",()=>dr(n)),e("    assignNodeIntersects",()=>cr(n)),e("    reversePoints",()=>fr(n)),e("    acyclic.undo",()=>Fn(n))}function Qe(n,e){s(n.nodes(),function(r){var t=n.node(r),o=e.node(r);t&&(t.x=o.x,t.y=o.y,e.children(r).length&&(t.width=o.width,t.height=o.height))}),s(n.edges(),function(r){var t=n.edge(r),o=e.edge(r);t.points=o.points,Object.prototype.hasOwnProperty.call(o,"x")&&(t.x=o.x,t.y=o.y)}),n.graph().width=e.graph().width,n.graph().height=e.graph().height}var Ue=["nodesep","edgesep","ranksep","marginx","marginy"],We={ranksep:50,edgesep:20,nodesep:50,rankdir:"tb"},Xe=["acyclicer","ranker","rankdir","align"],Ze=["width","height"],$e={width:0,height:0},nr=["minlen","weight","width","height","labeloffset"],er={minlen:1,weight:1,width:0,height:0,labeloffset:10,labelpos:"r"},rr=["labelpos"];function tr(n){var e=new m({multigraph:!0,compound:!0}),r=q(n.graph());return e.setGraph(Y({},We,B(r,Ue),L(r,Xe))),s(n.nodes(),function(t){var o=q(n.node(t));e.setNode(t,xn(B(o,Ze),$e)),e.setParent(t,n.parent(t))}),s(n.edges(),function(t){var o=q(n.edge(t));e.setEdge(t,Y({},er,B(o,nr),L(o,rr)))}),e}function or(n){var e=n.graph();e.ranksep/=2,s(n.edges(),function(r){var t=n.edge(r);t.minlen*=2,t.labelpos.toLowerCase()!=="c"&&(e.rankdir==="TB"||e.rankdir==="BT"?t.width+=t.labeloffset:t.height+=t.labeloffset)})}function ir(n){s(n.edges(),function(e){var r=n.edge(e);if(r.width&&r.height){var t=n.node(e.v),o=n.node(e.w),a={rank:(o.rank-t.rank)/2+t.rank,e};N(n,"edge-proxy",a,"_ep")}})}function ar(n){var e=0;s(n.nodes(),function(r){var t=n.node(r);t.borderTop&&(t.minRank=n.node(t.borderTop).rank,t.maxRank=n.node(t.borderBottom).rank,e=k(e,t.maxRank))}),n.graph().maxRank=e}function ur(n){s(n.nodes(),function(e){var r=n.node(e);r.dummy==="edge-proxy"&&(n.edge(r.e).labelRank=r.rank,n.removeNode(e))})}function dr(n){var e=Number.POSITIVE_INFINITY,r=0,t=Number.POSITIVE_INFINITY,o=0,a=n.graph(),i=a.marginx||0,u=a.marginy||0;function d(c){var f=c.x,h=c.y,g=c.width,v=c.height;e=Math.min(e,f-g/2),r=Math.max(r,f+g/2),t=Math.min(t,h-v/2),o=Math.max(o,h+v/2)}s(n.nodes(),function(c){d(n.node(c))}),s(n.edges(),function(c){var f=n.edge(c);Object.prototype.hasOwnProperty.call(f,"x")&&d(f)}),e-=i,t-=u,s(n.nodes(),function(c){var f=n.node(c);f.x-=e,f.y-=t}),s(n.edges(),function(c){var f=n.edge(c);s(f.points,function(h){h.x-=e,h.y-=t}),Object.prototype.hasOwnProperty.call(f,"x")&&(f.x-=e),Object.prototype.hasOwnProperty.call(f,"y")&&(f.y-=t)}),a.width=r-e+i,a.height=o-t+u}function cr(n){s(n.edges(),function(e){var r=n.edge(e),t=n.node(e.v),o=n.node(e.w),a,i;r.points?(a=r.points[0],i=r.points[r.points.length-1]):(r.points=[],a=o,i=t),r.points.unshift(X(t,a)),r.points.push(X(o,i))})}function sr(n){s(n.edges(),function(e){var r=n.edge(e);if(Object.prototype.hasOwnProperty.call(r,"x"))switch((r.labelpos==="l"||r.labelpos==="r")&&(r.width-=r.labeloffset),r.labelpos){case"l":r.x-=r.width/2+r.labeloffset;break;case"r":r.x+=r.width/2+r.labeloffset;break}})}function fr(n){s(n.edges(),function(e){var r=n.edge(e);r.reversed&&r.points.reverse()})}function hr(n){s(n.nodes(),function(e){if(n.children(e).length){var r=n.node(e),t=n.node(r.borderTop),o=n.node(r.borderBottom),a=n.node(T(r.borderLeft)),i=n.node(T(r.borderRight));r.width=Math.abs(i.x-a.x),r.height=Math.abs(o.y-t.y),r.x=a.x+r.width/2,r.y=t.y+r.height/2}}),s(n.nodes(),function(e){n.node(e).dummy==="border"&&n.removeNode(e)})}function gr(n){s(n.edges(),function(e){if(e.v===e.w){var r=n.node(e.v);r.selfEdges||(r.selfEdges=[]),r.selfEdges.push({e,label:n.edge(e)}),n.removeEdge(e)}})}function vr(n){var e=S(n);s(e,function(r){var t=0;s(r,function(o,a){var i=n.node(o);i.order=a+t,s(i.selfEdges,function(u){N(n,"selfedge",{width:u.label.width,height:u.label.height,rank:i.rank,order:a+ ++t,e:u.e,label:u.label},"_se")}),delete i.selfEdges})})}function lr(n){s(n.nodes(),function(e){var r=n.node(e);if(r.dummy==="selfedge"){var t=n.node(r.e.v),o=t.x+t.width/2,a=t.y,i=r.x-o,u=t.height/2;n.setEdge(r.e,r.label),n.removeNode(e),r.label.points=[{x:o+2*i/3,y:a-u},{x:o+5*i/6,y:a-u},{x:o+i,y:a},{x:o+5*i/6,y:a+u},{x:o+2*i/3,y:a+u}],r.label.x=r.x,r.label.y=r.y}})}function B(n,e){return C(L(n,e),Number)}function q(n){var e={};return s(n,function(r,t){e[t.toLowerCase()]=r}),e}export{xr as l};
//# sourceMappingURL=layout-0JowWxPT.chunk.mjs.map