@dagrejs/dagre
Advanced tools
Comparing version 1.1.0 to 1.1.1
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.run = run; | ||
exports.undo = undo; | ||
var _greedyFas = _interopRequireDefault(require("./greedy-fas.js")); | ||
var _util = require("./util.js"); | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
let greedyFAS = require("./greedy-fas"); | ||
let uniqueId = require("./util").uniqueId; | ||
module.exports = { | ||
run: run, | ||
undo: undo | ||
}; | ||
function run(g) { | ||
let fas = g.graph().acyclicer === "greedy" ? (0, _greedyFas.default)(g, weightFn(g)) : dfsFAS(g); | ||
let fas = (g.graph().acyclicer === "greedy" | ||
? greedyFAS(g, weightFn(g)) | ||
: dfsFAS(g)); | ||
fas.forEach(e => { | ||
@@ -18,4 +20,5 @@ let label = g.edge(e); | ||
label.reversed = true; | ||
g.setEdge(e.w, e.v, label, (0, _util.uniqueId)("rev")); | ||
g.setEdge(e.w, e.v, label, uniqueId("rev")); | ||
}); | ||
function weightFn(g) { | ||
@@ -27,2 +30,3 @@ return e => { | ||
} | ||
function dfsFAS(g) { | ||
@@ -32,2 +36,3 @@ let fas = []; | ||
let visited = {}; | ||
function dfs(v) { | ||
@@ -48,5 +53,7 @@ if (visited.hasOwnProperty(v)) { | ||
} | ||
g.nodes().forEach(dfs); | ||
return fas; | ||
} | ||
function undo(g) { | ||
@@ -57,2 +64,3 @@ g.edges().forEach(e => { | ||
g.removeEdge(e); | ||
let forwardName = label.forwardName; | ||
@@ -59,0 +67,0 @@ delete label.reversed; |
@@ -1,10 +0,5 @@ | ||
"use strict"; | ||
let util = require("./util"); | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = addBorderSegments; | ||
var util = _interopRequireWildcard(require("./util.js")); | ||
function _getRequireWildcardCache(e) { if ("function" != typeof WeakMap) return null; var r = new WeakMap(), t = new WeakMap(); return (_getRequireWildcardCache = function (e) { return e ? t : r; })(e); } | ||
function _interopRequireWildcard(e, r) { if (!r && e && e.__esModule) return e; if (null === e || "object" != typeof e && "function" != typeof e) return { default: e }; var t = _getRequireWildcardCache(r); if (t && t.has(e)) return t.get(e); var n = { __proto__: null }, a = Object.defineProperty && Object.getOwnPropertyDescriptor; for (var u in e) if ("default" !== u && Object.prototype.hasOwnProperty.call(e, u)) { var i = a ? Object.getOwnPropertyDescriptor(e, u) : null; i && (i.get || i.set) ? Object.defineProperty(n, u, i) : n[u] = e[u]; } return n.default = e, t && t.set(e, n), n; } | ||
module.exports = addBorderSegments; | ||
function addBorderSegments(g) { | ||
@@ -17,6 +12,9 @@ function dfs(v) { | ||
} | ||
if (node.hasOwnProperty("minRank")) { | ||
node.borderLeft = []; | ||
node.borderRight = []; | ||
for (let rank = node.minRank, maxRank = node.maxRank + 1; rank < maxRank; ++rank) { | ||
for (let rank = node.minRank, maxRank = node.maxRank + 1; | ||
rank < maxRank; | ||
++rank) { | ||
addBorderNode(g, "borderLeft", "_bl", v, node, rank); | ||
@@ -27,11 +25,8 @@ addBorderNode(g, "borderRight", "_br", v, node, rank); | ||
} | ||
g.children().forEach(dfs); | ||
} | ||
function addBorderNode(g, prop, prefix, sg, sgNode, rank) { | ||
let label = { | ||
width: 0, | ||
height: 0, | ||
rank: rank, | ||
borderType: prop | ||
}; | ||
let label = { width: 0, height: 0, rank: rank, borderType: prop }; | ||
let prev = sgNode[prop][rank - 1]; | ||
@@ -42,7 +37,4 @@ let curr = util.addDummyNode(g, "border", label, prefix); | ||
if (prev) { | ||
g.setEdge(prev, curr, { | ||
weight: 1 | ||
}); | ||
g.setEdge(prev, curr, { weight: 1 }); | ||
} | ||
} | ||
module.exports = exports.default; |
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.adjust = adjust; | ||
exports.undo = undo; | ||
module.exports = { | ||
adjust: adjust, | ||
undo: undo | ||
}; | ||
function adjust(g) { | ||
@@ -14,2 +14,3 @@ let rankDir = g.graph().rankdir.toLowerCase(); | ||
} | ||
function undo(g) { | ||
@@ -20,2 +21,3 @@ let rankDir = g.graph().rankdir.toLowerCase(); | ||
} | ||
if (rankDir === "lr" || rankDir === "rl") { | ||
@@ -26,2 +28,3 @@ swapXY(g); | ||
} | ||
function swapWidthHeight(g) { | ||
@@ -31,2 +34,3 @@ g.nodes().forEach(v => swapWidthHeightOne(g.node(v))); | ||
} | ||
function swapWidthHeightOne(attrs) { | ||
@@ -37,4 +41,6 @@ let w = attrs.width; | ||
} | ||
function reverseY(g) { | ||
g.nodes().forEach(v => reverseYOne(g.node(v))); | ||
g.edges().forEach(e => { | ||
@@ -48,7 +54,10 @@ let edge = g.edge(e); | ||
} | ||
function reverseYOne(attrs) { | ||
attrs.y = -attrs.y; | ||
} | ||
function swapXY(g) { | ||
g.nodes().forEach(v => swapXYOne(g.node(v))); | ||
g.edges().forEach(e => { | ||
@@ -62,2 +71,3 @@ let edge = g.edge(e); | ||
} | ||
function swapXYOne(attrs) { | ||
@@ -64,0 +74,0 @@ let x = attrs.x; |
@@ -1,7 +0,1 @@ | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = void 0; | ||
/* | ||
@@ -18,2 +12,3 @@ * Simple doubly linked list implementation derived from Cormen, et al., | ||
} | ||
dequeue() { | ||
@@ -27,2 +22,3 @@ let sentinel = this._sentinel; | ||
} | ||
enqueue(entry) { | ||
@@ -38,2 +34,3 @@ let sentinel = this._sentinel; | ||
} | ||
toString() { | ||
@@ -50,3 +47,3 @@ let strs = []; | ||
} | ||
exports.default = List; | ||
function unlink(entry) { | ||
@@ -58,2 +55,3 @@ entry._prev._next = entry._next; | ||
} | ||
function filterOutLinks(k, v) { | ||
@@ -64,2 +62,3 @@ if (k !== "_next" && k !== "_prev") { | ||
} | ||
module.exports = exports.default; | ||
module.exports = List; |
@@ -1,13 +0,7 @@ | ||
"use strict"; | ||
let util = require("./util"); | ||
let Graph = require("@dagrejs/graphlib").Graph; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = debugOrdering; | ||
var util = _interopRequireWildcard(require("./util.js")); | ||
var _graphlib = require("@dagrejs/graphlib"); | ||
function _getRequireWildcardCache(e) { if ("function" != typeof WeakMap) return null; var r = new WeakMap(), t = new WeakMap(); return (_getRequireWildcardCache = function (e) { return e ? t : r; })(e); } | ||
function _interopRequireWildcard(e, r) { if (!r && e && e.__esModule) return e; if (null === e || "object" != typeof e && "function" != typeof e) return { default: e }; var t = _getRequireWildcardCache(r); if (t && t.has(e)) return t.get(e); var n = { __proto__: null }, a = Object.defineProperty && Object.getOwnPropertyDescriptor; for (var u in e) if ("default" !== u && Object.prototype.hasOwnProperty.call(e, u)) { var i = a ? Object.getOwnPropertyDescriptor(e, u) : null; i && (i.get || i.set) ? Object.defineProperty(n, u, i) : n[u] = e[u]; } return n.default = e, t && t.set(e, n), n; } | ||
// web-devs write a <script type="importmap"> to map | ||
// nodejs paths to actual http://paths | ||
module.exports = { | ||
debugOrdering: debugOrdering | ||
}; | ||
@@ -17,27 +11,22 @@ /* istanbul ignore next */ | ||
let layerMatrix = util.buildLayerMatrix(g); | ||
let h = new _graphlib.Graph({ | ||
compound: true, | ||
multigraph: true | ||
}).setGraph({}); | ||
let h = new Graph({ compound: true, multigraph: true }).setGraph({}); | ||
g.nodes().forEach(v => { | ||
h.setNode(v, { | ||
label: v | ||
}); | ||
h.setNode(v, { label: v }); | ||
h.setParent(v, "layer" + g.node(v).rank); | ||
}); | ||
g.edges().forEach(e => h.setEdge(e.v, e.w, {}, e.name)); | ||
layerMatrix.forEach((layer, i) => { | ||
let layerV = "layer" + i; | ||
h.setNode(layerV, { | ||
rank: "same" | ||
}); | ||
h.setNode(layerV, { rank: "same" }); | ||
layer.reduce((u, v) => { | ||
h.setEdge(u, v, { | ||
style: "invis" | ||
}); | ||
h.setEdge(u, v, { style: "invis" }); | ||
return v; | ||
}); | ||
}); | ||
return h; | ||
} | ||
module.exports = exports.default; |
@@ -1,13 +0,4 @@ | ||
"use strict"; | ||
let Graph = require("@dagrejs/graphlib").Graph; | ||
let List = require("./data/list"); | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = greedyFAS; | ||
var _graphlib = require("@dagrejs/graphlib"); | ||
var _list = _interopRequireDefault(require("./data/list.js")); | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
// web-devs write a <script type="importmap"> to map | ||
// nodejs paths to actual http://paths | ||
/* | ||
@@ -20,4 +11,6 @@ * A greedy heuristic for finding a feedback arc set for a graph. A feedback | ||
*/ | ||
module.exports = greedyFAS; | ||
let DEFAULT_WEIGHT_FN = () => 1; | ||
function greedyFAS(g, weightFn) { | ||
@@ -33,2 +26,3 @@ if (g.nodeCount() <= 1) { | ||
} | ||
function doGreedyFAS(g, buckets, zeroIdx) { | ||
@@ -38,10 +32,7 @@ let results = []; | ||
let sinks = buckets[0]; | ||
let entry; | ||
while (g.nodeCount()) { | ||
while (entry = sinks.dequeue()) { | ||
removeNode(g, buckets, zeroIdx, entry); | ||
} | ||
while (entry = sources.dequeue()) { | ||
removeNode(g, buckets, zeroIdx, entry); | ||
} | ||
while ((entry = sinks.dequeue())) { removeNode(g, buckets, zeroIdx, entry); } | ||
while ((entry = sources.dequeue())) { removeNode(g, buckets, zeroIdx, entry); } | ||
if (g.nodeCount()) { | ||
@@ -57,18 +48,21 @@ for (let i = buckets.length - 2; i > 0; --i) { | ||
} | ||
return results; | ||
} | ||
function removeNode(g, buckets, zeroIdx, entry, collectPredecessors) { | ||
let results = collectPredecessors ? [] : undefined; | ||
g.inEdges(entry.v).forEach(edge => { | ||
let weight = g.edge(edge); | ||
let uEntry = g.node(edge.v); | ||
if (collectPredecessors) { | ||
results.push({ | ||
v: edge.v, | ||
w: edge.w | ||
}); | ||
results.push({ v: edge.v, w: edge.w }); | ||
} | ||
uEntry.out -= weight; | ||
assignBucket(buckets, zeroIdx, uEntry); | ||
}); | ||
g.outEdges(entry.v).forEach(edge => { | ||
@@ -81,15 +75,15 @@ let weight = g.edge(edge); | ||
}); | ||
g.removeNode(entry.v); | ||
return results; | ||
} | ||
function buildState(g, weightFn) { | ||
let fasGraph = new _graphlib.Graph(); | ||
let fasGraph = new Graph(); | ||
let maxIn = 0; | ||
let maxOut = 0; | ||
g.nodes().forEach(v => { | ||
fasGraph.setNode(v, { | ||
v: v, | ||
"in": 0, | ||
out: 0 | ||
}); | ||
fasGraph.setNode(v, { v: v, "in": 0, out: 0 }); | ||
}); | ||
@@ -105,15 +99,15 @@ | ||
maxOut = Math.max(maxOut, fasGraph.node(e.v).out += weight); | ||
maxIn = Math.max(maxIn, fasGraph.node(e.w)["in"] += weight); | ||
maxIn = Math.max(maxIn, fasGraph.node(e.w)["in"] += weight); | ||
}); | ||
let buckets = range(maxOut + maxIn + 3).map(() => new _list.default()); | ||
let buckets = range(maxOut + maxIn + 3).map(() => new List()); | ||
let zeroIdx = maxIn + 1; | ||
fasGraph.nodes().forEach(v => { | ||
assignBucket(buckets, zeroIdx, fasGraph.node(v)); | ||
}); | ||
return { | ||
graph: fasGraph, | ||
buckets: buckets, | ||
zeroIdx: zeroIdx | ||
}; | ||
return { graph: fasGraph, buckets: buckets, zeroIdx: zeroIdx }; | ||
} | ||
function assignBucket(buckets, zeroIdx, entry) { | ||
@@ -128,2 +122,3 @@ if (!entry.out) { | ||
} | ||
function range(limit) { | ||
@@ -134,4 +129,4 @@ const range = []; | ||
} | ||
return range; | ||
} | ||
module.exports = exports.default; |
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = layout; | ||
var acyclic = _interopRequireWildcard(require("./acyclic.js")); | ||
var normalize = _interopRequireWildcard(require("./normalize.js")); | ||
var _index = _interopRequireDefault(require("./rank/index.js")); | ||
var _parentDummyChains = _interopRequireDefault(require("./parent-dummy-chains.js")); | ||
var nestingGraph = _interopRequireWildcard(require("./nesting-graph.js")); | ||
var _addBorderSegments = _interopRequireDefault(require("./add-border-segments.js")); | ||
var coordinateSystem = _interopRequireWildcard(require("./coordinate-system.js")); | ||
var _index2 = _interopRequireDefault(require("./order/index.js")); | ||
var _index3 = _interopRequireDefault(require("./position/index.js")); | ||
var util = _interopRequireWildcard(require("./util.js")); | ||
var _graphlib = require("@dagrejs/graphlib"); | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
function _getRequireWildcardCache(e) { if ("function" != typeof WeakMap) return null; var r = new WeakMap(), t = new WeakMap(); return (_getRequireWildcardCache = function (e) { return e ? t : r; })(e); } | ||
function _interopRequireWildcard(e, r) { if (!r && e && e.__esModule) return e; if (null === e || "object" != typeof e && "function" != typeof e) return { default: e }; var t = _getRequireWildcardCache(r); if (t && t.has(e)) return t.get(e); var n = { __proto__: null }, a = Object.defineProperty && Object.getOwnPropertyDescriptor; for (var u in e) if ("default" !== u && Object.prototype.hasOwnProperty.call(e, u)) { var i = a ? Object.getOwnPropertyDescriptor(e, u) : null; i && (i.get || i.set) ? Object.defineProperty(n, u, i) : n[u] = e[u]; } return n.default = e, t && t.set(e, n), n; } | ||
const removeEmptyRanks = util.removeEmptyRanks; | ||
const normalizeRanks = util.normalizeRanks; | ||
let acyclic = require("./acyclic"); | ||
let normalize = require("./normalize"); | ||
let rank = require("./rank"); | ||
let normalizeRanks = require("./util").normalizeRanks; | ||
let parentDummyChains = require("./parent-dummy-chains"); | ||
let removeEmptyRanks = require("./util").removeEmptyRanks; | ||
let nestingGraph = require("./nesting-graph"); | ||
let addBorderSegments = require("./add-border-segments"); | ||
let coordinateSystem = require("./coordinate-system"); | ||
let order = require("./order"); | ||
let position = require("./position"); | ||
let util = require("./util"); | ||
let Graph = require("@dagrejs/graphlib").Graph; | ||
module.exports = layout; | ||
function layout(g, opts) { | ||
let time = opts && opts.debugTiming ? util.time : util.notime; | ||
time("layout", () => { | ||
let layoutGraph = time(" buildLayoutGraph", () => buildLayoutGraph(g)); | ||
time(" runLayout", () => runLayout(layoutGraph, time)); | ||
let layoutGraph = | ||
time(" buildLayoutGraph", () => buildLayoutGraph(g)); | ||
time(" runLayout", () => runLayout(layoutGraph, time)); | ||
time(" updateInputGraph", () => updateInputGraph(g, layoutGraph)); | ||
}); | ||
} | ||
function runLayout(g, time) { | ||
time(" makeSpaceForEdgeLabels", () => makeSpaceForEdgeLabels(g)); | ||
time(" removeSelfEdges", () => removeSelfEdges(g)); | ||
time(" acyclic", () => acyclic.run(g)); | ||
time(" nestingGraph.run", () => nestingGraph.run(g)); | ||
time(" rank", () => (0, _index.default)(util.asNonCompoundGraph(g))); | ||
time(" removeSelfEdges", () => removeSelfEdges(g)); | ||
time(" acyclic", () => acyclic.run(g)); | ||
time(" nestingGraph.run", () => nestingGraph.run(g)); | ||
time(" rank", () => rank(util.asNonCompoundGraph(g))); | ||
time(" injectEdgeLabelProxies", () => injectEdgeLabelProxies(g)); | ||
time(" removeEmptyRanks", () => removeEmptyRanks(g)); | ||
time(" nestingGraph.cleanup", () => nestingGraph.cleanup(g)); | ||
time(" normalizeRanks", () => normalizeRanks(g)); | ||
time(" assignRankMinMax", () => assignRankMinMax(g)); | ||
time(" removeEmptyRanks", () => removeEmptyRanks(g)); | ||
time(" nestingGraph.cleanup", () => nestingGraph.cleanup(g)); | ||
time(" normalizeRanks", () => normalizeRanks(g)); | ||
time(" assignRankMinMax", () => assignRankMinMax(g)); | ||
time(" removeEdgeLabelProxies", () => removeEdgeLabelProxies(g)); | ||
time(" normalize.run", () => normalize.run(g)); | ||
time(" parentDummyChains", () => (0, _parentDummyChains.default)(g)); | ||
time(" addBorderSegments", () => (0, _addBorderSegments.default)(g)); | ||
time(" order", () => (0, _index2.default)(g)); | ||
time(" insertSelfEdges", () => insertSelfEdges(g)); | ||
time(" normalize.run", () => normalize.run(g)); | ||
time(" parentDummyChains", () => parentDummyChains(g)); | ||
time(" addBorderSegments", () => addBorderSegments(g)); | ||
time(" order", () => order(g)); | ||
time(" insertSelfEdges", () => insertSelfEdges(g)); | ||
time(" adjustCoordinateSystem", () => coordinateSystem.adjust(g)); | ||
time(" position", () => (0, _index3.default)(g)); | ||
time(" positionSelfEdges", () => positionSelfEdges(g)); | ||
time(" removeBorderNodes", () => removeBorderNodes(g)); | ||
time(" normalize.undo", () => normalize.undo(g)); | ||
time(" fixupEdgeLabelCoords", () => fixupEdgeLabelCoords(g)); | ||
time(" undoCoordinateSystem", () => coordinateSystem.undo(g)); | ||
time(" translateGraph", () => translateGraph(g)); | ||
time(" assignNodeIntersects", () => assignNodeIntersects(g)); | ||
time(" reversePoints", () => reversePointsForReversedEdges(g)); | ||
time(" acyclic.undo", () => acyclic.undo(g)); | ||
time(" position", () => position(g)); | ||
time(" positionSelfEdges", () => positionSelfEdges(g)); | ||
time(" removeBorderNodes", () => removeBorderNodes(g)); | ||
time(" normalize.undo", () => normalize.undo(g)); | ||
time(" fixupEdgeLabelCoords", () => fixupEdgeLabelCoords(g)); | ||
time(" undoCoordinateSystem", () => coordinateSystem.undo(g)); | ||
time(" translateGraph", () => translateGraph(g)); | ||
time(" assignNodeIntersects", () => assignNodeIntersects(g)); | ||
time(" reversePoints", () => reversePointsForReversedEdges(g)); | ||
time(" acyclic.undo", () => acyclic.undo(g)); | ||
} | ||
@@ -71,2 +69,3 @@ | ||
let layoutLabel = layoutGraph.node(v); | ||
if (inputLabel) { | ||
@@ -76,2 +75,3 @@ inputLabel.x = layoutLabel.x; | ||
inputLabel.rank = layoutLabel.rank; | ||
if (layoutGraph.children(v).length) { | ||
@@ -83,5 +83,7 @@ inputLabel.width = layoutLabel.width; | ||
}); | ||
inputGraph.edges().forEach(e => { | ||
let inputLabel = inputGraph.edge(e); | ||
let layoutLabel = layoutGraph.edge(e); | ||
inputLabel.points = layoutLabel.points; | ||
@@ -93,26 +95,16 @@ if (layoutLabel.hasOwnProperty("x")) { | ||
}); | ||
inputGraph.graph().width = layoutGraph.graph().width; | ||
inputGraph.graph().height = layoutGraph.graph().height; | ||
} | ||
let graphNumAttrs = ["nodesep", "edgesep", "ranksep", "marginx", "marginy"]; | ||
let graphDefaults = { | ||
ranksep: 50, | ||
edgesep: 20, | ||
nodesep: 50, | ||
rankdir: "tb" | ||
}; | ||
let graphDefaults = { ranksep: 50, edgesep: 20, nodesep: 50, rankdir: "tb" }; | ||
let graphAttrs = ["acyclicer", "ranker", "rankdir", "align"]; | ||
let nodeNumAttrs = ["width", "height"]; | ||
let nodeDefaults = { | ||
width: 0, | ||
height: 0 | ||
}; | ||
let nodeDefaults = { width: 0, height: 0 }; | ||
let edgeNumAttrs = ["minlen", "weight", "width", "height", "labeloffset"]; | ||
let edgeDefaults = { | ||
minlen: 1, | ||
weight: 1, | ||
width: 0, | ||
height: 0, | ||
labeloffset: 10, | ||
labelpos: "r" | ||
minlen: 1, weight: 1, width: 0, height: 0, | ||
labeloffset: 10, labelpos: "r" | ||
}; | ||
@@ -128,8 +120,10 @@ let edgeAttrs = ["labelpos"]; | ||
function buildLayoutGraph(inputGraph) { | ||
let g = new _graphlib.Graph({ | ||
multigraph: true, | ||
compound: true | ||
}); | ||
let g = new Graph({ multigraph: true, compound: true }); | ||
let graph = canonicalize(inputGraph.graph()); | ||
g.setGraph(Object.assign({}, graphDefaults, selectNumberAttrs(graph, graphNumAttrs), util.pick(graph, graphAttrs))); | ||
g.setGraph(Object.assign({}, | ||
graphDefaults, | ||
selectNumberAttrs(graph, graphNumAttrs), | ||
util.pick(graph, graphAttrs))); | ||
inputGraph.nodes().forEach(v => { | ||
@@ -143,9 +137,15 @@ let node = canonicalize(inputGraph.node(v)); | ||
}); | ||
g.setNode(v, newNode); | ||
g.setParent(v, inputGraph.parent(v)); | ||
}); | ||
inputGraph.edges().forEach(e => { | ||
let edge = canonicalize(inputGraph.edge(e)); | ||
g.setEdge(e, Object.assign({}, edgeDefaults, selectNumberAttrs(edge, edgeNumAttrs), util.pick(edge, edgeAttrs))); | ||
g.setEdge(e, Object.assign({}, | ||
edgeDefaults, | ||
selectNumberAttrs(edge, edgeNumAttrs), | ||
util.pick(edge, edgeAttrs))); | ||
}); | ||
return g; | ||
@@ -190,6 +190,3 @@ } | ||
let w = g.node(e.w); | ||
let label = { | ||
rank: (w.rank - v.rank) / 2 + v.rank, | ||
e: e | ||
}; | ||
let label = { rank: (w.rank - v.rank) / 2 + v.rank, e: e }; | ||
util.addDummyNode(g, "edge-proxy", label, "_ep"); | ||
@@ -199,2 +196,3 @@ } | ||
} | ||
function assignRankMinMax(g) { | ||
@@ -212,2 +210,3 @@ let maxRank = 0; | ||
} | ||
function removeEdgeLabelProxies(g) { | ||
@@ -222,2 +221,3 @@ g.nodes().forEach(v => { | ||
} | ||
function translateGraph(g) { | ||
@@ -231,2 +231,3 @@ let minX = Number.POSITIVE_INFINITY; | ||
let marginY = graphLabel.marginy || 0; | ||
function getExtremes(attrs) { | ||
@@ -242,2 +243,3 @@ let x = attrs.x; | ||
} | ||
g.nodes().forEach(v => getExtremes(g.node(v))); | ||
@@ -250,4 +252,6 @@ g.edges().forEach(e => { | ||
}); | ||
minX -= marginX; | ||
minY -= marginY; | ||
g.nodes().forEach(v => { | ||
@@ -258,2 +262,3 @@ let node = g.node(v); | ||
}); | ||
g.edges().forEach(e => { | ||
@@ -265,12 +270,10 @@ let edge = g.edge(e); | ||
}); | ||
if (edge.hasOwnProperty("x")) { | ||
edge.x -= minX; | ||
} | ||
if (edge.hasOwnProperty("y")) { | ||
edge.y -= minY; | ||
} | ||
if (edge.hasOwnProperty("x")) { edge.x -= minX; } | ||
if (edge.hasOwnProperty("y")) { edge.y -= minY; } | ||
}); | ||
graphLabel.width = maxX - minX + marginX; | ||
graphLabel.height = maxY - minY + marginY; | ||
} | ||
function assignNodeIntersects(g) { | ||
@@ -294,2 +297,3 @@ g.edges().forEach(e => { | ||
} | ||
function fixupEdgeLabelCoords(g) { | ||
@@ -303,8 +307,4 @@ g.edges().forEach(e => { | ||
switch (edge.labelpos) { | ||
case "l": | ||
edge.x -= edge.width / 2 + edge.labeloffset; | ||
break; | ||
case "r": | ||
edge.x += edge.width / 2 + edge.labeloffset; | ||
break; | ||
case "l": edge.x -= edge.width / 2 + edge.labeloffset; break; | ||
case "r": edge.x += edge.width / 2 + edge.labeloffset; break; | ||
} | ||
@@ -314,2 +314,3 @@ } | ||
} | ||
function reversePointsForReversedEdges(g) { | ||
@@ -323,2 +324,3 @@ g.edges().forEach(e => { | ||
} | ||
function removeBorderNodes(g) { | ||
@@ -332,2 +334,3 @@ g.nodes().forEach(v => { | ||
let r = g.node(node.borderRight[node.borderRight.length - 1]); | ||
node.width = Math.abs(r.x - l.x); | ||
@@ -339,2 +342,3 @@ node.height = Math.abs(b.y - t.y); | ||
}); | ||
g.nodes().forEach(v => { | ||
@@ -346,2 +350,3 @@ if (g.node(v).dummy === "border") { | ||
} | ||
function removeSelfEdges(g) { | ||
@@ -354,6 +359,3 @@ g.edges().forEach(e => { | ||
} | ||
node.selfEdges.push({ | ||
e: e, | ||
label: g.edge(e) | ||
}); | ||
node.selfEdges.push({ e: e, label: g.edge(e) }); | ||
g.removeEdge(e); | ||
@@ -363,2 +365,3 @@ } | ||
} | ||
function insertSelfEdges(g) { | ||
@@ -376,3 +379,3 @@ var layers = util.buildLayerMatrix(g); | ||
rank: node.rank, | ||
order: i + ++orderShift, | ||
order: i + (++orderShift), | ||
e: selfEdge.e, | ||
@@ -386,2 +389,3 @@ label: selfEdge.label | ||
} | ||
function positionSelfEdges(g) { | ||
@@ -398,18 +402,9 @@ g.nodes().forEach(v => { | ||
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: y | ||
}, { | ||
x: x + 5 * dx / 6, | ||
y: y + dy | ||
}, { | ||
x: x + 2 * dx / 3, | ||
y: y + dy | ||
}]; | ||
node.label.points = [ | ||
{ x: x + 2 * dx / 3, y: y - dy }, | ||
{ x: x + 5 * dx / 6, y: y - dy }, | ||
{ x: x + dx , y: y }, | ||
{ x: x + 5 * dx / 6, y: y + dy }, | ||
{ x: x + 2 * dx / 3, y: y + dy } | ||
]; | ||
node.label.x = node.x; | ||
@@ -420,5 +415,7 @@ node.label.y = node.y; | ||
} | ||
function selectNumberAttrs(obj, attrs) { | ||
return util.mapValues(util.pick(obj, attrs), Number); | ||
} | ||
function canonicalize(attrs) { | ||
@@ -431,2 +428,3 @@ var newAttrs = {}; | ||
} | ||
newAttrs[k] = v; | ||
@@ -437,2 +435,1 @@ }); | ||
} | ||
module.exports = exports.default; |
@@ -1,11 +0,8 @@ | ||
"use strict"; | ||
let util = require("./util"); | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.cleanup = cleanup; | ||
exports.run = run; | ||
var util = _interopRequireWildcard(require("./util.js")); | ||
function _getRequireWildcardCache(e) { if ("function" != typeof WeakMap) return null; var r = new WeakMap(), t = new WeakMap(); return (_getRequireWildcardCache = function (e) { return e ? t : r; })(e); } | ||
function _interopRequireWildcard(e, r) { if (!r && e && e.__esModule) return e; if (null === e || "object" != typeof e && "function" != typeof e) return { default: e }; var t = _getRequireWildcardCache(r); if (t && t.has(e)) return t.get(e); var n = { __proto__: null }, a = Object.defineProperty && Object.getOwnPropertyDescriptor; for (var u in e) if ("default" !== u && Object.prototype.hasOwnProperty.call(e, u)) { var i = a ? Object.getOwnPropertyDescriptor(e, u) : null; i && (i.get || i.set) ? Object.defineProperty(n, u, i) : n[u] = e[u]; } return n.default = e, t && t.set(e, n), n; } | ||
module.exports = { | ||
run, | ||
cleanup, | ||
}; | ||
/* | ||
@@ -39,2 +36,3 @@ * A nesting graph creates dummy nodes for the tops and bottoms of subgraphs, | ||
let nodeSep = 2 * height + 1; | ||
g.graph().nestingRoot = root; | ||
@@ -55,2 +53,3 @@ | ||
} | ||
function dfs(g, root, nodeSep, weight, height, depths, v) { | ||
@@ -60,12 +59,11 @@ let children = g.children(v); | ||
if (v !== root) { | ||
g.setEdge(root, v, { | ||
weight: 0, | ||
minlen: nodeSep | ||
}); | ||
g.setEdge(root, v, { weight: 0, minlen: nodeSep }); | ||
} | ||
return; | ||
} | ||
let top = util.addBorderNode(g, "_bt"); | ||
let bottom = util.addBorderNode(g, "_bb"); | ||
let label = g.node(v); | ||
g.setParent(top, v); | ||
@@ -75,4 +73,6 @@ label.borderTop = top; | ||
label.borderBottom = bottom; | ||
children.forEach(child => { | ||
dfs(g, root, nodeSep, weight, height, depths, child); | ||
let childNode = g.node(child); | ||
@@ -83,2 +83,3 @@ let childTop = childNode.borderTop ? childNode.borderTop : child; | ||
let minlen = childTop !== childBottom ? 1 : height - depths[v] + 1; | ||
g.setEdge(top, childTop, { | ||
@@ -89,2 +90,3 @@ weight: thisWeight, | ||
}); | ||
g.setEdge(childBottom, bottom, { | ||
@@ -96,9 +98,8 @@ weight: thisWeight, | ||
}); | ||
if (!g.parent(v)) { | ||
g.setEdge(root, top, { | ||
weight: 0, | ||
minlen: height + depths[v] | ||
}); | ||
g.setEdge(root, top, { weight: 0, minlen: height + depths[v] }); | ||
} | ||
} | ||
function treeDepths(g) { | ||
@@ -116,5 +117,7 @@ var depths = {}; | ||
} | ||
function sumWeights(g) { | ||
return g.edges().reduce((acc, e) => acc + g.edge(e).weight, 0); | ||
} | ||
function cleanup(g) { | ||
@@ -121,0 +124,0 @@ var graphLabel = g.graph(); |
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.run = run; | ||
exports.undo = undo; | ||
var util = _interopRequireWildcard(require("./util.js")); | ||
function _getRequireWildcardCache(e) { if ("function" != typeof WeakMap) return null; var r = new WeakMap(), t = new WeakMap(); return (_getRequireWildcardCache = function (e) { return e ? t : r; })(e); } | ||
function _interopRequireWildcard(e, r) { if (!r && e && e.__esModule) return e; if (null === e || "object" != typeof e && "function" != typeof e) return { default: e }; var t = _getRequireWildcardCache(r); if (t && t.has(e)) return t.get(e); var n = { __proto__: null }, a = Object.defineProperty && Object.getOwnPropertyDescriptor; for (var u in e) if ("default" !== u && Object.prototype.hasOwnProperty.call(e, u)) { var i = a ? Object.getOwnPropertyDescriptor(e, u) : null; i && (i.get || i.set) ? Object.defineProperty(n, u, i) : n[u] = e[u]; } return n.default = e, t && t.set(e, n), n; } | ||
let util = require("./util"); | ||
module.exports = { | ||
run: run, | ||
undo: undo | ||
}; | ||
/* | ||
@@ -31,2 +30,3 @@ * Breaks any long edges in the graph into short segments that span 1 layer | ||
} | ||
function normalizeEdge(g, e) { | ||
@@ -40,4 +40,7 @@ let v = e.v; | ||
let labelRank = edgeLabel.labelRank; | ||
if (wRank === vRank + 1) return; | ||
g.removeEdge(e); | ||
let dummy, attrs, i; | ||
@@ -47,6 +50,4 @@ for (i = 0, ++vRank; vRank < wRank; ++i, ++vRank) { | ||
attrs = { | ||
width: 0, | ||
height: 0, | ||
edgeLabel: edgeLabel, | ||
edgeObj: e, | ||
width: 0, height: 0, | ||
edgeLabel: edgeLabel, edgeObj: e, | ||
rank: vRank | ||
@@ -61,5 +62,3 @@ }; | ||
} | ||
g.setEdge(v, dummy, { | ||
weight: edgeLabel.weight | ||
}, name); | ||
g.setEdge(v, dummy, { weight: edgeLabel.weight }, name); | ||
if (i === 0) { | ||
@@ -70,6 +69,6 @@ g.graph().dummyChains.push(dummy); | ||
} | ||
g.setEdge(v, w, { | ||
weight: edgeLabel.weight | ||
}, name); | ||
g.setEdge(v, w, { weight: edgeLabel.weight }, name); | ||
} | ||
function undo(g) { | ||
@@ -84,6 +83,3 @@ g.graph().dummyChains.forEach(v => { | ||
g.removeNode(v); | ||
origLabel.points.push({ | ||
x: node.x, | ||
y: node.y | ||
}); | ||
origLabel.points.push({ x: node.x, y: node.y }); | ||
if (node.dummy === "edge-label") { | ||
@@ -90,0 +86,0 @@ origLabel.x = node.x; |
@@ -1,10 +0,7 @@ | ||
"use strict"; | ||
module.exports = addSubgraphConstraints; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = addSubgraphConstraints; | ||
function addSubgraphConstraints(g, cg, vs) { | ||
let prev = {}, | ||
rootPrev; | ||
vs.forEach(v => { | ||
@@ -55,2 +52,1 @@ let child = g.parent(v), | ||
} | ||
module.exports = exports.default; |
@@ -1,7 +0,3 @@ | ||
"use strict"; | ||
module.exports = barycenter; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = barycenter; | ||
function barycenter(g, movable = []) { | ||
@@ -11,5 +7,3 @@ return movable.map(v => { | ||
if (!inV.length) { | ||
return { | ||
v: v | ||
}; | ||
return { v: v }; | ||
} else { | ||
@@ -20,9 +14,7 @@ let result = inV.reduce((acc, e) => { | ||
return { | ||
sum: acc.sum + edge.weight * nodeU.order, | ||
sum: acc.sum + (edge.weight * nodeU.order), | ||
weight: acc.weight + edge.weight | ||
}; | ||
}, { | ||
sum: 0, | ||
weight: 0 | ||
}); | ||
}, { sum: 0, weight: 0 }); | ||
return { | ||
@@ -36,2 +28,2 @@ v: v, | ||
} | ||
module.exports = exports.default; | ||
@@ -1,11 +0,6 @@ | ||
"use strict"; | ||
let Graph = require("@dagrejs/graphlib").Graph; | ||
let util = require("../util"); | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = buildLayerGraph; | ||
var _graphlib = require("@dagrejs/graphlib"); | ||
var util = _interopRequireWildcard(require("../util.js")); | ||
function _getRequireWildcardCache(e) { if ("function" != typeof WeakMap) return null; var r = new WeakMap(), t = new WeakMap(); return (_getRequireWildcardCache = function (e) { return e ? t : r; })(e); } | ||
function _interopRequireWildcard(e, r) { if (!r && e && e.__esModule) return e; if (null === e || "object" != typeof e && "function" != typeof e) return { default: e }; var t = _getRequireWildcardCache(r); if (t && t.has(e)) return t.get(e); var n = { __proto__: null }, a = Object.defineProperty && Object.getOwnPropertyDescriptor; for (var u in e) if ("default" !== u && Object.prototype.hasOwnProperty.call(e, u)) { var i = a ? Object.getOwnPropertyDescriptor(e, u) : null; i && (i.get || i.set) ? Object.defineProperty(n, u, i) : n[u] = e[u]; } return n.default = e, t && t.set(e, n), n; } | ||
module.exports = buildLayerGraph; | ||
/* | ||
@@ -43,10 +38,9 @@ * Constructs a graph that can be used to sort a layer of nodes. The graph will | ||
let root = createRootNode(g), | ||
result = new _graphlib.Graph({ | ||
compound: true | ||
}).setGraph({ | ||
root: root | ||
}).setDefaultNodeLabel(v => g.node(v)); | ||
result = new Graph({ compound: true }).setGraph({ root: root }) | ||
.setDefaultNodeLabel(v => g.node(v)); | ||
g.nodes().forEach(v => { | ||
let node = g.node(v), | ||
parent = g.parent(v); | ||
if (node.rank === rank || node.minRank <= rank && rank <= node.maxRank) { | ||
@@ -61,6 +55,5 @@ result.setNode(v); | ||
weight = edge !== undefined ? edge.weight : 0; | ||
result.setEdge(u, v, { | ||
weight: g.edge(e).weight + weight | ||
}); | ||
result.setEdge(u, v, { weight: g.edge(e).weight + weight }); | ||
}); | ||
if (node.hasOwnProperty("minRank")) { | ||
@@ -74,9 +67,10 @@ result.setNode(v, { | ||
}); | ||
return result; | ||
} | ||
function createRootNode(g) { | ||
var v; | ||
while (g.hasNode(v = util.uniqueId("_root"))); | ||
while (g.hasNode((v = util.uniqueId("_root")))); | ||
return v; | ||
} | ||
module.exports = exports.default; |
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = crossCount; | ||
var _util = require("../util.js"); | ||
let zipObject = require("../util").zipObject; | ||
module.exports = crossCount; | ||
/* | ||
@@ -27,6 +26,7 @@ * A function that takes a layering (an array of layers, each with an array of | ||
for (let i = 1; i < layering.length; ++i) { | ||
cc += twoLayerCrossCount(g, layering[i - 1], layering[i]); | ||
cc += twoLayerCrossCount(g, layering[i-1], layering[i]); | ||
} | ||
return cc; | ||
} | ||
function twoLayerCrossCount(g, northLayer, southLayer) { | ||
@@ -36,9 +36,6 @@ // Sort all of the edges between the north and south layers by their position | ||
// their head in the south layer. | ||
let southPos = (0, _util.zipObject)(southLayer, southLayer.map((v, i) => i)); | ||
let southPos = zipObject(southLayer, southLayer.map((v, i) => i)); | ||
let southEntries = northLayer.flatMap(v => { | ||
return g.outEdges(v).map(e => { | ||
return { | ||
pos: southPos[e.w], | ||
weight: g.edge(e).weight | ||
}; | ||
return { pos: southPos[e.w], weight: g.edge(e).weight }; | ||
}).sort((a, b) => a.pos - b.pos); | ||
@@ -64,3 +61,3 @@ }); | ||
} | ||
index = index - 1 >> 1; | ||
index = (index - 1) >> 1; | ||
tree[index] += entry.weight; | ||
@@ -70,4 +67,4 @@ } | ||
}); | ||
return cc; | ||
} | ||
module.exports = exports.default; |
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = order; | ||
var _initOrder = _interopRequireDefault(require("./init-order.js")); | ||
var _crossCount = _interopRequireDefault(require("./cross-count.js")); | ||
var _sortSubgraph = _interopRequireDefault(require("./sort-subgraph.js")); | ||
var _buildLayerGraph = _interopRequireDefault(require("./build-layer-graph.js")); | ||
var _addSubgraphConstraints = _interopRequireDefault(require("./add-subgraph-constraints.js")); | ||
var _graphlib = require("@dagrejs/graphlib"); | ||
var util = _interopRequireWildcard(require("../util.js")); | ||
function _getRequireWildcardCache(e) { if ("function" != typeof WeakMap) return null; var r = new WeakMap(), t = new WeakMap(); return (_getRequireWildcardCache = function (e) { return e ? t : r; })(e); } | ||
function _interopRequireWildcard(e, r) { if (!r && e && e.__esModule) return e; if (null === e || "object" != typeof e && "function" != typeof e) return { default: e }; var t = _getRequireWildcardCache(r); if (t && t.has(e)) return t.get(e); var n = { __proto__: null }, a = Object.defineProperty && Object.getOwnPropertyDescriptor; for (var u in e) if ("default" !== u && Object.prototype.hasOwnProperty.call(e, u)) { var i = a ? Object.getOwnPropertyDescriptor(e, u) : null; i && (i.get || i.set) ? Object.defineProperty(n, u, i) : n[u] = e[u]; } return n.default = e, t && t.set(e, n), n; } | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
let initOrder = require("./init-order"); | ||
let crossCount = require("./cross-count"); | ||
let sortSubgraph = require("./sort-subgraph"); | ||
let buildLayerGraph = require("./build-layer-graph"); | ||
let addSubgraphConstraints = require("./add-subgraph-constraints"); | ||
let Graph = require("@dagrejs/graphlib").Graph; | ||
let util = require("../util"); | ||
module.exports = order; | ||
/* | ||
@@ -42,3 +38,3 @@ * Applies heuristics to minimize edge crossings in the graph and sets the best | ||
let layering = (0, _initOrder.default)(g); | ||
let layering = initOrder(g); | ||
assignOrder(g, layering); | ||
@@ -55,4 +51,5 @@ | ||
sweepLayerGraphs(i % 2 ? downLayerGraphs : upLayerGraphs, i % 4 >= 2); | ||
layering = util.buildLayerMatrix(g); | ||
let cc = (0, _crossCount.default)(g, layering); | ||
let cc = crossCount(g, layering); | ||
if (cc < bestCC) { | ||
@@ -64,21 +61,24 @@ lastBest = 0; | ||
} | ||
assignOrder(g, best); | ||
} | ||
function buildLayerGraphs(g, ranks, relationship) { | ||
return ranks.map(function (rank) { | ||
return (0, _buildLayerGraph.default)(g, rank, relationship); | ||
return ranks.map(function(rank) { | ||
return buildLayerGraph(g, rank, relationship); | ||
}); | ||
} | ||
function sweepLayerGraphs(layerGraphs, biasRight) { | ||
let cg = new _graphlib.Graph(); | ||
layerGraphs.forEach(function (lg) { | ||
let cg = new Graph(); | ||
layerGraphs.forEach(function(lg) { | ||
let root = lg.graph().root; | ||
let sorted = (0, _sortSubgraph.default)(lg, root, cg, biasRight); | ||
let sorted = sortSubgraph(lg, root, cg, biasRight); | ||
sorted.vs.forEach((v, i) => lg.node(v).order = i); | ||
(0, _addSubgraphConstraints.default)(lg, cg, sorted.vs); | ||
addSubgraphConstraints(lg, cg, sorted.vs); | ||
}); | ||
} | ||
function assignOrder(g, layering) { | ||
Object.values(layering).forEach(layer => layer.forEach((v, i) => g.node(v).order = i)); | ||
} | ||
module.exports = exports.default; |
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = initOrder; | ||
var util = _interopRequireWildcard(require("../util.js")); | ||
function _getRequireWildcardCache(e) { if ("function" != typeof WeakMap) return null; var r = new WeakMap(), t = new WeakMap(); return (_getRequireWildcardCache = function (e) { return e ? t : r; })(e); } | ||
function _interopRequireWildcard(e, r) { if (!r && e && e.__esModule) return e; if (null === e || "object" != typeof e && "function" != typeof e) return { default: e }; var t = _getRequireWildcardCache(r); if (t && t.has(e)) return t.get(e); var n = { __proto__: null }, a = Object.defineProperty && Object.getOwnPropertyDescriptor; for (var u in e) if ("default" !== u && Object.prototype.hasOwnProperty.call(e, u)) { var i = a ? Object.getOwnPropertyDescriptor(e, u) : null; i && (i.get || i.set) ? Object.defineProperty(n, u, i) : n[u] = e[u]; } return n.default = e, t && t.set(e, n), n; } | ||
let util = require("../util"); | ||
module.exports = initOrder; | ||
/* | ||
@@ -26,2 +23,3 @@ * Assigns an initial order value for each node by performing a DFS search | ||
let layers = util.range(maxRank + 1).map(() => []); | ||
function dfs(v) { | ||
@@ -34,6 +32,7 @@ if (visited[v]) return; | ||
} | ||
let orderedVs = simpleNodes.sort((a, b) => g.node(a).rank - g.node(b).rank); | ||
orderedVs.forEach(dfs); | ||
return layers; | ||
} | ||
module.exports = exports.default; |
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = resolveConflicts; | ||
var util = _interopRequireWildcard(require("../util.js")); | ||
function _getRequireWildcardCache(e) { if ("function" != typeof WeakMap) return null; var r = new WeakMap(), t = new WeakMap(); return (_getRequireWildcardCache = function (e) { return e ? t : r; })(e); } | ||
function _interopRequireWildcard(e, r) { if (!r && e && e.__esModule) return e; if (null === e || "object" != typeof e && "function" != typeof e) return { default: e }; var t = _getRequireWildcardCache(r); if (t && t.has(e)) return t.get(e); var n = { __proto__: null }, a = Object.defineProperty && Object.getOwnPropertyDescriptor; for (var u in e) if ("default" !== u && Object.prototype.hasOwnProperty.call(e, u)) { var i = a ? Object.getOwnPropertyDescriptor(e, u) : null; i && (i.get || i.set) ? Object.defineProperty(n, u, i) : n[u] = e[u]; } return n.default = e, t && t.set(e, n), n; } | ||
let util = require("../util"); | ||
module.exports = resolveConflicts; | ||
/* | ||
@@ -50,2 +47,3 @@ * Given a list of entries of the form {v, barycenter, weight} and a | ||
}); | ||
cg.edges().forEach(e => { | ||
@@ -59,7 +57,11 @@ let entryV = mappedEntries[e.v]; | ||
}); | ||
let sourceSet = Object.values(mappedEntries).filter(entry => !entry.indegree); | ||
return doResolveConflicts(sourceSet); | ||
} | ||
function doResolveConflicts(sourceSet) { | ||
let entries = []; | ||
function handleIn(vEntry) { | ||
@@ -70,3 +72,5 @@ return uEntry => { | ||
} | ||
if (uEntry.barycenter === undefined || vEntry.barycenter === undefined || uEntry.barycenter >= vEntry.barycenter) { | ||
if (uEntry.barycenter === undefined || | ||
vEntry.barycenter === undefined || | ||
uEntry.barycenter >= vEntry.barycenter) { | ||
mergeEntries(vEntry, uEntry); | ||
@@ -76,2 +80,3 @@ } | ||
} | ||
function handleOut(vEntry) { | ||
@@ -85,2 +90,3 @@ return wEntry => { | ||
} | ||
while (sourceSet.length) { | ||
@@ -92,2 +98,3 @@ let entry = sourceSet.pop(); | ||
} | ||
return entries.filter(entry => !entry.merged).map(entry => { | ||
@@ -97,5 +104,7 @@ return util.pick(entry, ["vs", "i", "barycenter", "weight"]); | ||
} | ||
function mergeEntries(target, source) { | ||
let sum = 0; | ||
let weight = 0; | ||
if (target.weight) { | ||
@@ -105,2 +114,3 @@ sum += target.barycenter * target.weight; | ||
} | ||
if (source.weight) { | ||
@@ -110,2 +120,3 @@ sum += source.barycenter * source.weight; | ||
} | ||
target.vs = source.vs.concat(target.vs); | ||
@@ -117,2 +128,1 @@ target.barycenter = sum / weight; | ||
} | ||
module.exports = exports.default; |
@@ -1,11 +0,7 @@ | ||
"use strict"; | ||
let barycenter = require("./barycenter"); | ||
let resolveConflicts = require("./resolve-conflicts"); | ||
let sort = require("./sort"); | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = sortSubgraph; | ||
var _barycenter = _interopRequireDefault(require("./barycenter.js")); | ||
var _resolveConflicts = _interopRequireDefault(require("./resolve-conflicts.js")); | ||
var _sort = _interopRequireDefault(require("./sort.js")); | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
module.exports = sortSubgraph; | ||
function sortSubgraph(g, v, cg, biasRight) { | ||
@@ -15,8 +11,10 @@ let movable = g.children(v); | ||
let bl = node ? node.borderLeft : undefined; | ||
let br = node ? node.borderRight : undefined; | ||
let br = node ? node.borderRight: undefined; | ||
let subgraphs = {}; | ||
if (bl) { | ||
movable = movable.filter(w => w !== bl && w !== br); | ||
} | ||
let barycenters = (0, _barycenter.default)(g, movable); | ||
let barycenters = barycenter(g, movable); | ||
barycenters.forEach(entry => { | ||
@@ -31,5 +29,8 @@ if (g.children(entry.v).length) { | ||
}); | ||
let entries = (0, _resolveConflicts.default)(barycenters, cg); | ||
let entries = resolveConflicts(barycenters, cg); | ||
expandSubgraphs(entries, subgraphs); | ||
let result = (0, _sort.default)(entries, biasRight); | ||
let result = sort(entries, biasRight); | ||
if (bl) { | ||
@@ -44,8 +45,11 @@ result.vs = [bl, result.vs, br].flat(true); | ||
} | ||
result.barycenter = (result.barycenter * result.weight + blPred.order + brPred.order) / (result.weight + 2); | ||
result.barycenter = (result.barycenter * result.weight + | ||
blPred.order + brPred.order) / (result.weight + 2); | ||
result.weight += 2; | ||
} | ||
} | ||
return result; | ||
} | ||
function expandSubgraphs(entries, subgraphs) { | ||
@@ -61,5 +65,8 @@ entries.forEach(entry => { | ||
} | ||
function mergeBarycenters(target, other) { | ||
if (target.barycenter !== undefined) { | ||
target.barycenter = (target.barycenter * target.weight + other.barycenter * other.weight) / (target.weight + other.weight); | ||
target.barycenter = (target.barycenter * target.weight + | ||
other.barycenter * other.weight) / | ||
(target.weight + other.weight); | ||
target.weight += other.weight; | ||
@@ -71,2 +78,1 @@ } else { | ||
} | ||
module.exports = exports.default; |
@@ -1,10 +0,5 @@ | ||
"use strict"; | ||
let util = require("../util"); | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = sort; | ||
var util = _interopRequireWildcard(require("../util.js")); | ||
function _getRequireWildcardCache(e) { if ("function" != typeof WeakMap) return null; var r = new WeakMap(), t = new WeakMap(); return (_getRequireWildcardCache = function (e) { return e ? t : r; })(e); } | ||
function _interopRequireWildcard(e, r) { if (!r && e && e.__esModule) return e; if (null === e || "object" != typeof e && "function" != typeof e) return { default: e }; var t = _getRequireWildcardCache(r); if (t && t.has(e)) return t.get(e); var n = { __proto__: null }, a = Object.defineProperty && Object.getOwnPropertyDescriptor; for (var u in e) if ("default" !== u && Object.prototype.hasOwnProperty.call(e, u)) { var i = a ? Object.getOwnPropertyDescriptor(e, u) : null; i && (i.get || i.set) ? Object.defineProperty(n, u, i) : n[u] = e[u]; } return n.default = e, t && t.set(e, n), n; } | ||
module.exports = sort; | ||
function sort(entries, biasRight) { | ||
@@ -20,4 +15,7 @@ let parts = util.partition(entries, entry => { | ||
vsIndex = 0; | ||
sortable.sort(compareWithBias(!!biasRight)); | ||
vsIndex = consumeUnsortable(vs, unsortable, vsIndex); | ||
sortable.forEach(entry => { | ||
@@ -30,5 +28,4 @@ vsIndex += entry.vs.length; | ||
}); | ||
let result = { | ||
vs: vs.flat(true) | ||
}; | ||
let result = { vs: vs.flat(true) }; | ||
if (weight) { | ||
@@ -40,2 +37,3 @@ result.barycenter = sum / weight; | ||
} | ||
function consumeUnsortable(vs, unsortable, index) { | ||
@@ -50,2 +48,3 @@ let last; | ||
} | ||
function compareWithBias(bias) { | ||
@@ -58,5 +57,5 @@ return (entryV, entryW) => { | ||
} | ||
return !bias ? entryV.i - entryW.i : entryW.i - entryV.i; | ||
}; | ||
} | ||
module.exports = exports.default; |
@@ -1,9 +0,6 @@ | ||
"use strict"; | ||
module.exports = parentDummyChains; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = parentDummyChains; | ||
function parentDummyChains(g) { | ||
let postorderNums = postorder(g); | ||
g.graph().dummyChains.forEach(v => { | ||
@@ -18,8 +15,12 @@ let node = g.node(v); | ||
let ascending = true; | ||
while (v !== edgeObj.w) { | ||
node = g.node(v); | ||
if (ascending) { | ||
while ((pathV = path[pathIdx]) !== lca && g.node(pathV).maxRank < node.rank) { | ||
while ((pathV = path[pathIdx]) !== lca && | ||
g.node(pathV).maxRank < node.rank) { | ||
pathIdx++; | ||
} | ||
if (pathV === lca) { | ||
@@ -29,4 +30,6 @@ ascending = false; | ||
} | ||
if (!ascending) { | ||
while (pathIdx < path.length - 1 && g.node(pathV = path[pathIdx + 1]).minRank <= node.rank) { | ||
while (pathIdx < path.length - 1 && | ||
g.node(pathV = path[pathIdx + 1]).minRank <= node.rank) { | ||
pathIdx++; | ||
@@ -36,2 +39,3 @@ } | ||
} | ||
g.setParent(v, pathV); | ||
@@ -58,3 +62,4 @@ v = g.successors(v)[0]; | ||
vPath.push(parent); | ||
} while (parent && (postorderNums[parent].low > low || lim > postorderNums[parent].lim)); | ||
} while (parent && | ||
(postorderNums[parent].low > low || lim > postorderNums[parent].lim)); | ||
lca = parent; | ||
@@ -67,21 +72,18 @@ | ||
} | ||
return { | ||
path: vPath.concat(wPath.reverse()), | ||
lca: lca | ||
}; | ||
return { path: vPath.concat(wPath.reverse()), lca: lca }; | ||
} | ||
function postorder(g) { | ||
let result = {}; | ||
let lim = 0; | ||
function dfs(v) { | ||
let low = lim; | ||
g.children(v).forEach(dfs); | ||
result[v] = { | ||
low: low, | ||
lim: lim++ | ||
}; | ||
result[v] = { low: low, lim: lim++ }; | ||
} | ||
g.children().forEach(dfs); | ||
return result; | ||
} | ||
module.exports = exports.default; |
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.addConflict = addConflict; | ||
exports.alignCoordinates = alignCoordinates; | ||
exports.balance = balance; | ||
exports.findSmallestWidthAlignment = findSmallestWidthAlignment; | ||
exports.findType1Conflicts = findType1Conflicts; | ||
exports.findType2Conflicts = findType2Conflicts; | ||
exports.hasConflict = hasConflict; | ||
exports.horizontalCompaction = horizontalCompaction; | ||
exports.positionX = positionX; | ||
exports.verticalAlignment = verticalAlignment; | ||
var _graphlib = require("@dagrejs/graphlib"); | ||
var util = _interopRequireWildcard(require("../util.js")); | ||
function _getRequireWildcardCache(e) { if ("function" != typeof WeakMap) return null; var r = new WeakMap(), t = new WeakMap(); return (_getRequireWildcardCache = function (e) { return e ? t : r; })(e); } | ||
function _interopRequireWildcard(e, r) { if (!r && e && e.__esModule) return e; if (null === e || "object" != typeof e && "function" != typeof e) return { default: e }; var t = _getRequireWildcardCache(r); if (t && t.has(e)) return t.get(e); var n = { __proto__: null }, a = Object.defineProperty && Object.getOwnPropertyDescriptor; for (var u in e) if ("default" !== u && Object.prototype.hasOwnProperty.call(e, u)) { var i = a ? Object.getOwnPropertyDescriptor(e, u) : null; i && (i.get || i.set) ? Object.defineProperty(n, u, i) : n[u] = e[u]; } return n.default = e, t && t.set(e, n), n; } | ||
let Graph = require("@dagrejs/graphlib").Graph; | ||
let util = require("../util"); | ||
/* | ||
@@ -25,2 +11,15 @@ * This module provides coordinate assignment based on Brandes and Köpf, "Fast | ||
module.exports = { | ||
positionX: positionX, | ||
findType1Conflicts: findType1Conflicts, | ||
findType2Conflicts: findType2Conflicts, | ||
addConflict: addConflict, | ||
hasConflict: hasConflict, | ||
verticalAlignment: verticalAlignment, | ||
horizontalCompaction: horizontalCompaction, | ||
alignCoordinates: alignCoordinates, | ||
findSmallestWidthAlignment: findSmallestWidthAlignment, | ||
balance: balance | ||
}; | ||
/* | ||
@@ -45,2 +44,3 @@ * Marks all edges in the graph with a type-1 conflict with the "type1Conflict" | ||
let conflicts = {}; | ||
function visitLayer(prevLayer, layer) { | ||
@@ -56,11 +56,14 @@ let | ||
lastNode = layer[layer.length - 1]; | ||
layer.forEach((v, i) => { | ||
let w = findOtherInnerSegmentNode(g, v), | ||
k1 = w ? g.node(w).order : prevLayerLength; | ||
if (w || v === lastNode) { | ||
layer.slice(scanPos, i + 1).forEach(scanNode => { | ||
layer.slice(scanPos, i+1).forEach(scanNode => { | ||
g.predecessors(scanNode).forEach(u => { | ||
let uLabel = g.node(u), | ||
uPos = uLabel.order; | ||
if ((uPos < k0 || k1 < uPos) && !(uLabel.dummy && g.node(scanNode).dummy)) { | ||
if ((uPos < k0 || k1 < uPos) && | ||
!(uLabel.dummy && g.node(scanNode).dummy)) { | ||
addConflict(conflicts, u, scanNode); | ||
@@ -74,9 +77,14 @@ } | ||
}); | ||
return layer; | ||
} | ||
layering.length && layering.reduce(visitLayer); | ||
return conflicts; | ||
} | ||
function findType2Conflicts(g, layering) { | ||
let conflicts = {}; | ||
function scan(south, southPos, southEnd, prevNorthBorder, nextNorthBorder) { | ||
@@ -89,3 +97,4 @@ let v; | ||
let uNode = g.node(u); | ||
if (uNode.dummy && (uNode.order < prevNorthBorder || uNode.order > nextNorthBorder)) { | ||
if (uNode.dummy && | ||
(uNode.order < prevNorthBorder || uNode.order > nextNorthBorder)) { | ||
addConflict(conflicts, u, v); | ||
@@ -97,2 +106,4 @@ } | ||
} | ||
function visitLayer(north, south) { | ||
@@ -102,2 +113,3 @@ let prevNorthPos = -1, | ||
southPos = 0; | ||
south.forEach((v, southLookahead) => { | ||
@@ -115,7 +127,11 @@ if (g.node(v).dummy === "border") { | ||
}); | ||
return south; | ||
} | ||
layering.length && layering.reduce(visitLayer); | ||
return conflicts; | ||
} | ||
function findOtherInnerSegmentNode(g, v) { | ||
@@ -126,2 +142,3 @@ if (g.node(v).dummy) { | ||
} | ||
function addConflict(conflicts, v, w) { | ||
@@ -133,2 +150,3 @@ if (v > w) { | ||
} | ||
let conflictsV = conflicts[v]; | ||
@@ -140,2 +158,3 @@ if (!conflictsV) { | ||
} | ||
function hasConflict(conflicts, v, w) { | ||
@@ -173,2 +192,3 @@ if (v > w) { | ||
}); | ||
layering.forEach(layer => { | ||
@@ -183,3 +203,5 @@ let prevIdx = -1; | ||
let w = ws[i]; | ||
if (align[v] === v && prevIdx < pos[w] && !hasConflict(conflicts, v, w)) { | ||
if (align[v] === v && | ||
prevIdx < pos[w] && | ||
!hasConflict(conflicts, v, w)) { | ||
align[w] = v; | ||
@@ -193,7 +215,6 @@ align[v] = root[v] = root[w]; | ||
}); | ||
return { | ||
root: root, | ||
align: align | ||
}; | ||
return { root: root, align: align }; | ||
} | ||
function horizontalCompaction(g, layering, root, align, reverseSep) { | ||
@@ -208,2 +229,3 @@ // This portion of the algorithm differs from BK due to a number of problems. | ||
borderType = reverseSep ? "borderLeft" : "borderRight"; | ||
function iterate(setXsFunc, nextNodesFunc) { | ||
@@ -221,2 +243,3 @@ let stack = blockG.nodes(); | ||
} | ||
elem = stack.pop(); | ||
@@ -238,2 +261,3 @@ } | ||
}, Number.POSITIVE_INFINITY); | ||
let node = g.node(elem); | ||
@@ -244,2 +268,3 @@ if (min !== Number.POSITIVE_INFINITY && node.borderType !== borderType) { | ||
} | ||
iterate(pass1, blockG.predecessors.bind(blockG)); | ||
@@ -250,8 +275,12 @@ iterate(pass2, blockG.successors.bind(blockG)); | ||
Object.keys(align).forEach(v => xs[v] = xs[root[v]]); | ||
return xs; | ||
} | ||
function buildBlockGraph(g, layering, root, reverseSep) { | ||
let blockGraph = new _graphlib.Graph(), | ||
let blockGraph = new Graph(), | ||
graphLabel = g.graph(), | ||
sepFn = sep(graphLabel.nodesep, graphLabel.edgesep, reverseSep); | ||
layering.forEach(layer => { | ||
@@ -270,2 +299,3 @@ let u; | ||
}); | ||
return blockGraph; | ||
@@ -281,7 +311,10 @@ } | ||
let min = Number.POSITIVE_INFINITY; | ||
Object.entries(xs).forEach(([v, x]) => { | ||
let halfWidth = width(g, v) / 2; | ||
max = Math.max(x + halfWidth, max); | ||
min = Math.min(x - halfWidth, min); | ||
}); | ||
const newMin = max - min; | ||
@@ -306,2 +339,3 @@ if (newMin < currentMinAndXs[0]) { | ||
alignToMax = Math.max(...alignToVals); | ||
["u", "d"].forEach(vert => { | ||
@@ -311,3 +345,5 @@ ["l", "r"].forEach(horiz => { | ||
xs = xss[alignment]; | ||
if (xs === alignTo) return; | ||
let xsVals = Object.values(xs); | ||
@@ -318,2 +354,3 @@ let delta = alignToMin - Math.min(...xsVals); | ||
} | ||
if (delta) { | ||
@@ -325,2 +362,3 @@ xss[alignment] = util.mapValues(xs, x => x + delta); | ||
} | ||
function balance(xss, align) { | ||
@@ -336,5 +374,9 @@ return util.mapValues(xss.ul, (num, v) => { | ||
} | ||
function positionX(g) { | ||
let layering = util.buildLayerMatrix(g); | ||
let conflicts = Object.assign(findType1Conflicts(g, layering), findType2Conflicts(g, layering)); | ||
let conflicts = Object.assign( | ||
findType1Conflicts(g, layering), | ||
findType2Conflicts(g, layering)); | ||
let xss = {}; | ||
@@ -350,5 +392,7 @@ let adjustedLayering; | ||
} | ||
let neighborFn = (vert === "u" ? g.predecessors : g.successors).bind(g); | ||
let align = verticalAlignment(g, adjustedLayering, conflicts, neighborFn); | ||
let xs = horizontalCompaction(g, adjustedLayering, align.root, align.align, horiz === "r"); | ||
let xs = horizontalCompaction(g, adjustedLayering, | ||
align.root, align.align, horiz === "r"); | ||
if (horiz === "r") { | ||
@@ -360,2 +404,4 @@ xs = util.mapValues(xs, x => -x); | ||
}); | ||
let smallestWidth = findSmallestWidthAlignment(g, xss); | ||
@@ -365,2 +411,3 @@ alignCoordinates(xss, smallestWidth); | ||
} | ||
function sep(nodeSep, edgeSep, reverseSep) { | ||
@@ -372,11 +419,8 @@ return (g, v, w) => { | ||
let delta; | ||
sum += vLabel.width / 2; | ||
if (vLabel.hasOwnProperty("labelpos")) { | ||
switch (vLabel.labelpos.toLowerCase()) { | ||
case "l": | ||
delta = -vLabel.width / 2; | ||
break; | ||
case "r": | ||
delta = vLabel.width / 2; | ||
break; | ||
case "l": delta = -vLabel.width / 2; break; | ||
case "r": delta = vLabel.width / 2; break; | ||
} | ||
@@ -388,13 +432,11 @@ } | ||
delta = 0; | ||
sum += (vLabel.dummy ? edgeSep : nodeSep) / 2; | ||
sum += (wLabel.dummy ? edgeSep : nodeSep) / 2; | ||
sum += wLabel.width / 2; | ||
if (wLabel.hasOwnProperty("labelpos")) { | ||
switch (wLabel.labelpos.toLowerCase()) { | ||
case "l": | ||
delta = wLabel.width / 2; | ||
break; | ||
case "r": | ||
delta = -wLabel.width / 2; | ||
break; | ||
case "l": delta = wLabel.width / 2; break; | ||
case "r": delta = -wLabel.width / 2; break; | ||
} | ||
@@ -406,7 +448,9 @@ } | ||
delta = 0; | ||
return sum; | ||
}; | ||
} | ||
function width(g, v) { | ||
return g.node(v).width; | ||
} |
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = position; | ||
var util = _interopRequireWildcard(require("../util.js")); | ||
var _bk = require("./bk.js"); | ||
function _getRequireWildcardCache(e) { if ("function" != typeof WeakMap) return null; var r = new WeakMap(), t = new WeakMap(); return (_getRequireWildcardCache = function (e) { return e ? t : r; })(e); } | ||
function _interopRequireWildcard(e, r) { if (!r && e && e.__esModule) return e; if (null === e || "object" != typeof e && "function" != typeof e) return { default: e }; var t = _getRequireWildcardCache(r); if (t && t.has(e)) return t.get(e); var n = { __proto__: null }, a = Object.defineProperty && Object.getOwnPropertyDescriptor; for (var u in e) if ("default" !== u && Object.prototype.hasOwnProperty.call(e, u)) { var i = a ? Object.getOwnPropertyDescriptor(e, u) : null; i && (i.get || i.set) ? Object.defineProperty(n, u, i) : n[u] = e[u]; } return n.default = e, t && t.set(e, n), n; } | ||
let util = require("../util"); | ||
let positionX = require("./bk").positionX; | ||
module.exports = position; | ||
function position(g) { | ||
g = util.asNonCompoundGraph(g); | ||
positionY(g); | ||
Object.entries((0, _bk.positionX)(g)).forEach(([v, x]) => g.node(v).x = x); | ||
Object.entries(positionX(g)).forEach(([v, x]) => g.node(v).x = x); | ||
} | ||
function positionY(g) { | ||
@@ -33,2 +32,2 @@ let layering = util.buildLayerMatrix(g); | ||
} | ||
module.exports = exports.default; | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = feasibleTree; | ||
var _graphlib = require("@dagrejs/graphlib"); | ||
var _util = require("./util.js"); | ||
var Graph = require("@dagrejs/graphlib").Graph; | ||
var slack = require("./util").slack; | ||
module.exports = feasibleTree; | ||
/* | ||
@@ -35,5 +34,3 @@ * Constructs a spanning tree with tight edges and adjusted the input node's | ||
function feasibleTree(g) { | ||
var t = new _graphlib.Graph({ | ||
directed: false | ||
}); | ||
var t = new Graph({ directed: false }); | ||
@@ -44,8 +41,10 @@ // Choose arbitrary node from which to start our tree | ||
t.setNode(start, {}); | ||
var edge, delta; | ||
while (tightTree(t, g) < size) { | ||
edge = findMinSlackEdge(t, g); | ||
delta = t.hasNode(edge.v) ? (0, _util.slack)(g, edge) : -(0, _util.slack)(g, edge); | ||
delta = t.hasNode(edge.v) ? slack(g, edge) : -slack(g, edge); | ||
shiftRanks(t, g, delta); | ||
} | ||
return t; | ||
@@ -62,4 +61,4 @@ } | ||
var edgeV = e.v, | ||
w = v === edgeV ? e.w : edgeV; | ||
if (!t.hasNode(w) && !(0, _util.slack)(g, e)) { | ||
w = (v === edgeV) ? e.w : edgeV; | ||
if (!t.hasNode(w) && !slack(g, e)) { | ||
t.setNode(w, {}); | ||
@@ -71,2 +70,3 @@ t.setEdge(v, w, {}); | ||
} | ||
t.nodes().forEach(dfs); | ||
@@ -82,16 +82,19 @@ return t.nodeCount(); | ||
const edges = g.edges(); | ||
return edges.reduce((acc, edge) => { | ||
let edgeSlack = Number.POSITIVE_INFINITY; | ||
if (t.hasNode(edge.v) !== t.hasNode(edge.w)) { | ||
edgeSlack = (0, _util.slack)(g, edge); | ||
edgeSlack = slack(g, edge); | ||
} | ||
if (edgeSlack < acc[0]) { | ||
return [edgeSlack, edge]; | ||
} | ||
return acc; | ||
}, [Number.POSITIVE_INFINITY, null])[1]; | ||
} | ||
function shiftRanks(t, g, delta) { | ||
t.nodes().forEach(v => g.node(v).rank += delta); | ||
} | ||
module.exports = exports.default; |
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = rank; | ||
var rankUtil = _interopRequireWildcard(require("./util.js")); | ||
var _feasibleTree = _interopRequireDefault(require("./feasible-tree.js")); | ||
var _networkSimplex = _interopRequireDefault(require("./network-simplex.js")); | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
function _getRequireWildcardCache(e) { if ("function" != typeof WeakMap) return null; var r = new WeakMap(), t = new WeakMap(); return (_getRequireWildcardCache = function (e) { return e ? t : r; })(e); } | ||
function _interopRequireWildcard(e, r) { if (!r && e && e.__esModule) return e; if (null === e || "object" != typeof e && "function" != typeof e) return { default: e }; var t = _getRequireWildcardCache(r); if (t && t.has(e)) return t.get(e); var n = { __proto__: null }, a = Object.defineProperty && Object.getOwnPropertyDescriptor; for (var u in e) if ("default" !== u && Object.prototype.hasOwnProperty.call(e, u)) { var i = a ? Object.getOwnPropertyDescriptor(e, u) : null; i && (i.get || i.set) ? Object.defineProperty(n, u, i) : n[u] = e[u]; } return n.default = e, t && t.set(e, n), n; } | ||
var rankUtil = require("./util"); | ||
var longestPath = rankUtil.longestPath; | ||
var feasibleTree = require("./feasible-tree"); | ||
var networkSimplex = require("./network-simplex"); | ||
module.exports = rank; | ||
/* | ||
@@ -34,14 +30,7 @@ * Assigns a rank to each node in the input graph that respects the "minlen" | ||
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); | ||
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); | ||
} | ||
@@ -52,9 +41,10 @@ } | ||
var longestPathRanker = longestPath; | ||
function tightTreeRanker(g) { | ||
longestPath(g); | ||
(0, _feasibleTree.default)(g); | ||
feasibleTree(g); | ||
} | ||
function networkSimplexRanker(g) { | ||
(0, _networkSimplex.default)(g); | ||
networkSimplex(g); | ||
} | ||
module.exports = exports.default; |
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = networkSimplex; | ||
var _feasibleTree = _interopRequireDefault(require("./feasible-tree.js")); | ||
var _util = require("./util.js"); | ||
var _graphlib = require("@dagrejs/graphlib"); | ||
var _util2 = require("../util.js"); | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
var preorder = _graphlib.alg.preorder; | ||
var postorder = _graphlib.alg.postorder; | ||
var feasibleTree = require("./feasible-tree"); | ||
var slack = require("./util").slack; | ||
var initRank = require("./util").longestPath; | ||
var preorder = require("@dagrejs/graphlib").alg.preorder; | ||
var postorder = require("@dagrejs/graphlib").alg.postorder; | ||
var simplify = require("../util").simplify; | ||
module.exports = networkSimplex; | ||
// Expose some internals for testing purposes | ||
@@ -56,9 +54,10 @@ networkSimplex.initLowLimValues = initLowLimValues; | ||
function networkSimplex(g) { | ||
g = (0, _util2.simplify)(g); | ||
(0, _util.longestPath)(g); | ||
var t = (0, _feasibleTree.default)(g); | ||
g = simplify(g); | ||
initRank(g); | ||
var t = feasibleTree(g); | ||
initLowLimValues(t); | ||
initCutValues(t, g); | ||
var e, f; | ||
while (e = leaveEdge(t)) { | ||
while ((e = leaveEdge(t))) { | ||
f = enterEdge(t, g, e); | ||
@@ -77,2 +76,3 @@ exchangeEdges(t, g, e, f); | ||
} | ||
function assignCutValue(t, g, child) { | ||
@@ -97,2 +97,3 @@ var childLab = t.node(child); | ||
var cutValue = 0; | ||
if (!graphEdge) { | ||
@@ -102,9 +103,13 @@ childIsTail = false; | ||
} | ||
cutValue = graphEdge.weight; | ||
g.nodeEdges(child).forEach(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; | ||
@@ -117,4 +122,6 @@ if (isTreeEdge(t, child, other)) { | ||
}); | ||
return cutValue; | ||
} | ||
function initLowLimValues(tree, root) { | ||
@@ -126,5 +133,7 @@ if (arguments.length < 2) { | ||
} | ||
function dfsAssignLowLim(tree, visited, nextLim, v, parent) { | ||
var low = nextLim; | ||
var label = tree.node(v); | ||
visited[v] = true; | ||
@@ -136,2 +145,3 @@ tree.neighbors(v).forEach(w => { | ||
}); | ||
label.low = low; | ||
@@ -145,7 +155,10 @@ label.lim = nextLim++; | ||
} | ||
return nextLim; | ||
} | ||
function leaveEdge(tree) { | ||
return tree.edges().find(e => tree.edge(e).cutvalue < 0); | ||
} | ||
function enterEdge(t, g, edge) { | ||
@@ -162,2 +175,3 @@ var v = edge.v; | ||
} | ||
var vLabel = t.node(v); | ||
@@ -174,12 +188,17 @@ var wLabel = t.node(w); | ||
} | ||
var candidates = g.edges().filter(edge => { | ||
return flip === isDescendant(t, t.node(edge.v), tailLabel) && flip !== isDescendant(t, t.node(edge.w), tailLabel); | ||
return flip === isDescendant(t, t.node(edge.v), tailLabel) && | ||
flip !== isDescendant(t, t.node(edge.w), tailLabel); | ||
}); | ||
return candidates.reduce((acc, edge) => { | ||
if ((0, _util.slack)(g, edge) < (0, _util.slack)(g, acc)) { | ||
if (slack(g, edge) < slack(g, acc)) { | ||
return edge; | ||
} | ||
return acc; | ||
}); | ||
} | ||
function exchangeEdges(t, g, e, f) { | ||
@@ -194,2 +213,3 @@ var v = e.v; | ||
} | ||
function updateRanks(t, g) { | ||
@@ -203,2 +223,3 @@ var root = t.nodes().find(v => !g.node(v).parent); | ||
flipped = false; | ||
if (!edge) { | ||
@@ -208,2 +229,3 @@ edge = g.edge(parent, v); | ||
} | ||
g.node(v).rank = g.node(parent).rank + (flipped ? edge.minlen : -edge.minlen); | ||
@@ -227,2 +249,1 @@ }); | ||
} | ||
module.exports = exports.default; |
"use strict"; | ||
module.exports = { | ||
longestPath: longestPath, | ||
slack: slack | ||
}; | ||
/* | ||
@@ -24,9 +29,5 @@ * Initializes ranks for the input graph using the longest path algorithm. This | ||
*/ | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.longestPath = longestPath; | ||
exports.slack = slack; | ||
function longestPath(g) { | ||
var visited = {}; | ||
function dfs(v) { | ||
@@ -38,2 +39,3 @@ var label = g.node(v); | ||
visited[v] = true; | ||
var rank = Math.min(...g.outEdges(v).map(e => { | ||
@@ -43,9 +45,13 @@ if (e == null) { | ||
} | ||
return dfs(e.w) - g.edge(e).minlen; | ||
})); | ||
if (rank === Number.POSITIVE_INFINITY) { | ||
rank = 0; | ||
} | ||
return label.rank = rank; | ||
return (label.rank = rank); | ||
} | ||
g.sources().forEach(dfs); | ||
@@ -52,0 +58,0 @@ } |
@@ -5,25 +5,26 @@ /* eslint "no-console": off */ | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.addBorderNode = addBorderNode; | ||
exports.addDummyNode = addDummyNode; | ||
exports.asNonCompoundGraph = asNonCompoundGraph; | ||
exports.buildLayerMatrix = buildLayerMatrix; | ||
exports.intersectRect = intersectRect; | ||
exports.mapValues = mapValues; | ||
exports.maxRank = maxRank; | ||
exports.normalizeRanks = normalizeRanks; | ||
exports.notime = notime; | ||
exports.partition = partition; | ||
exports.pick = pick; | ||
exports.predecessorWeights = predecessorWeights; | ||
exports.range = range; | ||
exports.removeEmptyRanks = removeEmptyRanks; | ||
exports.simplify = simplify; | ||
exports.successorWeights = successorWeights; | ||
exports.time = time; | ||
exports.uniqueId = uniqueId; | ||
exports.zipObject = zipObject; | ||
var _graphlib = require("@dagrejs/graphlib"); | ||
let Graph = require("@dagrejs/graphlib").Graph; | ||
module.exports = { | ||
addBorderNode, | ||
addDummyNode, | ||
asNonCompoundGraph, | ||
buildLayerMatrix, | ||
intersectRect, | ||
mapValues, | ||
maxRank, | ||
normalizeRanks, | ||
notime, | ||
partition, | ||
pick, | ||
predecessorWeights, | ||
range, | ||
removeEmptyRanks, | ||
simplify, | ||
successorWeights, | ||
time, | ||
uniqueId, | ||
zipObject, | ||
}; | ||
/* | ||
@@ -37,2 +38,3 @@ * Adds a dummy node to the graph and return v. | ||
} while (g.hasNode(v)); | ||
attrs.dummy = type; | ||
@@ -48,9 +50,6 @@ g.setNode(v, attrs); | ||
function simplify(g) { | ||
let simplified = new _graphlib.Graph().setGraph(g.graph()); | ||
let simplified = new Graph().setGraph(g.graph()); | ||
g.nodes().forEach(v => simplified.setNode(v, g.node(v))); | ||
g.edges().forEach(e => { | ||
let simpleLabel = simplified.edge(e.v, e.w) || { | ||
weight: 0, | ||
minlen: 1 | ||
}; | ||
let simpleLabel = simplified.edge(e.v, e.w) || { weight: 0, minlen: 1 }; | ||
let label = g.edge(e); | ||
@@ -64,6 +63,5 @@ simplified.setEdge(e.v, e.w, { | ||
} | ||
function asNonCompoundGraph(g) { | ||
let simplified = new _graphlib.Graph({ | ||
multigraph: g.isMultigraph() | ||
}).setGraph(g.graph()); | ||
let simplified = new Graph({ multigraph: g.isMultigraph() }).setGraph(g.graph()); | ||
g.nodes().forEach(v => { | ||
@@ -79,2 +77,3 @@ if (!g.children(v).length) { | ||
} | ||
function successorWeights(g) { | ||
@@ -90,2 +89,3 @@ let weightMap = g.nodes().map(v => { | ||
} | ||
function predecessorWeights(g) { | ||
@@ -116,5 +116,7 @@ let weightMap = g.nodes().map(v => { | ||
let h = rect.height / 2; | ||
if (!dx && !dy) { | ||
throw new Error("Not possible to find intersection inside of the rectangle"); | ||
} | ||
let sx, sy; | ||
@@ -136,6 +138,4 @@ if (Math.abs(dy) * w > Math.abs(dx) * h) { | ||
} | ||
return { | ||
x: x + sx, | ||
y: y + sy | ||
}; | ||
return { x: x + sx, y: y + sy }; | ||
} | ||
@@ -169,2 +169,3 @@ | ||
} | ||
return rank; | ||
@@ -179,5 +180,7 @@ })); | ||
} | ||
function removeEmptyRanks(g) { | ||
// Ranks may not start at 0, so we need to offset them | ||
let offset = Math.min(...g.nodes().map(v => g.node(v).rank)); | ||
let layers = []; | ||
@@ -191,2 +194,3 @@ g.nodes().forEach(v => { | ||
}); | ||
let delta = 0; | ||
@@ -202,2 +206,3 @@ let nodeRankFactor = g.graph().nodeRankFactor; | ||
} | ||
function addBorderNode(g, prefix, rank, order) { | ||
@@ -214,2 +219,3 @@ let node = { | ||
} | ||
function maxRank(g) { | ||
@@ -221,2 +227,3 @@ return Math.max(...g.nodes().map(v => { | ||
} | ||
return rank; | ||
@@ -232,6 +239,3 @@ })); | ||
function partition(collection, fn) { | ||
let result = { | ||
lhs: [], | ||
rhs: [] | ||
}; | ||
let result = { lhs: [], rhs: [] }; | ||
collection.forEach(value => { | ||
@@ -259,5 +263,7 @@ if (fn(value)) { | ||
} | ||
function notime(name, fn) { | ||
return fn(); | ||
} | ||
let idCounter = 0; | ||
@@ -268,2 +274,3 @@ function uniqueId(prefix) { | ||
} | ||
function range(start, limit, step = 1) { | ||
@@ -274,6 +281,8 @@ if (limit == null) { | ||
} | ||
let endCon = i => i < limit; | ||
let endCon = (i) => i < limit; | ||
if (step < 0) { | ||
endCon = i => limit < i; | ||
endCon = (i) => limit < i; | ||
} | ||
const range = []; | ||
@@ -283,4 +292,6 @@ for (let i = start; endCon(i); i += step) { | ||
} | ||
return range; | ||
} | ||
function pick(source, keys) { | ||
@@ -293,9 +304,12 @@ const dest = {}; | ||
} | ||
return dest; | ||
} | ||
function mapValues(obj, funcOrProp) { | ||
let func = funcOrProp; | ||
if (typeof funcOrProp === 'string') { | ||
func = val => val[funcOrProp]; | ||
func = (val) => val[funcOrProp]; | ||
} | ||
return Object.entries(obj).reduce((acc, [k, v]) => { | ||
@@ -306,2 +320,3 @@ acc[k] = func(v, k); | ||
} | ||
function zipObject(props, values) { | ||
@@ -308,0 +323,0 @@ return props.reduce((acc, key, i) => { |
@@ -1,8 +0,1 @@ | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = void 0; | ||
var _default = exports.default = "1.1.0"; | ||
module.exports = exports.default; | ||
module.exports = "1.1.1"; |
{ | ||
"name": "@dagrejs/dagre", | ||
"version": "1.1.0", | ||
"version": "1.1.1", | ||
"description": "Graph layout for JavaScript", | ||
@@ -15,7 +15,2 @@ "author": "Chris Pettitt <cpettitt@gmail.com>", | ||
}, | ||
"module": "./mjs-lib/index.js", | ||
"exports": { | ||
"import": "./mjs-lib/index.js", | ||
"require": "./index.js" | ||
}, | ||
"files": [ | ||
@@ -25,4 +20,3 @@ "index.js", | ||
"dist/", | ||
"lib/", | ||
"mjs-lib/" | ||
"lib/" | ||
], | ||
@@ -35,10 +29,5 @@ "types": "index.d.ts", | ||
"dependencies": { | ||
"@dagrejs/graphlib": "2.2.0" | ||
"@dagrejs/graphlib": "2.2.1" | ||
}, | ||
"devDependencies": { | ||
"@babel/cli": "^7.23.9", | ||
"@babel/core": "^7.23.9", | ||
"@babel/plugin-transform-export-namespace-from": "^7.23.4", | ||
"@babel/plugin-transform-modules-commonjs": "^7.23.3", | ||
"babel-plugin-add-module-exports": "^1.0.4", | ||
"benchmark": "2.1.4", | ||
@@ -52,3 +41,2 @@ "browserify": "17.0.0", | ||
"karma-chrome-launcher": "3.1.1", | ||
"karma-firefox-launcher": "2.1.2", | ||
"karma-mocha": "2.0.1", | ||
@@ -55,0 +43,0 @@ "karma-requirejs": "1.1.0", |
Sorry, the diff of this file is too big to display
Sorry, the diff of this file is too big to display
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
17
295772
34
7404
+ Added@dagrejs/graphlib@2.2.1(transitive)
- Removed@dagrejs/graphlib@2.2.0(transitive)
Updated@dagrejs/graphlib@2.2.1