@dagrejs/dagre
Advanced tools
Comparing version 1.0.4 to 1.1.0
@@ -108,8 +108,15 @@ // Type definitions for dagre 1.0.1 | ||
height?: number | undefined; | ||
lablepos?: 'l' | 'c' | 'r' | undefined; | ||
labelpos?: 'l' | 'c' | 'r' | undefined; | ||
labeloffest?: number | undefined; | ||
} | ||
export function layout(graph: graphlib.Graph, layout?: GraphLabel & NodeConfig & EdgeConfig): void; | ||
export interface LayoutConfig { | ||
customOrder?: (graph: graphlib.Graph, order: (graph: graphlib.Graph, opts: configUnion) => void) => void; | ||
disableOptimalOrderHeuristic?: boolean; | ||
} | ||
type configUnion = GraphLabel & NodeConfig & EdgeConfig & LayoutConfig; | ||
export function layout(graph: graphlib.Graph, layout?: configUnion): void; | ||
export interface Edge { | ||
@@ -136,2 +143,3 @@ v: string; | ||
paddingY?: number | undefined; | ||
rank?: number | undefined; | ||
rx?: number | undefined; | ||
@@ -138,0 +146,0 @@ ry?: number | undefined; |
"use strict"; | ||
let greedyFAS = require("./greedy-fas"); | ||
let uniqueId = require("./util").uniqueId; | ||
module.exports = { | ||
run: run, | ||
undo: undo | ||
}; | ||
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 }; } | ||
function run(g) { | ||
let fas = (g.graph().acyclicer === "greedy" | ||
? greedyFAS(g, weightFn(g)) | ||
: dfsFAS(g)); | ||
let fas = g.graph().acyclicer === "greedy" ? (0, _greedyFas.default)(g, weightFn(g)) : dfsFAS(g); | ||
fas.forEach(e => { | ||
@@ -20,5 +18,4 @@ let label = g.edge(e); | ||
label.reversed = true; | ||
g.setEdge(e.w, e.v, label, uniqueId("rev")); | ||
g.setEdge(e.w, e.v, label, (0, _util.uniqueId)("rev")); | ||
}); | ||
function weightFn(g) { | ||
@@ -30,3 +27,2 @@ return e => { | ||
} | ||
function dfsFAS(g) { | ||
@@ -36,3 +32,2 @@ let fas = []; | ||
let visited = {}; | ||
function dfs(v) { | ||
@@ -53,7 +48,5 @@ if (visited.hasOwnProperty(v)) { | ||
} | ||
g.nodes().forEach(dfs); | ||
return fas; | ||
} | ||
function undo(g) { | ||
@@ -64,3 +57,2 @@ g.edges().forEach(e => { | ||
g.removeEdge(e); | ||
let forwardName = label.forwardName; | ||
@@ -67,0 +59,0 @@ delete label.reversed; |
@@ -1,5 +0,10 @@ | ||
let util = require("./util"); | ||
"use strict"; | ||
module.exports = addBorderSegments; | ||
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; } | ||
function addBorderSegments(g) { | ||
@@ -12,9 +17,6 @@ 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); | ||
@@ -25,8 +27,11 @@ 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]; | ||
@@ -37,4 +42,7 @@ 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"; | ||
module.exports = { | ||
adjust: adjust, | ||
undo: undo | ||
}; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.adjust = adjust; | ||
exports.undo = undo; | ||
function adjust(g) { | ||
@@ -14,3 +14,2 @@ let rankDir = g.graph().rankdir.toLowerCase(); | ||
} | ||
function undo(g) { | ||
@@ -21,3 +20,2 @@ let rankDir = g.graph().rankdir.toLowerCase(); | ||
} | ||
if (rankDir === "lr" || rankDir === "rl") { | ||
@@ -28,3 +26,2 @@ swapXY(g); | ||
} | ||
function swapWidthHeight(g) { | ||
@@ -34,3 +31,2 @@ g.nodes().forEach(v => swapWidthHeightOne(g.node(v))); | ||
} | ||
function swapWidthHeightOne(attrs) { | ||
@@ -41,6 +37,4 @@ let w = attrs.width; | ||
} | ||
function reverseY(g) { | ||
g.nodes().forEach(v => reverseYOne(g.node(v))); | ||
g.edges().forEach(e => { | ||
@@ -54,10 +48,7 @@ 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 => { | ||
@@ -71,3 +62,2 @@ let edge = g.edge(e); | ||
} | ||
function swapXYOne(attrs) { | ||
@@ -74,0 +64,0 @@ let x = attrs.x; |
@@ -0,1 +1,7 @@ | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = void 0; | ||
/* | ||
@@ -12,3 +18,2 @@ * Simple doubly linked list implementation derived from Cormen, et al., | ||
} | ||
dequeue() { | ||
@@ -22,3 +27,2 @@ let sentinel = this._sentinel; | ||
} | ||
enqueue(entry) { | ||
@@ -34,3 +38,2 @@ let sentinel = this._sentinel; | ||
} | ||
toString() { | ||
@@ -47,3 +50,3 @@ let strs = []; | ||
} | ||
exports.default = List; | ||
function unlink(entry) { | ||
@@ -55,3 +58,2 @@ entry._prev._next = entry._next; | ||
} | ||
function filterOutLinks(k, v) { | ||
@@ -62,3 +64,2 @@ if (k !== "_next" && k !== "_prev") { | ||
} | ||
module.exports = List; | ||
module.exports = exports.default; |
@@ -1,7 +0,13 @@ | ||
let util = require("./util"); | ||
let Graph = require("@dagrejs/graphlib").Graph; | ||
"use strict"; | ||
module.exports = { | ||
debugOrdering: debugOrdering | ||
}; | ||
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 | ||
@@ -11,22 +17,27 @@ /* istanbul ignore next */ | ||
let layerMatrix = util.buildLayerMatrix(g); | ||
let h = new Graph({ compound: true, multigraph: true }).setGraph({}); | ||
let h = new _graphlib.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,4 +0,13 @@ | ||
let Graph = require("@dagrejs/graphlib").Graph; | ||
let List = require("./data/list"); | ||
"use strict"; | ||
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 | ||
/* | ||
@@ -11,6 +20,4 @@ * 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) { | ||
@@ -26,3 +33,2 @@ if (g.nodeCount() <= 1) { | ||
} | ||
function doGreedyFAS(g, buckets, zeroIdx) { | ||
@@ -32,7 +38,10 @@ 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()) { | ||
@@ -48,21 +57,18 @@ 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 => { | ||
@@ -75,15 +81,15 @@ let weight = g.edge(edge); | ||
}); | ||
g.removeNode(entry.v); | ||
return results; | ||
} | ||
function buildState(g, weightFn) { | ||
let fasGraph = new Graph(); | ||
let fasGraph = new _graphlib.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 | ||
}); | ||
}); | ||
@@ -99,15 +105,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()); | ||
let buckets = range(maxOut + maxIn + 3).map(() => new _list.default()); | ||
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) { | ||
@@ -122,3 +128,2 @@ if (!entry.out) { | ||
} | ||
function range(limit) { | ||
@@ -129,4 +134,4 @@ const range = []; | ||
} | ||
return range; | ||
} | ||
module.exports = exports.default; |
"use strict"; | ||
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; | ||
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; | ||
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", () => rank(util.asNonCompoundGraph(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(" 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", () => parentDummyChains(g)); | ||
time(" addBorderSegments", () => addBorderSegments(g)); | ||
time(" order", () => order(g)); | ||
time(" insertSelfEdges", () => insertSelfEdges(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(" adjustCoordinateSystem", () => coordinateSystem.adjust(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)); | ||
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)); | ||
} | ||
@@ -69,3 +71,2 @@ | ||
let layoutLabel = layoutGraph.node(v); | ||
if (inputLabel) { | ||
@@ -75,3 +76,2 @@ inputLabel.x = layoutLabel.x; | ||
inputLabel.rank = layoutLabel.rank; | ||
if (layoutGraph.children(v).length) { | ||
@@ -83,7 +83,5 @@ inputLabel.width = layoutLabel.width; | ||
}); | ||
inputGraph.edges().forEach(e => { | ||
let inputLabel = inputGraph.edge(e); | ||
let layoutLabel = layoutGraph.edge(e); | ||
inputLabel.points = layoutLabel.points; | ||
@@ -95,16 +93,26 @@ 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" | ||
}; | ||
@@ -120,10 +128,8 @@ let edgeAttrs = ["labelpos"]; | ||
function buildLayoutGraph(inputGraph) { | ||
let g = new Graph({ multigraph: true, compound: true }); | ||
let g = new _graphlib.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 => { | ||
@@ -137,15 +143,9 @@ 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,3 +190,6 @@ } | ||
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"); | ||
@@ -196,3 +199,2 @@ } | ||
} | ||
function assignRankMinMax(g) { | ||
@@ -210,3 +212,2 @@ let maxRank = 0; | ||
} | ||
function removeEdgeLabelProxies(g) { | ||
@@ -221,3 +222,2 @@ g.nodes().forEach(v => { | ||
} | ||
function translateGraph(g) { | ||
@@ -231,3 +231,2 @@ let minX = Number.POSITIVE_INFINITY; | ||
let marginY = graphLabel.marginy || 0; | ||
function getExtremes(attrs) { | ||
@@ -243,3 +242,2 @@ let x = attrs.x; | ||
} | ||
g.nodes().forEach(v => getExtremes(g.node(v))); | ||
@@ -252,6 +250,4 @@ g.edges().forEach(e => { | ||
}); | ||
minX -= marginX; | ||
minY -= marginY; | ||
g.nodes().forEach(v => { | ||
@@ -262,3 +258,2 @@ let node = g.node(v); | ||
}); | ||
g.edges().forEach(e => { | ||
@@ -270,10 +265,12 @@ 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) { | ||
@@ -297,3 +294,2 @@ g.edges().forEach(e => { | ||
} | ||
function fixupEdgeLabelCoords(g) { | ||
@@ -307,4 +303,8 @@ 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,3 +314,2 @@ } | ||
} | ||
function reversePointsForReversedEdges(g) { | ||
@@ -324,3 +323,2 @@ g.edges().forEach(e => { | ||
} | ||
function removeBorderNodes(g) { | ||
@@ -334,3 +332,2 @@ g.nodes().forEach(v => { | ||
let r = g.node(node.borderRight[node.borderRight.length - 1]); | ||
node.width = Math.abs(r.x - l.x); | ||
@@ -342,3 +339,2 @@ node.height = Math.abs(b.y - t.y); | ||
}); | ||
g.nodes().forEach(v => { | ||
@@ -350,3 +346,2 @@ if (g.node(v).dummy === "border") { | ||
} | ||
function removeSelfEdges(g) { | ||
@@ -359,3 +354,6 @@ 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); | ||
@@ -365,3 +363,2 @@ } | ||
} | ||
function insertSelfEdges(g) { | ||
@@ -379,3 +376,3 @@ var layers = util.buildLayerMatrix(g); | ||
rank: node.rank, | ||
order: i + (++orderShift), | ||
order: i + ++orderShift, | ||
e: selfEdge.e, | ||
@@ -389,3 +386,2 @@ label: selfEdge.label | ||
} | ||
function positionSelfEdges(g) { | ||
@@ -402,9 +398,18 @@ 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; | ||
@@ -415,7 +420,5 @@ node.label.y = node.y; | ||
} | ||
function selectNumberAttrs(obj, attrs) { | ||
return util.mapValues(util.pick(obj, attrs), Number); | ||
} | ||
function canonicalize(attrs) { | ||
@@ -428,3 +431,2 @@ var newAttrs = {}; | ||
} | ||
newAttrs[k] = v; | ||
@@ -435,1 +437,2 @@ }); | ||
} | ||
module.exports = exports.default; |
@@ -1,8 +0,11 @@ | ||
let util = require("./util"); | ||
"use strict"; | ||
module.exports = { | ||
run, | ||
cleanup, | ||
}; | ||
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; } | ||
/* | ||
@@ -36,3 +39,2 @@ * A nesting graph creates dummy nodes for the tops and bottoms of subgraphs, | ||
let nodeSep = 2 * height + 1; | ||
g.graph().nestingRoot = root; | ||
@@ -53,3 +55,2 @@ | ||
} | ||
function dfs(g, root, nodeSep, weight, height, depths, v) { | ||
@@ -59,11 +60,12 @@ 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); | ||
@@ -73,6 +75,4 @@ label.borderTop = top; | ||
label.borderBottom = bottom; | ||
children.forEach(child => { | ||
dfs(g, root, nodeSep, weight, height, depths, child); | ||
let childNode = g.node(child); | ||
@@ -83,3 +83,2 @@ let childTop = childNode.borderTop ? childNode.borderTop : child; | ||
let minlen = childTop !== childBottom ? 1 : height - depths[v] + 1; | ||
g.setEdge(top, childTop, { | ||
@@ -90,3 +89,2 @@ weight: thisWeight, | ||
}); | ||
g.setEdge(childBottom, bottom, { | ||
@@ -98,8 +96,9 @@ 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) { | ||
@@ -117,7 +116,5 @@ var depths = {}; | ||
} | ||
function sumWeights(g) { | ||
return g.edges().reduce((acc, e) => acc + g.edge(e).weight, 0); | ||
} | ||
function cleanup(g) { | ||
@@ -124,0 +121,0 @@ var graphLabel = g.graph(); |
"use strict"; | ||
let util = require("./util"); | ||
module.exports = { | ||
run: run, | ||
undo: undo | ||
}; | ||
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; } | ||
/* | ||
@@ -30,3 +31,2 @@ * Breaks any long edges in the graph into short segments that span 1 layer | ||
} | ||
function normalizeEdge(g, e) { | ||
@@ -40,7 +40,4 @@ let v = e.v; | ||
let labelRank = edgeLabel.labelRank; | ||
if (wRank === vRank + 1) return; | ||
g.removeEdge(e); | ||
let dummy, attrs, i; | ||
@@ -50,4 +47,6 @@ 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 | ||
@@ -62,3 +61,5 @@ }; | ||
} | ||
g.setEdge(v, dummy, { weight: edgeLabel.weight }, name); | ||
g.setEdge(v, dummy, { | ||
weight: edgeLabel.weight | ||
}, name); | ||
if (i === 0) { | ||
@@ -69,6 +70,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) { | ||
@@ -83,3 +84,6 @@ 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") { | ||
@@ -86,0 +90,0 @@ origLabel.x = node.x; |
@@ -1,7 +0,10 @@ | ||
module.exports = addSubgraphConstraints; | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = addSubgraphConstraints; | ||
function addSubgraphConstraints(g, cg, vs) { | ||
let prev = {}, | ||
rootPrev; | ||
vs.forEach(v => { | ||
@@ -52,1 +55,2 @@ let child = g.parent(v), | ||
} | ||
module.exports = exports.default; |
@@ -1,3 +0,7 @@ | ||
module.exports = barycenter; | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = barycenter; | ||
function barycenter(g, movable = []) { | ||
@@ -7,3 +11,5 @@ return movable.map(v => { | ||
if (!inV.length) { | ||
return { v: v }; | ||
return { | ||
v: v | ||
}; | ||
} else { | ||
@@ -14,7 +20,9 @@ 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 { | ||
@@ -28,2 +36,2 @@ v: v, | ||
} | ||
module.exports = exports.default; |
@@ -1,6 +0,11 @@ | ||
let Graph = require("@dagrejs/graphlib").Graph; | ||
let util = require("../util"); | ||
"use strict"; | ||
module.exports = buildLayerGraph; | ||
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; } | ||
/* | ||
@@ -38,9 +43,10 @@ * Constructs a graph that can be used to sort a layer of nodes. The graph will | ||
let root = createRootNode(g), | ||
result = new Graph({ compound: true }).setGraph({ root: root }) | ||
.setDefaultNodeLabel(v => g.node(v)); | ||
result = new _graphlib.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) { | ||
@@ -55,5 +61,6 @@ 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")) { | ||
@@ -67,10 +74,9 @@ 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"; | ||
let zipObject = require("../util").zipObject; | ||
module.exports = crossCount; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = crossCount; | ||
var _util = require("../util.js"); | ||
/* | ||
@@ -26,7 +27,6 @@ * 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,6 +36,9 @@ // Sort all of the edges between the north and south layers by their position | ||
// their head in the south layer. | ||
let southPos = zipObject(southLayer, southLayer.map((v, i) => i)); | ||
let southPos = (0, _util.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); | ||
@@ -61,3 +64,3 @@ }); | ||
} | ||
index = (index - 1) >> 1; | ||
index = index - 1 >> 1; | ||
tree[index] += entry.weight; | ||
@@ -67,4 +70,4 @@ } | ||
}); | ||
return cc; | ||
} | ||
module.exports = exports.default; |
"use strict"; | ||
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; | ||
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 }; } | ||
/* | ||
@@ -28,3 +32,8 @@ * Applies heuristics to minimize edge crossings in the graph and sets the best | ||
*/ | ||
function order(g) { | ||
function order(g, opts) { | ||
if (opts && typeof opts.customOrder === 'function') { | ||
opts.customOrder(g, order); | ||
return; | ||
} | ||
let maxRank = util.maxRank(g), | ||
@@ -34,5 +43,9 @@ downLayerGraphs = buildLayerGraphs(g, util.range(1, maxRank + 1), "inEdges"), | ||
let layering = initOrder(g); | ||
let layering = (0, _initOrder.default)(g); | ||
assignOrder(g, layering); | ||
if (opts && opts.disableOptimalOrderHeuristic) { | ||
return; | ||
} | ||
let bestCC = Number.POSITIVE_INFINITY, | ||
@@ -43,5 +56,4 @@ best; | ||
sweepLayerGraphs(i % 2 ? downLayerGraphs : upLayerGraphs, i % 4 >= 2); | ||
layering = util.buildLayerMatrix(g); | ||
let cc = crossCount(g, layering); | ||
let cc = (0, _crossCount.default)(g, layering); | ||
if (cc < bestCC) { | ||
@@ -53,24 +65,21 @@ lastBest = 0; | ||
} | ||
assignOrder(g, best); | ||
} | ||
function buildLayerGraphs(g, ranks, relationship) { | ||
return ranks.map(function(rank) { | ||
return buildLayerGraph(g, rank, relationship); | ||
return ranks.map(function (rank) { | ||
return (0, _buildLayerGraph.default)(g, rank, relationship); | ||
}); | ||
} | ||
function sweepLayerGraphs(layerGraphs, biasRight) { | ||
let cg = new Graph(); | ||
layerGraphs.forEach(function(lg) { | ||
let cg = new _graphlib.Graph(); | ||
layerGraphs.forEach(function (lg) { | ||
let root = lg.graph().root; | ||
let sorted = sortSubgraph(lg, root, cg, biasRight); | ||
let sorted = (0, _sortSubgraph.default)(lg, root, cg, biasRight); | ||
sorted.vs.forEach((v, i) => lg.node(v).order = i); | ||
addSubgraphConstraints(lg, cg, sorted.vs); | ||
(0, _addSubgraphConstraints.default)(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"; | ||
let util = require("../util"); | ||
module.exports = initOrder; | ||
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; } | ||
/* | ||
@@ -23,3 +26,2 @@ * Assigns an initial order value for each node by performing a DFS search | ||
let layers = util.range(maxRank + 1).map(() => []); | ||
function dfs(v) { | ||
@@ -32,7 +34,6 @@ 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"; | ||
let util = require("../util"); | ||
module.exports = resolveConflicts; | ||
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; } | ||
/* | ||
@@ -47,3 +50,2 @@ * Given a list of entries of the form {v, barycenter, weight} and a | ||
}); | ||
cg.edges().forEach(e => { | ||
@@ -57,11 +59,7 @@ 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) { | ||
@@ -72,5 +70,3 @@ 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); | ||
@@ -80,3 +76,2 @@ } | ||
} | ||
function handleOut(vEntry) { | ||
@@ -90,3 +85,2 @@ return wEntry => { | ||
} | ||
while (sourceSet.length) { | ||
@@ -98,3 +92,2 @@ let entry = sourceSet.pop(); | ||
} | ||
return entries.filter(entry => !entry.merged).map(entry => { | ||
@@ -104,7 +97,5 @@ return util.pick(entry, ["vs", "i", "barycenter", "weight"]); | ||
} | ||
function mergeEntries(target, source) { | ||
let sum = 0; | ||
let weight = 0; | ||
if (target.weight) { | ||
@@ -114,3 +105,2 @@ sum += target.barycenter * target.weight; | ||
} | ||
if (source.weight) { | ||
@@ -120,3 +110,2 @@ sum += source.barycenter * source.weight; | ||
} | ||
target.vs = source.vs.concat(target.vs); | ||
@@ -128,1 +117,2 @@ target.barycenter = sum / weight; | ||
} | ||
module.exports = exports.default; |
@@ -1,7 +0,11 @@ | ||
let barycenter = require("./barycenter"); | ||
let resolveConflicts = require("./resolve-conflicts"); | ||
let sort = require("./sort"); | ||
"use strict"; | ||
module.exports = sortSubgraph; | ||
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 }; } | ||
function sortSubgraph(g, v, cg, biasRight) { | ||
@@ -11,10 +15,8 @@ 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 = barycenter(g, movable); | ||
let barycenters = (0, _barycenter.default)(g, movable); | ||
barycenters.forEach(entry => { | ||
@@ -29,8 +31,5 @@ if (g.children(entry.v).length) { | ||
}); | ||
let entries = resolveConflicts(barycenters, cg); | ||
let entries = (0, _resolveConflicts.default)(barycenters, cg); | ||
expandSubgraphs(entries, subgraphs); | ||
let result = sort(entries, biasRight); | ||
let result = (0, _sort.default)(entries, biasRight); | ||
if (bl) { | ||
@@ -45,11 +44,8 @@ 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) { | ||
@@ -65,8 +61,5 @@ 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; | ||
@@ -78,1 +71,2 @@ } else { | ||
} | ||
module.exports = exports.default; |
@@ -1,5 +0,10 @@ | ||
let util = require("../util"); | ||
"use strict"; | ||
module.exports = sort; | ||
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; } | ||
function sort(entries, biasRight) { | ||
@@ -15,7 +20,4 @@ let parts = util.partition(entries, entry => { | ||
vsIndex = 0; | ||
sortable.sort(compareWithBias(!!biasRight)); | ||
vsIndex = consumeUnsortable(vs, unsortable, vsIndex); | ||
sortable.forEach(entry => { | ||
@@ -28,4 +30,5 @@ vsIndex += entry.vs.length; | ||
}); | ||
let result = { vs: vs.flat(true) }; | ||
let result = { | ||
vs: vs.flat(true) | ||
}; | ||
if (weight) { | ||
@@ -37,3 +40,2 @@ result.barycenter = sum / weight; | ||
} | ||
function consumeUnsortable(vs, unsortable, index) { | ||
@@ -48,3 +50,2 @@ let last; | ||
} | ||
function compareWithBias(bias) { | ||
@@ -57,5 +58,5 @@ return (entryV, entryW) => { | ||
} | ||
return !bias ? entryV.i - entryW.i : entryW.i - entryV.i; | ||
}; | ||
} | ||
module.exports = exports.default; |
@@ -1,6 +0,9 @@ | ||
module.exports = parentDummyChains; | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = parentDummyChains; | ||
function parentDummyChains(g) { | ||
let postorderNums = postorder(g); | ||
g.graph().dummyChains.forEach(v => { | ||
@@ -15,12 +18,8 @@ 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) { | ||
@@ -30,6 +29,4 @@ 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++; | ||
@@ -39,3 +36,2 @@ } | ||
} | ||
g.setParent(v, pathV); | ||
@@ -62,4 +58,3 @@ 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; | ||
@@ -72,18 +67,21 @@ | ||
} | ||
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"; | ||
let Graph = require("@dagrejs/graphlib").Graph; | ||
let util = require("../util"); | ||
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; } | ||
/* | ||
@@ -11,15 +25,2 @@ * 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 | ||
}; | ||
/* | ||
@@ -44,3 +45,2 @@ * Marks all edges in the graph with a type-1 conflict with the "type1Conflict" | ||
let conflicts = {}; | ||
function visitLayer(prevLayer, layer) { | ||
@@ -56,14 +56,11 @@ 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); | ||
@@ -77,13 +74,9 @@ } | ||
}); | ||
return layer; | ||
} | ||
layering.reduce(visitLayer); | ||
layering.length && layering.reduce(visitLayer); | ||
return conflicts; | ||
} | ||
function findType2Conflicts(g, layering) { | ||
let conflicts = {}; | ||
function scan(south, southPos, southEnd, prevNorthBorder, nextNorthBorder) { | ||
@@ -96,4 +89,3 @@ 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); | ||
@@ -105,4 +97,2 @@ } | ||
} | ||
function visitLayer(north, south) { | ||
@@ -112,3 +102,2 @@ let prevNorthPos = -1, | ||
southPos = 0; | ||
south.forEach((v, southLookahead) => { | ||
@@ -126,10 +115,7 @@ if (g.node(v).dummy === "border") { | ||
}); | ||
return south; | ||
} | ||
layering.reduce(visitLayer); | ||
layering.length && layering.reduce(visitLayer); | ||
return conflicts; | ||
} | ||
function findOtherInnerSegmentNode(g, v) { | ||
@@ -140,3 +126,2 @@ if (g.node(v).dummy) { | ||
} | ||
function addConflict(conflicts, v, w) { | ||
@@ -148,3 +133,2 @@ if (v > w) { | ||
} | ||
let conflictsV = conflicts[v]; | ||
@@ -156,3 +140,2 @@ if (!conflictsV) { | ||
} | ||
function hasConflict(conflicts, v, w) { | ||
@@ -190,3 +173,2 @@ if (v > w) { | ||
}); | ||
layering.forEach(layer => { | ||
@@ -201,5 +183,3 @@ 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; | ||
@@ -213,6 +193,7 @@ align[v] = root[v] = root[w]; | ||
}); | ||
return { root: root, align: align }; | ||
return { | ||
root: root, | ||
align: align | ||
}; | ||
} | ||
function horizontalCompaction(g, layering, root, align, reverseSep) { | ||
@@ -227,3 +208,2 @@ // This portion of the algorithm differs from BK due to a number of problems. | ||
borderType = reverseSep ? "borderLeft" : "borderRight"; | ||
function iterate(setXsFunc, nextNodesFunc) { | ||
@@ -241,3 +221,2 @@ let stack = blockG.nodes(); | ||
} | ||
elem = stack.pop(); | ||
@@ -259,3 +238,2 @@ } | ||
}, Number.POSITIVE_INFINITY); | ||
let node = g.node(elem); | ||
@@ -266,3 +244,2 @@ if (min !== Number.POSITIVE_INFINITY && node.borderType !== borderType) { | ||
} | ||
iterate(pass1, blockG.predecessors.bind(blockG)); | ||
@@ -273,12 +250,8 @@ 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 Graph(), | ||
let blockGraph = new _graphlib.Graph(), | ||
graphLabel = g.graph(), | ||
sepFn = sep(graphLabel.nodesep, graphLabel.edgesep, reverseSep); | ||
layering.forEach(layer => { | ||
@@ -297,3 +270,2 @@ let u; | ||
}); | ||
return blockGraph; | ||
@@ -309,10 +281,7 @@ } | ||
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; | ||
@@ -337,3 +306,2 @@ if (newMin < currentMinAndXs[0]) { | ||
alignToMax = Math.max(...alignToVals); | ||
["u", "d"].forEach(vert => { | ||
@@ -343,5 +311,3 @@ ["l", "r"].forEach(horiz => { | ||
xs = xss[alignment]; | ||
if (xs === alignTo) return; | ||
let xsVals = Object.values(xs); | ||
@@ -352,3 +318,2 @@ let delta = alignToMin - Math.min(...xsVals); | ||
} | ||
if (delta) { | ||
@@ -360,3 +325,2 @@ xss[alignment] = util.mapValues(xs, x => x + delta); | ||
} | ||
function balance(xss, align) { | ||
@@ -372,9 +336,5 @@ 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 = {}; | ||
@@ -390,7 +350,5 @@ 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") { | ||
@@ -402,4 +360,2 @@ xs = util.mapValues(xs, x => -x); | ||
}); | ||
let smallestWidth = findSmallestWidthAlignment(g, xss); | ||
@@ -409,3 +365,2 @@ alignCoordinates(xss, smallestWidth); | ||
} | ||
function sep(nodeSep, edgeSep, reverseSep) { | ||
@@ -417,8 +372,11 @@ 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; | ||
} | ||
@@ -430,11 +388,13 @@ } | ||
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; | ||
} | ||
@@ -446,9 +406,7 @@ } | ||
delta = 0; | ||
return sum; | ||
}; | ||
} | ||
function width(g, v) { | ||
return g.node(v).width; | ||
} |
"use strict"; | ||
let util = require("../util"); | ||
let positionX = require("./bk").positionX; | ||
module.exports = position; | ||
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; } | ||
function position(g) { | ||
g = util.asNonCompoundGraph(g); | ||
positionY(g); | ||
Object.entries(positionX(g)).forEach(([v, x]) => g.node(v).x = x); | ||
Object.entries((0, _bk.positionX)(g)).forEach(([v, x]) => g.node(v).x = x); | ||
} | ||
function positionY(g) { | ||
@@ -32,2 +33,2 @@ let layering = util.buildLayerMatrix(g); | ||
} | ||
module.exports = exports.default; |
"use strict"; | ||
var Graph = require("@dagrejs/graphlib").Graph; | ||
var slack = require("./util").slack; | ||
module.exports = feasibleTree; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = feasibleTree; | ||
var _graphlib = require("@dagrejs/graphlib"); | ||
var _util = require("./util.js"); | ||
/* | ||
@@ -34,3 +35,5 @@ * Constructs a spanning tree with tight edges and adjusted the input node's | ||
function feasibleTree(g) { | ||
var t = new Graph({ directed: false }); | ||
var t = new _graphlib.Graph({ | ||
directed: false | ||
}); | ||
@@ -41,10 +44,8 @@ // 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) ? slack(g, edge) : -slack(g, edge); | ||
delta = t.hasNode(edge.v) ? (0, _util.slack)(g, edge) : -(0, _util.slack)(g, edge); | ||
shiftRanks(t, g, delta); | ||
} | ||
return t; | ||
@@ -61,4 +62,4 @@ } | ||
var edgeV = e.v, | ||
w = (v === edgeV) ? e.w : edgeV; | ||
if (!t.hasNode(w) && !slack(g, e)) { | ||
w = v === edgeV ? e.w : edgeV; | ||
if (!t.hasNode(w) && !(0, _util.slack)(g, e)) { | ||
t.setNode(w, {}); | ||
@@ -70,3 +71,2 @@ t.setEdge(v, w, {}); | ||
} | ||
t.nodes().forEach(dfs); | ||
@@ -82,19 +82,16 @@ 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 = slack(g, edge); | ||
edgeSlack = (0, _util.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"; | ||
var rankUtil = require("./util"); | ||
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 longestPath = rankUtil.longestPath; | ||
var feasibleTree = require("./feasible-tree"); | ||
var networkSimplex = require("./network-simplex"); | ||
module.exports = rank; | ||
/* | ||
@@ -30,7 +34,14 @@ * 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); | ||
} | ||
@@ -41,10 +52,9 @@ } | ||
var longestPathRanker = longestPath; | ||
function tightTreeRanker(g) { | ||
longestPath(g); | ||
feasibleTree(g); | ||
(0, _feasibleTree.default)(g); | ||
} | ||
function networkSimplexRanker(g) { | ||
networkSimplex(g); | ||
(0, _networkSimplex.default)(g); | ||
} | ||
module.exports = exports.default; |
"use strict"; | ||
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; | ||
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; | ||
// Expose some internals for testing purposes | ||
@@ -54,10 +56,9 @@ networkSimplex.initLowLimValues = initLowLimValues; | ||
function networkSimplex(g) { | ||
g = simplify(g); | ||
initRank(g); | ||
var t = feasibleTree(g); | ||
g = (0, _util2.simplify)(g); | ||
(0, _util.longestPath)(g); | ||
var t = (0, _feasibleTree.default)(g); | ||
initLowLimValues(t); | ||
initCutValues(t, g); | ||
var e, f; | ||
while ((e = leaveEdge(t))) { | ||
while (e = leaveEdge(t)) { | ||
f = enterEdge(t, g, e); | ||
@@ -76,3 +77,2 @@ exchangeEdges(t, g, e, f); | ||
} | ||
function assignCutValue(t, g, child) { | ||
@@ -97,3 +97,2 @@ var childLab = t.node(child); | ||
var cutValue = 0; | ||
if (!graphEdge) { | ||
@@ -103,13 +102,9 @@ 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; | ||
@@ -122,6 +117,4 @@ if (isTreeEdge(t, child, other)) { | ||
}); | ||
return cutValue; | ||
} | ||
function initLowLimValues(tree, root) { | ||
@@ -133,7 +126,5 @@ if (arguments.length < 2) { | ||
} | ||
function dfsAssignLowLim(tree, visited, nextLim, v, parent) { | ||
var low = nextLim; | ||
var label = tree.node(v); | ||
visited[v] = true; | ||
@@ -145,3 +136,2 @@ tree.neighbors(v).forEach(w => { | ||
}); | ||
label.low = low; | ||
@@ -155,10 +145,7 @@ label.lim = nextLim++; | ||
} | ||
return nextLim; | ||
} | ||
function leaveEdge(tree) { | ||
return tree.edges().find(e => tree.edge(e).cutvalue < 0); | ||
} | ||
function enterEdge(t, g, edge) { | ||
@@ -175,3 +162,2 @@ var v = edge.v; | ||
} | ||
var vLabel = t.node(v); | ||
@@ -188,17 +174,12 @@ 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 (slack(g, edge) < slack(g, acc)) { | ||
if ((0, _util.slack)(g, edge) < (0, _util.slack)(g, acc)) { | ||
return edge; | ||
} | ||
return acc; | ||
}); | ||
} | ||
function exchangeEdges(t, g, e, f) { | ||
@@ -213,3 +194,2 @@ var v = e.v; | ||
} | ||
function updateRanks(t, g) { | ||
@@ -223,3 +203,2 @@ var root = t.nodes().find(v => !g.node(v).parent); | ||
flipped = false; | ||
if (!edge) { | ||
@@ -229,3 +208,2 @@ edge = g.edge(parent, v); | ||
} | ||
g.node(v).rank = g.node(parent).rank + (flipped ? edge.minlen : -edge.minlen); | ||
@@ -249,1 +227,2 @@ }); | ||
} | ||
module.exports = exports.default; |
"use strict"; | ||
module.exports = { | ||
longestPath: longestPath, | ||
slack: slack | ||
}; | ||
/* | ||
@@ -29,5 +24,9 @@ * 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) { | ||
@@ -39,3 +38,2 @@ var label = g.node(v); | ||
visited[v] = true; | ||
var rank = Math.min(...g.outEdges(v).map(e => { | ||
@@ -45,13 +43,9 @@ 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); | ||
@@ -58,0 +52,0 @@ } |
@@ -5,26 +5,25 @@ /* eslint "no-console": off */ | ||
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, | ||
}; | ||
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"); | ||
/* | ||
@@ -38,3 +37,2 @@ * Adds a dummy node to the graph and return v. | ||
} while (g.hasNode(v)); | ||
attrs.dummy = type; | ||
@@ -50,6 +48,9 @@ g.setNode(v, attrs); | ||
function simplify(g) { | ||
let simplified = new Graph().setGraph(g.graph()); | ||
let simplified = new _graphlib.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); | ||
@@ -63,5 +64,6 @@ simplified.setEdge(e.v, e.w, { | ||
} | ||
function asNonCompoundGraph(g) { | ||
let simplified = new Graph({ multigraph: g.isMultigraph() }).setGraph(g.graph()); | ||
let simplified = new _graphlib.Graph({ | ||
multigraph: g.isMultigraph() | ||
}).setGraph(g.graph()); | ||
g.nodes().forEach(v => { | ||
@@ -77,3 +79,2 @@ if (!g.children(v).length) { | ||
} | ||
function successorWeights(g) { | ||
@@ -89,3 +90,2 @@ let weightMap = g.nodes().map(v => { | ||
} | ||
function predecessorWeights(g) { | ||
@@ -116,7 +116,5 @@ 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; | ||
@@ -138,4 +136,6 @@ if (Math.abs(dy) * w > Math.abs(dx) * h) { | ||
} | ||
return { x: x + sx, y: y + sy }; | ||
return { | ||
x: x + sx, | ||
y: y + sy | ||
}; | ||
} | ||
@@ -169,3 +169,2 @@ | ||
} | ||
return rank; | ||
@@ -180,7 +179,5 @@ })); | ||
} | ||
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 = []; | ||
@@ -194,3 +191,2 @@ g.nodes().forEach(v => { | ||
}); | ||
let delta = 0; | ||
@@ -206,3 +202,2 @@ let nodeRankFactor = g.graph().nodeRankFactor; | ||
} | ||
function addBorderNode(g, prefix, rank, order) { | ||
@@ -219,3 +214,2 @@ let node = { | ||
} | ||
function maxRank(g) { | ||
@@ -227,3 +221,2 @@ return Math.max(...g.nodes().map(v => { | ||
} | ||
return rank; | ||
@@ -239,3 +232,6 @@ })); | ||
function partition(collection, fn) { | ||
let result = { lhs: [], rhs: [] }; | ||
let result = { | ||
lhs: [], | ||
rhs: [] | ||
}; | ||
collection.forEach(value => { | ||
@@ -263,7 +259,5 @@ if (fn(value)) { | ||
} | ||
function notime(name, fn) { | ||
return fn(); | ||
} | ||
let idCounter = 0; | ||
@@ -274,3 +268,2 @@ function uniqueId(prefix) { | ||
} | ||
function range(start, limit, step = 1) { | ||
@@ -281,8 +274,6 @@ 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 = []; | ||
@@ -292,6 +283,4 @@ for (let i = start; endCon(i); i += step) { | ||
} | ||
return range; | ||
} | ||
function pick(source, keys) { | ||
@@ -304,12 +293,9 @@ 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]) => { | ||
@@ -320,3 +306,2 @@ acc[k] = func(v, k); | ||
} | ||
function zipObject(props, values) { | ||
@@ -323,0 +308,0 @@ return props.reduce((acc, key, i) => { |
@@ -1,1 +0,8 @@ | ||
module.exports = "1.0.4"; | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = void 0; | ||
var _default = exports.default = "1.1.0"; | ||
module.exports = exports.default; |
{ | ||
"name": "@dagrejs/dagre", | ||
"version": "1.0.4", | ||
"version": "1.1.0", | ||
"description": "Graph layout for JavaScript", | ||
@@ -15,2 +15,7 @@ "author": "Chris Pettitt <cpettitt@gmail.com>", | ||
}, | ||
"module": "./mjs-lib/index.js", | ||
"exports": { | ||
"import": "./mjs-lib/index.js", | ||
"require": "./index.js" | ||
}, | ||
"files": [ | ||
@@ -20,3 +25,4 @@ "index.js", | ||
"dist/", | ||
"lib/" | ||
"lib/", | ||
"mjs-lib/" | ||
], | ||
@@ -29,5 +35,10 @@ "types": "index.d.ts", | ||
"dependencies": { | ||
"@dagrejs/graphlib": "2.1.13" | ||
"@dagrejs/graphlib": "2.2.0" | ||
}, | ||
"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", | ||
@@ -34,0 +45,0 @@ "browserify": "17.0.0", |
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
388881
63
10138
23
+ Added@dagrejs/graphlib@2.2.0(transitive)
- Removed@dagrejs/graphlib@2.1.13(transitive)
Updated@dagrejs/graphlib@2.2.0