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