@dagrejs/dagre
Advanced tools
Comparing version 0.8.0 to 1.0.0
@@ -24,3 +24,3 @@ /* | ||
module.exports = { | ||
graphlib: require("./lib/graphlib"), | ||
graphlib: require("@dagrejs/graphlib"), | ||
@@ -27,0 +27,0 @@ layout: require("./lib/layout"), |
"use strict"; | ||
var _ = require("./lodash"), | ||
greedyFAS = require("./greedy-fas"); | ||
var greedyFAS = require("./greedy-fas"); | ||
var uniqueId = require("./util").uniqueId; | ||
@@ -13,5 +13,5 @@ module.exports = { | ||
var fas = (g.graph().acyclicer === "greedy" | ||
? greedyFAS(g, weightFn(g)) | ||
: dfsFAS(g)); | ||
_.forEach(fas, function(e) { | ||
? greedyFAS(g, weightFn(g)) | ||
: dfsFAS(g)); | ||
fas.forEach(function(e) { | ||
var label = g.edge(e); | ||
@@ -21,3 +21,3 @@ g.removeEdge(e); | ||
label.reversed = true; | ||
g.setEdge(e.w, e.v, label, _.uniqueId("rev")); | ||
g.setEdge(e.w, e.v, label, uniqueId("rev")); | ||
}); | ||
@@ -33,8 +33,8 @@ | ||
function dfsFAS(g) { | ||
var fas = [], | ||
stack = {}, | ||
visited = {}; | ||
var fas = []; | ||
var stack = {}; | ||
var visited = {}; | ||
function dfs(v) { | ||
if (_.has(visited, v)) { | ||
if (visited.hasOwnProperty(v)) { | ||
return; | ||
@@ -44,4 +44,4 @@ } | ||
stack[v] = true; | ||
_.forEach(g.outEdges(v), function(e) { | ||
if (_.has(stack, e.w)) { | ||
g.outEdges(v).forEach(function(e) { | ||
if (stack.hasOwnProperty(e.w)) { | ||
fas.push(e); | ||
@@ -55,3 +55,3 @@ } else { | ||
_.forEach(g.nodes(), dfs); | ||
g.nodes().forEach(dfs); | ||
return fas; | ||
@@ -61,3 +61,3 @@ } | ||
function undo(g) { | ||
_.forEach(g.edges(), function(e) { | ||
g.edges().forEach(function(e) { | ||
var label = g.edge(e); | ||
@@ -64,0 +64,0 @@ if (label.reversed) { |
@@ -1,3 +0,2 @@ | ||
var _ = require("./lodash"), | ||
util = require("./util"); | ||
var util = require("./util"); | ||
@@ -8,14 +7,14 @@ module.exports = addBorderSegments; | ||
function dfs(v) { | ||
var children = g.children(v), | ||
node = g.node(v); | ||
var children = g.children(v); | ||
var node = g.node(v); | ||
if (children.length) { | ||
_.forEach(children, dfs); | ||
children.forEach(dfs); | ||
} | ||
if (_.has(node, "minRank")) { | ||
if (node.hasOwnProperty("minRank")) { | ||
node.borderLeft = []; | ||
node.borderRight = []; | ||
for (var rank = node.minRank, maxRank = node.maxRank + 1; | ||
rank < maxRank; | ||
++rank) { | ||
rank < maxRank; | ||
++rank) { | ||
addBorderNode(g, "borderLeft", "_bl", v, node, rank); | ||
@@ -27,9 +26,9 @@ addBorderNode(g, "borderRight", "_br", v, node, rank); | ||
_.forEach(g.children(), dfs); | ||
g.children().forEach(dfs); | ||
} | ||
function addBorderNode(g, prop, prefix, sg, sgNode, rank) { | ||
var label = { width: 0, height: 0, rank: rank, borderType: prop }, | ||
prev = sgNode[prop][rank - 1], | ||
curr = util.addDummyNode(g, "border", label, prefix); | ||
var label = { width: 0, height: 0, rank: rank, borderType: prop }; | ||
var prev = sgNode[prop][rank - 1]; | ||
var curr = util.addDummyNode(g, "border", label, prefix); | ||
sgNode[prop][rank] = curr; | ||
@@ -36,0 +35,0 @@ g.setParent(curr, sg); |
"use strict"; | ||
var _ = require("./lodash"); | ||
module.exports = { | ||
@@ -30,4 +28,4 @@ adjust: adjust, | ||
function swapWidthHeight(g) { | ||
_.forEach(g.nodes(), function(v) { swapWidthHeightOne(g.node(v)); }); | ||
_.forEach(g.edges(), function(e) { swapWidthHeightOne(g.edge(e)); }); | ||
g.nodes().forEach(v => swapWidthHeightOne(g.node(v))); | ||
g.edges().forEach(e => swapWidthHeightOne(g.edge(e))); | ||
} | ||
@@ -42,8 +40,8 @@ | ||
function reverseY(g) { | ||
_.forEach(g.nodes(), function(v) { reverseYOne(g.node(v)); }); | ||
g.nodes().forEach(v => reverseYOne(g.node(v))); | ||
_.forEach(g.edges(), function(e) { | ||
g.edges().forEach(function(e) { | ||
var edge = g.edge(e); | ||
_.forEach(edge.points, reverseYOne); | ||
if (_.has(edge, "y")) { | ||
edge.points.forEach(reverseYOne); | ||
if (edge.hasOwnProperty("y")) { | ||
reverseYOne(edge); | ||
@@ -59,8 +57,8 @@ } | ||
function swapXY(g) { | ||
_.forEach(g.nodes(), function(v) { swapXYOne(g.node(v)); }); | ||
g.nodes().forEach(v => swapXYOne(g.node(v))); | ||
_.forEach(g.edges(), function(e) { | ||
g.edges().forEach(function(e) { | ||
var edge = g.edge(e); | ||
_.forEach(edge.points, swapXYOne); | ||
if (_.has(edge, "x")) { | ||
edge.points.forEach(swapXYOne); | ||
if (edge.hasOwnProperty("x")) { | ||
swapXYOne(edge); | ||
@@ -67,0 +65,0 @@ } |
@@ -15,4 +15,4 @@ /* | ||
List.prototype.dequeue = function() { | ||
var sentinel = this._sentinel, | ||
entry = sentinel._prev; | ||
var sentinel = this._sentinel; | ||
var entry = sentinel._prev; | ||
if (entry !== sentinel) { | ||
@@ -36,5 +36,5 @@ unlink(entry); | ||
List.prototype.toString = function() { | ||
var strs = [], | ||
sentinel = this._sentinel, | ||
curr = sentinel._prev; | ||
var strs = []; | ||
var sentinel = this._sentinel; | ||
var curr = sentinel._prev; | ||
while (curr !== sentinel) { | ||
@@ -41,0 +41,0 @@ strs.push(JSON.stringify(curr, filterOutLinks)); |
@@ -1,4 +0,3 @@ | ||
var _ = require("./lodash"), | ||
util = require("./util"), | ||
Graph = require("./graphlib").Graph; | ||
var util = require("./util"); | ||
var Graph = require("@dagrejs/graphlib").Graph; | ||
@@ -15,3 +14,3 @@ module.exports = { | ||
_.forEach(g.nodes(), function(v) { | ||
g.nodes().forEach(function(v) { | ||
h.setNode(v, { label: v }); | ||
@@ -21,10 +20,10 @@ h.setParent(v, "layer" + g.node(v).rank); | ||
_.forEach(g.edges(), function(e) { | ||
g.edges().forEach(function(e) { | ||
h.setEdge(e.v, e.w, {}, e.name); | ||
}); | ||
_.forEach(layerMatrix, function(layer, i) { | ||
layerMatrix.forEach(function(layer, i) { | ||
var layerV = "layer" + i; | ||
h.setNode(layerV, { rank: "same" }); | ||
_.reduce(layer, function(u, v) { | ||
layer.reduce(function(u, v) { | ||
h.setEdge(u, v, { style: "invis" }); | ||
@@ -31,0 +30,0 @@ return v; |
@@ -1,4 +0,3 @@ | ||
var _ = require("./lodash"), | ||
Graph = require("./graphlib").Graph, | ||
List = require("./data/list"); | ||
var Graph = require("@dagrejs/graphlib").Graph; | ||
var List = require("./data/list"); | ||
@@ -14,3 +13,3 @@ /* | ||
var DEFAULT_WEIGHT_FN = _.constant(1); | ||
var DEFAULT_WEIGHT_FN = () => 1; | ||
@@ -25,11 +24,9 @@ function greedyFAS(g, weightFn) { | ||
// Expand multi-edges | ||
return _.flatten(_.map(results, function(e) { | ||
return g.outEdges(e.v, e.w); | ||
}), true); | ||
return results.flatMap(e => g.outEdges(e.v, e.w)); | ||
} | ||
function doGreedyFAS(g, buckets, zeroIdx) { | ||
var results = [], | ||
sources = buckets[buckets.length - 1], | ||
sinks = buckets[0]; | ||
var results = []; | ||
var sources = buckets[buckets.length - 1]; | ||
var sinks = buckets[0]; | ||
@@ -57,5 +54,5 @@ var entry; | ||
_.forEach(g.inEdges(entry.v), function(edge) { | ||
var weight = g.edge(edge), | ||
uEntry = g.node(edge.v); | ||
g.inEdges(entry.v).forEach(function(edge) { | ||
var weight = g.edge(edge); | ||
var uEntry = g.node(edge.v); | ||
@@ -70,6 +67,6 @@ if (collectPredecessors) { | ||
_.forEach(g.outEdges(entry.v), function(edge) { | ||
var weight = g.edge(edge), | ||
w = edge.w, | ||
wEntry = g.node(w); | ||
g.outEdges(entry.v).forEach(function(edge) { | ||
var weight = g.edge(edge); | ||
var w = edge.w; | ||
var wEntry = g.node(w); | ||
wEntry["in"] -= weight; | ||
@@ -85,7 +82,7 @@ assignBucket(buckets, zeroIdx, wEntry); | ||
function buildState(g, weightFn) { | ||
var fasGraph = new Graph(), | ||
maxIn = 0, | ||
maxOut = 0; | ||
var fasGraph = new Graph(); | ||
var maxIn = 0; | ||
var maxOut = 0; | ||
_.forEach(g.nodes(), function(v) { | ||
g.nodes().forEach(function(v) { | ||
fasGraph.setNode(v, { v: v, "in": 0, out: 0 }); | ||
@@ -96,6 +93,6 @@ }); | ||
// into a single edge for the fasGraph. | ||
_.forEach(g.edges(), function(e) { | ||
var prevWeight = fasGraph.edge(e.v, e.w) || 0, | ||
weight = weightFn(e), | ||
edgeWeight = prevWeight + weight; | ||
g.edges().forEach(function(e) { | ||
var prevWeight = fasGraph.edge(e.v, e.w) || 0; | ||
var weight = weightFn(e); | ||
var edgeWeight = prevWeight + weight; | ||
fasGraph.setEdge(e.v, e.w, edgeWeight); | ||
@@ -106,6 +103,6 @@ maxOut = Math.max(maxOut, fasGraph.node(e.v).out += weight); | ||
var buckets = _.range(maxOut + maxIn + 3).map(function() { return new List(); }); | ||
var buckets = range(maxOut + maxIn + 3).map(() => new List()); | ||
var zeroIdx = maxIn + 1; | ||
_.forEach(fasGraph.nodes(), function(v) { | ||
fasGraph.nodes().forEach(function(v) { | ||
assignBucket(buckets, zeroIdx, fasGraph.node(v)); | ||
@@ -126,1 +123,10 @@ }); | ||
} | ||
function range(limit) { | ||
const range = []; | ||
for (let i = 0; i < limit; i++) { | ||
range.push(i); | ||
} | ||
return range; | ||
} |
"use strict"; | ||
var _ = require("./lodash"), | ||
acyclic = require("./acyclic"), | ||
normalize = require("./normalize"), | ||
rank = require("./rank"), | ||
normalizeRanks = require("./util").normalizeRanks, | ||
parentDummyChains = require("./parent-dummy-chains"), | ||
removeEmptyRanks = require("./util").removeEmptyRanks, | ||
nestingGraph = require("./nesting-graph"), | ||
addBorderSegments = require("./add-border-segments"), | ||
coordinateSystem = require("./coordinate-system"), | ||
order = require("./order"), | ||
position = require("./position"), | ||
util = require("./util"), | ||
Graph = require("./graphlib").Graph; | ||
var acyclic = require("./acyclic"); | ||
var normalize = require("./normalize"); | ||
var rank = require("./rank"); | ||
var normalizeRanks = require("./util").normalizeRanks; | ||
var parentDummyChains = require("./parent-dummy-chains"); | ||
var removeEmptyRanks = require("./util").removeEmptyRanks; | ||
var nestingGraph = require("./nesting-graph"); | ||
var addBorderSegments = require("./add-border-segments"); | ||
var coordinateSystem = require("./coordinate-system"); | ||
var order = require("./order"); | ||
var position = require("./position"); | ||
var util = require("./util"); | ||
var Graph = require("@dagrejs/graphlib").Graph; | ||
@@ -23,4 +22,4 @@ module.exports = layout; | ||
time("layout", function() { | ||
var layoutGraph = time(" buildLayoutGraph", | ||
function() { return buildLayoutGraph(g); }); | ||
var layoutGraph = | ||
time(" buildLayoutGraph", function() { return buildLayoutGraph(g); }); | ||
time(" runLayout", function() { runLayout(layoutGraph, time); }); | ||
@@ -68,5 +67,5 @@ time(" updateInputGraph", function() { updateInputGraph(g, layoutGraph); }); | ||
function updateInputGraph(inputGraph, layoutGraph) { | ||
_.forEach(inputGraph.nodes(), function(v) { | ||
var inputLabel = inputGraph.node(v), | ||
layoutLabel = layoutGraph.node(v); | ||
inputGraph.nodes().forEach(v => { | ||
var inputLabel = inputGraph.node(v); | ||
var layoutLabel = layoutGraph.node(v); | ||
@@ -76,2 +75,3 @@ if (inputLabel) { | ||
inputLabel.y = layoutLabel.y; | ||
inputLabel.rank = layoutLabel.rank; | ||
@@ -85,8 +85,8 @@ if (layoutGraph.children(v).length) { | ||
_.forEach(inputGraph.edges(), function(e) { | ||
var inputLabel = inputGraph.edge(e), | ||
layoutLabel = layoutGraph.edge(e); | ||
inputGraph.edges().forEach(e => { | ||
var inputLabel = inputGraph.edge(e); | ||
var layoutLabel = layoutGraph.edge(e); | ||
inputLabel.points = layoutLabel.points; | ||
if (_.has(layoutLabel, "x")) { | ||
if (layoutLabel.hasOwnProperty("x")) { | ||
inputLabel.x = layoutLabel.x; | ||
@@ -101,13 +101,13 @@ inputLabel.y = layoutLabel.y; | ||
var graphNumAttrs = ["nodesep", "edgesep", "ranksep", "marginx", "marginy"], | ||
graphDefaults = { ranksep: 50, edgesep: 20, nodesep: 50, rankdir: "tb" }, | ||
graphAttrs = ["acyclicer", "ranker", "rankdir", "align"], | ||
nodeNumAttrs = ["width", "height"], | ||
nodeDefaults = { width: 0, height: 0 }, | ||
edgeNumAttrs = ["minlen", "weight", "width", "height", "labeloffset"], | ||
edgeDefaults = { | ||
minlen: 1, weight: 1, width: 0, height: 0, | ||
labeloffset: 10, labelpos: "r" | ||
}, | ||
edgeAttrs = ["labelpos"]; | ||
var graphNumAttrs = ["nodesep", "edgesep", "ranksep", "marginx", "marginy"]; | ||
var graphDefaults = { ranksep: 50, edgesep: 20, nodesep: 50, rankdir: "tb" }; | ||
var graphAttrs = ["acyclicer", "ranker", "rankdir", "align"]; | ||
var nodeNumAttrs = ["width", "height"]; | ||
var nodeDefaults = { width: 0, height: 0 }; | ||
var edgeNumAttrs = ["minlen", "weight", "width", "height", "labeloffset"]; | ||
var edgeDefaults = { | ||
minlen: 1, weight: 1, width: 0, height: 0, | ||
labeloffset: 10, labelpos: "r" | ||
}; | ||
var edgeAttrs = ["labelpos"]; | ||
@@ -121,22 +121,29 @@ /* | ||
function buildLayoutGraph(inputGraph) { | ||
var g = new Graph({ multigraph: true, compound: true }), | ||
graph = canonicalize(inputGraph.graph()); | ||
var g = new Graph({ multigraph: true, compound: true }); | ||
var graph = canonicalize(inputGraph.graph()); | ||
g.setGraph(_.merge({}, | ||
g.setGraph(Object.assign({}, | ||
graphDefaults, | ||
selectNumberAttrs(graph, graphNumAttrs), | ||
_.pick(graph, graphAttrs))); | ||
util.pick(graph, graphAttrs))); | ||
_.forEach(inputGraph.nodes(), function(v) { | ||
inputGraph.nodes().forEach(v => { | ||
var node = canonicalize(inputGraph.node(v)); | ||
g.setNode(v, _.defaults(selectNumberAttrs(node, nodeNumAttrs), nodeDefaults)); | ||
const newNode = selectNumberAttrs(node, nodeNumAttrs); | ||
Object.keys(nodeDefaults).forEach(k => { | ||
if (newNode[k] === undefined) { | ||
newNode[k] = nodeDefaults[k]; | ||
} | ||
}); | ||
g.setNode(v, newNode); | ||
g.setParent(v, inputGraph.parent(v)); | ||
}); | ||
_.forEach(inputGraph.edges(), function(e) { | ||
inputGraph.edges().forEach(e => { | ||
var edge = canonicalize(inputGraph.edge(e)); | ||
g.setEdge(e, _.merge({}, | ||
g.setEdge(e, Object.assign({}, | ||
edgeDefaults, | ||
selectNumberAttrs(edge, edgeNumAttrs), | ||
_.pick(edge, edgeAttrs))); | ||
util.pick(edge, edgeAttrs))); | ||
}); | ||
@@ -158,3 +165,3 @@ | ||
graph.ranksep /= 2; | ||
_.forEach(g.edges(), function(e) { | ||
g.edges().forEach(e => { | ||
var edge = g.edge(e); | ||
@@ -179,8 +186,8 @@ edge.minlen *= 2; | ||
function injectEdgeLabelProxies(g) { | ||
_.forEach(g.edges(), function(e) { | ||
g.edges().forEach(e => { | ||
var edge = g.edge(e); | ||
if (edge.width && edge.height) { | ||
var v = g.node(e.v), | ||
w = g.node(e.w), | ||
label = { rank: (w.rank - v.rank) / 2 + v.rank, e: e }; | ||
var v = g.node(e.v); | ||
var w = g.node(e.w); | ||
var label = { rank: (w.rank - v.rank) / 2 + v.rank, e: e }; | ||
util.addDummyNode(g, "edge-proxy", label, "_ep"); | ||
@@ -193,3 +200,3 @@ } | ||
var maxRank = 0; | ||
_.forEach(g.nodes(), function(v) { | ||
g.nodes().forEach(v => { | ||
var node = g.node(v); | ||
@@ -199,3 +206,3 @@ if (node.borderTop) { | ||
node.maxRank = g.node(node.borderBottom).rank; | ||
maxRank = _.max(maxRank, node.maxRank); | ||
maxRank = Math.max(maxRank, node.maxRank); | ||
} | ||
@@ -207,3 +214,3 @@ }); | ||
function removeEdgeLabelProxies(g) { | ||
_.forEach(g.nodes(), function(v) { | ||
g.nodes().forEach(v => { | ||
var node = g.node(v); | ||
@@ -218,15 +225,15 @@ if (node.dummy === "edge-proxy") { | ||
function translateGraph(g) { | ||
var minX = Number.POSITIVE_INFINITY, | ||
maxX = 0, | ||
minY = Number.POSITIVE_INFINITY, | ||
maxY = 0, | ||
graphLabel = g.graph(), | ||
marginX = graphLabel.marginx || 0, | ||
marginY = graphLabel.marginy || 0; | ||
var minX = Number.POSITIVE_INFINITY; | ||
var maxX = 0; | ||
var minY = Number.POSITIVE_INFINITY; | ||
var maxY = 0; | ||
var graphLabel = g.graph(); | ||
var marginX = graphLabel.marginx || 0; | ||
var marginY = graphLabel.marginy || 0; | ||
function getExtremes(attrs) { | ||
var x = attrs.x, | ||
y = attrs.y, | ||
w = attrs.width, | ||
h = attrs.height; | ||
var x = attrs.x; | ||
var y = attrs.y; | ||
var w = attrs.width; | ||
var h = attrs.height; | ||
minX = Math.min(minX, x - w / 2); | ||
@@ -238,6 +245,6 @@ maxX = Math.max(maxX, x + w / 2); | ||
_.forEach(g.nodes(), function(v) { getExtremes(g.node(v)); }); | ||
_.forEach(g.edges(), function(e) { | ||
g.nodes().forEach(v => getExtremes(g.node(v))); | ||
g.edges().forEach(e => { | ||
var edge = g.edge(e); | ||
if (_.has(edge, "x")) { | ||
if (edge.hasOwnProperty("x")) { | ||
getExtremes(edge); | ||
@@ -250,3 +257,3 @@ } | ||
_.forEach(g.nodes(), function(v) { | ||
g.nodes().forEach(v => { | ||
var node = g.node(v); | ||
@@ -257,10 +264,10 @@ node.x -= minX; | ||
_.forEach(g.edges(), function(e) { | ||
g.edges().forEach(e => { | ||
var edge = g.edge(e); | ||
_.forEach(edge.points, function(p) { | ||
edge.points.forEach(p => { | ||
p.x -= minX; | ||
p.y -= minY; | ||
}); | ||
if (_.has(edge, "x")) { edge.x -= minX; } | ||
if (_.has(edge, "y")) { edge.y -= minY; } | ||
if (edge.hasOwnProperty("x")) { edge.x -= minX; } | ||
if (edge.hasOwnProperty("y")) { edge.y -= minY; } | ||
}); | ||
@@ -273,7 +280,7 @@ | ||
function assignNodeIntersects(g) { | ||
_.forEach(g.edges(), function(e) { | ||
var edge = g.edge(e), | ||
nodeV = g.node(e.v), | ||
nodeW = g.node(e.w), | ||
p1, p2; | ||
g.edges().forEach(e => { | ||
var edge = g.edge(e); | ||
var nodeV = g.node(e.v); | ||
var nodeW = g.node(e.w); | ||
var p1, p2; | ||
if (!edge.points) { | ||
@@ -293,5 +300,5 @@ edge.points = []; | ||
function fixupEdgeLabelCoords(g) { | ||
_.forEach(g.edges(), function(e) { | ||
g.edges().forEach(e => { | ||
var edge = g.edge(e); | ||
if (_.has(edge, "x")) { | ||
if (edge.hasOwnProperty("x")) { | ||
if (edge.labelpos === "l" || edge.labelpos === "r") { | ||
@@ -301,4 +308,4 @@ edge.width -= edge.labeloffset; | ||
switch (edge.labelpos) { | ||
case "l": edge.x -= edge.width / 2 + edge.labeloffset; break; | ||
case "r": edge.x += edge.width / 2 + edge.labeloffset; break; | ||
case "l": edge.x -= edge.width / 2 + edge.labeloffset; break; | ||
case "r": edge.x += edge.width / 2 + edge.labeloffset; break; | ||
} | ||
@@ -310,3 +317,3 @@ } | ||
function reversePointsForReversedEdges(g) { | ||
_.forEach(g.edges(), function(e) { | ||
g.edges().forEach(e => { | ||
var edge = g.edge(e); | ||
@@ -320,9 +327,9 @@ if (edge.reversed) { | ||
function removeBorderNodes(g) { | ||
_.forEach(g.nodes(), function(v) { | ||
g.nodes().forEach(v => { | ||
if (g.children(v).length) { | ||
var node = g.node(v), | ||
t = g.node(node.borderTop), | ||
b = g.node(node.borderBottom), | ||
l = g.node(_.last(node.borderLeft)), | ||
r = g.node(_.last(node.borderRight)); | ||
var node = g.node(v); | ||
var t = g.node(node.borderTop); | ||
var b = g.node(node.borderBottom); | ||
var l = g.node(node.borderLeft[node.borderLeft.length - 1]); | ||
var r = g.node(node.borderRight[node.borderRight.length - 1]); | ||
@@ -336,3 +343,3 @@ node.width = Math.abs(r.x - l.x); | ||
_.forEach(g.nodes(), function(v) { | ||
g.nodes().forEach(v => { | ||
if (g.node(v).dummy === "border") { | ||
@@ -345,3 +352,3 @@ g.removeNode(v); | ||
function removeSelfEdges(g) { | ||
_.forEach(g.edges(), function(e) { | ||
g.edges().forEach(e => { | ||
if (e.v === e.w) { | ||
@@ -360,8 +367,8 @@ var node = g.node(e.v); | ||
var layers = util.buildLayerMatrix(g); | ||
_.forEach(layers, function(layer) { | ||
layers.forEach(layer => { | ||
var orderShift = 0; | ||
_.forEach(layer, function(v, i) { | ||
layer.forEach((v, i) => { | ||
var node = g.node(v); | ||
node.order = i + orderShift; | ||
_.forEach(node.selfEdges, function(selfEdge) { | ||
(node.selfEdges || []).forEach(selfEdge => { | ||
util.addDummyNode(g, "selfedge", { | ||
@@ -382,10 +389,10 @@ width: selfEdge.label.width, | ||
function positionSelfEdges(g) { | ||
_.forEach(g.nodes(), function(v) { | ||
g.nodes().forEach(v => { | ||
var node = g.node(v); | ||
if (node.dummy === "selfedge") { | ||
var selfNode = g.node(node.e.v), | ||
x = selfNode.x + selfNode.width / 2, | ||
y = selfNode.y, | ||
dx = node.x - x, | ||
dy = selfNode.height / 2; | ||
var selfNode = g.node(node.e.v); | ||
var x = selfNode.x + selfNode.width / 2; | ||
var y = selfNode.y; | ||
var dx = node.x - x; | ||
var dy = selfNode.height / 2; | ||
g.setEdge(node.e, node.label); | ||
@@ -407,3 +414,3 @@ g.removeNode(v); | ||
function selectNumberAttrs(obj, attrs) { | ||
return _.mapValues(_.pick(obj, attrs), Number); | ||
return util.mapValues(util.pick(obj, attrs), Number); | ||
} | ||
@@ -413,6 +420,12 @@ | ||
var newAttrs = {}; | ||
_.forEach(attrs, function(v, k) { | ||
newAttrs[k.toLowerCase()] = v; | ||
}); | ||
if (attrs) { | ||
Object.entries(attrs).forEach(([k, v]) => { | ||
if (typeof k === "string") { | ||
k = k.toLowerCase(); | ||
} | ||
newAttrs[k] = v; | ||
}); | ||
} | ||
return newAttrs; | ||
} |
@@ -1,3 +0,2 @@ | ||
var _ = require("./lodash"), | ||
util = require("./util"); | ||
var util = require("./util"); | ||
@@ -35,3 +34,3 @@ module.exports = { | ||
var depths = treeDepths(g); | ||
var height = _.max(_.values(depths)) - 1; // Note: depths is an Object not an array | ||
var height = Math.max(...Object.values(depths)) - 1; // Note: depths is an Object not an array | ||
var nodeSep = 2 * height + 1; | ||
@@ -42,3 +41,3 @@ | ||
// Multiply minlen by nodeSep to align nodes on non-border ranks. | ||
_.forEach(g.edges(), function(e) { g.edge(e).minlen *= nodeSep; }); | ||
g.edges().forEach(e => g.edge(e).minlen *= nodeSep); | ||
@@ -49,3 +48,3 @@ // Calculate a weight that is sufficient to keep subgraphs vertically compact | ||
// Create border nodes and link them up | ||
_.forEach(g.children(), function(child) { | ||
g.children().forEach(function(child) { | ||
dfs(g, root, nodeSep, weight, height, depths, child); | ||
@@ -68,5 +67,5 @@ }); | ||
var top = util.addBorderNode(g, "_bt"), | ||
bottom = util.addBorderNode(g, "_bb"), | ||
label = g.node(v); | ||
var top = util.addBorderNode(g, "_bt"); | ||
var bottom = util.addBorderNode(g, "_bb"); | ||
var label = g.node(v); | ||
@@ -78,10 +77,10 @@ g.setParent(top, v); | ||
_.forEach(children, function(child) { | ||
children.forEach(function(child) { | ||
dfs(g, root, nodeSep, weight, height, depths, child); | ||
var childNode = g.node(child), | ||
childTop = childNode.borderTop ? childNode.borderTop : child, | ||
childBottom = childNode.borderBottom ? childNode.borderBottom : child, | ||
thisWeight = childNode.borderTop ? weight : 2 * weight, | ||
minlen = childTop !== childBottom ? 1 : height - depths[v] + 1; | ||
var childNode = g.node(child); | ||
var childTop = childNode.borderTop ? childNode.borderTop : child; | ||
var childBottom = childNode.borderBottom ? childNode.borderBottom : child; | ||
var thisWeight = childNode.borderTop ? weight : 2 * weight; | ||
var minlen = childTop !== childBottom ? 1 : height - depths[v] + 1; | ||
@@ -111,9 +110,7 @@ g.setEdge(top, childTop, { | ||
if (children && children.length) { | ||
_.forEach(children, function(child) { | ||
dfs(child, depth + 1); | ||
}); | ||
children.forEach(child => dfs(child, depth + 1)); | ||
} | ||
depths[v] = depth; | ||
} | ||
_.forEach(g.children(), function(v) { dfs(v, 1); }); | ||
g.children().forEach(v => dfs(v, 1)); | ||
return depths; | ||
@@ -123,5 +120,3 @@ } | ||
function sumWeights(g) { | ||
return _.reduce(g.edges(), function(acc, e) { | ||
return acc + g.edge(e).weight; | ||
}, 0); | ||
return g.edges().reduce((acc, e) => acc + g.edge(e).weight, 0); | ||
} | ||
@@ -133,3 +128,3 @@ | ||
delete graphLabel.nestingRoot; | ||
_.forEach(g.edges(), function(e) { | ||
g.edges().forEach(e => { | ||
var edge = g.edge(e); | ||
@@ -136,0 +131,0 @@ if (edge.nestingEdge) { |
"use strict"; | ||
var _ = require("./lodash"), | ||
util = require("./util"); | ||
var util = require("./util"); | ||
@@ -29,13 +28,13 @@ module.exports = { | ||
g.graph().dummyChains = []; | ||
_.forEach(g.edges(), function(edge) { normalizeEdge(g, edge); }); | ||
g.edges().forEach(edge => normalizeEdge(g, edge)); | ||
} | ||
function normalizeEdge(g, e) { | ||
var v = e.v, | ||
vRank = g.node(v).rank, | ||
w = e.w, | ||
wRank = g.node(w).rank, | ||
name = e.name, | ||
edgeLabel = g.edge(e), | ||
labelRank = edgeLabel.labelRank; | ||
var v = e.v; | ||
var vRank = g.node(v).rank; | ||
var w = e.w; | ||
var wRank = g.node(w).rank; | ||
var name = e.name; | ||
var edgeLabel = g.edge(e); | ||
var labelRank = edgeLabel.labelRank; | ||
@@ -72,6 +71,6 @@ if (wRank === vRank + 1) return; | ||
function undo(g) { | ||
_.forEach(g.graph().dummyChains, function(v) { | ||
var node = g.node(v), | ||
origLabel = node.edgeLabel, | ||
w; | ||
g.graph().dummyChains.forEach(function(v) { | ||
var node = g.node(v); | ||
var origLabel = node.edgeLabel; | ||
var w; | ||
g.setEdge(node.edgeObj, origLabel); | ||
@@ -78,0 +77,0 @@ while (node.dummy) { |
@@ -1,3 +0,1 @@ | ||
var _ = require("../lodash"); | ||
module.exports = addSubgraphConstraints; | ||
@@ -7,8 +5,8 @@ | ||
var prev = {}, | ||
rootPrev; | ||
rootPrev; | ||
_.forEach(vs, function(v) { | ||
vs.forEach(function(v) { | ||
var child = g.parent(v), | ||
parent, | ||
prevChild; | ||
parent, | ||
prevChild; | ||
while (child) { | ||
@@ -37,3 +35,3 @@ parent = g.parent(child); | ||
subgraphs = []; | ||
_.each(children, function(child) { | ||
children.forEach(function(child) { | ||
var childMin = dfs(child); | ||
@@ -45,3 +43,3 @@ if (g.children(child).length) { | ||
}); | ||
_.reduce(_.sortBy(subgraphs, "order"), function(prev, curr) { | ||
_.sortBy(subgraphs, "order").reduce(function(prev, curr) { | ||
cg.setEdge(prev.v, curr.v); | ||
@@ -48,0 +46,0 @@ return curr; |
@@ -1,7 +0,5 @@ | ||
var _ = require("../lodash"); | ||
module.exports = barycenter; | ||
function barycenter(g, movable) { | ||
return _.map(movable, function(v) { | ||
function barycenter(g, movable = []) { | ||
return movable.map(v => { | ||
var inV = g.inEdges(v); | ||
@@ -11,5 +9,5 @@ if (!inV.length) { | ||
} else { | ||
var result = _.reduce(inV, function(acc, e) { | ||
var result = inV.reduce((acc, e) => { | ||
var edge = g.edge(e), | ||
nodeU = g.node(e.v); | ||
nodeU = g.node(e.v); | ||
return { | ||
@@ -16,0 +14,0 @@ sum: acc.sum + (edge.weight * nodeU.order), |
@@ -1,3 +0,3 @@ | ||
var _ = require("../lodash"), | ||
Graph = require("../graphlib").Graph; | ||
var Graph = require("@dagrejs/graphlib").Graph; | ||
var util = require("../util"); | ||
@@ -38,8 +38,8 @@ module.exports = buildLayerGraph; | ||
var root = createRootNode(g), | ||
result = new Graph({ compound: true }).setGraph({ root: root }) | ||
.setDefaultNodeLabel(function(v) { return g.node(v); }); | ||
result = new Graph({ compound: true }).setGraph({ root: root }) | ||
.setDefaultNodeLabel(function(v) { return g.node(v); }); | ||
_.forEach(g.nodes(), function(v) { | ||
g.nodes().forEach(function(v) { | ||
var node = g.node(v), | ||
parent = g.parent(v); | ||
parent = g.parent(v); | ||
@@ -51,10 +51,10 @@ if (node.rank === rank || node.minRank <= rank && rank <= node.maxRank) { | ||
// This assumes we have only short edges! | ||
_.forEach(g[relationship](v), function(e) { | ||
g[relationship](v).forEach(function(e) { | ||
var u = e.v === v ? e.w : e.v, | ||
edge = result.edge(u, v), | ||
weight = !_.isUndefined(edge) ? edge.weight : 0; | ||
edge = result.edge(u, v), | ||
weight = edge !== undefined ? edge.weight : 0; | ||
result.setEdge(u, v, { weight: g.edge(e).weight + weight }); | ||
}); | ||
if (_.has(node, "minRank")) { | ||
if (node.hasOwnProperty("minRank")) { | ||
result.setNode(v, { | ||
@@ -73,4 +73,4 @@ borderLeft: node.borderLeft[rank], | ||
var v; | ||
while (g.hasNode((v = _.uniqueId("_root")))); | ||
while (g.hasNode((v = util.uniqueId("_root")))); | ||
return v; | ||
} |
"use strict"; | ||
var _ = require("../lodash"); | ||
var zipObject = require("../util").zipObject; | ||
@@ -35,12 +35,8 @@ module.exports = crossCount; | ||
// their head in the south layer. | ||
var southPos = _.zipObject(southLayer, | ||
_.map(southLayer, function (v, i) { return i; })); | ||
var southEntries = _.flatten(_.map(northLayer, function(v) { | ||
return _.chain(g.outEdges(v)) | ||
.map(function(e) { | ||
return { pos: southPos[e.w], weight: g.edge(e).weight }; | ||
}) | ||
.sortBy("pos") | ||
.value(); | ||
}), true); | ||
var southPos = zipObject(southLayer, southLayer.map((v, i) => i)); | ||
var southEntries = northLayer.flatMap(v => { | ||
return g.outEdges(v).map(e => { | ||
return { pos: southPos[e.w], weight: g.edge(e).weight }; | ||
}).sort((a, b) => a.pos - b.pos); | ||
}); | ||
@@ -52,7 +48,7 @@ // Build the accumulator tree | ||
firstIndex -= 1; | ||
var tree = _.map(new Array(treeSize), function() { return 0; }); | ||
var tree = new Array(treeSize).fill(0); | ||
// Calculate the weighted crossings | ||
var cc = 0; | ||
_.forEach(southEntries.forEach(function(entry) { | ||
southEntries.forEach(entry => { | ||
var index = entry.pos + firstIndex; | ||
@@ -69,5 +65,5 @@ tree[index] += entry.weight; | ||
cc += entry.weight * weightSum; | ||
})); | ||
}); | ||
return cc; | ||
} |
"use strict"; | ||
var _ = require("../lodash"), | ||
initOrder = require("./init-order"), | ||
crossCount = require("./cross-count"), | ||
sortSubgraph = require("./sort-subgraph"), | ||
buildLayerGraph = require("./build-layer-graph"), | ||
addSubgraphConstraints = require("./add-subgraph-constraints"), | ||
Graph = require("../graphlib").Graph, | ||
util = require("../util"); | ||
var initOrder = require("./init-order"); | ||
var crossCount = require("./cross-count"); | ||
var sortSubgraph = require("./sort-subgraph"); | ||
var buildLayerGraph = require("./build-layer-graph"); | ||
var addSubgraphConstraints = require("./add-subgraph-constraints"); | ||
var Graph = require("@dagrejs/graphlib").Graph; | ||
var util = require("../util"); | ||
@@ -31,4 +30,4 @@ module.exports = order; | ||
var maxRank = util.maxRank(g), | ||
downLayerGraphs = buildLayerGraphs(g, _.range(1, maxRank + 1), "inEdges"), | ||
upLayerGraphs = buildLayerGraphs(g, _.range(maxRank - 1, -1, -1), "outEdges"); | ||
downLayerGraphs = buildLayerGraphs(g, util.range(1, maxRank + 1), "inEdges"), | ||
upLayerGraphs = buildLayerGraphs(g, util.range(maxRank - 1, -1, -1), "outEdges"); | ||
@@ -39,3 +38,3 @@ var layering = initOrder(g); | ||
var bestCC = Number.POSITIVE_INFINITY, | ||
best; | ||
best; | ||
@@ -49,3 +48,3 @@ for (var i = 0, lastBest = 0; lastBest < 4; ++i, ++lastBest) { | ||
lastBest = 0; | ||
best = _.cloneDeep(layering); | ||
best = Object.assign({}, layering); | ||
bestCC = cc; | ||
@@ -59,3 +58,3 @@ } | ||
function buildLayerGraphs(g, ranks, relationship) { | ||
return _.map(ranks, function(rank) { | ||
return ranks.map(function(rank) { | ||
return buildLayerGraph(g, rank, relationship); | ||
@@ -67,8 +66,6 @@ }); | ||
var cg = new Graph(); | ||
_.forEach(layerGraphs, function(lg) { | ||
layerGraphs.forEach(function(lg) { | ||
var root = lg.graph().root; | ||
var sorted = sortSubgraph(lg, root, cg, biasRight); | ||
_.forEach(sorted.vs, function(v, i) { | ||
lg.node(v).order = i; | ||
}); | ||
sorted.vs.forEach((v, i) => lg.node(v).order = i); | ||
addSubgraphConstraints(lg, cg, sorted.vs); | ||
@@ -79,7 +76,3 @@ }); | ||
function assignOrder(g, layering) { | ||
_.forEach(layering, function(layer) { | ||
_.forEach(layer, function(v, i) { | ||
g.node(v).order = i; | ||
}); | ||
}); | ||
Object.values(layering).forEach(layer => layer.forEach((v, i) => g.node(v).order = i)); | ||
} |
"use strict"; | ||
var _ = require("../lodash"); | ||
var util = require("../util"); | ||
@@ -19,21 +19,19 @@ module.exports = initOrder; | ||
function initOrder(g) { | ||
var visited = {}, | ||
simpleNodes = _.filter(g.nodes(), function(v) { | ||
return !g.children(v).length; | ||
}), | ||
maxRank = _.max(_.map(simpleNodes, function(v) { return g.node(v).rank; })), | ||
layers = _.map(_.range(maxRank + 1), function() { return []; }); | ||
var visited = {}; | ||
var simpleNodes = g.nodes().filter(v => !g.children(v).length); | ||
var maxRank = Math.max(...simpleNodes.map(v => g.node(v).rank)); | ||
var layers = util.range(maxRank + 1).map(() => []); | ||
function dfs(v) { | ||
if (_.has(visited, v)) return; | ||
if (visited[v]) return; | ||
visited[v] = true; | ||
var node = g.node(v); | ||
layers[node.rank].push(v); | ||
_.forEach(g.successors(v), dfs); | ||
g.successors(v).forEach(dfs); | ||
} | ||
var orderedVs = _.sortBy(simpleNodes, function(v) { return g.node(v).rank; }); | ||
_.forEach(orderedVs, dfs); | ||
var orderedVs = simpleNodes.sort((a, b) => g.node(a).rank - g.node(b).rank); | ||
orderedVs.forEach(dfs); | ||
return layers; | ||
} |
"use strict"; | ||
var _ = require("../lodash"); | ||
var util = require("../util"); | ||
@@ -34,3 +34,3 @@ module.exports = resolveConflicts; | ||
var mappedEntries = {}; | ||
_.forEach(entries, function(entry, i) { | ||
entries.forEach((entry, i) => { | ||
var tmp = mappedEntries[entry.v] = { | ||
@@ -43,3 +43,3 @@ indegree: 0, | ||
}; | ||
if (!_.isUndefined(entry.barycenter)) { | ||
if (entry.barycenter !== undefined) { | ||
tmp.barycenter = entry.barycenter; | ||
@@ -50,6 +50,6 @@ tmp.weight = entry.weight; | ||
_.forEach(cg.edges(), function(e) { | ||
var entryV = mappedEntries[e.v], | ||
entryW = mappedEntries[e.w]; | ||
if (!_.isUndefined(entryV) && !_.isUndefined(entryW)) { | ||
cg.edges().forEach(e => { | ||
var entryV = mappedEntries[e.v]; | ||
var entryW = mappedEntries[e.w]; | ||
if (entryV !== undefined && entryW !== undefined) { | ||
entryW.indegree++; | ||
@@ -60,5 +60,3 @@ entryV.out.push(mappedEntries[e.w]); | ||
var sourceSet = _.filter(mappedEntries, function(entry) { | ||
return !entry.indegree; | ||
}); | ||
var sourceSet = Object.values(mappedEntries).filter(entry => !entry.indegree); | ||
@@ -76,4 +74,4 @@ return doResolveConflicts(sourceSet); | ||
} | ||
if (_.isUndefined(uEntry.barycenter) || | ||
_.isUndefined(vEntry.barycenter) || | ||
if (uEntry.barycenter === undefined || | ||
vEntry.barycenter === undefined || | ||
uEntry.barycenter >= vEntry.barycenter) { | ||
@@ -97,17 +95,14 @@ mergeEntries(vEntry, uEntry); | ||
entries.push(entry); | ||
_.forEach(entry["in"].reverse(), handleIn(entry)); | ||
_.forEach(entry.out, handleOut(entry)); | ||
entry["in"].reverse().forEach(handleIn(entry)); | ||
entry.out.forEach(handleOut(entry)); | ||
} | ||
return _.chain(entries) | ||
.filter(function(entry) { return !entry.merged; }) | ||
.map(function(entry) { | ||
return _.pick(entry, ["vs", "i", "barycenter", "weight"]); | ||
}) | ||
.value(); | ||
return entries.filter(entry => !entry.merged).map(entry => { | ||
return util.pick(entry, ["vs", "i", "barycenter", "weight"]); | ||
}); | ||
} | ||
function mergeEntries(target, source) { | ||
var sum = 0, | ||
weight = 0; | ||
var sum = 0; | ||
var weight = 0; | ||
@@ -114,0 +109,0 @@ if (target.weight) { |
@@ -1,5 +0,4 @@ | ||
var _ = require("../lodash"), | ||
barycenter = require("./barycenter"), | ||
resolveConflicts = require("./resolve-conflicts"), | ||
sort = require("./sort"); | ||
var barycenter = require("./barycenter"); | ||
var resolveConflicts = require("./resolve-conflicts"); | ||
var sort = require("./sort"); | ||
@@ -9,20 +8,18 @@ module.exports = sortSubgraph; | ||
function sortSubgraph(g, v, cg, biasRight) { | ||
var movable = g.children(v), | ||
node = g.node(v), | ||
bl = node ? node.borderLeft : undefined, | ||
br = node ? node.borderRight: undefined, | ||
subgraphs = {}; | ||
var movable = g.children(v); | ||
var node = g.node(v); | ||
var bl = node ? node.borderLeft : undefined; | ||
var br = node ? node.borderRight: undefined; | ||
var subgraphs = {}; | ||
if (bl) { | ||
movable = _.filter(movable, function(w) { | ||
return w !== bl && w !== br; | ||
}); | ||
movable = movable.filter(w => w !== bl && w !== br); | ||
} | ||
var barycenters = barycenter(g, movable); | ||
_.forEach(barycenters, function(entry) { | ||
barycenters.forEach(function(entry) { | ||
if (g.children(entry.v).length) { | ||
var subgraphResult = sortSubgraph(g, entry.v, cg, biasRight); | ||
subgraphs[entry.v] = subgraphResult; | ||
if (_.has(subgraphResult, "barycenter")) { | ||
if (subgraphResult.hasOwnProperty("barycenter")) { | ||
mergeBarycenters(entry, subgraphResult); | ||
@@ -39,7 +36,7 @@ } | ||
if (bl) { | ||
result.vs = _.flatten([bl, result.vs, br], true); | ||
result.vs = [bl, result.vs, br].flat(true); | ||
if (g.predecessors(bl).length) { | ||
var blPred = g.node(g.predecessors(bl)[0]), | ||
brPred = g.node(g.predecessors(br)[0]); | ||
if (!_.has(result, "barycenter")) { | ||
brPred = g.node(g.predecessors(br)[0]); | ||
if (!result.hasOwnProperty("barycenter")) { | ||
result.barycenter = 0; | ||
@@ -58,4 +55,4 @@ result.weight = 0; | ||
function expandSubgraphs(entries, subgraphs) { | ||
_.forEach(entries, function(entry) { | ||
entry.vs = _.flatten(entry.vs.map(function(v) { | ||
entries.forEach(function(entry) { | ||
entry.vs = entry.vs.flatMap(function(v) { | ||
if (subgraphs[v]) { | ||
@@ -65,3 +62,3 @@ return subgraphs[v].vs; | ||
return v; | ||
}), true); | ||
}); | ||
}); | ||
@@ -71,3 +68,3 @@ } | ||
function mergeBarycenters(target, other) { | ||
if (!_.isUndefined(target.barycenter)) { | ||
if (target.barycenter !== undefined) { | ||
target.barycenter = (target.barycenter * target.weight + | ||
@@ -74,0 +71,0 @@ other.barycenter * other.weight) / |
@@ -1,3 +0,2 @@ | ||
var _ = require("../lodash"), | ||
util = require("../util"); | ||
var util = require("../util"); | ||
@@ -8,10 +7,10 @@ module.exports = sort; | ||
var parts = util.partition(entries, function(entry) { | ||
return _.has(entry, "barycenter"); | ||
return entry.hasOwnProperty("barycenter"); | ||
}); | ||
var sortable = parts.lhs, | ||
unsortable = _.sortBy(parts.rhs, function(entry) { return -entry.i; }), | ||
vs = [], | ||
sum = 0, | ||
weight = 0, | ||
vsIndex = 0; | ||
unsortable = parts.rhs.sort((a, b) => b.i - a.i), | ||
vs = [], | ||
sum = 0, | ||
weight = 0, | ||
vsIndex = 0; | ||
@@ -22,3 +21,3 @@ sortable.sort(compareWithBias(!!biasRight)); | ||
_.forEach(sortable, function (entry) { | ||
sortable.forEach(function (entry) { | ||
vsIndex += entry.vs.length; | ||
@@ -31,3 +30,3 @@ vs.push(entry.vs); | ||
var result = { vs: _.flatten(vs, true) }; | ||
var result = { vs: vs.flat(true) }; | ||
if (weight) { | ||
@@ -42,3 +41,3 @@ result.barycenter = sum / weight; | ||
var last; | ||
while (unsortable.length && (last = _.last(unsortable)).i <= index) { | ||
while (unsortable.length && (last = unsortable[unsortable.length - 1]).i <= index) { | ||
unsortable.pop(); | ||
@@ -45,0 +44,0 @@ vs.push(last.vs); |
@@ -1,3 +0,1 @@ | ||
var _ = require("./lodash"); | ||
module.exports = parentDummyChains; | ||
@@ -8,11 +6,11 @@ | ||
_.forEach(g.graph().dummyChains, function(v) { | ||
var node = g.node(v), | ||
edgeObj = node.edgeObj, | ||
pathData = findPath(g, postorderNums, edgeObj.v, edgeObj.w), | ||
path = pathData.path, | ||
lca = pathData.lca, | ||
pathIdx = 0, | ||
pathV = path[pathIdx], | ||
ascending = true; | ||
g.graph().dummyChains.forEach(function(v) { | ||
var node = g.node(v); | ||
var edgeObj = node.edgeObj; | ||
var pathData = findPath(g, postorderNums, edgeObj.v, edgeObj.w); | ||
var path = pathData.path; | ||
var lca = pathData.lca; | ||
var pathIdx = 0; | ||
var pathV = path[pathIdx]; | ||
var ascending = true; | ||
@@ -50,8 +48,8 @@ while (v !== edgeObj.w) { | ||
function findPath(g, postorderNums, v, w) { | ||
var vPath = [], | ||
wPath = [], | ||
low = Math.min(postorderNums[v].low, postorderNums[w].low), | ||
lim = Math.max(postorderNums[v].lim, postorderNums[w].lim), | ||
parent, | ||
lca; | ||
var vPath = []; | ||
var wPath = []; | ||
var low = Math.min(postorderNums[v].low, postorderNums[w].low); | ||
var lim = Math.max(postorderNums[v].lim, postorderNums[w].lim); | ||
var parent; | ||
var lca; | ||
@@ -77,13 +75,13 @@ // Traverse up from v to find the LCA | ||
function postorder(g) { | ||
var result = {}, | ||
lim = 0; | ||
var result = {}; | ||
var lim = 0; | ||
function dfs(v) { | ||
var low = lim; | ||
_.forEach(g.children(v), dfs); | ||
g.children(v).forEach(dfs); | ||
result[v] = { low: low, lim: lim++ }; | ||
} | ||
_.forEach(g.children(), dfs); | ||
g.children().forEach(dfs); | ||
return result; | ||
} |
"use strict"; | ||
var _ = require("../lodash"), | ||
Graph = require("../graphlib").Graph, | ||
util = require("../util"); | ||
var Graph = require("@dagrejs/graphlib").Graph; | ||
var util = require("../util"); | ||
@@ -54,13 +53,13 @@ /* | ||
prevLayerLength = prevLayer.length, | ||
lastNode = _.last(layer); | ||
lastNode = layer[layer.length - 1]; | ||
_.forEach(layer, function(v, i) { | ||
layer.forEach(function(v, i) { | ||
var w = findOtherInnerSegmentNode(g, v), | ||
k1 = w ? g.node(w).order : prevLayerLength; | ||
k1 = w ? g.node(w).order : prevLayerLength; | ||
if (w || v === lastNode) { | ||
_.forEach(layer.slice(scanPos, i +1), function(scanNode) { | ||
_.forEach(g.predecessors(scanNode), function(u) { | ||
layer.slice(scanPos, i+1).forEach(function(scanNode) { | ||
g.predecessors(scanNode).forEach(function(u) { | ||
var uLabel = g.node(u), | ||
uPos = uLabel.order; | ||
uPos = uLabel.order; | ||
if ((uPos < k0 || k1 < uPos) && | ||
@@ -80,3 +79,3 @@ !(uLabel.dummy && g.node(scanNode).dummy)) { | ||
_.reduce(layering, visitLayer); | ||
layering.reduce(visitLayer); | ||
return conflicts; | ||
@@ -90,6 +89,6 @@ } | ||
var v; | ||
_.forEach(_.range(southPos, southEnd), function(i) { | ||
util.range(southPos, southEnd).forEach(function(i) { | ||
v = south[i]; | ||
if (g.node(v).dummy) { | ||
_.forEach(g.predecessors(v), function(u) { | ||
g.predecessors(v).forEach(function(u) { | ||
var uNode = g.node(u); | ||
@@ -108,6 +107,6 @@ if (uNode.dummy && | ||
var prevNorthPos = -1, | ||
nextNorthPos, | ||
southPos = 0; | ||
nextNorthPos, | ||
southPos = 0; | ||
_.forEach(south, function(v, southLookahead) { | ||
south.forEach(function(v, southLookahead) { | ||
if (g.node(v).dummy === "border") { | ||
@@ -128,3 +127,3 @@ var predecessors = g.predecessors(v); | ||
_.reduce(layering, visitLayer); | ||
layering.reduce(visitLayer); | ||
return conflicts; | ||
@@ -135,5 +134,3 @@ } | ||
if (g.node(v).dummy) { | ||
return _.find(g.predecessors(v), function(u) { | ||
return g.node(u).dummy; | ||
}); | ||
return g.predecessors(v).find(u => g.node(u).dummy); | ||
} | ||
@@ -162,3 +159,3 @@ } | ||
} | ||
return _.has(conflicts[v], w); | ||
return !!conflicts[v] && conflicts[v].hasOwnProperty(w); | ||
} | ||
@@ -176,4 +173,4 @@ | ||
var root = {}, | ||
align = {}, | ||
pos = {}; | ||
align = {}, | ||
pos = {}; | ||
@@ -183,4 +180,4 @@ // We cache the position here based on the layering because the graph and | ||
// generate different extreme alignments. | ||
_.forEach(layering, function(layer) { | ||
_.forEach(layer, function(v, order) { | ||
layering.forEach(function(layer) { | ||
layer.forEach(function(v, order) { | ||
root[v] = v; | ||
@@ -192,8 +189,8 @@ align[v] = v; | ||
_.forEach(layering, function(layer) { | ||
layering.forEach(function(layer) { | ||
var prevIdx = -1; | ||
_.forEach(layer, function(v) { | ||
layer.forEach(function(v) { | ||
var ws = neighborFn(v); | ||
if (ws.length) { | ||
ws = _.sortBy(ws, function(w) { return pos[w]; }); | ||
ws = ws.sort((a, b) => pos[a] - pos[b]); | ||
var mp = (ws.length - 1) / 2; | ||
@@ -224,37 +221,46 @@ for (var i = Math.floor(mp), il = Math.ceil(mp); i <= il; ++i) { | ||
var xs = {}, | ||
blockG = buildBlockGraph(g, layering, root, reverseSep); | ||
blockG = buildBlockGraph(g, layering, root, reverseSep), | ||
borderType = reverseSep ? "borderLeft" : "borderRight"; | ||
// First pass, assign smallest coordinates via DFS | ||
var visited = {}; | ||
function pass1(v) { | ||
if (!_.has(visited, v)) { | ||
visited[v] = true; | ||
xs[v] = _.reduce(blockG.inEdges(v), function(max, e) { | ||
pass1(e.v); | ||
return Math.max(max, xs[e.v] + blockG.edge(e)); | ||
}, 0); | ||
function iterate(setXsFunc, nextNodesFunc) { | ||
var stack = blockG.nodes(); | ||
var elem = stack.pop(); | ||
var visited = {}; | ||
while (elem) { | ||
if (visited[elem]) { | ||
setXsFunc(elem); | ||
} else { | ||
visited[elem] = true; | ||
stack.push(elem); | ||
stack = stack.concat(nextNodesFunc(elem)); | ||
} | ||
elem = stack.pop(); | ||
} | ||
} | ||
_.forEach(blockG.nodes(), pass1); | ||
var borderType = reverseSep ? "borderLeft" : "borderRight"; | ||
function pass2(v) { | ||
if (visited[v] !== 2) { | ||
visited[v]++; | ||
var node = g.node(v); | ||
var min = _.reduce(blockG.outEdges(v), function(min, e) { | ||
pass2(e.w); | ||
return Math.min(min, xs[e.w] - blockG.edge(e)); | ||
}, Number.POSITIVE_INFINITY); | ||
if (min !== Number.POSITIVE_INFINITY && node.borderType !== borderType) { | ||
xs[v] = Math.max(xs[v], min); | ||
} | ||
// First pass, assign smallest coordinates | ||
function pass1(elem) { | ||
xs[elem] = blockG.inEdges(elem).reduce(function(acc, e) { | ||
return Math.max(acc, xs[e.v] + blockG.edge(e)); | ||
}, 0); | ||
} | ||
// Second pass, assign greatest coordinates | ||
function pass2(elem) { | ||
var min = blockG.outEdges(elem).reduce(function(acc, e) { | ||
return Math.min(acc, xs[e.w] - blockG.edge(e)); | ||
}, Number.POSITIVE_INFINITY); | ||
var node = g.node(elem); | ||
if (min !== Number.POSITIVE_INFINITY && node.borderType !== borderType) { | ||
xs[elem] = Math.max(xs[elem], min); | ||
} | ||
} | ||
_.forEach(blockG.nodes(), pass2); | ||
iterate(pass1, blockG.predecessors.bind(blockG)); | ||
iterate(pass2, blockG.successors.bind(blockG)); | ||
// Assign x coordinates to all nodes | ||
_.forEach(align, function(v) { | ||
xs[v] = xs[root[v]]; | ||
}); | ||
Object.keys(align).forEach(v => xs[v] = xs[root[v]]); | ||
@@ -267,8 +273,8 @@ return xs; | ||
var blockGraph = new Graph(), | ||
graphLabel = g.graph(), | ||
sepFn = sep(graphLabel.nodesep, graphLabel.edgesep, reverseSep); | ||
graphLabel = g.graph(), | ||
sepFn = sep(graphLabel.nodesep, graphLabel.edgesep, reverseSep); | ||
_.forEach(layering, function(layer) { | ||
layering.forEach(function(layer) { | ||
var u; | ||
_.forEach(layer, function(v) { | ||
layer.forEach(function(v) { | ||
var vRoot = root[v]; | ||
@@ -278,3 +284,3 @@ blockGraph.setNode(vRoot); | ||
var uRoot = root[u], | ||
prevMax = blockGraph.edge(uRoot, vRoot); | ||
prevMax = blockGraph.edge(uRoot, vRoot); | ||
blockGraph.setEdge(uRoot, vRoot, Math.max(sepFn(g, v, u), prevMax || 0)); | ||
@@ -293,7 +299,7 @@ } | ||
function findSmallestWidthAlignment(g, xss) { | ||
return _.minBy(_.values(xss), function (xs) { | ||
return Object.values(xss).reduce((currentMinAndXs, xs) => { | ||
var max = Number.NEGATIVE_INFINITY; | ||
var min = Number.POSITIVE_INFINITY; | ||
_.forIn(xs, function (x, v) { | ||
Object.entries(xs).forEach(([v, x]) => { | ||
var halfWidth = width(g, v) / 2; | ||
@@ -305,4 +311,8 @@ | ||
return max - min; | ||
}); | ||
const newMin = max - min; | ||
if (newMin < currentMinAndXs[0]) { | ||
currentMinAndXs = [newMin, xs]; | ||
} | ||
return currentMinAndXs; | ||
}, [Number.POSITIVE_INFINITY, null])[1]; | ||
} | ||
@@ -318,18 +328,21 @@ | ||
function alignCoordinates(xss, alignTo) { | ||
var alignToVals = _.values(alignTo), | ||
alignToMin = _.min(alignToVals), | ||
alignToMax = _.max(alignToVals); | ||
var alignToVals = Object.values(alignTo), | ||
alignToMin = Math.min(...alignToVals), | ||
alignToMax = Math.max(...alignToVals); | ||
_.forEach(["u", "d"], function(vert) { | ||
_.forEach(["l", "r"], function(horiz) { | ||
["u", "d"].forEach(function(vert) { | ||
["l", "r"].forEach(function(horiz) { | ||
var alignment = vert + horiz, | ||
xs = xss[alignment], | ||
delta; | ||
xs = xss[alignment]; | ||
if (xs === alignTo) return; | ||
var xsVals = _.values(xs); | ||
delta = horiz === "l" ? alignToMin - _.min(xsVals) : alignToMax - _.max(xsVals); | ||
var xsVals = Object.values(xs); | ||
let delta = alignToMin - Math.min(...xsVals); | ||
if (horiz !== "l") { | ||
delta = alignToMax - Math.max(...xsVals); | ||
} | ||
if (delta) { | ||
xss[alignment] = _.mapValues(xs, function(x) { return x + delta; }); | ||
xss[alignment] = util.mapValues(xs, x => x + delta); | ||
} | ||
@@ -341,7 +354,7 @@ }); | ||
function balance(xss, align) { | ||
return _.mapValues(xss.ul, function(ignore, v) { | ||
return util.mapValues(xss.ul, function(num, v) { | ||
if (align) { | ||
return xss[align.toLowerCase()][v]; | ||
} else { | ||
var xs = _.sortBy(_.map(xss, v)); | ||
var xs = Object.values(xss).map(xs => xs[v]).sort((a, b) => a - b); | ||
return (xs[1] + xs[2]) / 2; | ||
@@ -353,24 +366,24 @@ } | ||
function positionX(g) { | ||
var layering = util.buildLayerMatrix(g), | ||
conflicts = _.merge(findType1Conflicts(g, layering), | ||
findType2Conflicts(g, layering)); | ||
var layering = util.buildLayerMatrix(g); | ||
var conflicts = Object.assign( | ||
findType1Conflicts(g, layering), | ||
findType2Conflicts(g, layering)); | ||
var xss = {}, | ||
adjustedLayering; | ||
_.forEach(["u", "d"], function(vert) { | ||
adjustedLayering = vert === "u" ? layering : _.values(layering).reverse(); | ||
_.forEach(["l", "r"], function(horiz) { | ||
var xss = {}; | ||
var adjustedLayering; | ||
["u", "d"].forEach(function(vert) { | ||
adjustedLayering = vert === "u" ? layering : Object.values(layering).reverse(); | ||
["l", "r"].forEach(function(horiz) { | ||
if (horiz === "r") { | ||
adjustedLayering = _.map(adjustedLayering, function(inner) { | ||
return _.values(inner).reverse(); | ||
adjustedLayering = adjustedLayering.map(inner => { | ||
return Object.values(inner).reverse(); | ||
}); | ||
} | ||
var neighborFn = _.bind(vert === "u" ? g.predecessors : g.successors, g); | ||
var neighborFn = (vert === "u" ? g.predecessors : g.successors).bind(g); | ||
var align = verticalAlignment(g, adjustedLayering, conflicts, neighborFn); | ||
var xs = horizontalCompaction(g, adjustedLayering, | ||
align.root, align.align, | ||
horiz === "r"); | ||
align.root, align.align, horiz === "r"); | ||
if (horiz === "r") { | ||
xs = _.mapValues(xs, function(x) { return -x; }); | ||
xs = util.mapValues(xs, x => -x); | ||
} | ||
@@ -381,2 +394,3 @@ xss[vert + horiz] = xs; | ||
var smallestWidth = findSmallestWidthAlignment(g, xss); | ||
@@ -389,12 +403,12 @@ alignCoordinates(xss, smallestWidth); | ||
return function(g, v, w) { | ||
var vLabel = g.node(v), | ||
wLabel = g.node(w), | ||
sum = 0, | ||
delta; | ||
var vLabel = g.node(v); | ||
var wLabel = g.node(w); | ||
var sum = 0; | ||
var delta; | ||
sum += vLabel.width / 2; | ||
if (_.has(vLabel, "labelpos")) { | ||
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; | ||
} | ||
@@ -411,6 +425,6 @@ } | ||
sum += wLabel.width / 2; | ||
if (_.has(wLabel, "labelpos")) { | ||
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; | ||
} | ||
@@ -417,0 +431,0 @@ } |
"use strict"; | ||
var _ = require("../lodash"), | ||
util = require("../util"), | ||
positionX = require("./bk").positionX; | ||
var util = require("../util"); | ||
var positionX = require("./bk").positionX; | ||
@@ -13,16 +12,19 @@ module.exports = position; | ||
positionY(g); | ||
_.forEach(positionX(g), function(x, v) { | ||
g.node(v).x = x; | ||
}); | ||
Object.entries(positionX(g)).forEach(([v, x]) => g.node(v).x = x); | ||
} | ||
function positionY(g) { | ||
var layering = util.buildLayerMatrix(g), | ||
rankSep = g.graph().ranksep, | ||
prevY = 0; | ||
_.forEach(layering, function(layer) { | ||
var maxHeight = _.max(_.map(layer, function(v) { return g.node(v).height; })); | ||
_.forEach(layer, function(v) { | ||
g.node(v).y = prevY + maxHeight / 2; | ||
}); | ||
var layering = util.buildLayerMatrix(g); | ||
var rankSep = g.graph().ranksep; | ||
var prevY = 0; | ||
layering.forEach(function(layer) { | ||
const maxHeight = layer.reduce((acc, v) => { | ||
const height = g.node(v).height; | ||
if (acc > height) { | ||
return acc; | ||
} else { | ||
return height; | ||
} | ||
}, 0); | ||
layer.forEach(v => g.node(v).y = prevY + maxHeight / 2); | ||
prevY += maxHeight + rankSep; | ||
@@ -29,0 +31,0 @@ }); |
"use strict"; | ||
var _ = require("../lodash"), | ||
Graph = require("../graphlib").Graph, | ||
slack = require("./util").slack; | ||
var Graph = require("@dagrejs/graphlib").Graph; | ||
var slack = require("./util").slack; | ||
@@ -38,4 +37,4 @@ module.exports = feasibleTree; | ||
// Choose arbitrary node from which to start our tree | ||
var start = g.nodes()[0], | ||
size = g.nodeCount(); | ||
var start = g.nodes()[0]; | ||
var size = g.nodeCount(); | ||
t.setNode(start, {}); | ||
@@ -59,5 +58,5 @@ | ||
function dfs(v) { | ||
_.forEach(g.nodeEdges(v), function(e) { | ||
g.nodeEdges(v).forEach(function(e) { | ||
var edgeV = e.v, | ||
w = (v === edgeV) ? e.w : edgeV; | ||
w = (v === edgeV) ? e.w : edgeV; | ||
if (!t.hasNode(w) && !slack(g, e)) { | ||
@@ -71,3 +70,3 @@ t.setNode(w, {}); | ||
_.forEach(t.nodes(), dfs); | ||
t.nodes().forEach(dfs); | ||
return t.nodeCount(); | ||
@@ -81,13 +80,20 @@ } | ||
function findMinSlackEdge(t, g) { | ||
return _.minBy(g.edges(), function(e) { | ||
if (t.hasNode(e.v) !== t.hasNode(e.w)) { | ||
return slack(g, e); | ||
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); | ||
} | ||
}); | ||
if (edgeSlack < acc[0]) { | ||
return [edgeSlack, edge]; | ||
} | ||
return acc; | ||
}, [Number.POSITIVE_INFINITY, null])[1]; | ||
} | ||
function shiftRanks(t, g, delta) { | ||
_.forEach(t.nodes(), function(v) { | ||
g.node(v).rank += delta; | ||
}); | ||
t.nodes().forEach(v => g.node(v).rank += delta); | ||
} |
"use strict"; | ||
var rankUtil = require("./util"), | ||
longestPath = rankUtil.longestPath, | ||
feasibleTree = require("./feasible-tree"), | ||
networkSimplex = require("./network-simplex"); | ||
var rankUtil = require("./util"); | ||
var longestPath = rankUtil.longestPath; | ||
var feasibleTree = require("./feasible-tree"); | ||
var networkSimplex = require("./network-simplex"); | ||
@@ -31,6 +31,6 @@ module.exports = rank; | ||
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); | ||
case "network-simplex": networkSimplexRanker(g); break; | ||
case "tight-tree": tightTreeRanker(g); break; | ||
case "longest-path": longestPathRanker(g); break; | ||
default: networkSimplexRanker(g); | ||
} | ||
@@ -37,0 +37,0 @@ } |
"use strict"; | ||
var _ = require("../lodash"), | ||
feasibleTree = require("./feasible-tree"), | ||
slack = require("./util").slack, | ||
initRank = require("./util").longestPath, | ||
preorder = require("../graphlib").alg.preorder, | ||
postorder = require("../graphlib").alg.postorder, | ||
simplify = require("../util").simplify; | ||
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; | ||
@@ -74,10 +73,8 @@ module.exports = networkSimplex; | ||
vs = vs.slice(0, vs.length - 1); | ||
_.forEach(vs, function(v) { | ||
assignCutValue(t, g, v); | ||
}); | ||
vs.forEach(v => assignCutValue(t, g, v)); | ||
} | ||
function assignCutValue(t, g, child) { | ||
var childLab = t.node(child), | ||
parent = childLab.parent; | ||
var childLab = t.node(child); | ||
var parent = childLab.parent; | ||
t.edge(child, parent).cutvalue = calcCutValue(t, g, child); | ||
@@ -91,10 +88,10 @@ } | ||
function calcCutValue(t, g, child) { | ||
var childLab = t.node(child), | ||
parent = childLab.parent, | ||
// True if the child is on the tail end of the edge in the directed graph | ||
childIsTail = true, | ||
// The graph's view of the tree edge we're inspecting | ||
graphEdge = g.edge(child, parent), | ||
// The accumulated cut value for the edge between this node and its parent | ||
cutValue = 0; | ||
var childLab = t.node(child); | ||
var parent = childLab.parent; | ||
// True if the child is on the tail end of the edge in the directed graph | ||
var childIsTail = true; | ||
// The graph's view of the tree edge we're inspecting | ||
var graphEdge = g.edge(child, parent); | ||
// The accumulated cut value for the edge between this node and its parent | ||
var cutValue = 0; | ||
@@ -108,9 +105,9 @@ if (!graphEdge) { | ||
_.forEach(g.nodeEdges(child), function(e) { | ||
g.nodeEdges(child).forEach(function(e) { | ||
var isOutEdge = e.v === child, | ||
other = isOutEdge ? e.w : e.v; | ||
other = isOutEdge ? e.w : e.v; | ||
if (other !== parent) { | ||
var pointsToHead = isOutEdge === childIsTail, | ||
otherWeight = g.edge(e).weight; | ||
otherWeight = g.edge(e).weight; | ||
@@ -136,8 +133,8 @@ cutValue += pointsToHead ? otherWeight : -otherWeight; | ||
function dfsAssignLowLim(tree, visited, nextLim, v, parent) { | ||
var low = nextLim, | ||
label = tree.node(v); | ||
var low = nextLim; | ||
var label = tree.node(v); | ||
visited[v] = true; | ||
_.forEach(tree.neighbors(v), function(w) { | ||
if (!_.has(visited, w)) { | ||
tree.neighbors(v).forEach(function(w) { | ||
if (!visited.hasOwnProperty(w)) { | ||
nextLim = dfsAssignLowLim(tree, visited, nextLim, w, v); | ||
@@ -160,10 +157,8 @@ } | ||
function leaveEdge(tree) { | ||
return _.find(tree.edges(), function(e) { | ||
return tree.edge(e).cutvalue < 0; | ||
}); | ||
return tree.edges().find(e => tree.edge(e).cutvalue < 0); | ||
} | ||
function enterEdge(t, g, edge) { | ||
var v = edge.v, | ||
w = edge.w; | ||
var v = edge.v; | ||
var w = edge.w; | ||
@@ -178,6 +173,6 @@ // For the rest of this function we assume that v is the tail and w is the | ||
var vLabel = t.node(v), | ||
wLabel = t.node(w), | ||
tailLabel = vLabel, | ||
flip = false; | ||
var vLabel = t.node(v); | ||
var wLabel = t.node(w); | ||
var tailLabel = vLabel; | ||
var flip = false; | ||
@@ -191,3 +186,3 @@ // If the root is in the tail of the edge then we need to flip the logic that | ||
var candidates = _.filter(g.edges(), function(edge) { | ||
var candidates = g.edges().filter(function(edge) { | ||
return flip === isDescendant(t, t.node(edge.v), tailLabel) && | ||
@@ -197,8 +192,14 @@ flip !== isDescendant(t, t.node(edge.w), tailLabel); | ||
return _.minBy(candidates, function(edge) { return slack(g, edge); }); | ||
return candidates.reduce((acc, edge) => { | ||
if (slack(g, edge) < slack(g, acc)) { | ||
return edge; | ||
} | ||
return acc; | ||
}); | ||
} | ||
function exchangeEdges(t, g, e, f) { | ||
var v = e.v, | ||
w = e.w; | ||
var v = e.v; | ||
var w = e.w; | ||
t.removeEdge(v, w); | ||
@@ -212,9 +213,9 @@ t.setEdge(f.v, f.w, {}); | ||
function updateRanks(t, g) { | ||
var root = _.find(t.nodes(), function(v) { return !g.node(v).parent; }), | ||
vs = preorder(t, root); | ||
var root = t.nodes().find(v => !g.node(v).parent); | ||
var vs = preorder(t, root); | ||
vs = vs.slice(1); | ||
_.forEach(vs, function(v) { | ||
vs.forEach(function(v) { | ||
var parent = t.node(v).parent, | ||
edge = g.edge(v, parent), | ||
flipped = false; | ||
edge = g.edge(v, parent), | ||
flipped = false; | ||
@@ -221,0 +222,0 @@ if (!edge) { |
"use strict"; | ||
var _ = require("../lodash"); | ||
module.exports = { | ||
@@ -36,3 +34,3 @@ longestPath: longestPath, | ||
var label = g.node(v); | ||
if (_.has(visited, v)) { | ||
if (visited.hasOwnProperty(v)) { | ||
return label.rank; | ||
@@ -42,9 +40,11 @@ } | ||
var rank = _.minBy(_.map(g.outEdges(v), function(e) { | ||
var rank = Math.min(...g.outEdges(v).map(e => { | ||
if (e == null) { | ||
return Number.POSITIVE_INFINITY; | ||
} | ||
return dfs(e.w) - g.edge(e).minlen; | ||
})); | ||
if (rank === Number.POSITIVE_INFINITY || // return value of _.map([]) for Lodash 3 | ||
rank === undefined || // return value of _.map([]) for Lodash 4 | ||
rank === null) { // return value of _.map([null]) | ||
if (rank === Number.POSITIVE_INFINITY) { | ||
rank = 0; | ||
@@ -56,3 +56,3 @@ } | ||
_.forEach(g.sources(), dfs); | ||
g.sources().forEach(dfs); | ||
} | ||
@@ -59,0 +59,0 @@ |
172
lib/util.js
@@ -0,21 +1,27 @@ | ||
/* eslint "no-console": off */ | ||
"use strict"; | ||
var _ = require("./lodash"), | ||
Graph = require("./graphlib").Graph; | ||
var Graph = require("@dagrejs/graphlib").Graph; | ||
module.exports = { | ||
addDummyNode: addDummyNode, | ||
simplify: simplify, | ||
asNonCompoundGraph: asNonCompoundGraph, | ||
successorWeights: successorWeights, | ||
predecessorWeights: predecessorWeights, | ||
intersectRect: intersectRect, | ||
buildLayerMatrix: buildLayerMatrix, | ||
normalizeRanks: normalizeRanks, | ||
removeEmptyRanks: removeEmptyRanks, | ||
addBorderNode: addBorderNode, | ||
maxRank: maxRank, | ||
partition: partition, | ||
time: time, | ||
notime: notime | ||
addBorderNode, | ||
addDummyNode, | ||
asNonCompoundGraph, | ||
buildLayerMatrix, | ||
intersectRect, | ||
mapValues, | ||
maxRank, | ||
normalizeRanks, | ||
notime, | ||
partition, | ||
pick, | ||
predecessorWeights, | ||
range, | ||
removeEmptyRanks, | ||
simplify, | ||
successorWeights, | ||
time, | ||
uniqueId, | ||
zipObject, | ||
}; | ||
@@ -29,3 +35,3 @@ | ||
do { | ||
v = _.uniqueId(name); | ||
v = uniqueId(name); | ||
} while (g.hasNode(v)); | ||
@@ -44,6 +50,6 @@ | ||
var simplified = new Graph().setGraph(g.graph()); | ||
_.forEach(g.nodes(), function(v) { simplified.setNode(v, g.node(v)); }); | ||
_.forEach(g.edges(), function(e) { | ||
var simpleLabel = simplified.edge(e.v, e.w) || { weight: 0, minlen: 1 }, | ||
label = g.edge(e); | ||
g.nodes().forEach(v => simplified.setNode(v, g.node(v))); | ||
g.edges().forEach(e => { | ||
var simpleLabel = simplified.edge(e.v, e.w) || { weight: 0, minlen: 1 }; | ||
var label = g.edge(e); | ||
simplified.setEdge(e.v, e.w, { | ||
@@ -59,3 +65,3 @@ weight: simpleLabel.weight + label.weight, | ||
var simplified = new Graph({ multigraph: g.isMultigraph() }).setGraph(g.graph()); | ||
_.forEach(g.nodes(), function(v) { | ||
g.nodes().forEach(v => { | ||
if (!g.children(v).length) { | ||
@@ -65,3 +71,3 @@ simplified.setNode(v, g.node(v)); | ||
}); | ||
_.forEach(g.edges(), function(e) { | ||
g.edges().forEach(e => { | ||
simplified.setEdge(e, g.edge(e)); | ||
@@ -73,5 +79,5 @@ }); | ||
function successorWeights(g) { | ||
var weightMap = _.map(g.nodes(), function(v) { | ||
var weightMap = g.nodes().map(v => { | ||
var sucs = {}; | ||
_.forEach(g.outEdges(v), function(e) { | ||
g.outEdges(v).forEach(e => { | ||
sucs[e.w] = (sucs[e.w] || 0) + g.edge(e).weight; | ||
@@ -81,9 +87,9 @@ }); | ||
}); | ||
return _.zipObject(g.nodes(), weightMap); | ||
return zipObject(g.nodes(), weightMap); | ||
} | ||
function predecessorWeights(g) { | ||
var weightMap = _.map(g.nodes(), function(v) { | ||
var weightMap = g.nodes().map(v => { | ||
var preds = {}; | ||
_.forEach(g.inEdges(v), function(e) { | ||
g.inEdges(v).forEach(e => { | ||
preds[e.v] = (preds[e.v] || 0) + g.edge(e).weight; | ||
@@ -93,3 +99,3 @@ }); | ||
}); | ||
return _.zipObject(g.nodes(), weightMap); | ||
return zipObject(g.nodes(), weightMap); | ||
} | ||
@@ -141,7 +147,7 @@ | ||
function buildLayerMatrix(g) { | ||
var layering = _.map(_.range(maxRank(g) + 1), function() { return []; }); | ||
_.forEach(g.nodes(), function(v) { | ||
var node = g.node(v), | ||
rank = node.rank; | ||
if (!_.isUndefined(rank)) { | ||
var layering = range(maxRank(g) + 1).map(() => []); | ||
g.nodes().forEach(v => { | ||
var node = g.node(v); | ||
var rank = node.rank; | ||
if (rank !== undefined) { | ||
layering[rank][node.order] = v; | ||
@@ -158,6 +164,13 @@ } | ||
function normalizeRanks(g) { | ||
var min = _.minBy(_.map(g.nodes(), function(v) { return g.node(v).rank; })); | ||
_.forEach(g.nodes(), function(v) { | ||
var min = Math.min(...g.nodes().map(v => { | ||
var rank = g.node(v).rank; | ||
if (rank === undefined) { | ||
return Number.MAX_VALUE; | ||
} | ||
return rank; | ||
})); | ||
g.nodes().forEach(v => { | ||
var node = g.node(v); | ||
if (_.has(node, "rank")) { | ||
if (node.hasOwnProperty("rank")) { | ||
node.rank -= min; | ||
@@ -170,6 +183,6 @@ } | ||
// Ranks may not start at 0, so we need to offset them | ||
var offset = _.minBy(_.map(g.nodes(), function(v) { return g.node(v).rank; })); | ||
var offset = Math.min(...g.nodes().map(v => g.node(v).rank)); | ||
var layers = []; | ||
_.forEach(g.nodes(), function(v) { | ||
g.nodes().forEach(v => { | ||
var rank = g.node(v).rank - offset; | ||
@@ -182,9 +195,9 @@ if (!layers[rank]) { | ||
var delta = 0, | ||
nodeRankFactor = g.graph().nodeRankFactor; | ||
_.forEach(layers, function(vs, i) { | ||
if (_.isUndefined(vs) && i % nodeRankFactor !== 0) { | ||
var delta = 0; | ||
var nodeRankFactor = g.graph().nodeRankFactor; | ||
Array.from(layers).forEach((vs, i) => { | ||
if (vs === undefined && i % nodeRankFactor !== 0) { | ||
--delta; | ||
} else if (delta) { | ||
_.forEach(vs, function(v) { g.node(v).rank += delta; }); | ||
} else if (vs !== undefined && delta) { | ||
vs.forEach(v => g.node(v).rank += delta); | ||
} | ||
@@ -207,7 +220,9 @@ }); | ||
function maxRank(g) { | ||
return _.max(_.map(g.nodes(), function(v) { | ||
return Math.max(...g.nodes().map(v => { | ||
var rank = g.node(v).rank; | ||
if (!_.isUndefined(rank)) { | ||
return rank; | ||
if (rank === undefined) { | ||
return Number.MIN_VALUE; | ||
} | ||
return rank; | ||
})); | ||
@@ -223,3 +238,3 @@ } | ||
var result = { lhs: [], rhs: [] }; | ||
_.forEach(collection, function(value) { | ||
collection.forEach(value => { | ||
if (fn(value)) { | ||
@@ -239,7 +254,7 @@ result.lhs.push(value); | ||
function time(name, fn) { | ||
var start = _.now(); | ||
var start = Date.now(); | ||
try { | ||
return fn(); | ||
} finally { | ||
console.log(name + " time: " + (_.now() - start) + "ms"); | ||
console.log(name + " time: " + (Date.now() - start) + "ms"); | ||
} | ||
@@ -251,1 +266,56 @@ } | ||
} | ||
let idCounter = 0; | ||
function uniqueId(prefix) { | ||
var id = ++idCounter; | ||
return toString(prefix) + id; | ||
} | ||
function range(start, limit, step = 1) { | ||
if (limit == null) { | ||
limit = start; | ||
start = 0; | ||
} | ||
let endCon = (i) => i < limit; | ||
if (step < 0) { | ||
endCon = (i) => limit < i; | ||
} | ||
const range = []; | ||
for (let i = start; endCon(i); i += step) { | ||
range.push(i); | ||
} | ||
return range; | ||
} | ||
function pick(source, keys) { | ||
const dest = {}; | ||
for (const key of keys) { | ||
if (source[key] !== undefined) { | ||
dest[key] = source[key]; | ||
} | ||
} | ||
return dest; | ||
} | ||
function mapValues(obj, funcOrProp) { | ||
let func = funcOrProp; | ||
if (typeof funcOrProp === 'string') { | ||
func = (val) => val[funcOrProp]; | ||
} | ||
return Object.entries(obj).reduce((acc, [k, v]) => { | ||
acc[k] = func(v, k); | ||
return acc; | ||
}, {}); | ||
} | ||
function zipObject(props, values) { | ||
return props.reduce((acc, key, i) => { | ||
acc[key] = values[i]; | ||
return acc; | ||
}, {}); | ||
} |
@@ -1,1 +0,1 @@ | ||
module.exports = "0.8.0"; | ||
module.exports = "1.0.0"; |
{ | ||
"name": "@dagrejs/dagre", | ||
"version": "0.8.0", | ||
"version": "1.0.0", | ||
"description": "Graph layout for JavaScript", | ||
@@ -9,3 +9,13 @@ "author": "Chris Pettitt <cpettitt@gmail.com>", | ||
], | ||
"license": "MIT", | ||
"main": "index.js", | ||
"scripts": { | ||
"lint": "make lint", | ||
"test": "make test" | ||
}, | ||
"files": [ | ||
"index.js", | ||
"dist/", | ||
"lib/" | ||
], | ||
"keywords": [ | ||
@@ -16,26 +26,23 @@ "graph", | ||
"dependencies": { | ||
"@dagrejs/graphlib": "^2.1.4", | ||
"lodash": "^4.11.1" | ||
"@dagrejs/graphlib": "2.1.12" | ||
}, | ||
"devDependencies": { | ||
"benchmark": "^1.0.0", | ||
"browserify": "^6.1.0", | ||
"chai": "^1.9.2", | ||
"istanbul": "^0.3.2", | ||
"jscs": "^1.7.3", | ||
"jshint": "^2.5.6", | ||
"jshint-stylish": "^1.0.0", | ||
"karma": "^0.13.22", | ||
"karma-chrome-launcher": "^0.2.0", | ||
"karma-firefox-launcher": "^0.1.6", | ||
"karma-mocha": "^0.2.0", | ||
"karma-phantomjs-launcher": "^1.0.0", | ||
"karma-requirejs": "^0.2.5", | ||
"karma-safari-launcher": "^0.1.1", | ||
"mocha": "^1.21.5", | ||
"phantomjs-prebuilt": "^2.1.7", | ||
"requirejs": "^2.1.22", | ||
"semver": "^4.1.0", | ||
"sprintf": "^0.1.4", | ||
"uglify-js": "^2.4.15" | ||
"benchmark": "2.1.4", | ||
"browserify": "17.0.0", | ||
"chai": "4.3.6", | ||
"eslint": "8.35.0", | ||
"jshint": "2.13.5", | ||
"jshint-stylish": "2.2.1", | ||
"karma": "6.4.1", | ||
"karma-chrome-launcher": "3.1.1", | ||
"karma-firefox-launcher": "2.1.2", | ||
"karma-mocha": "2.0.1", | ||
"karma-requirejs": "1.1.0", | ||
"karma-safari-launcher": "1.0.0", | ||
"mocha": "10.1.0", | ||
"nyc": "^15.1.0", | ||
"requirejs": "2.3.6", | ||
"semver": "7.3.7", | ||
"sprintf": "0.1.5", | ||
"uglify-js": "3.17.4" | ||
}, | ||
@@ -45,4 +52,3 @@ "repository": { | ||
"url": "https://github.com/dagrejs/dagre.git" | ||
}, | ||
"license": "MIT" | ||
} | ||
} |
@@ -0,14 +1,22 @@ | ||
# Important! | ||
**This project does not have a maintainer or active project members. There won’t be any support or attention to pull requests. Please do not contact previous maintainers unless you are qualified and have the resources to make a serious commitment to fully take over ownership of the project.** | ||
# dagre - Graph layout for JavaScript | ||
[![Build Status](https://secure.travis-ci.org/dagrejs/dagre.svg?branch=master)](http://travis-ci.org/dagrejs/dagre) | ||
[![Build Status](https://github.com/dagrejs/dagre/workflows/Build%20Status/badge.svg?branch=master)](https://github.com/dagrejs/dagre/actions?query=workflow%3A%22Build+Status%22) | ||
[![npm](https://img.shields.io/npm/v/dagre.svg)](https://www.npmjs.com/package/dagre) | ||
Dagre is a JavaScript library that makes it easy to lay out directed graphs on | ||
the client-side. | ||
For more details, including examples and configuration options, please see our | ||
[wiki](https://github.com/dagrejs/dagre/wiki). | ||
Dagre is a JavaScript library that makes it easy to lay out directed graphs on the client-side. | ||
For more details, including examples and configuration options, please see our [wiki](https://github.com/dagrejs/dagre/wiki). | ||
There are 2 versions on NPM, but only [the one in the DagreJs org](https://www.npmjs.com/package/@dagrejs/dagre) is receiving updates right now. | ||
## License | ||
dagre is licensed under the terms of the MIT License. See the LICENSE file | ||
for details. | ||
dagre is licensed under the terms of the MIT License. See the LICENSE file for details. |
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
Major refactor
Supply chain riskPackage has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.
Found 1 instance in 1 package
New author
Supply chain riskA new npm collaborator published a version of the package for the first time. New collaborators are usually benign additions to a project, but do indicate a change to the security surface area of a package.
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
Uses eval
Supply chain riskPackage uses eval() which is a dangerous function. This prevents the code from running in certain environments and increases the risk that the code may contain exploits or malicious behavior.
Found 1 instance in 1 package
No v1
QualityPackage is not semver >=1. This means it is not stable and does not support ^ ranges.
Found 1 instance in 1 package
1
18
1
23
4
2
291912
33
7250
+ Added@dagrejs/graphlib@2.1.12(transitive)
- Removedlodash@^4.11.1
- Removed@dagrejs/graphlib@2.2.4(transitive)
- Removedlodash@4.17.21(transitive)
Updated@dagrejs/graphlib@2.1.12