+++ /dev/null
-/*! JointJS v0.9.0 - JavaScript diagramming library 2014-05-13
-
-
-This Source Code Form is subject to the terms of the Mozilla Public
-License, v. 2.0. If a copy of the MPL was not distributed with this
-file, You can obtain one at http://mozilla.org/MPL/2.0/.
- */
-;(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){
-var global=typeof self !== "undefined" ? self : typeof window !== "undefined" ? window : {};/**
- * @license
- * Copyright (c) 2012-2013 Chris Pettitt
- *
- * Permission is hereby granted, free of charge, to any person obtaining a copy
- * of this software and associated documentation files (the "Software"), to deal
- * in the Software without restriction, including without limitation the rights
- * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
- * copies of the Software, and to permit persons to whom the Software is
- * furnished to do so, subject to the following conditions:
- *
- * The above copyright notice and this permission notice shall be included in
- * all copies or substantial portions of the Software.
- *
- * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
- * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
- * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
- * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
- * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
- * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
- * THE SOFTWARE.
- */
-global.dagre = require("./index");
-
-},{"./index":2}],2:[function(require,module,exports){
-/*
-Copyright (c) 2012-2013 Chris Pettitt
-
-Permission is hereby granted, free of charge, to any person obtaining a copy
-of this software and associated documentation files (the "Software"), to deal
-in the Software without restriction, including without limitation the rights
-to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
-copies of the Software, and to permit persons to whom the Software is
-furnished to do so, subject to the following conditions:
-
-The above copyright notice and this permission notice shall be included in
-all copies or substantial portions of the Software.
-
-THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
-IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
-FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
-AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
-LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
-OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
-THE SOFTWARE.
-*/
-exports.Digraph = require("graphlib").Digraph;
-exports.Graph = require("graphlib").Graph;
-exports.layout = require("./lib/layout");
-exports.version = require("./lib/version");
-
-},{"./lib/layout":3,"./lib/version":18,"graphlib":24}],3:[function(require,module,exports){
-var util = require('./util'),
- rank = require('./rank'),
- order = require('./order'),
- CGraph = require('graphlib').CGraph,
- CDigraph = require('graphlib').CDigraph;
-
-module.exports = function() {
- // External configuration
- var config = {
- // How much debug information to include?
- debugLevel: 2,
- // Max number of sweeps to perform in order phase
- orderMaxSweeps: order.DEFAULT_MAX_SWEEPS,
- // Use network simplex algorithm in ranking
- rankSimplex: false,
- // Rank direction. Valid values are (TB, LR)
- rankDir: 'TB'
- };
-
- // Phase functions
- var position = require('./position')();
-
- // This layout object
- var self = {};
-
- self.orderIters = util.propertyAccessor(self, config, 'orderMaxSweeps');
-
- self.rankSimplex = util.propertyAccessor(self, config, 'rankSimplex');
-
- self.nodeSep = delegateProperty(position.nodeSep);
- self.edgeSep = delegateProperty(position.edgeSep);
- self.universalSep = delegateProperty(position.universalSep);
- self.rankSep = delegateProperty(position.rankSep);
- self.rankDir = util.propertyAccessor(self, config, 'rankDir');
- self.debugAlignment = delegateProperty(position.debugAlignment);
-
- self.debugLevel = util.propertyAccessor(self, config, 'debugLevel', function(x) {
- util.log.level = x;
- position.debugLevel(x);
- });
-
- self.run = util.time('Total layout', run);
-
- self._normalize = normalize;
-
- return self;
-
- /*
- * Constructs an adjacency graph using the nodes and edges specified through
- * config. For each node and edge we add a property `dagre` that contains an
- * object that will hold intermediate and final layout information. Some of
- * the contents include:
- *
- * 1) A generated ID that uniquely identifies the object.
- * 2) Dimension information for nodes (copied from the source node).
- * 3) Optional dimension information for edges.
- *
- * After the adjacency graph is constructed the code no longer needs to use
- * the original nodes and edges passed in via config.
- */
- function initLayoutGraph(inputGraph) {
- var g = new CDigraph();
-
- inputGraph.eachNode(function(u, value) {
- if (value === undefined) value = {};
- g.addNode(u, {
- width: value.width,
- height: value.height
- });
- if (value.hasOwnProperty('rank')) {
- g.node(u).prefRank = value.rank;
- }
- });
-
- // Set up subgraphs
- if (inputGraph.parent) {
- inputGraph.nodes().forEach(function(u) {
- g.parent(u, inputGraph.parent(u));
- });
- }
-
- inputGraph.eachEdge(function(e, u, v, value) {
- if (value === undefined) value = {};
- var newValue = {
- e: e,
- minLen: value.minLen || 1,
- width: value.width || 0,
- height: value.height || 0,
- points: []
- };
-
- g.addEdge(null, u, v, newValue);
- });
-
- // Initial graph attributes
- var graphValue = inputGraph.graph() || {};
- g.graph({
- rankDir: graphValue.rankDir || config.rankDir,
- orderRestarts: graphValue.orderRestarts
- });
-
- return g;
- }
-
- function run(inputGraph) {
- var rankSep = self.rankSep();
- var g;
- try {
- // Build internal graph
- g = util.time('initLayoutGraph', initLayoutGraph)(inputGraph);
-
- if (g.order() === 0) {
- return g;
- }
-
- // Make space for edge labels
- g.eachEdge(function(e, s, t, a) {
- a.minLen *= 2;
- });
- self.rankSep(rankSep / 2);
-
- // Determine the rank for each node. Nodes with a lower rank will appear
- // above nodes of higher rank.
- util.time('rank.run', rank.run)(g, config.rankSimplex);
-
- // Normalize the graph by ensuring that every edge is proper (each edge has
- // a length of 1). We achieve this by adding dummy nodes to long edges,
- // thus shortening them.
- util.time('normalize', normalize)(g);
-
- // Order the nodes so that edge crossings are minimized.
- util.time('order', order)(g, config.orderMaxSweeps);
-
- // Find the x and y coordinates for every node in the graph.
- util.time('position', position.run)(g);
-
- // De-normalize the graph by removing dummy nodes and augmenting the
- // original long edges with coordinate information.
- util.time('undoNormalize', undoNormalize)(g);
-
- // Reverses points for edges that are in a reversed state.
- util.time('fixupEdgePoints', fixupEdgePoints)(g);
-
- // Restore delete edges and reverse edges that were reversed in the rank
- // phase.
- util.time('rank.restoreEdges', rank.restoreEdges)(g);
-
- // Construct final result graph and return it
- return util.time('createFinalGraph', createFinalGraph)(g, inputGraph.isDirected());
- } finally {
- self.rankSep(rankSep);
- }
- }
-
- /*
- * This function is responsible for 'normalizing' the graph. The process of
- * normalization ensures that no edge in the graph has spans more than one
- * rank. To do this it inserts dummy nodes as needed and links them by adding
- * dummy edges. This function keeps enough information in the dummy nodes and
- * edges to ensure that the original graph can be reconstructed later.
- *
- * This method assumes that the input graph is cycle free.
- */
- function normalize(g) {
- var dummyCount = 0;
- g.eachEdge(function(e, s, t, a) {
- var sourceRank = g.node(s).rank;
- var targetRank = g.node(t).rank;
- if (sourceRank + 1 < targetRank) {
- for (var u = s, rank = sourceRank + 1, i = 0; rank < targetRank; ++rank, ++i) {
- var v = '_D' + (++dummyCount);
- var node = {
- width: a.width,
- height: a.height,
- edge: { id: e, source: s, target: t, attrs: a },
- rank: rank,
- dummy: true
- };
-
- // If this node represents a bend then we will use it as a control
- // point. For edges with 2 segments this will be the center dummy
- // node. For edges with more than two segments, this will be the
- // first and last dummy node.
- if (i === 0) node.index = 0;
- else if (rank + 1 === targetRank) node.index = 1;
-
- g.addNode(v, node);
- g.addEdge(null, u, v, {});
- u = v;
- }
- g.addEdge(null, u, t, {});
- g.delEdge(e);
- }
- });
- }
-
- /*
- * Reconstructs the graph as it was before normalization. The positions of
- * dummy nodes are used to build an array of points for the original 'long'
- * edge. Dummy nodes and edges are removed.
- */
- function undoNormalize(g) {
- g.eachNode(function(u, a) {
- if (a.dummy) {
- if ('index' in a) {
- var edge = a.edge;
- if (!g.hasEdge(edge.id)) {
- g.addEdge(edge.id, edge.source, edge.target, edge.attrs);
- }
- var points = g.edge(edge.id).points;
- points[a.index] = { x: a.x, y: a.y, ul: a.ul, ur: a.ur, dl: a.dl, dr: a.dr };
- }
- g.delNode(u);
- }
- });
- }
-
- /*
- * For each edge that was reversed during the `acyclic` step, reverse its
- * array of points.
- */
- function fixupEdgePoints(g) {
- g.eachEdge(function(e, s, t, a) { if (a.reversed) a.points.reverse(); });
- }
-
- function createFinalGraph(g, isDirected) {
- var out = isDirected ? new CDigraph() : new CGraph();
- out.graph(g.graph());
- g.eachNode(function(u, value) { out.addNode(u, value); });
- g.eachNode(function(u) { out.parent(u, g.parent(u)); });
- g.eachEdge(function(e, u, v, value) {
- out.addEdge(value.e, u, v, value);
- });
-
- // Attach bounding box information
- var maxX = 0, maxY = 0;
- g.eachNode(function(u, value) {
- if (!g.children(u).length) {
- maxX = Math.max(maxX, value.x + value.width / 2);
- maxY = Math.max(maxY, value.y + value.height / 2);
- }
- });
- g.eachEdge(function(e, u, v, value) {
- var maxXPoints = Math.max.apply(Math, value.points.map(function(p) { return p.x; }));
- var maxYPoints = Math.max.apply(Math, value.points.map(function(p) { return p.y; }));
- maxX = Math.max(maxX, maxXPoints + value.width / 2);
- maxY = Math.max(maxY, maxYPoints + value.height / 2);
- });
- out.graph().width = maxX;
- out.graph().height = maxY;
-
- return out;
- }
-
- /*
- * Given a function, a new function is returned that invokes the given
- * function. The return value from the function is always the `self` object.
- */
- function delegateProperty(f) {
- return function() {
- if (!arguments.length) return f();
- f.apply(null, arguments);
- return self;
- };
- }
-};
-
-
-},{"./order":4,"./position":9,"./rank":10,"./util":17,"graphlib":24}],4:[function(require,module,exports){
-var util = require('./util'),
- crossCount = require('./order/crossCount'),
- initLayerGraphs = require('./order/initLayerGraphs'),
- initOrder = require('./order/initOrder'),
- sortLayer = require('./order/sortLayer');
-
-module.exports = order;
-
-// The maximum number of sweeps to perform before finishing the order phase.
-var DEFAULT_MAX_SWEEPS = 24;
-order.DEFAULT_MAX_SWEEPS = DEFAULT_MAX_SWEEPS;
-
-/*
- * Runs the order phase with the specified `graph, `maxSweeps`, and
- * `debugLevel`. If `maxSweeps` is not specified we use `DEFAULT_MAX_SWEEPS`.
- * If `debugLevel` is not set we assume 0.
- */
-function order(g, maxSweeps) {
- if (arguments.length < 2) {
- maxSweeps = DEFAULT_MAX_SWEEPS;
- }
-
- var restarts = g.graph().orderRestarts || 0;
-
- var layerGraphs = initLayerGraphs(g);
- // TODO: remove this when we add back support for ordering clusters
- layerGraphs.forEach(function(lg) {
- lg = lg.filterNodes(function(u) { return !g.children(u).length; });
- });
-
- var iters = 0,
- currentBestCC,
- allTimeBestCC = Number.MAX_VALUE,
- allTimeBest = {};
-
- function saveAllTimeBest() {
- g.eachNode(function(u, value) { allTimeBest[u] = value.order; });
- }
-
- for (var j = 0; j < Number(restarts) + 1 && allTimeBestCC !== 0; ++j) {
- currentBestCC = Number.MAX_VALUE;
- initOrder(g, restarts > 0);
-
- util.log(2, 'Order phase start cross count: ' + g.graph().orderInitCC);
-
- var i, lastBest, cc;
- for (i = 0, lastBest = 0; lastBest < 4 && i < maxSweeps && currentBestCC > 0; ++i, ++lastBest, ++iters) {
- sweep(g, layerGraphs, i);
- cc = crossCount(g);
- if (cc < currentBestCC) {
- lastBest = 0;
- currentBestCC = cc;
- if (cc < allTimeBestCC) {
- saveAllTimeBest();
- allTimeBestCC = cc;
- }
- }
- util.log(3, 'Order phase start ' + j + ' iter ' + i + ' cross count: ' + cc);
- }
- }
-
- Object.keys(allTimeBest).forEach(function(u) {
- if (!g.children || !g.children(u).length) {
- g.node(u).order = allTimeBest[u];
- }
- });
- g.graph().orderCC = allTimeBestCC;
-
- util.log(2, 'Order iterations: ' + iters);
- util.log(2, 'Order phase best cross count: ' + g.graph().orderCC);
-}
-
-function predecessorWeights(g, nodes) {
- var weights = {};
- nodes.forEach(function(u) {
- weights[u] = g.inEdges(u).map(function(e) {
- return g.node(g.source(e)).order;
- });
- });
- return weights;
-}
-
-function successorWeights(g, nodes) {
- var weights = {};
- nodes.forEach(function(u) {
- weights[u] = g.outEdges(u).map(function(e) {
- return g.node(g.target(e)).order;
- });
- });
- return weights;
-}
-
-function sweep(g, layerGraphs, iter) {
- if (iter % 2 === 0) {
- sweepDown(g, layerGraphs, iter);
- } else {
- sweepUp(g, layerGraphs, iter);
- }
-}
-
-function sweepDown(g, layerGraphs) {
- var cg;
- for (i = 1; i < layerGraphs.length; ++i) {
- cg = sortLayer(layerGraphs[i], cg, predecessorWeights(g, layerGraphs[i].nodes()));
- }
-}
-
-function sweepUp(g, layerGraphs) {
- var cg;
- for (i = layerGraphs.length - 2; i >= 0; --i) {
- sortLayer(layerGraphs[i], cg, successorWeights(g, layerGraphs[i].nodes()));
- }
-}
-
-},{"./order/crossCount":5,"./order/initLayerGraphs":6,"./order/initOrder":7,"./order/sortLayer":8,"./util":17}],5:[function(require,module,exports){
-var util = require('../util');
-
-module.exports = crossCount;
-
-/*
- * Returns the cross count for the given graph.
- */
-function crossCount(g) {
- var cc = 0;
- var ordering = util.ordering(g);
- for (var i = 1; i < ordering.length; ++i) {
- cc += twoLayerCrossCount(g, ordering[i-1], ordering[i]);
- }
- return cc;
-}
-
-/*
- * This function searches through a ranked and ordered graph and counts the
- * number of edges that cross. This algorithm is derived from:
- *
- * W. Barth et al., Bilayer Cross Counting, JGAA, 8(2) 179–194 (2004)
- */
-function twoLayerCrossCount(g, layer1, layer2) {
- var indices = [];
- layer1.forEach(function(u) {
- var nodeIndices = [];
- g.outEdges(u).forEach(function(e) { nodeIndices.push(g.node(g.target(e)).order); });
- nodeIndices.sort(function(x, y) { return x - y; });
- indices = indices.concat(nodeIndices);
- });
-
- var firstIndex = 1;
- while (firstIndex < layer2.length) firstIndex <<= 1;
-
- var treeSize = 2 * firstIndex - 1;
- firstIndex -= 1;
-
- var tree = [];
- for (var i = 0; i < treeSize; ++i) { tree[i] = 0; }
-
- var cc = 0;
- indices.forEach(function(i) {
- var treeIndex = i + firstIndex;
- ++tree[treeIndex];
- while (treeIndex > 0) {
- if (treeIndex % 2) {
- cc += tree[treeIndex + 1];
- }
- treeIndex = (treeIndex - 1) >> 1;
- ++tree[treeIndex];
- }
- });
-
- return cc;
-}
-
-},{"../util":17}],6:[function(require,module,exports){
-var nodesFromList = require('graphlib').filter.nodesFromList,
- /* jshint -W079 */
- Set = require('cp-data').Set;
-
-module.exports = initLayerGraphs;
-
-/*
- * This function takes a compound layered graph, g, and produces an array of
- * layer graphs. Each entry in the array represents a subgraph of nodes
- * relevant for performing crossing reduction on that layer.
- */
-function initLayerGraphs(g) {
- var ranks = [];
-
- function dfs(u) {
- if (u === null) {
- g.children(u).forEach(function(v) { dfs(v); });
- return;
- }
-
- var value = g.node(u);
- value.minRank = ('rank' in value) ? value.rank : Number.MAX_VALUE;
- value.maxRank = ('rank' in value) ? value.rank : Number.MIN_VALUE;
- var uRanks = new Set();
- g.children(u).forEach(function(v) {
- var rs = dfs(v);
- uRanks = Set.union([uRanks, rs]);
- value.minRank = Math.min(value.minRank, g.node(v).minRank);
- value.maxRank = Math.max(value.maxRank, g.node(v).maxRank);
- });
-
- if ('rank' in value) uRanks.add(value.rank);
-
- uRanks.keys().forEach(function(r) {
- if (!(r in ranks)) ranks[r] = [];
- ranks[r].push(u);
- });
-
- return uRanks;
- }
- dfs(null);
-
- var layerGraphs = [];
- ranks.forEach(function(us, rank) {
- layerGraphs[rank] = g.filterNodes(nodesFromList(us));
- });
-
- return layerGraphs;
-}
-
-},{"cp-data":19,"graphlib":24}],7:[function(require,module,exports){
-var crossCount = require('./crossCount'),
- util = require('../util');
-
-module.exports = initOrder;
-
-/*
- * Given a graph with a set of layered nodes (i.e. nodes that have a `rank`
- * attribute) this function attaches an `order` attribute that uniquely
- * arranges each node of each rank. If no constraint graph is provided the
- * order of the nodes in each rank is entirely arbitrary.
- */
-function initOrder(g, random) {
- var layers = [];
-
- g.eachNode(function(u, value) {
- var layer = layers[value.rank];
- if (g.children && g.children(u).length > 0) return;
- if (!layer) {
- layer = layers[value.rank] = [];
- }
- layer.push(u);
- });
-
- layers.forEach(function(layer) {
- if (random) {
- util.shuffle(layer);
- }
- layer.forEach(function(u, i) {
- g.node(u).order = i;
- });
- });
-
- var cc = crossCount(g);
- g.graph().orderInitCC = cc;
- g.graph().orderCC = Number.MAX_VALUE;
-}
-
-},{"../util":17,"./crossCount":5}],8:[function(require,module,exports){
-var util = require('../util');
-/*
- Digraph = require('graphlib').Digraph,
- topsort = require('graphlib').alg.topsort,
- nodesFromList = require('graphlib').filter.nodesFromList;
-*/
-
-module.exports = sortLayer;
-
-/*
-function sortLayer(g, cg, weights) {
- var result = sortLayerSubgraph(g, null, cg, weights);
- result.list.forEach(function(u, i) {
- g.node(u).order = i;
- });
- return result.constraintGraph;
-}
-*/
-
-function sortLayer(g, cg, weights) {
- var ordering = [];
- var bs = {};
- g.eachNode(function(u, value) {
- ordering[value.order] = u;
- var ws = weights[u];
- if (ws.length) {
- bs[u] = util.sum(ws) / ws.length;
- }
- });
-
- var toSort = g.nodes().filter(function(u) { return bs[u] !== undefined; });
- toSort.sort(function(x, y) {
- return bs[x] - bs[y] || g.node(x).order - g.node(y).order;
- });
-
- for (var i = 0, j = 0, jl = toSort.length; j < jl; ++i) {
- if (bs[ordering[i]] !== undefined) {
- g.node(toSort[j++]).order = i;
- }
- }
-}
-
-// TOOD: re-enable constrained sorting once we have a strategy for handling
-// undefined barycenters.
-/*
-function sortLayerSubgraph(g, sg, cg, weights) {
- cg = cg ? cg.filterNodes(nodesFromList(g.children(sg))) : new Digraph();
-
- var nodeData = {};
- g.children(sg).forEach(function(u) {
- if (g.children(u).length) {
- nodeData[u] = sortLayerSubgraph(g, u, cg, weights);
- nodeData[u].firstSG = u;
- nodeData[u].lastSG = u;
- } else {
- var ws = weights[u];
- nodeData[u] = {
- degree: ws.length,
- barycenter: ws.length > 0 ? util.sum(ws) / ws.length : 0,
- list: [u]
- };
- }
- });
-
- resolveViolatedConstraints(g, cg, nodeData);
-
- var keys = Object.keys(nodeData);
- keys.sort(function(x, y) {
- return nodeData[x].barycenter - nodeData[y].barycenter;
- });
-
- var result = keys.map(function(u) { return nodeData[u]; })
- .reduce(function(lhs, rhs) { return mergeNodeData(g, lhs, rhs); });
- return result;
-}
-
-/*
-function mergeNodeData(g, lhs, rhs) {
- var cg = mergeDigraphs(lhs.constraintGraph, rhs.constraintGraph);
-
- if (lhs.lastSG !== undefined && rhs.firstSG !== undefined) {
- if (cg === undefined) {
- cg = new Digraph();
- }
- if (!cg.hasNode(lhs.lastSG)) { cg.addNode(lhs.lastSG); }
- cg.addNode(rhs.firstSG);
- cg.addEdge(null, lhs.lastSG, rhs.firstSG);
- }
-
- return {
- degree: lhs.degree + rhs.degree,
- barycenter: (lhs.barycenter * lhs.degree + rhs.barycenter * rhs.degree) /
- (lhs.degree + rhs.degree),
- list: lhs.list.concat(rhs.list),
- firstSG: lhs.firstSG !== undefined ? lhs.firstSG : rhs.firstSG,
- lastSG: rhs.lastSG !== undefined ? rhs.lastSG : lhs.lastSG,
- constraintGraph: cg
- };
-}
-
-function mergeDigraphs(lhs, rhs) {
- if (lhs === undefined) return rhs;
- if (rhs === undefined) return lhs;
-
- lhs = lhs.copy();
- rhs.nodes().forEach(function(u) { lhs.addNode(u); });
- rhs.edges().forEach(function(e, u, v) { lhs.addEdge(null, u, v); });
- return lhs;
-}
-
-function resolveViolatedConstraints(g, cg, nodeData) {
- // Removes nodes `u` and `v` from `cg` and makes any edges incident on them
- // incident on `w` instead.
- function collapseNodes(u, v, w) {
- // TODO original paper removes self loops, but it is not obvious when this would happen
- cg.inEdges(u).forEach(function(e) {
- cg.delEdge(e);
- cg.addEdge(null, cg.source(e), w);
- });
-
- cg.outEdges(v).forEach(function(e) {
- cg.delEdge(e);
- cg.addEdge(null, w, cg.target(e));
- });
-
- cg.delNode(u);
- cg.delNode(v);
- }
-
- var violated;
- while ((violated = findViolatedConstraint(cg, nodeData)) !== undefined) {
- var source = cg.source(violated),
- target = cg.target(violated);
-
- var v;
- while ((v = cg.addNode(null)) && g.hasNode(v)) {
- cg.delNode(v);
- }
-
- // Collapse barycenter and list
- nodeData[v] = mergeNodeData(g, nodeData[source], nodeData[target]);
- delete nodeData[source];
- delete nodeData[target];
-
- collapseNodes(source, target, v);
- if (cg.incidentEdges(v).length === 0) { cg.delNode(v); }
- }
-}
-
-function findViolatedConstraint(cg, nodeData) {
- var us = topsort(cg);
- for (var i = 0; i < us.length; ++i) {
- var u = us[i];
- var inEdges = cg.inEdges(u);
- for (var j = 0; j < inEdges.length; ++j) {
- var e = inEdges[j];
- if (nodeData[cg.source(e)].barycenter >= nodeData[u].barycenter) {
- return e;
- }
- }
- }
-}
-*/
-
-},{"../util":17}],9:[function(require,module,exports){
-var util = require('./util');
-
-/*
- * The algorithms here are based on Brandes and Köpf, "Fast and Simple
- * Horizontal Coordinate Assignment".
- */
-module.exports = function() {
- // External configuration
- var config = {
- nodeSep: 50,
- edgeSep: 10,
- universalSep: null,
- rankSep: 30
- };
-
- var self = {};
-
- self.nodeSep = util.propertyAccessor(self, config, 'nodeSep');
- self.edgeSep = util.propertyAccessor(self, config, 'edgeSep');
- // If not null this separation value is used for all nodes and edges
- // regardless of their widths. `nodeSep` and `edgeSep` are ignored with this
- // option.
- self.universalSep = util.propertyAccessor(self, config, 'universalSep');
- self.rankSep = util.propertyAccessor(self, config, 'rankSep');
- self.debugLevel = util.propertyAccessor(self, config, 'debugLevel');
-
- self.run = run;
-
- return self;
-
- function run(g) {
- g = g.filterNodes(util.filterNonSubgraphs(g));
-
- var layering = util.ordering(g);
-
- var conflicts = findConflicts(g, layering);
-
- var xss = {};
- ['u', 'd'].forEach(function(vertDir) {
- if (vertDir === 'd') layering.reverse();
-
- ['l', 'r'].forEach(function(horizDir) {
- if (horizDir === 'r') reverseInnerOrder(layering);
-
- var dir = vertDir + horizDir;
- var align = verticalAlignment(g, layering, conflicts, vertDir === 'u' ? 'predecessors' : 'successors');
- xss[dir]= horizontalCompaction(g, layering, align.pos, align.root, align.align);
-
- if (config.debugLevel >= 3)
- debugPositioning(vertDir + horizDir, g, layering, xss[dir]);
-
- if (horizDir === 'r') flipHorizontally(xss[dir]);
-
- if (horizDir === 'r') reverseInnerOrder(layering);
- });
-
- if (vertDir === 'd') layering.reverse();
- });
-
- balance(g, layering, xss);
-
- g.eachNode(function(v) {
- var xs = [];
- for (var alignment in xss) {
- var alignmentX = xss[alignment][v];
- posXDebug(alignment, g, v, alignmentX);
- xs.push(alignmentX);
- }
- xs.sort(function(x, y) { return x - y; });
- posX(g, v, (xs[1] + xs[2]) / 2);
- });
-
- // Align y coordinates with ranks
- var y = 0, reverseY = g.graph().rankDir === 'BT' || g.graph().rankDir === 'RL';
- layering.forEach(function(layer) {
- var maxHeight = util.max(layer.map(function(u) { return height(g, u); }));
- y += maxHeight / 2;
- layer.forEach(function(u) {
- posY(g, u, reverseY ? -y : y);
- });
- y += maxHeight / 2 + config.rankSep;
- });
-
- // Translate layout so that top left corner of bounding rectangle has
- // coordinate (0, 0).
- var minX = util.min(g.nodes().map(function(u) { return posX(g, u) - width(g, u) / 2; }));
- var minY = util.min(g.nodes().map(function(u) { return posY(g, u) - height(g, u) / 2; }));
- g.eachNode(function(u) {
- posX(g, u, posX(g, u) - minX);
- posY(g, u, posY(g, u) - minY);
- });
- }
-
- /*
- * Generate an ID that can be used to represent any undirected edge that is
- * incident on `u` and `v`.
- */
- function undirEdgeId(u, v) {
- return u < v
- ? u.toString().length + ':' + u + '-' + v
- : v.toString().length + ':' + v + '-' + u;
- }
-
- function findConflicts(g, layering) {
- var conflicts = {}, // Set of conflicting edge ids
- pos = {}, // Position of node in its layer
- prevLayer,
- currLayer,
- k0, // Position of the last inner segment in the previous layer
- l, // Current position in the current layer (for iteration up to `l1`)
- k1; // Position of the next inner segment in the previous layer or
- // the position of the last element in the previous layer
-
- if (layering.length <= 2) return conflicts;
-
- function updateConflicts(v) {
- var k = pos[v];
- if (k < k0 || k > k1) {
- conflicts[undirEdgeId(currLayer[l], v)] = true;
- }
- }
-
- layering[1].forEach(function(u, i) { pos[u] = i; });
- for (var i = 1; i < layering.length - 1; ++i) {
- prevLayer = layering[i];
- currLayer = layering[i+1];
- k0 = 0;
- l = 0;
-
- // Scan current layer for next node that is incident to an inner segement
- // between layering[i+1] and layering[i].
- for (var l1 = 0; l1 < currLayer.length; ++l1) {
- var u = currLayer[l1]; // Next inner segment in the current layer or
- // last node in the current layer
- pos[u] = l1;
- k1 = undefined;
-
- if (g.node(u).dummy) {
- var uPred = g.predecessors(u)[0];
- // Note: In the case of self loops and sideways edges it is possible
- // for a dummy not to have a predecessor.
- if (uPred !== undefined && g.node(uPred).dummy)
- k1 = pos[uPred];
- }
- if (k1 === undefined && l1 === currLayer.length - 1)
- k1 = prevLayer.length - 1;
-
- if (k1 !== undefined) {
- for (; l <= l1; ++l) {
- g.predecessors(currLayer[l]).forEach(updateConflicts);
- }
- k0 = k1;
- }
- }
- }
-
- return conflicts;
- }
-
- function verticalAlignment(g, layering, conflicts, relationship) {
- var pos = {}, // Position for a node in its layer
- root = {}, // Root of the block that the node participates in
- align = {}; // Points to the next node in the block or, if the last
- // element in the block, points to the first block's root
-
- layering.forEach(function(layer) {
- layer.forEach(function(u, i) {
- root[u] = u;
- align[u] = u;
- pos[u] = i;
- });
- });
-
- layering.forEach(function(layer) {
- var prevIdx = -1;
- layer.forEach(function(v) {
- var related = g[relationship](v), // Adjacent nodes from the previous layer
- mid; // The mid point in the related array
-
- if (related.length > 0) {
- related.sort(function(x, y) { return pos[x] - pos[y]; });
- mid = (related.length - 1) / 2;
- related.slice(Math.floor(mid), Math.ceil(mid) + 1).forEach(function(u) {
- if (align[v] === v) {
- if (!conflicts[undirEdgeId(u, v)] && prevIdx < pos[u]) {
- align[u] = v;
- align[v] = root[v] = root[u];
- prevIdx = pos[u];
- }
- }
- });
- }
- });
- });
-
- return { pos: pos, root: root, align: align };
- }
-
- // This function deviates from the standard BK algorithm in two ways. First
- // it takes into account the size of the nodes. Second it includes a fix to
- // the original algorithm that is described in Carstens, "Node and Label
- // Placement in a Layered Layout Algorithm".
- function horizontalCompaction(g, layering, pos, root, align) {
- var sink = {}, // Mapping of node id -> sink node id for class
- maybeShift = {}, // Mapping of sink node id -> { class node id, min shift }
- shift = {}, // Mapping of sink node id -> shift
- pred = {}, // Mapping of node id -> predecessor node (or null)
- xs = {}; // Calculated X positions
-
- layering.forEach(function(layer) {
- layer.forEach(function(u, i) {
- sink[u] = u;
- maybeShift[u] = {};
- if (i > 0)
- pred[u] = layer[i - 1];
- });
- });
-
- function updateShift(toShift, neighbor, delta) {
- if (!(neighbor in maybeShift[toShift])) {
- maybeShift[toShift][neighbor] = delta;
- } else {
- maybeShift[toShift][neighbor] = Math.min(maybeShift[toShift][neighbor], delta);
- }
- }
-
- function placeBlock(v) {
- if (!(v in xs)) {
- xs[v] = 0;
- var w = v;
- do {
- if (pos[w] > 0) {
- var u = root[pred[w]];
- placeBlock(u);
- if (sink[v] === v) {
- sink[v] = sink[u];
- }
- var delta = sep(g, pred[w]) + sep(g, w);
- if (sink[v] !== sink[u]) {
- updateShift(sink[u], sink[v], xs[v] - xs[u] - delta);
- } else {
- xs[v] = Math.max(xs[v], xs[u] + delta);
- }
- }
- w = align[w];
- } while (w !== v);
- }
- }
-
- // Root coordinates relative to sink
- util.values(root).forEach(function(v) {
- placeBlock(v);
- });
-
- // Absolute coordinates
- // There is an assumption here that we've resolved shifts for any classes
- // that begin at an earlier layer. We guarantee this by visiting layers in
- // order.
- layering.forEach(function(layer) {
- layer.forEach(function(v) {
- xs[v] = xs[root[v]];
- if (v === root[v] && v === sink[v]) {
- var minShift = 0;
- if (v in maybeShift && Object.keys(maybeShift[v]).length > 0) {
- minShift = util.min(Object.keys(maybeShift[v])
- .map(function(u) {
- return maybeShift[v][u] + (u in shift ? shift[u] : 0);
- }
- ));
- }
- shift[v] = minShift;
- }
- });
- });
-
- layering.forEach(function(layer) {
- layer.forEach(function(v) {
- xs[v] += shift[sink[root[v]]] || 0;
- });
- });
-
- return xs;
- }
-
- function findMinCoord(g, layering, xs) {
- return util.min(layering.map(function(layer) {
- var u = layer[0];
- return xs[u];
- }));
- }
-
- function findMaxCoord(g, layering, xs) {
- return util.max(layering.map(function(layer) {
- var u = layer[layer.length - 1];
- return xs[u];
- }));
- }
-
- function balance(g, layering, xss) {
- var min = {}, // Min coordinate for the alignment
- max = {}, // Max coordinate for the alginment
- smallestAlignment,
- shift = {}; // Amount to shift a given alignment
-
- function updateAlignment(v) {
- xss[alignment][v] += shift[alignment];
- }
-
- var smallest = Number.POSITIVE_INFINITY;
- for (var alignment in xss) {
- var xs = xss[alignment];
- min[alignment] = findMinCoord(g, layering, xs);
- max[alignment] = findMaxCoord(g, layering, xs);
- var w = max[alignment] - min[alignment];
- if (w < smallest) {
- smallest = w;
- smallestAlignment = alignment;
- }
- }
-
- // Determine how much to adjust positioning for each alignment
- ['u', 'd'].forEach(function(vertDir) {
- ['l', 'r'].forEach(function(horizDir) {
- var alignment = vertDir + horizDir;
- shift[alignment] = horizDir === 'l'
- ? min[smallestAlignment] - min[alignment]
- : max[smallestAlignment] - max[alignment];
- });
- });
-
- // Find average of medians for xss array
- for (alignment in xss) {
- g.eachNode(updateAlignment);
- }
- }
-
- function flipHorizontally(xs) {
- for (var u in xs) {
- xs[u] = -xs[u];
- }
- }
-
- function reverseInnerOrder(layering) {
- layering.forEach(function(layer) {
- layer.reverse();
- });
- }
-
- function width(g, u) {
- switch (g.graph().rankDir) {
- case 'LR': return g.node(u).height;
- case 'RL': return g.node(u).height;
- default: return g.node(u).width;
- }
- }
-
- function height(g, u) {
- switch(g.graph().rankDir) {
- case 'LR': return g.node(u).width;
- case 'RL': return g.node(u).width;
- default: return g.node(u).height;
- }
- }
-
- function sep(g, u) {
- if (config.universalSep !== null) {
- return config.universalSep;
- }
- var w = width(g, u);
- var s = g.node(u).dummy ? config.edgeSep : config.nodeSep;
- return (w + s) / 2;
- }
-
- function posX(g, u, x) {
- if (g.graph().rankDir === 'LR' || g.graph().rankDir === 'RL') {
- if (arguments.length < 3) {
- return g.node(u).y;
- } else {
- g.node(u).y = x;
- }
- } else {
- if (arguments.length < 3) {
- return g.node(u).x;
- } else {
- g.node(u).x = x;
- }
- }
- }
-
- function posXDebug(name, g, u, x) {
- if (g.graph().rankDir === 'LR' || g.graph().rankDir === 'RL') {
- if (arguments.length < 3) {
- return g.node(u)[name];
- } else {
- g.node(u)[name] = x;
- }
- } else {
- if (arguments.length < 3) {
- return g.node(u)[name];
- } else {
- g.node(u)[name] = x;
- }
- }
- }
-
- function posY(g, u, y) {
- if (g.graph().rankDir === 'LR' || g.graph().rankDir === 'RL') {
- if (arguments.length < 3) {
- return g.node(u).x;
- } else {
- g.node(u).x = y;
- }
- } else {
- if (arguments.length < 3) {
- return g.node(u).y;
- } else {
- g.node(u).y = y;
- }
- }
- }
-
- function debugPositioning(align, g, layering, xs) {
- layering.forEach(function(l, li) {
- var u, xU;
- l.forEach(function(v) {
- var xV = xs[v];
- if (u) {
- var s = sep(g, u) + sep(g, v);
- if (xV - xU < s)
- console.log('Position phase: sep violation. Align: ' + align + '. Layer: ' + li + '. ' +
- 'U: ' + u + ' V: ' + v + '. Actual sep: ' + (xV - xU) + ' Expected sep: ' + s);
- }
- u = v;
- xU = xV;
- });
- });
- }
-};
-
-},{"./util":17}],10:[function(require,module,exports){
-var util = require('./util'),
- acyclic = require('./rank/acyclic'),
- initRank = require('./rank/initRank'),
- feasibleTree = require('./rank/feasibleTree'),
- constraints = require('./rank/constraints'),
- simplex = require('./rank/simplex'),
- components = require('graphlib').alg.components,
- filter = require('graphlib').filter;
-
-exports.run = run;
-exports.restoreEdges = restoreEdges;
-
-/*
- * Heuristic function that assigns a rank to each node of the input graph with
- * the intent of minimizing edge lengths, while respecting the `minLen`
- * attribute of incident edges.
- *
- * Prerequisites:
- *
- * * Each edge in the input graph must have an assigned 'minLen' attribute
- */
-function run(g, useSimplex) {
- expandSelfLoops(g);
-
- // If there are rank constraints on nodes, then build a new graph that
- // encodes the constraints.
- util.time('constraints.apply', constraints.apply)(g);
-
- expandSidewaysEdges(g);
-
- // Reverse edges to get an acyclic graph, we keep the graph in an acyclic
- // state until the very end.
- util.time('acyclic', acyclic)(g);
-
- // Convert the graph into a flat graph for ranking
- var flatGraph = g.filterNodes(util.filterNonSubgraphs(g));
-
- // Assign an initial ranking using DFS.
- initRank(flatGraph);
-
- // For each component improve the assigned ranks.
- components(flatGraph).forEach(function(cmpt) {
- var subgraph = flatGraph.filterNodes(filter.nodesFromList(cmpt));
- rankComponent(subgraph, useSimplex);
- });
-
- // Relax original constraints
- util.time('constraints.relax', constraints.relax(g));
-
- // When handling nodes with constrained ranks it is possible to end up with
- // edges that point to previous ranks. Most of the subsequent algorithms assume
- // that edges are pointing to successive ranks only. Here we reverse any "back
- // edges" and mark them as such. The acyclic algorithm will reverse them as a
- // post processing step.
- util.time('reorientEdges', reorientEdges)(g);
-}
-
-function restoreEdges(g) {
- acyclic.undo(g);
-}
-
-/*
- * Expand self loops into three dummy nodes. One will sit above the incident
- * node, one will be at the same level, and one below. The result looks like:
- *
- * /--<--x--->--\
- * node y
- * \--<--z--->--/
- *
- * Dummy nodes x, y, z give us the shape of a loop and node y is where we place
- * the label.
- *
- * TODO: consolidate knowledge of dummy node construction.
- * TODO: support minLen = 2
- */
-function expandSelfLoops(g) {
- g.eachEdge(function(e, u, v, a) {
- if (u === v) {
- var x = addDummyNode(g, e, u, v, a, 0, false),
- y = addDummyNode(g, e, u, v, a, 1, true),
- z = addDummyNode(g, e, u, v, a, 2, false);
- g.addEdge(null, x, u, {minLen: 1, selfLoop: true});
- g.addEdge(null, x, y, {minLen: 1, selfLoop: true});
- g.addEdge(null, u, z, {minLen: 1, selfLoop: true});
- g.addEdge(null, y, z, {minLen: 1, selfLoop: true});
- g.delEdge(e);
- }
- });
-}
-
-function expandSidewaysEdges(g) {
- g.eachEdge(function(e, u, v, a) {
- if (u === v) {
- var origEdge = a.originalEdge,
- dummy = addDummyNode(g, origEdge.e, origEdge.u, origEdge.v, origEdge.value, 0, true);
- g.addEdge(null, u, dummy, {minLen: 1});
- g.addEdge(null, dummy, v, {minLen: 1});
- g.delEdge(e);
- }
- });
-}
-
-function addDummyNode(g, e, u, v, a, index, isLabel) {
- return g.addNode(null, {
- width: isLabel ? a.width : 0,
- height: isLabel ? a.height : 0,
- edge: { id: e, source: u, target: v, attrs: a },
- dummy: true,
- index: index
- });
-}
-
-function reorientEdges(g) {
- g.eachEdge(function(e, u, v, value) {
- if (g.node(u).rank > g.node(v).rank) {
- g.delEdge(e);
- value.reversed = true;
- g.addEdge(e, v, u, value);
- }
- });
-}
-
-function rankComponent(subgraph, useSimplex) {
- var spanningTree = feasibleTree(subgraph);
-
- if (useSimplex) {
- util.log(1, 'Using network simplex for ranking');
- simplex(subgraph, spanningTree);
- }
- normalize(subgraph);
-}
-
-function normalize(g) {
- var m = util.min(g.nodes().map(function(u) { return g.node(u).rank; }));
- g.eachNode(function(u, node) { node.rank -= m; });
-}
-
-},{"./rank/acyclic":11,"./rank/constraints":12,"./rank/feasibleTree":13,"./rank/initRank":14,"./rank/simplex":16,"./util":17,"graphlib":24}],11:[function(require,module,exports){
-var util = require('../util');
-
-module.exports = acyclic;
-module.exports.undo = undo;
-
-/*
- * This function takes a directed graph that may have cycles and reverses edges
- * as appropriate to break these cycles. Each reversed edge is assigned a
- * `reversed` attribute with the value `true`.
- *
- * There should be no self loops in the graph.
- */
-function acyclic(g) {
- var onStack = {},
- visited = {},
- reverseCount = 0;
-
- function dfs(u) {
- if (u in visited) return;
- visited[u] = onStack[u] = true;
- g.outEdges(u).forEach(function(e) {
- var t = g.target(e),
- value;
-
- if (u === t) {
- console.error('Warning: found self loop "' + e + '" for node "' + u + '"');
- } else if (t in onStack) {
- value = g.edge(e);
- g.delEdge(e);
- value.reversed = true;
- ++reverseCount;
- g.addEdge(e, t, u, value);
- } else {
- dfs(t);
- }
- });
-
- delete onStack[u];
- }
-
- g.eachNode(function(u) { dfs(u); });
-
- util.log(2, 'Acyclic Phase: reversed ' + reverseCount + ' edge(s)');
-
- return reverseCount;
-}
-
-/*
- * Given a graph that has had the acyclic operation applied, this function
- * undoes that operation. More specifically, any edge with the `reversed`
- * attribute is again reversed to restore the original direction of the edge.
- */
-function undo(g) {
- g.eachEdge(function(e, s, t, a) {
- if (a.reversed) {
- delete a.reversed;
- g.delEdge(e);
- g.addEdge(e, t, s, a);
- }
- });
-}
-
-},{"../util":17}],12:[function(require,module,exports){
-exports.apply = function(g) {
- function dfs(sg) {
- var rankSets = {};
- g.children(sg).forEach(function(u) {
- if (g.children(u).length) {
- dfs(u);
- return;
- }
-
- var value = g.node(u),
- prefRank = value.prefRank;
- if (prefRank !== undefined) {
- if (!checkSupportedPrefRank(prefRank)) { return; }
-
- if (!(prefRank in rankSets)) {
- rankSets.prefRank = [u];
- } else {
- rankSets.prefRank.push(u);
- }
-
- var newU = rankSets[prefRank];
- if (newU === undefined) {
- newU = rankSets[prefRank] = g.addNode(null, { originalNodes: [] });
- g.parent(newU, sg);
- }
-
- redirectInEdges(g, u, newU, prefRank === 'min');
- redirectOutEdges(g, u, newU, prefRank === 'max');
-
- // Save original node and remove it from reduced graph
- g.node(newU).originalNodes.push({ u: u, value: value, parent: sg });
- g.delNode(u);
- }
- });
-
- addLightEdgesFromMinNode(g, sg, rankSets.min);
- addLightEdgesToMaxNode(g, sg, rankSets.max);
- }
-
- dfs(null);
-};
-
-function checkSupportedPrefRank(prefRank) {
- if (prefRank !== 'min' && prefRank !== 'max' && prefRank.indexOf('same_') !== 0) {
- console.error('Unsupported rank type: ' + prefRank);
- return false;
- }
- return true;
-}
-
-function redirectInEdges(g, u, newU, reverse) {
- g.inEdges(u).forEach(function(e) {
- var origValue = g.edge(e),
- value;
- if (origValue.originalEdge) {
- value = origValue;
- } else {
- value = {
- originalEdge: { e: e, u: g.source(e), v: g.target(e), value: origValue },
- minLen: g.edge(e).minLen
- };
- }
-
- // Do not reverse edges for self-loops.
- if (origValue.selfLoop) {
- reverse = false;
- }
-
- if (reverse) {
- // Ensure that all edges to min are reversed
- g.addEdge(null, newU, g.source(e), value);
- value.reversed = true;
- } else {
- g.addEdge(null, g.source(e), newU, value);
- }
- });
-}
-
-function redirectOutEdges(g, u, newU, reverse) {
- g.outEdges(u).forEach(function(e) {
- var origValue = g.edge(e),
- value;
- if (origValue.originalEdge) {
- value = origValue;
- } else {
- value = {
- originalEdge: { e: e, u: g.source(e), v: g.target(e), value: origValue },
- minLen: g.edge(e).minLen
- };
- }
-
- // Do not reverse edges for self-loops.
- if (origValue.selfLoop) {
- reverse = false;
- }
-
- if (reverse) {
- // Ensure that all edges from max are reversed
- g.addEdge(null, g.target(e), newU, value);
- value.reversed = true;
- } else {
- g.addEdge(null, newU, g.target(e), value);
- }
- });
-}
-
-function addLightEdgesFromMinNode(g, sg, minNode) {
- if (minNode !== undefined) {
- g.children(sg).forEach(function(u) {
- // The dummy check ensures we don't add an edge if the node is involved
- // in a self loop or sideways edge.
- if (u !== minNode && !g.outEdges(minNode, u).length && !g.node(u).dummy) {
- g.addEdge(null, minNode, u, { minLen: 0 });
- }
- });
- }
-}
-
-function addLightEdgesToMaxNode(g, sg, maxNode) {
- if (maxNode !== undefined) {
- g.children(sg).forEach(function(u) {
- // The dummy check ensures we don't add an edge if the node is involved
- // in a self loop or sideways edge.
- if (u !== maxNode && !g.outEdges(u, maxNode).length && !g.node(u).dummy) {
- g.addEdge(null, u, maxNode, { minLen: 0 });
- }
- });
- }
-}
-
-/*
- * This function "relaxes" the constraints applied previously by the "apply"
- * function. It expands any nodes that were collapsed and assigns the rank of
- * the collapsed node to each of the expanded nodes. It also restores the
- * original edges and removes any dummy edges pointing at the collapsed nodes.
- *
- * Note that the process of removing collapsed nodes also removes dummy edges
- * automatically.
- */
-exports.relax = function(g) {
- // Save original edges
- var originalEdges = [];
- g.eachEdge(function(e, u, v, value) {
- var originalEdge = value.originalEdge;
- if (originalEdge) {
- originalEdges.push(originalEdge);
- }
- });
-
- // Expand collapsed nodes
- g.eachNode(function(u, value) {
- var originalNodes = value.originalNodes;
- if (originalNodes) {
- originalNodes.forEach(function(originalNode) {
- originalNode.value.rank = value.rank;
- g.addNode(originalNode.u, originalNode.value);
- g.parent(originalNode.u, originalNode.parent);
- });
- g.delNode(u);
- }
- });
-
- // Restore original edges
- originalEdges.forEach(function(edge) {
- g.addEdge(edge.e, edge.u, edge.v, edge.value);
- });
-};
-
-},{}],13:[function(require,module,exports){
-/* jshint -W079 */
-var Set = require('cp-data').Set,
-/* jshint +W079 */
- Digraph = require('graphlib').Digraph,
- util = require('../util');
-
-module.exports = feasibleTree;
-
-/*
- * Given an acyclic graph with each node assigned a `rank` attribute, this
- * function constructs and returns a spanning tree. This function may reduce
- * the length of some edges from the initial rank assignment while maintaining
- * the `minLen` specified by each edge.
- *
- * Prerequisites:
- *
- * * The input graph is acyclic
- * * Each node in the input graph has an assigned `rank` attribute
- * * Each edge in the input graph has an assigned `minLen` attribute
- *
- * Outputs:
- *
- * A feasible spanning tree for the input graph (i.e. a spanning tree that
- * respects each graph edge's `minLen` attribute) represented as a Digraph with
- * a `root` attribute on graph.
- *
- * Nodes have the same id and value as that in the input graph.
- *
- * Edges in the tree have arbitrarily assigned ids. The attributes for edges
- * include `reversed`. `reversed` indicates that the edge is a
- * back edge in the input graph.
- */
-function feasibleTree(g) {
- var remaining = new Set(g.nodes()),
- tree = new Digraph();
-
- if (remaining.size() === 1) {
- var root = g.nodes()[0];
- tree.addNode(root, {});
- tree.graph({ root: root });
- return tree;
- }
-
- function addTightEdges(v) {
- var continueToScan = true;
- g.predecessors(v).forEach(function(u) {
- if (remaining.has(u) && !slack(g, u, v)) {
- if (remaining.has(v)) {
- tree.addNode(v, {});
- remaining.remove(v);
- tree.graph({ root: v });
- }
-
- tree.addNode(u, {});
- tree.addEdge(null, u, v, { reversed: true });
- remaining.remove(u);
- addTightEdges(u);
- continueToScan = false;
- }
- });
-
- g.successors(v).forEach(function(w) {
- if (remaining.has(w) && !slack(g, v, w)) {
- if (remaining.has(v)) {
- tree.addNode(v, {});
- remaining.remove(v);
- tree.graph({ root: v });
- }
-
- tree.addNode(w, {});
- tree.addEdge(null, v, w, {});
- remaining.remove(w);
- addTightEdges(w);
- continueToScan = false;
- }
- });
- return continueToScan;
- }
-
- function createTightEdge() {
- var minSlack = Number.MAX_VALUE;
- remaining.keys().forEach(function(v) {
- g.predecessors(v).forEach(function(u) {
- if (!remaining.has(u)) {
- var edgeSlack = slack(g, u, v);
- if (Math.abs(edgeSlack) < Math.abs(minSlack)) {
- minSlack = -edgeSlack;
- }
- }
- });
-
- g.successors(v).forEach(function(w) {
- if (!remaining.has(w)) {
- var edgeSlack = slack(g, v, w);
- if (Math.abs(edgeSlack) < Math.abs(minSlack)) {
- minSlack = edgeSlack;
- }
- }
- });
- });
-
- tree.eachNode(function(u) { g.node(u).rank -= minSlack; });
- }
-
- while (remaining.size()) {
- var nodesToSearch = !tree.order() ? remaining.keys() : tree.nodes();
- for (var i = 0, il = nodesToSearch.length;
- i < il && addTightEdges(nodesToSearch[i]);
- ++i);
- if (remaining.size()) {
- createTightEdge();
- }
- }
-
- return tree;
-}
-
-function slack(g, u, v) {
- var rankDiff = g.node(v).rank - g.node(u).rank;
- var maxMinLen = util.max(g.outEdges(u, v)
- .map(function(e) { return g.edge(e).minLen; }));
- return rankDiff - maxMinLen;
-}
-
-},{"../util":17,"cp-data":19,"graphlib":24}],14:[function(require,module,exports){
-var util = require('../util'),
- topsort = require('graphlib').alg.topsort;
-
-module.exports = initRank;
-
-/*
- * Assigns a `rank` attribute to each node in the input graph and ensures that
- * this rank respects the `minLen` attribute of incident edges.
- *
- * Prerequisites:
- *
- * * The input graph must be acyclic
- * * Each edge in the input graph must have an assigned 'minLen' attribute
- */
-function initRank(g) {
- var sorted = topsort(g);
-
- sorted.forEach(function(u) {
- var inEdges = g.inEdges(u);
- if (inEdges.length === 0) {
- g.node(u).rank = 0;
- return;
- }
-
- var minLens = inEdges.map(function(e) {
- return g.node(g.source(e)).rank + g.edge(e).minLen;
- });
- g.node(u).rank = util.max(minLens);
- });
-}
-
-},{"../util":17,"graphlib":24}],15:[function(require,module,exports){
-module.exports = {
- slack: slack
-};
-
-/*
- * A helper to calculate the slack between two nodes (`u` and `v`) given a
- * `minLen` constraint. The slack represents how much the distance between `u`
- * and `v` could shrink while maintaining the `minLen` constraint. If the value
- * is negative then the constraint is currently violated.
- *
- This function requires that `u` and `v` are in `graph` and they both have a
- `rank` attribute.
- */
-function slack(graph, u, v, minLen) {
- return Math.abs(graph.node(u).rank - graph.node(v).rank) - minLen;
-}
-
-},{}],16:[function(require,module,exports){
-var util = require('../util'),
- rankUtil = require('./rankUtil');
-
-module.exports = simplex;
-
-function simplex(graph, spanningTree) {
- // The network simplex algorithm repeatedly replaces edges of
- // the spanning tree with negative cut values until no such
- // edge exists.
- initCutValues(graph, spanningTree);
- while (true) {
- var e = leaveEdge(spanningTree);
- if (e === null) break;
- var f = enterEdge(graph, spanningTree, e);
- exchange(graph, spanningTree, e, f);
- }
-}
-
-/*
- * Set the cut values of edges in the spanning tree by a depth-first
- * postorder traversal. The cut value corresponds to the cost, in
- * terms of a ranking's edge length sum, of lengthening an edge.
- * Negative cut values typically indicate edges that would yield a
- * smaller edge length sum if they were lengthened.
- */
-function initCutValues(graph, spanningTree) {
- computeLowLim(spanningTree);
-
- spanningTree.eachEdge(function(id, u, v, treeValue) {
- treeValue.cutValue = 0;
- });
-
- // Propagate cut values up the tree.
- function dfs(n) {
- var children = spanningTree.successors(n);
- for (var c in children) {
- var child = children[c];
- dfs(child);
- }
- if (n !== spanningTree.graph().root) {
- setCutValue(graph, spanningTree, n);
- }
- }
- dfs(spanningTree.graph().root);
-}
-
-/*
- * Perform a DFS postorder traversal, labeling each node v with
- * its traversal order 'lim(v)' and the minimum traversal number
- * of any of its descendants 'low(v)'. This provides an efficient
- * way to test whether u is an ancestor of v since
- * low(u) <= lim(v) <= lim(u) if and only if u is an ancestor.
- */
-function computeLowLim(tree) {
- var postOrderNum = 0;
-
- function dfs(n) {
- var children = tree.successors(n);
- var low = postOrderNum;
- for (var c in children) {
- var child = children[c];
- dfs(child);
- low = Math.min(low, tree.node(child).low);
- }
- tree.node(n).low = low;
- tree.node(n).lim = postOrderNum++;
- }
-
- dfs(tree.graph().root);
-}
-
-/*
- * To compute the cut value of the edge parent -> child, we consider
- * it and any other graph edges to or from the child.
- * parent
- * |
- * child
- * / \
- * u v
- */
-function setCutValue(graph, tree, child) {
- var parentEdge = tree.inEdges(child)[0];
-
- // List of child's children in the spanning tree.
- var grandchildren = [];
- var grandchildEdges = tree.outEdges(child);
- for (var gce in grandchildEdges) {
- grandchildren.push(tree.target(grandchildEdges[gce]));
- }
-
- var cutValue = 0;
-
- // TODO: Replace unit increment/decrement with edge weights.
- var E = 0; // Edges from child to grandchild's subtree.
- var F = 0; // Edges to child from grandchild's subtree.
- var G = 0; // Edges from child to nodes outside of child's subtree.
- var H = 0; // Edges from nodes outside of child's subtree to child.
-
- // Consider all graph edges from child.
- var outEdges = graph.outEdges(child);
- var gc;
- for (var oe in outEdges) {
- var succ = graph.target(outEdges[oe]);
- for (gc in grandchildren) {
- if (inSubtree(tree, succ, grandchildren[gc])) {
- E++;
- }
- }
- if (!inSubtree(tree, succ, child)) {
- G++;
- }
- }
-
- // Consider all graph edges to child.
- var inEdges = graph.inEdges(child);
- for (var ie in inEdges) {
- var pred = graph.source(inEdges[ie]);
- for (gc in grandchildren) {
- if (inSubtree(tree, pred, grandchildren[gc])) {
- F++;
- }
- }
- if (!inSubtree(tree, pred, child)) {
- H++;
- }
- }
-
- // Contributions depend on the alignment of the parent -> child edge
- // and the child -> u or v edges.
- var grandchildCutSum = 0;
- for (gc in grandchildren) {
- var cv = tree.edge(grandchildEdges[gc]).cutValue;
- if (!tree.edge(grandchildEdges[gc]).reversed) {
- grandchildCutSum += cv;
- } else {
- grandchildCutSum -= cv;
- }
- }
-
- if (!tree.edge(parentEdge).reversed) {
- cutValue += grandchildCutSum - E + F - G + H;
- } else {
- cutValue -= grandchildCutSum - E + F - G + H;
- }
-
- tree.edge(parentEdge).cutValue = cutValue;
-}
-
-/*
- * Return whether n is a node in the subtree with the given
- * root.
- */
-function inSubtree(tree, n, root) {
- return (tree.node(root).low <= tree.node(n).lim &&
- tree.node(n).lim <= tree.node(root).lim);
-}
-
-/*
- * Return an edge from the tree with a negative cut value, or null if there
- * is none.
- */
-function leaveEdge(tree) {
- var edges = tree.edges();
- for (var n in edges) {
- var e = edges[n];
- var treeValue = tree.edge(e);
- if (treeValue.cutValue < 0) {
- return e;
- }
- }
- return null;
-}
-
-/*
- * The edge e should be an edge in the tree, with an underlying edge
- * in the graph, with a negative cut value. Of the two nodes incident
- * on the edge, take the lower one. enterEdge returns an edge with
- * minimum slack going from outside of that node's subtree to inside
- * of that node's subtree.
- */
-function enterEdge(graph, tree, e) {
- var source = tree.source(e);
- var target = tree.target(e);
- var lower = tree.node(target).lim < tree.node(source).lim ? target : source;
-
- // Is the tree edge aligned with the graph edge?
- var aligned = !tree.edge(e).reversed;
-
- var minSlack = Number.POSITIVE_INFINITY;
- var minSlackEdge;
- if (aligned) {
- graph.eachEdge(function(id, u, v, value) {
- if (id !== e && inSubtree(tree, u, lower) && !inSubtree(tree, v, lower)) {
- var slack = rankUtil.slack(graph, u, v, value.minLen);
- if (slack < minSlack) {
- minSlack = slack;
- minSlackEdge = id;
- }
- }
- });
- } else {
- graph.eachEdge(function(id, u, v, value) {
- if (id !== e && !inSubtree(tree, u, lower) && inSubtree(tree, v, lower)) {
- var slack = rankUtil.slack(graph, u, v, value.minLen);
- if (slack < minSlack) {
- minSlack = slack;
- minSlackEdge = id;
- }
- }
- });
- }
-
- if (minSlackEdge === undefined) {
- var outside = [];
- var inside = [];
- graph.eachNode(function(id) {
- if (!inSubtree(tree, id, lower)) {
- outside.push(id);
- } else {
- inside.push(id);
- }
- });
- throw new Error('No edge found from outside of tree to inside');
- }
-
- return minSlackEdge;
-}
-
-/*
- * Replace edge e with edge f in the tree, recalculating the tree root,
- * the nodes' low and lim properties and the edges' cut values.
- */
-function exchange(graph, tree, e, f) {
- tree.delEdge(e);
- var source = graph.source(f);
- var target = graph.target(f);
-
- // Redirect edges so that target is the root of its subtree.
- function redirect(v) {
- var edges = tree.inEdges(v);
- for (var i in edges) {
- var e = edges[i];
- var u = tree.source(e);
- var value = tree.edge(e);
- redirect(u);
- tree.delEdge(e);
- value.reversed = !value.reversed;
- tree.addEdge(e, v, u, value);
- }
- }
-
- redirect(target);
-
- var root = source;
- var edges = tree.inEdges(root);
- while (edges.length > 0) {
- root = tree.source(edges[0]);
- edges = tree.inEdges(root);
- }
-
- tree.graph().root = root;
-
- tree.addEdge(null, source, target, {cutValue: 0});
-
- initCutValues(graph, tree);
-
- adjustRanks(graph, tree);
-}
-
-/*
- * Reset the ranks of all nodes based on the current spanning tree.
- * The rank of the tree's root remains unchanged, while all other
- * nodes are set to the sum of minimum length constraints along
- * the path from the root.
- */
-function adjustRanks(graph, tree) {
- function dfs(p) {
- var children = tree.successors(p);
- children.forEach(function(c) {
- var minLen = minimumLength(graph, p, c);
- graph.node(c).rank = graph.node(p).rank + minLen;
- dfs(c);
- });
- }
-
- dfs(tree.graph().root);
-}
-
-/*
- * If u and v are connected by some edges in the graph, return the
- * minimum length of those edges, as a positive number if v succeeds
- * u and as a negative number if v precedes u.
- */
-function minimumLength(graph, u, v) {
- var outEdges = graph.outEdges(u, v);
- if (outEdges.length > 0) {
- return util.max(outEdges.map(function(e) {
- return graph.edge(e).minLen;
- }));
- }
-
- var inEdges = graph.inEdges(u, v);
- if (inEdges.length > 0) {
- return -util.max(inEdges.map(function(e) {
- return graph.edge(e).minLen;
- }));
- }
-}
-
-},{"../util":17,"./rankUtil":15}],17:[function(require,module,exports){
-/*
- * Returns the smallest value in the array.
- */
-exports.min = function(values) {
- return Math.min.apply(Math, values);
-};
-
-/*
- * Returns the largest value in the array.
- */
-exports.max = function(values) {
- return Math.max.apply(Math, values);
-};
-
-/*
- * Returns `true` only if `f(x)` is `true` for all `x` in `xs`. Otherwise
- * returns `false`. This function will return immediately if it finds a
- * case where `f(x)` does not hold.
- */
-exports.all = function(xs, f) {
- for (var i = 0; i < xs.length; ++i) {
- if (!f(xs[i])) {
- return false;
- }
- }
- return true;
-};
-
-/*
- * Accumulates the sum of elements in the given array using the `+` operator.
- */
-exports.sum = function(values) {
- return values.reduce(function(acc, x) { return acc + x; }, 0);
-};
-
-/*
- * Returns an array of all values in the given object.
- */
-exports.values = function(obj) {
- return Object.keys(obj).map(function(k) { return obj[k]; });
-};
-
-exports.shuffle = function(array) {
- for (i = array.length - 1; i > 0; --i) {
- var j = Math.floor(Math.random() * (i + 1));
- var aj = array[j];
- array[j] = array[i];
- array[i] = aj;
- }
-};
-
-exports.propertyAccessor = function(self, config, field, setHook) {
- return function(x) {
- if (!arguments.length) return config[field];
- config[field] = x;
- if (setHook) setHook(x);
- return self;
- };
-};
-
-/*
- * Given a layered, directed graph with `rank` and `order` node attributes,
- * this function returns an array of ordered ranks. Each rank contains an array
- * of the ids of the nodes in that rank in the order specified by the `order`
- * attribute.
- */
-exports.ordering = function(g) {
- var ordering = [];
- g.eachNode(function(u, value) {
- var rank = ordering[value.rank] || (ordering[value.rank] = []);
- rank[value.order] = u;
- });
- return ordering;
-};
-
-/*
- * A filter that can be used with `filterNodes` to get a graph that only
- * includes nodes that do not contain others nodes.
- */
-exports.filterNonSubgraphs = function(g) {
- return function(u) {
- return g.children(u).length === 0;
- };
-};
-
-/*
- * Returns a new function that wraps `func` with a timer. The wrapper logs the
- * time it takes to execute the function.
- *
- * The timer will be enabled provided `log.level >= 1`.
- */
-function time(name, func) {
- return function() {
- var start = new Date().getTime();
- try {
- return func.apply(null, arguments);
- } finally {
- log(1, name + ' time: ' + (new Date().getTime() - start) + 'ms');
- }
- };
-}
-time.enabled = false;
-
-exports.time = time;
-
-/*
- * A global logger with the specification `log(level, message, ...)` that
- * will log a message to the console if `log.level >= level`.
- */
-function log(level) {
- if (log.level >= level) {
- console.log.apply(console, Array.prototype.slice.call(arguments, 1));
- }
-}
-log.level = 0;
-
-exports.log = log;
-
-},{}],18:[function(require,module,exports){
-module.exports = '0.4.5';
-
-},{}],19:[function(require,module,exports){
-exports.Set = require('./lib/Set');
-exports.PriorityQueue = require('./lib/PriorityQueue');
-exports.version = require('./lib/version');
-
-},{"./lib/PriorityQueue":20,"./lib/Set":21,"./lib/version":23}],20:[function(require,module,exports){
-module.exports = PriorityQueue;
-
-/**
- * A min-priority queue data structure. This algorithm is derived from Cormen,
- * et al., "Introduction to Algorithms". The basic idea of a min-priority
- * queue is that you can efficiently (in O(1) time) get the smallest key in
- * the queue. Adding and removing elements takes O(log n) time. A key can
- * have its priority decreased in O(log n) time.
- */
-function PriorityQueue() {
- this._arr = [];
- this._keyIndices = {};
-}
-
-/**
- * Returns the number of elements in the queue. Takes `O(1)` time.
- */
-PriorityQueue.prototype.size = function() {
- return this._arr.length;
-};
-
-/**
- * Returns the keys that are in the queue. Takes `O(n)` time.
- */
-PriorityQueue.prototype.keys = function() {
- return this._arr.map(function(x) { return x.key; });
-};
-
-/**
- * Returns `true` if **key** is in the queue and `false` if not.
- */
-PriorityQueue.prototype.has = function(key) {
- return key in this._keyIndices;
-};
-
-/**
- * Returns the priority for **key**. If **key** is not present in the queue
- * then this function returns `undefined`. Takes `O(1)` time.
- *
- * @param {Object} key
- */
-PriorityQueue.prototype.priority = function(key) {
- var index = this._keyIndices[key];
- if (index !== undefined) {
- return this._arr[index].priority;
- }
-};
-
-/**
- * Returns the key for the minimum element in this queue. If the queue is
- * empty this function throws an Error. Takes `O(1)` time.
- */
-PriorityQueue.prototype.min = function() {
- if (this.size() === 0) {
- throw new Error("Queue underflow");
- }
- return this._arr[0].key;
-};
-
-/**
- * Inserts a new key into the priority queue. If the key already exists in
- * the queue this function returns `false`; otherwise it will return `true`.
- * Takes `O(n)` time.
- *
- * @param {Object} key the key to add
- * @param {Number} priority the initial priority for the key
- */
-PriorityQueue.prototype.add = function(key, priority) {
- var keyIndices = this._keyIndices;
- if (!(key in keyIndices)) {
- var arr = this._arr;
- var index = arr.length;
- keyIndices[key] = index;
- arr.push({key: key, priority: priority});
- this._decrease(index);
- return true;
- }
- return false;
-};
-
-/**
- * Removes and returns the smallest key in the queue. Takes `O(log n)` time.
- */
-PriorityQueue.prototype.removeMin = function() {
- this._swap(0, this._arr.length - 1);
- var min = this._arr.pop();
- delete this._keyIndices[min.key];
- this._heapify(0);
- return min.key;
-};
-
-/**
- * Decreases the priority for **key** to **priority**. If the new priority is
- * greater than the previous priority, this function will throw an Error.
- *
- * @param {Object} key the key for which to raise priority
- * @param {Number} priority the new priority for the key
- */
-PriorityQueue.prototype.decrease = function(key, priority) {
- var index = this._keyIndices[key];
- if (priority > this._arr[index].priority) {
- throw new Error("New priority is greater than current priority. " +
- "Key: " + key + " Old: " + this._arr[index].priority + " New: " + priority);
- }
- this._arr[index].priority = priority;
- this._decrease(index);
-};
-
-PriorityQueue.prototype._heapify = function(i) {
- var arr = this._arr;
- var l = 2 * i,
- r = l + 1,
- largest = i;
- if (l < arr.length) {
- largest = arr[l].priority < arr[largest].priority ? l : largest;
- if (r < arr.length) {
- largest = arr[r].priority < arr[largest].priority ? r : largest;
- }
- if (largest !== i) {
- this._swap(i, largest);
- this._heapify(largest);
- }
- }
-};
-
-PriorityQueue.prototype._decrease = function(index) {
- var arr = this._arr;
- var priority = arr[index].priority;
- var parent;
- while (index !== 0) {
- parent = index >> 1;
- if (arr[parent].priority < priority) {
- break;
- }
- this._swap(index, parent);
- index = parent;
- }
-};
-
-PriorityQueue.prototype._swap = function(i, j) {
- var arr = this._arr;
- var keyIndices = this._keyIndices;
- var origArrI = arr[i];
- var origArrJ = arr[j];
- arr[i] = origArrJ;
- arr[j] = origArrI;
- keyIndices[origArrJ.key] = i;
- keyIndices[origArrI.key] = j;
-};
-
-},{}],21:[function(require,module,exports){
-var util = require('./util');
-
-module.exports = Set;
-
-/**
- * Constructs a new Set with an optional set of `initialKeys`.
- *
- * It is important to note that keys are coerced to String for most purposes
- * with this object, similar to the behavior of JavaScript's Object. For
- * example, the following will add only one key:
- *
- * var s = new Set();
- * s.add(1);
- * s.add("1");
- *
- * However, the type of the key is preserved internally so that `keys` returns
- * the original key set uncoerced. For the above example, `keys` would return
- * `[1]`.
- */
-function Set(initialKeys) {
- this._size = 0;
- this._keys = {};
-
- if (initialKeys) {
- for (var i = 0, il = initialKeys.length; i < il; ++i) {
- this.add(initialKeys[i]);
- }
- }
-}
-
-/**
- * Returns a new Set that represents the set intersection of the array of given
- * sets.
- */
-Set.intersect = function(sets) {
- if (sets.length === 0) {
- return new Set();
- }
-
- var result = new Set(!util.isArray(sets[0]) ? sets[0].keys() : sets[0]);
- for (var i = 1, il = sets.length; i < il; ++i) {
- var resultKeys = result.keys(),
- other = !util.isArray(sets[i]) ? sets[i] : new Set(sets[i]);
- for (var j = 0, jl = resultKeys.length; j < jl; ++j) {
- var key = resultKeys[j];
- if (!other.has(key)) {
- result.remove(key);
- }
- }
- }
-
- return result;
-};
-
-/**
- * Returns a new Set that represents the set union of the array of given sets.
- */
-Set.union = function(sets) {
- var totalElems = util.reduce(sets, function(lhs, rhs) {
- return lhs + (rhs.size ? rhs.size() : rhs.length);
- }, 0);
- var arr = new Array(totalElems);
-
- var k = 0;
- for (var i = 0, il = sets.length; i < il; ++i) {
- var cur = sets[i],
- keys = !util.isArray(cur) ? cur.keys() : cur;
- for (var j = 0, jl = keys.length; j < jl; ++j) {
- arr[k++] = keys[j];
- }
- }
-
- return new Set(arr);
-};
-
-/**
- * Returns the size of this set in `O(1)` time.
- */
-Set.prototype.size = function() {
- return this._size;
-};
-
-/**
- * Returns the keys in this set. Takes `O(n)` time.
- */
-Set.prototype.keys = function() {
- return values(this._keys);
-};
-
-/**
- * Tests if a key is present in this Set. Returns `true` if it is and `false`
- * if not. Takes `O(1)` time.
- */
-Set.prototype.has = function(key) {
- return key in this._keys;
-};
-
-/**
- * Adds a new key to this Set if it is not already present. Returns `true` if
- * the key was added and `false` if it was already present. Takes `O(1)` time.
- */
-Set.prototype.add = function(key) {
- if (!(key in this._keys)) {
- this._keys[key] = key;
- ++this._size;
- return true;
- }
- return false;
-};
-
-/**
- * Removes a key from this Set. If the key was removed this function returns
- * `true`. If not, it returns `false`. Takes `O(1)` time.
- */
-Set.prototype.remove = function(key) {
- if (key in this._keys) {
- delete this._keys[key];
- --this._size;
- return true;
- }
- return false;
-};
-
-/*
- * Returns an array of all values for properties of **o**.
- */
-function values(o) {
- var ks = Object.keys(o),
- len = ks.length,
- result = new Array(len),
- i;
- for (i = 0; i < len; ++i) {
- result[i] = o[ks[i]];
- }
- return result;
-}
-
-},{"./util":22}],22:[function(require,module,exports){
-/*
- * This polyfill comes from
- * https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/isArray
- */
-if(!Array.isArray) {
- exports.isArray = function (vArg) {
- return Object.prototype.toString.call(vArg) === '[object Array]';
- };
-} else {
- exports.isArray = Array.isArray;
-}
-
-/*
- * Slightly adapted polyfill from
- * https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/Reduce
- */
-if ('function' !== typeof Array.prototype.reduce) {
- exports.reduce = function(array, callback, opt_initialValue) {
- 'use strict';
- if (null === array || 'undefined' === typeof array) {
- // At the moment all modern browsers, that support strict mode, have
- // native implementation of Array.prototype.reduce. For instance, IE8
- // does not support strict mode, so this check is actually useless.
- throw new TypeError(
- 'Array.prototype.reduce called on null or undefined');
- }
- if ('function' !== typeof callback) {
- throw new TypeError(callback + ' is not a function');
- }
- var index, value,
- length = array.length >>> 0,
- isValueSet = false;
- if (1 < arguments.length) {
- value = opt_initialValue;
- isValueSet = true;
- }
- for (index = 0; length > index; ++index) {
- if (array.hasOwnProperty(index)) {
- if (isValueSet) {
- value = callback(value, array[index], index, array);
- }
- else {
- value = array[index];
- isValueSet = true;
- }
- }
- }
- if (!isValueSet) {
- throw new TypeError('Reduce of empty array with no initial value');
- }
- return value;
- };
-} else {
- exports.reduce = function(array, callback, opt_initialValue) {
- return array.reduce(callback, opt_initialValue);
- };
-}
-
-},{}],23:[function(require,module,exports){
-module.exports = '1.1.3';
-
-},{}],24:[function(require,module,exports){
-exports.Graph = require("./lib/Graph");
-exports.Digraph = require("./lib/Digraph");
-exports.CGraph = require("./lib/CGraph");
-exports.CDigraph = require("./lib/CDigraph");
-require("./lib/graph-converters");
-
-exports.alg = {
- isAcyclic: require("./lib/alg/isAcyclic"),
- components: require("./lib/alg/components"),
- dijkstra: require("./lib/alg/dijkstra"),
- dijkstraAll: require("./lib/alg/dijkstraAll"),
- findCycles: require("./lib/alg/findCycles"),
- floydWarshall: require("./lib/alg/floydWarshall"),
- postorder: require("./lib/alg/postorder"),
- preorder: require("./lib/alg/preorder"),
- prim: require("./lib/alg/prim"),
- tarjan: require("./lib/alg/tarjan"),
- topsort: require("./lib/alg/topsort")
-};
-
-exports.converter = {
- json: require("./lib/converter/json.js")
-};
-
-var filter = require("./lib/filter");
-exports.filter = {
- all: filter.all,
- nodesFromList: filter.nodesFromList
-};
-
-exports.version = require("./lib/version");
-
-},{"./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){
-/* jshint -W079 */
-var Set = require("cp-data").Set;
-/* jshint +W079 */
-
-module.exports = BaseGraph;
-
-function BaseGraph() {
- // The value assigned to the graph itself.
- this._value = undefined;
-
- // Map of node id -> { id, value }
- this._nodes = {};
-
- // Map of edge id -> { id, u, v, value }
- this._edges = {};
-
- // Used to generate a unique id in the graph
- this._nextId = 0;
-}
-
-// Number of nodes
-BaseGraph.prototype.order = function() {
- return Object.keys(this._nodes).length;
-};
-
-// Number of edges
-BaseGraph.prototype.size = function() {
- return Object.keys(this._edges).length;
-};
-
-// Accessor for graph level value
-BaseGraph.prototype.graph = function(value) {
- if (arguments.length === 0) {
- return this._value;
- }
- this._value = value;
-};
-
-BaseGraph.prototype.hasNode = function(u) {
- return u in this._nodes;
-};
-
-BaseGraph.prototype.node = function(u, value) {
- var node = this._strictGetNode(u);
- if (arguments.length === 1) {
- return node.value;
- }
- node.value = value;
-};
-
-BaseGraph.prototype.nodes = function() {
- var nodes = [];
- this.eachNode(function(id) { nodes.push(id); });
- return nodes;
-};
-
-BaseGraph.prototype.eachNode = function(func) {
- for (var k in this._nodes) {
- var node = this._nodes[k];
- func(node.id, node.value);
- }
-};
-
-BaseGraph.prototype.hasEdge = function(e) {
- return e in this._edges;
-};
-
-BaseGraph.prototype.edge = function(e, value) {
- var edge = this._strictGetEdge(e);
- if (arguments.length === 1) {
- return edge.value;
- }
- edge.value = value;
-};
-
-BaseGraph.prototype.edges = function() {
- var es = [];
- this.eachEdge(function(id) { es.push(id); });
- return es;
-};
-
-BaseGraph.prototype.eachEdge = function(func) {
- for (var k in this._edges) {
- var edge = this._edges[k];
- func(edge.id, edge.u, edge.v, edge.value);
- }
-};
-
-BaseGraph.prototype.incidentNodes = function(e) {
- var edge = this._strictGetEdge(e);
- return [edge.u, edge.v];
-};
-
-BaseGraph.prototype.addNode = function(u, value) {
- if (u === undefined || u === null) {
- do {
- u = "_" + (++this._nextId);
- } while (this.hasNode(u));
- } else if (this.hasNode(u)) {
- throw new Error("Graph already has node '" + u + "'");
- }
- this._nodes[u] = { id: u, value: value };
- return u;
-};
-
-BaseGraph.prototype.delNode = function(u) {
- this._strictGetNode(u);
- this.incidentEdges(u).forEach(function(e) { this.delEdge(e); }, this);
- delete this._nodes[u];
-};
-
-// inMap and outMap are opposite sides of an incidence map. For example, for
-// Graph these would both come from the _incidentEdges map, while for Digraph
-// they would come from _inEdges and _outEdges.
-BaseGraph.prototype._addEdge = function(e, u, v, value, inMap, outMap) {
- this._strictGetNode(u);
- this._strictGetNode(v);
-
- if (e === undefined || e === null) {
- do {
- e = "_" + (++this._nextId);
- } while (this.hasEdge(e));
- }
- else if (this.hasEdge(e)) {
- throw new Error("Graph already has edge '" + e + "'");
- }
-
- this._edges[e] = { id: e, u: u, v: v, value: value };
- addEdgeToMap(inMap[v], u, e);
- addEdgeToMap(outMap[u], v, e);
-
- return e;
-};
-
-// See note for _addEdge regarding inMap and outMap.
-BaseGraph.prototype._delEdge = function(e, inMap, outMap) {
- var edge = this._strictGetEdge(e);
- delEdgeFromMap(inMap[edge.v], edge.u, e);
- delEdgeFromMap(outMap[edge.u], edge.v, e);
- delete this._edges[e];
-};
-
-BaseGraph.prototype.copy = function() {
- var copy = new this.constructor();
- copy.graph(this.graph());
- this.eachNode(function(u, value) { copy.addNode(u, value); });
- this.eachEdge(function(e, u, v, value) { copy.addEdge(e, u, v, value); });
- copy._nextId = this._nextId;
- return copy;
-};
-
-BaseGraph.prototype.filterNodes = function(filter) {
- var copy = new this.constructor();
- copy.graph(this.graph());
- this.eachNode(function(u, value) {
- if (filter(u)) {
- copy.addNode(u, value);
- }
- });
- this.eachEdge(function(e, u, v, value) {
- if (copy.hasNode(u) && copy.hasNode(v)) {
- copy.addEdge(e, u, v, value);
- }
- });
- return copy;
-};
-
-BaseGraph.prototype._strictGetNode = function(u) {
- var node = this._nodes[u];
- if (node === undefined) {
- throw new Error("Node '" + u + "' is not in graph");
- }
- return node;
-};
-
-BaseGraph.prototype._strictGetEdge = function(e) {
- var edge = this._edges[e];
- if (edge === undefined) {
- throw new Error("Edge '" + e + "' is not in graph");
- }
- return edge;
-};
-
-function addEdgeToMap(map, v, e) {
- (map[v] || (map[v] = new Set())).add(e);
-}
-
-function delEdgeFromMap(map, v, e) {
- var vEntry = map[v];
- vEntry.remove(e);
- if (vEntry.size() === 0) {
- delete map[v];
- }
-}
-
-
-},{"cp-data":19}],26:[function(require,module,exports){
-var Digraph = require("./Digraph"),
- compoundify = require("./compoundify");
-
-var CDigraph = compoundify(Digraph);
-
-module.exports = CDigraph;
-
-CDigraph.fromDigraph = function(src) {
- var g = new CDigraph(),
- graphValue = src.graph();
-
- if (graphValue !== undefined) {
- g.graph(graphValue);
- }
-
- src.eachNode(function(u, value) {
- if (value === undefined) {
- g.addNode(u);
- } else {
- g.addNode(u, value);
- }
- });
- src.eachEdge(function(e, u, v, value) {
- if (value === undefined) {
- g.addEdge(null, u, v);
- } else {
- g.addEdge(null, u, v, value);
- }
- });
- return g;
-};
-
-CDigraph.prototype.toString = function() {
- return "CDigraph " + JSON.stringify(this, null, 2);
-};
-
-},{"./Digraph":28,"./compoundify":41}],27:[function(require,module,exports){
-var Graph = require("./Graph"),
- compoundify = require("./compoundify");
-
-var CGraph = compoundify(Graph);
-
-module.exports = CGraph;
-
-CGraph.fromGraph = function(src) {
- var g = new CGraph(),
- graphValue = src.graph();
-
- if (graphValue !== undefined) {
- g.graph(graphValue);
- }
-
- src.eachNode(function(u, value) {
- if (value === undefined) {
- g.addNode(u);
- } else {
- g.addNode(u, value);
- }
- });
- src.eachEdge(function(e, u, v, value) {
- if (value === undefined) {
- g.addEdge(null, u, v);
- } else {
- g.addEdge(null, u, v, value);
- }
- });
- return g;
-};
-
-CGraph.prototype.toString = function() {
- return "CGraph " + JSON.stringify(this, null, 2);
-};
-
-},{"./Graph":29,"./compoundify":41}],28:[function(require,module,exports){
-/*
- * This file is organized with in the following order:
- *
- * Exports
- * Graph constructors
- * Graph queries (e.g. nodes(), edges()
- * Graph mutators
- * Helper functions
- */
-
-var util = require("./util"),
- BaseGraph = require("./BaseGraph"),
-/* jshint -W079 */
- Set = require("cp-data").Set;
-/* jshint +W079 */
-
-module.exports = Digraph;
-
-/*
- * Constructor to create a new directed multi-graph.
- */
-function Digraph() {
- BaseGraph.call(this);
-
- /*! Map of sourceId -> {targetId -> Set of edge ids} */
- this._inEdges = {};
-
- /*! Map of targetId -> {sourceId -> Set of edge ids} */
- this._outEdges = {};
-}
-
-Digraph.prototype = new BaseGraph();
-Digraph.prototype.constructor = Digraph;
-
-/*
- * Always returns `true`.
- */
-Digraph.prototype.isDirected = function() {
- return true;
-};
-
-/*
- * Returns all successors of the node with the id `u`. That is, all nodes
- * that have the node `u` as their source are returned.
- *
- * If no node `u` exists in the graph this function throws an Error.
- *
- * @param {String} u a node id
- */
-Digraph.prototype.successors = function(u) {
- this._strictGetNode(u);
- return Object.keys(this._outEdges[u])
- .map(function(v) { return this._nodes[v].id; }, this);
-};
-
-/*
- * Returns all predecessors of the node with the id `u`. That is, all nodes
- * that have the node `u` as their target are returned.
- *
- * If no node `u` exists in the graph this function throws an Error.
- *
- * @param {String} u a node id
- */
-Digraph.prototype.predecessors = function(u) {
- this._strictGetNode(u);
- return Object.keys(this._inEdges[u])
- .map(function(v) { return this._nodes[v].id; }, this);
-};
-
-/*
- * Returns all nodes that are adjacent to the node with the id `u`. In other
- * words, this function returns the set of all successors and predecessors of
- * node `u`.
- *
- * @param {String} u a node id
- */
-Digraph.prototype.neighbors = function(u) {
- return Set.union([this.successors(u), this.predecessors(u)]).keys();
-};
-
-/*
- * Returns all nodes in the graph that have no in-edges.
- */
-Digraph.prototype.sources = function() {
- var self = this;
- return this._filterNodes(function(u) {
- // This could have better space characteristics if we had an inDegree function.
- return self.inEdges(u).length === 0;
- });
-};
-
-/*
- * Returns all nodes in the graph that have no out-edges.
- */
-Digraph.prototype.sinks = function() {
- var self = this;
- return this._filterNodes(function(u) {
- // This could have better space characteristics if we have an outDegree function.
- return self.outEdges(u).length === 0;
- });
-};
-
-/*
- * Returns the source node incident on the edge identified by the id `e`. If no
- * such edge exists in the graph this function throws an Error.
- *
- * @param {String} e an edge id
- */
-Digraph.prototype.source = function(e) {
- return this._strictGetEdge(e).u;
-};
-
-/*
- * Returns the target node incident on the edge identified by the id `e`. If no
- * such edge exists in the graph this function throws an Error.
- *
- * @param {String} e an edge id
- */
-Digraph.prototype.target = function(e) {
- return this._strictGetEdge(e).v;
-};
-
-/*
- * Returns an array of ids for all edges in the graph that have the node
- * `target` as their target. If the node `target` is not in the graph this
- * function raises an Error.
- *
- * Optionally a `source` node can also be specified. This causes the results
- * to be filtered such that only edges from `source` to `target` are included.
- * If the node `source` is specified but is not in the graph then this function
- * raises an Error.
- *
- * @param {String} target the target node id
- * @param {String} [source] an optional source node id
- */
-Digraph.prototype.inEdges = function(target, source) {
- this._strictGetNode(target);
- var results = Set.union(util.values(this._inEdges[target])).keys();
- if (arguments.length > 1) {
- this._strictGetNode(source);
- results = results.filter(function(e) { return this.source(e) === source; }, this);
- }
- return results;
-};
-
-/*
- * Returns an array of ids for all edges in the graph that have the node
- * `source` as their source. If the node `source` is not in the graph this
- * function raises an Error.
- *
- * Optionally a `target` node may also be specified. This causes the results
- * to be filtered such that only edges from `source` to `target` are included.
- * If the node `target` is specified but is not in the graph then this function
- * raises an Error.
- *
- * @param {String} source the source node id
- * @param {String} [target] an optional target node id
- */
-Digraph.prototype.outEdges = function(source, target) {
- this._strictGetNode(source);
- var results = Set.union(util.values(this._outEdges[source])).keys();
- if (arguments.length > 1) {
- this._strictGetNode(target);
- results = results.filter(function(e) { return this.target(e) === target; }, this);
- }
- return results;
-};
-
-/*
- * Returns an array of ids for all edges in the graph that have the `u` as
- * their source or their target. If the node `u` is not in the graph this
- * function raises an Error.
- *
- * Optionally a `v` node may also be specified. This causes the results to be
- * filtered such that only edges between `u` and `v` - in either direction -
- * are included. IF the node `v` is specified but not in the graph then this
- * function raises an Error.
- *
- * @param {String} u the node for which to find incident edges
- * @param {String} [v] option node that must be adjacent to `u`
- */
-Digraph.prototype.incidentEdges = function(u, v) {
- if (arguments.length > 1) {
- return Set.union([this.outEdges(u, v), this.outEdges(v, u)]).keys();
- } else {
- return Set.union([this.inEdges(u), this.outEdges(u)]).keys();
- }
-};
-
-/*
- * Returns a string representation of this graph.
- */
-Digraph.prototype.toString = function() {
- return "Digraph " + JSON.stringify(this, null, 2);
-};
-
-/*
- * Adds a new node with the id `u` to the graph and assigns it the value
- * `value`. If a node with the id is already a part of the graph this function
- * throws an Error.
- *
- * @param {String} u a node id
- * @param {Object} [value] an optional value to attach to the node
- */
-Digraph.prototype.addNode = function(u, value) {
- u = BaseGraph.prototype.addNode.call(this, u, value);
- this._inEdges[u] = {};
- this._outEdges[u] = {};
- return u;
-};
-
-/*
- * Removes a node from the graph that has the id `u`. Any edges incident on the
- * node are also removed. If the graph does not contain a node with the id this
- * function will throw an Error.
- *
- * @param {String} u a node id
- */
-Digraph.prototype.delNode = function(u) {
- BaseGraph.prototype.delNode.call(this, u);
- delete this._inEdges[u];
- delete this._outEdges[u];
-};
-
-/*
- * Adds a new edge to the graph with the id `e` from a node with the id `source`
- * to a node with an id `target` and assigns it the value `value`. This graph
- * allows more than one edge from `source` to `target` as long as the id `e`
- * is unique in the set of edges. If `e` is `null` the graph will assign a
- * unique identifier to the edge.
- *
- * If `source` or `target` are not present in the graph this function will
- * throw an Error.
- *
- * @param {String} [e] an edge id
- * @param {String} source the source node id
- * @param {String} target the target node id
- * @param {Object} [value] an optional value to attach to the edge
- */
-Digraph.prototype.addEdge = function(e, source, target, value) {
- return BaseGraph.prototype._addEdge.call(this, e, source, target, value,
- this._inEdges, this._outEdges);
-};
-
-/*
- * Removes an edge in the graph with the id `e`. If no edge in the graph has
- * the id `e` this function will throw an Error.
- *
- * @param {String} e an edge id
- */
-Digraph.prototype.delEdge = function(e) {
- BaseGraph.prototype._delEdge.call(this, e, this._inEdges, this._outEdges);
-};
-
-// Unlike BaseGraph.filterNodes, this helper just returns nodes that
-// satisfy a predicate.
-Digraph.prototype._filterNodes = function(pred) {
- var filtered = [];
- this.eachNode(function(u) {
- if (pred(u)) {
- filtered.push(u);
- }
- });
- return filtered;
-};
-
-
-},{"./BaseGraph":25,"./util":45,"cp-data":19}],29:[function(require,module,exports){
-/*
- * This file is organized with in the following order:
- *
- * Exports
- * Graph constructors
- * Graph queries (e.g. nodes(), edges()
- * Graph mutators
- * Helper functions
- */
-
-var util = require("./util"),
- BaseGraph = require("./BaseGraph"),
-/* jshint -W079 */
- Set = require("cp-data").Set;
-/* jshint +W079 */
-
-module.exports = Graph;
-
-/*
- * Constructor to create a new undirected multi-graph.
- */
-function Graph() {
- BaseGraph.call(this);
-
- /*! Map of nodeId -> { otherNodeId -> Set of edge ids } */
- this._incidentEdges = {};
-}
-
-Graph.prototype = new BaseGraph();
-Graph.prototype.constructor = Graph;
-
-/*
- * Always returns `false`.
- */
-Graph.prototype.isDirected = function() {
- return false;
-};
-
-/*
- * Returns all nodes that are adjacent to the node with the id `u`.
- *
- * @param {String} u a node id
- */
-Graph.prototype.neighbors = function(u) {
- this._strictGetNode(u);
- return Object.keys(this._incidentEdges[u])
- .map(function(v) { return this._nodes[v].id; }, this);
-};
-
-/*
- * Returns an array of ids for all edges in the graph that are incident on `u`.
- * If the node `u` is not in the graph this function raises an Error.
- *
- * Optionally a `v` node may also be specified. This causes the results to be
- * filtered such that only edges between `u` and `v` are included. If the node
- * `v` is specified but not in the graph then this function raises an Error.
- *
- * @param {String} u the node for which to find incident edges
- * @param {String} [v] option node that must be adjacent to `u`
- */
-Graph.prototype.incidentEdges = function(u, v) {
- this._strictGetNode(u);
- if (arguments.length > 1) {
- this._strictGetNode(v);
- return v in this._incidentEdges[u] ? this._incidentEdges[u][v].keys() : [];
- } else {
- return Set.union(util.values(this._incidentEdges[u])).keys();
- }
-};
-
-/*
- * Returns a string representation of this graph.
- */
-Graph.prototype.toString = function() {
- return "Graph " + JSON.stringify(this, null, 2);
-};
-
-/*
- * Adds a new node with the id `u` to the graph and assigns it the value
- * `value`. If a node with the id is already a part of the graph this function
- * throws an Error.
- *
- * @param {String} u a node id
- * @param {Object} [value] an optional value to attach to the node
- */
-Graph.prototype.addNode = function(u, value) {
- u = BaseGraph.prototype.addNode.call(this, u, value);
- this._incidentEdges[u] = {};
- return u;
-};
-
-/*
- * Removes a node from the graph that has the id `u`. Any edges incident on the
- * node are also removed. If the graph does not contain a node with the id this
- * function will throw an Error.
- *
- * @param {String} u a node id
- */
-Graph.prototype.delNode = function(u) {
- BaseGraph.prototype.delNode.call(this, u);
- delete this._incidentEdges[u];
-};
-
-/*
- * Adds a new edge to the graph with the id `e` between a node with the id `u`
- * and a node with an id `v` and assigns it the value `value`. This graph
- * allows more than one edge between `u` and `v` as long as the id `e`
- * is unique in the set of edges. If `e` is `null` the graph will assign a
- * unique identifier to the edge.
- *
- * If `u` or `v` are not present in the graph this function will throw an
- * Error.
- *
- * @param {String} [e] an edge id
- * @param {String} u the node id of one of the adjacent nodes
- * @param {String} v the node id of the other adjacent node
- * @param {Object} [value] an optional value to attach to the edge
- */
-Graph.prototype.addEdge = function(e, u, v, value) {
- return BaseGraph.prototype._addEdge.call(this, e, u, v, value,
- this._incidentEdges, this._incidentEdges);
-};
-
-/*
- * Removes an edge in the graph with the id `e`. If no edge in the graph has
- * the id `e` this function will throw an Error.
- *
- * @param {String} e an edge id
- */
-Graph.prototype.delEdge = function(e) {
- BaseGraph.prototype._delEdge.call(this, e, this._incidentEdges, this._incidentEdges);
-};
-
-
-},{"./BaseGraph":25,"./util":45,"cp-data":19}],30:[function(require,module,exports){
-/* jshint -W079 */
-var Set = require("cp-data").Set;
-/* jshint +W079 */
-
-module.exports = components;
-
-/**
- * Finds all [connected components][] in a graph and returns an array of these
- * components. Each component is itself an array that contains the ids of nodes
- * in the component.
- *
- * This function only works with undirected Graphs.
- *
- * [connected components]: http://en.wikipedia.org/wiki/Connected_component_(graph_theory)
- *
- * @param {Graph} g the graph to search for components
- */
-function components(g) {
- var results = [];
- var visited = new Set();
-
- function dfs(v, component) {
- if (!visited.has(v)) {
- visited.add(v);
- component.push(v);
- g.neighbors(v).forEach(function(w) {
- dfs(w, component);
- });
- }
- }
-
- g.nodes().forEach(function(v) {
- var component = [];
- dfs(v, component);
- if (component.length > 0) {
- results.push(component);
- }
- });
-
- return results;
-}
-
-},{"cp-data":19}],31:[function(require,module,exports){
-var PriorityQueue = require("cp-data").PriorityQueue;
-
-module.exports = dijkstra;
-
-/**
- * This function is an implementation of [Dijkstra's algorithm][] which finds
- * the shortest path from **source** to all other nodes in **g**. This
- * function returns a map of `u -> { distance, predecessor }`. The distance
- * property holds the sum of the weights from **source** to `u` along the
- * shortest path or `Number.POSITIVE_INFINITY` if there is no path from
- * **source**. The predecessor property can be used to walk the individual
- * elements of the path from **source** to **u** in reverse order.
- *
- * This function takes an optional `weightFunc(e)` which returns the
- * weight of the edge `e`. If no weightFunc is supplied then each edge is
- * assumed to have a weight of 1. This function throws an Error if any of
- * the traversed edges have a negative edge weight.
- *
- * This function takes an optional `incidentFunc(u)` which returns the ids of
- * all edges incident to the node `u` for the purposes of shortest path
- * traversal. By default this function uses the `g.outEdges` for Digraphs and
- * `g.incidentEdges` for Graphs.
- *
- * This function takes `O((|E| + |V|) * log |V|)` time.
- *
- * [Dijkstra's algorithm]: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
- *
- * @param {Graph} g the graph to search for shortest paths from **source**
- * @param {Object} source the source from which to start the search
- * @param {Function} [weightFunc] optional weight function
- * @param {Function} [incidentFunc] optional incident function
- */
-function dijkstra(g, source, weightFunc, incidentFunc) {
- var results = {},
- pq = new PriorityQueue();
-
- function updateNeighbors(e) {
- var incidentNodes = g.incidentNodes(e),
- v = incidentNodes[0] !== u ? incidentNodes[0] : incidentNodes[1],
- vEntry = results[v],
- weight = weightFunc(e),
- distance = uEntry.distance + weight;
-
- if (weight < 0) {
- throw new Error("dijkstra does not allow negative edge weights. Bad edge: " + e + " Weight: " + weight);
- }
-
- if (distance < vEntry.distance) {
- vEntry.distance = distance;
- vEntry.predecessor = u;
- pq.decrease(v, distance);
- }
- }
-
- weightFunc = weightFunc || function() { return 1; };
- incidentFunc = incidentFunc || (g.isDirected()
- ? function(u) { return g.outEdges(u); }
- : function(u) { return g.incidentEdges(u); });
-
- g.eachNode(function(u) {
- var distance = u === source ? 0 : Number.POSITIVE_INFINITY;
- results[u] = { distance: distance };
- pq.add(u, distance);
- });
-
- var u, uEntry;
- while (pq.size() > 0) {
- u = pq.removeMin();
- uEntry = results[u];
- if (uEntry.distance === Number.POSITIVE_INFINITY) {
- break;
- }
-
- incidentFunc(u).forEach(updateNeighbors);
- }
-
- return results;
-}
-
-},{"cp-data":19}],32:[function(require,module,exports){
-var dijkstra = require("./dijkstra");
-
-module.exports = dijkstraAll;
-
-/**
- * This function finds the shortest path from each node to every other
- * reachable node in the graph. It is similar to [alg.dijkstra][], but
- * instead of returning a single-source array, it returns a mapping of
- * of `source -> alg.dijksta(g, source, weightFunc, incidentFunc)`.
- *
- * This function takes an optional `weightFunc(e)` which returns the
- * weight of the edge `e`. If no weightFunc is supplied then each edge is
- * assumed to have a weight of 1. This function throws an Error if any of
- * the traversed edges have a negative edge weight.
- *
- * This function takes an optional `incidentFunc(u)` which returns the ids of
- * all edges incident to the node `u` for the purposes of shortest path
- * traversal. By default this function uses the `outEdges` function on the
- * supplied graph.
- *
- * This function takes `O(|V| * (|E| + |V|) * log |V|)` time.
- *
- * [alg.dijkstra]: dijkstra.js.html#dijkstra
- *
- * @param {Graph} g the graph to search for shortest paths from **source**
- * @param {Function} [weightFunc] optional weight function
- * @param {Function} [incidentFunc] optional incident function
- */
-function dijkstraAll(g, weightFunc, incidentFunc) {
- var results = {};
- g.eachNode(function(u) {
- results[u] = dijkstra(g, u, weightFunc, incidentFunc);
- });
- return results;
-}
-
-},{"./dijkstra":31}],33:[function(require,module,exports){
-var tarjan = require("./tarjan");
-
-module.exports = findCycles;
-
-/*
- * Given a Digraph **g** this function returns all nodes that are part of a
- * cycle. Since there may be more than one cycle in a graph this function
- * returns an array of these cycles, where each cycle is itself represented
- * by an array of ids for each node involved in that cycle.
- *
- * [alg.isAcyclic][] is more efficient if you only need to determine whether
- * a graph has a cycle or not.
- *
- * [alg.isAcyclic]: isAcyclic.js.html#isAcyclic
- *
- * @param {Digraph} g the graph to search for cycles.
- */
-function findCycles(g) {
- return tarjan(g).filter(function(cmpt) { return cmpt.length > 1; });
-}
-
-},{"./tarjan":39}],34:[function(require,module,exports){
-module.exports = floydWarshall;
-
-/**
- * This function is an implementation of the [Floyd-Warshall algorithm][],
- * which finds the shortest path from each node to every other reachable node
- * in the graph. It is similar to [alg.dijkstraAll][], but it handles negative
- * edge weights and is more efficient for some types of graphs. This function
- * returns a map of `source -> { target -> { distance, predecessor }`. The
- * distance property holds the sum of the weights from `source` to `target`
- * along the shortest path of `Number.POSITIVE_INFINITY` if there is no path
- * from `source`. The predecessor property can be used to walk the individual
- * elements of the path from `source` to `target` in reverse order.
- *
- * This function takes an optional `weightFunc(e)` which returns the
- * weight of the edge `e`. If no weightFunc is supplied then each edge is
- * assumed to have a weight of 1.
- *
- * This function takes an optional `incidentFunc(u)` which returns the ids of
- * all edges incident to the node `u` for the purposes of shortest path
- * traversal. By default this function uses the `outEdges` function on the
- * supplied graph.
- *
- * This algorithm takes O(|V|^3) time.
- *
- * [Floyd-Warshall algorithm]: https://en.wikipedia.org/wiki/Floyd-Warshall_algorithm
- * [alg.dijkstraAll]: dijkstraAll.js.html#dijkstraAll
- *
- * @param {Graph} g the graph to search for shortest paths from **source**
- * @param {Function} [weightFunc] optional weight function
- * @param {Function} [incidentFunc] optional incident function
- */
-function floydWarshall(g, weightFunc, incidentFunc) {
- var results = {},
- nodes = g.nodes();
-
- weightFunc = weightFunc || function() { return 1; };
- incidentFunc = incidentFunc || (g.isDirected()
- ? function(u) { return g.outEdges(u); }
- : function(u) { return g.incidentEdges(u); });
-
- nodes.forEach(function(u) {
- results[u] = {};
- results[u][u] = { distance: 0 };
- nodes.forEach(function(v) {
- if (u !== v) {
- results[u][v] = { distance: Number.POSITIVE_INFINITY };
- }
- });
- incidentFunc(u).forEach(function(e) {
- var incidentNodes = g.incidentNodes(e),
- v = incidentNodes[0] !== u ? incidentNodes[0] : incidentNodes[1],
- d = weightFunc(e);
- if (d < results[u][v].distance) {
- results[u][v] = { distance: d, predecessor: u };
- }
- });
- });
-
- nodes.forEach(function(k) {
- var rowK = results[k];
- nodes.forEach(function(i) {
- var rowI = results[i];
- nodes.forEach(function(j) {
- var ik = rowI[k];
- var kj = rowK[j];
- var ij = rowI[j];
- var altDistance = ik.distance + kj.distance;
- if (altDistance < ij.distance) {
- ij.distance = altDistance;
- ij.predecessor = kj.predecessor;
- }
- });
- });
- });
-
- return results;
-}
-
-},{}],35:[function(require,module,exports){
-var topsort = require("./topsort");
-
-module.exports = isAcyclic;
-
-/*
- * Given a Digraph **g** this function returns `true` if the graph has no
- * cycles and returns `false` if it does. This algorithm returns as soon as it
- * detects the first cycle.
- *
- * Use [alg.findCycles][] if you need the actual list of cycles in a graph.
- *
- * [alg.findCycles]: findCycles.js.html#findCycles
- *
- * @param {Digraph} g the graph to test for cycles
- */
-function isAcyclic(g) {
- try {
- topsort(g);
- } catch (e) {
- if (e instanceof topsort.CycleException) return false;
- throw e;
- }
- return true;
-}
-
-},{"./topsort":40}],36:[function(require,module,exports){
-/* jshint -W079 */
-var Set = require("cp-data").Set;
-/* jshint +W079 */
-
-module.exports = postorder;
-
-// Postorder traversal of g, calling f for each visited node. Assumes the graph
-// is a tree.
-function postorder(g, root, f) {
- var visited = new Set();
- if (g.isDirected()) {
- throw new Error("This function only works for undirected graphs");
- }
- function dfs(u, prev) {
- if (visited.has(u)) {
- throw new Error("The input graph is not a tree: " + g);
- }
- visited.add(u);
- g.neighbors(u).forEach(function(v) {
- if (v !== prev) dfs(v, u);
- });
- f(u);
- }
- dfs(root);
-}
-
-},{"cp-data":19}],37:[function(require,module,exports){
-/* jshint -W079 */
-var Set = require("cp-data").Set;
-/* jshint +W079 */
-
-module.exports = preorder;
-
-// Preorder traversal of g, calling f for each visited node. Assumes the graph
-// is a tree.
-function preorder(g, root, f) {
- var visited = new Set();
- if (g.isDirected()) {
- throw new Error("This function only works for undirected graphs");
- }
- function dfs(u, prev) {
- if (visited.has(u)) {
- throw new Error("The input graph is not a tree: " + g);
- }
- visited.add(u);
- f(u);
- g.neighbors(u).forEach(function(v) {
- if (v !== prev) dfs(v, u);
- });
- }
- dfs(root);
-}
-
-},{"cp-data":19}],38:[function(require,module,exports){
-var Graph = require("../Graph"),
- PriorityQueue = require("cp-data").PriorityQueue;
-
-module.exports = prim;
-
-/**
- * [Prim's algorithm][] takes a connected undirected graph and generates a
- * [minimum spanning tree][]. This function returns the minimum spanning
- * tree as an undirected graph. This algorithm is derived from the description
- * in "Introduction to Algorithms", Third Edition, Cormen, et al., Pg 634.
- *
- * This function takes a `weightFunc(e)` which returns the weight of the edge
- * `e`. It throws an Error if the graph is not connected.
- *
- * This function takes `O(|E| log |V|)` time.
- *
- * [Prim's algorithm]: https://en.wikipedia.org/wiki/Prim's_algorithm
- * [minimum spanning tree]: https://en.wikipedia.org/wiki/Minimum_spanning_tree
- *
- * @param {Graph} g the graph used to generate the minimum spanning tree
- * @param {Function} weightFunc the weight function to use
- */
-function prim(g, weightFunc) {
- var result = new Graph(),
- parents = {},
- pq = new PriorityQueue(),
- u;
-
- function updateNeighbors(e) {
- var incidentNodes = g.incidentNodes(e),
- v = incidentNodes[0] !== u ? incidentNodes[0] : incidentNodes[1],
- pri = pq.priority(v);
- if (pri !== undefined) {
- var edgeWeight = weightFunc(e);
- if (edgeWeight < pri) {
- parents[v] = u;
- pq.decrease(v, edgeWeight);
- }
- }
- }
-
- if (g.order() === 0) {
- return result;
- }
-
- g.eachNode(function(u) {
- pq.add(u, Number.POSITIVE_INFINITY);
- result.addNode(u);
- });
-
- // Start from an arbitrary node
- pq.decrease(g.nodes()[0], 0);
-
- var init = false;
- while (pq.size() > 0) {
- u = pq.removeMin();
- if (u in parents) {
- result.addEdge(null, u, parents[u]);
- } else if (init) {
- throw new Error("Input graph is not connected: " + g);
- } else {
- init = true;
- }
-
- g.incidentEdges(u).forEach(updateNeighbors);
- }
-
- return result;
-}
-
-},{"../Graph":29,"cp-data":19}],39:[function(require,module,exports){
-module.exports = tarjan;
-
-/**
- * This function is an implementation of [Tarjan's algorithm][] which finds
- * all [strongly connected components][] in the directed graph **g**. Each
- * strongly connected component is composed of nodes that can reach all other
- * nodes in the component via directed edges. A strongly connected component
- * can consist of a single node if that node cannot both reach and be reached
- * by any other specific node in the graph. Components of more than one node
- * are guaranteed to have at least one cycle.
- *
- * This function returns an array of components. Each component is itself an
- * array that contains the ids of all nodes in the component.
- *
- * [Tarjan's algorithm]: http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm
- * [strongly connected components]: http://en.wikipedia.org/wiki/Strongly_connected_component
- *
- * @param {Digraph} g the graph to search for strongly connected components
- */
-function tarjan(g) {
- if (!g.isDirected()) {
- throw new Error("tarjan can only be applied to a directed graph. Bad input: " + g);
- }
-
- var index = 0,
- stack = [],
- visited = {}, // node id -> { onStack, lowlink, index }
- results = [];
-
- function dfs(u) {
- var entry = visited[u] = {
- onStack: true,
- lowlink: index,
- index: index++
- };
- stack.push(u);
-
- g.successors(u).forEach(function(v) {
- if (!(v in visited)) {
- dfs(v);
- entry.lowlink = Math.min(entry.lowlink, visited[v].lowlink);
- } else if (visited[v].onStack) {
- entry.lowlink = Math.min(entry.lowlink, visited[v].index);
- }
- });
-
- if (entry.lowlink === entry.index) {
- var cmpt = [],
- v;
- do {
- v = stack.pop();
- visited[v].onStack = false;
- cmpt.push(v);
- } while (u !== v);
- results.push(cmpt);
- }
- }
-
- g.nodes().forEach(function(u) {
- if (!(u in visited)) {
- dfs(u);
- }
- });
-
- return results;
-}
-
-},{}],40:[function(require,module,exports){
-module.exports = topsort;
-topsort.CycleException = CycleException;
-
-/*
- * Given a graph **g**, this function returns an ordered list of nodes such
- * that for each edge `u -> v`, `u` appears before `v` in the list. If the
- * graph has a cycle it is impossible to generate such a list and
- * **CycleException** is thrown.
- *
- * See [topological sorting](https://en.wikipedia.org/wiki/Topological_sorting)
- * for more details about how this algorithm works.
- *
- * @param {Digraph} g the graph to sort
- */
-function topsort(g) {
- if (!g.isDirected()) {
- throw new Error("topsort can only be applied to a directed graph. Bad input: " + g);
- }
-
- var visited = {};
- var stack = {};
- var results = [];
-
- function visit(node) {
- if (node in stack) {
- throw new CycleException();
- }
-
- if (!(node in visited)) {
- stack[node] = true;
- visited[node] = true;
- g.predecessors(node).forEach(function(pred) {
- visit(pred);
- });
- delete stack[node];
- results.push(node);
- }
- }
-
- var sinks = g.sinks();
- if (g.order() !== 0 && sinks.length === 0) {
- throw new CycleException();
- }
-
- g.sinks().forEach(function(sink) {
- visit(sink);
- });
-
- return results;
-}
-
-function CycleException() {}
-
-CycleException.prototype.toString = function() {
- return "Graph has at least one cycle";
-};
-
-},{}],41:[function(require,module,exports){
-// This file provides a helper function that mixes-in Dot behavior to an
-// existing graph prototype.
-
-/* jshint -W079 */
-var Set = require("cp-data").Set;
-/* jshint +W079 */
-
-module.exports = compoundify;
-
-// Extends the given SuperConstructor with the ability for nodes to contain
-// other nodes. A special node id `null` is used to indicate the root graph.
-function compoundify(SuperConstructor) {
- function Constructor() {
- SuperConstructor.call(this);
-
- // Map of object id -> parent id (or null for root graph)
- this._parents = {};
-
- // Map of id (or null) -> children set
- this._children = {};
- this._children[null] = new Set();
- }
-
- Constructor.prototype = new SuperConstructor();
- Constructor.prototype.constructor = Constructor;
-
- Constructor.prototype.parent = function(u, parent) {
- this._strictGetNode(u);
-
- if (arguments.length < 2) {
- return this._parents[u];
- }
-
- if (u === parent) {
- throw new Error("Cannot make " + u + " a parent of itself");
- }
- if (parent !== null) {
- this._strictGetNode(parent);
- }
-
- this._children[this._parents[u]].remove(u);
- this._parents[u] = parent;
- this._children[parent].add(u);
- };
-
- Constructor.prototype.children = function(u) {
- if (u !== null) {
- this._strictGetNode(u);
- }
- return this._children[u].keys();
- };
-
- Constructor.prototype.addNode = function(u, value) {
- u = SuperConstructor.prototype.addNode.call(this, u, value);
- this._parents[u] = null;
- this._children[u] = new Set();
- this._children[null].add(u);
- return u;
- };
-
- Constructor.prototype.delNode = function(u) {
- // Promote all children to the parent of the subgraph
- var parent = this.parent(u);
- this._children[u].keys().forEach(function(child) {
- this.parent(child, parent);
- }, this);
-
- this._children[parent].remove(u);
- delete this._parents[u];
- delete this._children[u];
-
- return SuperConstructor.prototype.delNode.call(this, u);
- };
-
- Constructor.prototype.copy = function() {
- var copy = SuperConstructor.prototype.copy.call(this);
- this.nodes().forEach(function(u) {
- copy.parent(u, this.parent(u));
- }, this);
- return copy;
- };
-
- Constructor.prototype.filterNodes = function(filter) {
- var self = this,
- copy = SuperConstructor.prototype.filterNodes.call(this, filter);
-
- var parents = {};
- function findParent(u) {
- var parent = self.parent(u);
- if (parent === null || copy.hasNode(parent)) {
- parents[u] = parent;
- return parent;
- } else if (parent in parents) {
- return parents[parent];
- } else {
- return findParent(parent);
- }
- }
-
- copy.eachNode(function(u) { copy.parent(u, findParent(u)); });
-
- return copy;
- };
-
- return Constructor;
-}
-
-},{"cp-data":19}],42:[function(require,module,exports){
-var Graph = require("../Graph"),
- Digraph = require("../Digraph"),
- CGraph = require("../CGraph"),
- CDigraph = require("../CDigraph");
-
-exports.decode = function(nodes, edges, Ctor) {
- Ctor = Ctor || Digraph;
-
- if (typeOf(nodes) !== "Array") {
- throw new Error("nodes is not an Array");
- }
-
- if (typeOf(edges) !== "Array") {
- throw new Error("edges is not an Array");
- }
-
- if (typeof Ctor === "string") {
- switch(Ctor) {
- case "graph": Ctor = Graph; break;
- case "digraph": Ctor = Digraph; break;
- case "cgraph": Ctor = CGraph; break;
- case "cdigraph": Ctor = CDigraph; break;
- default: throw new Error("Unrecognized graph type: " + Ctor);
- }
- }
-
- var graph = new Ctor();
-
- nodes.forEach(function(u) {
- graph.addNode(u.id, u.value);
- });
-
- // If the graph is compound, set up children...
- if (graph.parent) {
- nodes.forEach(function(u) {
- if (u.children) {
- u.children.forEach(function(v) {
- graph.parent(v, u.id);
- });
- }
- });
- }
-
- edges.forEach(function(e) {
- graph.addEdge(e.id, e.u, e.v, e.value);
- });
-
- return graph;
-};
-
-exports.encode = function(graph) {
- var nodes = [];
- var edges = [];
-
- graph.eachNode(function(u, value) {
- var node = {id: u, value: value};
- if (graph.children) {
- var children = graph.children(u);
- if (children.length) {
- node.children = children;
- }
- }
- nodes.push(node);
- });
-
- graph.eachEdge(function(e, u, v, value) {
- edges.push({id: e, u: u, v: v, value: value});
- });
-
- var type;
- if (graph instanceof CDigraph) {
- type = "cdigraph";
- } else if (graph instanceof CGraph) {
- type = "cgraph";
- } else if (graph instanceof Digraph) {
- type = "digraph";
- } else if (graph instanceof Graph) {
- type = "graph";
- } else {
- throw new Error("Couldn't determine type of graph: " + graph);
- }
-
- return { nodes: nodes, edges: edges, type: type };
-};
-
-function typeOf(obj) {
- return Object.prototype.toString.call(obj).slice(8, -1);
-}
-
-},{"../CDigraph":26,"../CGraph":27,"../Digraph":28,"../Graph":29}],43:[function(require,module,exports){
-/* jshint -W079 */
-var Set = require("cp-data").Set;
-/* jshint +W079 */
-
-exports.all = function() {
- return function() { return true; };
-};
-
-exports.nodesFromList = function(nodes) {
- var set = new Set(nodes);
- return function(u) {
- return set.has(u);
- };
-};
-
-},{"cp-data":19}],44:[function(require,module,exports){
-var Graph = require("./Graph"),
- Digraph = require("./Digraph");
-
-// Side-effect based changes are lousy, but node doesn't seem to resolve the
-// requires cycle.
-
-/**
- * Returns a new directed graph using the nodes and edges from this graph. The
- * new graph will have the same nodes, but will have twice the number of edges:
- * each edge is split into two edges with opposite directions. Edge ids,
- * consequently, are not preserved by this transformation.
- */
-Graph.prototype.toDigraph =
-Graph.prototype.asDirected = function() {
- var g = new Digraph();
- this.eachNode(function(u, value) { g.addNode(u, value); });
- this.eachEdge(function(e, u, v, value) {
- g.addEdge(null, u, v, value);
- g.addEdge(null, v, u, value);
- });
- return g;
-};
-
-/**
- * Returns a new undirected graph using the nodes and edges from this graph.
- * The new graph will have the same nodes, but the edges will be made
- * undirected. Edge ids are preserved in this transformation.
- */
-Digraph.prototype.toGraph =
-Digraph.prototype.asUndirected = function() {
- var g = new Graph();
- this.eachNode(function(u, value) { g.addNode(u, value); });
- this.eachEdge(function(e, u, v, value) {
- g.addEdge(e, u, v, value);
- });
- return g;
-};
-
-},{"./Digraph":28,"./Graph":29}],45:[function(require,module,exports){
-// Returns an array of all values for properties of **o**.
-exports.values = function(o) {
- var ks = Object.keys(o),
- len = ks.length,
- result = new Array(len),
- i;
- for (i = 0; i < len; ++i) {
- result[i] = o[ks[i]];
- }
- return result;
-};
-
-},{}],46:[function(require,module,exports){
-module.exports = '0.7.4';
-
-},{}]},{},[1])
-;
-joint.layout.DirectedGraph = {
-
- layout: function(graph, opt) {
-
- opt = opt || {};
-
- var inputGraph = this._prepareData(graph);
- var runner = dagre.layout();
-
- if (opt.debugLevel) { runner.debugLevel(opt.debugLevel); }
- if (opt.rankDir) { runner.rankDir(opt.rankDir); }
- if (opt.rankSep) { runner.rankSep(opt.rankSep); }
- if (opt.edgeSep) { runner.edgeSep(opt.edgeSep); }
- if (opt.nodeSep) { runner.nodeSep(opt.nodeSep); }
-
- var layoutGraph = runner.run(inputGraph);
-
- layoutGraph.eachNode(function(u, value) {
- if (!value.dummy) {
- graph.get('cells').get(u).set('position', {
- x: value.x - value.width/2,
- y: value.y - value.height/2
- });
- }
- });
-
- if (opt.setLinkVertices) {
-
- layoutGraph.eachEdge(function(e, u, v, value) {
- var link = graph.get('cells').get(e);
- if (link) {
- graph.get('cells').get(e).set('vertices', value.points);
- }
- });
- }
-
- return { width: layoutGraph.graph().width, height: layoutGraph.graph().height };
- },
-
- _prepareData: function(graph) {
- var dagreGraph = new dagre.Digraph();
-
- // For each element.
- _.each(graph.getElements(), function(cell) {
-
- if (dagreGraph.hasNode(cell.id)) return;
-
- dagreGraph.addNode(cell.id, {
- width: cell.get('size').width,
- height: cell.get('size').height,
- rank: cell.get('rank')
- });
- });
-
- // For each link.
- _.each(graph.getLinks(), function(cell) {
-
- if (dagreGraph.hasEdge(cell.id)) return;
-
- var sourceId = cell.get('source').id;
- var targetId = cell.get('target').id;
-
- dagreGraph.addEdge(cell.id, sourceId, targetId, { minLen: cell.get('minLen') || 1 });
- });
-
- return dagreGraph;
- }
-};
projects / VSoRC / .git / blobdiff