1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/browser/devtools/webaudioeditor/lib/dagre-d3.js Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,4560 @@
1.4 +;(function e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);throw new Error("Cannot find module '"+o+"'")}var f=n[o]={exports:{}};t[o][0].call(f.exports,function(e){var n=t[o][1][e];return s(n?n:e)},f,f.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return s})({1:[function(require,module,exports){
1.5 +var global=self;/**
1.6 + * @license
1.7 + * Copyright (c) 2012-2013 Chris Pettitt
1.8 + *
1.9 + * Permission is hereby granted, free of charge, to any person obtaining a copy
1.10 + * of this software and associated documentation files (the "Software"), to deal
1.11 + * in the Software without restriction, including without limitation the rights
1.12 + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
1.13 + * copies of the Software, and to permit persons to whom the Software is
1.14 + * furnished to do so, subject to the following conditions:
1.15 + *
1.16 + * The above copyright notice and this permission notice shall be included in
1.17 + * all copies or substantial portions of the Software.
1.18 + *
1.19 + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
1.20 + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
1.21 + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
1.22 + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
1.23 + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
1.24 + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
1.25 + * THE SOFTWARE.
1.26 + */
1.27 +global.dagreD3 = require('./index');
1.28 +
1.29 +},{"./index":2}],2:[function(require,module,exports){
1.30 +/**
1.31 + * @license
1.32 + * Copyright (c) 2012-2013 Chris Pettitt
1.33 + *
1.34 + * Permission is hereby granted, free of charge, to any person obtaining a copy
1.35 + * of this software and associated documentation files (the "Software"), to deal
1.36 + * in the Software without restriction, including without limitation the rights
1.37 + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
1.38 + * copies of the Software, and to permit persons to whom the Software is
1.39 + * furnished to do so, subject to the following conditions:
1.40 + *
1.41 + * The above copyright notice and this permission notice shall be included in
1.42 + * all copies or substantial portions of the Software.
1.43 + *
1.44 + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
1.45 + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
1.46 + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
1.47 + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
1.48 + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
1.49 + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
1.50 + * THE SOFTWARE.
1.51 + */
1.52 +module.exports = {
1.53 + Digraph: require('graphlib').Digraph,
1.54 + Renderer: require('./lib/Renderer'),
1.55 + json: require('graphlib').converter.json,
1.56 + layout: require('dagre').layout,
1.57 + version: require('./lib/version')
1.58 +};
1.59 +
1.60 +},{"./lib/Renderer":3,"./lib/version":4,"dagre":11,"graphlib":28}],3:[function(require,module,exports){
1.61 +var layout = require('dagre').layout;
1.62 +
1.63 +var d3;
1.64 +try { d3 = require('d3'); } catch (_) { d3 = window.d3; }
1.65 +
1.66 +module.exports = Renderer;
1.67 +
1.68 +function Renderer() {
1.69 + // Set up defaults...
1.70 + this._layout = layout();
1.71 +
1.72 + this.drawNodes(defaultDrawNodes);
1.73 + this.drawEdgeLabels(defaultDrawEdgeLabels);
1.74 + this.drawEdgePaths(defaultDrawEdgePaths);
1.75 + this.positionNodes(defaultPositionNodes);
1.76 + this.positionEdgeLabels(defaultPositionEdgeLabels);
1.77 + this.positionEdgePaths(defaultPositionEdgePaths);
1.78 + this.transition(defaultTransition);
1.79 + this.postLayout(defaultPostLayout);
1.80 + this.postRender(defaultPostRender);
1.81 +
1.82 + this.edgeInterpolate('bundle');
1.83 + this.edgeTension(0.95);
1.84 +}
1.85 +
1.86 +Renderer.prototype.layout = function(layout) {
1.87 + if (!arguments.length) { return this._layout; }
1.88 + this._layout = layout;
1.89 + return this;
1.90 +};
1.91 +
1.92 +Renderer.prototype.drawNodes = function(drawNodes) {
1.93 + if (!arguments.length) { return this._drawNodes; }
1.94 + this._drawNodes = bind(drawNodes, this);
1.95 + return this;
1.96 +};
1.97 +
1.98 +Renderer.prototype.drawEdgeLabels = function(drawEdgeLabels) {
1.99 + if (!arguments.length) { return this._drawEdgeLabels; }
1.100 + this._drawEdgeLabels = bind(drawEdgeLabels, this);
1.101 + return this;
1.102 +};
1.103 +
1.104 +Renderer.prototype.drawEdgePaths = function(drawEdgePaths) {
1.105 + if (!arguments.length) { return this._drawEdgePaths; }
1.106 + this._drawEdgePaths = bind(drawEdgePaths, this);
1.107 + return this;
1.108 +};
1.109 +
1.110 +Renderer.prototype.positionNodes = function(positionNodes) {
1.111 + if (!arguments.length) { return this._positionNodes; }
1.112 + this._positionNodes = bind(positionNodes, this);
1.113 + return this;
1.114 +};
1.115 +
1.116 +Renderer.prototype.positionEdgeLabels = function(positionEdgeLabels) {
1.117 + if (!arguments.length) { return this._positionEdgeLabels; }
1.118 + this._positionEdgeLabels = bind(positionEdgeLabels, this);
1.119 + return this;
1.120 +};
1.121 +
1.122 +Renderer.prototype.positionEdgePaths = function(positionEdgePaths) {
1.123 + if (!arguments.length) { return this._positionEdgePaths; }
1.124 + this._positionEdgePaths = bind(positionEdgePaths, this);
1.125 + return this;
1.126 +};
1.127 +
1.128 +Renderer.prototype.transition = function(transition) {
1.129 + if (!arguments.length) { return this._transition; }
1.130 + this._transition = bind(transition, this);
1.131 + return this;
1.132 +};
1.133 +
1.134 +Renderer.prototype.postLayout = function(postLayout) {
1.135 + if (!arguments.length) { return this._postLayout; }
1.136 + this._postLayout = bind(postLayout, this);
1.137 + return this;
1.138 +};
1.139 +
1.140 +Renderer.prototype.postRender = function(postRender) {
1.141 + if (!arguments.length) { return this._postRender; }
1.142 + this._postRender = bind(postRender, this);
1.143 + return this;
1.144 +};
1.145 +
1.146 +Renderer.prototype.edgeInterpolate = function(edgeInterpolate) {
1.147 + if (!arguments.length) { return this._edgeInterpolate; }
1.148 + this._edgeInterpolate = edgeInterpolate;
1.149 + return this;
1.150 +};
1.151 +
1.152 +Renderer.prototype.edgeTension = function(edgeTension) {
1.153 + if (!arguments.length) { return this._edgeTension; }
1.154 + this._edgeTension = edgeTension;
1.155 + return this;
1.156 +};
1.157 +
1.158 +Renderer.prototype.run = function(graph, svg) {
1.159 + // First copy the input graph so that it is not changed by the rendering
1.160 + // process.
1.161 + graph = copyAndInitGraph(graph);
1.162 +
1.163 + // Create layers
1.164 + svg
1.165 + .selectAll('g.edgePaths, g.edgeLabels, g.nodes')
1.166 + .data(['edgePaths', 'edgeLabels', 'nodes'])
1.167 + .enter()
1.168 + .append('g')
1.169 + .attr('class', function(d) { return d; });
1.170 +
1.171 +
1.172 + // Create node and edge roots, attach labels, and capture dimension
1.173 + // information for use with layout.
1.174 + var svgNodes = this._drawNodes(graph, svg.select('g.nodes'));
1.175 + var svgEdgeLabels = this._drawEdgeLabels(graph, svg.select('g.edgeLabels'));
1.176 +
1.177 + svgNodes.each(function(u) { calculateDimensions(this, graph.node(u)); });
1.178 + svgEdgeLabels.each(function(e) { calculateDimensions(this, graph.edge(e)); });
1.179 +
1.180 + // Now apply the layout function
1.181 + var result = runLayout(graph, this._layout);
1.182 +
1.183 + // Run any user-specified post layout processing
1.184 + this._postLayout(result, svg);
1.185 +
1.186 + var svgEdgePaths = this._drawEdgePaths(graph, svg.select('g.edgePaths'));
1.187 +
1.188 + // Apply the layout information to the graph
1.189 + this._positionNodes(result, svgNodes);
1.190 + this._positionEdgeLabels(result, svgEdgeLabels);
1.191 + this._positionEdgePaths(result, svgEdgePaths);
1.192 +
1.193 + this._postRender(result, svg);
1.194 +
1.195 + return result;
1.196 +};
1.197 +
1.198 +function copyAndInitGraph(graph) {
1.199 + var copy = graph.copy();
1.200 +
1.201 + // Init labels if they were not present in the source graph
1.202 + copy.nodes().forEach(function(u) {
1.203 + var value = copy.node(u);
1.204 + if (value === undefined) {
1.205 + value = {};
1.206 + copy.node(u, value);
1.207 + }
1.208 + if (!('label' in value)) { value.label = ''; }
1.209 + });
1.210 +
1.211 + copy.edges().forEach(function(e) {
1.212 + var value = copy.edge(e);
1.213 + if (value === undefined) {
1.214 + value = {};
1.215 + copy.edge(e, value);
1.216 + }
1.217 + if (!('label' in value)) { value.label = ''; }
1.218 + });
1.219 +
1.220 + return copy;
1.221 +}
1.222 +
1.223 +function calculateDimensions(group, value) {
1.224 + var bbox = group.getBBox();
1.225 + value.width = bbox.width;
1.226 + value.height = bbox.height;
1.227 +}
1.228 +
1.229 +function runLayout(graph, layout) {
1.230 + var result = layout.run(graph);
1.231 +
1.232 + // Copy labels to the result graph
1.233 + graph.eachNode(function(u, value) { result.node(u).label = value.label; });
1.234 + graph.eachEdge(function(e, u, v, value) { result.edge(e).label = value.label; });
1.235 +
1.236 + return result;
1.237 +}
1.238 +
1.239 +function defaultDrawNodes(g, root) {
1.240 + var nodes = g.nodes().filter(function(u) { return !isComposite(g, u); });
1.241 +
1.242 + var svgNodes = root
1.243 + .selectAll('g.node')
1.244 + .classed('enter', false)
1.245 + .data(nodes, function(u) { return u; });
1.246 +
1.247 + svgNodes.selectAll('*').remove();
1.248 +
1.249 + svgNodes
1.250 + .enter()
1.251 + .append('g')
1.252 + .style('opacity', 0)
1.253 + .attr('class', 'node enter');
1.254 +
1.255 + svgNodes.each(function(u) { addLabel(g.node(u), d3.select(this), 10, 10); });
1.256 +
1.257 + this._transition(svgNodes.exit())
1.258 + .style('opacity', 0)
1.259 + .remove();
1.260 +
1.261 + return svgNodes;
1.262 +}
1.263 +
1.264 +function defaultDrawEdgeLabels(g, root) {
1.265 + var svgEdgeLabels = root
1.266 + .selectAll('g.edgeLabel')
1.267 + .classed('enter', false)
1.268 + .data(g.edges(), function (e) { return e; });
1.269 +
1.270 + svgEdgeLabels.selectAll('*').remove();
1.271 +
1.272 + svgEdgeLabels
1.273 + .enter()
1.274 + .append('g')
1.275 + .style('opacity', 0)
1.276 + .attr('class', 'edgeLabel enter');
1.277 +
1.278 + svgEdgeLabels.each(function(e) { addLabel(g.edge(e), d3.select(this), 0, 0); });
1.279 +
1.280 + this._transition(svgEdgeLabels.exit())
1.281 + .style('opacity', 0)
1.282 + .remove();
1.283 +
1.284 + return svgEdgeLabels;
1.285 +}
1.286 +
1.287 +var defaultDrawEdgePaths = function(g, root) {
1.288 + var svgEdgePaths = root
1.289 + .selectAll('g.edgePath')
1.290 + .classed('enter', false)
1.291 + .data(g.edges(), function(e) { return e; });
1.292 +
1.293 + svgEdgePaths
1.294 + .enter()
1.295 + .append('g')
1.296 + .attr('class', 'edgePath enter')
1.297 + .append('path')
1.298 + .style('opacity', 0)
1.299 + .attr('marker-end', 'url(#arrowhead)');
1.300 +
1.301 + this._transition(svgEdgePaths.exit())
1.302 + .style('opacity', 0)
1.303 + .remove();
1.304 +
1.305 + return svgEdgePaths;
1.306 +};
1.307 +
1.308 +function defaultPositionNodes(g, svgNodes, svgNodesEnter) {
1.309 + function transform(u) {
1.310 + var value = g.node(u);
1.311 + return 'translate(' + value.x + ',' + value.y + ')';
1.312 + }
1.313 +
1.314 + // For entering nodes, position immediately without transition
1.315 + svgNodes.filter('.enter').attr('transform', transform);
1.316 +
1.317 + this._transition(svgNodes)
1.318 + .style('opacity', 1)
1.319 + .attr('transform', transform);
1.320 +}
1.321 +
1.322 +function defaultPositionEdgeLabels(g, svgEdgeLabels) {
1.323 + function transform(e) {
1.324 + var value = g.edge(e);
1.325 + var point = findMidPoint(value.points);
1.326 + return 'translate(' + point.x + ',' + point.y + ')';
1.327 + }
1.328 +
1.329 + // For entering edge labels, position immediately without transition
1.330 + svgEdgeLabels.filter('.enter').attr('transform', transform);
1.331 +
1.332 + this._transition(svgEdgeLabels)
1.333 + .style('opacity', 1)
1.334 + .attr('transform', transform);
1.335 +}
1.336 +
1.337 +function defaultPositionEdgePaths(g, svgEdgePaths) {
1.338 + var interpolate = this._edgeInterpolate,
1.339 + tension = this._edgeTension;
1.340 +
1.341 + function calcPoints(e) {
1.342 + var value = g.edge(e);
1.343 + var source = g.node(g.incidentNodes(e)[0]);
1.344 + var target = g.node(g.incidentNodes(e)[1]);
1.345 + var points = value.points.slice();
1.346 +
1.347 + var p0 = points.length === 0 ? target : points[0];
1.348 + var p1 = points.length === 0 ? source : points[points.length - 1];
1.349 +
1.350 + points.unshift(intersectRect(source, p0));
1.351 + // TODO: use bpodgursky's shortening algorithm here
1.352 + points.push(intersectRect(target, p1));
1.353 +
1.354 + return d3.svg.line()
1.355 + .x(function(d) { return d.x; })
1.356 + .y(function(d) { return d.y; })
1.357 + .interpolate(interpolate)
1.358 + .tension(tension)
1.359 + (points);
1.360 + }
1.361 +
1.362 + svgEdgePaths.filter('.enter').selectAll('path')
1.363 + .attr('d', calcPoints);
1.364 +
1.365 + this._transition(svgEdgePaths.selectAll('path'))
1.366 + .attr('d', calcPoints)
1.367 + .style('opacity', 1);
1.368 +}
1.369 +
1.370 +// By default we do not use transitions
1.371 +function defaultTransition(selection) {
1.372 + return selection;
1.373 +}
1.374 +
1.375 +function defaultPostLayout() {
1.376 + // Do nothing
1.377 +}
1.378 +
1.379 +function defaultPostRender(graph, root) {
1.380 + if (graph.isDirected() && root.select('#arrowhead').empty()) {
1.381 + root
1.382 + .append('svg:defs')
1.383 + .append('svg:marker')
1.384 + .attr('id', 'arrowhead')
1.385 + .attr('viewBox', '0 0 10 10')
1.386 + .attr('refX', 8)
1.387 + .attr('refY', 5)
1.388 + .attr('markerUnits', 'strokewidth')
1.389 + .attr('markerWidth', 8)
1.390 + .attr('markerHeight', 5)
1.391 + .attr('orient', 'auto')
1.392 + .attr('style', 'fill: #333')
1.393 + .append('svg:path')
1.394 + .attr('d', 'M 0 0 L 10 5 L 0 10 z');
1.395 + }
1.396 +}
1.397 +
1.398 +function addLabel(node, root, marginX, marginY) {
1.399 + // Add the rect first so that it appears behind the label
1.400 + var label = node.label;
1.401 + var rect = root.append('rect');
1.402 + var labelSvg = root.append('g');
1.403 +
1.404 + if (label[0] === '<') {
1.405 + addForeignObjectLabel(label, labelSvg);
1.406 + // No margin for HTML elements
1.407 + marginX = marginY = 0;
1.408 + } else {
1.409 + addTextLabel(label,
1.410 + labelSvg,
1.411 + Math.floor(node.labelCols),
1.412 + node.labelCut);
1.413 + }
1.414 +
1.415 + var bbox = root.node().getBBox();
1.416 +
1.417 + labelSvg.attr('transform',
1.418 + 'translate(' + (-bbox.width / 2) + ',' + (-bbox.height / 2) + ')');
1.419 +
1.420 + rect
1.421 + .attr('rx', 5)
1.422 + .attr('ry', 5)
1.423 + .attr('x', -(bbox.width / 2 + marginX))
1.424 + .attr('y', -(bbox.height / 2 + marginY))
1.425 + .attr('width', bbox.width + 2 * marginX)
1.426 + .attr('height', bbox.height + 2 * marginY);
1.427 +}
1.428 +
1.429 +function addForeignObjectLabel(label, root) {
1.430 + var fo = root
1.431 + .append('foreignObject')
1.432 + .attr('width', '100000');
1.433 +
1.434 + var w, h;
1.435 + fo
1.436 + .append('xhtml:div')
1.437 + .style('float', 'left')
1.438 + // TODO find a better way to get dimensions for foreignObjects...
1.439 + .html(function() { return label; })
1.440 + .each(function() {
1.441 + w = this.clientWidth;
1.442 + h = this.clientHeight;
1.443 + });
1.444 +
1.445 + fo
1.446 + .attr('width', w)
1.447 + .attr('height', h);
1.448 +}
1.449 +
1.450 +function addTextLabel(label, root, labelCols, labelCut) {
1.451 + if (labelCut === undefined) labelCut = "false";
1.452 + labelCut = (labelCut.toString().toLowerCase() === "true");
1.453 +
1.454 + var node = root
1.455 + .append('text')
1.456 + .attr('text-anchor', 'left');
1.457 +
1.458 + label = label.replace(/\\n/g, "\n");
1.459 +
1.460 + var arr = labelCols ? wordwrap(label, labelCols, labelCut) : label;
1.461 + arr = arr.split("\n");
1.462 + for (var i = 0; i < arr.length; i++) {
1.463 + node
1.464 + .append('tspan')
1.465 + .attr('dy', '1em')
1.466 + .attr('x', '1')
1.467 + .text(arr[i]);
1.468 + }
1.469 +}
1.470 +
1.471 +// Thanks to
1.472 +// http://james.padolsey.com/javascript/wordwrap-for-javascript/
1.473 +function wordwrap (str, width, cut, brk) {
1.474 + brk = brk || '\n';
1.475 + width = width || 75;
1.476 + cut = cut || false;
1.477 +
1.478 + if (!str) { return str; }
1.479 +
1.480 + var regex = '.{1,' +width+ '}(\\s|$)' + (cut ? '|.{' +width+ '}|.+$' : '|\\S+?(\\s|$)');
1.481 +
1.482 + return str.match( RegExp(regex, 'g') ).join( brk );
1.483 +}
1.484 +
1.485 +function findMidPoint(points) {
1.486 + var midIdx = points.length / 2;
1.487 + if (points.length % 2) {
1.488 + return points[Math.floor(midIdx)];
1.489 + } else {
1.490 + var p0 = points[midIdx - 1];
1.491 + var p1 = points[midIdx];
1.492 + return {x: (p0.x + p1.x) / 2, y: (p0.y + p1.y) / 2};
1.493 + }
1.494 +}
1.495 +
1.496 +function intersectRect(rect, point) {
1.497 + var x = rect.x;
1.498 + var y = rect.y;
1.499 +
1.500 + // For now we only support rectangles
1.501 +
1.502 + // Rectangle intersection algorithm from:
1.503 + // http://math.stackexchange.com/questions/108113/find-edge-between-two-boxes
1.504 + var dx = point.x - x;
1.505 + var dy = point.y - y;
1.506 + var w = rect.width / 2;
1.507 + var h = rect.height / 2;
1.508 +
1.509 + var sx, sy;
1.510 + if (Math.abs(dy) * w > Math.abs(dx) * h) {
1.511 + // Intersection is top or bottom of rect.
1.512 + if (dy < 0) {
1.513 + h = -h;
1.514 + }
1.515 + sx = dy === 0 ? 0 : h * dx / dy;
1.516 + sy = h;
1.517 + } else {
1.518 + // Intersection is left or right of rect.
1.519 + if (dx < 0) {
1.520 + w = -w;
1.521 + }
1.522 + sx = w;
1.523 + sy = dx === 0 ? 0 : w * dy / dx;
1.524 + }
1.525 +
1.526 + return {x: x + sx, y: y + sy};
1.527 +}
1.528 +
1.529 +function isComposite(g, u) {
1.530 + return 'children' in g && g.children(u).length;
1.531 +}
1.532 +
1.533 +function bind(func, thisArg) {
1.534 + // For some reason PhantomJS occassionally fails when using the builtin bind,
1.535 + // so we check if it is available and if not, use a degenerate polyfill.
1.536 + if (func.bind) {
1.537 + return func.bind(thisArg);
1.538 + }
1.539 +
1.540 + return function() {
1.541 + return func.apply(thisArg, arguments);
1.542 + };
1.543 +}
1.544 +
1.545 +},{"d3":10,"dagre":11}],4:[function(require,module,exports){
1.546 +module.exports = '0.1.5';
1.547 +
1.548 +},{}],5:[function(require,module,exports){
1.549 +exports.Set = require('./lib/Set');
1.550 +exports.PriorityQueue = require('./lib/PriorityQueue');
1.551 +exports.version = require('./lib/version');
1.552 +
1.553 +},{"./lib/PriorityQueue":6,"./lib/Set":7,"./lib/version":9}],6:[function(require,module,exports){
1.554 +module.exports = PriorityQueue;
1.555 +
1.556 +/**
1.557 + * A min-priority queue data structure. This algorithm is derived from Cormen,
1.558 + * et al., "Introduction to Algorithms". The basic idea of a min-priority
1.559 + * queue is that you can efficiently (in O(1) time) get the smallest key in
1.560 + * the queue. Adding and removing elements takes O(log n) time. A key can
1.561 + * have its priority decreased in O(log n) time.
1.562 + */
1.563 +function PriorityQueue() {
1.564 + this._arr = [];
1.565 + this._keyIndices = {};
1.566 +}
1.567 +
1.568 +/**
1.569 + * Returns the number of elements in the queue. Takes `O(1)` time.
1.570 + */
1.571 +PriorityQueue.prototype.size = function() {
1.572 + return this._arr.length;
1.573 +};
1.574 +
1.575 +/**
1.576 + * Returns the keys that are in the queue. Takes `O(n)` time.
1.577 + */
1.578 +PriorityQueue.prototype.keys = function() {
1.579 + return this._arr.map(function(x) { return x.key; });
1.580 +};
1.581 +
1.582 +/**
1.583 + * Returns `true` if **key** is in the queue and `false` if not.
1.584 + */
1.585 +PriorityQueue.prototype.has = function(key) {
1.586 + return key in this._keyIndices;
1.587 +};
1.588 +
1.589 +/**
1.590 + * Returns the priority for **key**. If **key** is not present in the queue
1.591 + * then this function returns `undefined`. Takes `O(1)` time.
1.592 + *
1.593 + * @param {Object} key
1.594 + */
1.595 +PriorityQueue.prototype.priority = function(key) {
1.596 + var index = this._keyIndices[key];
1.597 + if (index !== undefined) {
1.598 + return this._arr[index].priority;
1.599 + }
1.600 +};
1.601 +
1.602 +/**
1.603 + * Returns the key for the minimum element in this queue. If the queue is
1.604 + * empty this function throws an Error. Takes `O(1)` time.
1.605 + */
1.606 +PriorityQueue.prototype.min = function() {
1.607 + if (this.size() === 0) {
1.608 + throw new Error("Queue underflow");
1.609 + }
1.610 + return this._arr[0].key;
1.611 +};
1.612 +
1.613 +/**
1.614 + * Inserts a new key into the priority queue. If the key already exists in
1.615 + * the queue this function returns `false`; otherwise it will return `true`.
1.616 + * Takes `O(n)` time.
1.617 + *
1.618 + * @param {Object} key the key to add
1.619 + * @param {Number} priority the initial priority for the key
1.620 + */
1.621 +PriorityQueue.prototype.add = function(key, priority) {
1.622 + var keyIndices = this._keyIndices;
1.623 + if (!(key in keyIndices)) {
1.624 + var arr = this._arr;
1.625 + var index = arr.length;
1.626 + keyIndices[key] = index;
1.627 + arr.push({key: key, priority: priority});
1.628 + this._decrease(index);
1.629 + return true;
1.630 + }
1.631 + return false;
1.632 +};
1.633 +
1.634 +/**
1.635 + * Removes and returns the smallest key in the queue. Takes `O(log n)` time.
1.636 + */
1.637 +PriorityQueue.prototype.removeMin = function() {
1.638 + this._swap(0, this._arr.length - 1);
1.639 + var min = this._arr.pop();
1.640 + delete this._keyIndices[min.key];
1.641 + this._heapify(0);
1.642 + return min.key;
1.643 +};
1.644 +
1.645 +/**
1.646 + * Decreases the priority for **key** to **priority**. If the new priority is
1.647 + * greater than the previous priority, this function will throw an Error.
1.648 + *
1.649 + * @param {Object} key the key for which to raise priority
1.650 + * @param {Number} priority the new priority for the key
1.651 + */
1.652 +PriorityQueue.prototype.decrease = function(key, priority) {
1.653 + var index = this._keyIndices[key];
1.654 + if (priority > this._arr[index].priority) {
1.655 + throw new Error("New priority is greater than current priority. " +
1.656 + "Key: " + key + " Old: " + this._arr[index].priority + " New: " + priority);
1.657 + }
1.658 + this._arr[index].priority = priority;
1.659 + this._decrease(index);
1.660 +};
1.661 +
1.662 +PriorityQueue.prototype._heapify = function(i) {
1.663 + var arr = this._arr;
1.664 + var l = 2 * i,
1.665 + r = l + 1,
1.666 + largest = i;
1.667 + if (l < arr.length) {
1.668 + largest = arr[l].priority < arr[largest].priority ? l : largest;
1.669 + if (r < arr.length) {
1.670 + largest = arr[r].priority < arr[largest].priority ? r : largest;
1.671 + }
1.672 + if (largest !== i) {
1.673 + this._swap(i, largest);
1.674 + this._heapify(largest);
1.675 + }
1.676 + }
1.677 +};
1.678 +
1.679 +PriorityQueue.prototype._decrease = function(index) {
1.680 + var arr = this._arr;
1.681 + var priority = arr[index].priority;
1.682 + var parent;
1.683 + while (index !== 0) {
1.684 + parent = index >> 1;
1.685 + if (arr[parent].priority < priority) {
1.686 + break;
1.687 + }
1.688 + this._swap(index, parent);
1.689 + index = parent;
1.690 + }
1.691 +};
1.692 +
1.693 +PriorityQueue.prototype._swap = function(i, j) {
1.694 + var arr = this._arr;
1.695 + var keyIndices = this._keyIndices;
1.696 + var origArrI = arr[i];
1.697 + var origArrJ = arr[j];
1.698 + arr[i] = origArrJ;
1.699 + arr[j] = origArrI;
1.700 + keyIndices[origArrJ.key] = i;
1.701 + keyIndices[origArrI.key] = j;
1.702 +};
1.703 +
1.704 +},{}],7:[function(require,module,exports){
1.705 +var util = require('./util');
1.706 +
1.707 +module.exports = Set;
1.708 +
1.709 +/**
1.710 + * Constructs a new Set with an optional set of `initialKeys`.
1.711 + *
1.712 + * It is important to note that keys are coerced to String for most purposes
1.713 + * with this object, similar to the behavior of JavaScript's Object. For
1.714 + * example, the following will add only one key:
1.715 + *
1.716 + * var s = new Set();
1.717 + * s.add(1);
1.718 + * s.add("1");
1.719 + *
1.720 + * However, the type of the key is preserved internally so that `keys` returns
1.721 + * the original key set uncoerced. For the above example, `keys` would return
1.722 + * `[1]`.
1.723 + */
1.724 +function Set(initialKeys) {
1.725 + this._size = 0;
1.726 + this._keys = {};
1.727 +
1.728 + if (initialKeys) {
1.729 + for (var i = 0, il = initialKeys.length; i < il; ++i) {
1.730 + this.add(initialKeys[i]);
1.731 + }
1.732 + }
1.733 +}
1.734 +
1.735 +/**
1.736 + * Returns a new Set that represents the set intersection of the array of given
1.737 + * sets.
1.738 + */
1.739 +Set.intersect = function(sets) {
1.740 + if (sets.length === 0) {
1.741 + return new Set();
1.742 + }
1.743 +
1.744 + var result = new Set(!util.isArray(sets[0]) ? sets[0].keys() : sets[0]);
1.745 + for (var i = 1, il = sets.length; i < il; ++i) {
1.746 + var resultKeys = result.keys(),
1.747 + other = !util.isArray(sets[i]) ? sets[i] : new Set(sets[i]);
1.748 + for (var j = 0, jl = resultKeys.length; j < jl; ++j) {
1.749 + var key = resultKeys[j];
1.750 + if (!other.has(key)) {
1.751 + result.remove(key);
1.752 + }
1.753 + }
1.754 + }
1.755 +
1.756 + return result;
1.757 +};
1.758 +
1.759 +/**
1.760 + * Returns a new Set that represents the set union of the array of given sets.
1.761 + */
1.762 +Set.union = function(sets) {
1.763 + var totalElems = util.reduce(sets, function(lhs, rhs) {
1.764 + return lhs + (rhs.size ? rhs.size() : rhs.length);
1.765 + }, 0);
1.766 + var arr = new Array(totalElems);
1.767 +
1.768 + var k = 0;
1.769 + for (var i = 0, il = sets.length; i < il; ++i) {
1.770 + var cur = sets[i],
1.771 + keys = !util.isArray(cur) ? cur.keys() : cur;
1.772 + for (var j = 0, jl = keys.length; j < jl; ++j) {
1.773 + arr[k++] = keys[j];
1.774 + }
1.775 + }
1.776 +
1.777 + return new Set(arr);
1.778 +};
1.779 +
1.780 +/**
1.781 + * Returns the size of this set in `O(1)` time.
1.782 + */
1.783 +Set.prototype.size = function() {
1.784 + return this._size;
1.785 +};
1.786 +
1.787 +/**
1.788 + * Returns the keys in this set. Takes `O(n)` time.
1.789 + */
1.790 +Set.prototype.keys = function() {
1.791 + return values(this._keys);
1.792 +};
1.793 +
1.794 +/**
1.795 + * Tests if a key is present in this Set. Returns `true` if it is and `false`
1.796 + * if not. Takes `O(1)` time.
1.797 + */
1.798 +Set.prototype.has = function(key) {
1.799 + return key in this._keys;
1.800 +};
1.801 +
1.802 +/**
1.803 + * Adds a new key to this Set if it is not already present. Returns `true` if
1.804 + * the key was added and `false` if it was already present. Takes `O(1)` time.
1.805 + */
1.806 +Set.prototype.add = function(key) {
1.807 + if (!(key in this._keys)) {
1.808 + this._keys[key] = key;
1.809 + ++this._size;
1.810 + return true;
1.811 + }
1.812 + return false;
1.813 +};
1.814 +
1.815 +/**
1.816 + * Removes a key from this Set. If the key was removed this function returns
1.817 + * `true`. If not, it returns `false`. Takes `O(1)` time.
1.818 + */
1.819 +Set.prototype.remove = function(key) {
1.820 + if (key in this._keys) {
1.821 + delete this._keys[key];
1.822 + --this._size;
1.823 + return true;
1.824 + }
1.825 + return false;
1.826 +};
1.827 +
1.828 +/*
1.829 + * Returns an array of all values for properties of **o**.
1.830 + */
1.831 +function values(o) {
1.832 + var ks = Object.keys(o),
1.833 + len = ks.length,
1.834 + result = new Array(len),
1.835 + i;
1.836 + for (i = 0; i < len; ++i) {
1.837 + result[i] = o[ks[i]];
1.838 + }
1.839 + return result;
1.840 +}
1.841 +
1.842 +},{"./util":8}],8:[function(require,module,exports){
1.843 +/*
1.844 + * This polyfill comes from
1.845 + * https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/isArray
1.846 + */
1.847 +if(!Array.isArray) {
1.848 + exports.isArray = function (vArg) {
1.849 + return Object.prototype.toString.call(vArg) === '[object Array]';
1.850 + };
1.851 +} else {
1.852 + exports.isArray = Array.isArray;
1.853 +}
1.854 +
1.855 +/*
1.856 + * Slightly adapted polyfill from
1.857 + * https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/Reduce
1.858 + */
1.859 +if ('function' !== typeof Array.prototype.reduce) {
1.860 + exports.reduce = function(array, callback, opt_initialValue) {
1.861 + 'use strict';
1.862 + if (null === array || 'undefined' === typeof array) {
1.863 + // At the moment all modern browsers, that support strict mode, have
1.864 + // native implementation of Array.prototype.reduce. For instance, IE8
1.865 + // does not support strict mode, so this check is actually useless.
1.866 + throw new TypeError(
1.867 + 'Array.prototype.reduce called on null or undefined');
1.868 + }
1.869 + if ('function' !== typeof callback) {
1.870 + throw new TypeError(callback + ' is not a function');
1.871 + }
1.872 + var index, value,
1.873 + length = array.length >>> 0,
1.874 + isValueSet = false;
1.875 + if (1 < arguments.length) {
1.876 + value = opt_initialValue;
1.877 + isValueSet = true;
1.878 + }
1.879 + for (index = 0; length > index; ++index) {
1.880 + if (array.hasOwnProperty(index)) {
1.881 + if (isValueSet) {
1.882 + value = callback(value, array[index], index, array);
1.883 + }
1.884 + else {
1.885 + value = array[index];
1.886 + isValueSet = true;
1.887 + }
1.888 + }
1.889 + }
1.890 + if (!isValueSet) {
1.891 + throw new TypeError('Reduce of empty array with no initial value');
1.892 + }
1.893 + return value;
1.894 + };
1.895 +} else {
1.896 + exports.reduce = function(array, callback, opt_initialValue) {
1.897 + return array.reduce(callback, opt_initialValue);
1.898 + };
1.899 +}
1.900 +
1.901 +},{}],9:[function(require,module,exports){
1.902 +module.exports = '1.1.3';
1.903 +
1.904 +},{}],10:[function(require,module,exports){
1.905 +require("./d3");
1.906 +module.exports = d3;
1.907 +(function () { delete this.d3; })(); // unset global
1.908 +
1.909 +},{}],11:[function(require,module,exports){
1.910 +/*
1.911 +Copyright (c) 2012-2013 Chris Pettitt
1.912 +
1.913 +Permission is hereby granted, free of charge, to any person obtaining a copy
1.914 +of this software and associated documentation files (the "Software"), to deal
1.915 +in the Software without restriction, including without limitation the rights
1.916 +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
1.917 +copies of the Software, and to permit persons to whom the Software is
1.918 +furnished to do so, subject to the following conditions:
1.919 +
1.920 +The above copyright notice and this permission notice shall be included in
1.921 +all copies or substantial portions of the Software.
1.922 +
1.923 +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
1.924 +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
1.925 +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
1.926 +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
1.927 +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
1.928 +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
1.929 +THE SOFTWARE.
1.930 +*/
1.931 +exports.Digraph = require("graphlib").Digraph;
1.932 +exports.Graph = require("graphlib").Graph;
1.933 +exports.layout = require("./lib/layout");
1.934 +exports.version = require("./lib/version");
1.935 +
1.936 +},{"./lib/layout":12,"./lib/version":27,"graphlib":28}],12:[function(require,module,exports){
1.937 +var util = require('./util'),
1.938 + rank = require('./rank'),
1.939 + order = require('./order'),
1.940 + CGraph = require('graphlib').CGraph,
1.941 + CDigraph = require('graphlib').CDigraph;
1.942 +
1.943 +module.exports = function() {
1.944 + // External configuration
1.945 + var config = {
1.946 + // How much debug information to include?
1.947 + debugLevel: 0,
1.948 + // Max number of sweeps to perform in order phase
1.949 + orderMaxSweeps: order.DEFAULT_MAX_SWEEPS,
1.950 + // Use network simplex algorithm in ranking
1.951 + rankSimplex: false,
1.952 + // Rank direction. Valid values are (TB, LR)
1.953 + rankDir: 'TB'
1.954 + };
1.955 +
1.956 + // Phase functions
1.957 + var position = require('./position')();
1.958 +
1.959 + // This layout object
1.960 + var self = {};
1.961 +
1.962 + self.orderIters = util.propertyAccessor(self, config, 'orderMaxSweeps');
1.963 +
1.964 + self.rankSimplex = util.propertyAccessor(self, config, 'rankSimplex');
1.965 +
1.966 + self.nodeSep = delegateProperty(position.nodeSep);
1.967 + self.edgeSep = delegateProperty(position.edgeSep);
1.968 + self.universalSep = delegateProperty(position.universalSep);
1.969 + self.rankSep = delegateProperty(position.rankSep);
1.970 + self.rankDir = util.propertyAccessor(self, config, 'rankDir');
1.971 + self.debugAlignment = delegateProperty(position.debugAlignment);
1.972 +
1.973 + self.debugLevel = util.propertyAccessor(self, config, 'debugLevel', function(x) {
1.974 + util.log.level = x;
1.975 + position.debugLevel(x);
1.976 + });
1.977 +
1.978 + self.run = util.time('Total layout', run);
1.979 +
1.980 + self._normalize = normalize;
1.981 +
1.982 + return self;
1.983 +
1.984 + /*
1.985 + * Constructs an adjacency graph using the nodes and edges specified through
1.986 + * config. For each node and edge we add a property `dagre` that contains an
1.987 + * object that will hold intermediate and final layout information. Some of
1.988 + * the contents include:
1.989 + *
1.990 + * 1) A generated ID that uniquely identifies the object.
1.991 + * 2) Dimension information for nodes (copied from the source node).
1.992 + * 3) Optional dimension information for edges.
1.993 + *
1.994 + * After the adjacency graph is constructed the code no longer needs to use
1.995 + * the original nodes and edges passed in via config.
1.996 + */
1.997 + function initLayoutGraph(inputGraph) {
1.998 + var g = new CDigraph();
1.999 +
1.1000 + inputGraph.eachNode(function(u, value) {
1.1001 + if (value === undefined) value = {};
1.1002 + g.addNode(u, {
1.1003 + width: value.width,
1.1004 + height: value.height
1.1005 + });
1.1006 + if (value.hasOwnProperty('rank')) {
1.1007 + g.node(u).prefRank = value.rank;
1.1008 + }
1.1009 + });
1.1010 +
1.1011 + // Set up subgraphs
1.1012 + if (inputGraph.parent) {
1.1013 + inputGraph.nodes().forEach(function(u) {
1.1014 + g.parent(u, inputGraph.parent(u));
1.1015 + });
1.1016 + }
1.1017 +
1.1018 + inputGraph.eachEdge(function(e, u, v, value) {
1.1019 + if (value === undefined) value = {};
1.1020 + var newValue = {
1.1021 + e: e,
1.1022 + minLen: value.minLen || 1,
1.1023 + width: value.width || 0,
1.1024 + height: value.height || 0,
1.1025 + points: []
1.1026 + };
1.1027 +
1.1028 + g.addEdge(null, u, v, newValue);
1.1029 + });
1.1030 +
1.1031 + // Initial graph attributes
1.1032 + var graphValue = inputGraph.graph() || {};
1.1033 + g.graph({
1.1034 + rankDir: graphValue.rankDir || config.rankDir,
1.1035 + orderRestarts: graphValue.orderRestarts
1.1036 + });
1.1037 +
1.1038 + return g;
1.1039 + }
1.1040 +
1.1041 + function run(inputGraph) {
1.1042 + var rankSep = self.rankSep();
1.1043 + var g;
1.1044 + try {
1.1045 + // Build internal graph
1.1046 + g = util.time('initLayoutGraph', initLayoutGraph)(inputGraph);
1.1047 +
1.1048 + if (g.order() === 0) {
1.1049 + return g;
1.1050 + }
1.1051 +
1.1052 + // Make space for edge labels
1.1053 + g.eachEdge(function(e, s, t, a) {
1.1054 + a.minLen *= 2;
1.1055 + });
1.1056 + self.rankSep(rankSep / 2);
1.1057 +
1.1058 + // Determine the rank for each node. Nodes with a lower rank will appear
1.1059 + // above nodes of higher rank.
1.1060 + util.time('rank.run', rank.run)(g, config.rankSimplex);
1.1061 +
1.1062 + // Normalize the graph by ensuring that every edge is proper (each edge has
1.1063 + // a length of 1). We achieve this by adding dummy nodes to long edges,
1.1064 + // thus shortening them.
1.1065 + util.time('normalize', normalize)(g);
1.1066 +
1.1067 + // Order the nodes so that edge crossings are minimized.
1.1068 + util.time('order', order)(g, config.orderMaxSweeps);
1.1069 +
1.1070 + // Find the x and y coordinates for every node in the graph.
1.1071 + util.time('position', position.run)(g);
1.1072 +
1.1073 + // De-normalize the graph by removing dummy nodes and augmenting the
1.1074 + // original long edges with coordinate information.
1.1075 + util.time('undoNormalize', undoNormalize)(g);
1.1076 +
1.1077 + // Reverses points for edges that are in a reversed state.
1.1078 + util.time('fixupEdgePoints', fixupEdgePoints)(g);
1.1079 +
1.1080 + // Restore delete edges and reverse edges that were reversed in the rank
1.1081 + // phase.
1.1082 + util.time('rank.restoreEdges', rank.restoreEdges)(g);
1.1083 +
1.1084 + // Construct final result graph and return it
1.1085 + return util.time('createFinalGraph', createFinalGraph)(g, inputGraph.isDirected());
1.1086 + } finally {
1.1087 + self.rankSep(rankSep);
1.1088 + }
1.1089 + }
1.1090 +
1.1091 + /*
1.1092 + * This function is responsible for 'normalizing' the graph. The process of
1.1093 + * normalization ensures that no edge in the graph has spans more than one
1.1094 + * rank. To do this it inserts dummy nodes as needed and links them by adding
1.1095 + * dummy edges. This function keeps enough information in the dummy nodes and
1.1096 + * edges to ensure that the original graph can be reconstructed later.
1.1097 + *
1.1098 + * This method assumes that the input graph is cycle free.
1.1099 + */
1.1100 + function normalize(g) {
1.1101 + var dummyCount = 0;
1.1102 + g.eachEdge(function(e, s, t, a) {
1.1103 + var sourceRank = g.node(s).rank;
1.1104 + var targetRank = g.node(t).rank;
1.1105 + if (sourceRank + 1 < targetRank) {
1.1106 + for (var u = s, rank = sourceRank + 1, i = 0; rank < targetRank; ++rank, ++i) {
1.1107 + var v = '_D' + (++dummyCount);
1.1108 + var node = {
1.1109 + width: a.width,
1.1110 + height: a.height,
1.1111 + edge: { id: e, source: s, target: t, attrs: a },
1.1112 + rank: rank,
1.1113 + dummy: true
1.1114 + };
1.1115 +
1.1116 + // If this node represents a bend then we will use it as a control
1.1117 + // point. For edges with 2 segments this will be the center dummy
1.1118 + // node. For edges with more than two segments, this will be the
1.1119 + // first and last dummy node.
1.1120 + if (i === 0) node.index = 0;
1.1121 + else if (rank + 1 === targetRank) node.index = 1;
1.1122 +
1.1123 + g.addNode(v, node);
1.1124 + g.addEdge(null, u, v, {});
1.1125 + u = v;
1.1126 + }
1.1127 + g.addEdge(null, u, t, {});
1.1128 + g.delEdge(e);
1.1129 + }
1.1130 + });
1.1131 + }
1.1132 +
1.1133 + /*
1.1134 + * Reconstructs the graph as it was before normalization. The positions of
1.1135 + * dummy nodes are used to build an array of points for the original 'long'
1.1136 + * edge. Dummy nodes and edges are removed.
1.1137 + */
1.1138 + function undoNormalize(g) {
1.1139 + g.eachNode(function(u, a) {
1.1140 + if (a.dummy) {
1.1141 + if ('index' in a) {
1.1142 + var edge = a.edge;
1.1143 + if (!g.hasEdge(edge.id)) {
1.1144 + g.addEdge(edge.id, edge.source, edge.target, edge.attrs);
1.1145 + }
1.1146 + var points = g.edge(edge.id).points;
1.1147 + points[a.index] = { x: a.x, y: a.y, ul: a.ul, ur: a.ur, dl: a.dl, dr: a.dr };
1.1148 + }
1.1149 + g.delNode(u);
1.1150 + }
1.1151 + });
1.1152 + }
1.1153 +
1.1154 + /*
1.1155 + * For each edge that was reversed during the `acyclic` step, reverse its
1.1156 + * array of points.
1.1157 + */
1.1158 + function fixupEdgePoints(g) {
1.1159 + g.eachEdge(function(e, s, t, a) { if (a.reversed) a.points.reverse(); });
1.1160 + }
1.1161 +
1.1162 + function createFinalGraph(g, isDirected) {
1.1163 + var out = isDirected ? new CDigraph() : new CGraph();
1.1164 + out.graph(g.graph());
1.1165 + g.eachNode(function(u, value) { out.addNode(u, value); });
1.1166 + g.eachNode(function(u) { out.parent(u, g.parent(u)); });
1.1167 + g.eachEdge(function(e, u, v, value) {
1.1168 + out.addEdge(value.e, u, v, value);
1.1169 + });
1.1170 +
1.1171 + // Attach bounding box information
1.1172 + var maxX = 0, maxY = 0;
1.1173 + g.eachNode(function(u, value) {
1.1174 + if (!g.children(u).length) {
1.1175 + maxX = Math.max(maxX, value.x + value.width / 2);
1.1176 + maxY = Math.max(maxY, value.y + value.height / 2);
1.1177 + }
1.1178 + });
1.1179 + g.eachEdge(function(e, u, v, value) {
1.1180 + var maxXPoints = Math.max.apply(Math, value.points.map(function(p) { return p.x; }));
1.1181 + var maxYPoints = Math.max.apply(Math, value.points.map(function(p) { return p.y; }));
1.1182 + maxX = Math.max(maxX, maxXPoints + value.width / 2);
1.1183 + maxY = Math.max(maxY, maxYPoints + value.height / 2);
1.1184 + });
1.1185 + out.graph().width = maxX;
1.1186 + out.graph().height = maxY;
1.1187 +
1.1188 + return out;
1.1189 + }
1.1190 +
1.1191 + /*
1.1192 + * Given a function, a new function is returned that invokes the given
1.1193 + * function. The return value from the function is always the `self` object.
1.1194 + */
1.1195 + function delegateProperty(f) {
1.1196 + return function() {
1.1197 + if (!arguments.length) return f();
1.1198 + f.apply(null, arguments);
1.1199 + return self;
1.1200 + };
1.1201 + }
1.1202 +};
1.1203 +
1.1204 +
1.1205 +},{"./order":13,"./position":18,"./rank":19,"./util":26,"graphlib":28}],13:[function(require,module,exports){
1.1206 +var util = require('./util'),
1.1207 + crossCount = require('./order/crossCount'),
1.1208 + initLayerGraphs = require('./order/initLayerGraphs'),
1.1209 + initOrder = require('./order/initOrder'),
1.1210 + sortLayer = require('./order/sortLayer');
1.1211 +
1.1212 +module.exports = order;
1.1213 +
1.1214 +// The maximum number of sweeps to perform before finishing the order phase.
1.1215 +var DEFAULT_MAX_SWEEPS = 24;
1.1216 +order.DEFAULT_MAX_SWEEPS = DEFAULT_MAX_SWEEPS;
1.1217 +
1.1218 +/*
1.1219 + * Runs the order phase with the specified `graph, `maxSweeps`, and
1.1220 + * `debugLevel`. If `maxSweeps` is not specified we use `DEFAULT_MAX_SWEEPS`.
1.1221 + * If `debugLevel` is not set we assume 0.
1.1222 + */
1.1223 +function order(g, maxSweeps) {
1.1224 + if (arguments.length < 2) {
1.1225 + maxSweeps = DEFAULT_MAX_SWEEPS;
1.1226 + }
1.1227 +
1.1228 + var restarts = g.graph().orderRestarts || 0;
1.1229 +
1.1230 + var layerGraphs = initLayerGraphs(g);
1.1231 + // TODO: remove this when we add back support for ordering clusters
1.1232 + layerGraphs.forEach(function(lg) {
1.1233 + lg = lg.filterNodes(function(u) { return !g.children(u).length; });
1.1234 + });
1.1235 +
1.1236 + var iters = 0,
1.1237 + currentBestCC,
1.1238 + allTimeBestCC = Number.MAX_VALUE,
1.1239 + allTimeBest = {};
1.1240 +
1.1241 + function saveAllTimeBest() {
1.1242 + g.eachNode(function(u, value) { allTimeBest[u] = value.order; });
1.1243 + }
1.1244 +
1.1245 + for (var j = 0; j < Number(restarts) + 1 && allTimeBestCC !== 0; ++j) {
1.1246 + currentBestCC = Number.MAX_VALUE;
1.1247 + initOrder(g, restarts > 0);
1.1248 +
1.1249 + util.log(2, 'Order phase start cross count: ' + g.graph().orderInitCC);
1.1250 +
1.1251 + var i, lastBest, cc;
1.1252 + for (i = 0, lastBest = 0; lastBest < 4 && i < maxSweeps && currentBestCC > 0; ++i, ++lastBest, ++iters) {
1.1253 + sweep(g, layerGraphs, i);
1.1254 + cc = crossCount(g);
1.1255 + if (cc < currentBestCC) {
1.1256 + lastBest = 0;
1.1257 + currentBestCC = cc;
1.1258 + if (cc < allTimeBestCC) {
1.1259 + saveAllTimeBest();
1.1260 + allTimeBestCC = cc;
1.1261 + }
1.1262 + }
1.1263 + util.log(3, 'Order phase start ' + j + ' iter ' + i + ' cross count: ' + cc);
1.1264 + }
1.1265 + }
1.1266 +
1.1267 + Object.keys(allTimeBest).forEach(function(u) {
1.1268 + if (!g.children || !g.children(u).length) {
1.1269 + g.node(u).order = allTimeBest[u];
1.1270 + }
1.1271 + });
1.1272 + g.graph().orderCC = allTimeBestCC;
1.1273 +
1.1274 + util.log(2, 'Order iterations: ' + iters);
1.1275 + util.log(2, 'Order phase best cross count: ' + g.graph().orderCC);
1.1276 +}
1.1277 +
1.1278 +function predecessorWeights(g, nodes) {
1.1279 + var weights = {};
1.1280 + nodes.forEach(function(u) {
1.1281 + weights[u] = g.inEdges(u).map(function(e) {
1.1282 + return g.node(g.source(e)).order;
1.1283 + });
1.1284 + });
1.1285 + return weights;
1.1286 +}
1.1287 +
1.1288 +function successorWeights(g, nodes) {
1.1289 + var weights = {};
1.1290 + nodes.forEach(function(u) {
1.1291 + weights[u] = g.outEdges(u).map(function(e) {
1.1292 + return g.node(g.target(e)).order;
1.1293 + });
1.1294 + });
1.1295 + return weights;
1.1296 +}
1.1297 +
1.1298 +function sweep(g, layerGraphs, iter) {
1.1299 + if (iter % 2 === 0) {
1.1300 + sweepDown(g, layerGraphs, iter);
1.1301 + } else {
1.1302 + sweepUp(g, layerGraphs, iter);
1.1303 + }
1.1304 +}
1.1305 +
1.1306 +function sweepDown(g, layerGraphs) {
1.1307 + var cg;
1.1308 + for (i = 1; i < layerGraphs.length; ++i) {
1.1309 + cg = sortLayer(layerGraphs[i], cg, predecessorWeights(g, layerGraphs[i].nodes()));
1.1310 + }
1.1311 +}
1.1312 +
1.1313 +function sweepUp(g, layerGraphs) {
1.1314 + var cg;
1.1315 + for (i = layerGraphs.length - 2; i >= 0; --i) {
1.1316 + sortLayer(layerGraphs[i], cg, successorWeights(g, layerGraphs[i].nodes()));
1.1317 + }
1.1318 +}
1.1319 +
1.1320 +},{"./order/crossCount":14,"./order/initLayerGraphs":15,"./order/initOrder":16,"./order/sortLayer":17,"./util":26}],14:[function(require,module,exports){
1.1321 +var util = require('../util');
1.1322 +
1.1323 +module.exports = crossCount;
1.1324 +
1.1325 +/*
1.1326 + * Returns the cross count for the given graph.
1.1327 + */
1.1328 +function crossCount(g) {
1.1329 + var cc = 0;
1.1330 + var ordering = util.ordering(g);
1.1331 + for (var i = 1; i < ordering.length; ++i) {
1.1332 + cc += twoLayerCrossCount(g, ordering[i-1], ordering[i]);
1.1333 + }
1.1334 + return cc;
1.1335 +}
1.1336 +
1.1337 +/*
1.1338 + * This function searches through a ranked and ordered graph and counts the
1.1339 + * number of edges that cross. This algorithm is derived from:
1.1340 + *
1.1341 + * W. Barth et al., Bilayer Cross Counting, JGAA, 8(2) 179–194 (2004)
1.1342 + */
1.1343 +function twoLayerCrossCount(g, layer1, layer2) {
1.1344 + var indices = [];
1.1345 + layer1.forEach(function(u) {
1.1346 + var nodeIndices = [];
1.1347 + g.outEdges(u).forEach(function(e) { nodeIndices.push(g.node(g.target(e)).order); });
1.1348 + nodeIndices.sort(function(x, y) { return x - y; });
1.1349 + indices = indices.concat(nodeIndices);
1.1350 + });
1.1351 +
1.1352 + var firstIndex = 1;
1.1353 + while (firstIndex < layer2.length) firstIndex <<= 1;
1.1354 +
1.1355 + var treeSize = 2 * firstIndex - 1;
1.1356 + firstIndex -= 1;
1.1357 +
1.1358 + var tree = [];
1.1359 + for (var i = 0; i < treeSize; ++i) { tree[i] = 0; }
1.1360 +
1.1361 + var cc = 0;
1.1362 + indices.forEach(function(i) {
1.1363 + var treeIndex = i + firstIndex;
1.1364 + ++tree[treeIndex];
1.1365 + while (treeIndex > 0) {
1.1366 + if (treeIndex % 2) {
1.1367 + cc += tree[treeIndex + 1];
1.1368 + }
1.1369 + treeIndex = (treeIndex - 1) >> 1;
1.1370 + ++tree[treeIndex];
1.1371 + }
1.1372 + });
1.1373 +
1.1374 + return cc;
1.1375 +}
1.1376 +
1.1377 +},{"../util":26}],15:[function(require,module,exports){
1.1378 +var nodesFromList = require('graphlib').filter.nodesFromList,
1.1379 + /* jshint -W079 */
1.1380 + Set = require('cp-data').Set;
1.1381 +
1.1382 +module.exports = initLayerGraphs;
1.1383 +
1.1384 +/*
1.1385 + * This function takes a compound layered graph, g, and produces an array of
1.1386 + * layer graphs. Each entry in the array represents a subgraph of nodes
1.1387 + * relevant for performing crossing reduction on that layer.
1.1388 + */
1.1389 +function initLayerGraphs(g) {
1.1390 + var ranks = [];
1.1391 +
1.1392 + function dfs(u) {
1.1393 + if (u === null) {
1.1394 + g.children(u).forEach(function(v) { dfs(v); });
1.1395 + return;
1.1396 + }
1.1397 +
1.1398 + var value = g.node(u);
1.1399 + value.minRank = ('rank' in value) ? value.rank : Number.MAX_VALUE;
1.1400 + value.maxRank = ('rank' in value) ? value.rank : Number.MIN_VALUE;
1.1401 + var uRanks = new Set();
1.1402 + g.children(u).forEach(function(v) {
1.1403 + var rs = dfs(v);
1.1404 + uRanks = Set.union([uRanks, rs]);
1.1405 + value.minRank = Math.min(value.minRank, g.node(v).minRank);
1.1406 + value.maxRank = Math.max(value.maxRank, g.node(v).maxRank);
1.1407 + });
1.1408 +
1.1409 + if ('rank' in value) uRanks.add(value.rank);
1.1410 +
1.1411 + uRanks.keys().forEach(function(r) {
1.1412 + if (!(r in ranks)) ranks[r] = [];
1.1413 + ranks[r].push(u);
1.1414 + });
1.1415 +
1.1416 + return uRanks;
1.1417 + }
1.1418 + dfs(null);
1.1419 +
1.1420 + var layerGraphs = [];
1.1421 + ranks.forEach(function(us, rank) {
1.1422 + layerGraphs[rank] = g.filterNodes(nodesFromList(us));
1.1423 + });
1.1424 +
1.1425 + return layerGraphs;
1.1426 +}
1.1427 +
1.1428 +},{"cp-data":5,"graphlib":28}],16:[function(require,module,exports){
1.1429 +var crossCount = require('./crossCount'),
1.1430 + util = require('../util');
1.1431 +
1.1432 +module.exports = initOrder;
1.1433 +
1.1434 +/*
1.1435 + * Given a graph with a set of layered nodes (i.e. nodes that have a `rank`
1.1436 + * attribute) this function attaches an `order` attribute that uniquely
1.1437 + * arranges each node of each rank. If no constraint graph is provided the
1.1438 + * order of the nodes in each rank is entirely arbitrary.
1.1439 + */
1.1440 +function initOrder(g, random) {
1.1441 + var layers = [];
1.1442 +
1.1443 + g.eachNode(function(u, value) {
1.1444 + var layer = layers[value.rank];
1.1445 + if (g.children && g.children(u).length > 0) return;
1.1446 + if (!layer) {
1.1447 + layer = layers[value.rank] = [];
1.1448 + }
1.1449 + layer.push(u);
1.1450 + });
1.1451 +
1.1452 + layers.forEach(function(layer) {
1.1453 + if (random) {
1.1454 + util.shuffle(layer);
1.1455 + }
1.1456 + layer.forEach(function(u, i) {
1.1457 + g.node(u).order = i;
1.1458 + });
1.1459 + });
1.1460 +
1.1461 + var cc = crossCount(g);
1.1462 + g.graph().orderInitCC = cc;
1.1463 + g.graph().orderCC = Number.MAX_VALUE;
1.1464 +}
1.1465 +
1.1466 +},{"../util":26,"./crossCount":14}],17:[function(require,module,exports){
1.1467 +var util = require('../util');
1.1468 +/*
1.1469 + Digraph = require('graphlib').Digraph,
1.1470 + topsort = require('graphlib').alg.topsort,
1.1471 + nodesFromList = require('graphlib').filter.nodesFromList;
1.1472 +*/
1.1473 +
1.1474 +module.exports = sortLayer;
1.1475 +
1.1476 +/*
1.1477 +function sortLayer(g, cg, weights) {
1.1478 + var result = sortLayerSubgraph(g, null, cg, weights);
1.1479 + result.list.forEach(function(u, i) {
1.1480 + g.node(u).order = i;
1.1481 + });
1.1482 + return result.constraintGraph;
1.1483 +}
1.1484 +*/
1.1485 +
1.1486 +function sortLayer(g, cg, weights) {
1.1487 + var ordering = [];
1.1488 + var bs = {};
1.1489 + g.eachNode(function(u, value) {
1.1490 + ordering[value.order] = u;
1.1491 + var ws = weights[u];
1.1492 + if (ws.length) {
1.1493 + bs[u] = util.sum(ws) / ws.length;
1.1494 + }
1.1495 + });
1.1496 +
1.1497 + var toSort = g.nodes().filter(function(u) { return bs[u] !== undefined; });
1.1498 + toSort.sort(function(x, y) {
1.1499 + return bs[x] - bs[y] || g.node(x).order - g.node(y).order;
1.1500 + });
1.1501 +
1.1502 + for (var i = 0, j = 0, jl = toSort.length; j < jl; ++i) {
1.1503 + if (bs[ordering[i]] !== undefined) {
1.1504 + g.node(toSort[j++]).order = i;
1.1505 + }
1.1506 + }
1.1507 +}
1.1508 +
1.1509 +// TOOD: re-enable constrained sorting once we have a strategy for handling
1.1510 +// undefined barycenters.
1.1511 +/*
1.1512 +function sortLayerSubgraph(g, sg, cg, weights) {
1.1513 + cg = cg ? cg.filterNodes(nodesFromList(g.children(sg))) : new Digraph();
1.1514 +
1.1515 + var nodeData = {};
1.1516 + g.children(sg).forEach(function(u) {
1.1517 + if (g.children(u).length) {
1.1518 + nodeData[u] = sortLayerSubgraph(g, u, cg, weights);
1.1519 + nodeData[u].firstSG = u;
1.1520 + nodeData[u].lastSG = u;
1.1521 + } else {
1.1522 + var ws = weights[u];
1.1523 + nodeData[u] = {
1.1524 + degree: ws.length,
1.1525 + barycenter: ws.length > 0 ? util.sum(ws) / ws.length : 0,
1.1526 + list: [u]
1.1527 + };
1.1528 + }
1.1529 + });
1.1530 +
1.1531 + resolveViolatedConstraints(g, cg, nodeData);
1.1532 +
1.1533 + var keys = Object.keys(nodeData);
1.1534 + keys.sort(function(x, y) {
1.1535 + return nodeData[x].barycenter - nodeData[y].barycenter;
1.1536 + });
1.1537 +
1.1538 + var result = keys.map(function(u) { return nodeData[u]; })
1.1539 + .reduce(function(lhs, rhs) { return mergeNodeData(g, lhs, rhs); });
1.1540 + return result;
1.1541 +}
1.1542 +
1.1543 +/*
1.1544 +function mergeNodeData(g, lhs, rhs) {
1.1545 + var cg = mergeDigraphs(lhs.constraintGraph, rhs.constraintGraph);
1.1546 +
1.1547 + if (lhs.lastSG !== undefined && rhs.firstSG !== undefined) {
1.1548 + if (cg === undefined) {
1.1549 + cg = new Digraph();
1.1550 + }
1.1551 + if (!cg.hasNode(lhs.lastSG)) { cg.addNode(lhs.lastSG); }
1.1552 + cg.addNode(rhs.firstSG);
1.1553 + cg.addEdge(null, lhs.lastSG, rhs.firstSG);
1.1554 + }
1.1555 +
1.1556 + return {
1.1557 + degree: lhs.degree + rhs.degree,
1.1558 + barycenter: (lhs.barycenter * lhs.degree + rhs.barycenter * rhs.degree) /
1.1559 + (lhs.degree + rhs.degree),
1.1560 + list: lhs.list.concat(rhs.list),
1.1561 + firstSG: lhs.firstSG !== undefined ? lhs.firstSG : rhs.firstSG,
1.1562 + lastSG: rhs.lastSG !== undefined ? rhs.lastSG : lhs.lastSG,
1.1563 + constraintGraph: cg
1.1564 + };
1.1565 +}
1.1566 +
1.1567 +function mergeDigraphs(lhs, rhs) {
1.1568 + if (lhs === undefined) return rhs;
1.1569 + if (rhs === undefined) return lhs;
1.1570 +
1.1571 + lhs = lhs.copy();
1.1572 + rhs.nodes().forEach(function(u) { lhs.addNode(u); });
1.1573 + rhs.edges().forEach(function(e, u, v) { lhs.addEdge(null, u, v); });
1.1574 + return lhs;
1.1575 +}
1.1576 +
1.1577 +function resolveViolatedConstraints(g, cg, nodeData) {
1.1578 + // Removes nodes `u` and `v` from `cg` and makes any edges incident on them
1.1579 + // incident on `w` instead.
1.1580 + function collapseNodes(u, v, w) {
1.1581 + // TODO original paper removes self loops, but it is not obvious when this would happen
1.1582 + cg.inEdges(u).forEach(function(e) {
1.1583 + cg.delEdge(e);
1.1584 + cg.addEdge(null, cg.source(e), w);
1.1585 + });
1.1586 +
1.1587 + cg.outEdges(v).forEach(function(e) {
1.1588 + cg.delEdge(e);
1.1589 + cg.addEdge(null, w, cg.target(e));
1.1590 + });
1.1591 +
1.1592 + cg.delNode(u);
1.1593 + cg.delNode(v);
1.1594 + }
1.1595 +
1.1596 + var violated;
1.1597 + while ((violated = findViolatedConstraint(cg, nodeData)) !== undefined) {
1.1598 + var source = cg.source(violated),
1.1599 + target = cg.target(violated);
1.1600 +
1.1601 + var v;
1.1602 + while ((v = cg.addNode(null)) && g.hasNode(v)) {
1.1603 + cg.delNode(v);
1.1604 + }
1.1605 +
1.1606 + // Collapse barycenter and list
1.1607 + nodeData[v] = mergeNodeData(g, nodeData[source], nodeData[target]);
1.1608 + delete nodeData[source];
1.1609 + delete nodeData[target];
1.1610 +
1.1611 + collapseNodes(source, target, v);
1.1612 + if (cg.incidentEdges(v).length === 0) { cg.delNode(v); }
1.1613 + }
1.1614 +}
1.1615 +
1.1616 +function findViolatedConstraint(cg, nodeData) {
1.1617 + var us = topsort(cg);
1.1618 + for (var i = 0; i < us.length; ++i) {
1.1619 + var u = us[i];
1.1620 + var inEdges = cg.inEdges(u);
1.1621 + for (var j = 0; j < inEdges.length; ++j) {
1.1622 + var e = inEdges[j];
1.1623 + if (nodeData[cg.source(e)].barycenter >= nodeData[u].barycenter) {
1.1624 + return e;
1.1625 + }
1.1626 + }
1.1627 + }
1.1628 +}
1.1629 +*/
1.1630 +
1.1631 +},{"../util":26}],18:[function(require,module,exports){
1.1632 +var util = require('./util');
1.1633 +
1.1634 +/*
1.1635 + * The algorithms here are based on Brandes and Köpf, "Fast and Simple
1.1636 + * Horizontal Coordinate Assignment".
1.1637 + */
1.1638 +module.exports = function() {
1.1639 + // External configuration
1.1640 + var config = {
1.1641 + nodeSep: 50,
1.1642 + edgeSep: 10,
1.1643 + universalSep: null,
1.1644 + rankSep: 30
1.1645 + };
1.1646 +
1.1647 + var self = {};
1.1648 +
1.1649 + self.nodeSep = util.propertyAccessor(self, config, 'nodeSep');
1.1650 + self.edgeSep = util.propertyAccessor(self, config, 'edgeSep');
1.1651 + // If not null this separation value is used for all nodes and edges
1.1652 + // regardless of their widths. `nodeSep` and `edgeSep` are ignored with this
1.1653 + // option.
1.1654 + self.universalSep = util.propertyAccessor(self, config, 'universalSep');
1.1655 + self.rankSep = util.propertyAccessor(self, config, 'rankSep');
1.1656 + self.debugLevel = util.propertyAccessor(self, config, 'debugLevel');
1.1657 +
1.1658 + self.run = run;
1.1659 +
1.1660 + return self;
1.1661 +
1.1662 + function run(g) {
1.1663 + g = g.filterNodes(util.filterNonSubgraphs(g));
1.1664 +
1.1665 + var layering = util.ordering(g);
1.1666 +
1.1667 + var conflicts = findConflicts(g, layering);
1.1668 +
1.1669 + var xss = {};
1.1670 + ['u', 'd'].forEach(function(vertDir) {
1.1671 + if (vertDir === 'd') layering.reverse();
1.1672 +
1.1673 + ['l', 'r'].forEach(function(horizDir) {
1.1674 + if (horizDir === 'r') reverseInnerOrder(layering);
1.1675 +
1.1676 + var dir = vertDir + horizDir;
1.1677 + var align = verticalAlignment(g, layering, conflicts, vertDir === 'u' ? 'predecessors' : 'successors');
1.1678 + xss[dir]= horizontalCompaction(g, layering, align.pos, align.root, align.align);
1.1679 +
1.1680 + if (config.debugLevel >= 3)
1.1681 + debugPositioning(vertDir + horizDir, g, layering, xss[dir]);
1.1682 +
1.1683 + if (horizDir === 'r') flipHorizontally(xss[dir]);
1.1684 +
1.1685 + if (horizDir === 'r') reverseInnerOrder(layering);
1.1686 + });
1.1687 +
1.1688 + if (vertDir === 'd') layering.reverse();
1.1689 + });
1.1690 +
1.1691 + balance(g, layering, xss);
1.1692 +
1.1693 + g.eachNode(function(v) {
1.1694 + var xs = [];
1.1695 + for (var alignment in xss) {
1.1696 + var alignmentX = xss[alignment][v];
1.1697 + posXDebug(alignment, g, v, alignmentX);
1.1698 + xs.push(alignmentX);
1.1699 + }
1.1700 + xs.sort(function(x, y) { return x - y; });
1.1701 + posX(g, v, (xs[1] + xs[2]) / 2);
1.1702 + });
1.1703 +
1.1704 + // Align y coordinates with ranks
1.1705 + var y = 0, reverseY = g.graph().rankDir === 'BT' || g.graph().rankDir === 'RL';
1.1706 + layering.forEach(function(layer) {
1.1707 + var maxHeight = util.max(layer.map(function(u) { return height(g, u); }));
1.1708 + y += maxHeight / 2;
1.1709 + layer.forEach(function(u) {
1.1710 + posY(g, u, reverseY ? -y : y);
1.1711 + });
1.1712 + y += maxHeight / 2 + config.rankSep;
1.1713 + });
1.1714 +
1.1715 + // Translate layout so that top left corner of bounding rectangle has
1.1716 + // coordinate (0, 0).
1.1717 + var minX = util.min(g.nodes().map(function(u) { return posX(g, u) - width(g, u) / 2; }));
1.1718 + var minY = util.min(g.nodes().map(function(u) { return posY(g, u) - height(g, u) / 2; }));
1.1719 + g.eachNode(function(u) {
1.1720 + posX(g, u, posX(g, u) - minX);
1.1721 + posY(g, u, posY(g, u) - minY);
1.1722 + });
1.1723 + }
1.1724 +
1.1725 + /*
1.1726 + * Generate an ID that can be used to represent any undirected edge that is
1.1727 + * incident on `u` and `v`.
1.1728 + */
1.1729 + function undirEdgeId(u, v) {
1.1730 + return u < v
1.1731 + ? u.toString().length + ':' + u + '-' + v
1.1732 + : v.toString().length + ':' + v + '-' + u;
1.1733 + }
1.1734 +
1.1735 + function findConflicts(g, layering) {
1.1736 + var conflicts = {}, // Set of conflicting edge ids
1.1737 + pos = {}, // Position of node in its layer
1.1738 + prevLayer,
1.1739 + currLayer,
1.1740 + k0, // Position of the last inner segment in the previous layer
1.1741 + l, // Current position in the current layer (for iteration up to `l1`)
1.1742 + k1; // Position of the next inner segment in the previous layer or
1.1743 + // the position of the last element in the previous layer
1.1744 +
1.1745 + if (layering.length <= 2) return conflicts;
1.1746 +
1.1747 + function updateConflicts(v) {
1.1748 + var k = pos[v];
1.1749 + if (k < k0 || k > k1) {
1.1750 + conflicts[undirEdgeId(currLayer[l], v)] = true;
1.1751 + }
1.1752 + }
1.1753 +
1.1754 + layering[1].forEach(function(u, i) { pos[u] = i; });
1.1755 + for (var i = 1; i < layering.length - 1; ++i) {
1.1756 + prevLayer = layering[i];
1.1757 + currLayer = layering[i+1];
1.1758 + k0 = 0;
1.1759 + l = 0;
1.1760 +
1.1761 + // Scan current layer for next node that is incident to an inner segement
1.1762 + // between layering[i+1] and layering[i].
1.1763 + for (var l1 = 0; l1 < currLayer.length; ++l1) {
1.1764 + var u = currLayer[l1]; // Next inner segment in the current layer or
1.1765 + // last node in the current layer
1.1766 + pos[u] = l1;
1.1767 + k1 = undefined;
1.1768 +
1.1769 + if (g.node(u).dummy) {
1.1770 + var uPred = g.predecessors(u)[0];
1.1771 + // Note: In the case of self loops and sideways edges it is possible
1.1772 + // for a dummy not to have a predecessor.
1.1773 + if (uPred !== undefined && g.node(uPred).dummy)
1.1774 + k1 = pos[uPred];
1.1775 + }
1.1776 + if (k1 === undefined && l1 === currLayer.length - 1)
1.1777 + k1 = prevLayer.length - 1;
1.1778 +
1.1779 + if (k1 !== undefined) {
1.1780 + for (; l <= l1; ++l) {
1.1781 + g.predecessors(currLayer[l]).forEach(updateConflicts);
1.1782 + }
1.1783 + k0 = k1;
1.1784 + }
1.1785 + }
1.1786 + }
1.1787 +
1.1788 + return conflicts;
1.1789 + }
1.1790 +
1.1791 + function verticalAlignment(g, layering, conflicts, relationship) {
1.1792 + var pos = {}, // Position for a node in its layer
1.1793 + root = {}, // Root of the block that the node participates in
1.1794 + align = {}; // Points to the next node in the block or, if the last
1.1795 + // element in the block, points to the first block's root
1.1796 +
1.1797 + layering.forEach(function(layer) {
1.1798 + layer.forEach(function(u, i) {
1.1799 + root[u] = u;
1.1800 + align[u] = u;
1.1801 + pos[u] = i;
1.1802 + });
1.1803 + });
1.1804 +
1.1805 + layering.forEach(function(layer) {
1.1806 + var prevIdx = -1;
1.1807 + layer.forEach(function(v) {
1.1808 + var related = g[relationship](v), // Adjacent nodes from the previous layer
1.1809 + mid; // The mid point in the related array
1.1810 +
1.1811 + if (related.length > 0) {
1.1812 + related.sort(function(x, y) { return pos[x] - pos[y]; });
1.1813 + mid = (related.length - 1) / 2;
1.1814 + related.slice(Math.floor(mid), Math.ceil(mid) + 1).forEach(function(u) {
1.1815 + if (align[v] === v) {
1.1816 + if (!conflicts[undirEdgeId(u, v)] && prevIdx < pos[u]) {
1.1817 + align[u] = v;
1.1818 + align[v] = root[v] = root[u];
1.1819 + prevIdx = pos[u];
1.1820 + }
1.1821 + }
1.1822 + });
1.1823 + }
1.1824 + });
1.1825 + });
1.1826 +
1.1827 + return { pos: pos, root: root, align: align };
1.1828 + }
1.1829 +
1.1830 + // This function deviates from the standard BK algorithm in two ways. First
1.1831 + // it takes into account the size of the nodes. Second it includes a fix to
1.1832 + // the original algorithm that is described in Carstens, "Node and Label
1.1833 + // Placement in a Layered Layout Algorithm".
1.1834 + function horizontalCompaction(g, layering, pos, root, align) {
1.1835 + var sink = {}, // Mapping of node id -> sink node id for class
1.1836 + maybeShift = {}, // Mapping of sink node id -> { class node id, min shift }
1.1837 + shift = {}, // Mapping of sink node id -> shift
1.1838 + pred = {}, // Mapping of node id -> predecessor node (or null)
1.1839 + xs = {}; // Calculated X positions
1.1840 +
1.1841 + layering.forEach(function(layer) {
1.1842 + layer.forEach(function(u, i) {
1.1843 + sink[u] = u;
1.1844 + maybeShift[u] = {};
1.1845 + if (i > 0)
1.1846 + pred[u] = layer[i - 1];
1.1847 + });
1.1848 + });
1.1849 +
1.1850 + function updateShift(toShift, neighbor, delta) {
1.1851 + if (!(neighbor in maybeShift[toShift])) {
1.1852 + maybeShift[toShift][neighbor] = delta;
1.1853 + } else {
1.1854 + maybeShift[toShift][neighbor] = Math.min(maybeShift[toShift][neighbor], delta);
1.1855 + }
1.1856 + }
1.1857 +
1.1858 + function placeBlock(v) {
1.1859 + if (!(v in xs)) {
1.1860 + xs[v] = 0;
1.1861 + var w = v;
1.1862 + do {
1.1863 + if (pos[w] > 0) {
1.1864 + var u = root[pred[w]];
1.1865 + placeBlock(u);
1.1866 + if (sink[v] === v) {
1.1867 + sink[v] = sink[u];
1.1868 + }
1.1869 + var delta = sep(g, pred[w]) + sep(g, w);
1.1870 + if (sink[v] !== sink[u]) {
1.1871 + updateShift(sink[u], sink[v], xs[v] - xs[u] - delta);
1.1872 + } else {
1.1873 + xs[v] = Math.max(xs[v], xs[u] + delta);
1.1874 + }
1.1875 + }
1.1876 + w = align[w];
1.1877 + } while (w !== v);
1.1878 + }
1.1879 + }
1.1880 +
1.1881 + // Root coordinates relative to sink
1.1882 + util.values(root).forEach(function(v) {
1.1883 + placeBlock(v);
1.1884 + });
1.1885 +
1.1886 + // Absolute coordinates
1.1887 + // There is an assumption here that we've resolved shifts for any classes
1.1888 + // that begin at an earlier layer. We guarantee this by visiting layers in
1.1889 + // order.
1.1890 + layering.forEach(function(layer) {
1.1891 + layer.forEach(function(v) {
1.1892 + xs[v] = xs[root[v]];
1.1893 + if (v === root[v] && v === sink[v]) {
1.1894 + var minShift = 0;
1.1895 + if (v in maybeShift && Object.keys(maybeShift[v]).length > 0) {
1.1896 + minShift = util.min(Object.keys(maybeShift[v])
1.1897 + .map(function(u) {
1.1898 + return maybeShift[v][u] + (u in shift ? shift[u] : 0);
1.1899 + }
1.1900 + ));
1.1901 + }
1.1902 + shift[v] = minShift;
1.1903 + }
1.1904 + });
1.1905 + });
1.1906 +
1.1907 + layering.forEach(function(layer) {
1.1908 + layer.forEach(function(v) {
1.1909 + xs[v] += shift[sink[root[v]]] || 0;
1.1910 + });
1.1911 + });
1.1912 +
1.1913 + return xs;
1.1914 + }
1.1915 +
1.1916 + function findMinCoord(g, layering, xs) {
1.1917 + return util.min(layering.map(function(layer) {
1.1918 + var u = layer[0];
1.1919 + return xs[u];
1.1920 + }));
1.1921 + }
1.1922 +
1.1923 + function findMaxCoord(g, layering, xs) {
1.1924 + return util.max(layering.map(function(layer) {
1.1925 + var u = layer[layer.length - 1];
1.1926 + return xs[u];
1.1927 + }));
1.1928 + }
1.1929 +
1.1930 + function balance(g, layering, xss) {
1.1931 + var min = {}, // Min coordinate for the alignment
1.1932 + max = {}, // Max coordinate for the alginment
1.1933 + smallestAlignment,
1.1934 + shift = {}; // Amount to shift a given alignment
1.1935 +
1.1936 + function updateAlignment(v) {
1.1937 + xss[alignment][v] += shift[alignment];
1.1938 + }
1.1939 +
1.1940 + var smallest = Number.POSITIVE_INFINITY;
1.1941 + for (var alignment in xss) {
1.1942 + var xs = xss[alignment];
1.1943 + min[alignment] = findMinCoord(g, layering, xs);
1.1944 + max[alignment] = findMaxCoord(g, layering, xs);
1.1945 + var w = max[alignment] - min[alignment];
1.1946 + if (w < smallest) {
1.1947 + smallest = w;
1.1948 + smallestAlignment = alignment;
1.1949 + }
1.1950 + }
1.1951 +
1.1952 + // Determine how much to adjust positioning for each alignment
1.1953 + ['u', 'd'].forEach(function(vertDir) {
1.1954 + ['l', 'r'].forEach(function(horizDir) {
1.1955 + var alignment = vertDir + horizDir;
1.1956 + shift[alignment] = horizDir === 'l'
1.1957 + ? min[smallestAlignment] - min[alignment]
1.1958 + : max[smallestAlignment] - max[alignment];
1.1959 + });
1.1960 + });
1.1961 +
1.1962 + // Find average of medians for xss array
1.1963 + for (alignment in xss) {
1.1964 + g.eachNode(updateAlignment);
1.1965 + }
1.1966 + }
1.1967 +
1.1968 + function flipHorizontally(xs) {
1.1969 + for (var u in xs) {
1.1970 + xs[u] = -xs[u];
1.1971 + }
1.1972 + }
1.1973 +
1.1974 + function reverseInnerOrder(layering) {
1.1975 + layering.forEach(function(layer) {
1.1976 + layer.reverse();
1.1977 + });
1.1978 + }
1.1979 +
1.1980 + function width(g, u) {
1.1981 + switch (g.graph().rankDir) {
1.1982 + case 'LR': return g.node(u).height;
1.1983 + case 'RL': return g.node(u).height;
1.1984 + default: return g.node(u).width;
1.1985 + }
1.1986 + }
1.1987 +
1.1988 + function height(g, u) {
1.1989 + switch(g.graph().rankDir) {
1.1990 + case 'LR': return g.node(u).width;
1.1991 + case 'RL': return g.node(u).width;
1.1992 + default: return g.node(u).height;
1.1993 + }
1.1994 + }
1.1995 +
1.1996 + function sep(g, u) {
1.1997 + if (config.universalSep !== null) {
1.1998 + return config.universalSep;
1.1999 + }
1.2000 + var w = width(g, u);
1.2001 + var s = g.node(u).dummy ? config.edgeSep : config.nodeSep;
1.2002 + return (w + s) / 2;
1.2003 + }
1.2004 +
1.2005 + function posX(g, u, x) {
1.2006 + if (g.graph().rankDir === 'LR' || g.graph().rankDir === 'RL') {
1.2007 + if (arguments.length < 3) {
1.2008 + return g.node(u).y;
1.2009 + } else {
1.2010 + g.node(u).y = x;
1.2011 + }
1.2012 + } else {
1.2013 + if (arguments.length < 3) {
1.2014 + return g.node(u).x;
1.2015 + } else {
1.2016 + g.node(u).x = x;
1.2017 + }
1.2018 + }
1.2019 + }
1.2020 +
1.2021 + function posXDebug(name, g, u, x) {
1.2022 + if (g.graph().rankDir === 'LR' || g.graph().rankDir === 'RL') {
1.2023 + if (arguments.length < 3) {
1.2024 + return g.node(u)[name];
1.2025 + } else {
1.2026 + g.node(u)[name] = x;
1.2027 + }
1.2028 + } else {
1.2029 + if (arguments.length < 3) {
1.2030 + return g.node(u)[name];
1.2031 + } else {
1.2032 + g.node(u)[name] = x;
1.2033 + }
1.2034 + }
1.2035 + }
1.2036 +
1.2037 + function posY(g, u, y) {
1.2038 + if (g.graph().rankDir === 'LR' || g.graph().rankDir === 'RL') {
1.2039 + if (arguments.length < 3) {
1.2040 + return g.node(u).x;
1.2041 + } else {
1.2042 + g.node(u).x = y;
1.2043 + }
1.2044 + } else {
1.2045 + if (arguments.length < 3) {
1.2046 + return g.node(u).y;
1.2047 + } else {
1.2048 + g.node(u).y = y;
1.2049 + }
1.2050 + }
1.2051 + }
1.2052 +
1.2053 + function debugPositioning(align, g, layering, xs) {
1.2054 + layering.forEach(function(l, li) {
1.2055 + var u, xU;
1.2056 + l.forEach(function(v) {
1.2057 + var xV = xs[v];
1.2058 + if (u) {
1.2059 + var s = sep(g, u) + sep(g, v);
1.2060 + if (xV - xU < s)
1.2061 + console.log('Position phase: sep violation. Align: ' + align + '. Layer: ' + li + '. ' +
1.2062 + 'U: ' + u + ' V: ' + v + '. Actual sep: ' + (xV - xU) + ' Expected sep: ' + s);
1.2063 + }
1.2064 + u = v;
1.2065 + xU = xV;
1.2066 + });
1.2067 + });
1.2068 + }
1.2069 +};
1.2070 +
1.2071 +},{"./util":26}],19:[function(require,module,exports){
1.2072 +var util = require('./util'),
1.2073 + acyclic = require('./rank/acyclic'),
1.2074 + initRank = require('./rank/initRank'),
1.2075 + feasibleTree = require('./rank/feasibleTree'),
1.2076 + constraints = require('./rank/constraints'),
1.2077 + simplex = require('./rank/simplex'),
1.2078 + components = require('graphlib').alg.components,
1.2079 + filter = require('graphlib').filter;
1.2080 +
1.2081 +exports.run = run;
1.2082 +exports.restoreEdges = restoreEdges;
1.2083 +
1.2084 +/*
1.2085 + * Heuristic function that assigns a rank to each node of the input graph with
1.2086 + * the intent of minimizing edge lengths, while respecting the `minLen`
1.2087 + * attribute of incident edges.
1.2088 + *
1.2089 + * Prerequisites:
1.2090 + *
1.2091 + * * Each edge in the input graph must have an assigned 'minLen' attribute
1.2092 + */
1.2093 +function run(g, useSimplex) {
1.2094 + expandSelfLoops(g);
1.2095 +
1.2096 + // If there are rank constraints on nodes, then build a new graph that
1.2097 + // encodes the constraints.
1.2098 + util.time('constraints.apply', constraints.apply)(g);
1.2099 +
1.2100 + expandSidewaysEdges(g);
1.2101 +
1.2102 + // Reverse edges to get an acyclic graph, we keep the graph in an acyclic
1.2103 + // state until the very end.
1.2104 + util.time('acyclic', acyclic)(g);
1.2105 +
1.2106 + // Convert the graph into a flat graph for ranking
1.2107 + var flatGraph = g.filterNodes(util.filterNonSubgraphs(g));
1.2108 +
1.2109 + // Assign an initial ranking using DFS.
1.2110 + initRank(flatGraph);
1.2111 +
1.2112 + // For each component improve the assigned ranks.
1.2113 + components(flatGraph).forEach(function(cmpt) {
1.2114 + var subgraph = flatGraph.filterNodes(filter.nodesFromList(cmpt));
1.2115 + rankComponent(subgraph, useSimplex);
1.2116 + });
1.2117 +
1.2118 + // Relax original constraints
1.2119 + util.time('constraints.relax', constraints.relax(g));
1.2120 +
1.2121 + // When handling nodes with constrained ranks it is possible to end up with
1.2122 + // edges that point to previous ranks. Most of the subsequent algorithms assume
1.2123 + // that edges are pointing to successive ranks only. Here we reverse any "back
1.2124 + // edges" and mark them as such. The acyclic algorithm will reverse them as a
1.2125 + // post processing step.
1.2126 + util.time('reorientEdges', reorientEdges)(g);
1.2127 +}
1.2128 +
1.2129 +function restoreEdges(g) {
1.2130 + acyclic.undo(g);
1.2131 +}
1.2132 +
1.2133 +/*
1.2134 + * Expand self loops into three dummy nodes. One will sit above the incident
1.2135 + * node, one will be at the same level, and one below. The result looks like:
1.2136 + *
1.2137 + * /--<--x--->--\
1.2138 + * node y
1.2139 + * \--<--z--->--/
1.2140 + *
1.2141 + * Dummy nodes x, y, z give us the shape of a loop and node y is where we place
1.2142 + * the label.
1.2143 + *
1.2144 + * TODO: consolidate knowledge of dummy node construction.
1.2145 + * TODO: support minLen = 2
1.2146 + */
1.2147 +function expandSelfLoops(g) {
1.2148 + g.eachEdge(function(e, u, v, a) {
1.2149 + if (u === v) {
1.2150 + var x = addDummyNode(g, e, u, v, a, 0, false),
1.2151 + y = addDummyNode(g, e, u, v, a, 1, true),
1.2152 + z = addDummyNode(g, e, u, v, a, 2, false);
1.2153 + g.addEdge(null, x, u, {minLen: 1, selfLoop: true});
1.2154 + g.addEdge(null, x, y, {minLen: 1, selfLoop: true});
1.2155 + g.addEdge(null, u, z, {minLen: 1, selfLoop: true});
1.2156 + g.addEdge(null, y, z, {minLen: 1, selfLoop: true});
1.2157 + g.delEdge(e);
1.2158 + }
1.2159 + });
1.2160 +}
1.2161 +
1.2162 +function expandSidewaysEdges(g) {
1.2163 + g.eachEdge(function(e, u, v, a) {
1.2164 + if (u === v) {
1.2165 + var origEdge = a.originalEdge,
1.2166 + dummy = addDummyNode(g, origEdge.e, origEdge.u, origEdge.v, origEdge.value, 0, true);
1.2167 + g.addEdge(null, u, dummy, {minLen: 1});
1.2168 + g.addEdge(null, dummy, v, {minLen: 1});
1.2169 + g.delEdge(e);
1.2170 + }
1.2171 + });
1.2172 +}
1.2173 +
1.2174 +function addDummyNode(g, e, u, v, a, index, isLabel) {
1.2175 + return g.addNode(null, {
1.2176 + width: isLabel ? a.width : 0,
1.2177 + height: isLabel ? a.height : 0,
1.2178 + edge: { id: e, source: u, target: v, attrs: a },
1.2179 + dummy: true,
1.2180 + index: index
1.2181 + });
1.2182 +}
1.2183 +
1.2184 +function reorientEdges(g) {
1.2185 + g.eachEdge(function(e, u, v, value) {
1.2186 + if (g.node(u).rank > g.node(v).rank) {
1.2187 + g.delEdge(e);
1.2188 + value.reversed = true;
1.2189 + g.addEdge(e, v, u, value);
1.2190 + }
1.2191 + });
1.2192 +}
1.2193 +
1.2194 +function rankComponent(subgraph, useSimplex) {
1.2195 + var spanningTree = feasibleTree(subgraph);
1.2196 +
1.2197 + if (useSimplex) {
1.2198 + util.log(1, 'Using network simplex for ranking');
1.2199 + simplex(subgraph, spanningTree);
1.2200 + }
1.2201 + normalize(subgraph);
1.2202 +}
1.2203 +
1.2204 +function normalize(g) {
1.2205 + var m = util.min(g.nodes().map(function(u) { return g.node(u).rank; }));
1.2206 + g.eachNode(function(u, node) { node.rank -= m; });
1.2207 +}
1.2208 +
1.2209 +},{"./rank/acyclic":20,"./rank/constraints":21,"./rank/feasibleTree":22,"./rank/initRank":23,"./rank/simplex":25,"./util":26,"graphlib":28}],20:[function(require,module,exports){
1.2210 +var util = require('../util');
1.2211 +
1.2212 +module.exports = acyclic;
1.2213 +module.exports.undo = undo;
1.2214 +
1.2215 +/*
1.2216 + * This function takes a directed graph that may have cycles and reverses edges
1.2217 + * as appropriate to break these cycles. Each reversed edge is assigned a
1.2218 + * `reversed` attribute with the value `true`.
1.2219 + *
1.2220 + * There should be no self loops in the graph.
1.2221 + */
1.2222 +function acyclic(g) {
1.2223 + var onStack = {},
1.2224 + visited = {},
1.2225 + reverseCount = 0;
1.2226 +
1.2227 + function dfs(u) {
1.2228 + if (u in visited) return;
1.2229 + visited[u] = onStack[u] = true;
1.2230 + g.outEdges(u).forEach(function(e) {
1.2231 + var t = g.target(e),
1.2232 + value;
1.2233 +
1.2234 + if (u === t) {
1.2235 + console.error('Warning: found self loop "' + e + '" for node "' + u + '"');
1.2236 + } else if (t in onStack) {
1.2237 + value = g.edge(e);
1.2238 + g.delEdge(e);
1.2239 + value.reversed = true;
1.2240 + ++reverseCount;
1.2241 + g.addEdge(e, t, u, value);
1.2242 + } else {
1.2243 + dfs(t);
1.2244 + }
1.2245 + });
1.2246 +
1.2247 + delete onStack[u];
1.2248 + }
1.2249 +
1.2250 + g.eachNode(function(u) { dfs(u); });
1.2251 +
1.2252 + util.log(2, 'Acyclic Phase: reversed ' + reverseCount + ' edge(s)');
1.2253 +
1.2254 + return reverseCount;
1.2255 +}
1.2256 +
1.2257 +/*
1.2258 + * Given a graph that has had the acyclic operation applied, this function
1.2259 + * undoes that operation. More specifically, any edge with the `reversed`
1.2260 + * attribute is again reversed to restore the original direction of the edge.
1.2261 + */
1.2262 +function undo(g) {
1.2263 + g.eachEdge(function(e, s, t, a) {
1.2264 + if (a.reversed) {
1.2265 + delete a.reversed;
1.2266 + g.delEdge(e);
1.2267 + g.addEdge(e, t, s, a);
1.2268 + }
1.2269 + });
1.2270 +}
1.2271 +
1.2272 +},{"../util":26}],21:[function(require,module,exports){
1.2273 +exports.apply = function(g) {
1.2274 + function dfs(sg) {
1.2275 + var rankSets = {};
1.2276 + g.children(sg).forEach(function(u) {
1.2277 + if (g.children(u).length) {
1.2278 + dfs(u);
1.2279 + return;
1.2280 + }
1.2281 +
1.2282 + var value = g.node(u),
1.2283 + prefRank = value.prefRank;
1.2284 + if (prefRank !== undefined) {
1.2285 + if (!checkSupportedPrefRank(prefRank)) { return; }
1.2286 +
1.2287 + if (!(prefRank in rankSets)) {
1.2288 + rankSets.prefRank = [u];
1.2289 + } else {
1.2290 + rankSets.prefRank.push(u);
1.2291 + }
1.2292 +
1.2293 + var newU = rankSets[prefRank];
1.2294 + if (newU === undefined) {
1.2295 + newU = rankSets[prefRank] = g.addNode(null, { originalNodes: [] });
1.2296 + g.parent(newU, sg);
1.2297 + }
1.2298 +
1.2299 + redirectInEdges(g, u, newU, prefRank === 'min');
1.2300 + redirectOutEdges(g, u, newU, prefRank === 'max');
1.2301 +
1.2302 + // Save original node and remove it from reduced graph
1.2303 + g.node(newU).originalNodes.push({ u: u, value: value, parent: sg });
1.2304 + g.delNode(u);
1.2305 + }
1.2306 + });
1.2307 +
1.2308 + addLightEdgesFromMinNode(g, sg, rankSets.min);
1.2309 + addLightEdgesToMaxNode(g, sg, rankSets.max);
1.2310 + }
1.2311 +
1.2312 + dfs(null);
1.2313 +};
1.2314 +
1.2315 +function checkSupportedPrefRank(prefRank) {
1.2316 + if (prefRank !== 'min' && prefRank !== 'max' && prefRank.indexOf('same_') !== 0) {
1.2317 + console.error('Unsupported rank type: ' + prefRank);
1.2318 + return false;
1.2319 + }
1.2320 + return true;
1.2321 +}
1.2322 +
1.2323 +function redirectInEdges(g, u, newU, reverse) {
1.2324 + g.inEdges(u).forEach(function(e) {
1.2325 + var origValue = g.edge(e),
1.2326 + value;
1.2327 + if (origValue.originalEdge) {
1.2328 + value = origValue;
1.2329 + } else {
1.2330 + value = {
1.2331 + originalEdge: { e: e, u: g.source(e), v: g.target(e), value: origValue },
1.2332 + minLen: g.edge(e).minLen
1.2333 + };
1.2334 + }
1.2335 +
1.2336 + // Do not reverse edges for self-loops.
1.2337 + if (origValue.selfLoop) {
1.2338 + reverse = false;
1.2339 + }
1.2340 +
1.2341 + if (reverse) {
1.2342 + // Ensure that all edges to min are reversed
1.2343 + g.addEdge(null, newU, g.source(e), value);
1.2344 + value.reversed = true;
1.2345 + } else {
1.2346 + g.addEdge(null, g.source(e), newU, value);
1.2347 + }
1.2348 + });
1.2349 +}
1.2350 +
1.2351 +function redirectOutEdges(g, u, newU, reverse) {
1.2352 + g.outEdges(u).forEach(function(e) {
1.2353 + var origValue = g.edge(e),
1.2354 + value;
1.2355 + if (origValue.originalEdge) {
1.2356 + value = origValue;
1.2357 + } else {
1.2358 + value = {
1.2359 + originalEdge: { e: e, u: g.source(e), v: g.target(e), value: origValue },
1.2360 + minLen: g.edge(e).minLen
1.2361 + };
1.2362 + }
1.2363 +
1.2364 + // Do not reverse edges for self-loops.
1.2365 + if (origValue.selfLoop) {
1.2366 + reverse = false;
1.2367 + }
1.2368 +
1.2369 + if (reverse) {
1.2370 + // Ensure that all edges from max are reversed
1.2371 + g.addEdge(null, g.target(e), newU, value);
1.2372 + value.reversed = true;
1.2373 + } else {
1.2374 + g.addEdge(null, newU, g.target(e), value);
1.2375 + }
1.2376 + });
1.2377 +}
1.2378 +
1.2379 +function addLightEdgesFromMinNode(g, sg, minNode) {
1.2380 + if (minNode !== undefined) {
1.2381 + g.children(sg).forEach(function(u) {
1.2382 + // The dummy check ensures we don't add an edge if the node is involved
1.2383 + // in a self loop or sideways edge.
1.2384 + if (u !== minNode && !g.outEdges(minNode, u).length && !g.node(u).dummy) {
1.2385 + g.addEdge(null, minNode, u, { minLen: 0 });
1.2386 + }
1.2387 + });
1.2388 + }
1.2389 +}
1.2390 +
1.2391 +function addLightEdgesToMaxNode(g, sg, maxNode) {
1.2392 + if (maxNode !== undefined) {
1.2393 + g.children(sg).forEach(function(u) {
1.2394 + // The dummy check ensures we don't add an edge if the node is involved
1.2395 + // in a self loop or sideways edge.
1.2396 + if (u !== maxNode && !g.outEdges(u, maxNode).length && !g.node(u).dummy) {
1.2397 + g.addEdge(null, u, maxNode, { minLen: 0 });
1.2398 + }
1.2399 + });
1.2400 + }
1.2401 +}
1.2402 +
1.2403 +/*
1.2404 + * This function "relaxes" the constraints applied previously by the "apply"
1.2405 + * function. It expands any nodes that were collapsed and assigns the rank of
1.2406 + * the collapsed node to each of the expanded nodes. It also restores the
1.2407 + * original edges and removes any dummy edges pointing at the collapsed nodes.
1.2408 + *
1.2409 + * Note that the process of removing collapsed nodes also removes dummy edges
1.2410 + * automatically.
1.2411 + */
1.2412 +exports.relax = function(g) {
1.2413 + // Save original edges
1.2414 + var originalEdges = [];
1.2415 + g.eachEdge(function(e, u, v, value) {
1.2416 + var originalEdge = value.originalEdge;
1.2417 + if (originalEdge) {
1.2418 + originalEdges.push(originalEdge);
1.2419 + }
1.2420 + });
1.2421 +
1.2422 + // Expand collapsed nodes
1.2423 + g.eachNode(function(u, value) {
1.2424 + var originalNodes = value.originalNodes;
1.2425 + if (originalNodes) {
1.2426 + originalNodes.forEach(function(originalNode) {
1.2427 + originalNode.value.rank = value.rank;
1.2428 + g.addNode(originalNode.u, originalNode.value);
1.2429 + g.parent(originalNode.u, originalNode.parent);
1.2430 + });
1.2431 + g.delNode(u);
1.2432 + }
1.2433 + });
1.2434 +
1.2435 + // Restore original edges
1.2436 + originalEdges.forEach(function(edge) {
1.2437 + g.addEdge(edge.e, edge.u, edge.v, edge.value);
1.2438 + });
1.2439 +};
1.2440 +
1.2441 +},{}],22:[function(require,module,exports){
1.2442 +/* jshint -W079 */
1.2443 +var Set = require('cp-data').Set,
1.2444 +/* jshint +W079 */
1.2445 + Digraph = require('graphlib').Digraph,
1.2446 + util = require('../util');
1.2447 +
1.2448 +module.exports = feasibleTree;
1.2449 +
1.2450 +/*
1.2451 + * Given an acyclic graph with each node assigned a `rank` attribute, this
1.2452 + * function constructs and returns a spanning tree. This function may reduce
1.2453 + * the length of some edges from the initial rank assignment while maintaining
1.2454 + * the `minLen` specified by each edge.
1.2455 + *
1.2456 + * Prerequisites:
1.2457 + *
1.2458 + * * The input graph is acyclic
1.2459 + * * Each node in the input graph has an assigned `rank` attribute
1.2460 + * * Each edge in the input graph has an assigned `minLen` attribute
1.2461 + *
1.2462 + * Outputs:
1.2463 + *
1.2464 + * A feasible spanning tree for the input graph (i.e. a spanning tree that
1.2465 + * respects each graph edge's `minLen` attribute) represented as a Digraph with
1.2466 + * a `root` attribute on graph.
1.2467 + *
1.2468 + * Nodes have the same id and value as that in the input graph.
1.2469 + *
1.2470 + * Edges in the tree have arbitrarily assigned ids. The attributes for edges
1.2471 + * include `reversed`. `reversed` indicates that the edge is a
1.2472 + * back edge in the input graph.
1.2473 + */
1.2474 +function feasibleTree(g) {
1.2475 + var remaining = new Set(g.nodes()),
1.2476 + tree = new Digraph();
1.2477 +
1.2478 + if (remaining.size() === 1) {
1.2479 + var root = g.nodes()[0];
1.2480 + tree.addNode(root, {});
1.2481 + tree.graph({ root: root });
1.2482 + return tree;
1.2483 + }
1.2484 +
1.2485 + function addTightEdges(v) {
1.2486 + var continueToScan = true;
1.2487 + g.predecessors(v).forEach(function(u) {
1.2488 + if (remaining.has(u) && !slack(g, u, v)) {
1.2489 + if (remaining.has(v)) {
1.2490 + tree.addNode(v, {});
1.2491 + remaining.remove(v);
1.2492 + tree.graph({ root: v });
1.2493 + }
1.2494 +
1.2495 + tree.addNode(u, {});
1.2496 + tree.addEdge(null, u, v, { reversed: true });
1.2497 + remaining.remove(u);
1.2498 + addTightEdges(u);
1.2499 + continueToScan = false;
1.2500 + }
1.2501 + });
1.2502 +
1.2503 + g.successors(v).forEach(function(w) {
1.2504 + if (remaining.has(w) && !slack(g, v, w)) {
1.2505 + if (remaining.has(v)) {
1.2506 + tree.addNode(v, {});
1.2507 + remaining.remove(v);
1.2508 + tree.graph({ root: v });
1.2509 + }
1.2510 +
1.2511 + tree.addNode(w, {});
1.2512 + tree.addEdge(null, v, w, {});
1.2513 + remaining.remove(w);
1.2514 + addTightEdges(w);
1.2515 + continueToScan = false;
1.2516 + }
1.2517 + });
1.2518 + return continueToScan;
1.2519 + }
1.2520 +
1.2521 + function createTightEdge() {
1.2522 + var minSlack = Number.MAX_VALUE;
1.2523 + remaining.keys().forEach(function(v) {
1.2524 + g.predecessors(v).forEach(function(u) {
1.2525 + if (!remaining.has(u)) {
1.2526 + var edgeSlack = slack(g, u, v);
1.2527 + if (Math.abs(edgeSlack) < Math.abs(minSlack)) {
1.2528 + minSlack = -edgeSlack;
1.2529 + }
1.2530 + }
1.2531 + });
1.2532 +
1.2533 + g.successors(v).forEach(function(w) {
1.2534 + if (!remaining.has(w)) {
1.2535 + var edgeSlack = slack(g, v, w);
1.2536 + if (Math.abs(edgeSlack) < Math.abs(minSlack)) {
1.2537 + minSlack = edgeSlack;
1.2538 + }
1.2539 + }
1.2540 + });
1.2541 + });
1.2542 +
1.2543 + tree.eachNode(function(u) { g.node(u).rank -= minSlack; });
1.2544 + }
1.2545 +
1.2546 + while (remaining.size()) {
1.2547 + var nodesToSearch = !tree.order() ? remaining.keys() : tree.nodes();
1.2548 + for (var i = 0, il = nodesToSearch.length;
1.2549 + i < il && addTightEdges(nodesToSearch[i]);
1.2550 + ++i);
1.2551 + if (remaining.size()) {
1.2552 + createTightEdge();
1.2553 + }
1.2554 + }
1.2555 +
1.2556 + return tree;
1.2557 +}
1.2558 +
1.2559 +function slack(g, u, v) {
1.2560 + var rankDiff = g.node(v).rank - g.node(u).rank;
1.2561 + var maxMinLen = util.max(g.outEdges(u, v)
1.2562 + .map(function(e) { return g.edge(e).minLen; }));
1.2563 + return rankDiff - maxMinLen;
1.2564 +}
1.2565 +
1.2566 +},{"../util":26,"cp-data":5,"graphlib":28}],23:[function(require,module,exports){
1.2567 +var util = require('../util'),
1.2568 + topsort = require('graphlib').alg.topsort;
1.2569 +
1.2570 +module.exports = initRank;
1.2571 +
1.2572 +/*
1.2573 + * Assigns a `rank` attribute to each node in the input graph and ensures that
1.2574 + * this rank respects the `minLen` attribute of incident edges.
1.2575 + *
1.2576 + * Prerequisites:
1.2577 + *
1.2578 + * * The input graph must be acyclic
1.2579 + * * Each edge in the input graph must have an assigned 'minLen' attribute
1.2580 + */
1.2581 +function initRank(g) {
1.2582 + var sorted = topsort(g);
1.2583 +
1.2584 + sorted.forEach(function(u) {
1.2585 + var inEdges = g.inEdges(u);
1.2586 + if (inEdges.length === 0) {
1.2587 + g.node(u).rank = 0;
1.2588 + return;
1.2589 + }
1.2590 +
1.2591 + var minLens = inEdges.map(function(e) {
1.2592 + return g.node(g.source(e)).rank + g.edge(e).minLen;
1.2593 + });
1.2594 + g.node(u).rank = util.max(minLens);
1.2595 + });
1.2596 +}
1.2597 +
1.2598 +},{"../util":26,"graphlib":28}],24:[function(require,module,exports){
1.2599 +module.exports = {
1.2600 + slack: slack
1.2601 +};
1.2602 +
1.2603 +/*
1.2604 + * A helper to calculate the slack between two nodes (`u` and `v`) given a
1.2605 + * `minLen` constraint. The slack represents how much the distance between `u`
1.2606 + * and `v` could shrink while maintaining the `minLen` constraint. If the value
1.2607 + * is negative then the constraint is currently violated.
1.2608 + *
1.2609 + This function requires that `u` and `v` are in `graph` and they both have a
1.2610 + `rank` attribute.
1.2611 + */
1.2612 +function slack(graph, u, v, minLen) {
1.2613 + return Math.abs(graph.node(u).rank - graph.node(v).rank) - minLen;
1.2614 +}
1.2615 +
1.2616 +},{}],25:[function(require,module,exports){
1.2617 +var util = require('../util'),
1.2618 + rankUtil = require('./rankUtil');
1.2619 +
1.2620 +module.exports = simplex;
1.2621 +
1.2622 +function simplex(graph, spanningTree) {
1.2623 + // The network simplex algorithm repeatedly replaces edges of
1.2624 + // the spanning tree with negative cut values until no such
1.2625 + // edge exists.
1.2626 + initCutValues(graph, spanningTree);
1.2627 + while (true) {
1.2628 + var e = leaveEdge(spanningTree);
1.2629 + if (e === null) break;
1.2630 + var f = enterEdge(graph, spanningTree, e);
1.2631 + exchange(graph, spanningTree, e, f);
1.2632 + }
1.2633 +}
1.2634 +
1.2635 +/*
1.2636 + * Set the cut values of edges in the spanning tree by a depth-first
1.2637 + * postorder traversal. The cut value corresponds to the cost, in
1.2638 + * terms of a ranking's edge length sum, of lengthening an edge.
1.2639 + * Negative cut values typically indicate edges that would yield a
1.2640 + * smaller edge length sum if they were lengthened.
1.2641 + */
1.2642 +function initCutValues(graph, spanningTree) {
1.2643 + computeLowLim(spanningTree);
1.2644 +
1.2645 + spanningTree.eachEdge(function(id, u, v, treeValue) {
1.2646 + treeValue.cutValue = 0;
1.2647 + });
1.2648 +
1.2649 + // Propagate cut values up the tree.
1.2650 + function dfs(n) {
1.2651 + var children = spanningTree.successors(n);
1.2652 + for (var c in children) {
1.2653 + var child = children[c];
1.2654 + dfs(child);
1.2655 + }
1.2656 + if (n !== spanningTree.graph().root) {
1.2657 + setCutValue(graph, spanningTree, n);
1.2658 + }
1.2659 + }
1.2660 + dfs(spanningTree.graph().root);
1.2661 +}
1.2662 +
1.2663 +/*
1.2664 + * Perform a DFS postorder traversal, labeling each node v with
1.2665 + * its traversal order 'lim(v)' and the minimum traversal number
1.2666 + * of any of its descendants 'low(v)'. This provides an efficient
1.2667 + * way to test whether u is an ancestor of v since
1.2668 + * low(u) <= lim(v) <= lim(u) if and only if u is an ancestor.
1.2669 + */
1.2670 +function computeLowLim(tree) {
1.2671 + var postOrderNum = 0;
1.2672 +
1.2673 + function dfs(n) {
1.2674 + var children = tree.successors(n);
1.2675 + var low = postOrderNum;
1.2676 + for (var c in children) {
1.2677 + var child = children[c];
1.2678 + dfs(child);
1.2679 + low = Math.min(low, tree.node(child).low);
1.2680 + }
1.2681 + tree.node(n).low = low;
1.2682 + tree.node(n).lim = postOrderNum++;
1.2683 + }
1.2684 +
1.2685 + dfs(tree.graph().root);
1.2686 +}
1.2687 +
1.2688 +/*
1.2689 + * To compute the cut value of the edge parent -> child, we consider
1.2690 + * it and any other graph edges to or from the child.
1.2691 + * parent
1.2692 + * |
1.2693 + * child
1.2694 + * / \
1.2695 + * u v
1.2696 + */
1.2697 +function setCutValue(graph, tree, child) {
1.2698 + var parentEdge = tree.inEdges(child)[0];
1.2699 +
1.2700 + // List of child's children in the spanning tree.
1.2701 + var grandchildren = [];
1.2702 + var grandchildEdges = tree.outEdges(child);
1.2703 + for (var gce in grandchildEdges) {
1.2704 + grandchildren.push(tree.target(grandchildEdges[gce]));
1.2705 + }
1.2706 +
1.2707 + var cutValue = 0;
1.2708 +
1.2709 + // TODO: Replace unit increment/decrement with edge weights.
1.2710 + var E = 0; // Edges from child to grandchild's subtree.
1.2711 + var F = 0; // Edges to child from grandchild's subtree.
1.2712 + var G = 0; // Edges from child to nodes outside of child's subtree.
1.2713 + var H = 0; // Edges from nodes outside of child's subtree to child.
1.2714 +
1.2715 + // Consider all graph edges from child.
1.2716 + var outEdges = graph.outEdges(child);
1.2717 + var gc;
1.2718 + for (var oe in outEdges) {
1.2719 + var succ = graph.target(outEdges[oe]);
1.2720 + for (gc in grandchildren) {
1.2721 + if (inSubtree(tree, succ, grandchildren[gc])) {
1.2722 + E++;
1.2723 + }
1.2724 + }
1.2725 + if (!inSubtree(tree, succ, child)) {
1.2726 + G++;
1.2727 + }
1.2728 + }
1.2729 +
1.2730 + // Consider all graph edges to child.
1.2731 + var inEdges = graph.inEdges(child);
1.2732 + for (var ie in inEdges) {
1.2733 + var pred = graph.source(inEdges[ie]);
1.2734 + for (gc in grandchildren) {
1.2735 + if (inSubtree(tree, pred, grandchildren[gc])) {
1.2736 + F++;
1.2737 + }
1.2738 + }
1.2739 + if (!inSubtree(tree, pred, child)) {
1.2740 + H++;
1.2741 + }
1.2742 + }
1.2743 +
1.2744 + // Contributions depend on the alignment of the parent -> child edge
1.2745 + // and the child -> u or v edges.
1.2746 + var grandchildCutSum = 0;
1.2747 + for (gc in grandchildren) {
1.2748 + var cv = tree.edge(grandchildEdges[gc]).cutValue;
1.2749 + if (!tree.edge(grandchildEdges[gc]).reversed) {
1.2750 + grandchildCutSum += cv;
1.2751 + } else {
1.2752 + grandchildCutSum -= cv;
1.2753 + }
1.2754 + }
1.2755 +
1.2756 + if (!tree.edge(parentEdge).reversed) {
1.2757 + cutValue += grandchildCutSum - E + F - G + H;
1.2758 + } else {
1.2759 + cutValue -= grandchildCutSum - E + F - G + H;
1.2760 + }
1.2761 +
1.2762 + tree.edge(parentEdge).cutValue = cutValue;
1.2763 +}
1.2764 +
1.2765 +/*
1.2766 + * Return whether n is a node in the subtree with the given
1.2767 + * root.
1.2768 + */
1.2769 +function inSubtree(tree, n, root) {
1.2770 + return (tree.node(root).low <= tree.node(n).lim &&
1.2771 + tree.node(n).lim <= tree.node(root).lim);
1.2772 +}
1.2773 +
1.2774 +/*
1.2775 + * Return an edge from the tree with a negative cut value, or null if there
1.2776 + * is none.
1.2777 + */
1.2778 +function leaveEdge(tree) {
1.2779 + var edges = tree.edges();
1.2780 + for (var n in edges) {
1.2781 + var e = edges[n];
1.2782 + var treeValue = tree.edge(e);
1.2783 + if (treeValue.cutValue < 0) {
1.2784 + return e;
1.2785 + }
1.2786 + }
1.2787 + return null;
1.2788 +}
1.2789 +
1.2790 +/*
1.2791 + * The edge e should be an edge in the tree, with an underlying edge
1.2792 + * in the graph, with a negative cut value. Of the two nodes incident
1.2793 + * on the edge, take the lower one. enterEdge returns an edge with
1.2794 + * minimum slack going from outside of that node's subtree to inside
1.2795 + * of that node's subtree.
1.2796 + */
1.2797 +function enterEdge(graph, tree, e) {
1.2798 + var source = tree.source(e);
1.2799 + var target = tree.target(e);
1.2800 + var lower = tree.node(target).lim < tree.node(source).lim ? target : source;
1.2801 +
1.2802 + // Is the tree edge aligned with the graph edge?
1.2803 + var aligned = !tree.edge(e).reversed;
1.2804 +
1.2805 + var minSlack = Number.POSITIVE_INFINITY;
1.2806 + var minSlackEdge;
1.2807 + if (aligned) {
1.2808 + graph.eachEdge(function(id, u, v, value) {
1.2809 + if (id !== e && inSubtree(tree, u, lower) && !inSubtree(tree, v, lower)) {
1.2810 + var slack = rankUtil.slack(graph, u, v, value.minLen);
1.2811 + if (slack < minSlack) {
1.2812 + minSlack = slack;
1.2813 + minSlackEdge = id;
1.2814 + }
1.2815 + }
1.2816 + });
1.2817 + } else {
1.2818 + graph.eachEdge(function(id, u, v, value) {
1.2819 + if (id !== e && !inSubtree(tree, u, lower) && inSubtree(tree, v, lower)) {
1.2820 + var slack = rankUtil.slack(graph, u, v, value.minLen);
1.2821 + if (slack < minSlack) {
1.2822 + minSlack = slack;
1.2823 + minSlackEdge = id;
1.2824 + }
1.2825 + }
1.2826 + });
1.2827 + }
1.2828 +
1.2829 + if (minSlackEdge === undefined) {
1.2830 + var outside = [];
1.2831 + var inside = [];
1.2832 + graph.eachNode(function(id) {
1.2833 + if (!inSubtree(tree, id, lower)) {
1.2834 + outside.push(id);
1.2835 + } else {
1.2836 + inside.push(id);
1.2837 + }
1.2838 + });
1.2839 + throw new Error('No edge found from outside of tree to inside');
1.2840 + }
1.2841 +
1.2842 + return minSlackEdge;
1.2843 +}
1.2844 +
1.2845 +/*
1.2846 + * Replace edge e with edge f in the tree, recalculating the tree root,
1.2847 + * the nodes' low and lim properties and the edges' cut values.
1.2848 + */
1.2849 +function exchange(graph, tree, e, f) {
1.2850 + tree.delEdge(e);
1.2851 + var source = graph.source(f);
1.2852 + var target = graph.target(f);
1.2853 +
1.2854 + // Redirect edges so that target is the root of its subtree.
1.2855 + function redirect(v) {
1.2856 + var edges = tree.inEdges(v);
1.2857 + for (var i in edges) {
1.2858 + var e = edges[i];
1.2859 + var u = tree.source(e);
1.2860 + var value = tree.edge(e);
1.2861 + redirect(u);
1.2862 + tree.delEdge(e);
1.2863 + value.reversed = !value.reversed;
1.2864 + tree.addEdge(e, v, u, value);
1.2865 + }
1.2866 + }
1.2867 +
1.2868 + redirect(target);
1.2869 +
1.2870 + var root = source;
1.2871 + var edges = tree.inEdges(root);
1.2872 + while (edges.length > 0) {
1.2873 + root = tree.source(edges[0]);
1.2874 + edges = tree.inEdges(root);
1.2875 + }
1.2876 +
1.2877 + tree.graph().root = root;
1.2878 +
1.2879 + tree.addEdge(null, source, target, {cutValue: 0});
1.2880 +
1.2881 + initCutValues(graph, tree);
1.2882 +
1.2883 + adjustRanks(graph, tree);
1.2884 +}
1.2885 +
1.2886 +/*
1.2887 + * Reset the ranks of all nodes based on the current spanning tree.
1.2888 + * The rank of the tree's root remains unchanged, while all other
1.2889 + * nodes are set to the sum of minimum length constraints along
1.2890 + * the path from the root.
1.2891 + */
1.2892 +function adjustRanks(graph, tree) {
1.2893 + function dfs(p) {
1.2894 + var children = tree.successors(p);
1.2895 + children.forEach(function(c) {
1.2896 + var minLen = minimumLength(graph, p, c);
1.2897 + graph.node(c).rank = graph.node(p).rank + minLen;
1.2898 + dfs(c);
1.2899 + });
1.2900 + }
1.2901 +
1.2902 + dfs(tree.graph().root);
1.2903 +}
1.2904 +
1.2905 +/*
1.2906 + * If u and v are connected by some edges in the graph, return the
1.2907 + * minimum length of those edges, as a positive number if v succeeds
1.2908 + * u and as a negative number if v precedes u.
1.2909 + */
1.2910 +function minimumLength(graph, u, v) {
1.2911 + var outEdges = graph.outEdges(u, v);
1.2912 + if (outEdges.length > 0) {
1.2913 + return util.max(outEdges.map(function(e) {
1.2914 + return graph.edge(e).minLen;
1.2915 + }));
1.2916 + }
1.2917 +
1.2918 + var inEdges = graph.inEdges(u, v);
1.2919 + if (inEdges.length > 0) {
1.2920 + return -util.max(inEdges.map(function(e) {
1.2921 + return graph.edge(e).minLen;
1.2922 + }));
1.2923 + }
1.2924 +}
1.2925 +
1.2926 +},{"../util":26,"./rankUtil":24}],26:[function(require,module,exports){
1.2927 +/*
1.2928 + * Returns the smallest value in the array.
1.2929 + */
1.2930 +exports.min = function(values) {
1.2931 + return Math.min.apply(Math, values);
1.2932 +};
1.2933 +
1.2934 +/*
1.2935 + * Returns the largest value in the array.
1.2936 + */
1.2937 +exports.max = function(values) {
1.2938 + return Math.max.apply(Math, values);
1.2939 +};
1.2940 +
1.2941 +/*
1.2942 + * Returns `true` only if `f(x)` is `true` for all `x` in `xs`. Otherwise
1.2943 + * returns `false`. This function will return immediately if it finds a
1.2944 + * case where `f(x)` does not hold.
1.2945 + */
1.2946 +exports.all = function(xs, f) {
1.2947 + for (var i = 0; i < xs.length; ++i) {
1.2948 + if (!f(xs[i])) {
1.2949 + return false;
1.2950 + }
1.2951 + }
1.2952 + return true;
1.2953 +};
1.2954 +
1.2955 +/*
1.2956 + * Accumulates the sum of elements in the given array using the `+` operator.
1.2957 + */
1.2958 +exports.sum = function(values) {
1.2959 + return values.reduce(function(acc, x) { return acc + x; }, 0);
1.2960 +};
1.2961 +
1.2962 +/*
1.2963 + * Returns an array of all values in the given object.
1.2964 + */
1.2965 +exports.values = function(obj) {
1.2966 + return Object.keys(obj).map(function(k) { return obj[k]; });
1.2967 +};
1.2968 +
1.2969 +exports.shuffle = function(array) {
1.2970 + for (i = array.length - 1; i > 0; --i) {
1.2971 + var j = Math.floor(Math.random() * (i + 1));
1.2972 + var aj = array[j];
1.2973 + array[j] = array[i];
1.2974 + array[i] = aj;
1.2975 + }
1.2976 +};
1.2977 +
1.2978 +exports.propertyAccessor = function(self, config, field, setHook) {
1.2979 + return function(x) {
1.2980 + if (!arguments.length) return config[field];
1.2981 + config[field] = x;
1.2982 + if (setHook) setHook(x);
1.2983 + return self;
1.2984 + };
1.2985 +};
1.2986 +
1.2987 +/*
1.2988 + * Given a layered, directed graph with `rank` and `order` node attributes,
1.2989 + * this function returns an array of ordered ranks. Each rank contains an array
1.2990 + * of the ids of the nodes in that rank in the order specified by the `order`
1.2991 + * attribute.
1.2992 + */
1.2993 +exports.ordering = function(g) {
1.2994 + var ordering = [];
1.2995 + g.eachNode(function(u, value) {
1.2996 + var rank = ordering[value.rank] || (ordering[value.rank] = []);
1.2997 + rank[value.order] = u;
1.2998 + });
1.2999 + return ordering;
1.3000 +};
1.3001 +
1.3002 +/*
1.3003 + * A filter that can be used with `filterNodes` to get a graph that only
1.3004 + * includes nodes that do not contain others nodes.
1.3005 + */
1.3006 +exports.filterNonSubgraphs = function(g) {
1.3007 + return function(u) {
1.3008 + return g.children(u).length === 0;
1.3009 + };
1.3010 +};
1.3011 +
1.3012 +/*
1.3013 + * Returns a new function that wraps `func` with a timer. The wrapper logs the
1.3014 + * time it takes to execute the function.
1.3015 + *
1.3016 + * The timer will be enabled provided `log.level >= 1`.
1.3017 + */
1.3018 +function time(name, func) {
1.3019 + return function() {
1.3020 + var start = new Date().getTime();
1.3021 + try {
1.3022 + return func.apply(null, arguments);
1.3023 + } finally {
1.3024 + log(1, name + ' time: ' + (new Date().getTime() - start) + 'ms');
1.3025 + }
1.3026 + };
1.3027 +}
1.3028 +time.enabled = false;
1.3029 +
1.3030 +exports.time = time;
1.3031 +
1.3032 +/*
1.3033 + * A global logger with the specification `log(level, message, ...)` that
1.3034 + * will log a message to the console if `log.level >= level`.
1.3035 + */
1.3036 +function log(level) {
1.3037 + if (log.level >= level) {
1.3038 + console.log.apply(console, Array.prototype.slice.call(arguments, 1));
1.3039 + }
1.3040 +}
1.3041 +log.level = 0;
1.3042 +
1.3043 +exports.log = log;
1.3044 +
1.3045 +},{}],27:[function(require,module,exports){
1.3046 +module.exports = '0.4.5';
1.3047 +
1.3048 +},{}],28:[function(require,module,exports){
1.3049 +exports.Graph = require("./lib/Graph");
1.3050 +exports.Digraph = require("./lib/Digraph");
1.3051 +exports.CGraph = require("./lib/CGraph");
1.3052 +exports.CDigraph = require("./lib/CDigraph");
1.3053 +require("./lib/graph-converters");
1.3054 +
1.3055 +exports.alg = {
1.3056 + isAcyclic: require("./lib/alg/isAcyclic"),
1.3057 + components: require("./lib/alg/components"),
1.3058 + dijkstra: require("./lib/alg/dijkstra"),
1.3059 + dijkstraAll: require("./lib/alg/dijkstraAll"),
1.3060 + findCycles: require("./lib/alg/findCycles"),
1.3061 + floydWarshall: require("./lib/alg/floydWarshall"),
1.3062 + postorder: require("./lib/alg/postorder"),
1.3063 + preorder: require("./lib/alg/preorder"),
1.3064 + prim: require("./lib/alg/prim"),
1.3065 + tarjan: require("./lib/alg/tarjan"),
1.3066 + topsort: require("./lib/alg/topsort")
1.3067 +};
1.3068 +
1.3069 +exports.converter = {
1.3070 + json: require("./lib/converter/json.js")
1.3071 +};
1.3072 +
1.3073 +var filter = require("./lib/filter");
1.3074 +exports.filter = {
1.3075 + all: filter.all,
1.3076 + nodesFromList: filter.nodesFromList
1.3077 +};
1.3078 +
1.3079 +exports.version = require("./lib/version");
1.3080 +
1.3081 +},{"./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){
1.3082 +/* jshint -W079 */
1.3083 +var Set = require("cp-data").Set;
1.3084 +/* jshint +W079 */
1.3085 +
1.3086 +module.exports = BaseGraph;
1.3087 +
1.3088 +function BaseGraph() {
1.3089 + // The value assigned to the graph itself.
1.3090 + this._value = undefined;
1.3091 +
1.3092 + // Map of node id -> { id, value }
1.3093 + this._nodes = {};
1.3094 +
1.3095 + // Map of edge id -> { id, u, v, value }
1.3096 + this._edges = {};
1.3097 +
1.3098 + // Used to generate a unique id in the graph
1.3099 + this._nextId = 0;
1.3100 +}
1.3101 +
1.3102 +// Number of nodes
1.3103 +BaseGraph.prototype.order = function() {
1.3104 + return Object.keys(this._nodes).length;
1.3105 +};
1.3106 +
1.3107 +// Number of edges
1.3108 +BaseGraph.prototype.size = function() {
1.3109 + return Object.keys(this._edges).length;
1.3110 +};
1.3111 +
1.3112 +// Accessor for graph level value
1.3113 +BaseGraph.prototype.graph = function(value) {
1.3114 + if (arguments.length === 0) {
1.3115 + return this._value;
1.3116 + }
1.3117 + this._value = value;
1.3118 +};
1.3119 +
1.3120 +BaseGraph.prototype.hasNode = function(u) {
1.3121 + return u in this._nodes;
1.3122 +};
1.3123 +
1.3124 +BaseGraph.prototype.node = function(u, value) {
1.3125 + var node = this._strictGetNode(u);
1.3126 + if (arguments.length === 1) {
1.3127 + return node.value;
1.3128 + }
1.3129 + node.value = value;
1.3130 +};
1.3131 +
1.3132 +BaseGraph.prototype.nodes = function() {
1.3133 + var nodes = [];
1.3134 + this.eachNode(function(id) { nodes.push(id); });
1.3135 + return nodes;
1.3136 +};
1.3137 +
1.3138 +BaseGraph.prototype.eachNode = function(func) {
1.3139 + for (var k in this._nodes) {
1.3140 + var node = this._nodes[k];
1.3141 + func(node.id, node.value);
1.3142 + }
1.3143 +};
1.3144 +
1.3145 +BaseGraph.prototype.hasEdge = function(e) {
1.3146 + return e in this._edges;
1.3147 +};
1.3148 +
1.3149 +BaseGraph.prototype.edge = function(e, value) {
1.3150 + var edge = this._strictGetEdge(e);
1.3151 + if (arguments.length === 1) {
1.3152 + return edge.value;
1.3153 + }
1.3154 + edge.value = value;
1.3155 +};
1.3156 +
1.3157 +BaseGraph.prototype.edges = function() {
1.3158 + var es = [];
1.3159 + this.eachEdge(function(id) { es.push(id); });
1.3160 + return es;
1.3161 +};
1.3162 +
1.3163 +BaseGraph.prototype.eachEdge = function(func) {
1.3164 + for (var k in this._edges) {
1.3165 + var edge = this._edges[k];
1.3166 + func(edge.id, edge.u, edge.v, edge.value);
1.3167 + }
1.3168 +};
1.3169 +
1.3170 +BaseGraph.prototype.incidentNodes = function(e) {
1.3171 + var edge = this._strictGetEdge(e);
1.3172 + return [edge.u, edge.v];
1.3173 +};
1.3174 +
1.3175 +BaseGraph.prototype.addNode = function(u, value) {
1.3176 + if (u === undefined || u === null) {
1.3177 + do {
1.3178 + u = "_" + (++this._nextId);
1.3179 + } while (this.hasNode(u));
1.3180 + } else if (this.hasNode(u)) {
1.3181 + throw new Error("Graph already has node '" + u + "'");
1.3182 + }
1.3183 + this._nodes[u] = { id: u, value: value };
1.3184 + return u;
1.3185 +};
1.3186 +
1.3187 +BaseGraph.prototype.delNode = function(u) {
1.3188 + this._strictGetNode(u);
1.3189 + this.incidentEdges(u).forEach(function(e) { this.delEdge(e); }, this);
1.3190 + delete this._nodes[u];
1.3191 +};
1.3192 +
1.3193 +// inMap and outMap are opposite sides of an incidence map. For example, for
1.3194 +// Graph these would both come from the _incidentEdges map, while for Digraph
1.3195 +// they would come from _inEdges and _outEdges.
1.3196 +BaseGraph.prototype._addEdge = function(e, u, v, value, inMap, outMap) {
1.3197 + this._strictGetNode(u);
1.3198 + this._strictGetNode(v);
1.3199 +
1.3200 + if (e === undefined || e === null) {
1.3201 + do {
1.3202 + e = "_" + (++this._nextId);
1.3203 + } while (this.hasEdge(e));
1.3204 + }
1.3205 + else if (this.hasEdge(e)) {
1.3206 + throw new Error("Graph already has edge '" + e + "'");
1.3207 + }
1.3208 +
1.3209 + this._edges[e] = { id: e, u: u, v: v, value: value };
1.3210 + addEdgeToMap(inMap[v], u, e);
1.3211 + addEdgeToMap(outMap[u], v, e);
1.3212 +
1.3213 + return e;
1.3214 +};
1.3215 +
1.3216 +// See note for _addEdge regarding inMap and outMap.
1.3217 +BaseGraph.prototype._delEdge = function(e, inMap, outMap) {
1.3218 + var edge = this._strictGetEdge(e);
1.3219 + delEdgeFromMap(inMap[edge.v], edge.u, e);
1.3220 + delEdgeFromMap(outMap[edge.u], edge.v, e);
1.3221 + delete this._edges[e];
1.3222 +};
1.3223 +
1.3224 +BaseGraph.prototype.copy = function() {
1.3225 + var copy = new this.constructor();
1.3226 + copy.graph(this.graph());
1.3227 + this.eachNode(function(u, value) { copy.addNode(u, value); });
1.3228 + this.eachEdge(function(e, u, v, value) { copy.addEdge(e, u, v, value); });
1.3229 + copy._nextId = this._nextId;
1.3230 + return copy;
1.3231 +};
1.3232 +
1.3233 +BaseGraph.prototype.filterNodes = function(filter) {
1.3234 + var copy = new this.constructor();
1.3235 + copy.graph(this.graph());
1.3236 + this.eachNode(function(u, value) {
1.3237 + if (filter(u)) {
1.3238 + copy.addNode(u, value);
1.3239 + }
1.3240 + });
1.3241 + this.eachEdge(function(e, u, v, value) {
1.3242 + if (copy.hasNode(u) && copy.hasNode(v)) {
1.3243 + copy.addEdge(e, u, v, value);
1.3244 + }
1.3245 + });
1.3246 + return copy;
1.3247 +};
1.3248 +
1.3249 +BaseGraph.prototype._strictGetNode = function(u) {
1.3250 + var node = this._nodes[u];
1.3251 + if (node === undefined) {
1.3252 + throw new Error("Node '" + u + "' is not in graph");
1.3253 + }
1.3254 + return node;
1.3255 +};
1.3256 +
1.3257 +BaseGraph.prototype._strictGetEdge = function(e) {
1.3258 + var edge = this._edges[e];
1.3259 + if (edge === undefined) {
1.3260 + throw new Error("Edge '" + e + "' is not in graph");
1.3261 + }
1.3262 + return edge;
1.3263 +};
1.3264 +
1.3265 +function addEdgeToMap(map, v, e) {
1.3266 + (map[v] || (map[v] = new Set())).add(e);
1.3267 +}
1.3268 +
1.3269 +function delEdgeFromMap(map, v, e) {
1.3270 + var vEntry = map[v];
1.3271 + vEntry.remove(e);
1.3272 + if (vEntry.size() === 0) {
1.3273 + delete map[v];
1.3274 + }
1.3275 +}
1.3276 +
1.3277 +
1.3278 +},{"cp-data":5}],30:[function(require,module,exports){
1.3279 +var Digraph = require("./Digraph"),
1.3280 + compoundify = require("./compoundify");
1.3281 +
1.3282 +var CDigraph = compoundify(Digraph);
1.3283 +
1.3284 +module.exports = CDigraph;
1.3285 +
1.3286 +CDigraph.fromDigraph = function(src) {
1.3287 + var g = new CDigraph(),
1.3288 + graphValue = src.graph();
1.3289 +
1.3290 + if (graphValue !== undefined) {
1.3291 + g.graph(graphValue);
1.3292 + }
1.3293 +
1.3294 + src.eachNode(function(u, value) {
1.3295 + if (value === undefined) {
1.3296 + g.addNode(u);
1.3297 + } else {
1.3298 + g.addNode(u, value);
1.3299 + }
1.3300 + });
1.3301 + src.eachEdge(function(e, u, v, value) {
1.3302 + if (value === undefined) {
1.3303 + g.addEdge(null, u, v);
1.3304 + } else {
1.3305 + g.addEdge(null, u, v, value);
1.3306 + }
1.3307 + });
1.3308 + return g;
1.3309 +};
1.3310 +
1.3311 +CDigraph.prototype.toString = function() {
1.3312 + return "CDigraph " + JSON.stringify(this, null, 2);
1.3313 +};
1.3314 +
1.3315 +},{"./Digraph":32,"./compoundify":45}],31:[function(require,module,exports){
1.3316 +var Graph = require("./Graph"),
1.3317 + compoundify = require("./compoundify");
1.3318 +
1.3319 +var CGraph = compoundify(Graph);
1.3320 +
1.3321 +module.exports = CGraph;
1.3322 +
1.3323 +CGraph.fromGraph = function(src) {
1.3324 + var g = new CGraph(),
1.3325 + graphValue = src.graph();
1.3326 +
1.3327 + if (graphValue !== undefined) {
1.3328 + g.graph(graphValue);
1.3329 + }
1.3330 +
1.3331 + src.eachNode(function(u, value) {
1.3332 + if (value === undefined) {
1.3333 + g.addNode(u);
1.3334 + } else {
1.3335 + g.addNode(u, value);
1.3336 + }
1.3337 + });
1.3338 + src.eachEdge(function(e, u, v, value) {
1.3339 + if (value === undefined) {
1.3340 + g.addEdge(null, u, v);
1.3341 + } else {
1.3342 + g.addEdge(null, u, v, value);
1.3343 + }
1.3344 + });
1.3345 + return g;
1.3346 +};
1.3347 +
1.3348 +CGraph.prototype.toString = function() {
1.3349 + return "CGraph " + JSON.stringify(this, null, 2);
1.3350 +};
1.3351 +
1.3352 +},{"./Graph":33,"./compoundify":45}],32:[function(require,module,exports){
1.3353 +/*
1.3354 + * This file is organized with in the following order:
1.3355 + *
1.3356 + * Exports
1.3357 + * Graph constructors
1.3358 + * Graph queries (e.g. nodes(), edges()
1.3359 + * Graph mutators
1.3360 + * Helper functions
1.3361 + */
1.3362 +
1.3363 +var util = require("./util"),
1.3364 + BaseGraph = require("./BaseGraph"),
1.3365 +/* jshint -W079 */
1.3366 + Set = require("cp-data").Set;
1.3367 +/* jshint +W079 */
1.3368 +
1.3369 +module.exports = Digraph;
1.3370 +
1.3371 +/*
1.3372 + * Constructor to create a new directed multi-graph.
1.3373 + */
1.3374 +function Digraph() {
1.3375 + BaseGraph.call(this);
1.3376 +
1.3377 + /*! Map of sourceId -> {targetId -> Set of edge ids} */
1.3378 + this._inEdges = {};
1.3379 +
1.3380 + /*! Map of targetId -> {sourceId -> Set of edge ids} */
1.3381 + this._outEdges = {};
1.3382 +}
1.3383 +
1.3384 +Digraph.prototype = new BaseGraph();
1.3385 +Digraph.prototype.constructor = Digraph;
1.3386 +
1.3387 +/*
1.3388 + * Always returns `true`.
1.3389 + */
1.3390 +Digraph.prototype.isDirected = function() {
1.3391 + return true;
1.3392 +};
1.3393 +
1.3394 +/*
1.3395 + * Returns all successors of the node with the id `u`. That is, all nodes
1.3396 + * that have the node `u` as their source are returned.
1.3397 + *
1.3398 + * If no node `u` exists in the graph this function throws an Error.
1.3399 + *
1.3400 + * @param {String} u a node id
1.3401 + */
1.3402 +Digraph.prototype.successors = function(u) {
1.3403 + this._strictGetNode(u);
1.3404 + return Object.keys(this._outEdges[u])
1.3405 + .map(function(v) { return this._nodes[v].id; }, this);
1.3406 +};
1.3407 +
1.3408 +/*
1.3409 + * Returns all predecessors of the node with the id `u`. That is, all nodes
1.3410 + * that have the node `u` as their target are returned.
1.3411 + *
1.3412 + * If no node `u` exists in the graph this function throws an Error.
1.3413 + *
1.3414 + * @param {String} u a node id
1.3415 + */
1.3416 +Digraph.prototype.predecessors = function(u) {
1.3417 + this._strictGetNode(u);
1.3418 + return Object.keys(this._inEdges[u])
1.3419 + .map(function(v) { return this._nodes[v].id; }, this);
1.3420 +};
1.3421 +
1.3422 +/*
1.3423 + * Returns all nodes that are adjacent to the node with the id `u`. In other
1.3424 + * words, this function returns the set of all successors and predecessors of
1.3425 + * node `u`.
1.3426 + *
1.3427 + * @param {String} u a node id
1.3428 + */
1.3429 +Digraph.prototype.neighbors = function(u) {
1.3430 + return Set.union([this.successors(u), this.predecessors(u)]).keys();
1.3431 +};
1.3432 +
1.3433 +/*
1.3434 + * Returns all nodes in the graph that have no in-edges.
1.3435 + */
1.3436 +Digraph.prototype.sources = function() {
1.3437 + var self = this;
1.3438 + return this._filterNodes(function(u) {
1.3439 + // This could have better space characteristics if we had an inDegree function.
1.3440 + return self.inEdges(u).length === 0;
1.3441 + });
1.3442 +};
1.3443 +
1.3444 +/*
1.3445 + * Returns all nodes in the graph that have no out-edges.
1.3446 + */
1.3447 +Digraph.prototype.sinks = function() {
1.3448 + var self = this;
1.3449 + return this._filterNodes(function(u) {
1.3450 + // This could have better space characteristics if we have an outDegree function.
1.3451 + return self.outEdges(u).length === 0;
1.3452 + });
1.3453 +};
1.3454 +
1.3455 +/*
1.3456 + * Returns the source node incident on the edge identified by the id `e`. If no
1.3457 + * such edge exists in the graph this function throws an Error.
1.3458 + *
1.3459 + * @param {String} e an edge id
1.3460 + */
1.3461 +Digraph.prototype.source = function(e) {
1.3462 + return this._strictGetEdge(e).u;
1.3463 +};
1.3464 +
1.3465 +/*
1.3466 + * Returns the target node incident on the edge identified by the id `e`. If no
1.3467 + * such edge exists in the graph this function throws an Error.
1.3468 + *
1.3469 + * @param {String} e an edge id
1.3470 + */
1.3471 +Digraph.prototype.target = function(e) {
1.3472 + return this._strictGetEdge(e).v;
1.3473 +};
1.3474 +
1.3475 +/*
1.3476 + * Returns an array of ids for all edges in the graph that have the node
1.3477 + * `target` as their target. If the node `target` is not in the graph this
1.3478 + * function raises an Error.
1.3479 + *
1.3480 + * Optionally a `source` node can also be specified. This causes the results
1.3481 + * to be filtered such that only edges from `source` to `target` are included.
1.3482 + * If the node `source` is specified but is not in the graph then this function
1.3483 + * raises an Error.
1.3484 + *
1.3485 + * @param {String} target the target node id
1.3486 + * @param {String} [source] an optional source node id
1.3487 + */
1.3488 +Digraph.prototype.inEdges = function(target, source) {
1.3489 + this._strictGetNode(target);
1.3490 + var results = Set.union(util.values(this._inEdges[target])).keys();
1.3491 + if (arguments.length > 1) {
1.3492 + this._strictGetNode(source);
1.3493 + results = results.filter(function(e) { return this.source(e) === source; }, this);
1.3494 + }
1.3495 + return results;
1.3496 +};
1.3497 +
1.3498 +/*
1.3499 + * Returns an array of ids for all edges in the graph that have the node
1.3500 + * `source` as their source. If the node `source` is not in the graph this
1.3501 + * function raises an Error.
1.3502 + *
1.3503 + * Optionally a `target` node may also be specified. This causes the results
1.3504 + * to be filtered such that only edges from `source` to `target` are included.
1.3505 + * If the node `target` is specified but is not in the graph then this function
1.3506 + * raises an Error.
1.3507 + *
1.3508 + * @param {String} source the source node id
1.3509 + * @param {String} [target] an optional target node id
1.3510 + */
1.3511 +Digraph.prototype.outEdges = function(source, target) {
1.3512 + this._strictGetNode(source);
1.3513 + var results = Set.union(util.values(this._outEdges[source])).keys();
1.3514 + if (arguments.length > 1) {
1.3515 + this._strictGetNode(target);
1.3516 + results = results.filter(function(e) { return this.target(e) === target; }, this);
1.3517 + }
1.3518 + return results;
1.3519 +};
1.3520 +
1.3521 +/*
1.3522 + * Returns an array of ids for all edges in the graph that have the `u` as
1.3523 + * their source or their target. If the node `u` is not in the graph this
1.3524 + * function raises an Error.
1.3525 + *
1.3526 + * Optionally a `v` node may also be specified. This causes the results to be
1.3527 + * filtered such that only edges between `u` and `v` - in either direction -
1.3528 + * are included. IF the node `v` is specified but not in the graph then this
1.3529 + * function raises an Error.
1.3530 + *
1.3531 + * @param {String} u the node for which to find incident edges
1.3532 + * @param {String} [v] option node that must be adjacent to `u`
1.3533 + */
1.3534 +Digraph.prototype.incidentEdges = function(u, v) {
1.3535 + if (arguments.length > 1) {
1.3536 + return Set.union([this.outEdges(u, v), this.outEdges(v, u)]).keys();
1.3537 + } else {
1.3538 + return Set.union([this.inEdges(u), this.outEdges(u)]).keys();
1.3539 + }
1.3540 +};
1.3541 +
1.3542 +/*
1.3543 + * Returns a string representation of this graph.
1.3544 + */
1.3545 +Digraph.prototype.toString = function() {
1.3546 + return "Digraph " + JSON.stringify(this, null, 2);
1.3547 +};
1.3548 +
1.3549 +/*
1.3550 + * Adds a new node with the id `u` to the graph and assigns it the value
1.3551 + * `value`. If a node with the id is already a part of the graph this function
1.3552 + * throws an Error.
1.3553 + *
1.3554 + * @param {String} u a node id
1.3555 + * @param {Object} [value] an optional value to attach to the node
1.3556 + */
1.3557 +Digraph.prototype.addNode = function(u, value) {
1.3558 + u = BaseGraph.prototype.addNode.call(this, u, value);
1.3559 + this._inEdges[u] = {};
1.3560 + this._outEdges[u] = {};
1.3561 + return u;
1.3562 +};
1.3563 +
1.3564 +/*
1.3565 + * Removes a node from the graph that has the id `u`. Any edges incident on the
1.3566 + * node are also removed. If the graph does not contain a node with the id this
1.3567 + * function will throw an Error.
1.3568 + *
1.3569 + * @param {String} u a node id
1.3570 + */
1.3571 +Digraph.prototype.delNode = function(u) {
1.3572 + BaseGraph.prototype.delNode.call(this, u);
1.3573 + delete this._inEdges[u];
1.3574 + delete this._outEdges[u];
1.3575 +};
1.3576 +
1.3577 +/*
1.3578 + * Adds a new edge to the graph with the id `e` from a node with the id `source`
1.3579 + * to a node with an id `target` and assigns it the value `value`. This graph
1.3580 + * allows more than one edge from `source` to `target` as long as the id `e`
1.3581 + * is unique in the set of edges. If `e` is `null` the graph will assign a
1.3582 + * unique identifier to the edge.
1.3583 + *
1.3584 + * If `source` or `target` are not present in the graph this function will
1.3585 + * throw an Error.
1.3586 + *
1.3587 + * @param {String} [e] an edge id
1.3588 + * @param {String} source the source node id
1.3589 + * @param {String} target the target node id
1.3590 + * @param {Object} [value] an optional value to attach to the edge
1.3591 + */
1.3592 +Digraph.prototype.addEdge = function(e, source, target, value) {
1.3593 + return BaseGraph.prototype._addEdge.call(this, e, source, target, value,
1.3594 + this._inEdges, this._outEdges);
1.3595 +};
1.3596 +
1.3597 +/*
1.3598 + * Removes an edge in the graph with the id `e`. If no edge in the graph has
1.3599 + * the id `e` this function will throw an Error.
1.3600 + *
1.3601 + * @param {String} e an edge id
1.3602 + */
1.3603 +Digraph.prototype.delEdge = function(e) {
1.3604 + BaseGraph.prototype._delEdge.call(this, e, this._inEdges, this._outEdges);
1.3605 +};
1.3606 +
1.3607 +// Unlike BaseGraph.filterNodes, this helper just returns nodes that
1.3608 +// satisfy a predicate.
1.3609 +Digraph.prototype._filterNodes = function(pred) {
1.3610 + var filtered = [];
1.3611 + this.eachNode(function(u) {
1.3612 + if (pred(u)) {
1.3613 + filtered.push(u);
1.3614 + }
1.3615 + });
1.3616 + return filtered;
1.3617 +};
1.3618 +
1.3619 +
1.3620 +},{"./BaseGraph":29,"./util":49,"cp-data":5}],33:[function(require,module,exports){
1.3621 +/*
1.3622 + * This file is organized with in the following order:
1.3623 + *
1.3624 + * Exports
1.3625 + * Graph constructors
1.3626 + * Graph queries (e.g. nodes(), edges()
1.3627 + * Graph mutators
1.3628 + * Helper functions
1.3629 + */
1.3630 +
1.3631 +var util = require("./util"),
1.3632 + BaseGraph = require("./BaseGraph"),
1.3633 +/* jshint -W079 */
1.3634 + Set = require("cp-data").Set;
1.3635 +/* jshint +W079 */
1.3636 +
1.3637 +module.exports = Graph;
1.3638 +
1.3639 +/*
1.3640 + * Constructor to create a new undirected multi-graph.
1.3641 + */
1.3642 +function Graph() {
1.3643 + BaseGraph.call(this);
1.3644 +
1.3645 + /*! Map of nodeId -> { otherNodeId -> Set of edge ids } */
1.3646 + this._incidentEdges = {};
1.3647 +}
1.3648 +
1.3649 +Graph.prototype = new BaseGraph();
1.3650 +Graph.prototype.constructor = Graph;
1.3651 +
1.3652 +/*
1.3653 + * Always returns `false`.
1.3654 + */
1.3655 +Graph.prototype.isDirected = function() {
1.3656 + return false;
1.3657 +};
1.3658 +
1.3659 +/*
1.3660 + * Returns all nodes that are adjacent to the node with the id `u`.
1.3661 + *
1.3662 + * @param {String} u a node id
1.3663 + */
1.3664 +Graph.prototype.neighbors = function(u) {
1.3665 + this._strictGetNode(u);
1.3666 + return Object.keys(this._incidentEdges[u])
1.3667 + .map(function(v) { return this._nodes[v].id; }, this);
1.3668 +};
1.3669 +
1.3670 +/*
1.3671 + * Returns an array of ids for all edges in the graph that are incident on `u`.
1.3672 + * If the node `u` is not in the graph this function raises an Error.
1.3673 + *
1.3674 + * Optionally a `v` node may also be specified. This causes the results to be
1.3675 + * filtered such that only edges between `u` and `v` are included. If the node
1.3676 + * `v` is specified but not in the graph then this function raises an Error.
1.3677 + *
1.3678 + * @param {String} u the node for which to find incident edges
1.3679 + * @param {String} [v] option node that must be adjacent to `u`
1.3680 + */
1.3681 +Graph.prototype.incidentEdges = function(u, v) {
1.3682 + this._strictGetNode(u);
1.3683 + if (arguments.length > 1) {
1.3684 + this._strictGetNode(v);
1.3685 + return v in this._incidentEdges[u] ? this._incidentEdges[u][v].keys() : [];
1.3686 + } else {
1.3687 + return Set.union(util.values(this._incidentEdges[u])).keys();
1.3688 + }
1.3689 +};
1.3690 +
1.3691 +/*
1.3692 + * Returns a string representation of this graph.
1.3693 + */
1.3694 +Graph.prototype.toString = function() {
1.3695 + return "Graph " + JSON.stringify(this, null, 2);
1.3696 +};
1.3697 +
1.3698 +/*
1.3699 + * Adds a new node with the id `u` to the graph and assigns it the value
1.3700 + * `value`. If a node with the id is already a part of the graph this function
1.3701 + * throws an Error.
1.3702 + *
1.3703 + * @param {String} u a node id
1.3704 + * @param {Object} [value] an optional value to attach to the node
1.3705 + */
1.3706 +Graph.prototype.addNode = function(u, value) {
1.3707 + u = BaseGraph.prototype.addNode.call(this, u, value);
1.3708 + this._incidentEdges[u] = {};
1.3709 + return u;
1.3710 +};
1.3711 +
1.3712 +/*
1.3713 + * Removes a node from the graph that has the id `u`. Any edges incident on the
1.3714 + * node are also removed. If the graph does not contain a node with the id this
1.3715 + * function will throw an Error.
1.3716 + *
1.3717 + * @param {String} u a node id
1.3718 + */
1.3719 +Graph.prototype.delNode = function(u) {
1.3720 + BaseGraph.prototype.delNode.call(this, u);
1.3721 + delete this._incidentEdges[u];
1.3722 +};
1.3723 +
1.3724 +/*
1.3725 + * Adds a new edge to the graph with the id `e` between a node with the id `u`
1.3726 + * and a node with an id `v` and assigns it the value `value`. This graph
1.3727 + * allows more than one edge between `u` and `v` as long as the id `e`
1.3728 + * is unique in the set of edges. If `e` is `null` the graph will assign a
1.3729 + * unique identifier to the edge.
1.3730 + *
1.3731 + * If `u` or `v` are not present in the graph this function will throw an
1.3732 + * Error.
1.3733 + *
1.3734 + * @param {String} [e] an edge id
1.3735 + * @param {String} u the node id of one of the adjacent nodes
1.3736 + * @param {String} v the node id of the other adjacent node
1.3737 + * @param {Object} [value] an optional value to attach to the edge
1.3738 + */
1.3739 +Graph.prototype.addEdge = function(e, u, v, value) {
1.3740 + return BaseGraph.prototype._addEdge.call(this, e, u, v, value,
1.3741 + this._incidentEdges, this._incidentEdges);
1.3742 +};
1.3743 +
1.3744 +/*
1.3745 + * Removes an edge in the graph with the id `e`. If no edge in the graph has
1.3746 + * the id `e` this function will throw an Error.
1.3747 + *
1.3748 + * @param {String} e an edge id
1.3749 + */
1.3750 +Graph.prototype.delEdge = function(e) {
1.3751 + BaseGraph.prototype._delEdge.call(this, e, this._incidentEdges, this._incidentEdges);
1.3752 +};
1.3753 +
1.3754 +
1.3755 +},{"./BaseGraph":29,"./util":49,"cp-data":5}],34:[function(require,module,exports){
1.3756 +/* jshint -W079 */
1.3757 +var Set = require("cp-data").Set;
1.3758 +/* jshint +W079 */
1.3759 +
1.3760 +module.exports = components;
1.3761 +
1.3762 +/**
1.3763 + * Finds all [connected components][] in a graph and returns an array of these
1.3764 + * components. Each component is itself an array that contains the ids of nodes
1.3765 + * in the component.
1.3766 + *
1.3767 + * This function only works with undirected Graphs.
1.3768 + *
1.3769 + * [connected components]: http://en.wikipedia.org/wiki/Connected_component_(graph_theory)
1.3770 + *
1.3771 + * @param {Graph} g the graph to search for components
1.3772 + */
1.3773 +function components(g) {
1.3774 + var results = [];
1.3775 + var visited = new Set();
1.3776 +
1.3777 + function dfs(v, component) {
1.3778 + if (!visited.has(v)) {
1.3779 + visited.add(v);
1.3780 + component.push(v);
1.3781 + g.neighbors(v).forEach(function(w) {
1.3782 + dfs(w, component);
1.3783 + });
1.3784 + }
1.3785 + }
1.3786 +
1.3787 + g.nodes().forEach(function(v) {
1.3788 + var component = [];
1.3789 + dfs(v, component);
1.3790 + if (component.length > 0) {
1.3791 + results.push(component);
1.3792 + }
1.3793 + });
1.3794 +
1.3795 + return results;
1.3796 +}
1.3797 +
1.3798 +},{"cp-data":5}],35:[function(require,module,exports){
1.3799 +var PriorityQueue = require("cp-data").PriorityQueue;
1.3800 +
1.3801 +module.exports = dijkstra;
1.3802 +
1.3803 +/**
1.3804 + * This function is an implementation of [Dijkstra's algorithm][] which finds
1.3805 + * the shortest path from **source** to all other nodes in **g**. This
1.3806 + * function returns a map of `u -> { distance, predecessor }`. The distance
1.3807 + * property holds the sum of the weights from **source** to `u` along the
1.3808 + * shortest path or `Number.POSITIVE_INFINITY` if there is no path from
1.3809 + * **source**. The predecessor property can be used to walk the individual
1.3810 + * elements of the path from **source** to **u** in reverse order.
1.3811 + *
1.3812 + * This function takes an optional `weightFunc(e)` which returns the
1.3813 + * weight of the edge `e`. If no weightFunc is supplied then each edge is
1.3814 + * assumed to have a weight of 1. This function throws an Error if any of
1.3815 + * the traversed edges have a negative edge weight.
1.3816 + *
1.3817 + * This function takes an optional `incidentFunc(u)` which returns the ids of
1.3818 + * all edges incident to the node `u` for the purposes of shortest path
1.3819 + * traversal. By default this function uses the `g.outEdges` for Digraphs and
1.3820 + * `g.incidentEdges` for Graphs.
1.3821 + *
1.3822 + * This function takes `O((|E| + |V|) * log |V|)` time.
1.3823 + *
1.3824 + * [Dijkstra's algorithm]: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
1.3825 + *
1.3826 + * @param {Graph} g the graph to search for shortest paths from **source**
1.3827 + * @param {Object} source the source from which to start the search
1.3828 + * @param {Function} [weightFunc] optional weight function
1.3829 + * @param {Function} [incidentFunc] optional incident function
1.3830 + */
1.3831 +function dijkstra(g, source, weightFunc, incidentFunc) {
1.3832 + var results = {},
1.3833 + pq = new PriorityQueue();
1.3834 +
1.3835 + function updateNeighbors(e) {
1.3836 + var incidentNodes = g.incidentNodes(e),
1.3837 + v = incidentNodes[0] !== u ? incidentNodes[0] : incidentNodes[1],
1.3838 + vEntry = results[v],
1.3839 + weight = weightFunc(e),
1.3840 + distance = uEntry.distance + weight;
1.3841 +
1.3842 + if (weight < 0) {
1.3843 + throw new Error("dijkstra does not allow negative edge weights. Bad edge: " + e + " Weight: " + weight);
1.3844 + }
1.3845 +
1.3846 + if (distance < vEntry.distance) {
1.3847 + vEntry.distance = distance;
1.3848 + vEntry.predecessor = u;
1.3849 + pq.decrease(v, distance);
1.3850 + }
1.3851 + }
1.3852 +
1.3853 + weightFunc = weightFunc || function() { return 1; };
1.3854 + incidentFunc = incidentFunc || (g.isDirected()
1.3855 + ? function(u) { return g.outEdges(u); }
1.3856 + : function(u) { return g.incidentEdges(u); });
1.3857 +
1.3858 + g.eachNode(function(u) {
1.3859 + var distance = u === source ? 0 : Number.POSITIVE_INFINITY;
1.3860 + results[u] = { distance: distance };
1.3861 + pq.add(u, distance);
1.3862 + });
1.3863 +
1.3864 + var u, uEntry;
1.3865 + while (pq.size() > 0) {
1.3866 + u = pq.removeMin();
1.3867 + uEntry = results[u];
1.3868 + if (uEntry.distance === Number.POSITIVE_INFINITY) {
1.3869 + break;
1.3870 + }
1.3871 +
1.3872 + incidentFunc(u).forEach(updateNeighbors);
1.3873 + }
1.3874 +
1.3875 + return results;
1.3876 +}
1.3877 +
1.3878 +},{"cp-data":5}],36:[function(require,module,exports){
1.3879 +var dijkstra = require("./dijkstra");
1.3880 +
1.3881 +module.exports = dijkstraAll;
1.3882 +
1.3883 +/**
1.3884 + * This function finds the shortest path from each node to every other
1.3885 + * reachable node in the graph. It is similar to [alg.dijkstra][], but
1.3886 + * instead of returning a single-source array, it returns a mapping of
1.3887 + * of `source -> alg.dijksta(g, source, weightFunc, incidentFunc)`.
1.3888 + *
1.3889 + * This function takes an optional `weightFunc(e)` which returns the
1.3890 + * weight of the edge `e`. If no weightFunc is supplied then each edge is
1.3891 + * assumed to have a weight of 1. This function throws an Error if any of
1.3892 + * the traversed edges have a negative edge weight.
1.3893 + *
1.3894 + * This function takes an optional `incidentFunc(u)` which returns the ids of
1.3895 + * all edges incident to the node `u` for the purposes of shortest path
1.3896 + * traversal. By default this function uses the `outEdges` function on the
1.3897 + * supplied graph.
1.3898 + *
1.3899 + * This function takes `O(|V| * (|E| + |V|) * log |V|)` time.
1.3900 + *
1.3901 + * [alg.dijkstra]: dijkstra.js.html#dijkstra
1.3902 + *
1.3903 + * @param {Graph} g the graph to search for shortest paths from **source**
1.3904 + * @param {Function} [weightFunc] optional weight function
1.3905 + * @param {Function} [incidentFunc] optional incident function
1.3906 + */
1.3907 +function dijkstraAll(g, weightFunc, incidentFunc) {
1.3908 + var results = {};
1.3909 + g.eachNode(function(u) {
1.3910 + results[u] = dijkstra(g, u, weightFunc, incidentFunc);
1.3911 + });
1.3912 + return results;
1.3913 +}
1.3914 +
1.3915 +},{"./dijkstra":35}],37:[function(require,module,exports){
1.3916 +var tarjan = require("./tarjan");
1.3917 +
1.3918 +module.exports = findCycles;
1.3919 +
1.3920 +/*
1.3921 + * Given a Digraph **g** this function returns all nodes that are part of a
1.3922 + * cycle. Since there may be more than one cycle in a graph this function
1.3923 + * returns an array of these cycles, where each cycle is itself represented
1.3924 + * by an array of ids for each node involved in that cycle.
1.3925 + *
1.3926 + * [alg.isAcyclic][] is more efficient if you only need to determine whether
1.3927 + * a graph has a cycle or not.
1.3928 + *
1.3929 + * [alg.isAcyclic]: isAcyclic.js.html#isAcyclic
1.3930 + *
1.3931 + * @param {Digraph} g the graph to search for cycles.
1.3932 + */
1.3933 +function findCycles(g) {
1.3934 + return tarjan(g).filter(function(cmpt) { return cmpt.length > 1; });
1.3935 +}
1.3936 +
1.3937 +},{"./tarjan":43}],38:[function(require,module,exports){
1.3938 +module.exports = floydWarshall;
1.3939 +
1.3940 +/**
1.3941 + * This function is an implementation of the [Floyd-Warshall algorithm][],
1.3942 + * which finds the shortest path from each node to every other reachable node
1.3943 + * in the graph. It is similar to [alg.dijkstraAll][], but it handles negative
1.3944 + * edge weights and is more efficient for some types of graphs. This function
1.3945 + * returns a map of `source -> { target -> { distance, predecessor }`. The
1.3946 + * distance property holds the sum of the weights from `source` to `target`
1.3947 + * along the shortest path of `Number.POSITIVE_INFINITY` if there is no path
1.3948 + * from `source`. The predecessor property can be used to walk the individual
1.3949 + * elements of the path from `source` to `target` in reverse order.
1.3950 + *
1.3951 + * This function takes an optional `weightFunc(e)` which returns the
1.3952 + * weight of the edge `e`. If no weightFunc is supplied then each edge is
1.3953 + * assumed to have a weight of 1.
1.3954 + *
1.3955 + * This function takes an optional `incidentFunc(u)` which returns the ids of
1.3956 + * all edges incident to the node `u` for the purposes of shortest path
1.3957 + * traversal. By default this function uses the `outEdges` function on the
1.3958 + * supplied graph.
1.3959 + *
1.3960 + * This algorithm takes O(|V|^3) time.
1.3961 + *
1.3962 + * [Floyd-Warshall algorithm]: https://en.wikipedia.org/wiki/Floyd-Warshall_algorithm
1.3963 + * [alg.dijkstraAll]: dijkstraAll.js.html#dijkstraAll
1.3964 + *
1.3965 + * @param {Graph} g the graph to search for shortest paths from **source**
1.3966 + * @param {Function} [weightFunc] optional weight function
1.3967 + * @param {Function} [incidentFunc] optional incident function
1.3968 + */
1.3969 +function floydWarshall(g, weightFunc, incidentFunc) {
1.3970 + var results = {},
1.3971 + nodes = g.nodes();
1.3972 +
1.3973 + weightFunc = weightFunc || function() { return 1; };
1.3974 + incidentFunc = incidentFunc || (g.isDirected()
1.3975 + ? function(u) { return g.outEdges(u); }
1.3976 + : function(u) { return g.incidentEdges(u); });
1.3977 +
1.3978 + nodes.forEach(function(u) {
1.3979 + results[u] = {};
1.3980 + results[u][u] = { distance: 0 };
1.3981 + nodes.forEach(function(v) {
1.3982 + if (u !== v) {
1.3983 + results[u][v] = { distance: Number.POSITIVE_INFINITY };
1.3984 + }
1.3985 + });
1.3986 + incidentFunc(u).forEach(function(e) {
1.3987 + var incidentNodes = g.incidentNodes(e),
1.3988 + v = incidentNodes[0] !== u ? incidentNodes[0] : incidentNodes[1],
1.3989 + d = weightFunc(e);
1.3990 + if (d < results[u][v].distance) {
1.3991 + results[u][v] = { distance: d, predecessor: u };
1.3992 + }
1.3993 + });
1.3994 + });
1.3995 +
1.3996 + nodes.forEach(function(k) {
1.3997 + var rowK = results[k];
1.3998 + nodes.forEach(function(i) {
1.3999 + var rowI = results[i];
1.4000 + nodes.forEach(function(j) {
1.4001 + var ik = rowI[k];
1.4002 + var kj = rowK[j];
1.4003 + var ij = rowI[j];
1.4004 + var altDistance = ik.distance + kj.distance;
1.4005 + if (altDistance < ij.distance) {
1.4006 + ij.distance = altDistance;
1.4007 + ij.predecessor = kj.predecessor;
1.4008 + }
1.4009 + });
1.4010 + });
1.4011 + });
1.4012 +
1.4013 + return results;
1.4014 +}
1.4015 +
1.4016 +},{}],39:[function(require,module,exports){
1.4017 +var topsort = require("./topsort");
1.4018 +
1.4019 +module.exports = isAcyclic;
1.4020 +
1.4021 +/*
1.4022 + * Given a Digraph **g** this function returns `true` if the graph has no
1.4023 + * cycles and returns `false` if it does. This algorithm returns as soon as it
1.4024 + * detects the first cycle.
1.4025 + *
1.4026 + * Use [alg.findCycles][] if you need the actual list of cycles in a graph.
1.4027 + *
1.4028 + * [alg.findCycles]: findCycles.js.html#findCycles
1.4029 + *
1.4030 + * @param {Digraph} g the graph to test for cycles
1.4031 + */
1.4032 +function isAcyclic(g) {
1.4033 + try {
1.4034 + topsort(g);
1.4035 + } catch (e) {
1.4036 + if (e instanceof topsort.CycleException) return false;
1.4037 + throw e;
1.4038 + }
1.4039 + return true;
1.4040 +}
1.4041 +
1.4042 +},{"./topsort":44}],40:[function(require,module,exports){
1.4043 +/* jshint -W079 */
1.4044 +var Set = require("cp-data").Set;
1.4045 +/* jshint +W079 */
1.4046 +
1.4047 +module.exports = postorder;
1.4048 +
1.4049 +// Postorder traversal of g, calling f for each visited node. Assumes the graph
1.4050 +// is a tree.
1.4051 +function postorder(g, root, f) {
1.4052 + var visited = new Set();
1.4053 + if (g.isDirected()) {
1.4054 + throw new Error("This function only works for undirected graphs");
1.4055 + }
1.4056 + function dfs(u, prev) {
1.4057 + if (visited.has(u)) {
1.4058 + throw new Error("The input graph is not a tree: " + g);
1.4059 + }
1.4060 + visited.add(u);
1.4061 + g.neighbors(u).forEach(function(v) {
1.4062 + if (v !== prev) dfs(v, u);
1.4063 + });
1.4064 + f(u);
1.4065 + }
1.4066 + dfs(root);
1.4067 +}
1.4068 +
1.4069 +},{"cp-data":5}],41:[function(require,module,exports){
1.4070 +/* jshint -W079 */
1.4071 +var Set = require("cp-data").Set;
1.4072 +/* jshint +W079 */
1.4073 +
1.4074 +module.exports = preorder;
1.4075 +
1.4076 +// Preorder traversal of g, calling f for each visited node. Assumes the graph
1.4077 +// is a tree.
1.4078 +function preorder(g, root, f) {
1.4079 + var visited = new Set();
1.4080 + if (g.isDirected()) {
1.4081 + throw new Error("This function only works for undirected graphs");
1.4082 + }
1.4083 + function dfs(u, prev) {
1.4084 + if (visited.has(u)) {
1.4085 + throw new Error("The input graph is not a tree: " + g);
1.4086 + }
1.4087 + visited.add(u);
1.4088 + f(u);
1.4089 + g.neighbors(u).forEach(function(v) {
1.4090 + if (v !== prev) dfs(v, u);
1.4091 + });
1.4092 + }
1.4093 + dfs(root);
1.4094 +}
1.4095 +
1.4096 +},{"cp-data":5}],42:[function(require,module,exports){
1.4097 +var Graph = require("../Graph"),
1.4098 + PriorityQueue = require("cp-data").PriorityQueue;
1.4099 +
1.4100 +module.exports = prim;
1.4101 +
1.4102 +/**
1.4103 + * [Prim's algorithm][] takes a connected undirected graph and generates a
1.4104 + * [minimum spanning tree][]. This function returns the minimum spanning
1.4105 + * tree as an undirected graph. This algorithm is derived from the description
1.4106 + * in "Introduction to Algorithms", Third Edition, Cormen, et al., Pg 634.
1.4107 + *
1.4108 + * This function takes a `weightFunc(e)` which returns the weight of the edge
1.4109 + * `e`. It throws an Error if the graph is not connected.
1.4110 + *
1.4111 + * This function takes `O(|E| log |V|)` time.
1.4112 + *
1.4113 + * [Prim's algorithm]: https://en.wikipedia.org/wiki/Prim's_algorithm
1.4114 + * [minimum spanning tree]: https://en.wikipedia.org/wiki/Minimum_spanning_tree
1.4115 + *
1.4116 + * @param {Graph} g the graph used to generate the minimum spanning tree
1.4117 + * @param {Function} weightFunc the weight function to use
1.4118 + */
1.4119 +function prim(g, weightFunc) {
1.4120 + var result = new Graph(),
1.4121 + parents = {},
1.4122 + pq = new PriorityQueue(),
1.4123 + u;
1.4124 +
1.4125 + function updateNeighbors(e) {
1.4126 + var incidentNodes = g.incidentNodes(e),
1.4127 + v = incidentNodes[0] !== u ? incidentNodes[0] : incidentNodes[1],
1.4128 + pri = pq.priority(v);
1.4129 + if (pri !== undefined) {
1.4130 + var edgeWeight = weightFunc(e);
1.4131 + if (edgeWeight < pri) {
1.4132 + parents[v] = u;
1.4133 + pq.decrease(v, edgeWeight);
1.4134 + }
1.4135 + }
1.4136 + }
1.4137 +
1.4138 + if (g.order() === 0) {
1.4139 + return result;
1.4140 + }
1.4141 +
1.4142 + g.eachNode(function(u) {
1.4143 + pq.add(u, Number.POSITIVE_INFINITY);
1.4144 + result.addNode(u);
1.4145 + });
1.4146 +
1.4147 + // Start from an arbitrary node
1.4148 + pq.decrease(g.nodes()[0], 0);
1.4149 +
1.4150 + var init = false;
1.4151 + while (pq.size() > 0) {
1.4152 + u = pq.removeMin();
1.4153 + if (u in parents) {
1.4154 + result.addEdge(null, u, parents[u]);
1.4155 + } else if (init) {
1.4156 + throw new Error("Input graph is not connected: " + g);
1.4157 + } else {
1.4158 + init = true;
1.4159 + }
1.4160 +
1.4161 + g.incidentEdges(u).forEach(updateNeighbors);
1.4162 + }
1.4163 +
1.4164 + return result;
1.4165 +}
1.4166 +
1.4167 +},{"../Graph":33,"cp-data":5}],43:[function(require,module,exports){
1.4168 +module.exports = tarjan;
1.4169 +
1.4170 +/**
1.4171 + * This function is an implementation of [Tarjan's algorithm][] which finds
1.4172 + * all [strongly connected components][] in the directed graph **g**. Each
1.4173 + * strongly connected component is composed of nodes that can reach all other
1.4174 + * nodes in the component via directed edges. A strongly connected component
1.4175 + * can consist of a single node if that node cannot both reach and be reached
1.4176 + * by any other specific node in the graph. Components of more than one node
1.4177 + * are guaranteed to have at least one cycle.
1.4178 + *
1.4179 + * This function returns an array of components. Each component is itself an
1.4180 + * array that contains the ids of all nodes in the component.
1.4181 + *
1.4182 + * [Tarjan's algorithm]: http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm
1.4183 + * [strongly connected components]: http://en.wikipedia.org/wiki/Strongly_connected_component
1.4184 + *
1.4185 + * @param {Digraph} g the graph to search for strongly connected components
1.4186 + */
1.4187 +function tarjan(g) {
1.4188 + if (!g.isDirected()) {
1.4189 + throw new Error("tarjan can only be applied to a directed graph. Bad input: " + g);
1.4190 + }
1.4191 +
1.4192 + var index = 0,
1.4193 + stack = [],
1.4194 + visited = {}, // node id -> { onStack, lowlink, index }
1.4195 + results = [];
1.4196 +
1.4197 + function dfs(u) {
1.4198 + var entry = visited[u] = {
1.4199 + onStack: true,
1.4200 + lowlink: index,
1.4201 + index: index++
1.4202 + };
1.4203 + stack.push(u);
1.4204 +
1.4205 + g.successors(u).forEach(function(v) {
1.4206 + if (!(v in visited)) {
1.4207 + dfs(v);
1.4208 + entry.lowlink = Math.min(entry.lowlink, visited[v].lowlink);
1.4209 + } else if (visited[v].onStack) {
1.4210 + entry.lowlink = Math.min(entry.lowlink, visited[v].index);
1.4211 + }
1.4212 + });
1.4213 +
1.4214 + if (entry.lowlink === entry.index) {
1.4215 + var cmpt = [],
1.4216 + v;
1.4217 + do {
1.4218 + v = stack.pop();
1.4219 + visited[v].onStack = false;
1.4220 + cmpt.push(v);
1.4221 + } while (u !== v);
1.4222 + results.push(cmpt);
1.4223 + }
1.4224 + }
1.4225 +
1.4226 + g.nodes().forEach(function(u) {
1.4227 + if (!(u in visited)) {
1.4228 + dfs(u);
1.4229 + }
1.4230 + });
1.4231 +
1.4232 + return results;
1.4233 +}
1.4234 +
1.4235 +},{}],44:[function(require,module,exports){
1.4236 +module.exports = topsort;
1.4237 +topsort.CycleException = CycleException;
1.4238 +
1.4239 +/*
1.4240 + * Given a graph **g**, this function returns an ordered list of nodes such
1.4241 + * that for each edge `u -> v`, `u` appears before `v` in the list. If the
1.4242 + * graph has a cycle it is impossible to generate such a list and
1.4243 + * **CycleException** is thrown.
1.4244 + *
1.4245 + * See [topological sorting](https://en.wikipedia.org/wiki/Topological_sorting)
1.4246 + * for more details about how this algorithm works.
1.4247 + *
1.4248 + * @param {Digraph} g the graph to sort
1.4249 + */
1.4250 +function topsort(g) {
1.4251 + if (!g.isDirected()) {
1.4252 + throw new Error("topsort can only be applied to a directed graph. Bad input: " + g);
1.4253 + }
1.4254 +
1.4255 + var visited = {};
1.4256 + var stack = {};
1.4257 + var results = [];
1.4258 +
1.4259 + function visit(node) {
1.4260 + if (node in stack) {
1.4261 + throw new CycleException();
1.4262 + }
1.4263 +
1.4264 + if (!(node in visited)) {
1.4265 + stack[node] = true;
1.4266 + visited[node] = true;
1.4267 + g.predecessors(node).forEach(function(pred) {
1.4268 + visit(pred);
1.4269 + });
1.4270 + delete stack[node];
1.4271 + results.push(node);
1.4272 + }
1.4273 + }
1.4274 +
1.4275 + var sinks = g.sinks();
1.4276 + if (g.order() !== 0 && sinks.length === 0) {
1.4277 + throw new CycleException();
1.4278 + }
1.4279 +
1.4280 + g.sinks().forEach(function(sink) {
1.4281 + visit(sink);
1.4282 + });
1.4283 +
1.4284 + return results;
1.4285 +}
1.4286 +
1.4287 +function CycleException() {}
1.4288 +
1.4289 +CycleException.prototype.toString = function() {
1.4290 + return "Graph has at least one cycle";
1.4291 +};
1.4292 +
1.4293 +},{}],45:[function(require,module,exports){
1.4294 +// This file provides a helper function that mixes-in Dot behavior to an
1.4295 +// existing graph prototype.
1.4296 +
1.4297 +/* jshint -W079 */
1.4298 +var Set = require("cp-data").Set;
1.4299 +/* jshint +W079 */
1.4300 +
1.4301 +module.exports = compoundify;
1.4302 +
1.4303 +// Extends the given SuperConstructor with the ability for nodes to contain
1.4304 +// other nodes. A special node id `null` is used to indicate the root graph.
1.4305 +function compoundify(SuperConstructor) {
1.4306 + function Constructor() {
1.4307 + SuperConstructor.call(this);
1.4308 +
1.4309 + // Map of object id -> parent id (or null for root graph)
1.4310 + this._parents = {};
1.4311 +
1.4312 + // Map of id (or null) -> children set
1.4313 + this._children = {};
1.4314 + this._children[null] = new Set();
1.4315 + }
1.4316 +
1.4317 + Constructor.prototype = new SuperConstructor();
1.4318 + Constructor.prototype.constructor = Constructor;
1.4319 +
1.4320 + Constructor.prototype.parent = function(u, parent) {
1.4321 + this._strictGetNode(u);
1.4322 +
1.4323 + if (arguments.length < 2) {
1.4324 + return this._parents[u];
1.4325 + }
1.4326 +
1.4327 + if (u === parent) {
1.4328 + throw new Error("Cannot make " + u + " a parent of itself");
1.4329 + }
1.4330 + if (parent !== null) {
1.4331 + this._strictGetNode(parent);
1.4332 + }
1.4333 +
1.4334 + this._children[this._parents[u]].remove(u);
1.4335 + this._parents[u] = parent;
1.4336 + this._children[parent].add(u);
1.4337 + };
1.4338 +
1.4339 + Constructor.prototype.children = function(u) {
1.4340 + if (u !== null) {
1.4341 + this._strictGetNode(u);
1.4342 + }
1.4343 + return this._children[u].keys();
1.4344 + };
1.4345 +
1.4346 + Constructor.prototype.addNode = function(u, value) {
1.4347 + u = SuperConstructor.prototype.addNode.call(this, u, value);
1.4348 + this._parents[u] = null;
1.4349 + this._children[u] = new Set();
1.4350 + this._children[null].add(u);
1.4351 + return u;
1.4352 + };
1.4353 +
1.4354 + Constructor.prototype.delNode = function(u) {
1.4355 + // Promote all children to the parent of the subgraph
1.4356 + var parent = this.parent(u);
1.4357 + this._children[u].keys().forEach(function(child) {
1.4358 + this.parent(child, parent);
1.4359 + }, this);
1.4360 +
1.4361 + this._children[parent].remove(u);
1.4362 + delete this._parents[u];
1.4363 + delete this._children[u];
1.4364 +
1.4365 + return SuperConstructor.prototype.delNode.call(this, u);
1.4366 + };
1.4367 +
1.4368 + Constructor.prototype.copy = function() {
1.4369 + var copy = SuperConstructor.prototype.copy.call(this);
1.4370 + this.nodes().forEach(function(u) {
1.4371 + copy.parent(u, this.parent(u));
1.4372 + }, this);
1.4373 + return copy;
1.4374 + };
1.4375 +
1.4376 + Constructor.prototype.filterNodes = function(filter) {
1.4377 + var self = this,
1.4378 + copy = SuperConstructor.prototype.filterNodes.call(this, filter);
1.4379 +
1.4380 + var parents = {};
1.4381 + function findParent(u) {
1.4382 + var parent = self.parent(u);
1.4383 + if (parent === null || copy.hasNode(parent)) {
1.4384 + parents[u] = parent;
1.4385 + return parent;
1.4386 + } else if (parent in parents) {
1.4387 + return parents[parent];
1.4388 + } else {
1.4389 + return findParent(parent);
1.4390 + }
1.4391 + }
1.4392 +
1.4393 + copy.eachNode(function(u) { copy.parent(u, findParent(u)); });
1.4394 +
1.4395 + return copy;
1.4396 + };
1.4397 +
1.4398 + return Constructor;
1.4399 +}
1.4400 +
1.4401 +},{"cp-data":5}],46:[function(require,module,exports){
1.4402 +var Graph = require("../Graph"),
1.4403 + Digraph = require("../Digraph"),
1.4404 + CGraph = require("../CGraph"),
1.4405 + CDigraph = require("../CDigraph");
1.4406 +
1.4407 +exports.decode = function(nodes, edges, Ctor) {
1.4408 + Ctor = Ctor || Digraph;
1.4409 +
1.4410 + if (typeOf(nodes) !== "Array") {
1.4411 + throw new Error("nodes is not an Array");
1.4412 + }
1.4413 +
1.4414 + if (typeOf(edges) !== "Array") {
1.4415 + throw new Error("edges is not an Array");
1.4416 + }
1.4417 +
1.4418 + if (typeof Ctor === "string") {
1.4419 + switch(Ctor) {
1.4420 + case "graph": Ctor = Graph; break;
1.4421 + case "digraph": Ctor = Digraph; break;
1.4422 + case "cgraph": Ctor = CGraph; break;
1.4423 + case "cdigraph": Ctor = CDigraph; break;
1.4424 + default: throw new Error("Unrecognized graph type: " + Ctor);
1.4425 + }
1.4426 + }
1.4427 +
1.4428 + var graph = new Ctor();
1.4429 +
1.4430 + nodes.forEach(function(u) {
1.4431 + graph.addNode(u.id, u.value);
1.4432 + });
1.4433 +
1.4434 + // If the graph is compound, set up children...
1.4435 + if (graph.parent) {
1.4436 + nodes.forEach(function(u) {
1.4437 + if (u.children) {
1.4438 + u.children.forEach(function(v) {
1.4439 + graph.parent(v, u.id);
1.4440 + });
1.4441 + }
1.4442 + });
1.4443 + }
1.4444 +
1.4445 + edges.forEach(function(e) {
1.4446 + graph.addEdge(e.id, e.u, e.v, e.value);
1.4447 + });
1.4448 +
1.4449 + return graph;
1.4450 +};
1.4451 +
1.4452 +exports.encode = function(graph) {
1.4453 + var nodes = [];
1.4454 + var edges = [];
1.4455 +
1.4456 + graph.eachNode(function(u, value) {
1.4457 + var node = {id: u, value: value};
1.4458 + if (graph.children) {
1.4459 + var children = graph.children(u);
1.4460 + if (children.length) {
1.4461 + node.children = children;
1.4462 + }
1.4463 + }
1.4464 + nodes.push(node);
1.4465 + });
1.4466 +
1.4467 + graph.eachEdge(function(e, u, v, value) {
1.4468 + edges.push({id: e, u: u, v: v, value: value});
1.4469 + });
1.4470 +
1.4471 + var type;
1.4472 + if (graph instanceof CDigraph) {
1.4473 + type = "cdigraph";
1.4474 + } else if (graph instanceof CGraph) {
1.4475 + type = "cgraph";
1.4476 + } else if (graph instanceof Digraph) {
1.4477 + type = "digraph";
1.4478 + } else if (graph instanceof Graph) {
1.4479 + type = "graph";
1.4480 + } else {
1.4481 + throw new Error("Couldn't determine type of graph: " + graph);
1.4482 + }
1.4483 +
1.4484 + return { nodes: nodes, edges: edges, type: type };
1.4485 +};
1.4486 +
1.4487 +function typeOf(obj) {
1.4488 + return Object.prototype.toString.call(obj).slice(8, -1);
1.4489 +}
1.4490 +
1.4491 +},{"../CDigraph":30,"../CGraph":31,"../Digraph":32,"../Graph":33}],47:[function(require,module,exports){
1.4492 +/* jshint -W079 */
1.4493 +var Set = require("cp-data").Set;
1.4494 +/* jshint +W079 */
1.4495 +
1.4496 +exports.all = function() {
1.4497 + return function() { return true; };
1.4498 +};
1.4499 +
1.4500 +exports.nodesFromList = function(nodes) {
1.4501 + var set = new Set(nodes);
1.4502 + return function(u) {
1.4503 + return set.has(u);
1.4504 + };
1.4505 +};
1.4506 +
1.4507 +},{"cp-data":5}],48:[function(require,module,exports){
1.4508 +var Graph = require("./Graph"),
1.4509 + Digraph = require("./Digraph");
1.4510 +
1.4511 +// Side-effect based changes are lousy, but node doesn't seem to resolve the
1.4512 +// requires cycle.
1.4513 +
1.4514 +/**
1.4515 + * Returns a new directed graph using the nodes and edges from this graph. The
1.4516 + * new graph will have the same nodes, but will have twice the number of edges:
1.4517 + * each edge is split into two edges with opposite directions. Edge ids,
1.4518 + * consequently, are not preserved by this transformation.
1.4519 + */
1.4520 +Graph.prototype.toDigraph =
1.4521 +Graph.prototype.asDirected = function() {
1.4522 + var g = new Digraph();
1.4523 + this.eachNode(function(u, value) { g.addNode(u, value); });
1.4524 + this.eachEdge(function(e, u, v, value) {
1.4525 + g.addEdge(null, u, v, value);
1.4526 + g.addEdge(null, v, u, value);
1.4527 + });
1.4528 + return g;
1.4529 +};
1.4530 +
1.4531 +/**
1.4532 + * Returns a new undirected graph using the nodes and edges from this graph.
1.4533 + * The new graph will have the same nodes, but the edges will be made
1.4534 + * undirected. Edge ids are preserved in this transformation.
1.4535 + */
1.4536 +Digraph.prototype.toGraph =
1.4537 +Digraph.prototype.asUndirected = function() {
1.4538 + var g = new Graph();
1.4539 + this.eachNode(function(u, value) { g.addNode(u, value); });
1.4540 + this.eachEdge(function(e, u, v, value) {
1.4541 + g.addEdge(e, u, v, value);
1.4542 + });
1.4543 + return g;
1.4544 +};
1.4545 +
1.4546 +},{"./Digraph":32,"./Graph":33}],49:[function(require,module,exports){
1.4547 +// Returns an array of all values for properties of **o**.
1.4548 +exports.values = function(o) {
1.4549 + var ks = Object.keys(o),
1.4550 + len = ks.length,
1.4551 + result = new Array(len),
1.4552 + i;
1.4553 + for (i = 0; i < len; ++i) {
1.4554 + result[i] = o[ks[i]];
1.4555 + }
1.4556 + return result;
1.4557 +};
1.4558 +
1.4559 +},{}],50:[function(require,module,exports){
1.4560 +module.exports = '0.7.4';
1.4561 +
1.4562 +},{}]},{},[1])
1.4563 +;
1.4564 \ No newline at end of file
