1 /*! JointJS v0.9.0 - JavaScript diagramming library 2014-05-13
4 This Source Code Form is subject to the terms of the Mozilla Public
5 License, v. 2.0. If a copy of the MPL was not distributed with this
6 file, You can obtain one at http://mozilla.org/MPL/2.0/.
8 ;(function e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);throw new Error("Cannot find module '"+o+"'")}var f=n[o]={exports:{}};t[o][0].call(f.exports,function(e){var n=t[o][1][e];return s(n?n:e)},f,f.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return s})({1:[function(require,module,exports){
9 var global=typeof self !== "undefined" ? self : typeof window !== "undefined" ? window : {};/**
11 * Copyright (c) 2012-2013 Chris Pettitt
13 * Permission is hereby granted, free of charge, to any person obtaining a copy
14 * of this software and associated documentation files (the "Software"), to deal
15 * in the Software without restriction, including without limitation the rights
16 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
17 * copies of the Software, and to permit persons to whom the Software is
18 * furnished to do so, subject to the following conditions:
20 * The above copyright notice and this permission notice shall be included in
21 * all copies or substantial portions of the Software.
23 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
24 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
25 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
26 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
27 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
28 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
31 global.dagre = require("./index");
33 },{"./index":2}],2:[function(require,module,exports){
35 Copyright (c) 2012-2013 Chris Pettitt
37 Permission is hereby granted, free of charge, to any person obtaining a copy
38 of this software and associated documentation files (the "Software"), to deal
39 in the Software without restriction, including without limitation the rights
40 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
41 copies of the Software, and to permit persons to whom the Software is
42 furnished to do so, subject to the following conditions:
44 The above copyright notice and this permission notice shall be included in
45 all copies or substantial portions of the Software.
47 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
48 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
49 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
50 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
51 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
52 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
55 exports.Digraph = require("graphlib").Digraph;
56 exports.Graph = require("graphlib").Graph;
57 exports.layout = require("./lib/layout");
58 exports.version = require("./lib/version");
60 },{"./lib/layout":3,"./lib/version":18,"graphlib":24}],3:[function(require,module,exports){
61 var util = require('./util'),
62 rank = require('./rank'),
63 order = require('./order'),
64 CGraph = require('graphlib').CGraph,
65 CDigraph = require('graphlib').CDigraph;
67 module.exports = function() {
68 // External configuration
70 // How much debug information to include?
72 // Max number of sweeps to perform in order phase
73 orderMaxSweeps: order.DEFAULT_MAX_SWEEPS,
74 // Use network simplex algorithm in ranking
76 // Rank direction. Valid values are (TB, LR)
81 var position = require('./position')();
86 self.orderIters = util.propertyAccessor(self, config, 'orderMaxSweeps');
88 self.rankSimplex = util.propertyAccessor(self, config, 'rankSimplex');
90 self.nodeSep = delegateProperty(position.nodeSep);
91 self.edgeSep = delegateProperty(position.edgeSep);
92 self.universalSep = delegateProperty(position.universalSep);
93 self.rankSep = delegateProperty(position.rankSep);
94 self.rankDir = util.propertyAccessor(self, config, 'rankDir');
95 self.debugAlignment = delegateProperty(position.debugAlignment);
97 self.debugLevel = util.propertyAccessor(self, config, 'debugLevel', function(x) {
99 position.debugLevel(x);
102 self.run = util.time('Total layout', run);
104 self._normalize = normalize;
109 * Constructs an adjacency graph using the nodes and edges specified through
110 * config. For each node and edge we add a property `dagre` that contains an
111 * object that will hold intermediate and final layout information. Some of
112 * the contents include:
114 * 1) A generated ID that uniquely identifies the object.
115 * 2) Dimension information for nodes (copied from the source node).
116 * 3) Optional dimension information for edges.
118 * After the adjacency graph is constructed the code no longer needs to use
119 * the original nodes and edges passed in via config.
121 function initLayoutGraph(inputGraph) {
122 var g = new CDigraph();
124 inputGraph.eachNode(function(u, value) {
125 if (value === undefined) value = {};
130 if (value.hasOwnProperty('rank')) {
131 g.node(u).prefRank = value.rank;
136 if (inputGraph.parent) {
137 inputGraph.nodes().forEach(function(u) {
138 g.parent(u, inputGraph.parent(u));
142 inputGraph.eachEdge(function(e, u, v, value) {
143 if (value === undefined) value = {};
146 minLen: value.minLen || 1,
147 width: value.width || 0,
148 height: value.height || 0,
152 g.addEdge(null, u, v, newValue);
155 // Initial graph attributes
156 var graphValue = inputGraph.graph() || {};
158 rankDir: graphValue.rankDir || config.rankDir,
159 orderRestarts: graphValue.orderRestarts
165 function run(inputGraph) {
166 var rankSep = self.rankSep();
169 // Build internal graph
170 g = util.time('initLayoutGraph', initLayoutGraph)(inputGraph);
172 if (g.order() === 0) {
176 // Make space for edge labels
177 g.eachEdge(function(e, s, t, a) {
180 self.rankSep(rankSep / 2);
182 // Determine the rank for each node. Nodes with a lower rank will appear
183 // above nodes of higher rank.
184 util.time('rank.run', rank.run)(g, config.rankSimplex);
186 // Normalize the graph by ensuring that every edge is proper (each edge has
187 // a length of 1). We achieve this by adding dummy nodes to long edges,
188 // thus shortening them.
189 util.time('normalize', normalize)(g);
191 // Order the nodes so that edge crossings are minimized.
192 util.time('order', order)(g, config.orderMaxSweeps);
194 // Find the x and y coordinates for every node in the graph.
195 util.time('position', position.run)(g);
197 // De-normalize the graph by removing dummy nodes and augmenting the
198 // original long edges with coordinate information.
199 util.time('undoNormalize', undoNormalize)(g);
201 // Reverses points for edges that are in a reversed state.
202 util.time('fixupEdgePoints', fixupEdgePoints)(g);
204 // Restore delete edges and reverse edges that were reversed in the rank
206 util.time('rank.restoreEdges', rank.restoreEdges)(g);
208 // Construct final result graph and return it
209 return util.time('createFinalGraph', createFinalGraph)(g, inputGraph.isDirected());
211 self.rankSep(rankSep);
216 * This function is responsible for 'normalizing' the graph. The process of
217 * normalization ensures that no edge in the graph has spans more than one
218 * rank. To do this it inserts dummy nodes as needed and links them by adding
219 * dummy edges. This function keeps enough information in the dummy nodes and
220 * edges to ensure that the original graph can be reconstructed later.
222 * This method assumes that the input graph is cycle free.
224 function normalize(g) {
226 g.eachEdge(function(e, s, t, a) {
227 var sourceRank = g.node(s).rank;
228 var targetRank = g.node(t).rank;
229 if (sourceRank + 1 < targetRank) {
230 for (var u = s, rank = sourceRank + 1, i = 0; rank < targetRank; ++rank, ++i) {
231 var v = '_D' + (++dummyCount);
235 edge: { id: e, source: s, target: t, attrs: a },
240 // If this node represents a bend then we will use it as a control
241 // point. For edges with 2 segments this will be the center dummy
242 // node. For edges with more than two segments, this will be the
243 // first and last dummy node.
244 if (i === 0) node.index = 0;
245 else if (rank + 1 === targetRank) node.index = 1;
248 g.addEdge(null, u, v, {});
251 g.addEdge(null, u, t, {});
258 * Reconstructs the graph as it was before normalization. The positions of
259 * dummy nodes are used to build an array of points for the original 'long'
260 * edge. Dummy nodes and edges are removed.
262 function undoNormalize(g) {
263 g.eachNode(function(u, a) {
267 if (!g.hasEdge(edge.id)) {
268 g.addEdge(edge.id, edge.source, edge.target, edge.attrs);
270 var points = g.edge(edge.id).points;
271 points[a.index] = { x: a.x, y: a.y, ul: a.ul, ur: a.ur, dl: a.dl, dr: a.dr };
279 * For each edge that was reversed during the `acyclic` step, reverse its
282 function fixupEdgePoints(g) {
283 g.eachEdge(function(e, s, t, a) { if (a.reversed) a.points.reverse(); });
286 function createFinalGraph(g, isDirected) {
287 var out = isDirected ? new CDigraph() : new CGraph();
288 out.graph(g.graph());
289 g.eachNode(function(u, value) { out.addNode(u, value); });
290 g.eachNode(function(u) { out.parent(u, g.parent(u)); });
291 g.eachEdge(function(e, u, v, value) {
292 out.addEdge(value.e, u, v, value);
295 // Attach bounding box information
296 var maxX = 0, maxY = 0;
297 g.eachNode(function(u, value) {
298 if (!g.children(u).length) {
299 maxX = Math.max(maxX, value.x + value.width / 2);
300 maxY = Math.max(maxY, value.y + value.height / 2);
303 g.eachEdge(function(e, u, v, value) {
304 var maxXPoints = Math.max.apply(Math, value.points.map(function(p) { return p.x; }));
305 var maxYPoints = Math.max.apply(Math, value.points.map(function(p) { return p.y; }));
306 maxX = Math.max(maxX, maxXPoints + value.width / 2);
307 maxY = Math.max(maxY, maxYPoints + value.height / 2);
309 out.graph().width = maxX;
310 out.graph().height = maxY;
316 * Given a function, a new function is returned that invokes the given
317 * function. The return value from the function is always the `self` object.
319 function delegateProperty(f) {
321 if (!arguments.length) return f();
322 f.apply(null, arguments);
329 },{"./order":4,"./position":9,"./rank":10,"./util":17,"graphlib":24}],4:[function(require,module,exports){
330 var util = require('./util'),
331 crossCount = require('./order/crossCount'),
332 initLayerGraphs = require('./order/initLayerGraphs'),
333 initOrder = require('./order/initOrder'),
334 sortLayer = require('./order/sortLayer');
336 module.exports = order;
338 // The maximum number of sweeps to perform before finishing the order phase.
339 var DEFAULT_MAX_SWEEPS = 24;
340 order.DEFAULT_MAX_SWEEPS = DEFAULT_MAX_SWEEPS;
343 * Runs the order phase with the specified `graph, `maxSweeps`, and
344 * `debugLevel`. If `maxSweeps` is not specified we use `DEFAULT_MAX_SWEEPS`.
345 * If `debugLevel` is not set we assume 0.
347 function order(g, maxSweeps) {
348 if (arguments.length < 2) {
349 maxSweeps = DEFAULT_MAX_SWEEPS;
352 var restarts = g.graph().orderRestarts || 0;
354 var layerGraphs = initLayerGraphs(g);
355 // TODO: remove this when we add back support for ordering clusters
356 layerGraphs.forEach(function(lg) {
357 lg = lg.filterNodes(function(u) { return !g.children(u).length; });
362 allTimeBestCC = Number.MAX_VALUE,
365 function saveAllTimeBest() {
366 g.eachNode(function(u, value) { allTimeBest[u] = value.order; });
369 for (var j = 0; j < Number(restarts) + 1 && allTimeBestCC !== 0; ++j) {
370 currentBestCC = Number.MAX_VALUE;
371 initOrder(g, restarts > 0);
373 util.log(2, 'Order phase start cross count: ' + g.graph().orderInitCC);
376 for (i = 0, lastBest = 0; lastBest < 4 && i < maxSweeps && currentBestCC > 0; ++i, ++lastBest, ++iters) {
377 sweep(g, layerGraphs, i);
379 if (cc < currentBestCC) {
382 if (cc < allTimeBestCC) {
387 util.log(3, 'Order phase start ' + j + ' iter ' + i + ' cross count: ' + cc);
391 Object.keys(allTimeBest).forEach(function(u) {
392 if (!g.children || !g.children(u).length) {
393 g.node(u).order = allTimeBest[u];
396 g.graph().orderCC = allTimeBestCC;
398 util.log(2, 'Order iterations: ' + iters);
399 util.log(2, 'Order phase best cross count: ' + g.graph().orderCC);
402 function predecessorWeights(g, nodes) {
404 nodes.forEach(function(u) {
405 weights[u] = g.inEdges(u).map(function(e) {
406 return g.node(g.source(e)).order;
412 function successorWeights(g, nodes) {
414 nodes.forEach(function(u) {
415 weights[u] = g.outEdges(u).map(function(e) {
416 return g.node(g.target(e)).order;
422 function sweep(g, layerGraphs, iter) {
423 if (iter % 2 === 0) {
424 sweepDown(g, layerGraphs, iter);
426 sweepUp(g, layerGraphs, iter);
430 function sweepDown(g, layerGraphs) {
432 for (i = 1; i < layerGraphs.length; ++i) {
433 cg = sortLayer(layerGraphs[i], cg, predecessorWeights(g, layerGraphs[i].nodes()));
437 function sweepUp(g, layerGraphs) {
439 for (i = layerGraphs.length - 2; i >= 0; --i) {
440 sortLayer(layerGraphs[i], cg, successorWeights(g, layerGraphs[i].nodes()));
444 },{"./order/crossCount":5,"./order/initLayerGraphs":6,"./order/initOrder":7,"./order/sortLayer":8,"./util":17}],5:[function(require,module,exports){
445 var util = require('../util');
447 module.exports = crossCount;
450 * Returns the cross count for the given graph.
452 function crossCount(g) {
454 var ordering = util.ordering(g);
455 for (var i = 1; i < ordering.length; ++i) {
456 cc += twoLayerCrossCount(g, ordering[i-1], ordering[i]);
462 * This function searches through a ranked and ordered graph and counts the
463 * number of edges that cross. This algorithm is derived from:
465 * W. Barth et al., Bilayer Cross Counting, JGAA, 8(2) 179–194 (2004)
467 function twoLayerCrossCount(g, layer1, layer2) {
469 layer1.forEach(function(u) {
470 var nodeIndices = [];
471 g.outEdges(u).forEach(function(e) { nodeIndices.push(g.node(g.target(e)).order); });
472 nodeIndices.sort(function(x, y) { return x - y; });
473 indices = indices.concat(nodeIndices);
477 while (firstIndex < layer2.length) firstIndex <<= 1;
479 var treeSize = 2 * firstIndex - 1;
483 for (var i = 0; i < treeSize; ++i) { tree[i] = 0; }
486 indices.forEach(function(i) {
487 var treeIndex = i + firstIndex;
489 while (treeIndex > 0) {
491 cc += tree[treeIndex + 1];
493 treeIndex = (treeIndex - 1) >> 1;
501 },{"../util":17}],6:[function(require,module,exports){
502 var nodesFromList = require('graphlib').filter.nodesFromList,
504 Set = require('cp-data').Set;
506 module.exports = initLayerGraphs;
509 * This function takes a compound layered graph, g, and produces an array of
510 * layer graphs. Each entry in the array represents a subgraph of nodes
511 * relevant for performing crossing reduction on that layer.
513 function initLayerGraphs(g) {
518 g.children(u).forEach(function(v) { dfs(v); });
522 var value = g.node(u);
523 value.minRank = ('rank' in value) ? value.rank : Number.MAX_VALUE;
524 value.maxRank = ('rank' in value) ? value.rank : Number.MIN_VALUE;
525 var uRanks = new Set();
526 g.children(u).forEach(function(v) {
528 uRanks = Set.union([uRanks, rs]);
529 value.minRank = Math.min(value.minRank, g.node(v).minRank);
530 value.maxRank = Math.max(value.maxRank, g.node(v).maxRank);
533 if ('rank' in value) uRanks.add(value.rank);
535 uRanks.keys().forEach(function(r) {
536 if (!(r in ranks)) ranks[r] = [];
544 var layerGraphs = [];
545 ranks.forEach(function(us, rank) {
546 layerGraphs[rank] = g.filterNodes(nodesFromList(us));
552 },{"cp-data":19,"graphlib":24}],7:[function(require,module,exports){
553 var crossCount = require('./crossCount'),
554 util = require('../util');
556 module.exports = initOrder;
559 * Given a graph with a set of layered nodes (i.e. nodes that have a `rank`
560 * attribute) this function attaches an `order` attribute that uniquely
561 * arranges each node of each rank. If no constraint graph is provided the
562 * order of the nodes in each rank is entirely arbitrary.
564 function initOrder(g, random) {
567 g.eachNode(function(u, value) {
568 var layer = layers[value.rank];
569 if (g.children && g.children(u).length > 0) return;
571 layer = layers[value.rank] = [];
576 layers.forEach(function(layer) {
580 layer.forEach(function(u, i) {
585 var cc = crossCount(g);
586 g.graph().orderInitCC = cc;
587 g.graph().orderCC = Number.MAX_VALUE;
590 },{"../util":17,"./crossCount":5}],8:[function(require,module,exports){
591 var util = require('../util');
593 Digraph = require('graphlib').Digraph,
594 topsort = require('graphlib').alg.topsort,
595 nodesFromList = require('graphlib').filter.nodesFromList;
598 module.exports = sortLayer;
601 function sortLayer(g, cg, weights) {
602 var result = sortLayerSubgraph(g, null, cg, weights);
603 result.list.forEach(function(u, i) {
606 return result.constraintGraph;
610 function sortLayer(g, cg, weights) {
613 g.eachNode(function(u, value) {
614 ordering[value.order] = u;
617 bs[u] = util.sum(ws) / ws.length;
621 var toSort = g.nodes().filter(function(u) { return bs[u] !== undefined; });
622 toSort.sort(function(x, y) {
623 return bs[x] - bs[y] || g.node(x).order - g.node(y).order;
626 for (var i = 0, j = 0, jl = toSort.length; j < jl; ++i) {
627 if (bs[ordering[i]] !== undefined) {
628 g.node(toSort[j++]).order = i;
633 // TOOD: re-enable constrained sorting once we have a strategy for handling
634 // undefined barycenters.
636 function sortLayerSubgraph(g, sg, cg, weights) {
637 cg = cg ? cg.filterNodes(nodesFromList(g.children(sg))) : new Digraph();
640 g.children(sg).forEach(function(u) {
641 if (g.children(u).length) {
642 nodeData[u] = sortLayerSubgraph(g, u, cg, weights);
643 nodeData[u].firstSG = u;
644 nodeData[u].lastSG = u;
649 barycenter: ws.length > 0 ? util.sum(ws) / ws.length : 0,
655 resolveViolatedConstraints(g, cg, nodeData);
657 var keys = Object.keys(nodeData);
658 keys.sort(function(x, y) {
659 return nodeData[x].barycenter - nodeData[y].barycenter;
662 var result = keys.map(function(u) { return nodeData[u]; })
663 .reduce(function(lhs, rhs) { return mergeNodeData(g, lhs, rhs); });
668 function mergeNodeData(g, lhs, rhs) {
669 var cg = mergeDigraphs(lhs.constraintGraph, rhs.constraintGraph);
671 if (lhs.lastSG !== undefined && rhs.firstSG !== undefined) {
672 if (cg === undefined) {
675 if (!cg.hasNode(lhs.lastSG)) { cg.addNode(lhs.lastSG); }
676 cg.addNode(rhs.firstSG);
677 cg.addEdge(null, lhs.lastSG, rhs.firstSG);
681 degree: lhs.degree + rhs.degree,
682 barycenter: (lhs.barycenter * lhs.degree + rhs.barycenter * rhs.degree) /
683 (lhs.degree + rhs.degree),
684 list: lhs.list.concat(rhs.list),
685 firstSG: lhs.firstSG !== undefined ? lhs.firstSG : rhs.firstSG,
686 lastSG: rhs.lastSG !== undefined ? rhs.lastSG : lhs.lastSG,
691 function mergeDigraphs(lhs, rhs) {
692 if (lhs === undefined) return rhs;
693 if (rhs === undefined) return lhs;
696 rhs.nodes().forEach(function(u) { lhs.addNode(u); });
697 rhs.edges().forEach(function(e, u, v) { lhs.addEdge(null, u, v); });
701 function resolveViolatedConstraints(g, cg, nodeData) {
702 // Removes nodes `u` and `v` from `cg` and makes any edges incident on them
703 // incident on `w` instead.
704 function collapseNodes(u, v, w) {
705 // TODO original paper removes self loops, but it is not obvious when this would happen
706 cg.inEdges(u).forEach(function(e) {
708 cg.addEdge(null, cg.source(e), w);
711 cg.outEdges(v).forEach(function(e) {
713 cg.addEdge(null, w, cg.target(e));
721 while ((violated = findViolatedConstraint(cg, nodeData)) !== undefined) {
722 var source = cg.source(violated),
723 target = cg.target(violated);
726 while ((v = cg.addNode(null)) && g.hasNode(v)) {
730 // Collapse barycenter and list
731 nodeData[v] = mergeNodeData(g, nodeData[source], nodeData[target]);
732 delete nodeData[source];
733 delete nodeData[target];
735 collapseNodes(source, target, v);
736 if (cg.incidentEdges(v).length === 0) { cg.delNode(v); }
740 function findViolatedConstraint(cg, nodeData) {
741 var us = topsort(cg);
742 for (var i = 0; i < us.length; ++i) {
744 var inEdges = cg.inEdges(u);
745 for (var j = 0; j < inEdges.length; ++j) {
747 if (nodeData[cg.source(e)].barycenter >= nodeData[u].barycenter) {
755 },{"../util":17}],9:[function(require,module,exports){
756 var util = require('./util');
759 * The algorithms here are based on Brandes and Köpf, "Fast and Simple
760 * Horizontal Coordinate Assignment".
762 module.exports = function() {
763 // External configuration
773 self.nodeSep = util.propertyAccessor(self, config, 'nodeSep');
774 self.edgeSep = util.propertyAccessor(self, config, 'edgeSep');
775 // If not null this separation value is used for all nodes and edges
776 // regardless of their widths. `nodeSep` and `edgeSep` are ignored with this
778 self.universalSep = util.propertyAccessor(self, config, 'universalSep');
779 self.rankSep = util.propertyAccessor(self, config, 'rankSep');
780 self.debugLevel = util.propertyAccessor(self, config, 'debugLevel');
787 g = g.filterNodes(util.filterNonSubgraphs(g));
789 var layering = util.ordering(g);
791 var conflicts = findConflicts(g, layering);
794 ['u', 'd'].forEach(function(vertDir) {
795 if (vertDir === 'd') layering.reverse();
797 ['l', 'r'].forEach(function(horizDir) {
798 if (horizDir === 'r') reverseInnerOrder(layering);
800 var dir = vertDir + horizDir;
801 var align = verticalAlignment(g, layering, conflicts, vertDir === 'u' ? 'predecessors' : 'successors');
802 xss[dir]= horizontalCompaction(g, layering, align.pos, align.root, align.align);
804 if (config.debugLevel >= 3)
805 debugPositioning(vertDir + horizDir, g, layering, xss[dir]);
807 if (horizDir === 'r') flipHorizontally(xss[dir]);
809 if (horizDir === 'r') reverseInnerOrder(layering);
812 if (vertDir === 'd') layering.reverse();
815 balance(g, layering, xss);
817 g.eachNode(function(v) {
819 for (var alignment in xss) {
820 var alignmentX = xss[alignment][v];
821 posXDebug(alignment, g, v, alignmentX);
824 xs.sort(function(x, y) { return x - y; });
825 posX(g, v, (xs[1] + xs[2]) / 2);
828 // Align y coordinates with ranks
829 var y = 0, reverseY = g.graph().rankDir === 'BT' || g.graph().rankDir === 'RL';
830 layering.forEach(function(layer) {
831 var maxHeight = util.max(layer.map(function(u) { return height(g, u); }));
833 layer.forEach(function(u) {
834 posY(g, u, reverseY ? -y : y);
836 y += maxHeight / 2 + config.rankSep;
839 // Translate layout so that top left corner of bounding rectangle has
840 // coordinate (0, 0).
841 var minX = util.min(g.nodes().map(function(u) { return posX(g, u) - width(g, u) / 2; }));
842 var minY = util.min(g.nodes().map(function(u) { return posY(g, u) - height(g, u) / 2; }));
843 g.eachNode(function(u) {
844 posX(g, u, posX(g, u) - minX);
845 posY(g, u, posY(g, u) - minY);
850 * Generate an ID that can be used to represent any undirected edge that is
851 * incident on `u` and `v`.
853 function undirEdgeId(u, v) {
855 ? u.toString().length + ':' + u + '-' + v
856 : v.toString().length + ':' + v + '-' + u;
859 function findConflicts(g, layering) {
860 var conflicts = {}, // Set of conflicting edge ids
861 pos = {}, // Position of node in its layer
864 k0, // Position of the last inner segment in the previous layer
865 l, // Current position in the current layer (for iteration up to `l1`)
866 k1; // Position of the next inner segment in the previous layer or
867 // the position of the last element in the previous layer
869 if (layering.length <= 2) return conflicts;
871 function updateConflicts(v) {
873 if (k < k0 || k > k1) {
874 conflicts[undirEdgeId(currLayer[l], v)] = true;
878 layering[1].forEach(function(u, i) { pos[u] = i; });
879 for (var i = 1; i < layering.length - 1; ++i) {
880 prevLayer = layering[i];
881 currLayer = layering[i+1];
885 // Scan current layer for next node that is incident to an inner segement
886 // between layering[i+1] and layering[i].
887 for (var l1 = 0; l1 < currLayer.length; ++l1) {
888 var u = currLayer[l1]; // Next inner segment in the current layer or
889 // last node in the current layer
893 if (g.node(u).dummy) {
894 var uPred = g.predecessors(u)[0];
895 // Note: In the case of self loops and sideways edges it is possible
896 // for a dummy not to have a predecessor.
897 if (uPred !== undefined && g.node(uPred).dummy)
900 if (k1 === undefined && l1 === currLayer.length - 1)
901 k1 = prevLayer.length - 1;
903 if (k1 !== undefined) {
904 for (; l <= l1; ++l) {
905 g.predecessors(currLayer[l]).forEach(updateConflicts);
915 function verticalAlignment(g, layering, conflicts, relationship) {
916 var pos = {}, // Position for a node in its layer
917 root = {}, // Root of the block that the node participates in
918 align = {}; // Points to the next node in the block or, if the last
919 // element in the block, points to the first block's root
921 layering.forEach(function(layer) {
922 layer.forEach(function(u, i) {
929 layering.forEach(function(layer) {
931 layer.forEach(function(v) {
932 var related = g[relationship](v), // Adjacent nodes from the previous layer
933 mid; // The mid point in the related array
935 if (related.length > 0) {
936 related.sort(function(x, y) { return pos[x] - pos[y]; });
937 mid = (related.length - 1) / 2;
938 related.slice(Math.floor(mid), Math.ceil(mid) + 1).forEach(function(u) {
939 if (align[v] === v) {
940 if (!conflicts[undirEdgeId(u, v)] && prevIdx < pos[u]) {
942 align[v] = root[v] = root[u];
951 return { pos: pos, root: root, align: align };
954 // This function deviates from the standard BK algorithm in two ways. First
955 // it takes into account the size of the nodes. Second it includes a fix to
956 // the original algorithm that is described in Carstens, "Node and Label
957 // Placement in a Layered Layout Algorithm".
958 function horizontalCompaction(g, layering, pos, root, align) {
959 var sink = {}, // Mapping of node id -> sink node id for class
960 maybeShift = {}, // Mapping of sink node id -> { class node id, min shift }
961 shift = {}, // Mapping of sink node id -> shift
962 pred = {}, // Mapping of node id -> predecessor node (or null)
963 xs = {}; // Calculated X positions
965 layering.forEach(function(layer) {
966 layer.forEach(function(u, i) {
970 pred[u] = layer[i - 1];
974 function updateShift(toShift, neighbor, delta) {
975 if (!(neighbor in maybeShift[toShift])) {
976 maybeShift[toShift][neighbor] = delta;
978 maybeShift[toShift][neighbor] = Math.min(maybeShift[toShift][neighbor], delta);
982 function placeBlock(v) {
988 var u = root[pred[w]];
993 var delta = sep(g, pred[w]) + sep(g, w);
994 if (sink[v] !== sink[u]) {
995 updateShift(sink[u], sink[v], xs[v] - xs[u] - delta);
997 xs[v] = Math.max(xs[v], xs[u] + delta);
1005 // Root coordinates relative to sink
1006 util.values(root).forEach(function(v) {
1010 // Absolute coordinates
1011 // There is an assumption here that we've resolved shifts for any classes
1012 // that begin at an earlier layer. We guarantee this by visiting layers in
1014 layering.forEach(function(layer) {
1015 layer.forEach(function(v) {
1016 xs[v] = xs[root[v]];
1017 if (v === root[v] && v === sink[v]) {
1019 if (v in maybeShift && Object.keys(maybeShift[v]).length > 0) {
1020 minShift = util.min(Object.keys(maybeShift[v])
1022 return maybeShift[v][u] + (u in shift ? shift[u] : 0);
1026 shift[v] = minShift;
1031 layering.forEach(function(layer) {
1032 layer.forEach(function(v) {
1033 xs[v] += shift[sink[root[v]]] || 0;
1040 function findMinCoord(g, layering, xs) {
1041 return util.min(layering.map(function(layer) {
1047 function findMaxCoord(g, layering, xs) {
1048 return util.max(layering.map(function(layer) {
1049 var u = layer[layer.length - 1];
1054 function balance(g, layering, xss) {
1055 var min = {}, // Min coordinate for the alignment
1056 max = {}, // Max coordinate for the alginment
1058 shift = {}; // Amount to shift a given alignment
1060 function updateAlignment(v) {
1061 xss[alignment][v] += shift[alignment];
1064 var smallest = Number.POSITIVE_INFINITY;
1065 for (var alignment in xss) {
1066 var xs = xss[alignment];
1067 min[alignment] = findMinCoord(g, layering, xs);
1068 max[alignment] = findMaxCoord(g, layering, xs);
1069 var w = max[alignment] - min[alignment];
1072 smallestAlignment = alignment;
1076 // Determine how much to adjust positioning for each alignment
1077 ['u', 'd'].forEach(function(vertDir) {
1078 ['l', 'r'].forEach(function(horizDir) {
1079 var alignment = vertDir + horizDir;
1080 shift[alignment] = horizDir === 'l'
1081 ? min[smallestAlignment] - min[alignment]
1082 : max[smallestAlignment] - max[alignment];
1086 // Find average of medians for xss array
1087 for (alignment in xss) {
1088 g.eachNode(updateAlignment);
1092 function flipHorizontally(xs) {
1098 function reverseInnerOrder(layering) {
1099 layering.forEach(function(layer) {
1104 function width(g, u) {
1105 switch (g.graph().rankDir) {
1106 case 'LR': return g.node(u).height;
1107 case 'RL': return g.node(u).height;
1108 default: return g.node(u).width;
1112 function height(g, u) {
1113 switch(g.graph().rankDir) {
1114 case 'LR': return g.node(u).width;
1115 case 'RL': return g.node(u).width;
1116 default: return g.node(u).height;
1120 function sep(g, u) {
1121 if (config.universalSep !== null) {
1122 return config.universalSep;
1124 var w = width(g, u);
1125 var s = g.node(u).dummy ? config.edgeSep : config.nodeSep;
1129 function posX(g, u, x) {
1130 if (g.graph().rankDir === 'LR' || g.graph().rankDir === 'RL') {
1131 if (arguments.length < 3) {
1137 if (arguments.length < 3) {
1145 function posXDebug(name, g, u, x) {
1146 if (g.graph().rankDir === 'LR' || g.graph().rankDir === 'RL') {
1147 if (arguments.length < 3) {
1148 return g.node(u)[name];
1150 g.node(u)[name] = x;
1153 if (arguments.length < 3) {
1154 return g.node(u)[name];
1156 g.node(u)[name] = x;
1161 function posY(g, u, y) {
1162 if (g.graph().rankDir === 'LR' || g.graph().rankDir === 'RL') {
1163 if (arguments.length < 3) {
1169 if (arguments.length < 3) {
1177 function debugPositioning(align, g, layering, xs) {
1178 layering.forEach(function(l, li) {
1180 l.forEach(function(v) {
1183 var s = sep(g, u) + sep(g, v);
1185 console.log('Position phase: sep violation. Align: ' + align + '. Layer: ' + li + '. ' +
1186 'U: ' + u + ' V: ' + v + '. Actual sep: ' + (xV - xU) + ' Expected sep: ' + s);
1195 },{"./util":17}],10:[function(require,module,exports){
1196 var util = require('./util'),
1197 acyclic = require('./rank/acyclic'),
1198 initRank = require('./rank/initRank'),
1199 feasibleTree = require('./rank/feasibleTree'),
1200 constraints = require('./rank/constraints'),
1201 simplex = require('./rank/simplex'),
1202 components = require('graphlib').alg.components,
1203 filter = require('graphlib').filter;
1206 exports.restoreEdges = restoreEdges;
1209 * Heuristic function that assigns a rank to each node of the input graph with
1210 * the intent of minimizing edge lengths, while respecting the `minLen`
1211 * attribute of incident edges.
1215 * * Each edge in the input graph must have an assigned 'minLen' attribute
1217 function run(g, useSimplex) {
1220 // If there are rank constraints on nodes, then build a new graph that
1221 // encodes the constraints.
1222 util.time('constraints.apply', constraints.apply)(g);
1224 expandSidewaysEdges(g);
1226 // Reverse edges to get an acyclic graph, we keep the graph in an acyclic
1227 // state until the very end.
1228 util.time('acyclic', acyclic)(g);
1230 // Convert the graph into a flat graph for ranking
1231 var flatGraph = g.filterNodes(util.filterNonSubgraphs(g));
1233 // Assign an initial ranking using DFS.
1234 initRank(flatGraph);
1236 // For each component improve the assigned ranks.
1237 components(flatGraph).forEach(function(cmpt) {
1238 var subgraph = flatGraph.filterNodes(filter.nodesFromList(cmpt));
1239 rankComponent(subgraph, useSimplex);
1242 // Relax original constraints
1243 util.time('constraints.relax', constraints.relax(g));
1245 // When handling nodes with constrained ranks it is possible to end up with
1246 // edges that point to previous ranks. Most of the subsequent algorithms assume
1247 // that edges are pointing to successive ranks only. Here we reverse any "back
1248 // edges" and mark them as such. The acyclic algorithm will reverse them as a
1249 // post processing step.
1250 util.time('reorientEdges', reorientEdges)(g);
1253 function restoreEdges(g) {
1258 * Expand self loops into three dummy nodes. One will sit above the incident
1259 * node, one will be at the same level, and one below. The result looks like:
1265 * Dummy nodes x, y, z give us the shape of a loop and node y is where we place
1268 * TODO: consolidate knowledge of dummy node construction.
1269 * TODO: support minLen = 2
1271 function expandSelfLoops(g) {
1272 g.eachEdge(function(e, u, v, a) {
1274 var x = addDummyNode(g, e, u, v, a, 0, false),
1275 y = addDummyNode(g, e, u, v, a, 1, true),
1276 z = addDummyNode(g, e, u, v, a, 2, false);
1277 g.addEdge(null, x, u, {minLen: 1, selfLoop: true});
1278 g.addEdge(null, x, y, {minLen: 1, selfLoop: true});
1279 g.addEdge(null, u, z, {minLen: 1, selfLoop: true});
1280 g.addEdge(null, y, z, {minLen: 1, selfLoop: true});
1286 function expandSidewaysEdges(g) {
1287 g.eachEdge(function(e, u, v, a) {
1289 var origEdge = a.originalEdge,
1290 dummy = addDummyNode(g, origEdge.e, origEdge.u, origEdge.v, origEdge.value, 0, true);
1291 g.addEdge(null, u, dummy, {minLen: 1});
1292 g.addEdge(null, dummy, v, {minLen: 1});
1298 function addDummyNode(g, e, u, v, a, index, isLabel) {
1299 return g.addNode(null, {
1300 width: isLabel ? a.width : 0,
1301 height: isLabel ? a.height : 0,
1302 edge: { id: e, source: u, target: v, attrs: a },
1308 function reorientEdges(g) {
1309 g.eachEdge(function(e, u, v, value) {
1310 if (g.node(u).rank > g.node(v).rank) {
1312 value.reversed = true;
1313 g.addEdge(e, v, u, value);
1318 function rankComponent(subgraph, useSimplex) {
1319 var spanningTree = feasibleTree(subgraph);
1322 util.log(1, 'Using network simplex for ranking');
1323 simplex(subgraph, spanningTree);
1325 normalize(subgraph);
1328 function normalize(g) {
1329 var m = util.min(g.nodes().map(function(u) { return g.node(u).rank; }));
1330 g.eachNode(function(u, node) { node.rank -= m; });
1333 },{"./rank/acyclic":11,"./rank/constraints":12,"./rank/feasibleTree":13,"./rank/initRank":14,"./rank/simplex":16,"./util":17,"graphlib":24}],11:[function(require,module,exports){
1334 var util = require('../util');
1336 module.exports = acyclic;
1337 module.exports.undo = undo;
1340 * This function takes a directed graph that may have cycles and reverses edges
1341 * as appropriate to break these cycles. Each reversed edge is assigned a
1342 * `reversed` attribute with the value `true`.
1344 * There should be no self loops in the graph.
1346 function acyclic(g) {
1352 if (u in visited) return;
1353 visited[u] = onStack[u] = true;
1354 g.outEdges(u).forEach(function(e) {
1355 var t = g.target(e),
1359 console.error('Warning: found self loop "' + e + '" for node "' + u + '"');
1360 } else if (t in onStack) {
1363 value.reversed = true;
1365 g.addEdge(e, t, u, value);
1374 g.eachNode(function(u) { dfs(u); });
1376 util.log(2, 'Acyclic Phase: reversed ' + reverseCount + ' edge(s)');
1378 return reverseCount;
1382 * Given a graph that has had the acyclic operation applied, this function
1383 * undoes that operation. More specifically, any edge with the `reversed`
1384 * attribute is again reversed to restore the original direction of the edge.
1387 g.eachEdge(function(e, s, t, a) {
1391 g.addEdge(e, t, s, a);
1396 },{"../util":17}],12:[function(require,module,exports){
1397 exports.apply = function(g) {
1400 g.children(sg).forEach(function(u) {
1401 if (g.children(u).length) {
1406 var value = g.node(u),
1407 prefRank = value.prefRank;
1408 if (prefRank !== undefined) {
1409 if (!checkSupportedPrefRank(prefRank)) { return; }
1411 if (!(prefRank in rankSets)) {
1412 rankSets.prefRank = [u];
1414 rankSets.prefRank.push(u);
1417 var newU = rankSets[prefRank];
1418 if (newU === undefined) {
1419 newU = rankSets[prefRank] = g.addNode(null, { originalNodes: [] });
1423 redirectInEdges(g, u, newU, prefRank === 'min');
1424 redirectOutEdges(g, u, newU, prefRank === 'max');
1426 // Save original node and remove it from reduced graph
1427 g.node(newU).originalNodes.push({ u: u, value: value, parent: sg });
1432 addLightEdgesFromMinNode(g, sg, rankSets.min);
1433 addLightEdgesToMaxNode(g, sg, rankSets.max);
1439 function checkSupportedPrefRank(prefRank) {
1440 if (prefRank !== 'min' && prefRank !== 'max' && prefRank.indexOf('same_') !== 0) {
1441 console.error('Unsupported rank type: ' + prefRank);
1447 function redirectInEdges(g, u, newU, reverse) {
1448 g.inEdges(u).forEach(function(e) {
1449 var origValue = g.edge(e),
1451 if (origValue.originalEdge) {
1455 originalEdge: { e: e, u: g.source(e), v: g.target(e), value: origValue },
1456 minLen: g.edge(e).minLen
1460 // Do not reverse edges for self-loops.
1461 if (origValue.selfLoop) {
1466 // Ensure that all edges to min are reversed
1467 g.addEdge(null, newU, g.source(e), value);
1468 value.reversed = true;
1470 g.addEdge(null, g.source(e), newU, value);
1475 function redirectOutEdges(g, u, newU, reverse) {
1476 g.outEdges(u).forEach(function(e) {
1477 var origValue = g.edge(e),
1479 if (origValue.originalEdge) {
1483 originalEdge: { e: e, u: g.source(e), v: g.target(e), value: origValue },
1484 minLen: g.edge(e).minLen
1488 // Do not reverse edges for self-loops.
1489 if (origValue.selfLoop) {
1494 // Ensure that all edges from max are reversed
1495 g.addEdge(null, g.target(e), newU, value);
1496 value.reversed = true;
1498 g.addEdge(null, newU, g.target(e), value);
1503 function addLightEdgesFromMinNode(g, sg, minNode) {
1504 if (minNode !== undefined) {
1505 g.children(sg).forEach(function(u) {
1506 // The dummy check ensures we don't add an edge if the node is involved
1507 // in a self loop or sideways edge.
1508 if (u !== minNode && !g.outEdges(minNode, u).length && !g.node(u).dummy) {
1509 g.addEdge(null, minNode, u, { minLen: 0 });
1515 function addLightEdgesToMaxNode(g, sg, maxNode) {
1516 if (maxNode !== undefined) {
1517 g.children(sg).forEach(function(u) {
1518 // The dummy check ensures we don't add an edge if the node is involved
1519 // in a self loop or sideways edge.
1520 if (u !== maxNode && !g.outEdges(u, maxNode).length && !g.node(u).dummy) {
1521 g.addEdge(null, u, maxNode, { minLen: 0 });
1528 * This function "relaxes" the constraints applied previously by the "apply"
1529 * function. It expands any nodes that were collapsed and assigns the rank of
1530 * the collapsed node to each of the expanded nodes. It also restores the
1531 * original edges and removes any dummy edges pointing at the collapsed nodes.
1533 * Note that the process of removing collapsed nodes also removes dummy edges
1536 exports.relax = function(g) {
1537 // Save original edges
1538 var originalEdges = [];
1539 g.eachEdge(function(e, u, v, value) {
1540 var originalEdge = value.originalEdge;
1542 originalEdges.push(originalEdge);
1546 // Expand collapsed nodes
1547 g.eachNode(function(u, value) {
1548 var originalNodes = value.originalNodes;
1549 if (originalNodes) {
1550 originalNodes.forEach(function(originalNode) {
1551 originalNode.value.rank = value.rank;
1552 g.addNode(originalNode.u, originalNode.value);
1553 g.parent(originalNode.u, originalNode.parent);
1559 // Restore original edges
1560 originalEdges.forEach(function(edge) {
1561 g.addEdge(edge.e, edge.u, edge.v, edge.value);
1565 },{}],13:[function(require,module,exports){
1567 var Set = require('cp-data').Set,
1569 Digraph = require('graphlib').Digraph,
1570 util = require('../util');
1572 module.exports = feasibleTree;
1575 * Given an acyclic graph with each node assigned a `rank` attribute, this
1576 * function constructs and returns a spanning tree. This function may reduce
1577 * the length of some edges from the initial rank assignment while maintaining
1578 * the `minLen` specified by each edge.
1582 * * The input graph is acyclic
1583 * * Each node in the input graph has an assigned `rank` attribute
1584 * * Each edge in the input graph has an assigned `minLen` attribute
1588 * A feasible spanning tree for the input graph (i.e. a spanning tree that
1589 * respects each graph edge's `minLen` attribute) represented as a Digraph with
1590 * a `root` attribute on graph.
1592 * Nodes have the same id and value as that in the input graph.
1594 * Edges in the tree have arbitrarily assigned ids. The attributes for edges
1595 * include `reversed`. `reversed` indicates that the edge is a
1596 * back edge in the input graph.
1598 function feasibleTree(g) {
1599 var remaining = new Set(g.nodes()),
1600 tree = new Digraph();
1602 if (remaining.size() === 1) {
1603 var root = g.nodes()[0];
1604 tree.addNode(root, {});
1605 tree.graph({ root: root });
1609 function addTightEdges(v) {
1610 var continueToScan = true;
1611 g.predecessors(v).forEach(function(u) {
1612 if (remaining.has(u) && !slack(g, u, v)) {
1613 if (remaining.has(v)) {
1614 tree.addNode(v, {});
1615 remaining.remove(v);
1616 tree.graph({ root: v });
1619 tree.addNode(u, {});
1620 tree.addEdge(null, u, v, { reversed: true });
1621 remaining.remove(u);
1623 continueToScan = false;
1627 g.successors(v).forEach(function(w) {
1628 if (remaining.has(w) && !slack(g, v, w)) {
1629 if (remaining.has(v)) {
1630 tree.addNode(v, {});
1631 remaining.remove(v);
1632 tree.graph({ root: v });
1635 tree.addNode(w, {});
1636 tree.addEdge(null, v, w, {});
1637 remaining.remove(w);
1639 continueToScan = false;
1642 return continueToScan;
1645 function createTightEdge() {
1646 var minSlack = Number.MAX_VALUE;
1647 remaining.keys().forEach(function(v) {
1648 g.predecessors(v).forEach(function(u) {
1649 if (!remaining.has(u)) {
1650 var edgeSlack = slack(g, u, v);
1651 if (Math.abs(edgeSlack) < Math.abs(minSlack)) {
1652 minSlack = -edgeSlack;
1657 g.successors(v).forEach(function(w) {
1658 if (!remaining.has(w)) {
1659 var edgeSlack = slack(g, v, w);
1660 if (Math.abs(edgeSlack) < Math.abs(minSlack)) {
1661 minSlack = edgeSlack;
1667 tree.eachNode(function(u) { g.node(u).rank -= minSlack; });
1670 while (remaining.size()) {
1671 var nodesToSearch = !tree.order() ? remaining.keys() : tree.nodes();
1672 for (var i = 0, il = nodesToSearch.length;
1673 i < il && addTightEdges(nodesToSearch[i]);
1675 if (remaining.size()) {
1683 function slack(g, u, v) {
1684 var rankDiff = g.node(v).rank - g.node(u).rank;
1685 var maxMinLen = util.max(g.outEdges(u, v)
1686 .map(function(e) { return g.edge(e).minLen; }));
1687 return rankDiff - maxMinLen;
1690 },{"../util":17,"cp-data":19,"graphlib":24}],14:[function(require,module,exports){
1691 var util = require('../util'),
1692 topsort = require('graphlib').alg.topsort;
1694 module.exports = initRank;
1697 * Assigns a `rank` attribute to each node in the input graph and ensures that
1698 * this rank respects the `minLen` attribute of incident edges.
1702 * * The input graph must be acyclic
1703 * * Each edge in the input graph must have an assigned 'minLen' attribute
1705 function initRank(g) {
1706 var sorted = topsort(g);
1708 sorted.forEach(function(u) {
1709 var inEdges = g.inEdges(u);
1710 if (inEdges.length === 0) {
1715 var minLens = inEdges.map(function(e) {
1716 return g.node(g.source(e)).rank + g.edge(e).minLen;
1718 g.node(u).rank = util.max(minLens);
1722 },{"../util":17,"graphlib":24}],15:[function(require,module,exports){
1728 * A helper to calculate the slack between two nodes (`u` and `v`) given a
1729 * `minLen` constraint. The slack represents how much the distance between `u`
1730 * and `v` could shrink while maintaining the `minLen` constraint. If the value
1731 * is negative then the constraint is currently violated.
1733 This function requires that `u` and `v` are in `graph` and they both have a
1736 function slack(graph, u, v, minLen) {
1737 return Math.abs(graph.node(u).rank - graph.node(v).rank) - minLen;
1740 },{}],16:[function(require,module,exports){
1741 var util = require('../util'),
1742 rankUtil = require('./rankUtil');
1744 module.exports = simplex;
1746 function simplex(graph, spanningTree) {
1747 // The network simplex algorithm repeatedly replaces edges of
1748 // the spanning tree with negative cut values until no such
1750 initCutValues(graph, spanningTree);
1752 var e = leaveEdge(spanningTree);
1753 if (e === null) break;
1754 var f = enterEdge(graph, spanningTree, e);
1755 exchange(graph, spanningTree, e, f);
1760 * Set the cut values of edges in the spanning tree by a depth-first
1761 * postorder traversal. The cut value corresponds to the cost, in
1762 * terms of a ranking's edge length sum, of lengthening an edge.
1763 * Negative cut values typically indicate edges that would yield a
1764 * smaller edge length sum if they were lengthened.
1766 function initCutValues(graph, spanningTree) {
1767 computeLowLim(spanningTree);
1769 spanningTree.eachEdge(function(id, u, v, treeValue) {
1770 treeValue.cutValue = 0;
1773 // Propagate cut values up the tree.
1775 var children = spanningTree.successors(n);
1776 for (var c in children) {
1777 var child = children[c];
1780 if (n !== spanningTree.graph().root) {
1781 setCutValue(graph, spanningTree, n);
1784 dfs(spanningTree.graph().root);
1788 * Perform a DFS postorder traversal, labeling each node v with
1789 * its traversal order 'lim(v)' and the minimum traversal number
1790 * of any of its descendants 'low(v)'. This provides an efficient
1791 * way to test whether u is an ancestor of v since
1792 * low(u) <= lim(v) <= lim(u) if and only if u is an ancestor.
1794 function computeLowLim(tree) {
1795 var postOrderNum = 0;
1798 var children = tree.successors(n);
1799 var low = postOrderNum;
1800 for (var c in children) {
1801 var child = children[c];
1803 low = Math.min(low, tree.node(child).low);
1805 tree.node(n).low = low;
1806 tree.node(n).lim = postOrderNum++;
1809 dfs(tree.graph().root);
1813 * To compute the cut value of the edge parent -> child, we consider
1814 * it and any other graph edges to or from the child.
1821 function setCutValue(graph, tree, child) {
1822 var parentEdge = tree.inEdges(child)[0];
1824 // List of child's children in the spanning tree.
1825 var grandchildren = [];
1826 var grandchildEdges = tree.outEdges(child);
1827 for (var gce in grandchildEdges) {
1828 grandchildren.push(tree.target(grandchildEdges[gce]));
1833 // TODO: Replace unit increment/decrement with edge weights.
1834 var E = 0; // Edges from child to grandchild's subtree.
1835 var F = 0; // Edges to child from grandchild's subtree.
1836 var G = 0; // Edges from child to nodes outside of child's subtree.
1837 var H = 0; // Edges from nodes outside of child's subtree to child.
1839 // Consider all graph edges from child.
1840 var outEdges = graph.outEdges(child);
1842 for (var oe in outEdges) {
1843 var succ = graph.target(outEdges[oe]);
1844 for (gc in grandchildren) {
1845 if (inSubtree(tree, succ, grandchildren[gc])) {
1849 if (!inSubtree(tree, succ, child)) {
1854 // Consider all graph edges to child.
1855 var inEdges = graph.inEdges(child);
1856 for (var ie in inEdges) {
1857 var pred = graph.source(inEdges[ie]);
1858 for (gc in grandchildren) {
1859 if (inSubtree(tree, pred, grandchildren[gc])) {
1863 if (!inSubtree(tree, pred, child)) {
1868 // Contributions depend on the alignment of the parent -> child edge
1869 // and the child -> u or v edges.
1870 var grandchildCutSum = 0;
1871 for (gc in grandchildren) {
1872 var cv = tree.edge(grandchildEdges[gc]).cutValue;
1873 if (!tree.edge(grandchildEdges[gc]).reversed) {
1874 grandchildCutSum += cv;
1876 grandchildCutSum -= cv;
1880 if (!tree.edge(parentEdge).reversed) {
1881 cutValue += grandchildCutSum - E + F - G + H;
1883 cutValue -= grandchildCutSum - E + F - G + H;
1886 tree.edge(parentEdge).cutValue = cutValue;
1890 * Return whether n is a node in the subtree with the given
1893 function inSubtree(tree, n, root) {
1894 return (tree.node(root).low <= tree.node(n).lim &&
1895 tree.node(n).lim <= tree.node(root).lim);
1899 * Return an edge from the tree with a negative cut value, or null if there
1902 function leaveEdge(tree) {
1903 var edges = tree.edges();
1904 for (var n in edges) {
1906 var treeValue = tree.edge(e);
1907 if (treeValue.cutValue < 0) {
1915 * The edge e should be an edge in the tree, with an underlying edge
1916 * in the graph, with a negative cut value. Of the two nodes incident
1917 * on the edge, take the lower one. enterEdge returns an edge with
1918 * minimum slack going from outside of that node's subtree to inside
1919 * of that node's subtree.
1921 function enterEdge(graph, tree, e) {
1922 var source = tree.source(e);
1923 var target = tree.target(e);
1924 var lower = tree.node(target).lim < tree.node(source).lim ? target : source;
1926 // Is the tree edge aligned with the graph edge?
1927 var aligned = !tree.edge(e).reversed;
1929 var minSlack = Number.POSITIVE_INFINITY;
1932 graph.eachEdge(function(id, u, v, value) {
1933 if (id !== e && inSubtree(tree, u, lower) && !inSubtree(tree, v, lower)) {
1934 var slack = rankUtil.slack(graph, u, v, value.minLen);
1935 if (slack < minSlack) {
1942 graph.eachEdge(function(id, u, v, value) {
1943 if (id !== e && !inSubtree(tree, u, lower) && inSubtree(tree, v, lower)) {
1944 var slack = rankUtil.slack(graph, u, v, value.minLen);
1945 if (slack < minSlack) {
1953 if (minSlackEdge === undefined) {
1956 graph.eachNode(function(id) {
1957 if (!inSubtree(tree, id, lower)) {
1963 throw new Error('No edge found from outside of tree to inside');
1966 return minSlackEdge;
1970 * Replace edge e with edge f in the tree, recalculating the tree root,
1971 * the nodes' low and lim properties and the edges' cut values.
1973 function exchange(graph, tree, e, f) {
1975 var source = graph.source(f);
1976 var target = graph.target(f);
1978 // Redirect edges so that target is the root of its subtree.
1979 function redirect(v) {
1980 var edges = tree.inEdges(v);
1981 for (var i in edges) {
1983 var u = tree.source(e);
1984 var value = tree.edge(e);
1987 value.reversed = !value.reversed;
1988 tree.addEdge(e, v, u, value);
1995 var edges = tree.inEdges(root);
1996 while (edges.length > 0) {
1997 root = tree.source(edges[0]);
1998 edges = tree.inEdges(root);
2001 tree.graph().root = root;
2003 tree.addEdge(null, source, target, {cutValue: 0});
2005 initCutValues(graph, tree);
2007 adjustRanks(graph, tree);
2011 * Reset the ranks of all nodes based on the current spanning tree.
2012 * The rank of the tree's root remains unchanged, while all other
2013 * nodes are set to the sum of minimum length constraints along
2014 * the path from the root.
2016 function adjustRanks(graph, tree) {
2018 var children = tree.successors(p);
2019 children.forEach(function(c) {
2020 var minLen = minimumLength(graph, p, c);
2021 graph.node(c).rank = graph.node(p).rank + minLen;
2026 dfs(tree.graph().root);
2030 * If u and v are connected by some edges in the graph, return the
2031 * minimum length of those edges, as a positive number if v succeeds
2032 * u and as a negative number if v precedes u.
2034 function minimumLength(graph, u, v) {
2035 var outEdges = graph.outEdges(u, v);
2036 if (outEdges.length > 0) {
2037 return util.max(outEdges.map(function(e) {
2038 return graph.edge(e).minLen;
2042 var inEdges = graph.inEdges(u, v);
2043 if (inEdges.length > 0) {
2044 return -util.max(inEdges.map(function(e) {
2045 return graph.edge(e).minLen;
2050 },{"../util":17,"./rankUtil":15}],17:[function(require,module,exports){
2052 * Returns the smallest value in the array.
2054 exports.min = function(values) {
2055 return Math.min.apply(Math, values);
2059 * Returns the largest value in the array.
2061 exports.max = function(values) {
2062 return Math.max.apply(Math, values);
2066 * Returns `true` only if `f(x)` is `true` for all `x` in `xs`. Otherwise
2067 * returns `false`. This function will return immediately if it finds a
2068 * case where `f(x)` does not hold.
2070 exports.all = function(xs, f) {
2071 for (var i = 0; i < xs.length; ++i) {
2080 * Accumulates the sum of elements in the given array using the `+` operator.
2082 exports.sum = function(values) {
2083 return values.reduce(function(acc, x) { return acc + x; }, 0);
2087 * Returns an array of all values in the given object.
2089 exports.values = function(obj) {
2090 return Object.keys(obj).map(function(k) { return obj[k]; });
2093 exports.shuffle = function(array) {
2094 for (i = array.length - 1; i > 0; --i) {
2095 var j = Math.floor(Math.random() * (i + 1));
2097 array[j] = array[i];
2102 exports.propertyAccessor = function(self, config, field, setHook) {
2103 return function(x) {
2104 if (!arguments.length) return config[field];
2106 if (setHook) setHook(x);
2112 * Given a layered, directed graph with `rank` and `order` node attributes,
2113 * this function returns an array of ordered ranks. Each rank contains an array
2114 * of the ids of the nodes in that rank in the order specified by the `order`
2117 exports.ordering = function(g) {
2119 g.eachNode(function(u, value) {
2120 var rank = ordering[value.rank] || (ordering[value.rank] = []);
2121 rank[value.order] = u;
2127 * A filter that can be used with `filterNodes` to get a graph that only
2128 * includes nodes that do not contain others nodes.
2130 exports.filterNonSubgraphs = function(g) {
2131 return function(u) {
2132 return g.children(u).length === 0;
2137 * Returns a new function that wraps `func` with a timer. The wrapper logs the
2138 * time it takes to execute the function.
2140 * The timer will be enabled provided `log.level >= 1`.
2142 function time(name, func) {
2144 var start = new Date().getTime();
2146 return func.apply(null, arguments);
2148 log(1, name + ' time: ' + (new Date().getTime() - start) + 'ms');
2152 time.enabled = false;
2154 exports.time = time;
2157 * A global logger with the specification `log(level, message, ...)` that
2158 * will log a message to the console if `log.level >= level`.
2160 function log(level) {
2161 if (log.level >= level) {
2162 console.log.apply(console, Array.prototype.slice.call(arguments, 1));
2169 },{}],18:[function(require,module,exports){
2170 module.exports = '0.4.5';
2172 },{}],19:[function(require,module,exports){
2173 exports.Set = require('./lib/Set');
2174 exports.PriorityQueue = require('./lib/PriorityQueue');
2175 exports.version = require('./lib/version');
2177 },{"./lib/PriorityQueue":20,"./lib/Set":21,"./lib/version":23}],20:[function(require,module,exports){
2178 module.exports = PriorityQueue;
2181 * A min-priority queue data structure. This algorithm is derived from Cormen,
2182 * et al., "Introduction to Algorithms". The basic idea of a min-priority
2183 * queue is that you can efficiently (in O(1) time) get the smallest key in
2184 * the queue. Adding and removing elements takes O(log n) time. A key can
2185 * have its priority decreased in O(log n) time.
2187 function PriorityQueue() {
2189 this._keyIndices = {};
2193 * Returns the number of elements in the queue. Takes `O(1)` time.
2195 PriorityQueue.prototype.size = function() {
2196 return this._arr.length;
2200 * Returns the keys that are in the queue. Takes `O(n)` time.
2202 PriorityQueue.prototype.keys = function() {
2203 return this._arr.map(function(x) { return x.key; });
2207 * Returns `true` if **key** is in the queue and `false` if not.
2209 PriorityQueue.prototype.has = function(key) {
2210 return key in this._keyIndices;
2214 * Returns the priority for **key**. If **key** is not present in the queue
2215 * then this function returns `undefined`. Takes `O(1)` time.
2217 * @param {Object} key
2219 PriorityQueue.prototype.priority = function(key) {
2220 var index = this._keyIndices[key];
2221 if (index !== undefined) {
2222 return this._arr[index].priority;
2227 * Returns the key for the minimum element in this queue. If the queue is
2228 * empty this function throws an Error. Takes `O(1)` time.
2230 PriorityQueue.prototype.min = function() {
2231 if (this.size() === 0) {
2232 throw new Error("Queue underflow");
2234 return this._arr[0].key;
2238 * Inserts a new key into the priority queue. If the key already exists in
2239 * the queue this function returns `false`; otherwise it will return `true`.
2240 * Takes `O(n)` time.
2242 * @param {Object} key the key to add
2243 * @param {Number} priority the initial priority for the key
2245 PriorityQueue.prototype.add = function(key, priority) {
2246 var keyIndices = this._keyIndices;
2247 if (!(key in keyIndices)) {
2248 var arr = this._arr;
2249 var index = arr.length;
2250 keyIndices[key] = index;
2251 arr.push({key: key, priority: priority});
2252 this._decrease(index);
2259 * Removes and returns the smallest key in the queue. Takes `O(log n)` time.
2261 PriorityQueue.prototype.removeMin = function() {
2262 this._swap(0, this._arr.length - 1);
2263 var min = this._arr.pop();
2264 delete this._keyIndices[min.key];
2270 * Decreases the priority for **key** to **priority**. If the new priority is
2271 * greater than the previous priority, this function will throw an Error.
2273 * @param {Object} key the key for which to raise priority
2274 * @param {Number} priority the new priority for the key
2276 PriorityQueue.prototype.decrease = function(key, priority) {
2277 var index = this._keyIndices[key];
2278 if (priority > this._arr[index].priority) {
2279 throw new Error("New priority is greater than current priority. " +
2280 "Key: " + key + " Old: " + this._arr[index].priority + " New: " + priority);
2282 this._arr[index].priority = priority;
2283 this._decrease(index);
2286 PriorityQueue.prototype._heapify = function(i) {
2287 var arr = this._arr;
2291 if (l < arr.length) {
2292 largest = arr[l].priority < arr[largest].priority ? l : largest;
2293 if (r < arr.length) {
2294 largest = arr[r].priority < arr[largest].priority ? r : largest;
2296 if (largest !== i) {
2297 this._swap(i, largest);
2298 this._heapify(largest);
2303 PriorityQueue.prototype._decrease = function(index) {
2304 var arr = this._arr;
2305 var priority = arr[index].priority;
2307 while (index !== 0) {
2308 parent = index >> 1;
2309 if (arr[parent].priority < priority) {
2312 this._swap(index, parent);
2317 PriorityQueue.prototype._swap = function(i, j) {
2318 var arr = this._arr;
2319 var keyIndices = this._keyIndices;
2320 var origArrI = arr[i];
2321 var origArrJ = arr[j];
2324 keyIndices[origArrJ.key] = i;
2325 keyIndices[origArrI.key] = j;
2328 },{}],21:[function(require,module,exports){
2329 var util = require('./util');
2331 module.exports = Set;
2334 * Constructs a new Set with an optional set of `initialKeys`.
2336 * It is important to note that keys are coerced to String for most purposes
2337 * with this object, similar to the behavior of JavaScript's Object. For
2338 * example, the following will add only one key:
2340 * var s = new Set();
2344 * However, the type of the key is preserved internally so that `keys` returns
2345 * the original key set uncoerced. For the above example, `keys` would return
2348 function Set(initialKeys) {
2353 for (var i = 0, il = initialKeys.length; i < il; ++i) {
2354 this.add(initialKeys[i]);
2360 * Returns a new Set that represents the set intersection of the array of given
2363 Set.intersect = function(sets) {
2364 if (sets.length === 0) {
2368 var result = new Set(!util.isArray(sets[0]) ? sets[0].keys() : sets[0]);
2369 for (var i = 1, il = sets.length; i < il; ++i) {
2370 var resultKeys = result.keys(),
2371 other = !util.isArray(sets[i]) ? sets[i] : new Set(sets[i]);
2372 for (var j = 0, jl = resultKeys.length; j < jl; ++j) {
2373 var key = resultKeys[j];
2374 if (!other.has(key)) {
2384 * Returns a new Set that represents the set union of the array of given sets.
2386 Set.union = function(sets) {
2387 var totalElems = util.reduce(sets, function(lhs, rhs) {
2388 return lhs + (rhs.size ? rhs.size() : rhs.length);
2390 var arr = new Array(totalElems);
2393 for (var i = 0, il = sets.length; i < il; ++i) {
2395 keys = !util.isArray(cur) ? cur.keys() : cur;
2396 for (var j = 0, jl = keys.length; j < jl; ++j) {
2401 return new Set(arr);
2405 * Returns the size of this set in `O(1)` time.
2407 Set.prototype.size = function() {
2412 * Returns the keys in this set. Takes `O(n)` time.
2414 Set.prototype.keys = function() {
2415 return values(this._keys);
2419 * Tests if a key is present in this Set. Returns `true` if it is and `false`
2420 * if not. Takes `O(1)` time.
2422 Set.prototype.has = function(key) {
2423 return key in this._keys;
2427 * Adds a new key to this Set if it is not already present. Returns `true` if
2428 * the key was added and `false` if it was already present. Takes `O(1)` time.
2430 Set.prototype.add = function(key) {
2431 if (!(key in this._keys)) {
2432 this._keys[key] = key;
2440 * Removes a key from this Set. If the key was removed this function returns
2441 * `true`. If not, it returns `false`. Takes `O(1)` time.
2443 Set.prototype.remove = function(key) {
2444 if (key in this._keys) {
2445 delete this._keys[key];
2453 * Returns an array of all values for properties of **o**.
2455 function values(o) {
2456 var ks = Object.keys(o),
2458 result = new Array(len),
2460 for (i = 0; i < len; ++i) {
2461 result[i] = o[ks[i]];
2466 },{"./util":22}],22:[function(require,module,exports){
2468 * This polyfill comes from
2469 * https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/isArray
2471 if(!Array.isArray) {
2472 exports.isArray = function (vArg) {
2473 return Object.prototype.toString.call(vArg) === '[object Array]';
2476 exports.isArray = Array.isArray;
2480 * Slightly adapted polyfill from
2481 * https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/Reduce
2483 if ('function' !== typeof Array.prototype.reduce) {
2484 exports.reduce = function(array, callback, opt_initialValue) {
2486 if (null === array || 'undefined' === typeof array) {
2487 // At the moment all modern browsers, that support strict mode, have
2488 // native implementation of Array.prototype.reduce. For instance, IE8
2489 // does not support strict mode, so this check is actually useless.
2490 throw new TypeError(
2491 'Array.prototype.reduce called on null or undefined');
2493 if ('function' !== typeof callback) {
2494 throw new TypeError(callback + ' is not a function');
2497 length = array.length >>> 0,
2499 if (1 < arguments.length) {
2500 value = opt_initialValue;
2503 for (index = 0; length > index; ++index) {
2504 if (array.hasOwnProperty(index)) {
2506 value = callback(value, array[index], index, array);
2509 value = array[index];
2515 throw new TypeError('Reduce of empty array with no initial value');
2520 exports.reduce = function(array, callback, opt_initialValue) {
2521 return array.reduce(callback, opt_initialValue);
2525 },{}],23:[function(require,module,exports){
2526 module.exports = '1.1.3';
2528 },{}],24:[function(require,module,exports){
2529 exports.Graph = require("./lib/Graph");
2530 exports.Digraph = require("./lib/Digraph");
2531 exports.CGraph = require("./lib/CGraph");
2532 exports.CDigraph = require("./lib/CDigraph");
2533 require("./lib/graph-converters");
2536 isAcyclic: require("./lib/alg/isAcyclic"),
2537 components: require("./lib/alg/components"),
2538 dijkstra: require("./lib/alg/dijkstra"),
2539 dijkstraAll: require("./lib/alg/dijkstraAll"),
2540 findCycles: require("./lib/alg/findCycles"),
2541 floydWarshall: require("./lib/alg/floydWarshall"),
2542 postorder: require("./lib/alg/postorder"),
2543 preorder: require("./lib/alg/preorder"),
2544 prim: require("./lib/alg/prim"),
2545 tarjan: require("./lib/alg/tarjan"),
2546 topsort: require("./lib/alg/topsort")
2549 exports.converter = {
2550 json: require("./lib/converter/json.js")
2553 var filter = require("./lib/filter");
2556 nodesFromList: filter.nodesFromList
2559 exports.version = require("./lib/version");
2561 },{"./lib/CDigraph":26,"./lib/CGraph":27,"./lib/Digraph":28,"./lib/Graph":29,"./lib/alg/components":30,"./lib/alg/dijkstra":31,"./lib/alg/dijkstraAll":32,"./lib/alg/findCycles":33,"./lib/alg/floydWarshall":34,"./lib/alg/isAcyclic":35,"./lib/alg/postorder":36,"./lib/alg/preorder":37,"./lib/alg/prim":38,"./lib/alg/tarjan":39,"./lib/alg/topsort":40,"./lib/converter/json.js":42,"./lib/filter":43,"./lib/graph-converters":44,"./lib/version":46}],25:[function(require,module,exports){
2563 var Set = require("cp-data").Set;
2566 module.exports = BaseGraph;
2568 function BaseGraph() {
2569 // The value assigned to the graph itself.
2570 this._value = undefined;
2572 // Map of node id -> { id, value }
2575 // Map of edge id -> { id, u, v, value }
2578 // Used to generate a unique id in the graph
2583 BaseGraph.prototype.order = function() {
2584 return Object.keys(this._nodes).length;
2588 BaseGraph.prototype.size = function() {
2589 return Object.keys(this._edges).length;
2592 // Accessor for graph level value
2593 BaseGraph.prototype.graph = function(value) {
2594 if (arguments.length === 0) {
2597 this._value = value;
2600 BaseGraph.prototype.hasNode = function(u) {
2601 return u in this._nodes;
2604 BaseGraph.prototype.node = function(u, value) {
2605 var node = this._strictGetNode(u);
2606 if (arguments.length === 1) {
2612 BaseGraph.prototype.nodes = function() {
2614 this.eachNode(function(id) { nodes.push(id); });
2618 BaseGraph.prototype.eachNode = function(func) {
2619 for (var k in this._nodes) {
2620 var node = this._nodes[k];
2621 func(node.id, node.value);
2625 BaseGraph.prototype.hasEdge = function(e) {
2626 return e in this._edges;
2629 BaseGraph.prototype.edge = function(e, value) {
2630 var edge = this._strictGetEdge(e);
2631 if (arguments.length === 1) {
2637 BaseGraph.prototype.edges = function() {
2639 this.eachEdge(function(id) { es.push(id); });
2643 BaseGraph.prototype.eachEdge = function(func) {
2644 for (var k in this._edges) {
2645 var edge = this._edges[k];
2646 func(edge.id, edge.u, edge.v, edge.value);
2650 BaseGraph.prototype.incidentNodes = function(e) {
2651 var edge = this._strictGetEdge(e);
2652 return [edge.u, edge.v];
2655 BaseGraph.prototype.addNode = function(u, value) {
2656 if (u === undefined || u === null) {
2658 u = "_" + (++this._nextId);
2659 } while (this.hasNode(u));
2660 } else if (this.hasNode(u)) {
2661 throw new Error("Graph already has node '" + u + "'");
2663 this._nodes[u] = { id: u, value: value };
2667 BaseGraph.prototype.delNode = function(u) {
2668 this._strictGetNode(u);
2669 this.incidentEdges(u).forEach(function(e) { this.delEdge(e); }, this);
2670 delete this._nodes[u];
2673 // inMap and outMap are opposite sides of an incidence map. For example, for
2674 // Graph these would both come from the _incidentEdges map, while for Digraph
2675 // they would come from _inEdges and _outEdges.
2676 BaseGraph.prototype._addEdge = function(e, u, v, value, inMap, outMap) {
2677 this._strictGetNode(u);
2678 this._strictGetNode(v);
2680 if (e === undefined || e === null) {
2682 e = "_" + (++this._nextId);
2683 } while (this.hasEdge(e));
2685 else if (this.hasEdge(e)) {
2686 throw new Error("Graph already has edge '" + e + "'");
2689 this._edges[e] = { id: e, u: u, v: v, value: value };
2690 addEdgeToMap(inMap[v], u, e);
2691 addEdgeToMap(outMap[u], v, e);
2696 // See note for _addEdge regarding inMap and outMap.
2697 BaseGraph.prototype._delEdge = function(e, inMap, outMap) {
2698 var edge = this._strictGetEdge(e);
2699 delEdgeFromMap(inMap[edge.v], edge.u, e);
2700 delEdgeFromMap(outMap[edge.u], edge.v, e);
2701 delete this._edges[e];
2704 BaseGraph.prototype.copy = function() {
2705 var copy = new this.constructor();
2706 copy.graph(this.graph());
2707 this.eachNode(function(u, value) { copy.addNode(u, value); });
2708 this.eachEdge(function(e, u, v, value) { copy.addEdge(e, u, v, value); });
2709 copy._nextId = this._nextId;
2713 BaseGraph.prototype.filterNodes = function(filter) {
2714 var copy = new this.constructor();
2715 copy.graph(this.graph());
2716 this.eachNode(function(u, value) {
2718 copy.addNode(u, value);
2721 this.eachEdge(function(e, u, v, value) {
2722 if (copy.hasNode(u) && copy.hasNode(v)) {
2723 copy.addEdge(e, u, v, value);
2729 BaseGraph.prototype._strictGetNode = function(u) {
2730 var node = this._nodes[u];
2731 if (node === undefined) {
2732 throw new Error("Node '" + u + "' is not in graph");
2737 BaseGraph.prototype._strictGetEdge = function(e) {
2738 var edge = this._edges[e];
2739 if (edge === undefined) {
2740 throw new Error("Edge '" + e + "' is not in graph");
2745 function addEdgeToMap(map, v, e) {
2746 (map[v] || (map[v] = new Set())).add(e);
2749 function delEdgeFromMap(map, v, e) {
2750 var vEntry = map[v];
2752 if (vEntry.size() === 0) {
2758 },{"cp-data":19}],26:[function(require,module,exports){
2759 var Digraph = require("./Digraph"),
2760 compoundify = require("./compoundify");
2762 var CDigraph = compoundify(Digraph);
2764 module.exports = CDigraph;
2766 CDigraph.fromDigraph = function(src) {
2767 var g = new CDigraph(),
2768 graphValue = src.graph();
2770 if (graphValue !== undefined) {
2771 g.graph(graphValue);
2774 src.eachNode(function(u, value) {
2775 if (value === undefined) {
2778 g.addNode(u, value);
2781 src.eachEdge(function(e, u, v, value) {
2782 if (value === undefined) {
2783 g.addEdge(null, u, v);
2785 g.addEdge(null, u, v, value);
2791 CDigraph.prototype.toString = function() {
2792 return "CDigraph " + JSON.stringify(this, null, 2);
2795 },{"./Digraph":28,"./compoundify":41}],27:[function(require,module,exports){
2796 var Graph = require("./Graph"),
2797 compoundify = require("./compoundify");
2799 var CGraph = compoundify(Graph);
2801 module.exports = CGraph;
2803 CGraph.fromGraph = function(src) {
2804 var g = new CGraph(),
2805 graphValue = src.graph();
2807 if (graphValue !== undefined) {
2808 g.graph(graphValue);
2811 src.eachNode(function(u, value) {
2812 if (value === undefined) {
2815 g.addNode(u, value);
2818 src.eachEdge(function(e, u, v, value) {
2819 if (value === undefined) {
2820 g.addEdge(null, u, v);
2822 g.addEdge(null, u, v, value);
2828 CGraph.prototype.toString = function() {
2829 return "CGraph " + JSON.stringify(this, null, 2);
2832 },{"./Graph":29,"./compoundify":41}],28:[function(require,module,exports){
2834 * This file is organized with in the following order:
2837 * Graph constructors
2838 * Graph queries (e.g. nodes(), edges()
2843 var util = require("./util"),
2844 BaseGraph = require("./BaseGraph"),
2846 Set = require("cp-data").Set;
2849 module.exports = Digraph;
2852 * Constructor to create a new directed multi-graph.
2854 function Digraph() {
2855 BaseGraph.call(this);
2857 /*! Map of sourceId -> {targetId -> Set of edge ids} */
2860 /*! Map of targetId -> {sourceId -> Set of edge ids} */
2861 this._outEdges = {};
2864 Digraph.prototype = new BaseGraph();
2865 Digraph.prototype.constructor = Digraph;
2868 * Always returns `true`.
2870 Digraph.prototype.isDirected = function() {
2875 * Returns all successors of the node with the id `u`. That is, all nodes
2876 * that have the node `u` as their source are returned.
2878 * If no node `u` exists in the graph this function throws an Error.
2880 * @param {String} u a node id
2882 Digraph.prototype.successors = function(u) {
2883 this._strictGetNode(u);
2884 return Object.keys(this._outEdges[u])
2885 .map(function(v) { return this._nodes[v].id; }, this);
2889 * Returns all predecessors of the node with the id `u`. That is, all nodes
2890 * that have the node `u` as their target are returned.
2892 * If no node `u` exists in the graph this function throws an Error.
2894 * @param {String} u a node id
2896 Digraph.prototype.predecessors = function(u) {
2897 this._strictGetNode(u);
2898 return Object.keys(this._inEdges[u])
2899 .map(function(v) { return this._nodes[v].id; }, this);
2903 * Returns all nodes that are adjacent to the node with the id `u`. In other
2904 * words, this function returns the set of all successors and predecessors of
2907 * @param {String} u a node id
2909 Digraph.prototype.neighbors = function(u) {
2910 return Set.union([this.successors(u), this.predecessors(u)]).keys();
2914 * Returns all nodes in the graph that have no in-edges.
2916 Digraph.prototype.sources = function() {
2918 return this._filterNodes(function(u) {
2919 // This could have better space characteristics if we had an inDegree function.
2920 return self.inEdges(u).length === 0;
2925 * Returns all nodes in the graph that have no out-edges.
2927 Digraph.prototype.sinks = function() {
2929 return this._filterNodes(function(u) {
2930 // This could have better space characteristics if we have an outDegree function.
2931 return self.outEdges(u).length === 0;
2936 * Returns the source node incident on the edge identified by the id `e`. If no
2937 * such edge exists in the graph this function throws an Error.
2939 * @param {String} e an edge id
2941 Digraph.prototype.source = function(e) {
2942 return this._strictGetEdge(e).u;
2946 * Returns the target node incident on the edge identified by the id `e`. If no
2947 * such edge exists in the graph this function throws an Error.
2949 * @param {String} e an edge id
2951 Digraph.prototype.target = function(e) {
2952 return this._strictGetEdge(e).v;
2956 * Returns an array of ids for all edges in the graph that have the node
2957 * `target` as their target. If the node `target` is not in the graph this
2958 * function raises an Error.
2960 * Optionally a `source` node can also be specified. This causes the results
2961 * to be filtered such that only edges from `source` to `target` are included.
2962 * If the node `source` is specified but is not in the graph then this function
2965 * @param {String} target the target node id
2966 * @param {String} [source] an optional source node id
2968 Digraph.prototype.inEdges = function(target, source) {
2969 this._strictGetNode(target);
2970 var results = Set.union(util.values(this._inEdges[target])).keys();
2971 if (arguments.length > 1) {
2972 this._strictGetNode(source);
2973 results = results.filter(function(e) { return this.source(e) === source; }, this);
2979 * Returns an array of ids for all edges in the graph that have the node
2980 * `source` as their source. If the node `source` is not in the graph this
2981 * function raises an Error.
2983 * Optionally a `target` node may also be specified. This causes the results
2984 * to be filtered such that only edges from `source` to `target` are included.
2985 * If the node `target` is specified but is not in the graph then this function
2988 * @param {String} source the source node id
2989 * @param {String} [target] an optional target node id
2991 Digraph.prototype.outEdges = function(source, target) {
2992 this._strictGetNode(source);
2993 var results = Set.union(util.values(this._outEdges[source])).keys();
2994 if (arguments.length > 1) {
2995 this._strictGetNode(target);
2996 results = results.filter(function(e) { return this.target(e) === target; }, this);
3002 * Returns an array of ids for all edges in the graph that have the `u` as
3003 * their source or their target. If the node `u` is not in the graph this
3004 * function raises an Error.
3006 * Optionally a `v` node may also be specified. This causes the results to be
3007 * filtered such that only edges between `u` and `v` - in either direction -
3008 * are included. IF the node `v` is specified but not in the graph then this
3009 * function raises an Error.
3011 * @param {String} u the node for which to find incident edges
3012 * @param {String} [v] option node that must be adjacent to `u`
3014 Digraph.prototype.incidentEdges = function(u, v) {
3015 if (arguments.length > 1) {
3016 return Set.union([this.outEdges(u, v), this.outEdges(v, u)]).keys();
3018 return Set.union([this.inEdges(u), this.outEdges(u)]).keys();
3023 * Returns a string representation of this graph.
3025 Digraph.prototype.toString = function() {
3026 return "Digraph " + JSON.stringify(this, null, 2);
3030 * Adds a new node with the id `u` to the graph and assigns it the value
3031 * `value`. If a node with the id is already a part of the graph this function
3034 * @param {String} u a node id
3035 * @param {Object} [value] an optional value to attach to the node
3037 Digraph.prototype.addNode = function(u, value) {
3038 u = BaseGraph.prototype.addNode.call(this, u, value);
3039 this._inEdges[u] = {};
3040 this._outEdges[u] = {};
3045 * Removes a node from the graph that has the id `u`. Any edges incident on the
3046 * node are also removed. If the graph does not contain a node with the id this
3047 * function will throw an Error.
3049 * @param {String} u a node id
3051 Digraph.prototype.delNode = function(u) {
3052 BaseGraph.prototype.delNode.call(this, u);
3053 delete this._inEdges[u];
3054 delete this._outEdges[u];
3058 * Adds a new edge to the graph with the id `e` from a node with the id `source`
3059 * to a node with an id `target` and assigns it the value `value`. This graph
3060 * allows more than one edge from `source` to `target` as long as the id `e`
3061 * is unique in the set of edges. If `e` is `null` the graph will assign a
3062 * unique identifier to the edge.
3064 * If `source` or `target` are not present in the graph this function will
3067 * @param {String} [e] an edge id
3068 * @param {String} source the source node id
3069 * @param {String} target the target node id
3070 * @param {Object} [value] an optional value to attach to the edge
3072 Digraph.prototype.addEdge = function(e, source, target, value) {
3073 return BaseGraph.prototype._addEdge.call(this, e, source, target, value,
3074 this._inEdges, this._outEdges);
3078 * Removes an edge in the graph with the id `e`. If no edge in the graph has
3079 * the id `e` this function will throw an Error.
3081 * @param {String} e an edge id
3083 Digraph.prototype.delEdge = function(e) {
3084 BaseGraph.prototype._delEdge.call(this, e, this._inEdges, this._outEdges);
3087 // Unlike BaseGraph.filterNodes, this helper just returns nodes that
3088 // satisfy a predicate.
3089 Digraph.prototype._filterNodes = function(pred) {
3091 this.eachNode(function(u) {
3100 },{"./BaseGraph":25,"./util":45,"cp-data":19}],29:[function(require,module,exports){
3102 * This file is organized with in the following order:
3105 * Graph constructors
3106 * Graph queries (e.g. nodes(), edges()
3111 var util = require("./util"),
3112 BaseGraph = require("./BaseGraph"),
3114 Set = require("cp-data").Set;
3117 module.exports = Graph;
3120 * Constructor to create a new undirected multi-graph.
3123 BaseGraph.call(this);
3125 /*! Map of nodeId -> { otherNodeId -> Set of edge ids } */
3126 this._incidentEdges = {};
3129 Graph.prototype = new BaseGraph();
3130 Graph.prototype.constructor = Graph;
3133 * Always returns `false`.
3135 Graph.prototype.isDirected = function() {
3140 * Returns all nodes that are adjacent to the node with the id `u`.
3142 * @param {String} u a node id
3144 Graph.prototype.neighbors = function(u) {
3145 this._strictGetNode(u);
3146 return Object.keys(this._incidentEdges[u])
3147 .map(function(v) { return this._nodes[v].id; }, this);
3151 * Returns an array of ids for all edges in the graph that are incident on `u`.
3152 * If the node `u` is not in the graph this function raises an Error.
3154 * Optionally a `v` node may also be specified. This causes the results to be
3155 * filtered such that only edges between `u` and `v` are included. If the node
3156 * `v` is specified but not in the graph then this function raises an Error.
3158 * @param {String} u the node for which to find incident edges
3159 * @param {String} [v] option node that must be adjacent to `u`
3161 Graph.prototype.incidentEdges = function(u, v) {
3162 this._strictGetNode(u);
3163 if (arguments.length > 1) {
3164 this._strictGetNode(v);
3165 return v in this._incidentEdges[u] ? this._incidentEdges[u][v].keys() : [];
3167 return Set.union(util.values(this._incidentEdges[u])).keys();
3172 * Returns a string representation of this graph.
3174 Graph.prototype.toString = function() {
3175 return "Graph " + JSON.stringify(this, null, 2);
3179 * Adds a new node with the id `u` to the graph and assigns it the value
3180 * `value`. If a node with the id is already a part of the graph this function
3183 * @param {String} u a node id
3184 * @param {Object} [value] an optional value to attach to the node
3186 Graph.prototype.addNode = function(u, value) {
3187 u = BaseGraph.prototype.addNode.call(this, u, value);
3188 this._incidentEdges[u] = {};
3193 * Removes a node from the graph that has the id `u`. Any edges incident on the
3194 * node are also removed. If the graph does not contain a node with the id this
3195 * function will throw an Error.
3197 * @param {String} u a node id
3199 Graph.prototype.delNode = function(u) {
3200 BaseGraph.prototype.delNode.call(this, u);
3201 delete this._incidentEdges[u];
3205 * Adds a new edge to the graph with the id `e` between a node with the id `u`
3206 * and a node with an id `v` and assigns it the value `value`. This graph
3207 * allows more than one edge between `u` and `v` as long as the id `e`
3208 * is unique in the set of edges. If `e` is `null` the graph will assign a
3209 * unique identifier to the edge.
3211 * If `u` or `v` are not present in the graph this function will throw an
3214 * @param {String} [e] an edge id
3215 * @param {String} u the node id of one of the adjacent nodes
3216 * @param {String} v the node id of the other adjacent node
3217 * @param {Object} [value] an optional value to attach to the edge
3219 Graph.prototype.addEdge = function(e, u, v, value) {
3220 return BaseGraph.prototype._addEdge.call(this, e, u, v, value,
3221 this._incidentEdges, this._incidentEdges);
3225 * Removes an edge in the graph with the id `e`. If no edge in the graph has
3226 * the id `e` this function will throw an Error.
3228 * @param {String} e an edge id
3230 Graph.prototype.delEdge = function(e) {
3231 BaseGraph.prototype._delEdge.call(this, e, this._incidentEdges, this._incidentEdges);
3235 },{"./BaseGraph":25,"./util":45,"cp-data":19}],30:[function(require,module,exports){
3237 var Set = require("cp-data").Set;
3240 module.exports = components;
3243 * Finds all [connected components][] in a graph and returns an array of these
3244 * components. Each component is itself an array that contains the ids of nodes
3247 * This function only works with undirected Graphs.
3249 * [connected components]: http://en.wikipedia.org/wiki/Connected_component_(graph_theory)
3251 * @param {Graph} g the graph to search for components
3253 function components(g) {
3255 var visited = new Set();
3257 function dfs(v, component) {
3258 if (!visited.has(v)) {
3261 g.neighbors(v).forEach(function(w) {
3267 g.nodes().forEach(function(v) {
3270 if (component.length > 0) {
3271 results.push(component);
3278 },{"cp-data":19}],31:[function(require,module,exports){
3279 var PriorityQueue = require("cp-data").PriorityQueue;
3281 module.exports = dijkstra;
3284 * This function is an implementation of [Dijkstra's algorithm][] which finds
3285 * the shortest path from **source** to all other nodes in **g**. This
3286 * function returns a map of `u -> { distance, predecessor }`. The distance
3287 * property holds the sum of the weights from **source** to `u` along the
3288 * shortest path or `Number.POSITIVE_INFINITY` if there is no path from
3289 * **source**. The predecessor property can be used to walk the individual
3290 * elements of the path from **source** to **u** in reverse order.
3292 * This function takes an optional `weightFunc(e)` which returns the
3293 * weight of the edge `e`. If no weightFunc is supplied then each edge is
3294 * assumed to have a weight of 1. This function throws an Error if any of
3295 * the traversed edges have a negative edge weight.
3297 * This function takes an optional `incidentFunc(u)` which returns the ids of
3298 * all edges incident to the node `u` for the purposes of shortest path
3299 * traversal. By default this function uses the `g.outEdges` for Digraphs and
3300 * `g.incidentEdges` for Graphs.
3302 * This function takes `O((|E| + |V|) * log |V|)` time.
3304 * [Dijkstra's algorithm]: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
3306 * @param {Graph} g the graph to search for shortest paths from **source**
3307 * @param {Object} source the source from which to start the search
3308 * @param {Function} [weightFunc] optional weight function
3309 * @param {Function} [incidentFunc] optional incident function
3311 function dijkstra(g, source, weightFunc, incidentFunc) {
3313 pq = new PriorityQueue();
3315 function updateNeighbors(e) {
3316 var incidentNodes = g.incidentNodes(e),
3317 v = incidentNodes[0] !== u ? incidentNodes[0] : incidentNodes[1],
3318 vEntry = results[v],
3319 weight = weightFunc(e),
3320 distance = uEntry.distance + weight;
3323 throw new Error("dijkstra does not allow negative edge weights. Bad edge: " + e + " Weight: " + weight);
3326 if (distance < vEntry.distance) {
3327 vEntry.distance = distance;
3328 vEntry.predecessor = u;
3329 pq.decrease(v, distance);
3333 weightFunc = weightFunc || function() { return 1; };
3334 incidentFunc = incidentFunc || (g.isDirected()
3335 ? function(u) { return g.outEdges(u); }
3336 : function(u) { return g.incidentEdges(u); });
3338 g.eachNode(function(u) {
3339 var distance = u === source ? 0 : Number.POSITIVE_INFINITY;
3340 results[u] = { distance: distance };
3341 pq.add(u, distance);
3345 while (pq.size() > 0) {
3347 uEntry = results[u];
3348 if (uEntry.distance === Number.POSITIVE_INFINITY) {
3352 incidentFunc(u).forEach(updateNeighbors);
3358 },{"cp-data":19}],32:[function(require,module,exports){
3359 var dijkstra = require("./dijkstra");
3361 module.exports = dijkstraAll;
3364 * This function finds the shortest path from each node to every other
3365 * reachable node in the graph. It is similar to [alg.dijkstra][], but
3366 * instead of returning a single-source array, it returns a mapping of
3367 * of `source -> alg.dijksta(g, source, weightFunc, incidentFunc)`.
3369 * This function takes an optional `weightFunc(e)` which returns the
3370 * weight of the edge `e`. If no weightFunc is supplied then each edge is
3371 * assumed to have a weight of 1. This function throws an Error if any of
3372 * the traversed edges have a negative edge weight.
3374 * This function takes an optional `incidentFunc(u)` which returns the ids of
3375 * all edges incident to the node `u` for the purposes of shortest path
3376 * traversal. By default this function uses the `outEdges` function on the
3379 * This function takes `O(|V| * (|E| + |V|) * log |V|)` time.
3381 * [alg.dijkstra]: dijkstra.js.html#dijkstra
3383 * @param {Graph} g the graph to search for shortest paths from **source**
3384 * @param {Function} [weightFunc] optional weight function
3385 * @param {Function} [incidentFunc] optional incident function
3387 function dijkstraAll(g, weightFunc, incidentFunc) {
3389 g.eachNode(function(u) {
3390 results[u] = dijkstra(g, u, weightFunc, incidentFunc);
3395 },{"./dijkstra":31}],33:[function(require,module,exports){
3396 var tarjan = require("./tarjan");
3398 module.exports = findCycles;
3401 * Given a Digraph **g** this function returns all nodes that are part of a
3402 * cycle. Since there may be more than one cycle in a graph this function
3403 * returns an array of these cycles, where each cycle is itself represented
3404 * by an array of ids for each node involved in that cycle.
3406 * [alg.isAcyclic][] is more efficient if you only need to determine whether
3407 * a graph has a cycle or not.
3409 * [alg.isAcyclic]: isAcyclic.js.html#isAcyclic
3411 * @param {Digraph} g the graph to search for cycles.
3413 function findCycles(g) {
3414 return tarjan(g).filter(function(cmpt) { return cmpt.length > 1; });
3417 },{"./tarjan":39}],34:[function(require,module,exports){
3418 module.exports = floydWarshall;
3421 * This function is an implementation of the [Floyd-Warshall algorithm][],
3422 * which finds the shortest path from each node to every other reachable node
3423 * in the graph. It is similar to [alg.dijkstraAll][], but it handles negative
3424 * edge weights and is more efficient for some types of graphs. This function
3425 * returns a map of `source -> { target -> { distance, predecessor }`. The
3426 * distance property holds the sum of the weights from `source` to `target`
3427 * along the shortest path of `Number.POSITIVE_INFINITY` if there is no path
3428 * from `source`. The predecessor property can be used to walk the individual
3429 * elements of the path from `source` to `target` in reverse order.
3431 * This function takes an optional `weightFunc(e)` which returns the
3432 * weight of the edge `e`. If no weightFunc is supplied then each edge is
3433 * assumed to have a weight of 1.
3435 * This function takes an optional `incidentFunc(u)` which returns the ids of
3436 * all edges incident to the node `u` for the purposes of shortest path
3437 * traversal. By default this function uses the `outEdges` function on the
3440 * This algorithm takes O(|V|^3) time.
3442 * [Floyd-Warshall algorithm]: https://en.wikipedia.org/wiki/Floyd-Warshall_algorithm
3443 * [alg.dijkstraAll]: dijkstraAll.js.html#dijkstraAll
3445 * @param {Graph} g the graph to search for shortest paths from **source**
3446 * @param {Function} [weightFunc] optional weight function
3447 * @param {Function} [incidentFunc] optional incident function
3449 function floydWarshall(g, weightFunc, incidentFunc) {
3453 weightFunc = weightFunc || function() { return 1; };
3454 incidentFunc = incidentFunc || (g.isDirected()
3455 ? function(u) { return g.outEdges(u); }
3456 : function(u) { return g.incidentEdges(u); });
3458 nodes.forEach(function(u) {
3460 results[u][u] = { distance: 0 };
3461 nodes.forEach(function(v) {
3463 results[u][v] = { distance: Number.POSITIVE_INFINITY };
3466 incidentFunc(u).forEach(function(e) {
3467 var incidentNodes = g.incidentNodes(e),
3468 v = incidentNodes[0] !== u ? incidentNodes[0] : incidentNodes[1],
3470 if (d < results[u][v].distance) {
3471 results[u][v] = { distance: d, predecessor: u };
3476 nodes.forEach(function(k) {
3477 var rowK = results[k];
3478 nodes.forEach(function(i) {
3479 var rowI = results[i];
3480 nodes.forEach(function(j) {
3484 var altDistance = ik.distance + kj.distance;
3485 if (altDistance < ij.distance) {
3486 ij.distance = altDistance;
3487 ij.predecessor = kj.predecessor;
3496 },{}],35:[function(require,module,exports){
3497 var topsort = require("./topsort");
3499 module.exports = isAcyclic;
3502 * Given a Digraph **g** this function returns `true` if the graph has no
3503 * cycles and returns `false` if it does. This algorithm returns as soon as it
3504 * detects the first cycle.
3506 * Use [alg.findCycles][] if you need the actual list of cycles in a graph.
3508 * [alg.findCycles]: findCycles.js.html#findCycles
3510 * @param {Digraph} g the graph to test for cycles
3512 function isAcyclic(g) {
3516 if (e instanceof topsort.CycleException) return false;
3522 },{"./topsort":40}],36:[function(require,module,exports){
3524 var Set = require("cp-data").Set;
3527 module.exports = postorder;
3529 // Postorder traversal of g, calling f for each visited node. Assumes the graph
3531 function postorder(g, root, f) {
3532 var visited = new Set();
3533 if (g.isDirected()) {
3534 throw new Error("This function only works for undirected graphs");
3536 function dfs(u, prev) {
3537 if (visited.has(u)) {
3538 throw new Error("The input graph is not a tree: " + g);
3541 g.neighbors(u).forEach(function(v) {
3542 if (v !== prev) dfs(v, u);
3549 },{"cp-data":19}],37:[function(require,module,exports){
3551 var Set = require("cp-data").Set;
3554 module.exports = preorder;
3556 // Preorder traversal of g, calling f for each visited node. Assumes the graph
3558 function preorder(g, root, f) {
3559 var visited = new Set();
3560 if (g.isDirected()) {
3561 throw new Error("This function only works for undirected graphs");
3563 function dfs(u, prev) {
3564 if (visited.has(u)) {
3565 throw new Error("The input graph is not a tree: " + g);
3569 g.neighbors(u).forEach(function(v) {
3570 if (v !== prev) dfs(v, u);
3576 },{"cp-data":19}],38:[function(require,module,exports){
3577 var Graph = require("../Graph"),
3578 PriorityQueue = require("cp-data").PriorityQueue;
3580 module.exports = prim;
3583 * [Prim's algorithm][] takes a connected undirected graph and generates a
3584 * [minimum spanning tree][]. This function returns the minimum spanning
3585 * tree as an undirected graph. This algorithm is derived from the description
3586 * in "Introduction to Algorithms", Third Edition, Cormen, et al., Pg 634.
3588 * This function takes a `weightFunc(e)` which returns the weight of the edge
3589 * `e`. It throws an Error if the graph is not connected.
3591 * This function takes `O(|E| log |V|)` time.
3593 * [Prim's algorithm]: https://en.wikipedia.org/wiki/Prim's_algorithm
3594 * [minimum spanning tree]: https://en.wikipedia.org/wiki/Minimum_spanning_tree
3596 * @param {Graph} g the graph used to generate the minimum spanning tree
3597 * @param {Function} weightFunc the weight function to use
3599 function prim(g, weightFunc) {
3600 var result = new Graph(),
3602 pq = new PriorityQueue(),
3605 function updateNeighbors(e) {
3606 var incidentNodes = g.incidentNodes(e),
3607 v = incidentNodes[0] !== u ? incidentNodes[0] : incidentNodes[1],
3608 pri = pq.priority(v);
3609 if (pri !== undefined) {
3610 var edgeWeight = weightFunc(e);
3611 if (edgeWeight < pri) {
3613 pq.decrease(v, edgeWeight);
3618 if (g.order() === 0) {
3622 g.eachNode(function(u) {
3623 pq.add(u, Number.POSITIVE_INFINITY);
3627 // Start from an arbitrary node
3628 pq.decrease(g.nodes()[0], 0);
3631 while (pq.size() > 0) {
3634 result.addEdge(null, u, parents[u]);
3636 throw new Error("Input graph is not connected: " + g);
3641 g.incidentEdges(u).forEach(updateNeighbors);
3647 },{"../Graph":29,"cp-data":19}],39:[function(require,module,exports){
3648 module.exports = tarjan;
3651 * This function is an implementation of [Tarjan's algorithm][] which finds
3652 * all [strongly connected components][] in the directed graph **g**. Each
3653 * strongly connected component is composed of nodes that can reach all other
3654 * nodes in the component via directed edges. A strongly connected component
3655 * can consist of a single node if that node cannot both reach and be reached
3656 * by any other specific node in the graph. Components of more than one node
3657 * are guaranteed to have at least one cycle.
3659 * This function returns an array of components. Each component is itself an
3660 * array that contains the ids of all nodes in the component.
3662 * [Tarjan's algorithm]: http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm
3663 * [strongly connected components]: http://en.wikipedia.org/wiki/Strongly_connected_component
3665 * @param {Digraph} g the graph to search for strongly connected components
3667 function tarjan(g) {
3668 if (!g.isDirected()) {
3669 throw new Error("tarjan can only be applied to a directed graph. Bad input: " + g);
3674 visited = {}, // node id -> { onStack, lowlink, index }
3678 var entry = visited[u] = {
3685 g.successors(u).forEach(function(v) {
3686 if (!(v in visited)) {
3688 entry.lowlink = Math.min(entry.lowlink, visited[v].lowlink);
3689 } else if (visited[v].onStack) {
3690 entry.lowlink = Math.min(entry.lowlink, visited[v].index);
3694 if (entry.lowlink === entry.index) {
3699 visited[v].onStack = false;
3706 g.nodes().forEach(function(u) {
3707 if (!(u in visited)) {
3715 },{}],40:[function(require,module,exports){
3716 module.exports = topsort;
3717 topsort.CycleException = CycleException;
3720 * Given a graph **g**, this function returns an ordered list of nodes such
3721 * that for each edge `u -> v`, `u` appears before `v` in the list. If the
3722 * graph has a cycle it is impossible to generate such a list and
3723 * **CycleException** is thrown.
3725 * See [topological sorting](https://en.wikipedia.org/wiki/Topological_sorting)
3726 * for more details about how this algorithm works.
3728 * @param {Digraph} g the graph to sort
3730 function topsort(g) {
3731 if (!g.isDirected()) {
3732 throw new Error("topsort can only be applied to a directed graph. Bad input: " + g);
3739 function visit(node) {
3740 if (node in stack) {
3741 throw new CycleException();
3744 if (!(node in visited)) {
3746 visited[node] = true;
3747 g.predecessors(node).forEach(function(pred) {
3755 var sinks = g.sinks();
3756 if (g.order() !== 0 && sinks.length === 0) {
3757 throw new CycleException();
3760 g.sinks().forEach(function(sink) {
3767 function CycleException() {}
3769 CycleException.prototype.toString = function() {
3770 return "Graph has at least one cycle";
3773 },{}],41:[function(require,module,exports){
3774 // This file provides a helper function that mixes-in Dot behavior to an
3775 // existing graph prototype.
3778 var Set = require("cp-data").Set;
3781 module.exports = compoundify;
3783 // Extends the given SuperConstructor with the ability for nodes to contain
3784 // other nodes. A special node id `null` is used to indicate the root graph.
3785 function compoundify(SuperConstructor) {
3786 function Constructor() {
3787 SuperConstructor.call(this);
3789 // Map of object id -> parent id (or null for root graph)
3792 // Map of id (or null) -> children set
3793 this._children = {};
3794 this._children[null] = new Set();
3797 Constructor.prototype = new SuperConstructor();
3798 Constructor.prototype.constructor = Constructor;
3800 Constructor.prototype.parent = function(u, parent) {
3801 this._strictGetNode(u);
3803 if (arguments.length < 2) {
3804 return this._parents[u];
3808 throw new Error("Cannot make " + u + " a parent of itself");
3810 if (parent !== null) {
3811 this._strictGetNode(parent);
3814 this._children[this._parents[u]].remove(u);
3815 this._parents[u] = parent;
3816 this._children[parent].add(u);
3819 Constructor.prototype.children = function(u) {
3821 this._strictGetNode(u);
3823 return this._children[u].keys();
3826 Constructor.prototype.addNode = function(u, value) {
3827 u = SuperConstructor.prototype.addNode.call(this, u, value);
3828 this._parents[u] = null;
3829 this._children[u] = new Set();
3830 this._children[null].add(u);
3834 Constructor.prototype.delNode = function(u) {
3835 // Promote all children to the parent of the subgraph
3836 var parent = this.parent(u);
3837 this._children[u].keys().forEach(function(child) {
3838 this.parent(child, parent);
3841 this._children[parent].remove(u);
3842 delete this._parents[u];
3843 delete this._children[u];
3845 return SuperConstructor.prototype.delNode.call(this, u);
3848 Constructor.prototype.copy = function() {
3849 var copy = SuperConstructor.prototype.copy.call(this);
3850 this.nodes().forEach(function(u) {
3851 copy.parent(u, this.parent(u));
3856 Constructor.prototype.filterNodes = function(filter) {
3858 copy = SuperConstructor.prototype.filterNodes.call(this, filter);
3861 function findParent(u) {
3862 var parent = self.parent(u);
3863 if (parent === null || copy.hasNode(parent)) {
3864 parents[u] = parent;
3866 } else if (parent in parents) {
3867 return parents[parent];
3869 return findParent(parent);
3873 copy.eachNode(function(u) { copy.parent(u, findParent(u)); });
3881 },{"cp-data":19}],42:[function(require,module,exports){
3882 var Graph = require("../Graph"),
3883 Digraph = require("../Digraph"),
3884 CGraph = require("../CGraph"),
3885 CDigraph = require("../CDigraph");
3887 exports.decode = function(nodes, edges, Ctor) {
3888 Ctor = Ctor || Digraph;
3890 if (typeOf(nodes) !== "Array") {
3891 throw new Error("nodes is not an Array");
3894 if (typeOf(edges) !== "Array") {
3895 throw new Error("edges is not an Array");
3898 if (typeof Ctor === "string") {
3900 case "graph": Ctor = Graph; break;
3901 case "digraph": Ctor = Digraph; break;
3902 case "cgraph": Ctor = CGraph; break;
3903 case "cdigraph": Ctor = CDigraph; break;
3904 default: throw new Error("Unrecognized graph type: " + Ctor);
3908 var graph = new Ctor();
3910 nodes.forEach(function(u) {
3911 graph.addNode(u.id, u.value);
3914 // If the graph is compound, set up children...
3916 nodes.forEach(function(u) {
3918 u.children.forEach(function(v) {
3919 graph.parent(v, u.id);
3925 edges.forEach(function(e) {
3926 graph.addEdge(e.id, e.u, e.v, e.value);
3932 exports.encode = function(graph) {
3936 graph.eachNode(function(u, value) {
3937 var node = {id: u, value: value};
3938 if (graph.children) {
3939 var children = graph.children(u);
3940 if (children.length) {
3941 node.children = children;
3947 graph.eachEdge(function(e, u, v, value) {
3948 edges.push({id: e, u: u, v: v, value: value});
3952 if (graph instanceof CDigraph) {
3954 } else if (graph instanceof CGraph) {
3956 } else if (graph instanceof Digraph) {
3958 } else if (graph instanceof Graph) {
3961 throw new Error("Couldn't determine type of graph: " + graph);
3964 return { nodes: nodes, edges: edges, type: type };
3967 function typeOf(obj) {
3968 return Object.prototype.toString.call(obj).slice(8, -1);
3971 },{"../CDigraph":26,"../CGraph":27,"../Digraph":28,"../Graph":29}],43:[function(require,module,exports){
3973 var Set = require("cp-data").Set;
3976 exports.all = function() {
3977 return function() { return true; };
3980 exports.nodesFromList = function(nodes) {
3981 var set = new Set(nodes);
3982 return function(u) {
3987 },{"cp-data":19}],44:[function(require,module,exports){
3988 var Graph = require("./Graph"),
3989 Digraph = require("./Digraph");
3991 // Side-effect based changes are lousy, but node doesn't seem to resolve the
3995 * Returns a new directed graph using the nodes and edges from this graph. The
3996 * new graph will have the same nodes, but will have twice the number of edges:
3997 * each edge is split into two edges with opposite directions. Edge ids,
3998 * consequently, are not preserved by this transformation.
4000 Graph.prototype.toDigraph =
4001 Graph.prototype.asDirected = function() {
4002 var g = new Digraph();
4003 this.eachNode(function(u, value) { g.addNode(u, value); });
4004 this.eachEdge(function(e, u, v, value) {
4005 g.addEdge(null, u, v, value);
4006 g.addEdge(null, v, u, value);
4012 * Returns a new undirected graph using the nodes and edges from this graph.
4013 * The new graph will have the same nodes, but the edges will be made
4014 * undirected. Edge ids are preserved in this transformation.
4016 Digraph.prototype.toGraph =
4017 Digraph.prototype.asUndirected = function() {
4018 var g = new Graph();
4019 this.eachNode(function(u, value) { g.addNode(u, value); });
4020 this.eachEdge(function(e, u, v, value) {
4021 g.addEdge(e, u, v, value);
4026 },{"./Digraph":28,"./Graph":29}],45:[function(require,module,exports){
4027 // Returns an array of all values for properties of **o**.
4028 exports.values = function(o) {
4029 var ks = Object.keys(o),
4031 result = new Array(len),
4033 for (i = 0; i < len; ++i) {
4034 result[i] = o[ks[i]];
4039 },{}],46:[function(require,module,exports){
4040 module.exports = '0.7.4';
4044 joint.layout.DirectedGraph = {
4046 layout: function(graph, opt) {
4050 var inputGraph = this._prepareData(graph);
4051 var runner = dagre.layout();
4053 if (opt.debugLevel) { runner.debugLevel(opt.debugLevel); }
4054 if (opt.rankDir) { runner.rankDir(opt.rankDir); }
4055 if (opt.rankSep) { runner.rankSep(opt.rankSep); }
4056 if (opt.edgeSep) { runner.edgeSep(opt.edgeSep); }
4057 if (opt.nodeSep) { runner.nodeSep(opt.nodeSep); }
4059 var layoutGraph = runner.run(inputGraph);
4061 layoutGraph.eachNode(function(u, value) {
4063 graph.get('cells').get(u).set('position', {
4064 x: value.x - value.width/2,
4065 y: value.y - value.height/2
4070 if (opt.setLinkVertices) {
4072 layoutGraph.eachEdge(function(e, u, v, value) {
4073 var link = graph.get('cells').get(e);
4075 graph.get('cells').get(e).set('vertices', value.points);
4080 return { width: layoutGraph.graph().width, height: layoutGraph.graph().height };
4083 _prepareData: function(graph) {
4084 var dagreGraph = new dagre.Digraph();
4086 // For each element.
4087 _.each(graph.getElements(), function(cell) {
4089 if (dagreGraph.hasNode(cell.id)) return;
4091 dagreGraph.addNode(cell.id, {
4092 width: cell.get('size').width,
4093 height: cell.get('size').height,
4094 rank: cell.get('rank')
4099 _.each(graph.getLinks(), function(cell) {
4101 if (dagreGraph.hasEdge(cell.id)) return;
4103 var sourceId = cell.get('source').id;
4104 var targetId = cell.get('target').id;
4106 dagreGraph.addEdge(cell.id, sourceId, targetId, { minLen: cell.get('minLen') || 1 });