diff options
author | Christoph Cullmann <christoph@cullmann.io> | 2024-07-15 22:27:55 +0200 |
---|---|---|
committer | Christoph Cullmann <christoph@cullmann.io> | 2024-07-15 22:27:55 +0200 |
commit | 3be5285488090ab70254b3080e33e64e6c702d2c (patch) | |
tree | 1e54462f560fd759b5be13d5ecfe1fa5c2c832ed /themes/blowfish/assets/lib/mermaid/layout-163b9689.js | |
parent | 69075c6fb15ae660fc3d78eb2a4dfcde1c5fba1c (diff) |
sync theme
Diffstat (limited to 'themes/blowfish/assets/lib/mermaid/layout-163b9689.js')
-rw-r--r-- | themes/blowfish/assets/lib/mermaid/layout-163b9689.js | 2314 |
1 files changed, 0 insertions, 2314 deletions
diff --git a/themes/blowfish/assets/lib/mermaid/layout-163b9689.js b/themes/blowfish/assets/lib/mermaid/layout-163b9689.js deleted file mode 100644 index 5781ad2..0000000 --- a/themes/blowfish/assets/lib/mermaid/layout-163b9689.js +++ /dev/null @@ -1,2314 +0,0 @@ -import { a as isSymbol, b as baseFlatten, c as baseClone, d as baseIteratee, k as keys, e as baseFindIndex, g as baseEach, j as arrayMap, l as castFunction, m as baseForOwn, n as castPath, t as toKey, o as baseGet, p as hasIn, q as toString, f as forEach, G as Graph, h as has, i as isUndefined, r as filter, v as values, s as reduce } from "./graph-fe24fab6.js"; -import { a8 as isObject, a9 as setToString, aa as overRest, ab as root, ac as baseRest, ad as isIterateeCall, ae as keysIn, af as eq, ag as isArrayLike, ah as isArray, ai as baseFor, aj as baseAssignValue, ak as identity, al as isIndex, am as assignValue, an as baseUnary, ao as constant, ap as merge } from "./mermaid-dcacb631.js"; -var reWhitespace = /\s/; -function trimmedEndIndex(string) { - var index = string.length; - while (index-- && reWhitespace.test(string.charAt(index))) { - } - return index; -} -var reTrimStart = /^\s+/; -function baseTrim(string) { - return string ? string.slice(0, trimmedEndIndex(string) + 1).replace(reTrimStart, "") : string; -} -var NAN = 0 / 0; -var reIsBadHex = /^[-+]0x[0-9a-f]+$/i; -var reIsBinary = /^0b[01]+$/i; -var reIsOctal = /^0o[0-7]+$/i; -var freeParseInt = parseInt; -function toNumber(value) { - if (typeof value == "number") { - return value; - } - if (isSymbol(value)) { - return NAN; - } - if (isObject(value)) { - var other = typeof value.valueOf == "function" ? value.valueOf() : value; - value = isObject(other) ? other + "" : other; - } - if (typeof value != "string") { - return value === 0 ? value : +value; - } - value = baseTrim(value); - var isBinary = reIsBinary.test(value); - return isBinary || reIsOctal.test(value) ? freeParseInt(value.slice(2), isBinary ? 2 : 8) : reIsBadHex.test(value) ? NAN : +value; -} -var INFINITY = 1 / 0, MAX_INTEGER = 17976931348623157e292; -function toFinite(value) { - if (!value) { - return value === 0 ? value : 0; - } - value = toNumber(value); - if (value === INFINITY || value === -INFINITY) { - var sign = value < 0 ? -1 : 1; - return sign * MAX_INTEGER; - } - return value === value ? value : 0; -} -function toInteger(value) { - var result = toFinite(value), remainder = result % 1; - return result === result ? remainder ? result - remainder : result : 0; -} -function flatten(array) { - var length = array == null ? 0 : array.length; - return length ? baseFlatten(array, 1) : []; -} -function flatRest(func) { - return setToString(overRest(func, void 0, flatten), func + ""); -} -var CLONE_DEEP_FLAG = 1, CLONE_SYMBOLS_FLAG = 4; -function cloneDeep(value) { - return baseClone(value, CLONE_DEEP_FLAG | CLONE_SYMBOLS_FLAG); -} -var now = function() { - return root.Date.now(); -}; -const now$1 = now; -var objectProto = Object.prototype; -var hasOwnProperty = objectProto.hasOwnProperty; -var defaults = baseRest(function(object, sources) { - object = Object(object); - var index = -1; - var length = sources.length; - var guard = length > 2 ? sources[2] : void 0; - if (guard && isIterateeCall(sources[0], sources[1], guard)) { - length = 1; - } - while (++index < length) { - var source = sources[index]; - var props = keysIn(source); - var propsIndex = -1; - var propsLength = props.length; - while (++propsIndex < propsLength) { - var key = props[propsIndex]; - var value = object[key]; - if (value === void 0 || eq(value, objectProto[key]) && !hasOwnProperty.call(object, key)) { - object[key] = source[key]; - } - } - } - return object; -}); -const defaults$1 = defaults; -function last(array) { - var length = array == null ? 0 : array.length; - return length ? array[length - 1] : void 0; -} -function createFind(findIndexFunc) { - return function(collection, predicate, fromIndex) { - var iterable = Object(collection); - if (!isArrayLike(collection)) { - var iteratee = baseIteratee(predicate); - collection = keys(collection); - predicate = function(key) { - return iteratee(iterable[key], key, iterable); - }; - } - var index = findIndexFunc(collection, predicate, fromIndex); - return index > -1 ? iterable[iteratee ? collection[index] : index] : void 0; - }; -} -var nativeMax$1 = Math.max; -function findIndex(array, predicate, fromIndex) { - var length = array == null ? 0 : array.length; - if (!length) { - return -1; - } - var index = fromIndex == null ? 0 : toInteger(fromIndex); - if (index < 0) { - index = nativeMax$1(length + index, 0); - } - return baseFindIndex(array, baseIteratee(predicate), index); -} -var find = createFind(findIndex); -const find$1 = find; -function baseMap(collection, iteratee) { - var index = -1, result = isArrayLike(collection) ? Array(collection.length) : []; - baseEach(collection, function(value, key, collection2) { - result[++index] = iteratee(value, key, collection2); - }); - return result; -} -function map(collection, iteratee) { - var func = isArray(collection) ? arrayMap : baseMap; - return func(collection, baseIteratee(iteratee)); -} -function forIn(object, iteratee) { - return object == null ? object : baseFor(object, castFunction(iteratee), keysIn); -} -function forOwn(object, iteratee) { - return object && baseForOwn(object, castFunction(iteratee)); -} -function baseGt(value, other) { - return value > other; -} -function baseLt(value, other) { - return value < other; -} -function mapValues(object, iteratee) { - var result = {}; - iteratee = baseIteratee(iteratee); - baseForOwn(object, function(value, key, object2) { - baseAssignValue(result, key, iteratee(value, key, object2)); - }); - return result; -} -function baseExtremum(array, iteratee, comparator) { - var index = -1, length = array.length; - while (++index < length) { - var value = array[index], current = iteratee(value); - if (current != null && (computed === void 0 ? current === current && !isSymbol(current) : comparator(current, computed))) { - var computed = current, result = value; - } - } - return result; -} -function max(array) { - return array && array.length ? baseExtremum(array, identity, baseGt) : void 0; -} -function min(array) { - return array && array.length ? baseExtremum(array, identity, baseLt) : void 0; -} -function minBy(array, iteratee) { - return array && array.length ? baseExtremum(array, baseIteratee(iteratee), baseLt) : void 0; -} -function baseSet(object, path, value, customizer) { - if (!isObject(object)) { - return object; - } - path = castPath(path, object); - var index = -1, length = path.length, lastIndex = length - 1, nested = object; - while (nested != null && ++index < length) { - var key = toKey(path[index]), newValue = value; - if (key === "__proto__" || key === "constructor" || key === "prototype") { - return object; - } - if (index != lastIndex) { - var objValue = nested[key]; - newValue = customizer ? customizer(objValue, key, nested) : void 0; - if (newValue === void 0) { - newValue = isObject(objValue) ? objValue : isIndex(path[index + 1]) ? [] : {}; - } - } - assignValue(nested, key, newValue); - nested = nested[key]; - } - return object; -} -function basePickBy(object, paths, predicate) { - var index = -1, length = paths.length, result = {}; - while (++index < length) { - var path = paths[index], value = baseGet(object, path); - if (predicate(value, path)) { - baseSet(result, castPath(path, object), value); - } - } - return result; -} -function baseSortBy(array, comparer) { - var length = array.length; - array.sort(comparer); - while (length--) { - array[length] = array[length].value; - } - return array; -} -function compareAscending(value, other) { - if (value !== other) { - var valIsDefined = value !== void 0, valIsNull = value === null, valIsReflexive = value === value, valIsSymbol = isSymbol(value); - var othIsDefined = other !== void 0, othIsNull = other === null, othIsReflexive = other === other, othIsSymbol = isSymbol(other); - if (!othIsNull && !othIsSymbol && !valIsSymbol && value > other || valIsSymbol && othIsDefined && othIsReflexive && !othIsNull && !othIsSymbol || valIsNull && othIsDefined && othIsReflexive || !valIsDefined && othIsReflexive || !valIsReflexive) { - return 1; - } - if (!valIsNull && !valIsSymbol && !othIsSymbol && value < other || othIsSymbol && valIsDefined && valIsReflexive && !valIsNull && !valIsSymbol || othIsNull && valIsDefined && valIsReflexive || !othIsDefined && valIsReflexive || !othIsReflexive) { - return -1; - } - } - return 0; -} -function compareMultiple(object, other, orders) { - var index = -1, objCriteria = object.criteria, othCriteria = other.criteria, length = objCriteria.length, ordersLength = orders.length; - while (++index < length) { - var result = compareAscending(objCriteria[index], othCriteria[index]); - if (result) { - if (index >= ordersLength) { - return result; - } - var order2 = orders[index]; - return result * (order2 == "desc" ? -1 : 1); - } - } - return object.index - other.index; -} -function baseOrderBy(collection, iteratees, orders) { - if (iteratees.length) { - iteratees = arrayMap(iteratees, function(iteratee) { - if (isArray(iteratee)) { - return function(value) { - return baseGet(value, iteratee.length === 1 ? iteratee[0] : iteratee); - }; - } - return iteratee; - }); - } else { - iteratees = [identity]; - } - var index = -1; - iteratees = arrayMap(iteratees, baseUnary(baseIteratee)); - var result = baseMap(collection, function(value, key, collection2) { - var criteria = arrayMap(iteratees, function(iteratee) { - return iteratee(value); - }); - return { "criteria": criteria, "index": ++index, "value": value }; - }); - return baseSortBy(result, function(object, other) { - return compareMultiple(object, other, orders); - }); -} -function basePick(object, paths) { - return basePickBy(object, paths, function(value, path) { - return hasIn(object, path); - }); -} -var pick = flatRest(function(object, paths) { - return object == null ? {} : basePick(object, paths); -}); -const pick$1 = pick; -var nativeCeil = Math.ceil, nativeMax = Math.max; -function baseRange(start, end, step, fromRight) { - var index = -1, length = nativeMax(nativeCeil((end - start) / (step || 1)), 0), result = Array(length); - while (length--) { - result[fromRight ? length : ++index] = start; - start += step; - } - return result; -} -function createRange(fromRight) { - return function(start, end, step) { - if (step && typeof step != "number" && isIterateeCall(start, end, step)) { - end = step = void 0; - } - start = toFinite(start); - if (end === void 0) { - end = start; - start = 0; - } else { - end = toFinite(end); - } - step = step === void 0 ? start < end ? 1 : -1 : toFinite(step); - return baseRange(start, end, step, fromRight); - }; -} -var range = createRange(); -const range$1 = range; -var sortBy = baseRest(function(collection, iteratees) { - if (collection == null) { - return []; - } - var length = iteratees.length; - if (length > 1 && isIterateeCall(collection, iteratees[0], iteratees[1])) { - iteratees = []; - } else if (length > 2 && isIterateeCall(iteratees[0], iteratees[1], iteratees[2])) { - iteratees = [iteratees[0]]; - } - return baseOrderBy(collection, baseFlatten(iteratees, 1), []); -}); -const sortBy$1 = sortBy; -var idCounter = 0; -function uniqueId(prefix) { - var id = ++idCounter; - return toString(prefix) + id; -} -function baseZipObject(props, values2, assignFunc) { - var index = -1, length = props.length, valsLength = values2.length, result = {}; - while (++index < length) { - var value = index < valsLength ? values2[index] : void 0; - assignFunc(result, props[index], value); - } - return result; -} -function zipObject(props, values2) { - return baseZipObject(props || [], values2 || [], assignValue); -} -class List { - constructor() { - var sentinel = {}; - sentinel._next = sentinel._prev = sentinel; - this._sentinel = sentinel; - } - dequeue() { - var sentinel = this._sentinel; - var entry = sentinel._prev; - if (entry !== sentinel) { - unlink(entry); - return entry; - } - } - enqueue(entry) { - var sentinel = this._sentinel; - if (entry._prev && entry._next) { - unlink(entry); - } - entry._next = sentinel._next; - sentinel._next._prev = entry; - sentinel._next = entry; - entry._prev = sentinel; - } - toString() { - var strs = []; - var sentinel = this._sentinel; - var curr = sentinel._prev; - while (curr !== sentinel) { - strs.push(JSON.stringify(curr, filterOutLinks)); - curr = curr._prev; - } - return "[" + strs.join(", ") + "]"; - } -} -function unlink(entry) { - entry._prev._next = entry._next; - entry._next._prev = entry._prev; - delete entry._next; - delete entry._prev; -} -function filterOutLinks(k, v) { - if (k !== "_next" && k !== "_prev") { - return v; - } -} -var DEFAULT_WEIGHT_FN = constant(1); -function greedyFAS(g, weightFn) { - if (g.nodeCount() <= 1) { - return []; - } - var state = buildState(g, weightFn || DEFAULT_WEIGHT_FN); - var results = doGreedyFAS(state.graph, state.buckets, state.zeroIdx); - return flatten( - map(results, function(e) { - return g.outEdges(e.v, e.w); - }) - ); -} -function doGreedyFAS(g, buckets, zeroIdx) { - var results = []; - var sources = buckets[buckets.length - 1]; - var sinks = buckets[0]; - var entry; - while (g.nodeCount()) { - while (entry = sinks.dequeue()) { - removeNode(g, buckets, zeroIdx, entry); - } - while (entry = sources.dequeue()) { - removeNode(g, buckets, zeroIdx, entry); - } - if (g.nodeCount()) { - for (var i = buckets.length - 2; i > 0; --i) { - entry = buckets[i].dequeue(); - if (entry) { - results = results.concat(removeNode(g, buckets, zeroIdx, entry, true)); - break; - } - } - } - } - return results; -} -function removeNode(g, buckets, zeroIdx, entry, collectPredecessors) { - var results = collectPredecessors ? [] : void 0; - forEach(g.inEdges(entry.v), function(edge) { - var weight = g.edge(edge); - var uEntry = g.node(edge.v); - if (collectPredecessors) { - results.push({ v: edge.v, w: edge.w }); - } - uEntry.out -= weight; - assignBucket(buckets, zeroIdx, uEntry); - }); - forEach(g.outEdges(entry.v), function(edge) { - var weight = g.edge(edge); - var w = edge.w; - var wEntry = g.node(w); - wEntry["in"] -= weight; - assignBucket(buckets, zeroIdx, wEntry); - }); - g.removeNode(entry.v); - return results; -} -function buildState(g, weightFn) { - var fasGraph = new Graph(); - var maxIn = 0; - var maxOut = 0; - forEach(g.nodes(), function(v) { - fasGraph.setNode(v, { v, in: 0, out: 0 }); - }); - forEach(g.edges(), function(e) { - var prevWeight = fasGraph.edge(e.v, e.w) || 0; - var weight = weightFn(e); - var edgeWeight = prevWeight + weight; - fasGraph.setEdge(e.v, e.w, edgeWeight); - maxOut = Math.max(maxOut, fasGraph.node(e.v).out += weight); - maxIn = Math.max(maxIn, fasGraph.node(e.w)["in"] += weight); - }); - var buckets = range$1(maxOut + maxIn + 3).map(function() { - return new List(); - }); - var zeroIdx = maxIn + 1; - forEach(fasGraph.nodes(), function(v) { - assignBucket(buckets, zeroIdx, fasGraph.node(v)); - }); - return { graph: fasGraph, buckets, zeroIdx }; -} -function assignBucket(buckets, zeroIdx, entry) { - if (!entry.out) { - buckets[0].enqueue(entry); - } else if (!entry["in"]) { - buckets[buckets.length - 1].enqueue(entry); - } else { - buckets[entry.out - entry["in"] + zeroIdx].enqueue(entry); - } -} -function run$2(g) { - var fas = g.graph().acyclicer === "greedy" ? greedyFAS(g, weightFn(g)) : dfsFAS(g); - forEach(fas, function(e) { - var label = g.edge(e); - g.removeEdge(e); - label.forwardName = e.name; - label.reversed = true; - g.setEdge(e.w, e.v, label, uniqueId("rev")); - }); - function weightFn(g2) { - return function(e) { - return g2.edge(e).weight; - }; - } -} -function dfsFAS(g) { - var fas = []; - var stack = {}; - var visited = {}; - function dfs2(v) { - if (has(visited, v)) { - return; - } - visited[v] = true; - stack[v] = true; - forEach(g.outEdges(v), function(e) { - if (has(stack, e.w)) { - fas.push(e); - } else { - dfs2(e.w); - } - }); - delete stack[v]; - } - forEach(g.nodes(), dfs2); - return fas; -} -function undo$2(g) { - forEach(g.edges(), function(e) { - var label = g.edge(e); - if (label.reversed) { - g.removeEdge(e); - var forwardName = label.forwardName; - delete label.reversed; - delete label.forwardName; - g.setEdge(e.w, e.v, label, forwardName); - } - }); -} -function addDummyNode(g, type, attrs, name) { - var v; - do { - v = uniqueId(name); - } while (g.hasNode(v)); - attrs.dummy = type; - g.setNode(v, attrs); - return v; -} -function simplify(g) { - var simplified = new Graph().setGraph(g.graph()); - forEach(g.nodes(), function(v) { - simplified.setNode(v, g.node(v)); - }); - forEach(g.edges(), function(e) { - var simpleLabel = simplified.edge(e.v, e.w) || { weight: 0, minlen: 1 }; - var label = g.edge(e); - simplified.setEdge(e.v, e.w, { - weight: simpleLabel.weight + label.weight, - minlen: Math.max(simpleLabel.minlen, label.minlen) - }); - }); - return simplified; -} -function asNonCompoundGraph(g) { - var simplified = new Graph({ multigraph: g.isMultigraph() }).setGraph(g.graph()); - forEach(g.nodes(), function(v) { - if (!g.children(v).length) { - simplified.setNode(v, g.node(v)); - } - }); - forEach(g.edges(), function(e) { - simplified.setEdge(e, g.edge(e)); - }); - return simplified; -} -function intersectRect(rect, point) { - var x = rect.x; - var y = rect.y; - var dx = point.x - x; - var dy = point.y - y; - var w = rect.width / 2; - var h = rect.height / 2; - if (!dx && !dy) { - throw new Error("Not possible to find intersection inside of the rectangle"); - } - var sx, sy; - if (Math.abs(dy) * w > Math.abs(dx) * h) { - if (dy < 0) { - h = -h; - } - sx = h * dx / dy; - sy = h; - } else { - if (dx < 0) { - w = -w; - } - sx = w; - sy = w * dy / dx; - } - return { x: x + sx, y: y + sy }; -} -function buildLayerMatrix(g) { - var layering = map(range$1(maxRank(g) + 1), function() { - return []; - }); - forEach(g.nodes(), function(v) { - var node = g.node(v); - var rank2 = node.rank; - if (!isUndefined(rank2)) { - layering[rank2][node.order] = v; - } - }); - return layering; -} -function normalizeRanks(g) { - var min$1 = min( - map(g.nodes(), function(v) { - return g.node(v).rank; - }) - ); - forEach(g.nodes(), function(v) { - var node = g.node(v); - if (has(node, "rank")) { - node.rank -= min$1; - } - }); -} -function removeEmptyRanks(g) { - var offset = min( - map(g.nodes(), function(v) { - return g.node(v).rank; - }) - ); - var layers = []; - forEach(g.nodes(), function(v) { - var rank2 = g.node(v).rank - offset; - if (!layers[rank2]) { - layers[rank2] = []; - } - layers[rank2].push(v); - }); - var delta = 0; - var nodeRankFactor = g.graph().nodeRankFactor; - forEach(layers, function(vs, i) { - if (isUndefined(vs) && i % nodeRankFactor !== 0) { - --delta; - } else if (delta) { - forEach(vs, function(v) { - g.node(v).rank += delta; - }); - } - }); -} -function addBorderNode$1(g, prefix, rank2, order2) { - var node = { - width: 0, - height: 0 - }; - if (arguments.length >= 4) { - node.rank = rank2; - node.order = order2; - } - return addDummyNode(g, "border", node, prefix); -} -function maxRank(g) { - return max( - map(g.nodes(), function(v) { - var rank2 = g.node(v).rank; - if (!isUndefined(rank2)) { - return rank2; - } - }) - ); -} -function partition(collection, fn) { - var result = { lhs: [], rhs: [] }; - forEach(collection, function(value) { - if (fn(value)) { - result.lhs.push(value); - } else { - result.rhs.push(value); - } - }); - return result; -} -function time(name, fn) { - var start = now$1(); - try { - return fn(); - } finally { - console.log(name + " time: " + (now$1() - start) + "ms"); - } -} -function notime(name, fn) { - return fn(); -} -function addBorderSegments(g) { - function dfs2(v) { - var children = g.children(v); - var node = g.node(v); - if (children.length) { - forEach(children, dfs2); - } - if (has(node, "minRank")) { - node.borderLeft = []; - node.borderRight = []; - for (var rank2 = node.minRank, maxRank2 = node.maxRank + 1; rank2 < maxRank2; ++rank2) { - addBorderNode(g, "borderLeft", "_bl", v, node, rank2); - addBorderNode(g, "borderRight", "_br", v, node, rank2); - } - } - } - forEach(g.children(), dfs2); -} -function addBorderNode(g, prop, prefix, sg, sgNode, rank2) { - var label = { width: 0, height: 0, rank: rank2, borderType: prop }; - var prev = sgNode[prop][rank2 - 1]; - var curr = addDummyNode(g, "border", label, prefix); - sgNode[prop][rank2] = curr; - g.setParent(curr, sg); - if (prev) { - g.setEdge(prev, curr, { weight: 1 }); - } -} -function adjust(g) { - var rankDir = g.graph().rankdir.toLowerCase(); - if (rankDir === "lr" || rankDir === "rl") { - swapWidthHeight(g); - } -} -function undo$1(g) { - var rankDir = g.graph().rankdir.toLowerCase(); - if (rankDir === "bt" || rankDir === "rl") { - reverseY(g); - } - if (rankDir === "lr" || rankDir === "rl") { - swapXY(g); - swapWidthHeight(g); - } -} -function swapWidthHeight(g) { - forEach(g.nodes(), function(v) { - swapWidthHeightOne(g.node(v)); - }); - forEach(g.edges(), function(e) { - swapWidthHeightOne(g.edge(e)); - }); -} -function swapWidthHeightOne(attrs) { - var w = attrs.width; - attrs.width = attrs.height; - attrs.height = w; -} -function reverseY(g) { - forEach(g.nodes(), function(v) { - reverseYOne(g.node(v)); - }); - forEach(g.edges(), function(e) { - var edge = g.edge(e); - forEach(edge.points, reverseYOne); - if (has(edge, "y")) { - reverseYOne(edge); - } - }); -} -function reverseYOne(attrs) { - attrs.y = -attrs.y; -} -function swapXY(g) { - forEach(g.nodes(), function(v) { - swapXYOne(g.node(v)); - }); - forEach(g.edges(), function(e) { - var edge = g.edge(e); - forEach(edge.points, swapXYOne); - if (has(edge, "x")) { - swapXYOne(edge); - } - }); -} -function swapXYOne(attrs) { - var x = attrs.x; - attrs.x = attrs.y; - attrs.y = x; -} -function run$1(g) { - g.graph().dummyChains = []; - forEach(g.edges(), function(edge) { - normalizeEdge(g, edge); - }); -} -function normalizeEdge(g, e) { - var v = e.v; - var vRank = g.node(v).rank; - var w = e.w; - var wRank = g.node(w).rank; - var name = e.name; - var edgeLabel = g.edge(e); - var labelRank = edgeLabel.labelRank; - if (wRank === vRank + 1) - return; - g.removeEdge(e); - var dummy, attrs, i; - for (i = 0, ++vRank; vRank < wRank; ++i, ++vRank) { - edgeLabel.points = []; - attrs = { - width: 0, - height: 0, - edgeLabel, - edgeObj: e, - rank: vRank - }; - dummy = addDummyNode(g, "edge", attrs, "_d"); - if (vRank === labelRank) { - attrs.width = edgeLabel.width; - attrs.height = edgeLabel.height; - attrs.dummy = "edge-label"; - attrs.labelpos = edgeLabel.labelpos; - } - g.setEdge(v, dummy, { weight: edgeLabel.weight }, name); - if (i === 0) { - g.graph().dummyChains.push(dummy); - } - v = dummy; - } - g.setEdge(v, w, { weight: edgeLabel.weight }, name); -} -function undo(g) { - forEach(g.graph().dummyChains, function(v) { - var node = g.node(v); - var origLabel = node.edgeLabel; - var w; - g.setEdge(node.edgeObj, origLabel); - while (node.dummy) { - w = g.successors(v)[0]; - g.removeNode(v); - origLabel.points.push({ x: node.x, y: node.y }); - if (node.dummy === "edge-label") { - origLabel.x = node.x; - origLabel.y = node.y; - origLabel.width = node.width; - origLabel.height = node.height; - } - v = w; - node = g.node(v); - } - }); -} -function longestPath(g) { - var visited = {}; - function dfs2(v) { - var label = g.node(v); - if (has(visited, v)) { - return label.rank; - } - visited[v] = true; - var rank2 = min( - map(g.outEdges(v), function(e) { - return dfs2(e.w) - g.edge(e).minlen; - }) - ); - if (rank2 === Number.POSITIVE_INFINITY || // return value of _.map([]) for Lodash 3 - rank2 === void 0 || // return value of _.map([]) for Lodash 4 - rank2 === null) { - rank2 = 0; - } - return label.rank = rank2; - } - forEach(g.sources(), dfs2); -} -function slack(g, e) { - return g.node(e.w).rank - g.node(e.v).rank - g.edge(e).minlen; -} -function feasibleTree(g) { - var t = new Graph({ directed: false }); - var start = g.nodes()[0]; - var size = g.nodeCount(); - t.setNode(start, {}); - var edge, delta; - while (tightTree(t, g) < size) { - edge = findMinSlackEdge(t, g); - delta = t.hasNode(edge.v) ? slack(g, edge) : -slack(g, edge); - shiftRanks(t, g, delta); - } - return t; -} -function tightTree(t, g) { - function dfs2(v) { - forEach(g.nodeEdges(v), function(e) { - var edgeV = e.v, w = v === edgeV ? e.w : edgeV; - if (!t.hasNode(w) && !slack(g, e)) { - t.setNode(w, {}); - t.setEdge(v, w, {}); - dfs2(w); - } - }); - } - forEach(t.nodes(), dfs2); - return t.nodeCount(); -} -function findMinSlackEdge(t, g) { - return minBy(g.edges(), function(e) { - if (t.hasNode(e.v) !== t.hasNode(e.w)) { - return slack(g, e); - } - }); -} -function shiftRanks(t, g, delta) { - forEach(t.nodes(), function(v) { - g.node(v).rank += delta; - }); -} -function CycleException() { -} -CycleException.prototype = new Error(); -function dfs$1(g, vs, order2) { - if (!isArray(vs)) { - vs = [vs]; - } - var navigation = (g.isDirected() ? g.successors : g.neighbors).bind(g); - var acc = []; - var visited = {}; - forEach(vs, function(v) { - if (!g.hasNode(v)) { - throw new Error("Graph does not have node: " + v); - } - doDfs(g, v, order2 === "post", visited, navigation, acc); - }); - return acc; -} -function doDfs(g, v, postorder2, visited, navigation, acc) { - if (!has(visited, v)) { - visited[v] = true; - if (!postorder2) { - acc.push(v); - } - forEach(navigation(v), function(w) { - doDfs(g, w, postorder2, visited, navigation, acc); - }); - if (postorder2) { - acc.push(v); - } - } -} -function postorder$1(g, vs) { - return dfs$1(g, vs, "post"); -} -function preorder(g, vs) { - return dfs$1(g, vs, "pre"); -} -networkSimplex.initLowLimValues = initLowLimValues; -networkSimplex.initCutValues = initCutValues; -networkSimplex.calcCutValue = calcCutValue; -networkSimplex.leaveEdge = leaveEdge; -networkSimplex.enterEdge = enterEdge; -networkSimplex.exchangeEdges = exchangeEdges; -function networkSimplex(g) { - g = simplify(g); - longestPath(g); - var t = feasibleTree(g); - initLowLimValues(t); - initCutValues(t, g); - var e, f; - while (e = leaveEdge(t)) { - f = enterEdge(t, g, e); - exchangeEdges(t, g, e, f); - } -} -function initCutValues(t, g) { - var vs = postorder$1(t, t.nodes()); - vs = vs.slice(0, vs.length - 1); - forEach(vs, function(v) { - assignCutValue(t, g, v); - }); -} -function assignCutValue(t, g, child) { - var childLab = t.node(child); - var parent = childLab.parent; - t.edge(child, parent).cutvalue = calcCutValue(t, g, child); -} -function calcCutValue(t, g, child) { - var childLab = t.node(child); - var parent = childLab.parent; - var childIsTail = true; - var graphEdge = g.edge(child, parent); - var cutValue = 0; - if (!graphEdge) { - childIsTail = false; - graphEdge = g.edge(parent, child); - } - cutValue = graphEdge.weight; - forEach(g.nodeEdges(child), function(e) { - var isOutEdge = e.v === child, other = isOutEdge ? e.w : e.v; - if (other !== parent) { - var pointsToHead = isOutEdge === childIsTail, otherWeight = g.edge(e).weight; - cutValue += pointsToHead ? otherWeight : -otherWeight; - if (isTreeEdge(t, child, other)) { - var otherCutValue = t.edge(child, other).cutvalue; - cutValue += pointsToHead ? -otherCutValue : otherCutValue; - } - } - }); - return cutValue; -} -function initLowLimValues(tree, root2) { - if (arguments.length < 2) { - root2 = tree.nodes()[0]; - } - dfsAssignLowLim(tree, {}, 1, root2); -} -function dfsAssignLowLim(tree, visited, nextLim, v, parent) { - var low = nextLim; - var label = tree.node(v); - visited[v] = true; - forEach(tree.neighbors(v), function(w) { - if (!has(visited, w)) { - nextLim = dfsAssignLowLim(tree, visited, nextLim, w, v); - } - }); - label.low = low; - label.lim = nextLim++; - if (parent) { - label.parent = parent; - } else { - delete label.parent; - } - return nextLim; -} -function leaveEdge(tree) { - return find$1(tree.edges(), function(e) { - return tree.edge(e).cutvalue < 0; - }); -} -function enterEdge(t, g, edge) { - var v = edge.v; - var w = edge.w; - if (!g.hasEdge(v, w)) { - v = edge.w; - w = edge.v; - } - var vLabel = t.node(v); - var wLabel = t.node(w); - var tailLabel = vLabel; - var flip = false; - if (vLabel.lim > wLabel.lim) { - tailLabel = wLabel; - flip = true; - } - var candidates = filter(g.edges(), function(edge2) { - return flip === isDescendant(t, t.node(edge2.v), tailLabel) && flip !== isDescendant(t, t.node(edge2.w), tailLabel); - }); - return minBy(candidates, function(edge2) { - return slack(g, edge2); - }); -} -function exchangeEdges(t, g, e, f) { - var v = e.v; - var w = e.w; - t.removeEdge(v, w); - t.setEdge(f.v, f.w, {}); - initLowLimValues(t); - initCutValues(t, g); - updateRanks(t, g); -} -function updateRanks(t, g) { - var root2 = find$1(t.nodes(), function(v) { - return !g.node(v).parent; - }); - var vs = preorder(t, root2); - vs = vs.slice(1); - forEach(vs, function(v) { - var parent = t.node(v).parent, edge = g.edge(v, parent), flipped = false; - if (!edge) { - edge = g.edge(parent, v); - flipped = true; - } - g.node(v).rank = g.node(parent).rank + (flipped ? edge.minlen : -edge.minlen); - }); -} -function isTreeEdge(tree, u, v) { - return tree.hasEdge(u, v); -} -function isDescendant(tree, vLabel, rootLabel) { - return rootLabel.low <= vLabel.lim && vLabel.lim <= rootLabel.lim; -} -function rank(g) { - switch (g.graph().ranker) { - case "network-simplex": - networkSimplexRanker(g); - break; - case "tight-tree": - tightTreeRanker(g); - break; - case "longest-path": - longestPathRanker(g); - break; - default: - networkSimplexRanker(g); - } -} -var longestPathRanker = longestPath; -function tightTreeRanker(g) { - longestPath(g); - feasibleTree(g); -} -function networkSimplexRanker(g) { - networkSimplex(g); -} -function run(g) { - var root2 = addDummyNode(g, "root", {}, "_root"); - var depths = treeDepths(g); - var height = max(values(depths)) - 1; - var nodeSep = 2 * height + 1; - g.graph().nestingRoot = root2; - forEach(g.edges(), function(e) { - g.edge(e).minlen *= nodeSep; - }); - var weight = sumWeights(g) + 1; - forEach(g.children(), function(child) { - dfs(g, root2, nodeSep, weight, height, depths, child); - }); - g.graph().nodeRankFactor = nodeSep; -} -function dfs(g, root2, nodeSep, weight, height, depths, v) { - var children = g.children(v); - if (!children.length) { - if (v !== root2) { - g.setEdge(root2, v, { weight: 0, minlen: nodeSep }); - } - return; - } - var top = addBorderNode$1(g, "_bt"); - var bottom = addBorderNode$1(g, "_bb"); - var label = g.node(v); - g.setParent(top, v); - label.borderTop = top; - g.setParent(bottom, v); - label.borderBottom = bottom; - forEach(children, function(child) { - dfs(g, root2, nodeSep, weight, height, depths, child); - var childNode = g.node(child); - var childTop = childNode.borderTop ? childNode.borderTop : child; - var childBottom = childNode.borderBottom ? childNode.borderBottom : child; - var thisWeight = childNode.borderTop ? weight : 2 * weight; - var minlen = childTop !== childBottom ? 1 : height - depths[v] + 1; - g.setEdge(top, childTop, { - weight: thisWeight, - minlen, - nestingEdge: true - }); - g.setEdge(childBottom, bottom, { - weight: thisWeight, - minlen, - nestingEdge: true - }); - }); - if (!g.parent(v)) { - g.setEdge(root2, top, { weight: 0, minlen: height + depths[v] }); - } -} -function treeDepths(g) { - var depths = {}; - function dfs2(v, depth) { - var children = g.children(v); - if (children && children.length) { - forEach(children, function(child) { - dfs2(child, depth + 1); - }); - } - depths[v] = depth; - } - forEach(g.children(), function(v) { - dfs2(v, 1); - }); - return depths; -} -function sumWeights(g) { - return reduce( - g.edges(), - function(acc, e) { - return acc + g.edge(e).weight; - }, - 0 - ); -} -function cleanup(g) { - var graphLabel = g.graph(); - g.removeNode(graphLabel.nestingRoot); - delete graphLabel.nestingRoot; - forEach(g.edges(), function(e) { - var edge = g.edge(e); - if (edge.nestingEdge) { - g.removeEdge(e); - } - }); -} -function addSubgraphConstraints(g, cg, vs) { - var prev = {}, rootPrev; - forEach(vs, function(v) { - var child = g.parent(v), parent, prevChild; - while (child) { - parent = g.parent(child); - if (parent) { - prevChild = prev[parent]; - prev[parent] = child; - } else { - prevChild = rootPrev; - rootPrev = child; - } - if (prevChild && prevChild !== child) { - cg.setEdge(prevChild, child); - return; - } - child = parent; - } - }); -} -function buildLayerGraph(g, rank2, relationship) { - var root2 = createRootNode(g), result = new Graph({ compound: true }).setGraph({ root: root2 }).setDefaultNodeLabel(function(v) { - return g.node(v); - }); - forEach(g.nodes(), function(v) { - var node = g.node(v), parent = g.parent(v); - if (node.rank === rank2 || node.minRank <= rank2 && rank2 <= node.maxRank) { - result.setNode(v); - result.setParent(v, parent || root2); - forEach(g[relationship](v), function(e) { - var u = e.v === v ? e.w : e.v, edge = result.edge(u, v), weight = !isUndefined(edge) ? edge.weight : 0; - result.setEdge(u, v, { weight: g.edge(e).weight + weight }); - }); - if (has(node, "minRank")) { - result.setNode(v, { - borderLeft: node.borderLeft[rank2], - borderRight: node.borderRight[rank2] - }); - } - } - }); - return result; -} -function createRootNode(g) { - var v; - while (g.hasNode(v = uniqueId("_root"))) - ; - return v; -} -function crossCount(g, layering) { - var cc = 0; - for (var i = 1; i < layering.length; ++i) { - cc += twoLayerCrossCount(g, layering[i - 1], layering[i]); - } - return cc; -} -function twoLayerCrossCount(g, northLayer, southLayer) { - var southPos = zipObject( - southLayer, - map(southLayer, function(v, i) { - return i; - }) - ); - var southEntries = flatten( - map(northLayer, function(v) { - return sortBy$1( - map(g.outEdges(v), function(e) { - return { pos: southPos[e.w], weight: g.edge(e).weight }; - }), - "pos" - ); - }) - ); - var firstIndex = 1; - while (firstIndex < southLayer.length) - firstIndex <<= 1; - var treeSize = 2 * firstIndex - 1; - firstIndex -= 1; - var tree = map(new Array(treeSize), function() { - return 0; - }); - var cc = 0; - forEach( - // @ts-expect-error - southEntries.forEach(function(entry) { - var index = entry.pos + firstIndex; - tree[index] += entry.weight; - var weightSum = 0; - while (index > 0) { - if (index % 2) { - weightSum += tree[index + 1]; - } - index = index - 1 >> 1; - tree[index] += entry.weight; - } - cc += entry.weight * weightSum; - }) - ); - return cc; -} -function initOrder(g) { - var visited = {}; - var simpleNodes = filter(g.nodes(), function(v) { - return !g.children(v).length; - }); - var maxRank2 = max( - map(simpleNodes, function(v) { - return g.node(v).rank; - }) - ); - var layers = map(range$1(maxRank2 + 1), function() { - return []; - }); - function dfs2(v) { - if (has(visited, v)) - return; - visited[v] = true; - var node = g.node(v); - layers[node.rank].push(v); - forEach(g.successors(v), dfs2); - } - var orderedVs = sortBy$1(simpleNodes, function(v) { - return g.node(v).rank; - }); - forEach(orderedVs, dfs2); - return layers; -} -function barycenter(g, movable) { - return map(movable, function(v) { - var inV = g.inEdges(v); - if (!inV.length) { - return { v }; - } else { - var result = reduce( - inV, - function(acc, e) { - var edge = g.edge(e), nodeU = g.node(e.v); - return { - sum: acc.sum + edge.weight * nodeU.order, - weight: acc.weight + edge.weight - }; - }, - { sum: 0, weight: 0 } - ); - return { - v, - barycenter: result.sum / result.weight, - weight: result.weight - }; - } - }); -} -function resolveConflicts(entries, cg) { - var mappedEntries = {}; - forEach(entries, function(entry, i) { - var tmp = mappedEntries[entry.v] = { - indegree: 0, - in: [], - out: [], - vs: [entry.v], - i - }; - if (!isUndefined(entry.barycenter)) { - tmp.barycenter = entry.barycenter; - tmp.weight = entry.weight; - } - }); - forEach(cg.edges(), function(e) { - var entryV = mappedEntries[e.v]; - var entryW = mappedEntries[e.w]; - if (!isUndefined(entryV) && !isUndefined(entryW)) { - entryW.indegree++; - entryV.out.push(mappedEntries[e.w]); - } - }); - var sourceSet = filter(mappedEntries, function(entry) { - return !entry.indegree; - }); - return doResolveConflicts(sourceSet); -} -function doResolveConflicts(sourceSet) { - var entries = []; - function handleIn(vEntry) { - return function(uEntry) { - if (uEntry.merged) { - return; - } - if (isUndefined(uEntry.barycenter) || isUndefined(vEntry.barycenter) || uEntry.barycenter >= vEntry.barycenter) { - mergeEntries(vEntry, uEntry); - } - }; - } - function handleOut(vEntry) { - return function(wEntry) { - wEntry["in"].push(vEntry); - if (--wEntry.indegree === 0) { - sourceSet.push(wEntry); - } - }; - } - while (sourceSet.length) { - var entry = sourceSet.pop(); - entries.push(entry); - forEach(entry["in"].reverse(), handleIn(entry)); - forEach(entry.out, handleOut(entry)); - } - return map( - filter(entries, function(entry2) { - return !entry2.merged; - }), - function(entry2) { - return pick$1(entry2, ["vs", "i", "barycenter", "weight"]); - } - ); -} -function mergeEntries(target, source) { - var sum = 0; - var weight = 0; - if (target.weight) { - sum += target.barycenter * target.weight; - weight += target.weight; - } - if (source.weight) { - sum += source.barycenter * source.weight; - weight += source.weight; - } - target.vs = source.vs.concat(target.vs); - target.barycenter = sum / weight; - target.weight = weight; - target.i = Math.min(source.i, target.i); - source.merged = true; -} -function sort(entries, biasRight) { - var parts = partition(entries, function(entry) { - return has(entry, "barycenter"); - }); - var sortable = parts.lhs, unsortable = sortBy$1(parts.rhs, function(entry) { - return -entry.i; - }), vs = [], sum = 0, weight = 0, vsIndex = 0; - sortable.sort(compareWithBias(!!biasRight)); - vsIndex = consumeUnsortable(vs, unsortable, vsIndex); - forEach(sortable, function(entry) { - vsIndex += entry.vs.length; - vs.push(entry.vs); - sum += entry.barycenter * entry.weight; - weight += entry.weight; - vsIndex = consumeUnsortable(vs, unsortable, vsIndex); - }); - var result = { vs: flatten(vs) }; - if (weight) { - result.barycenter = sum / weight; - result.weight = weight; - } - return result; -} -function consumeUnsortable(vs, unsortable, index) { - var last$1; - while (unsortable.length && (last$1 = last(unsortable)).i <= index) { - unsortable.pop(); - vs.push(last$1.vs); - index++; - } - return index; -} -function compareWithBias(bias) { - return function(entryV, entryW) { - if (entryV.barycenter < entryW.barycenter) { - return -1; - } else if (entryV.barycenter > entryW.barycenter) { - return 1; - } - return !bias ? entryV.i - entryW.i : entryW.i - entryV.i; - }; -} -function sortSubgraph(g, v, cg, biasRight) { - var movable = g.children(v); - var node = g.node(v); - var bl = node ? node.borderLeft : void 0; - var br = node ? node.borderRight : void 0; - var subgraphs = {}; - if (bl) { - movable = filter(movable, function(w) { - return w !== bl && w !== br; - }); - } - var barycenters = barycenter(g, movable); - forEach(barycenters, function(entry) { - if (g.children(entry.v).length) { - var subgraphResult = sortSubgraph(g, entry.v, cg, biasRight); - subgraphs[entry.v] = subgraphResult; - if (has(subgraphResult, "barycenter")) { - mergeBarycenters(entry, subgraphResult); - } - } - }); - var entries = resolveConflicts(barycenters, cg); - expandSubgraphs(entries, subgraphs); - var result = sort(entries, biasRight); - if (bl) { - result.vs = flatten([bl, result.vs, br]); - if (g.predecessors(bl).length) { - var blPred = g.node(g.predecessors(bl)[0]), brPred = g.node(g.predecessors(br)[0]); - if (!has(result, "barycenter")) { - result.barycenter = 0; - result.weight = 0; - } - result.barycenter = (result.barycenter * result.weight + blPred.order + brPred.order) / (result.weight + 2); - result.weight += 2; - } - } - return result; -} -function expandSubgraphs(entries, subgraphs) { - forEach(entries, function(entry) { - entry.vs = flatten( - entry.vs.map(function(v) { - if (subgraphs[v]) { - return subgraphs[v].vs; - } - return v; - }) - ); - }); -} -function mergeBarycenters(target, other) { - if (!isUndefined(target.barycenter)) { - target.barycenter = (target.barycenter * target.weight + other.barycenter * other.weight) / (target.weight + other.weight); - target.weight += other.weight; - } else { - target.barycenter = other.barycenter; - target.weight = other.weight; - } -} -function order(g) { - var maxRank$1 = maxRank(g), downLayerGraphs = buildLayerGraphs(g, range$1(1, maxRank$1 + 1), "inEdges"), upLayerGraphs = buildLayerGraphs(g, range$1(maxRank$1 - 1, -1, -1), "outEdges"); - var layering = initOrder(g); - assignOrder(g, layering); - var bestCC = Number.POSITIVE_INFINITY, best; - for (var i = 0, lastBest = 0; lastBest < 4; ++i, ++lastBest) { - sweepLayerGraphs(i % 2 ? downLayerGraphs : upLayerGraphs, i % 4 >= 2); - layering = buildLayerMatrix(g); - var cc = crossCount(g, layering); - if (cc < bestCC) { - lastBest = 0; - best = cloneDeep(layering); - bestCC = cc; - } - } - assignOrder(g, best); -} -function buildLayerGraphs(g, ranks, relationship) { - return map(ranks, function(rank2) { - return buildLayerGraph(g, rank2, relationship); - }); -} -function sweepLayerGraphs(layerGraphs, biasRight) { - var cg = new Graph(); - forEach(layerGraphs, function(lg) { - var root2 = lg.graph().root; - var sorted = sortSubgraph(lg, root2, cg, biasRight); - forEach(sorted.vs, function(v, i) { - lg.node(v).order = i; - }); - addSubgraphConstraints(lg, cg, sorted.vs); - }); -} -function assignOrder(g, layering) { - forEach(layering, function(layer) { - forEach(layer, function(v, i) { - g.node(v).order = i; - }); - }); -} -function parentDummyChains(g) { - var postorderNums = postorder(g); - forEach(g.graph().dummyChains, function(v) { - var node = g.node(v); - var edgeObj = node.edgeObj; - var pathData = findPath(g, postorderNums, edgeObj.v, edgeObj.w); - var path = pathData.path; - var lca = pathData.lca; - var pathIdx = 0; - var pathV = path[pathIdx]; - var ascending = true; - while (v !== edgeObj.w) { - node = g.node(v); - if (ascending) { - while ((pathV = path[pathIdx]) !== lca && g.node(pathV).maxRank < node.rank) { - pathIdx++; - } - if (pathV === lca) { - ascending = false; - } - } - if (!ascending) { - while (pathIdx < path.length - 1 && g.node(pathV = path[pathIdx + 1]).minRank <= node.rank) { - pathIdx++; - } - pathV = path[pathIdx]; - } - g.setParent(v, pathV); - v = g.successors(v)[0]; - } - }); -} -function findPath(g, postorderNums, v, w) { - var vPath = []; - var wPath = []; - var low = Math.min(postorderNums[v].low, postorderNums[w].low); - var lim = Math.max(postorderNums[v].lim, postorderNums[w].lim); - var parent; - var lca; - parent = v; - do { - parent = g.parent(parent); - vPath.push(parent); - } while (parent && (postorderNums[parent].low > low || lim > postorderNums[parent].lim)); - lca = parent; - parent = w; - while ((parent = g.parent(parent)) !== lca) { - wPath.push(parent); - } - return { path: vPath.concat(wPath.reverse()), lca }; -} -function postorder(g) { - var result = {}; - var lim = 0; - function dfs2(v) { - var low = lim; - forEach(g.children(v), dfs2); - result[v] = { low, lim: lim++ }; - } - forEach(g.children(), dfs2); - return result; -} -function findType1Conflicts(g, layering) { - var conflicts = {}; - function visitLayer(prevLayer, layer) { - var k0 = 0, scanPos = 0, prevLayerLength = prevLayer.length, lastNode = last(layer); - forEach(layer, function(v, i) { - var w = findOtherInnerSegmentNode(g, v), k1 = w ? g.node(w).order : prevLayerLength; - if (w || v === lastNode) { - forEach(layer.slice(scanPos, i + 1), function(scanNode) { - forEach(g.predecessors(scanNode), function(u) { - var uLabel = g.node(u), uPos = uLabel.order; - if ((uPos < k0 || k1 < uPos) && !(uLabel.dummy && g.node(scanNode).dummy)) { - addConflict(conflicts, u, scanNode); - } - }); - }); - scanPos = i + 1; - k0 = k1; - } - }); - return layer; - } - reduce(layering, visitLayer); - return conflicts; -} -function findType2Conflicts(g, layering) { - var conflicts = {}; - function scan(south, southPos, southEnd, prevNorthBorder, nextNorthBorder) { - var v; - forEach(range$1(southPos, southEnd), function(i) { - v = south[i]; - if (g.node(v).dummy) { - forEach(g.predecessors(v), function(u) { - var uNode = g.node(u); - if (uNode.dummy && (uNode.order < prevNorthBorder || uNode.order > nextNorthBorder)) { - addConflict(conflicts, u, v); - } - }); - } - }); - } - function visitLayer(north, south) { - var prevNorthPos = -1, nextNorthPos, southPos = 0; - forEach(south, function(v, southLookahead) { - if (g.node(v).dummy === "border") { - var predecessors = g.predecessors(v); - if (predecessors.length) { - nextNorthPos = g.node(predecessors[0]).order; - scan(south, southPos, southLookahead, prevNorthPos, nextNorthPos); - southPos = southLookahead; - prevNorthPos = nextNorthPos; - } - } - scan(south, southPos, south.length, nextNorthPos, north.length); - }); - return south; - } - reduce(layering, visitLayer); - return conflicts; -} -function findOtherInnerSegmentNode(g, v) { - if (g.node(v).dummy) { - return find$1(g.predecessors(v), function(u) { - return g.node(u).dummy; - }); - } -} -function addConflict(conflicts, v, w) { - if (v > w) { - var tmp = v; - v = w; - w = tmp; - } - var conflictsV = conflicts[v]; - if (!conflictsV) { - conflicts[v] = conflictsV = {}; - } - conflictsV[w] = true; -} -function hasConflict(conflicts, v, w) { - if (v > w) { - var tmp = v; - v = w; - w = tmp; - } - return has(conflicts[v], w); -} -function verticalAlignment(g, layering, conflicts, neighborFn) { - var root2 = {}, align = {}, pos = {}; - forEach(layering, function(layer) { - forEach(layer, function(v, order2) { - root2[v] = v; - align[v] = v; - pos[v] = order2; - }); - }); - forEach(layering, function(layer) { - var prevIdx = -1; - forEach(layer, function(v) { - var ws = neighborFn(v); - if (ws.length) { - ws = sortBy$1(ws, function(w2) { - return pos[w2]; - }); - var mp = (ws.length - 1) / 2; - for (var i = Math.floor(mp), il = Math.ceil(mp); i <= il; ++i) { - var w = ws[i]; - if (align[v] === v && prevIdx < pos[w] && !hasConflict(conflicts, v, w)) { - align[w] = v; - align[v] = root2[v] = root2[w]; - prevIdx = pos[w]; - } - } - } - }); - }); - return { root: root2, align }; -} -function horizontalCompaction(g, layering, root2, align, reverseSep) { - var xs = {}, blockG = buildBlockGraph(g, layering, root2, reverseSep), borderType = reverseSep ? "borderLeft" : "borderRight"; - function iterate(setXsFunc, nextNodesFunc) { - var stack = blockG.nodes(); - var elem = stack.pop(); - var visited = {}; - while (elem) { - if (visited[elem]) { - setXsFunc(elem); - } else { - visited[elem] = true; - stack.push(elem); - stack = stack.concat(nextNodesFunc(elem)); - } - elem = stack.pop(); - } - } - function pass1(elem) { - xs[elem] = blockG.inEdges(elem).reduce(function(acc, e) { - return Math.max(acc, xs[e.v] + blockG.edge(e)); - }, 0); - } - function pass2(elem) { - var min2 = blockG.outEdges(elem).reduce(function(acc, e) { - return Math.min(acc, xs[e.w] - blockG.edge(e)); - }, Number.POSITIVE_INFINITY); - var node = g.node(elem); - if (min2 !== Number.POSITIVE_INFINITY && node.borderType !== borderType) { - xs[elem] = Math.max(xs[elem], min2); - } - } - iterate(pass1, blockG.predecessors.bind(blockG)); - iterate(pass2, blockG.successors.bind(blockG)); - forEach(align, function(v) { - xs[v] = xs[root2[v]]; - }); - return xs; -} -function buildBlockGraph(g, layering, root2, reverseSep) { - var blockGraph = new Graph(), graphLabel = g.graph(), sepFn = sep(graphLabel.nodesep, graphLabel.edgesep, reverseSep); - forEach(layering, function(layer) { - var u; - forEach(layer, function(v) { - var vRoot = root2[v]; - blockGraph.setNode(vRoot); - if (u) { - var uRoot = root2[u], prevMax = blockGraph.edge(uRoot, vRoot); - blockGraph.setEdge(uRoot, vRoot, Math.max(sepFn(g, v, u), prevMax || 0)); - } - u = v; - }); - }); - return blockGraph; -} -function findSmallestWidthAlignment(g, xss) { - return minBy(values(xss), function(xs) { - var max2 = Number.NEGATIVE_INFINITY; - var min2 = Number.POSITIVE_INFINITY; - forIn(xs, function(x, v) { - var halfWidth = width(g, v) / 2; - max2 = Math.max(x + halfWidth, max2); - min2 = Math.min(x - halfWidth, min2); - }); - return max2 - min2; - }); -} -function alignCoordinates(xss, alignTo) { - var alignToVals = values(alignTo), alignToMin = min(alignToVals), alignToMax = max(alignToVals); - forEach(["u", "d"], function(vert) { - forEach(["l", "r"], function(horiz) { - var alignment = vert + horiz, xs = xss[alignment], delta; - if (xs === alignTo) - return; - var xsVals = values(xs); - delta = horiz === "l" ? alignToMin - min(xsVals) : alignToMax - max(xsVals); - if (delta) { - xss[alignment] = mapValues(xs, function(x) { - return x + delta; - }); - } - }); - }); -} -function balance(xss, align) { - return mapValues(xss.ul, function(ignore, v) { - if (align) { - return xss[align.toLowerCase()][v]; - } else { - var xs = sortBy$1(map(xss, v)); - return (xs[1] + xs[2]) / 2; - } - }); -} -function positionX(g) { - var layering = buildLayerMatrix(g); - var conflicts = merge(findType1Conflicts(g, layering), findType2Conflicts(g, layering)); - var xss = {}; - var adjustedLayering; - forEach(["u", "d"], function(vert) { - adjustedLayering = vert === "u" ? layering : values(layering).reverse(); - forEach(["l", "r"], function(horiz) { - if (horiz === "r") { - adjustedLayering = map(adjustedLayering, function(inner) { - return values(inner).reverse(); - }); - } - var neighborFn = (vert === "u" ? g.predecessors : g.successors).bind(g); - var align = verticalAlignment(g, adjustedLayering, conflicts, neighborFn); - var xs = horizontalCompaction(g, adjustedLayering, align.root, align.align, horiz === "r"); - if (horiz === "r") { - xs = mapValues(xs, function(x) { - return -x; - }); - } - xss[vert + horiz] = xs; - }); - }); - var smallestWidth = findSmallestWidthAlignment(g, xss); - alignCoordinates(xss, smallestWidth); - return balance(xss, g.graph().align); -} -function sep(nodeSep, edgeSep, reverseSep) { - return function(g, v, w) { - var vLabel = g.node(v); - var wLabel = g.node(w); - var sum = 0; - var delta; - sum += vLabel.width / 2; - if (has(vLabel, "labelpos")) { - switch (vLabel.labelpos.toLowerCase()) { - case "l": - delta = -vLabel.width / 2; - break; - case "r": - delta = vLabel.width / 2; - break; - } - } - if (delta) { - sum += reverseSep ? delta : -delta; - } - delta = 0; - sum += (vLabel.dummy ? edgeSep : nodeSep) / 2; - sum += (wLabel.dummy ? edgeSep : nodeSep) / 2; - sum += wLabel.width / 2; - if (has(wLabel, "labelpos")) { - switch (wLabel.labelpos.toLowerCase()) { - case "l": - delta = wLabel.width / 2; - break; - case "r": - delta = -wLabel.width / 2; - break; - } - } - if (delta) { - sum += reverseSep ? delta : -delta; - } - delta = 0; - return sum; - }; -} -function width(g, v) { - return g.node(v).width; -} -function position(g) { - g = asNonCompoundGraph(g); - positionY(g); - forOwn(positionX(g), function(x, v) { - g.node(v).x = x; - }); -} -function positionY(g) { - var layering = buildLayerMatrix(g); - var rankSep = g.graph().ranksep; - var prevY = 0; - forEach(layering, function(layer) { - var maxHeight = max( - map(layer, function(v) { - return g.node(v).height; - }) - ); - forEach(layer, function(v) { - g.node(v).y = prevY + maxHeight / 2; - }); - prevY += maxHeight + rankSep; - }); -} -function layout(g, opts) { - var time$1 = opts && opts.debugTiming ? time : notime; - time$1("layout", function() { - var layoutGraph = time$1(" buildLayoutGraph", function() { - return buildLayoutGraph(g); - }); - time$1(" runLayout", function() { - runLayout(layoutGraph, time$1); - }); - time$1(" updateInputGraph", function() { - updateInputGraph(g, layoutGraph); - }); - }); -} -function runLayout(g, time2) { - time2(" makeSpaceForEdgeLabels", function() { - makeSpaceForEdgeLabels(g); - }); - time2(" removeSelfEdges", function() { - removeSelfEdges(g); - }); - time2(" acyclic", function() { - run$2(g); - }); - time2(" nestingGraph.run", function() { - run(g); - }); - time2(" rank", function() { - rank(asNonCompoundGraph(g)); - }); - time2(" injectEdgeLabelProxies", function() { - injectEdgeLabelProxies(g); - }); - time2(" removeEmptyRanks", function() { - removeEmptyRanks(g); - }); - time2(" nestingGraph.cleanup", function() { - cleanup(g); - }); - time2(" normalizeRanks", function() { - normalizeRanks(g); - }); - time2(" assignRankMinMax", function() { - assignRankMinMax(g); - }); - time2(" removeEdgeLabelProxies", function() { - removeEdgeLabelProxies(g); - }); - time2(" normalize.run", function() { - run$1(g); - }); - time2(" parentDummyChains", function() { - parentDummyChains(g); - }); - time2(" addBorderSegments", function() { - addBorderSegments(g); - }); - time2(" order", function() { - order(g); - }); - time2(" insertSelfEdges", function() { - insertSelfEdges(g); - }); - time2(" adjustCoordinateSystem", function() { - adjust(g); - }); - time2(" position", function() { - position(g); - }); - time2(" positionSelfEdges", function() { - positionSelfEdges(g); - }); - time2(" removeBorderNodes", function() { - removeBorderNodes(g); - }); - time2(" normalize.undo", function() { - undo(g); - }); - time2(" fixupEdgeLabelCoords", function() { - fixupEdgeLabelCoords(g); - }); - time2(" undoCoordinateSystem", function() { - undo$1(g); - }); - time2(" translateGraph", function() { - translateGraph(g); - }); - time2(" assignNodeIntersects", function() { - assignNodeIntersects(g); - }); - time2(" reversePoints", function() { - reversePointsForReversedEdges(g); - }); - time2(" acyclic.undo", function() { - undo$2(g); - }); -} -function updateInputGraph(inputGraph, layoutGraph) { - forEach(inputGraph.nodes(), function(v) { - var inputLabel = inputGraph.node(v); - var layoutLabel = layoutGraph.node(v); - if (inputLabel) { - inputLabel.x = layoutLabel.x; - inputLabel.y = layoutLabel.y; - if (layoutGraph.children(v).length) { - inputLabel.width = layoutLabel.width; - inputLabel.height = layoutLabel.height; - } - } - }); - forEach(inputGraph.edges(), function(e) { - var inputLabel = inputGraph.edge(e); - var layoutLabel = layoutGraph.edge(e); - inputLabel.points = layoutLabel.points; - if (has(layoutLabel, "x")) { - inputLabel.x = layoutLabel.x; - inputLabel.y = layoutLabel.y; - } - }); - inputGraph.graph().width = layoutGraph.graph().width; - inputGraph.graph().height = layoutGraph.graph().height; -} -var graphNumAttrs = ["nodesep", "edgesep", "ranksep", "marginx", "marginy"]; -var graphDefaults = { ranksep: 50, edgesep: 20, nodesep: 50, rankdir: "tb" }; -var graphAttrs = ["acyclicer", "ranker", "rankdir", "align"]; -var nodeNumAttrs = ["width", "height"]; -var nodeDefaults = { width: 0, height: 0 }; -var edgeNumAttrs = ["minlen", "weight", "width", "height", "labeloffset"]; -var edgeDefaults = { - minlen: 1, - weight: 1, - width: 0, - height: 0, - labeloffset: 10, - labelpos: "r" -}; -var edgeAttrs = ["labelpos"]; -function buildLayoutGraph(inputGraph) { - var g = new Graph({ multigraph: true, compound: true }); - var graph = canonicalize(inputGraph.graph()); - g.setGraph( - merge({}, graphDefaults, selectNumberAttrs(graph, graphNumAttrs), pick$1(graph, graphAttrs)) - ); - forEach(inputGraph.nodes(), function(v) { - var node = canonicalize(inputGraph.node(v)); - g.setNode(v, defaults$1(selectNumberAttrs(node, nodeNumAttrs), nodeDefaults)); - g.setParent(v, inputGraph.parent(v)); - }); - forEach(inputGraph.edges(), function(e) { - var edge = canonicalize(inputGraph.edge(e)); - g.setEdge( - e, - merge({}, edgeDefaults, selectNumberAttrs(edge, edgeNumAttrs), pick$1(edge, edgeAttrs)) - ); - }); - return g; -} -function makeSpaceForEdgeLabels(g) { - var graph = g.graph(); - graph.ranksep /= 2; - forEach(g.edges(), function(e) { - var edge = g.edge(e); - edge.minlen *= 2; - if (edge.labelpos.toLowerCase() !== "c") { - if (graph.rankdir === "TB" || graph.rankdir === "BT") { - edge.width += edge.labeloffset; - } else { - edge.height += edge.labeloffset; - } - } - }); -} -function injectEdgeLabelProxies(g) { - forEach(g.edges(), function(e) { - var edge = g.edge(e); - if (edge.width && edge.height) { - var v = g.node(e.v); - var w = g.node(e.w); - var label = { rank: (w.rank - v.rank) / 2 + v.rank, e }; - addDummyNode(g, "edge-proxy", label, "_ep"); - } - }); -} -function assignRankMinMax(g) { - var maxRank2 = 0; - forEach(g.nodes(), function(v) { - var node = g.node(v); - if (node.borderTop) { - node.minRank = g.node(node.borderTop).rank; - node.maxRank = g.node(node.borderBottom).rank; - maxRank2 = max(maxRank2, node.maxRank); - } - }); - g.graph().maxRank = maxRank2; -} -function removeEdgeLabelProxies(g) { - forEach(g.nodes(), function(v) { - var node = g.node(v); - if (node.dummy === "edge-proxy") { - g.edge(node.e).labelRank = node.rank; - g.removeNode(v); - } - }); -} -function translateGraph(g) { - var minX = Number.POSITIVE_INFINITY; - var maxX = 0; - var minY = Number.POSITIVE_INFINITY; - var maxY = 0; - var graphLabel = g.graph(); - var marginX = graphLabel.marginx || 0; - var marginY = graphLabel.marginy || 0; - function getExtremes(attrs) { - var x = attrs.x; - var y = attrs.y; - var w = attrs.width; - var h = attrs.height; - minX = Math.min(minX, x - w / 2); - maxX = Math.max(maxX, x + w / 2); - minY = Math.min(minY, y - h / 2); - maxY = Math.max(maxY, y + h / 2); - } - forEach(g.nodes(), function(v) { - getExtremes(g.node(v)); - }); - forEach(g.edges(), function(e) { - var edge = g.edge(e); - if (has(edge, "x")) { - getExtremes(edge); - } - }); - minX -= marginX; - minY -= marginY; - forEach(g.nodes(), function(v) { - var node = g.node(v); - node.x -= minX; - node.y -= minY; - }); - forEach(g.edges(), function(e) { - var edge = g.edge(e); - forEach(edge.points, function(p) { - p.x -= minX; - p.y -= minY; - }); - if (has(edge, "x")) { - edge.x -= minX; - } - if (has(edge, "y")) { - edge.y -= minY; - } - }); - graphLabel.width = maxX - minX + marginX; - graphLabel.height = maxY - minY + marginY; -} -function assignNodeIntersects(g) { - forEach(g.edges(), function(e) { - var edge = g.edge(e); - var nodeV = g.node(e.v); - var nodeW = g.node(e.w); - var p1, p2; - if (!edge.points) { - edge.points = []; - p1 = nodeW; - p2 = nodeV; - } else { - p1 = edge.points[0]; - p2 = edge.points[edge.points.length - 1]; - } - edge.points.unshift(intersectRect(nodeV, p1)); - edge.points.push(intersectRect(nodeW, p2)); - }); -} -function fixupEdgeLabelCoords(g) { - forEach(g.edges(), function(e) { - var edge = g.edge(e); - if (has(edge, "x")) { - if (edge.labelpos === "l" || edge.labelpos === "r") { - edge.width -= edge.labeloffset; - } - switch (edge.labelpos) { - case "l": - edge.x -= edge.width / 2 + edge.labeloffset; - break; - case "r": - edge.x += edge.width / 2 + edge.labeloffset; - break; - } - } - }); -} -function reversePointsForReversedEdges(g) { - forEach(g.edges(), function(e) { - var edge = g.edge(e); - if (edge.reversed) { - edge.points.reverse(); - } - }); -} -function removeBorderNodes(g) { - forEach(g.nodes(), function(v) { - if (g.children(v).length) { - var node = g.node(v); - var t = g.node(node.borderTop); - var b = g.node(node.borderBottom); - var l = g.node(last(node.borderLeft)); - var r = g.node(last(node.borderRight)); - node.width = Math.abs(r.x - l.x); - node.height = Math.abs(b.y - t.y); - node.x = l.x + node.width / 2; - node.y = t.y + node.height / 2; - } - }); - forEach(g.nodes(), function(v) { - if (g.node(v).dummy === "border") { - g.removeNode(v); - } - }); -} -function removeSelfEdges(g) { - forEach(g.edges(), function(e) { - if (e.v === e.w) { - var node = g.node(e.v); - if (!node.selfEdges) { - node.selfEdges = []; - } - node.selfEdges.push({ e, label: g.edge(e) }); - g.removeEdge(e); - } - }); -} -function insertSelfEdges(g) { - var layers = buildLayerMatrix(g); - forEach(layers, function(layer) { - var orderShift = 0; - forEach(layer, function(v, i) { - var node = g.node(v); - node.order = i + orderShift; - forEach(node.selfEdges, function(selfEdge) { - addDummyNode( - g, - "selfedge", - { - width: selfEdge.label.width, - height: selfEdge.label.height, - rank: node.rank, - order: i + ++orderShift, - e: selfEdge.e, - label: selfEdge.label - }, - "_se" - ); - }); - delete node.selfEdges; - }); - }); -} -function positionSelfEdges(g) { - forEach(g.nodes(), function(v) { - var node = g.node(v); - if (node.dummy === "selfedge") { - var selfNode = g.node(node.e.v); - var x = selfNode.x + selfNode.width / 2; - var y = selfNode.y; - var dx = node.x - x; - var dy = selfNode.height / 2; - g.setEdge(node.e, node.label); - g.removeNode(v); - node.label.points = [ - { x: x + 2 * dx / 3, y: y - dy }, - { x: x + 5 * dx / 6, y: y - dy }, - { x: x + dx, y }, - { x: x + 5 * dx / 6, y: y + dy }, - { x: x + 2 * dx / 3, y: y + dy } - ]; - node.label.x = node.x; - node.label.y = node.y; - } - }); -} -function selectNumberAttrs(obj, attrs) { - return mapValues(pick$1(obj, attrs), Number); -} -function canonicalize(attrs) { - var newAttrs = {}; - forEach(attrs, function(v, k) { - newAttrs[k.toLowerCase()] = v; - }); - return newAttrs; -} -export { - defaults$1 as d, - layout as l, - map as m, - pick$1 as p, - range$1 as r, - uniqueId as u -}; |