Spaces:
Running
Running
| import{G as e}from"./graph-XoNMemoA.js";import{b as n,e as r,c as t,i as o,f as i,v as a,r as u}from"./_baseUniq-DUj_-ybn.js";import{b as d,a as c,m as s,c as f,h,f as g,l as v,d as l}from"./min-FhCtSWQU.js";import{cd as p,bG as w,cT as m,aj as b,cU as y,cM as x,cV as k,cW as E,B as N,ah as O,cX as _,cY as I}from"./index-BiV-b1K2.js";import{c as P,a as j}from"./_baseEach-DDZLUgL5.js";import{s as R}from"./sortBy-CHDem8Sy.js";function T(e,n){return e>n}function M(e,n){var r={};return n=j(n),P(e,(function(e,t,o){m(r,t,n(e,t,o))})),r}function L(e){return e&&e.length?d(e,b,T):void 0}function C(e,n){return e&&e.length?d(e,j(n),c):void 0}var S=0;function G(e){var n=++S;return y(e)+n}class V{constructor(){var e={};e._next=e._prev=e,this._sentinel=e}dequeue(){var e=this._sentinel,n=e._prev;if(n!==e)return B(n),n}enqueue(e){var n=this._sentinel;e._prev&&e._next&&B(e),e._next=n._next,n._next._prev=e,n._next=e,e._prev=n}toString(){for(var e=[],n=this._sentinel,r=n._prev;r!==n;)e.push(JSON.stringify(r,F)),r=r._prev;return"["+e.join(", ")+"]"}}function B(e){e._prev._next=e._next,e._next._prev=e._prev,delete e._next,delete e._prev}function F(e,n){if("_next"!==e&&"_prev"!==e)return n}var q=N(1);function Y(n,r){if(n.nodeCount()<=1)return[];var o=function(n,r){var o=new e,i=0,a=0;t(n.nodes(),(function(e){o.setNode(e,{v:e,in:0,out:0})})),t(n.edges(),(function(e){var n=o.edge(e.v,e.w)||0,t=r(e),u=n+t;o.setEdge(e.v,e.w,u),a=Math.max(a,o.node(e.v).out+=t),i=Math.max(i,o.node(e.w).in+=t)}));var u=E(a+i+3).map((function(){return new V})),d=i+1;return t(o.nodes(),(function(e){D(u,d,o.node(e))})),{graph:o,buckets:u,zeroIdx:d}}(n,r||q),i=function(e,n,r){var t,o=[],i=n[n.length-1],a=n[0];for(;e.nodeCount();){for(;t=a.dequeue();)z(e,n,r,t);for(;t=i.dequeue();)z(e,n,r,t);if(e.nodeCount())for(var u=n.length-2;u>0;--u)if(t=n[u].dequeue()){o=o.concat(z(e,n,r,t,!0));break}}return o}(o.graph,o.buckets,o.zeroIdx);return k(s(i,(function(e){return n.outEdges(e.v,e.w)})))}function z(e,n,r,o,i){var a=i?[]:void 0;return t(e.inEdges(o.v),(function(t){var o=e.edge(t),u=e.node(t.v);i&&a.push({v:t.v,w:t.w}),u.out-=o,D(n,r,u)})),t(e.outEdges(o.v),(function(t){var o=e.edge(t),i=t.w,a=e.node(i);a.in-=o,D(n,r,a)})),e.removeNode(o.v),a}function D(e,n,r){r.out?r.in?e[r.out-r.in+n].enqueue(r):e[e.length-1].enqueue(r):e[0].enqueue(r)}function A(e){var n,r="greedy"===e.graph().acyclicer?Y(e,(n=e,function(e){return n.edge(e).weight})):function(e){var n=[],r={},o={};function i(a){Object.prototype.hasOwnProperty.call(o,a)||(o[a]=!0,r[a]=!0,t(e.outEdges(a),(function(e){Object.prototype.hasOwnProperty.call(r,e.w)?n.push(e):i(e.w)})),delete r[a])}return t(e.nodes(),i),n}(e);t(r,(function(n){var r=e.edge(n);e.removeEdge(n),r.forwardName=n.name,r.reversed=!0,e.setEdge(n.w,n.v,r,G("rev"))}))}function U(e,n,r,t){var o;do{o=G(t)}while(e.hasNode(o));return r.dummy=n,e.setNode(o,r),o}function J(n){var r=new e({multigraph:n.isMultigraph()}).setGraph(n.graph());return t(n.nodes(),(function(e){n.children(e).length||r.setNode(e,n.node(e))})),t(n.edges(),(function(e){r.setEdge(e,n.edge(e))})),r}function W(e,n){var r,t,o=e.x,i=e.y,a=n.x-o,u=n.y-i,d=e.width/2,c=e.height/2;if(!a&&!u)throw new Error("Not possible to find intersection inside of the rectangle");return Math.abs(u)*d>Math.abs(a)*c?(u<0&&(c=-c),r=c*a/u,t=c):(a<0&&(d=-d),r=d,t=d*u/a),{x:o+r,y:i+t}}function X(e){var n=s(E(K(e)+1),(function(){return[]}));return t(e.nodes(),(function(r){var t=e.node(r),i=t.rank;o(i)||(n[i][t.order]=r)})),n}function H(e,n,r,t){var o={width:0,height:0};return arguments.length>=4&&(o.rank=r,o.order=t),U(e,"border",o,n)}function K(e){return L(s(e.nodes(),(function(n){var r=e.node(n).rank;if(!o(r))return r})))}function Q(e,n){return n()}function Z(e,n,r,t,o,i){var a={width:0,height:0,rank:i,borderType:n},u=o[n][i-1],d=U(e,"border",a,r);o[n][i]=d,e.setParent(d,t),u&&e.setEdge(u,d,{weight:1})}function $(e){var n=e.graph().rankdir.toLowerCase();"bt"!==n&&"rl"!==n||function(e){t(e.nodes(),(function(n){re(e.node(n))})),t(e.edges(),(function(n){var r=e.edge(n);t(r.points,re),Object.prototype.hasOwnProperty.call(r,"y")&&re(r)}))}(e),"lr"!==n&&"rl"!==n||(!function(e){t(e.nodes(),(function(n){te(e.node(n))})),t(e.edges(),(function(n){var r=e.edge(n);t(r.points,te),Object.prototype.hasOwnProperty.call(r,"x")&&te(r)}))}(e),ee(e))}function ee(e){t(e.nodes(),(function(n){ne(e.node(n))})),t(e.edges(),(function(n){ne(e.edge(n))}))}function ne(e){var n=e.width;e.width=e.height,e.height=n}function re(e){e.y=-e.y}function te(e){var n=e.x;e.x=e.y,e.y=n}function oe(e){e.graph().dummyChains=[],t(e.edges(),(function(n){!function(e,n){var r=n.v,t=e.node(r).rank,o=n.w,i=e.node(o).rank,a=n.name,u=e.edge(n),d=u.labelRank;if(i===t+1)return;e.removeEdge(n);var c,s,f=void 0;for(s=0,++t;t<i;++s,++t)u.points=[],c=U(e,"edge",f={width:0,height:0,edgeLabel:u,edgeObj:n,rank:t},"_d"),t===d&&(f.width=u.width,f.height=u.height,f.dummy="edge-label",f.labelpos=u.labelpos),e.setEdge(r,c,{weight:u.weight},a),0===s&&e.graph().dummyChains.push(c),r=c;e.setEdge(r,o,{weight:u.weight},a)}(e,n)}))}function ie(e){var n={};t(e.sources(),(function r(t){var o=e.node(t);if(Object.prototype.hasOwnProperty.call(n,t))return o.rank;n[t]=!0;var i=f(s(e.outEdges(t),(function(n){return r(n.w)-e.edge(n).minlen})));return i!==Number.POSITIVE_INFINITY&&null!=i||(i=0),o.rank=i}))}function ae(e,n){return e.node(n.w).rank-e.node(n.v).rank-e.edge(n).minlen}function ue(n){var r,t,o=new e({directed:!1}),i=n.nodes()[0],a=n.nodeCount();for(o.setNode(i,{});de(o,n)<a;)r=ce(o,n),t=o.hasNode(r.v)?ae(n,r):-ae(n,r),se(o,n,t);return o}function de(e,n){return t(e.nodes(),(function r(o){t(n.nodeEdges(o),(function(t){var i=t.v,a=o===i?t.w:i;e.hasNode(a)||ae(n,t)||(e.setNode(a,{}),e.setEdge(o,a,{}),r(a))}))})),e.nodeCount()}function ce(e,n){return C(n.edges(),(function(r){if(e.hasNode(r.v)!==e.hasNode(r.w))return ae(n,r)}))}function se(e,n,r){t(e.nodes(),(function(e){n.node(e).rank+=r}))}function fe(e,n,r){O(n)||(n=[n]);var o=(e.isDirected()?e.successors:e.neighbors).bind(e),i=[],a={};return t(n,(function(n){if(!e.hasNode(n))throw new Error("Graph does not have node: "+n);he(e,n,"post"===r,a,o,i)})),i}function he(e,n,r,o,i,a){Object.prototype.hasOwnProperty.call(o,n)||(o[n]=!0,r||a.push(n),t(i(n),(function(n){he(e,n,r,o,i,a)})),r&&a.push(n))}function ge(n){n=function(n){var r=(new e).setGraph(n.graph());return t(n.nodes(),(function(e){r.setNode(e,n.node(e))})),t(n.edges(),(function(e){var t=r.edge(e.v,e.w)||{weight:0,minlen:1},o=n.edge(e);r.setEdge(e.v,e.w,{weight:t.weight+o.weight,minlen:Math.max(t.minlen,o.minlen)})})),r}(n),ie(n);var r,o=ue(n);for(pe(o),ve(o,n);r=me(o);)ye(o,n,r,be(o,n,r))}function ve(e,n){var r=function(e,n){return fe(e,n,"post")}(e,e.nodes());r=r.slice(0,r.length-1),t(r,(function(r){!function(e,n,r){var t=e.node(r),o=t.parent;e.edge(r,o).cutvalue=le(e,n,r)}(e,n,r)}))}function le(e,n,r){var o=e.node(r).parent,i=!0,a=n.edge(r,o),u=0;return a||(i=!1,a=n.edge(o,r)),u=a.weight,t(n.nodeEdges(r),(function(t){var a,d,c=t.v===r,s=c?t.w:t.v;if(s!==o){var f=c===i,h=n.edge(t).weight;if(u+=f?h:-h,a=r,d=s,e.hasEdge(a,d)){var g=e.edge(r,s).cutvalue;u+=f?-g:g}}})),u}function pe(e,n){arguments.length<2&&(n=e.nodes()[0]),we(e,{},1,n)}function we(e,n,r,o,i){var a=r,u=e.node(o);return n[o]=!0,t(e.neighbors(o),(function(t){Object.prototype.hasOwnProperty.call(n,t)||(r=we(e,n,r,t,o))})),u.low=a,u.lim=r++,i?u.parent=i:delete u.parent,r}function me(e){return g(e.edges(),(function(n){return e.edge(n).cutvalue<0}))}function be(e,n,r){var t=r.v,o=r.w;n.hasEdge(t,o)||(t=r.w,o=r.v);var a=e.node(t),u=e.node(o),d=a,c=!1;return a.lim>u.lim&&(d=u,c=!0),C(i(n.edges(),(function(n){return c===xe(e,e.node(n.v),d)&&c!==xe(e,e.node(n.w),d)})),(function(e){return ae(n,e)}))}function ye(e,n,r,o){var i=r.v,a=r.w;e.removeEdge(i,a),e.setEdge(o.v,o.w,{}),pe(e),ve(e,n),function(e,n){var r=g(e.nodes(),(function(e){return!n.node(e).parent})),o=function(e,n){return fe(e,n,"pre")}(e,r);o=o.slice(1),t(o,(function(r){var t=e.node(r).parent,o=n.edge(r,t),i=!1;o||(o=n.edge(t,r),i=!0),n.node(r).rank=n.node(t).rank+(i?o.minlen:-o.minlen)}))}(e,n)}function xe(e,n,r){return r.low<=n.lim&&n.lim<=r.lim}function ke(e){switch(e.graph().ranker){case"network-simplex":default:Ne(e);break;case"tight-tree":!function(e){ie(e),ue(e)}(e);break;case"longest-path":Ee(e)}}new Error,ge.initLowLimValues=pe,ge.initCutValues=ve,ge.calcCutValue=le,ge.leaveEdge=me,ge.enterEdge=be,ge.exchangeEdges=ye;var Ee=ie;function Ne(e){ge(e)}function Oe(e){var n=U(e,"root",{},"_root"),r=function(e){var n={};function r(o,i){var a=e.children(o);a&&a.length&&t(a,(function(e){r(e,i+1)})),n[o]=i}return t(e.children(),(function(e){r(e,1)})),n}(e),o=L(a(r))-1,i=2*o+1;e.graph().nestingRoot=n,t(e.edges(),(function(n){e.edge(n).minlen*=i}));var d=function(e){return u(e.edges(),(function(n,r){return n+e.edge(r).weight}),0)}(e)+1;t(e.children(),(function(t){_e(e,n,i,d,o,r,t)})),e.graph().nodeRankFactor=i}function _e(e,n,r,o,i,a,u){var d=e.children(u);if(d.length){var c=H(e,"_bt"),s=H(e,"_bb"),f=e.node(u);e.setParent(c,u),f.borderTop=c,e.setParent(s,u),f.borderBottom=s,t(d,(function(t){_e(e,n,r,o,i,a,t);var d=e.node(t),f=d.borderTop?d.borderTop:t,h=d.borderBottom?d.borderBottom:t,g=d.borderTop?o:2*o,v=f!==h?1:i-a[u]+1;e.setEdge(c,f,{weight:g,minlen:v,nestingEdge:!0}),e.setEdge(h,s,{weight:g,minlen:v,nestingEdge:!0})})),e.parent(u)||e.setEdge(n,c,{weight:0,minlen:i+a[u]})}else u!==n&&e.setEdge(n,u,{weight:0,minlen:r})}function Ie(n,r,i){var a=function(e){var n;for(;e.hasNode(n=G("_root")););return n}(n),u=new e({compound:!0}).setGraph({root:a}).setDefaultNodeLabel((function(e){return n.node(e)}));return t(n.nodes(),(function(e){var d=n.node(e),c=n.parent(e);(d.rank===r||d.minRank<=r&&r<=d.maxRank)&&(u.setNode(e),u.setParent(e,c||a),t(n[i](e),(function(r){var t=r.v===e?r.w:r.v,i=u.edge(t,e),a=o(i)?0:i.weight;u.setEdge(t,e,{weight:n.edge(r).weight+a})})),Object.prototype.hasOwnProperty.call(d,"minRank")&&u.setNode(e,{borderLeft:d.borderLeft[r],borderRight:d.borderRight[r]}))})),u}function Pe(e,n){for(var r=0,t=1;t<n.length;++t)r+=je(e,n[t-1],n[t]);return r}function je(e,n,r){for(var o,i,a=(o=r,i=s(r,(function(e,n){return n})),function(e,n,r){for(var t=-1,o=e.length,i=n.length,a={};++t<o;){var u=t<i?n[t]:void 0;r(a,e[t],u)}return a}(o||[],i||[],x)),u=k(s(n,(function(n){return R(s(e.outEdges(n),(function(n){return{pos:a[n.w],weight:e.edge(n).weight}})),"pos")}))),d=1;d<r.length;)d<<=1;var c=2*d-1;d-=1;var f=s(new Array(c),(function(){return 0})),h=0;return t(u.forEach((function(e){var n=e.pos+d;f[n]+=e.weight;for(var r=0;n>0;)n%2&&(r+=f[n+1]),f[n=n-1>>1]+=e.weight;h+=e.weight*r}))),h}function Re(e,n){var r={};return t(e,(function(e,n){var t=r[e.v]={indegree:0,in:[],out:[],vs:[e.v],i:n};o(e.barycenter)||(t.barycenter=e.barycenter,t.weight=e.weight)})),t(n.edges(),(function(e){var n=r[e.v],t=r[e.w];o(n)||o(t)||(t.indegree++,n.out.push(r[e.w]))})),function(e){var n=[];function r(e){return function(n){n.merged||(o(n.barycenter)||o(e.barycenter)||n.barycenter>=e.barycenter)&&function(e,n){var r=0,t=0;e.weight&&(r+=e.barycenter*e.weight,t+=e.weight);n.weight&&(r+=n.barycenter*n.weight,t+=n.weight);e.vs=n.vs.concat(e.vs),e.barycenter=r/t,e.weight=t,e.i=Math.min(n.i,e.i),n.merged=!0}(e,n)}}function a(n){return function(r){r.in.push(n),0==--r.indegree&&e.push(r)}}for(;e.length;){var u=e.pop();n.push(u),t(u.in.reverse(),r(u)),t(u.out,a(u))}return s(i(n,(function(e){return!e.merged})),(function(e){return _(e,["vs","i","barycenter","weight"])}))}(i(r,(function(e){return!e.indegree})))}function Te(e,n){var r,o=function(e,n){var r={lhs:[],rhs:[]};return t(e,(function(e){n(e)?r.lhs.push(e):r.rhs.push(e)})),r}(e,(function(e){return Object.prototype.hasOwnProperty.call(e,"barycenter")})),i=o.lhs,a=R(o.rhs,(function(e){return-e.i})),u=[],d=0,c=0,s=0;i.sort((r=!!n,function(e,n){return e.barycenter<n.barycenter?-1:e.barycenter>n.barycenter?1:r?n.i-e.i:e.i-n.i})),s=Me(u,a,s),t(i,(function(e){s+=e.vs.length,u.push(e.vs),d+=e.barycenter*e.weight,c+=e.weight,s=Me(u,a,s)}));var f={vs:k(u)};return c&&(f.barycenter=d/c,f.weight=c),f}function Me(e,n,r){for(var t;n.length&&(t=v(n)).i<=r;)n.pop(),e.push(t.vs),r++;return r}function Le(e,n,r,a){var d=e.children(n),c=e.node(n),f=c?c.borderLeft:void 0,h=c?c.borderRight:void 0,g={};f&&(d=i(d,(function(e){return e!==f&&e!==h})));var v=function(e,n){return s(n,(function(n){var r=e.inEdges(n);if(r.length){var t=u(r,(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:n,barycenter:t.sum/t.weight,weight:t.weight}}return{v:n}}))}(e,d);t(v,(function(n){if(e.children(n.v).length){var t=Le(e,n.v,r,a);g[n.v]=t,Object.prototype.hasOwnProperty.call(t,"barycenter")&&(u=t,o((i=n).barycenter)?(i.barycenter=u.barycenter,i.weight=u.weight):(i.barycenter=(i.barycenter*i.weight+u.barycenter*u.weight)/(i.weight+u.weight),i.weight+=u.weight))}var i,u}));var l=Re(v,r);!function(e,n){t(e,(function(e){e.vs=k(e.vs.map((function(e){return n[e]?n[e].vs:e})))}))}(l,g);var p=Te(l,a);if(f&&(p.vs=k([f,p.vs,h]),e.predecessors(f).length)){var w=e.node(e.predecessors(f)[0]),m=e.node(e.predecessors(h)[0]);Object.prototype.hasOwnProperty.call(p,"barycenter")||(p.barycenter=0,p.weight=0),p.barycenter=(p.barycenter*p.weight+w.order+m.order)/(p.weight+2),p.weight+=2}return p}function Ce(e){var r=K(e),o=Se(e,E(1,r+1),"inEdges"),a=Se(e,E(r-1,-1,-1),"outEdges"),u=function(e){var n={},r=i(e.nodes(),(function(n){return!e.children(n).length})),o=L(s(r,(function(n){return e.node(n).rank}))),a=s(E(o+1),(function(){return[]})),u=R(r,(function(n){return e.node(n).rank}));return t(u,(function r(o){if(!h(n,o)){n[o]=!0;var i=e.node(o);a[i.rank].push(o),t(e.successors(o),r)}})),a}(e);Ve(e,u);for(var d,c=Number.POSITIVE_INFINITY,f=0,g=0;g<4;++f,++g){Ge(f%2?o:a,f%4>=2);var v=Pe(e,u=X(e));v<c&&(g=0,d=n(u,5),c=v)}Ve(e,d)}function Se(e,n,r){return s(n,(function(n){return Ie(e,n,r)}))}function Ge(n,r){var o=new e;t(n,(function(e){var n=e.graph().root,i=Le(e,n,o,r);t(i.vs,(function(n,r){e.node(n).order=r})),function(e,n,r){var o,i={};t(r,(function(r){for(var t,a,u=e.parent(r);u;){if((t=e.parent(u))?(a=i[t],i[t]=u):(a=o,o=u),a&&a!==u)return void n.setEdge(a,u);u=t}}))}(e,o,i.vs)}))}function Ve(e,n){t(n,(function(n){t(n,(function(n,r){e.node(n).order=r}))}))}function Be(e){var n=function(e){var n={},r=0;function o(i){var a=r;t(e.children(i),o),n[i]={low:a,lim:r++}}return t(e.children(),o),n}(e);t(e.graph().dummyChains,(function(r){for(var t=e.node(r),o=t.edgeObj,i=function(e,n,r,t){var o,i,a=[],u=[],d=Math.min(n[r].low,n[t].low),c=Math.max(n[r].lim,n[t].lim);o=r;do{o=e.parent(o),a.push(o)}while(o&&(n[o].low>d||c>n[o].lim));i=o,o=t;for(;(o=e.parent(o))!==i;)u.push(o);return{path:a.concat(u.reverse()),lca:i}}(e,n,o.v,o.w),a=i.path,u=i.lca,d=0,c=a[d],s=!0;r!==o.w;){if(t=e.node(r),s){for(;(c=a[d])!==u&&e.node(c).maxRank<t.rank;)d++;c===u&&(s=!1)}if(!s){for(;d<a.length-1&&e.node(c=a[d+1]).minRank<=t.rank;)d++;c=a[d]}e.setParent(r,c),r=e.successors(r)[0]}}))}function Fe(e,n){var r={};return u(n,(function(n,o){var i=0,a=0,u=n.length,d=v(o);return t(o,(function(n,c){var s=function(e,n){if(e.node(n).dummy)return g(e.predecessors(n),(function(n){return e.node(n).dummy}))}(e,n),f=s?e.node(s).order:u;(s||n===d)&&(t(o.slice(a,c+1),(function(n){t(e.predecessors(n),(function(t){var o=e.node(t),a=o.order;!(a<i||f<a)||o.dummy&&e.node(n).dummy||qe(r,t,n)}))})),a=c+1,i=f)})),o})),r}function qe(e,n,r){if(n>r){var t=n;n=r,r=t}var o=e[n];o||(e[n]=o={}),o[r]=!0}function Ye(e,n,r){if(n>r){var t=n;n=r,r=t}return!!e[n]&&Object.prototype.hasOwnProperty.call(e[n],r)}function ze(n,r,o,i,a){var u={},d=function(n,r,o,i){var a=new e,u=n.graph(),d=function(e,n,r){return function(t,o,i){var a,u=t.node(o),d=t.node(i),c=0;if(c+=u.width/2,Object.prototype.hasOwnProperty.call(u,"labelpos"))switch(u.labelpos.toLowerCase()){case"l":a=-u.width/2;break;case"r":a=u.width/2}if(a&&(c+=r?a:-a),a=0,c+=(u.dummy?n:e)/2,c+=(d.dummy?n:e)/2,c+=d.width/2,Object.prototype.hasOwnProperty.call(d,"labelpos"))switch(d.labelpos.toLowerCase()){case"l":a=d.width/2;break;case"r":a=-d.width/2}return a&&(c+=r?a:-a),a=0,c}}(u.nodesep,u.edgesep,i);return t(r,(function(e){var r;t(e,(function(e){var t=o[e];if(a.setNode(t),r){var i=o[r],u=a.edge(i,t);a.setEdge(i,t,Math.max(d(n,e,r),u||0))}r=e}))})),a}(n,r,o,a),c=a?"borderLeft":"borderRight";function s(e,n){for(var r=d.nodes(),t=r.pop(),o={};t;)o[t]?e(t):(o[t]=!0,r.push(t),r=r.concat(n(t))),t=r.pop()}return s((function(e){u[e]=d.inEdges(e).reduce((function(e,n){return Math.max(e,u[n.v]+d.edge(n))}),0)}),d.predecessors.bind(d)),s((function(e){var r=d.outEdges(e).reduce((function(e,n){return Math.min(e,u[n.w]-d.edge(n))}),Number.POSITIVE_INFINITY),t=n.node(e);r!==Number.POSITIVE_INFINITY&&t.borderType!==c&&(u[e]=Math.max(u[e],r))}),d.successors.bind(d)),t(i,(function(e){u[e]=u[o[e]]})),u}function De(e,n){return C(a(n),(function(n){var t,o,i=Number.NEGATIVE_INFINITY,a=Number.POSITIVE_INFINITY;return o=function(n,r){var t=function(e,n){return e.node(n).width}(e,r)/2;i=Math.max(n+t,i),a=Math.min(n-t,a)},null==(t=n)||p(t,r(o),w),i-a}))}function Ae(e){var n,r=X(e),o=I(Fe(e,r),function(e,n){var r={};function o(n,o,i,a,u){var d;t(E(o,i),(function(o){d=n[o],e.node(d).dummy&&t(e.predecessors(d),(function(n){var t=e.node(n);t.dummy&&(t.order<a||t.order>u)&&qe(r,n,d)}))}))}return u(n,(function(n,r){var i,a=-1,u=0;return t(r,(function(t,d){if("border"===e.node(t).dummy){var c=e.predecessors(t);c.length&&(i=e.node(c[0]).order,o(r,u,d,a,i),u=d,a=i)}o(r,u,r.length,i,n.length)})),r})),r}(e,r)),i={};t(["u","d"],(function(u){n="u"===u?r:a(r).reverse(),t(["l","r"],(function(r){"r"===r&&(n=s(n,(function(e){return a(e).reverse()})));var d=("u"===u?e.predecessors:e.successors).bind(e),c=function(e,n,r,o){var i={},a={},u={};return t(n,(function(e){t(e,(function(e,n){i[e]=e,a[e]=e,u[e]=n}))})),t(n,(function(e){var n=-1;t(e,(function(e){var t=o(e);if(t.length)for(var d=((t=R(t,(function(e){return u[e]}))).length-1)/2,c=Math.floor(d),s=Math.ceil(d);c<=s;++c){var f=t[c];a[e]===e&&n<u[f]&&!Ye(r,e,f)&&(a[f]=e,a[e]=i[e]=i[f],n=u[f])}}))})),{root:i,align:a}}(0,n,o,d),f=ze(e,n,c.root,c.align,"r"===r);"r"===r&&(f=M(f,(function(e){return-e}))),i[u+r]=f}))}));var d=De(e,i);return function(e,n){var r=a(n),o=f(r),i=L(r);t(["u","d"],(function(r){t(["l","r"],(function(t){var u,d=r+t,c=e[d];if(c!==n){var s=a(c);(u="l"===t?o-f(s):i-L(s))&&(e[d]=M(c,(function(e){return e+u})))}}))}))}(i,d),function(e,n){return M(e.ul,(function(r,t){if(n)return e[n.toLowerCase()][t];var o=R(s(e,t));return(o[1]+o[2])/2}))}(i,e.graph().align)}function Ue(e){var n,o;(function(e){var n=X(e),r=e.graph().ranksep,o=0;t(n,(function(n){var i=L(s(n,(function(n){return e.node(n).height})));t(n,(function(n){e.node(n).y=o+i/2})),o+=i+r}))})(e=J(e)),n=Ae(e),o=function(n,r){e.node(r).x=n},n&&P(n,r(o))}function Je(n,r){var i=Q;i("layout",(()=>{var r=i(" buildLayoutGraph",(()=>function(n){var r=new e({multigraph:!0,compound:!0}),o=rn(n.graph());return r.setGraph(I({},Xe,nn(o,We),_(o,He))),t(n.nodes(),(function(e){var t=rn(n.node(e));r.setNode(e,l(nn(t,Ke),Qe)),r.setParent(e,n.parent(e))})),t(n.edges(),(function(e){var t=rn(n.edge(e));r.setEdge(e,I({},$e,nn(t,Ze),_(t,en)))})),r}(n)));i(" runLayout",(()=>function(e,n){n(" makeSpaceForEdgeLabels",(()=>function(e){var n=e.graph();n.ranksep/=2,t(e.edges(),(function(r){var t=e.edge(r);t.minlen*=2,"c"!==t.labelpos.toLowerCase()&&("TB"===n.rankdir||"BT"===n.rankdir?t.width+=t.labeloffset:t.height+=t.labeloffset)}))}(e))),n(" removeSelfEdges",(()=>function(e){t(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)}}))}(e))),n(" acyclic",(()=>A(e))),n(" nestingGraph.run",(()=>Oe(e))),n(" rank",(()=>ke(J(e)))),n(" injectEdgeLabelProxies",(()=>function(e){t(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};U(e,"edge-proxy",o,"_ep")}}))}(e))),n(" removeEmptyRanks",(()=>function(e){var n=f(s(e.nodes(),(function(n){return e.node(n).rank}))),r=[];t(e.nodes(),(function(t){var o=e.node(t).rank-n;r[o]||(r[o]=[]),r[o].push(t)}));var i=0,a=e.graph().nodeRankFactor;t(r,(function(n,r){o(n)&&r%a!=0?--i:i&&t(n,(function(n){e.node(n).rank+=i}))}))}(e))),n(" nestingGraph.cleanup",(()=>function(e){var n=e.graph();e.removeNode(n.nestingRoot),delete n.nestingRoot,t(e.edges(),(function(n){e.edge(n).nestingEdge&&e.removeEdge(n)}))}(e))),n(" normalizeRanks",(()=>function(e){var n=f(s(e.nodes(),(function(n){return e.node(n).rank})));t(e.nodes(),(function(r){var t=e.node(r);h(t,"rank")&&(t.rank-=n)}))}(e))),n(" assignRankMinMax",(()=>function(e){var n=0;t(e.nodes(),(function(r){var t=e.node(r);t.borderTop&&(t.minRank=e.node(t.borderTop).rank,t.maxRank=e.node(t.borderBottom).rank,n=L(n,t.maxRank))})),e.graph().maxRank=n}(e))),n(" removeEdgeLabelProxies",(()=>function(e){t(e.nodes(),(function(n){var r=e.node(n);"edge-proxy"===r.dummy&&(e.edge(r.e).labelRank=r.rank,e.removeNode(n))}))}(e))),n(" normalize.run",(()=>oe(e))),n(" parentDummyChains",(()=>Be(e))),n(" addBorderSegments",(()=>function(e){t(e.children(),(function n(r){var o=e.children(r),i=e.node(r);if(o.length&&t(o,n),Object.prototype.hasOwnProperty.call(i,"minRank")){i.borderLeft=[],i.borderRight=[];for(var a=i.minRank,u=i.maxRank+1;a<u;++a)Z(e,"borderLeft","_bl",r,i,a),Z(e,"borderRight","_br",r,i,a)}}))}(e))),n(" order",(()=>Ce(e))),n(" insertSelfEdges",(()=>function(e){var n=X(e);t(n,(function(n){var r=0;t(n,(function(n,o){var i=e.node(n);i.order=o+r,t(i.selfEdges,(function(n){U(e,"selfedge",{width:n.label.width,height:n.label.height,rank:i.rank,order:o+ ++r,e:n.e,label:n.label},"_se")})),delete i.selfEdges}))}))}(e))),n(" adjustCoordinateSystem",(()=>function(e){var n=e.graph().rankdir.toLowerCase();"lr"!==n&&"rl"!==n||ee(e)}(e))),n(" position",(()=>Ue(e))),n(" positionSelfEdges",(()=>function(e){t(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,i=t.y,a=r.x-o,u=t.height/2;e.setEdge(r.e,r.label),e.removeNode(n),r.label.points=[{x:o+2*a/3,y:i-u},{x:o+5*a/6,y:i-u},{x:o+a,y:i},{x:o+5*a/6,y:i+u},{x:o+2*a/3,y:i+u}],r.label.x=r.x,r.label.y=r.y}}))}(e))),n(" removeBorderNodes",(()=>function(e){t(e.nodes(),(function(n){if(e.children(n).length){var r=e.node(n),t=e.node(r.borderTop),o=e.node(r.borderBottom),i=e.node(v(r.borderLeft)),a=e.node(v(r.borderRight));r.width=Math.abs(a.x-i.x),r.height=Math.abs(o.y-t.y),r.x=i.x+r.width/2,r.y=t.y+r.height/2}})),t(e.nodes(),(function(n){"border"===e.node(n).dummy&&e.removeNode(n)}))}(e))),n(" normalize.undo",(()=>function(e){t(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)}))}(e))),n(" fixupEdgeLabelCoords",(()=>function(e){t(e.edges(),(function(n){var r=e.edge(n);if(Object.prototype.hasOwnProperty.call(r,"x"))switch("l"!==r.labelpos&&"r"!==r.labelpos||(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}}))}(e))),n(" undoCoordinateSystem",(()=>$(e))),n(" translateGraph",(()=>function(e){var n=Number.POSITIVE_INFINITY,r=0,o=Number.POSITIVE_INFINITY,i=0,a=e.graph(),u=a.marginx||0,d=a.marginy||0;function c(e){var t=e.x,a=e.y,u=e.width,d=e.height;n=Math.min(n,t-u/2),r=Math.max(r,t+u/2),o=Math.min(o,a-d/2),i=Math.max(i,a+d/2)}t(e.nodes(),(function(n){c(e.node(n))})),t(e.edges(),(function(n){var r=e.edge(n);Object.prototype.hasOwnProperty.call(r,"x")&&c(r)})),n-=u,o-=d,t(e.nodes(),(function(r){var t=e.node(r);t.x-=n,t.y-=o})),t(e.edges(),(function(r){var i=e.edge(r);t(i.points,(function(e){e.x-=n,e.y-=o})),Object.prototype.hasOwnProperty.call(i,"x")&&(i.x-=n),Object.prototype.hasOwnProperty.call(i,"y")&&(i.y-=o)})),a.width=r-n+u,a.height=i-o+d}(e))),n(" assignNodeIntersects",(()=>function(e){t(e.edges(),(function(n){var r,t,o=e.edge(n),i=e.node(n.v),a=e.node(n.w);o.points?(r=o.points[0],t=o.points[o.points.length-1]):(o.points=[],r=a,t=i),o.points.unshift(W(i,r)),o.points.push(W(a,t))}))}(e))),n(" reversePoints",(()=>function(e){t(e.edges(),(function(n){var r=e.edge(n);r.reversed&&r.points.reverse()}))}(e))),n(" acyclic.undo",(()=>function(e){t(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)}}))}(e)))}(r,i))),i(" updateInputGraph",(()=>function(e,n){t(e.nodes(),(function(r){var t=e.node(r),o=n.node(r);t&&(t.x=o.x,t.y=o.y,n.children(r).length&&(t.width=o.width,t.height=o.height))})),t(e.edges(),(function(r){var t=e.edge(r),o=n.edge(r);t.points=o.points,Object.prototype.hasOwnProperty.call(o,"x")&&(t.x=o.x,t.y=o.y)})),e.graph().width=n.graph().width,e.graph().height=n.graph().height}(n,r)))}))}var We=["nodesep","edgesep","ranksep","marginx","marginy"],Xe={ranksep:50,edgesep:20,nodesep:50,rankdir:"tb"},He=["acyclicer","ranker","rankdir","align"],Ke=["width","height"],Qe={width:0,height:0},Ze=["minlen","weight","width","height","labeloffset"],$e={minlen:1,weight:1,width:0,height:0,labeloffset:10,labelpos:"r"},en=["labelpos"];function nn(e,n){return M(_(e,n),Number)}function rn(e){var n={};return t(e,(function(e,r){n[r.toLowerCase()]=e})),n}export{Je as l}; | |