diff options
Diffstat (limited to 'devtools/client/shared/vendor/dagre-d3.js')
| -rw-r--r-- | devtools/client/shared/vendor/dagre-d3.js | 4560 |
1 files changed, 4560 insertions, 0 deletions
diff --git a/devtools/client/shared/vendor/dagre-d3.js b/devtools/client/shared/vendor/dagre-d3.js new file mode 100644 index 0000000000..482ce827f9 --- /dev/null +++ b/devtools/client/shared/vendor/dagre-d3.js @@ -0,0 +1,4560 @@ +;(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=self;/** + * @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.dagreD3 = require('./index'); + +},{"./index":2}],2:[function(require,module,exports){ +/** + * @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. + */ +module.exports = { + Digraph: require('graphlib').Digraph, + Renderer: require('./lib/Renderer'), + json: require('graphlib').converter.json, + layout: require('dagre').layout, + version: require('./lib/version') +}; + +},{"./lib/Renderer":3,"./lib/version":4,"dagre":11,"graphlib":28}],3:[function(require,module,exports){ +var layout = require('dagre').layout; + +var d3; +try { d3 = require('d3'); } catch (_) { d3 = window.d3; } + +module.exports = Renderer; + +function Renderer() { + // Set up defaults... + this._layout = layout(); + + this.drawNodes(defaultDrawNodes); + this.drawEdgeLabels(defaultDrawEdgeLabels); + this.drawEdgePaths(defaultDrawEdgePaths); + this.positionNodes(defaultPositionNodes); + this.positionEdgeLabels(defaultPositionEdgeLabels); + this.positionEdgePaths(defaultPositionEdgePaths); + this.transition(defaultTransition); + this.postLayout(defaultPostLayout); + this.postRender(defaultPostRender); + + this.edgeInterpolate('bundle'); + this.edgeTension(0.95); +} + +Renderer.prototype.layout = function(layout) { + if (!arguments.length) { return this._layout; } + this._layout = layout; + return this; +}; + +Renderer.prototype.drawNodes = function(drawNodes) { + if (!arguments.length) { return this._drawNodes; } + this._drawNodes = bind(drawNodes, this); + return this; +}; + +Renderer.prototype.drawEdgeLabels = function(drawEdgeLabels) { + if (!arguments.length) { return this._drawEdgeLabels; } + this._drawEdgeLabels = bind(drawEdgeLabels, this); + return this; +}; + +Renderer.prototype.drawEdgePaths = function(drawEdgePaths) { + if (!arguments.length) { return this._drawEdgePaths; } + this._drawEdgePaths = bind(drawEdgePaths, this); + return this; +}; + +Renderer.prototype.positionNodes = function(positionNodes) { + if (!arguments.length) { return this._positionNodes; } + this._positionNodes = bind(positionNodes, this); + return this; +}; + +Renderer.prototype.positionEdgeLabels = function(positionEdgeLabels) { + if (!arguments.length) { return this._positionEdgeLabels; } + this._positionEdgeLabels = bind(positionEdgeLabels, this); + return this; +}; + +Renderer.prototype.positionEdgePaths = function(positionEdgePaths) { + if (!arguments.length) { return this._positionEdgePaths; } + this._positionEdgePaths = bind(positionEdgePaths, this); + return this; +}; + +Renderer.prototype.transition = function(transition) { + if (!arguments.length) { return this._transition; } + this._transition = bind(transition, this); + return this; +}; + +Renderer.prototype.postLayout = function(postLayout) { + if (!arguments.length) { return this._postLayout; } + this._postLayout = bind(postLayout, this); + return this; +}; + +Renderer.prototype.postRender = function(postRender) { + if (!arguments.length) { return this._postRender; } + this._postRender = bind(postRender, this); + return this; +}; + +Renderer.prototype.edgeInterpolate = function(edgeInterpolate) { + if (!arguments.length) { return this._edgeInterpolate; } + this._edgeInterpolate = edgeInterpolate; + return this; +}; + +Renderer.prototype.edgeTension = function(edgeTension) { + if (!arguments.length) { return this._edgeTension; } + this._edgeTension = edgeTension; + return this; +}; + +Renderer.prototype.run = function(graph, svg) { + // First copy the input graph so that it is not changed by the rendering + // process. + graph = copyAndInitGraph(graph); + + // Create layers + svg + .selectAll('g.edgePaths, g.edgeLabels, g.nodes') + .data(['edgePaths', 'edgeLabels', 'nodes']) + .enter() + .append('g') + .attr('class', function(d) { return d; }); + + + // Create node and edge roots, attach labels, and capture dimension + // information for use with layout. + var svgNodes = this._drawNodes(graph, svg.select('g.nodes')); + var svgEdgeLabels = this._drawEdgeLabels(graph, svg.select('g.edgeLabels')); + + svgNodes.each(function(u) { calculateDimensions(this, graph.node(u)); }); + svgEdgeLabels.each(function(e) { calculateDimensions(this, graph.edge(e)); }); + + // Now apply the layout function + var result = runLayout(graph, this._layout); + + // Run any user-specified post layout processing + this._postLayout(result, svg); + + var svgEdgePaths = this._drawEdgePaths(graph, svg.select('g.edgePaths')); + + // Apply the layout information to the graph + this._positionNodes(result, svgNodes); + this._positionEdgeLabels(result, svgEdgeLabels); + this._positionEdgePaths(result, svgEdgePaths); + + this._postRender(result, svg); + + return result; +}; + +function copyAndInitGraph(graph) { + var copy = graph.copy(); + + // Init labels if they were not present in the source graph + copy.nodes().forEach(function(u) { + var value = copy.node(u); + if (value === undefined) { + value = {}; + copy.node(u, value); + } + if (!('label' in value)) { value.label = ''; } + }); + + copy.edges().forEach(function(e) { + var value = copy.edge(e); + if (value === undefined) { + value = {}; + copy.edge(e, value); + } + if (!('label' in value)) { value.label = ''; } + }); + + return copy; +} + +function calculateDimensions(group, value) { + var bbox = group.getBBox(); + value.width = bbox.width; + value.height = bbox.height; +} + +function runLayout(graph, layout) { + var result = layout.run(graph); + + // Copy labels to the result graph + graph.eachNode(function(u, value) { result.node(u).label = value.label; }); + graph.eachEdge(function(e, u, v, value) { result.edge(e).label = value.label; }); + + return result; +} + +function defaultDrawNodes(g, root) { + var nodes = g.nodes().filter(function(u) { return !isComposite(g, u); }); + + var svgNodes = root + .selectAll('g.node') + .classed('enter', false) + .data(nodes, function(u) { return u; }); + + svgNodes.selectAll('*').remove(); + + svgNodes + .enter() + .append('g') + .style('opacity', 0) + .attr('class', 'node enter'); + + svgNodes.each(function(u) { addLabel(g.node(u), d3.select(this), 10, 10); }); + + this._transition(svgNodes.exit()) + .style('opacity', 0) + .remove(); + + return svgNodes; +} + +function defaultDrawEdgeLabels(g, root) { + var svgEdgeLabels = root + .selectAll('g.edgeLabel') + .classed('enter', false) + .data(g.edges(), function (e) { return e; }); + + svgEdgeLabels.selectAll('*').remove(); + + svgEdgeLabels + .enter() + .append('g') + .style('opacity', 0) + .attr('class', 'edgeLabel enter'); + + svgEdgeLabels.each(function(e) { addLabel(g.edge(e), d3.select(this), 0, 0); }); + + this._transition(svgEdgeLabels.exit()) + .style('opacity', 0) + .remove(); + + return svgEdgeLabels; +} + +var defaultDrawEdgePaths = function(g, root) { + var svgEdgePaths = root + .selectAll('g.edgePath') + .classed('enter', false) + .data(g.edges(), function(e) { return e; }); + + svgEdgePaths + .enter() + .append('g') + .attr('class', 'edgePath enter') + .append('path') + .style('opacity', 0) + .attr('marker-end', 'url(#arrowhead)'); + + this._transition(svgEdgePaths.exit()) + .style('opacity', 0) + .remove(); + + return svgEdgePaths; +}; + +function defaultPositionNodes(g, svgNodes, svgNodesEnter) { + function transform(u) { + var value = g.node(u); + return 'translate(' + value.x + ',' + value.y + ')'; + } + + // For entering nodes, position immediately without transition + svgNodes.filter('.enter').attr('transform', transform); + + this._transition(svgNodes) + .style('opacity', 1) + .attr('transform', transform); +} + +function defaultPositionEdgeLabels(g, svgEdgeLabels) { + function transform(e) { + var value = g.edge(e); + var point = findMidPoint(value.points); + return 'translate(' + point.x + ',' + point.y + ')'; + } + + // For entering edge labels, position immediately without transition + svgEdgeLabels.filter('.enter').attr('transform', transform); + + this._transition(svgEdgeLabels) + .style('opacity', 1) + .attr('transform', transform); +} + +function defaultPositionEdgePaths(g, svgEdgePaths) { + var interpolate = this._edgeInterpolate, + tension = this._edgeTension; + + function calcPoints(e) { + var value = g.edge(e); + var source = g.node(g.incidentNodes(e)[0]); + var target = g.node(g.incidentNodes(e)[1]); + var points = value.points.slice(); + + var p0 = points.length === 0 ? target : points[0]; + var p1 = points.length === 0 ? source : points[points.length - 1]; + + points.unshift(intersectRect(source, p0)); + // TODO: use bpodgursky's shortening algorithm here + points.push(intersectRect(target, p1)); + + return d3.svg.line() + .x(function(d) { return d.x; }) + .y(function(d) { return d.y; }) + .interpolate(interpolate) + .tension(tension) + (points); + } + + svgEdgePaths.filter('.enter').selectAll('path') + .attr('d', calcPoints); + + this._transition(svgEdgePaths.selectAll('path')) + .attr('d', calcPoints) + .style('opacity', 1); +} + +// By default we do not use transitions +function defaultTransition(selection) { + return selection; +} + +function defaultPostLayout() { + // Do nothing +} + +function defaultPostRender(graph, root) { + if (graph.isDirected() && root.select('#arrowhead').empty()) { + root + .append('svg:defs') + .append('svg:marker') + .attr('id', 'arrowhead') + .attr('viewBox', '0 0 10 10') + .attr('refX', 8) + .attr('refY', 5) + .attr('markerUnits', 'strokewidth') + .attr('markerWidth', 8) + .attr('markerHeight', 5) + .attr('orient', 'auto') + .attr('style', 'fill: #333') + .append('svg:path') + .attr('d', 'M 0 0 L 10 5 L 0 10 z'); + } +} + +function addLabel(node, root, marginX, marginY) { + // Add the rect first so that it appears behind the label + var label = node.label; + var rect = root.append('rect'); + var labelSvg = root.append('g'); + + if (label[0] === '<') { + addForeignObjectLabel(label, labelSvg); + // No margin for HTML elements + marginX = marginY = 0; + } else { + addTextLabel(label, + labelSvg, + Math.floor(node.labelCols), + node.labelCut); + } + + var bbox = root.node().getBBox(); + + labelSvg.attr('transform', + 'translate(' + (-bbox.width / 2) + ',' + (-bbox.height / 2) + ')'); + + rect + .attr('rx', 5) + .attr('ry', 5) + .attr('x', -(bbox.width / 2 + marginX)) + .attr('y', -(bbox.height / 2 + marginY)) + .attr('width', bbox.width + 2 * marginX) + .attr('height', bbox.height + 2 * marginY); +} + +function addForeignObjectLabel(label, root) { + var fo = root + .append('foreignObject') + .attr('width', '100000'); + + var w, h; + fo + .append('xhtml:div') + .style('float', 'left') + // TODO find a better way to get dimensions for foreignObjects... + .html(function() { return label; }) + .each(function() { + w = this.clientWidth; + h = this.clientHeight; + }); + + fo + .attr('width', w) + .attr('height', h); +} + +function addTextLabel(label, root, labelCols, labelCut) { + if (labelCut === undefined) labelCut = "false"; + labelCut = (labelCut.toString().toLowerCase() === "true"); + + var node = root + .append('text') + .attr('text-anchor', 'left'); + + label = label.replace(/\\n/g, "\n"); + + var arr = labelCols ? wordwrap(label, labelCols, labelCut) : label; + arr = arr.split("\n"); + for (var i = 0; i < arr.length; i++) { + node + .append('tspan') + .attr('dy', '1em') + .attr('x', '1') + .text(arr[i]); + } +} + +// Thanks to +// http://james.padolsey.com/javascript/wordwrap-for-javascript/ +function wordwrap (str, width, cut, brk) { + brk = brk || '\n'; + width = width || 75; + cut = cut || false; + + if (!str) { return str; } + + var regex = '.{1,' +width+ '}(\\s|$)' + (cut ? '|.{' +width+ '}|.+$' : '|\\S+?(\\s|$)'); + + return str.match( RegExp(regex, 'g') ).join( brk ); +} + +function findMidPoint(points) { + var midIdx = points.length / 2; + if (points.length % 2) { + return points[Math.floor(midIdx)]; + } else { + var p0 = points[midIdx - 1]; + var p1 = points[midIdx]; + return {x: (p0.x + p1.x) / 2, y: (p0.y + p1.y) / 2}; + } +} + +function intersectRect(rect, point) { + var x = rect.x; + var y = rect.y; + + // For now we only support rectangles + + // Rectangle intersection algorithm from: + // http://math.stackexchange.com/questions/108113/find-edge-between-two-boxes + var dx = point.x - x; + var dy = point.y - y; + var w = rect.width / 2; + var h = rect.height / 2; + + var sx, sy; + if (Math.abs(dy) * w > Math.abs(dx) * h) { + // Intersection is top or bottom of rect. + if (dy < 0) { + h = -h; + } + sx = dy === 0 ? 0 : h * dx / dy; + sy = h; + } else { + // Intersection is left or right of rect. + if (dx < 0) { + w = -w; + } + sx = w; + sy = dx === 0 ? 0 : w * dy / dx; + } + + return {x: x + sx, y: y + sy}; +} + +function isComposite(g, u) { + return 'children' in g && g.children(u).length; +} + +function bind(func, thisArg) { + // For some reason PhantomJS occassionally fails when using the builtin bind, + // so we check if it is available and if not, use a degenerate polyfill. + if (func.bind) { + return func.bind(thisArg); + } + + return function() { + return func.apply(thisArg, arguments); + }; +} + +},{"d3":10,"dagre":11}],4:[function(require,module,exports){ +module.exports = '0.1.5'; + +},{}],5:[function(require,module,exports){ +exports.Set = require('./lib/Set'); +exports.PriorityQueue = require('./lib/PriorityQueue'); +exports.version = require('./lib/version'); + +},{"./lib/PriorityQueue":6,"./lib/Set":7,"./lib/version":9}],6:[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; +}; + +},{}],7:[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":8}],8:[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); + }; +} + +},{}],9:[function(require,module,exports){ +module.exports = '1.1.3'; + +},{}],10:[function(require,module,exports){ +require("./d3"); +module.exports = d3; +(function () { delete this.d3; })(); // unset global + +},{}],11:[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":12,"./lib/version":27,"graphlib":28}],12:[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: 0, + // 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":13,"./position":18,"./rank":19,"./util":26,"graphlib":28}],13:[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":14,"./order/initLayerGraphs":15,"./order/initOrder":16,"./order/sortLayer":17,"./util":26}],14:[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":26}],15:[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":5,"graphlib":28}],16:[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":26,"./crossCount":14}],17:[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":26}],18:[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":26}],19:[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":20,"./rank/constraints":21,"./rank/feasibleTree":22,"./rank/initRank":23,"./rank/simplex":25,"./util":26,"graphlib":28}],20:[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":26}],21:[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); + }); +}; + +},{}],22:[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":26,"cp-data":5,"graphlib":28}],23:[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":26,"graphlib":28}],24:[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; +} + +},{}],25:[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":26,"./rankUtil":24}],26:[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; + +},{}],27:[function(require,module,exports){ +module.exports = '0.4.5'; + +},{}],28:[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":30,"./lib/CGraph":31,"./lib/Digraph":32,"./lib/Graph":33,"./lib/alg/components":34,"./lib/alg/dijkstra":35,"./lib/alg/dijkstraAll":36,"./lib/alg/findCycles":37,"./lib/alg/floydWarshall":38,"./lib/alg/isAcyclic":39,"./lib/alg/postorder":40,"./lib/alg/preorder":41,"./lib/alg/prim":42,"./lib/alg/tarjan":43,"./lib/alg/topsort":44,"./lib/converter/json.js":46,"./lib/filter":47,"./lib/graph-converters":48,"./lib/version":50}],29:[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":5}],30:[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":32,"./compoundify":45}],31:[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":33,"./compoundify":45}],32:[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":29,"./util":49,"cp-data":5}],33:[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":29,"./util":49,"cp-data":5}],34:[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":5}],35:[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":5}],36:[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":35}],37:[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":43}],38:[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; +} + +},{}],39:[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":44}],40:[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":5}],41:[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":5}],42:[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":33,"cp-data":5}],43:[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; +} + +},{}],44:[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"; +}; + +},{}],45:[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":5}],46:[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":30,"../CGraph":31,"../Digraph":32,"../Graph":33}],47:[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":5}],48:[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":32,"./Graph":33}],49:[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; +}; + +},{}],50:[function(require,module,exports){ +module.exports = '0.7.4'; + +},{}]},{},[1]) +;
\ No newline at end of file |