import{j as n}from"./dayjs.DCWbrgJ0.js";import{c as e}from"./exceljs.DLSZe_6I.js";import{r}from"./graphlib.CqVsUrOV.js";import{p as t,r as o,q as a,s as i,d as u,t as f,u as c,v as d,w as s,x as h,y as g,z as v,A as l,e as p,B as m,g as E,k as w,C as b,D as y,E as x,F as k,l as N,m as I,G as _,n as R,H as C}from"./lodash.D-BGNLlY.js";var L,M,T,B,G,P,j,S,O,V,q,z,F,D,U,Y,A,W,X,H,J,$,K,Q,Z,nn,en,rn,tn,on,an,un,fn,cn,dn,sn,hn,gn,vn,ln,pn,mn,En,wn,bn,yn,xn,kn,Nn,In,_n,Rn,Cn,Ln,Mn,Tn,Bn,Gn,Pn,jn;function Sn(){if(M)return L;var n;if(M=1,"function"==typeof e)try{n=r()}catch(t){}return n||(n=window.graphlib),L=n}function On(){if(B)return T;var n;if(B=1,"function"==typeof e)try{n={cloneDeep:C(),constant:R(),defaults:_(),each:I(),filter:N(),find:k(),flatten:x(),forEach:y(),forIn:b(),has:w(),isUndefined:E(),last:m(),map:p(),mapValues:l(),max:v(),merge:g(),min:h(),minBy:s(),now:d(),pick:c(),range:f(),reduce:u(),sortBy:i(),uniqueId:a(),values:o(),zipObject:t()}}catch(r){}return n||(n=window._),T=n}function Vn(){if(S)return j;S=1;var n=On(),e=Sn().Graph,r=function(){if(P)return G;function n(){var n={};n._next=n._prev=n,this._sentinel=n}function e(n){n._prev._next=n._next,n._next._prev=n._prev,delete n._next,delete n._prev}function r(n,e){if("_next"!==n&&"_prev"!==n)return e}return P=1,G=n,n.prototype.dequeue=function(){var n=this._sentinel,r=n._prev;if(r!==n)return e(r),r},n.prototype.enqueue=function(n){var r=this._sentinel;n._prev&&n._next&&e(n),n._next=r._next,r._next._prev=n,r._next=n,n._prev=r},n.prototype.toString=function(){for(var n=[],e=this._sentinel,t=e._prev;t!==e;)n.push(JSON.stringify(t,r)),t=t._prev;return"["+n.join(", ")+"]"},G}();j=function(i,u){if(i.nodeCount()<=1)return[];var f=function(t,o){var i=new e,u=0,f=0;n.forEach(t.nodes(),function(n){i.setNode(n,{v:n,in:0,out:0})}),n.forEach(t.edges(),function(n){var e=i.edge(n.v,n.w)||0,r=o(n),t=e+r;i.setEdge(n.v,n.w,t),f=Math.max(f,i.node(n.v).out+=r),u=Math.max(u,i.node(n.w).in+=r)});var c=n.range(f+u+3).map(function(){return new r}),d=u+1;return n.forEach(i.nodes(),function(n){a(c,d,i.node(n))}),{graph:i,buckets:c,zeroIdx:d}}(i,u||t),c=function(n,e,r){var t,a=[],i=e[e.length-1],u=e[0];for(;n.nodeCount();){for(;t=u.dequeue();)o(n,e,r,t);for(;t=i.dequeue();)o(n,e,r,t);if(n.nodeCount())for(var f=e.length-2;f>0;--f)if(t=e[f].dequeue()){a=a.concat(o(n,e,r,t,!0));break}}return a}(f.graph,f.buckets,f.zeroIdx);return n.flatten(n.map(c,function(n){return i.outEdges(n.v,n.w)}),!0)};var t=n.constant(1);function o(e,r,t,o,i){var u=i?[]:void 0;return n.forEach(e.inEdges(o.v),function(n){var o=e.edge(n),f=e.node(n.v);i&&u.push({v:n.v,w:n.w}),f.out-=o,a(r,t,f)}),n.forEach(e.outEdges(o.v),function(n){var o=e.edge(n),i=n.w,u=e.node(i);u.in-=o,a(r,t,u)}),e.removeNode(o.v),u}function a(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)}return j}function qn(){if(V)return O;V=1;var n=On(),e=Vn();return O={run:function(r){var t="greedy"===r.graph().acyclicer?e(r,(o=r,function(n){return o.edge(n).weight})):function(e){var r=[],t={},o={};function a(i){n.has(o,i)||(o[i]=!0,t[i]=!0,n.forEach(e.outEdges(i),function(e){n.has(t,e.w)?r.push(e):a(e.w)}),delete t[i])}return n.forEach(e.nodes(),a),r}(r);var o;n.forEach(t,function(e){var t=r.edge(e);r.removeEdge(e),t.forwardName=e.name,t.reversed=!0,r.setEdge(e.w,e.v,t,n.uniqueId("rev"))})},undo:function(e){n.forEach(e.edges(),function(n){var r=e.edge(n);if(r.reversed){e.removeEdge(n);var t=r.forwardName;delete r.reversed,delete r.forwardName,e.setEdge(n.w,n.v,r,t)}})}}}function zn(){if(z)return q;z=1;var n=On(),e=Sn().Graph;function r(e,r,t,o){var a;do{a=n.uniqueId(o)}while(e.hasNode(a));return t.dummy=r,e.setNode(a,t),a}function t(e){return n.max(n.map(e.nodes(),function(r){var t=e.node(r).rank;if(!n.isUndefined(t))return t}))}return q={addDummyNode:r,simplify:function(r){var t=(new e).setGraph(r.graph());return n.forEach(r.nodes(),function(n){t.setNode(n,r.node(n))}),n.forEach(r.edges(),function(n){var e=t.edge(n.v,n.w)||{weight:0,minlen:1},o=r.edge(n);t.setEdge(n.v,n.w,{weight:e.weight+o.weight,minlen:Math.max(e.minlen,o.minlen)})}),t},asNonCompoundGraph:function(r){var t=new e({multigraph:r.isMultigraph()}).setGraph(r.graph());return n.forEach(r.nodes(),function(n){r.children(n).length||t.setNode(n,r.node(n))}),n.forEach(r.edges(),function(n){t.setEdge(n,r.edge(n))}),t},successorWeights:function(e){var r=n.map(e.nodes(),function(r){var t={};return n.forEach(e.outEdges(r),function(n){t[n.w]=(t[n.w]||0)+e.edge(n).weight}),t});return n.zipObject(e.nodes(),r)},predecessorWeights:function(e){var r=n.map(e.nodes(),function(r){var t={};return n.forEach(e.inEdges(r),function(n){t[n.v]=(t[n.v]||0)+e.edge(n).weight}),t});return n.zipObject(e.nodes(),r)},intersectRect:function(n,e){var r,t,o=n.x,a=n.y,i=e.x-o,u=e.y-a,f=n.width/2,c=n.height/2;if(!i&&!u)throw new Error("Not possible to find intersection inside of the rectangle");Math.abs(u)*f>Math.abs(i)*c?(u<0&&(c=-c),r=c*i/u,t=c):(i<0&&(f=-f),r=f,t=f*u/i);return{x:o+r,y:a+t}},buildLayerMatrix:function(e){var r=n.map(n.range(t(e)+1),function(){return[]});return n.forEach(e.nodes(),function(t){var o=e.node(t),a=o.rank;n.isUndefined(a)||(r[a][o.order]=t)}),r},normalizeRanks:function(e){var r=n.min(n.map(e.nodes(),function(n){return e.node(n).rank}));n.forEach(e.nodes(),function(t){var o=e.node(t);n.has(o,"rank")&&(o.rank-=r)})},removeEmptyRanks:function(e){var r=n.min(n.map(e.nodes(),function(n){return e.node(n).rank})),t=[];n.forEach(e.nodes(),function(n){var o=e.node(n).rank-r;t[o]||(t[o]=[]),t[o].push(n)});var o=0,a=e.graph().nodeRankFactor;n.forEach(t,function(r,t){n.isUndefined(r)&&t%a!==0?--o:o&&n.forEach(r,function(n){e.node(n).rank+=o})})},addBorderNode:function(n,e,t,o){var a={width:0,height:0};arguments.length>=4&&(a.rank=t,a.order=o);return r(n,"border",a,e)},maxRank:t,partition:function(e,r){var t={lhs:[],rhs:[]};return n.forEach(e,function(n){r(n)?t.lhs.push(n):t.rhs.push(n)}),t},time:function(e,r){n.now();try{return r()}finally{}},notime:function(n,e){return e()}},q}function Fn(){if(D)return F;D=1;var n=On(),e=zn();return F={run:function(r){r.graph().dummyChains=[],n.forEach(r.edges(),function(n){!function(n,r){var t,o,a,i=r.v,u=n.node(i).rank,f=r.w,c=n.node(f).rank,d=r.name,s=n.edge(r),h=s.labelRank;if(c===u+1)return;for(n.removeEdge(r),a=0,++u;u<c;++a,++u)s.points=[],o={width:0,height:0,edgeLabel:s,edgeObj:r,rank:u},t=e.addDummyNode(n,"edge",o,"_d"),u===h&&(o.width=s.width,o.height=s.height,o.dummy="edge-label",o.labelpos=s.labelpos),n.setEdge(i,t,{weight:s.weight},d),0===a&&n.graph().dummyChains.push(t),i=t;n.setEdge(i,f,{weight:s.weight},d)}(r,n)})},undo:function(e){n.forEach(e.graph().dummyChains,function(n){var r,t=e.node(n),o=t.edgeLabel;for(e.setEdge(t.edgeObj,o);t.dummy;)r=e.successors(n)[0],e.removeNode(n),o.points.push({x:t.x,y:t.y}),"edge-label"===t.dummy&&(o.x=t.x,o.y=t.y,o.width=t.width,o.height=t.height),n=r,t=e.node(n)})}}}function Dn(){if(Y)return U;Y=1;var n=On();return U={longestPath:function(e){var r={};n.forEach(e.sources(),function t(o){var a=e.node(o);if(n.has(r,o))return a.rank;r[o]=!0;var i=n.min(n.map(e.outEdges(o),function(n){return t(n.w)-e.edge(n).minlen}));return i!==Number.POSITIVE_INFINITY&&null!=// return value of _.map([]) for Lodash 3
i||(i=0),a.rank=i})},slack:function(n,e){return n.node(e.w).rank-n.node(e.v).rank-n.edge(e).minlen}}}function Un(){if(W)return A;W=1;var n=On(),e=Sn().Graph,r=Dn().slack;function t(e,t){return n.forEach(e.nodes(),function o(a){n.forEach(t.nodeEdges(a),function(n){var i=n.v,u=a===i?n.w:i;e.hasNode(u)||r(t,n)||(e.setNode(u,{}),e.setEdge(a,u,{}),o(u))})}),e.nodeCount()}function o(e,t){return n.minBy(t.edges(),function(n){if(e.hasNode(n.v)!==e.hasNode(n.w))return r(t,n)})}function a(e,r,t){n.forEach(e.nodes(),function(n){r.node(n).rank+=t})}return A=function(n){var i,u,f=new e({directed:!1}),c=n.nodes()[0],d=n.nodeCount();f.setNode(c,{});for(;t(f,n)<d;)i=o(f,n),u=f.hasNode(i.v)?r(n,i):-r(n,i),a(f,n,u);return f}}function Yn(){if(H)return X;H=1;var n=On(),e=Un(),r=Dn().slack,t=Dn().longestPath,o=Sn().alg.preorder,a=Sn().alg.postorder,i=zn().simplify;function u(n){n=i(n),t(n);var r,o=e(n);for(d(o),f(o,n);r=h(o);)v(o,n,r,g(o,n,r))}function f(e,r){var t=a(e,e.nodes());t=t.slice(0,t.length-1),n.forEach(t,function(n){!function(n,e,r){var t=n.node(r),o=t.parent;n.edge(r,o).cutvalue=c(n,e,r)}(e,r,n)})}function c(e,r,t){var o=e.node(t).parent,a=!0,i=r.edge(t,o),u=0;return i||(a=!1,i=r.edge(o,t)),u=i.weight,n.forEach(r.nodeEdges(t),function(n){var i,f,c=n.v===t,d=c?n.w:n.v;if(d!==o){var s=c===a,h=r.edge(n).weight;if(u+=s?h:-h,i=t,f=d,e.hasEdge(i,f)){var g=e.edge(t,d).cutvalue;u+=s?-g:g}}}),u}function d(n,e){arguments.length<2&&(e=n.nodes()[0]),s(n,{},1,e)}function s(e,r,t,o,a){var i=t,u=e.node(o);return r[o]=!0,n.forEach(e.neighbors(o),function(a){n.has(r,a)||(t=s(e,r,t,a,o))}),u.low=i,u.lim=t++,a?u.parent=a:delete u.parent,t}function h(e){return n.find(e.edges(),function(n){return e.edge(n).cutvalue<0})}function g(e,t,o){var a=o.v,i=o.w;t.hasEdge(a,i)||(a=o.w,i=o.v);var u=e.node(a),f=e.node(i),c=u,d=!1;u.lim>f.lim&&(c=f,d=!0);var s=n.filter(t.edges(),function(n){return d===l(e,e.node(n.v),c)&&d!==l(e,e.node(n.w),c)});return n.minBy(s,function(n){return r(t,n)})}function v(e,r,t,a){var i=t.v,u=t.w;e.removeEdge(i,u),e.setEdge(a.v,a.w,{}),d(e),f(e,r),function(e,r){var t=n.find(e.nodes(),function(n){return!r.node(n).parent}),a=o(e,t);a=a.slice(1),n.forEach(a,function(n){var t=e.node(n).parent,o=r.edge(n,t),a=!1;o||(o=r.edge(t,n),a=!0),r.node(n).rank=r.node(t).rank+(a?o.minlen:-o.minlen)})}(e,r)}function l(n,e,r){return r.low<=e.lim&&e.lim<=r.lim}return X=u,u.initLowLimValues=d,u.initCutValues=f,u.calcCutValue=c,u.leaveEdge=h,u.enterEdge=g,u.exchangeEdges=v,X}function An(){if($)return J;$=1;var n=Dn().longestPath,e=Un(),r=Yn();J=function(r){switch(r.graph().ranker){case"network-simplex":default:o(r);break;case"tight-tree":!function(r){n(r),e(r)}(r);break;case"longest-path":t(r)}};var t=n;function o(n){r(n)}return J}function Wn(){if(Q)return K;Q=1;var n=On();return K=function(e){var r=function(e){var r={},t=0;function o(a){var i=t;n.forEach(e.children(a),o),r[a]={low:i,lim:t++}}return n.forEach(e.children(),o),r}(e);n.forEach(e.graph().dummyChains,function(n){for(var t=e.node(n),o=t.edgeObj,a=function(n,e,r,t){var o,a,i=[],u=[],f=Math.min(e[r].low,e[t].low),c=Math.max(e[r].lim,e[t].lim);o=r;do{o=n.parent(o),i.push(o)}while(o&&(e[o].low>f||c>e[o].lim));a=o,o=t;for(;(o=n.parent(o))!==a;)u.push(o);return{path:i.concat(u.reverse()),lca:a}}(e,r,o.v,o.w),i=a.path,u=a.lca,f=0,c=i[f],d=!0;n!==o.w;){if(t=e.node(n),d){for(;(c=i[f])!==u&&e.node(c).maxRank<t.rank;)f++;c===u&&(d=!1)}if(!d){for(;f<i.length-1&&e.node(c=i[f+1]).minRank<=t.rank;)f++;c=i[f]}e.setParent(n,c),n=e.successors(n)[0]}})}}function Xn(){if(nn)return Z;nn=1;var n=On(),e=zn();function r(t,o,a,i,u,f,c){var d=t.children(c);if(d.length){var s=e.addBorderNode(t,"_bt"),h=e.addBorderNode(t,"_bb"),g=t.node(c);t.setParent(s,c),g.borderTop=s,t.setParent(h,c),g.borderBottom=h,n.forEach(d,function(n){r(t,o,a,i,u,f,n);var e=t.node(n),d=e.borderTop?e.borderTop:n,g=e.borderBottom?e.borderBottom:n,v=e.borderTop?i:2*i,l=d!==g?1:u-f[c]+1;t.setEdge(s,d,{weight:v,minlen:l,nestingEdge:!0}),t.setEdge(g,h,{weight:v,minlen:l,nestingEdge:!0})}),t.parent(c)||t.setEdge(o,s,{weight:0,minlen:u+f[c]})}else c!==o&&t.setEdge(o,c,{weight:0,minlen:a})}return Z={run:function(t){var o=e.addDummyNode(t,"root",{},"_root"),a=function(e){var r={};function t(o,a){var i=e.children(o);i&&i.length&&n.forEach(i,function(n){t(n,a+1)}),r[o]=a}return n.forEach(e.children(),function(n){t(n,1)}),r}(t),i=n.max(n.values(a))-1,u=2*i+1;t.graph().nestingRoot=o,n.forEach(t.edges(),function(n){t.edge(n).minlen*=u});var f=function(e){return n.reduce(e.edges(),function(n,r){return n+e.edge(r).weight},0)}(t)+1;n.forEach(t.children(),function(n){r(t,o,u,f,i,a,n)}),t.graph().nodeRankFactor=u},cleanup:function(e){var r=e.graph();e.removeNode(r.nestingRoot),delete r.nestingRoot,n.forEach(e.edges(),function(n){e.edge(n).nestingEdge&&e.removeEdge(n)})}}}function Hn(){if(on)return tn;on=1;var n=On();function e(e){n.forEach(e.nodes(),function(n){r(e.node(n))}),n.forEach(e.edges(),function(n){r(e.edge(n))})}function r(n){var e=n.width;n.width=n.height,n.height=e}function t(n){n.y=-n.y}function o(n){var e=n.x;n.x=n.y,n.y=e}return tn={adjust:function(n){var r=n.graph().rankdir.toLowerCase();"lr"!==r&&"rl"!==r||e(n)},undo:function(r){var a=r.graph().rankdir.toLowerCase();"bt"!==a&&"rl"!==a||function(e){n.forEach(e.nodes(),function(n){t(e.node(n))}),n.forEach(e.edges(),function(r){var o=e.edge(r);n.forEach(o.points,t),n.has(o,"y")&&t(o)})}(r);"lr"!==a&&"rl"!==a||(!function(e){n.forEach(e.nodes(),function(n){o(e.node(n))}),n.forEach(e.edges(),function(r){var t=e.edge(r);n.forEach(t.points,o),n.has(t,"x")&&o(t)})}(r),e(r))}}}function Jn(){if(gn)return hn;gn=1;var n=On();return hn=function(e,r){var t={};return n.forEach(e,function(e,r){var o=t[e.v]={indegree:0,in:[],out:[],vs:[e.v],i:r};n.isUndefined(e.barycenter)||(o.barycenter=e.barycenter,o.weight=e.weight)}),n.forEach(r.edges(),function(e){var r=t[e.v],o=t[e.w];n.isUndefined(r)||n.isUndefined(o)||(o.indegree++,r.out.push(t[e.w]))}),function(e){var r=[];function t(e){return function(r){r.merged||(n.isUndefined(r.barycenter)||n.isUndefined(e.barycenter)||r.barycenter>=e.barycenter)&&function(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}(e,r)}}function o(n){return function(r){r.in.push(n),0===--r.indegree&&e.push(r)}}for(;e.length;){var a=e.pop();r.push(a),n.forEach(a.in.reverse(),t(a)),n.forEach(a.out,o(a))}return n.map(n.filter(r,function(n){return!n.merged}),function(e){return n.pick(e,["vs","i","barycenter","weight"])})}(n.filter(t,function(n){return!n.indegree}))}}function $n(){if(mn)return pn;mn=1;var n=On(),e=function(){if(sn)return dn;sn=1;var n=On();return dn=function(e,r){return n.map(r,function(r){var t=e.inEdges(r);if(t.length){var o=n.reduce(t,function(n,r){var t=e.edge(r),o=e.node(r.v);return{sum:n.sum+t.weight*o.order,weight:n.weight+t.weight}},{sum:0,weight:0});return{v:r,barycenter:o.sum/o.weight,weight:o.weight}}return{v:r}})}}(),r=Jn(),t=function(){if(ln)return vn;ln=1;var n=On(),e=zn();function r(e,r,t){for(var o;r.length&&(o=n.last(r)).i<=t;)r.pop(),e.push(o.vs),t++;return t}return vn=function(t,o){var a,i=e.partition(t,function(e){return n.has(e,"barycenter")}),u=i.lhs,f=n.sortBy(i.rhs,function(n){return-n.i}),c=[],d=0,s=0,h=0;u.sort((a=!!o,function(n,e){return n.barycenter<e.barycenter?-1:n.barycenter>e.barycenter?1:a?e.i-n.i:n.i-e.i})),h=r(c,f,h),n.forEach(u,function(n){h+=n.vs.length,c.push(n.vs),d+=n.barycenter*n.weight,s+=n.weight,h=r(c,f,h)});var g={vs:n.flatten(c,!0)};return s&&(g.barycenter=d/s,g.weight=s),g}}();return pn=function o(a,i,u,f){var c=a.children(i),d=a.node(i),s=d?d.borderLeft:void 0,h=d?d.borderRight:void 0,g={};s&&(c=n.filter(c,function(n){return n!==s&&n!==h}));var v=e(a,c);n.forEach(v,function(e){if(a.children(e.v).length){var r=o(a,e.v,u,f);g[e.v]=r,n.has(r,"barycenter")&&(t=e,i=r,n.isUndefined(t.barycenter)?(t.barycenter=i.barycenter,t.weight=i.weight):(t.barycenter=(t.barycenter*t.weight+i.barycenter*i.weight)/(t.weight+i.weight),t.weight+=i.weight))}var t,i});var l=r(v,u);!function(e,r){n.forEach(e,function(e){e.vs=n.flatten(e.vs.map(function(n){return r[n]?r[n].vs:n}),!0)})}(l,g);var p=t(l,f);if(s&&(p.vs=n.flatten([s,p.vs,h],!0),a.predecessors(s).length)){var m=a.node(a.predecessors(s)[0]),E=a.node(a.predecessors(h)[0]);n.has(p,"barycenter")||(p.barycenter=0,p.weight=0),p.barycenter=(p.barycenter*p.weight+m.order+E.order)/(p.weight+2),p.weight+=2}return p},pn}function Kn(){if(wn)return En;wn=1;var n=On(),e=Sn().Graph;return En=function(r,t,o){var a=function(e){var r;for(;e.hasNode(r=n.uniqueId("_root")););return r}(r),i=new e({compound:!0}).setGraph({root:a}).setDefaultNodeLabel(function(n){return r.node(n)});return n.forEach(r.nodes(),function(e){var u=r.node(e),f=r.parent(e);(u.rank===t||u.minRank<=t&&t<=u.maxRank)&&(i.setNode(e),i.setParent(e,f||a),n.forEach(r[o](e),function(t){var o=t.v===e?t.w:t.v,a=i.edge(o,e),u=n.isUndefined(a)?0:a.weight;i.setEdge(o,e,{weight:r.edge(t).weight+u})}),n.has(u,"minRank")&&i.setNode(e,{borderLeft:u.borderLeft[t],borderRight:u.borderRight[t]}))}),i}}function Qn(){if(kn)return xn;kn=1;var n=On(),e=function(){if(un)return an;un=1;var n=On();return an=function(e){var r={},t=n.filter(e.nodes(),function(n){return!e.children(n).length}),o=n.max(n.map(t,function(n){return e.node(n).rank})),a=n.map(n.range(o+1),function(){return[]}),i=n.sortBy(t,function(n){return e.node(n).rank});return n.forEach(i,function t(o){if(!n.has(r,o)){r[o]=!0;var i=e.node(o);a[i.rank].push(o),n.forEach(e.successors(o),t)}}),a}}(),r=function(){if(cn)return fn;cn=1;var n=On();function e(e,r,t){for(var o=n.zipObject(t,n.map(t,function(n,e){return e})),a=n.flatten(n.map(r,function(r){return n.sortBy(n.map(e.outEdges(r),function(n){return{pos:o[n.w],weight:e.edge(n).weight}}),"pos")}),!0),i=1;i<t.length;)i<<=1;var u=2*i-1;i-=1;var f=n.map(new Array(u),function(){return 0}),c=0;return n.forEach(a.forEach(function(n){var e=n.pos+i;f[e]+=n.weight;for(var r=0;e>0;)e%2&&(r+=f[e+1]),f[e=e-1>>1]+=n.weight;c+=n.weight*r})),c}return fn=function(n,r){for(var t=0,o=1;o<r.length;++o)t+=e(n,r[o-1],r[o]);return t}}(),t=$n(),o=Kn(),a=function(){if(yn)return bn;yn=1;var n=On();return bn=function(e,r,t){var o,a={};n.forEach(t,function(n){for(var t,i,u=e.parent(n);u;){if((t=e.parent(u))?(i=a[t],a[t]=u):(i=o,o=u),i&&i!==u)return void r.setEdge(i,u);u=t}})}}(),i=Sn().Graph,u=zn();function f(e,r,t){return n.map(r,function(n){return o(e,n,t)})}function c(e,r){var o=new i;n.forEach(e,function(e){var i=e.graph().root,u=t(e,i,o,r);n.forEach(u.vs,function(n,r){e.node(n).order=r}),a(e,o,u.vs)})}function d(e,r){n.forEach(r,function(r){n.forEach(r,function(n,r){e.node(n).order=r})})}return xn=function(t){var o=u.maxRank(t),a=f(t,n.range(1,o+1),"inEdges"),i=f(t,n.range(o-1,-1,-1),"outEdges"),s=e(t);d(t,s);for(var h,g=Number.POSITIVE_INFINITY,v=0,l=0;l<4;++v,++l){c(v%2?a:i,v%4>=2),s=u.buildLayerMatrix(t);var p=r(t,s);p<g&&(l=0,h=n.cloneDeep(s),g=p)}d(t,h)}}function Zn(){if(In)return Nn;In=1;var n=On(),e=Sn().Graph,r=zn();function t(e,r){var t={};return n.reduce(r,function(r,o){var i=0,u=0,f=r.length,c=n.last(o);return n.forEach(o,function(r,d){var s=function(e,r){if(e.node(r).dummy)return n.find(e.predecessors(r),function(n){return e.node(n).dummy})}(e,r),h=s?e.node(s).order:f;(s||r===c)&&(n.forEach(o.slice(u,d+1),function(r){n.forEach(e.predecessors(r),function(n){var o=e.node(n),u=o.order;!(u<i||h<u)||o.dummy&&e.node(r).dummy||a(t,n,r)})}),u=d+1,i=h)}),o}),t}function o(e,r){var t={};function o(r,o,i,u,f){var c;n.forEach(n.range(o,i),function(o){c=r[o],e.node(c).dummy&&n.forEach(e.predecessors(c),function(n){var r=e.node(n);r.dummy&&(r.order<u||r.order>f)&&a(t,n,c)})})}return n.reduce(r,function(r,t){var a,i=-1,u=0;return n.forEach(t,function(n,f){if("border"===e.node(n).dummy){var c=e.predecessors(n);c.length&&(a=e.node(c[0]).order,o(t,u,f,i,a),u=f,i=a)}o(t,u,t.length,a,r.length)}),t}),t}function a(n,e,r){if(e>r){var t=e;e=r,r=t}var o=n[e];o||(n[e]=o={}),o[r]=!0}function i(e,r,t){if(r>t){var o=r;r=t,t=o}return n.has(e[r],t)}function u(e,r,t,o){var a={},u={},f={};return n.forEach(r,function(e){n.forEach(e,function(n,e){a[n]=n,u[n]=n,f[n]=e})}),n.forEach(r,function(e){var r=-1;n.forEach(e,function(e){var c=o(e);if(c.length)for(var d=((c=n.sortBy(c,function(n){return f[n]})).length-1)/2,s=Math.floor(d),h=Math.ceil(d);s<=h;++s){var g=c[s];u[e]===e&&r<f[g]&&!i(t,e,g)&&(u[g]=e,u[e]=a[e]=a[g],r=f[g])}})}),{root:a,align:u}}function f(r,t,o,a,i){var u={},f=function(r,t,o,a){var i=new e,u=r.graph(),f=function(e,r,t){return function(o,a,i){var u,f=o.node(a),c=o.node(i),d=0;if(d+=f.width/2,n.has(f,"labelpos"))switch(f.labelpos.toLowerCase()){case"l":u=-f.width/2;break;case"r":u=f.width/2}if(u&&(d+=t?u:-u),u=0,d+=(f.dummy?r:e)/2,d+=(c.dummy?r:e)/2,d+=c.width/2,n.has(c,"labelpos"))switch(c.labelpos.toLowerCase()){case"l":u=c.width/2;break;case"r":u=-c.width/2}return u&&(d+=t?u:-u),u=0,d}}(u.nodesep,u.edgesep,a);return n.forEach(t,function(e){var t;n.forEach(e,function(n){var e=o[n];if(i.setNode(e),t){var a=o[t],u=i.edge(a,e);i.setEdge(a,e,Math.max(f(r,n,t),u||0))}t=n})}),i}(r,t,o,i),c=i?"borderLeft":"borderRight";function d(n,e){for(var r=f.nodes(),t=r.pop(),o={};t;)o[t]?n(t):(o[t]=!0,r.push(t),r=r.concat(e(t))),t=r.pop()}return d(function(n){u[n]=f.inEdges(n).reduce(function(n,e){return Math.max(n,u[e.v]+f.edge(e))},0)},f.predecessors.bind(f)),d(function(n){var e=f.outEdges(n).reduce(function(n,e){return Math.min(n,u[e.w]-f.edge(e))},Number.POSITIVE_INFINITY),t=r.node(n);e!==Number.POSITIVE_INFINITY&&t.borderType!==c&&(u[n]=Math.max(u[n],e))},f.successors.bind(f)),n.forEach(a,function(n){u[n]=u[o[n]]}),u}function c(e,r){return n.minBy(n.values(r),function(r){var t=Number.NEGATIVE_INFINITY,o=Number.POSITIVE_INFINITY;return n.forIn(r,function(n,r){var a=function(n,e){return n.node(e).width}(e,r)/2;t=Math.max(n+a,t),o=Math.min(n-a,o)}),t-o})}function d(e,r){var t=n.values(r),o=n.min(t),a=n.max(t);n.forEach(["u","d"],function(t){n.forEach(["l","r"],function(i){var u,f=t+i,c=e[f];if(c!==r){var d=n.values(c);(u="l"===i?o-n.min(d):a-n.max(d))&&(e[f]=n.mapValues(c,function(n){return n+u}))}})})}function s(e,r){return n.mapValues(e.ul,function(t,o){if(r)return e[r.toLowerCase()][o];var a=n.sortBy(n.map(e,o));return(a[1]+a[2])/2})}return Nn={positionX:function(e){var a,i=r.buildLayerMatrix(e),h=n.merge(t(e,i),o(e,i)),g={};n.forEach(["u","d"],function(r){a="u"===r?i:n.values(i).reverse(),n.forEach(["l","r"],function(t){"r"===t&&(a=n.map(a,function(e){return n.values(e).reverse()}));var o=("u"===r?e.predecessors:e.successors).bind(e),i=u(e,a,h,o),c=f(e,a,i.root,i.align,"r"===t);"r"===t&&(c=n.mapValues(c,function(n){return-n})),g[r+t]=c})});var v=c(e,g);return d(g,v),s(g,e.graph().align)},findType1Conflicts:t,findType2Conflicts:o,addConflict:a,hasConflict:i,verticalAlignment:u,horizontalCompaction:f,alignCoordinates:d,findSmallestWidthAlignment:c,balance:s}}function ne(){if(Rn)return _n;Rn=1;var n=On(),e=zn(),r=Zn().positionX;return _n=function(t){(function(r){var t=e.buildLayerMatrix(r),o=r.graph().ranksep,a=0;n.forEach(t,function(e){var t=n.max(n.map(e,function(n){return r.node(n).height}));n.forEach(e,function(n){r.node(n).y=a+t/2}),a+=t+o})})(t=e.asNonCompoundGraph(t)),n.forEach(r(t),function(n,e){t.node(e).x=n})}}function ee(){if(Ln)return Cn;Ln=1;var n=On(),e=qn(),r=Fn(),t=An(),o=zn().normalizeRanks,a=Wn(),i=zn().removeEmptyRanks,u=Xn(),f=function(){if(rn)return en;rn=1;var n=On(),e=zn();function r(n,r,t,o,a,i){var u={width:0,height:0,rank:i,borderType:r},f=a[r][i-1],c=e.addDummyNode(n,"border",u,t);a[r][i]=c,n.setParent(c,o),f&&n.setEdge(f,c,{weight:1})}return en=function(e){n.forEach(e.children(),function t(o){var a=e.children(o),i=e.node(o);if(a.length&&n.forEach(a,t),n.has(i,"minRank")){i.borderLeft=[],i.borderRight=[];for(var u=i.minRank,f=i.maxRank+1;u<f;++u)r(e,"borderLeft","_bl",o,i,u),r(e,"borderRight","_br",o,i,u)}})}}(),c=Hn(),d=Qn(),s=ne(),h=zn(),g=Sn().Graph;Cn=function(N,I){var _=I&&I.debugTiming?h.time:h.notime;_("layout",function(){var I=_("  buildLayoutGraph",function(){return function(e){var r=new g({multigraph:!0,compound:!0}),t=k(e.graph());return r.setGraph(n.merge({},l,x(t,v),n.pick(t,p))),n.forEach(e.nodes(),function(t){var o=k(e.node(t));r.setNode(t,n.defaults(x(o,m),E)),r.setParent(t,e.parent(t))}),n.forEach(e.edges(),function(t){var o=k(e.edge(t));r.setEdge(t,n.merge({},b,x(o,w),n.pick(o,y)))}),r}(N)});_("  runLayout",function(){!function(g,v){v("    makeSpaceForEdgeLabels",function(){!function(e){var r=e.graph();r.ranksep/=2,n.forEach(e.edges(),function(n){var t=e.edge(n);t.minlen*=2,"c"!==t.labelpos.toLowerCase()&&("TB"===r.rankdir||"BT"===r.rankdir?t.width+=t.labeloffset:t.height+=t.labeloffset)})}(g)}),v("    removeSelfEdges",function(){!function(e){n.forEach(e.edges(),function(n){if(n.v===n.w){var r=e.node(n.v);r.selfEdges||(r.selfEdges=[]),r.selfEdges.push({e:n,label:e.edge(n)}),e.removeEdge(n)}})}(g)}),v("    acyclic",function(){e.run(g)}),v("    nestingGraph.run",function(){u.run(g)}),v("    rank",function(){t(h.asNonCompoundGraph(g))}),v("    injectEdgeLabelProxies",function(){!function(e){n.forEach(e.edges(),function(n){var r=e.edge(n);if(r.width&&r.height){var t=e.node(n.v),o={rank:(e.node(n.w).rank-t.rank)/2+t.rank,e:n};h.addDummyNode(e,"edge-proxy",o,"_ep")}})}(g)}),v("    removeEmptyRanks",function(){i(g)}),v("    nestingGraph.cleanup",function(){u.cleanup(g)}),v("    normalizeRanks",function(){o(g)}),v("    assignRankMinMax",function(){!function(e){var r=0;n.forEach(e.nodes(),function(t){var o=e.node(t);o.borderTop&&(o.minRank=e.node(o.borderTop).rank,o.maxRank=e.node(o.borderBottom).rank,r=n.max(r,o.maxRank))}),e.graph().maxRank=r}(g)}),v("    removeEdgeLabelProxies",function(){!function(e){n.forEach(e.nodes(),function(n){var r=e.node(n);"edge-proxy"===r.dummy&&(e.edge(r.e).labelRank=r.rank,e.removeNode(n))})}(g)}),v("    normalize.run",function(){r.run(g)}),v("    parentDummyChains",function(){a(g)}),v("    addBorderSegments",function(){f(g)}),v("    order",function(){d(g)}),v("    insertSelfEdges",function(){!function(e){var r=h.buildLayerMatrix(e);n.forEach(r,function(r){var t=0;n.forEach(r,function(r,o){var a=e.node(r);a.order=o+t,n.forEach(a.selfEdges,function(n){h.addDummyNode(e,"selfedge",{width:n.label.width,height:n.label.height,rank:a.rank,order:o+ ++t,e:n.e,label:n.label},"_se")}),delete a.selfEdges})})}(g)}),v("    adjustCoordinateSystem",function(){c.adjust(g)}),v("    position",function(){s(g)}),v("    positionSelfEdges",function(){!function(e){n.forEach(e.nodes(),function(n){var r=e.node(n);if("selfedge"===r.dummy){var t=e.node(r.e.v),o=t.x+t.width/2,a=t.y,i=r.x-o,u=t.height/2;e.setEdge(r.e,r.label),e.removeNode(n),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}})}(g)}),v("    removeBorderNodes",function(){!function(e){n.forEach(e.nodes(),function(r){if(e.children(r).length){var t=e.node(r),o=e.node(t.borderTop),a=e.node(t.borderBottom),i=e.node(n.last(t.borderLeft)),u=e.node(n.last(t.borderRight));t.width=Math.abs(u.x-i.x),t.height=Math.abs(a.y-o.y),t.x=i.x+t.width/2,t.y=o.y+t.height/2}}),n.forEach(e.nodes(),function(n){"border"===e.node(n).dummy&&e.removeNode(n)})}(g)}),v("    normalize.undo",function(){r.undo(g)}),v("    fixupEdgeLabelCoords",function(){!function(e){n.forEach(e.edges(),function(r){var t=e.edge(r);if(n.has(t,"x"))switch("l"!==t.labelpos&&"r"!==t.labelpos||(t.width-=t.labeloffset),t.labelpos){case"l":t.x-=t.width/2+t.labeloffset;break;case"r":t.x+=t.width/2+t.labeloffset}})}(g)}),v("    undoCoordinateSystem",function(){c.undo(g)}),v("    translateGraph",function(){!function(e){var r=Number.POSITIVE_INFINITY,t=0,o=Number.POSITIVE_INFINITY,a=0,i=e.graph(),u=i.marginx||0,f=i.marginy||0;function c(n){var e=n.x,i=n.y,u=n.width,f=n.height;r=Math.min(r,e-u/2),t=Math.max(t,e+u/2),o=Math.min(o,i-f/2),a=Math.max(a,i+f/2)}n.forEach(e.nodes(),function(n){c(e.node(n))}),n.forEach(e.edges(),function(r){var t=e.edge(r);n.has(t,"x")&&c(t)}),r-=u,o-=f,n.forEach(e.nodes(),function(n){var t=e.node(n);t.x-=r,t.y-=o}),n.forEach(e.edges(),function(t){var a=e.edge(t);n.forEach(a.points,function(n){n.x-=r,n.y-=o}),n.has(a,"x")&&(a.x-=r),n.has(a,"y")&&(a.y-=o)}),i.width=t-r+u,i.height=a-o+f}(g)}),v("    assignNodeIntersects",function(){!function(e){n.forEach(e.edges(),function(n){var r,t,o=e.edge(n),a=e.node(n.v),i=e.node(n.w);o.points?(r=o.points[0],t=o.points[o.points.length-1]):(o.points=[],r=i,t=a),o.points.unshift(h.intersectRect(a,r)),o.points.push(h.intersectRect(i,t))})}(g)}),v("    reversePoints",function(){!function(e){n.forEach(e.edges(),function(n){var r=e.edge(n);r.reversed&&r.points.reverse()})}(g)}),v("    acyclic.undo",function(){e.undo(g)})}(I,_)}),_("  updateInputGraph",function(){!function(e,r){n.forEach(e.nodes(),function(n){var t=e.node(n),o=r.node(n);t&&(t.x=o.x,t.y=o.y,r.children(n).length&&(t.width=o.width,t.height=o.height))}),n.forEach(e.edges(),function(t){var o=e.edge(t),a=r.edge(t);o.points=a.points,n.has(a,"x")&&(o.x=a.x,o.y=a.y)}),e.graph().width=r.graph().width,e.graph().height=r.graph().height}(N,I)})})};var v=["nodesep","edgesep","ranksep","marginx","marginy"],l={ranksep:50,edgesep:20,nodesep:50,rankdir:"tb"},p=["acyclicer","ranker","rankdir","align"],m=["width","height"],E={width:0,height:0},w=["minlen","weight","width","height","labeloffset"],b={minlen:1,weight:1,width:0,height:0,labeloffset:10,labelpos:"r"},y=["labelpos"];function x(e,r){return n.mapValues(n.pick(e,r),Number)}function k(e){var r={};return n.forEach(e,function(n,e){r[e.toLowerCase()]=n}),r}return Cn}function re(){if(Tn)return Mn;Tn=1;var n=On(),e=zn(),r=Sn().Graph;return Mn={debugOrdering:function(t){var o=e.buildLayerMatrix(t),a=new r({compound:!0,multigraph:!0}).setGraph({});return n.forEach(t.nodes(),function(n){a.setNode(n,{label:n}),a.setParent(n,"layer"+t.node(n).rank)}),n.forEach(t.edges(),function(n){a.setEdge(n.v,n.w,{},n.name)}),n.forEach(o,function(e,r){var t="layer"+r;a.setNode(t,{rank:"same"}),n.reduce(e,function(n,e){return a.setEdge(n,e,{style:"invis"}),e})}),a}}}const te=n(jn?Pn:(jn=1,Pn={graphlib:Sn(),layout:ee(),debug:re(),util:{time:zn().time,notime:zn().notime},version:Gn?Bn:(Gn=1,Bn="0.8.5")}));export{te as d};