The Tor Browser / file revision

 ;(function e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);throw new Error("Cannot find module '"+o+"'")}var f=n[o]={exports:{}};t[o][0].call(f.exports,function(e){var n=t[o][1][e];return s(n?n:e)},f,f.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return s})({1:[function(require,module,exports){

 var global=self;/**

  * @license

  * Copyright (c) 2012-2013 Chris Pettitt

  *

  * Permission is hereby granted, free of charge, to any person obtaining a copy

  * of this software and associated documentation files (the "Software"), to deal

  * in the Software without restriction, including without limitation the rights

  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell

  * copies of the Software, and to permit persons to whom the Software is

  * furnished to do so, subject to the following conditions:

  *

  * The above copyright notice and this permission notice shall be included in

  * all copies or substantial portions of the Software.

  *

  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE

  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,

  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN

  * THE SOFTWARE.

  */

 global.dagreD3 = require('./index');

 },{"./index":2}],2:[function(require,module,exports){

 /**

  * @license

  * Copyright (c) 2012-2013 Chris Pettitt

  *

  * Permission is hereby granted, free of charge, to any person obtaining a copy

  * of this software and associated documentation files (the "Software"), to deal

  * in the Software without restriction, including without limitation the rights

  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell

  * copies of the Software, and to permit persons to whom the Software is

  * furnished to do so, subject to the following conditions:

  *

  * The above copyright notice and this permission notice shall be included in

  * all copies or substantial portions of the Software.

  *

  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE

  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,

  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN

  * THE SOFTWARE.

  */

 module.exports =  {

   Digraph: require('graphlib').Digraph,

   Renderer: require('./lib/Renderer'),

   json: require('graphlib').converter.json,

   layout: require('dagre').layout,

   version: require('./lib/version')

 };

 },{"./lib/Renderer":3,"./lib/version":4,"dagre":11,"graphlib":28}],3:[function(require,module,exports){

 var layout = require('dagre').layout;

 var d3;

 try { d3 = require('d3'); } catch (_) { d3 = window.d3; }

 module.exports = Renderer;

 function Renderer() {

   // Set up defaults...

   this._layout = layout();

   this.drawNodes(defaultDrawNodes);

   this.drawEdgeLabels(defaultDrawEdgeLabels);

   this.drawEdgePaths(defaultDrawEdgePaths);

   this.positionNodes(defaultPositionNodes);

   this.positionEdgeLabels(defaultPositionEdgeLabels);

   this.positionEdgePaths(defaultPositionEdgePaths);

   this.transition(defaultTransition);

   this.postLayout(defaultPostLayout);

   this.postRender(defaultPostRender);

   this.edgeInterpolate('bundle');

   this.edgeTension(0.95);

 }

 Renderer.prototype.layout = function(layout) {

   if (!arguments.length) { return this._layout; }

   this._layout = layout;

   return this;

 };

 Renderer.prototype.drawNodes = function(drawNodes) {

   if (!arguments.length) { return this._drawNodes; }

   this._drawNodes = bind(drawNodes, this);

   return this;

 };

 Renderer.prototype.drawEdgeLabels = function(drawEdgeLabels) {

   if (!arguments.length) { return this._drawEdgeLabels; }

   this._drawEdgeLabels = bind(drawEdgeLabels, this);

   return this;

 };

 Renderer.prototype.drawEdgePaths = function(drawEdgePaths) {

   if (!arguments.length) { return this._drawEdgePaths; }

   this._drawEdgePaths = bind(drawEdgePaths, this);

   return this;

 };

 Renderer.prototype.positionNodes = function(positionNodes) {

   if (!arguments.length) { return this._positionNodes; }

   this._positionNodes = bind(positionNodes, this);

   return this;

 };

 Renderer.prototype.positionEdgeLabels = function(positionEdgeLabels) {

   if (!arguments.length) { return this._positionEdgeLabels; }

   this._positionEdgeLabels = bind(positionEdgeLabels, this);

   return this;

 };

 Renderer.prototype.positionEdgePaths = function(positionEdgePaths) {

   if (!arguments.length) { return this._positionEdgePaths; }

   this._positionEdgePaths = bind(positionEdgePaths, this);

   return this;

 };

 Renderer.prototype.transition = function(transition) {

   if (!arguments.length) { return this._transition; }

   this._transition = bind(transition, this);

   return this;

 };

 Renderer.prototype.postLayout = function(postLayout) {

   if (!arguments.length) { return this._postLayout; }

   this._postLayout = bind(postLayout, this);

   return this;

 };

 Renderer.prototype.postRender = function(postRender) {

   if (!arguments.length) { return this._postRender; }

   this._postRender = bind(postRender, this);

   return this;

 };

 Renderer.prototype.edgeInterpolate = function(edgeInterpolate) {

   if (!arguments.length) { return this._edgeInterpolate; }

   this._edgeInterpolate = edgeInterpolate;

   return this;

 };

 Renderer.prototype.edgeTension = function(edgeTension) {

   if (!arguments.length) { return this._edgeTension; }

   this._edgeTension = edgeTension;

   return this;

 };

 Renderer.prototype.run = function(graph, svg) {

   // First copy the input graph so that it is not changed by the rendering

   // process.

   graph = copyAndInitGraph(graph);

   // Create layers

   svg

     .selectAll('g.edgePaths, g.edgeLabels, g.nodes')

     .data(['edgePaths', 'edgeLabels', 'nodes'])

     .enter()

       .append('g')

       .attr('class', function(d) { return d; });

   // Create node and edge roots, attach labels, and capture dimension

   // information for use with layout.

   var svgNodes = this._drawNodes(graph, svg.select('g.nodes'));

   var svgEdgeLabels = this._drawEdgeLabels(graph, svg.select('g.edgeLabels'));

   svgNodes.each(function(u) { calculateDimensions(this, graph.node(u)); });

   svgEdgeLabels.each(function(e) { calculateDimensions(this, graph.edge(e)); });

   // Now apply the layout function

   var result = runLayout(graph, this._layout);

   // Run any user-specified post layout processing

   this._postLayout(result, svg);

   var svgEdgePaths = this._drawEdgePaths(graph, svg.select('g.edgePaths'));

   // Apply the layout information to the graph

   this._positionNodes(result, svgNodes);

   this._positionEdgeLabels(result, svgEdgeLabels);

   this._positionEdgePaths(result, svgEdgePaths);

   this._postRender(result, svg);

   return result;

 };

 function copyAndInitGraph(graph) {

   var copy = graph.copy();

   // Init labels if they were not present in the source graph

   copy.nodes().forEach(function(u) {

     var value = copy.node(u);

     if (value === undefined) {

       value = {};

       copy.node(u, value);

     }

     if (!('label' in value)) { value.label = ''; }

   });

   copy.edges().forEach(function(e) {

     var value = copy.edge(e);

     if (value === undefined) {

       value = {};

       copy.edge(e, value);

     }

     if (!('label' in value)) { value.label = ''; }

   });

   return copy;

 }

 function calculateDimensions(group, value) {

   var bbox = group.getBBox();

   value.width = bbox.width;

   value.height = bbox.height;

 }

 function runLayout(graph, layout) {

   var result = layout.run(graph);

   // Copy labels to the result graph

   graph.eachNode(function(u, value) { result.node(u).label = value.label; });

   graph.eachEdge(function(e, u, v, value) { result.edge(e).label = value.label; });

   return result;

 }

 function defaultDrawNodes(g, root) {

   var nodes = g.nodes().filter(function(u) { return !isComposite(g, u); });

   var svgNodes = root

     .selectAll('g.node')

     .classed('enter', false)

     .data(nodes, function(u) { return u; });

   svgNodes.selectAll('*').remove();

   svgNodes

     .enter()

       .append('g')

         .style('opacity', 0)

         .attr('class', 'node enter');

   svgNodes.each(function(u) { addLabel(g.node(u), d3.select(this), 10, 10); });

   this._transition(svgNodes.exit())

       .style('opacity', 0)

       .remove();

   return svgNodes;

 }

 function defaultDrawEdgeLabels(g, root) {

   var svgEdgeLabels = root

     .selectAll('g.edgeLabel')

     .classed('enter', false)

     .data(g.edges(), function (e) { return e; });

   svgEdgeLabels.selectAll('*').remove();

   svgEdgeLabels

     .enter()

       .append('g')

         .style('opacity', 0)

         .attr('class', 'edgeLabel enter');

   svgEdgeLabels.each(function(e) { addLabel(g.edge(e), d3.select(this), 0, 0); });

   this._transition(svgEdgeLabels.exit())

       .style('opacity', 0)

       .remove();

   return svgEdgeLabels;

 }

 var defaultDrawEdgePaths = function(g, root) {

   var svgEdgePaths = root

     .selectAll('g.edgePath')

     .classed('enter', false)

     .data(g.edges(), function(e) { return e; });

   svgEdgePaths

     .enter()

       .append('g')

         .attr('class', 'edgePath enter')

         .append('path')

           .style('opacity', 0)

           .attr('marker-end', 'url(#arrowhead)');

   this._transition(svgEdgePaths.exit())

       .style('opacity', 0)

       .remove();

   return svgEdgePaths;

 };

 function defaultPositionNodes(g, svgNodes, svgNodesEnter) {

   function transform(u) {

     var value = g.node(u);

     return 'translate(' + value.x + ',' + value.y + ')';

   }

   // For entering nodes, position immediately without transition

   svgNodes.filter('.enter').attr('transform', transform);

   this._transition(svgNodes)

       .style('opacity', 1)

       .attr('transform', transform);

 }

 function defaultPositionEdgeLabels(g, svgEdgeLabels) {

   function transform(e) {

     var value = g.edge(e);

     var point = findMidPoint(value.points);

     return 'translate(' + point.x + ',' + point.y + ')';

   }

   // For entering edge labels, position immediately without transition

   svgEdgeLabels.filter('.enter').attr('transform', transform);

   this._transition(svgEdgeLabels)

     .style('opacity', 1)

     .attr('transform', transform);

 }

 function defaultPositionEdgePaths(g, svgEdgePaths) {

   var interpolate = this._edgeInterpolate,

       tension = this._edgeTension;

   function calcPoints(e) {

     var value = g.edge(e);

     var source = g.node(g.incidentNodes(e)[0]);

     var target = g.node(g.incidentNodes(e)[1]);

     var points = value.points.slice();

     var p0 = points.length === 0 ? target : points[0];

     var p1 = points.length === 0 ? source : points[points.length - 1];

     points.unshift(intersectRect(source, p0));

     // TODO: use bpodgursky's shortening algorithm here

     points.push(intersectRect(target, p1));

     return d3.svg.line()

       .x(function(d) { return d.x; })

       .y(function(d) { return d.y; })

       .interpolate(interpolate)

       .tension(tension)

       (points);

   }

   svgEdgePaths.filter('.enter').selectAll('path')

       .attr('d', calcPoints);

   this._transition(svgEdgePaths.selectAll('path'))

       .attr('d', calcPoints)

       .style('opacity', 1);

 }

 // By default we do not use transitions

 function defaultTransition(selection) {

   return selection;

 }

 function defaultPostLayout() {

   // Do nothing

 }

 function defaultPostRender(graph, root) {

   if (graph.isDirected() && root.select('#arrowhead').empty()) {

     root

       .append('svg:defs')

         .append('svg:marker')

           .attr('id', 'arrowhead')

           .attr('viewBox', '0 0 10 10')

           .attr('refX', 8)

           .attr('refY', 5)

           .attr('markerUnits', 'strokewidth')

           .attr('markerWidth', 8)

           .attr('markerHeight', 5)

           .attr('orient', 'auto')

           .attr('style', 'fill: #333')

           .append('svg:path')

             .attr('d', 'M 0 0 L 10 5 L 0 10 z');

   }

 }

 function addLabel(node, root, marginX, marginY) {

   // Add the rect first so that it appears behind the label

   var label = node.label;

   var rect = root.append('rect');

   var labelSvg = root.append('g');

   if (label[0] === '<') {

     addForeignObjectLabel(label, labelSvg);

     // No margin for HTML elements

     marginX = marginY = 0;

   } else {

     addTextLabel(label,

                  labelSvg,

                  Math.floor(node.labelCols),

                  node.labelCut);

   }

   var bbox = root.node().getBBox();

   labelSvg.attr('transform',

              'translate(' + (-bbox.width / 2) + ',' + (-bbox.height / 2) + ')');

   rect

     .attr('rx', 5)

     .attr('ry', 5)

     .attr('x', -(bbox.width / 2 + marginX))

     .attr('y', -(bbox.height / 2 + marginY))

     .attr('width', bbox.width + 2 * marginX)

     .attr('height', bbox.height + 2 * marginY);

 }

 function addForeignObjectLabel(label, root) {

   var fo = root

     .append('foreignObject')

       .attr('width', '100000');

   var w, h;

   fo

     .append('xhtml:div')

       .style('float', 'left')

       // TODO find a better way to get dimensions for foreignObjects...

       .html(function() { return label; })

       .each(function() {

         w = this.clientWidth;

         h = this.clientHeight;

       });

   fo

     .attr('width', w)

     .attr('height', h);

 }

 function addTextLabel(label, root, labelCols, labelCut) {

   if (labelCut === undefined) labelCut = "false";

   labelCut = (labelCut.toString().toLowerCase() === "true");

   var node = root

     .append('text')

     .attr('text-anchor', 'left');

   label = label.replace(/\\n/g, "\n");

   var arr = labelCols ? wordwrap(label, labelCols, labelCut) : label;

   arr = arr.split("\n");

   for (var i = 0; i < arr.length; i++) {

     node

       .append('tspan')

         .attr('dy', '1em')

         .attr('x', '1')

         .text(arr[i]);

   }

 }

 // Thanks to

 // http://james.padolsey.com/javascript/wordwrap-for-javascript/

 function wordwrap (str, width, cut, brk) {

      brk = brk || '\n';

      width = width || 75;

      cut = cut || false;

      if (!str) { return str; }

      var regex = '.{1,' +width+ '}(\\s|$)' + (cut ? '|.{' +width+ '}|.+$' : '|\\S+?(\\s|$)');

      return str.match( RegExp(regex, 'g') ).join( brk );

 }

 function findMidPoint(points) {

   var midIdx = points.length / 2;

   if (points.length % 2) {

     return points[Math.floor(midIdx)];

   } else {

     var p0 = points[midIdx - 1];

     var p1 = points[midIdx];

     return {x: (p0.x + p1.x) / 2, y: (p0.y + p1.y) / 2};

   }

 }

 function intersectRect(rect, point) {

   var x = rect.x;

   var y = rect.y;

   // For now we only support rectangles

   // Rectangle intersection algorithm from:

   // http://math.stackexchange.com/questions/108113/find-edge-between-two-boxes

   var dx = point.x - x;

   var dy = point.y - y;

   var w = rect.width / 2;

   var h = rect.height / 2;

   var sx, sy;

   if (Math.abs(dy) * w > Math.abs(dx) * h) {

     // Intersection is top or bottom of rect.

     if (dy < 0) {

       h = -h;

     }

     sx = dy === 0 ? 0 : h * dx / dy;

     sy = h;

   } else {

     // Intersection is left or right of rect.

     if (dx < 0) {

       w = -w;

     }

     sx = w;

     sy = dx === 0 ? 0 : w * dy / dx;

   }

   return {x: x + sx, y: y + sy};

 }

 function isComposite(g, u) {

   return 'children' in g && g.children(u).length;

 }

 function bind(func, thisArg) {

   // For some reason PhantomJS occassionally fails when using the builtin bind,

   // so we check if it is available and if not, use a degenerate polyfill.

   if (func.bind) {

     return func.bind(thisArg);

   }

   return function() {

     return func.apply(thisArg, arguments);

   };

 }

 },{"d3":10,"dagre":11}],4:[function(require,module,exports){

 module.exports = '0.1.5';

 },{}],5:[function(require,module,exports){

 exports.Set = require('./lib/Set');

 exports.PriorityQueue = require('./lib/PriorityQueue');

 exports.version = require('./lib/version');

 },{"./lib/PriorityQueue":6,"./lib/Set":7,"./lib/version":9}],6:[function(require,module,exports){

 module.exports = PriorityQueue;

 /**

  * A min-priority queue data structure. This algorithm is derived from Cormen,

  * et al., "Introduction to Algorithms". The basic idea of a min-priority

  * queue is that you can efficiently (in O(1) time) get the smallest key in

  * the queue. Adding and removing elements takes O(log n) time. A key can

  * have its priority decreased in O(log n) time.

  */

 function PriorityQueue() {

   this._arr = [];

   this._keyIndices = {};

 }

 /**

  * Returns the number of elements in the queue. Takes `O(1)` time.

  */

 PriorityQueue.prototype.size = function() {

   return this._arr.length;

 };

 /**

  * Returns the keys that are in the queue. Takes `O(n)` time.

  */

 PriorityQueue.prototype.keys = function() {

   return this._arr.map(function(x) { return x.key; });

 };

 /**

  * Returns `true` if **key** is in the queue and `false` if not.

  */

 PriorityQueue.prototype.has = function(key) {

   return key in this._keyIndices;

 };

 /**

  * Returns the priority for **key**. If **key** is not present in the queue

  * then this function returns `undefined`. Takes `O(1)` time.

  *

  * @param {Object} key

  */

 PriorityQueue.prototype.priority = function(key) {

   var index = this._keyIndices[key];

   if (index !== undefined) {

     return this._arr[index].priority;

   }

 };

 /**

  * Returns the key for the minimum element in this queue. If the queue is

  * empty this function throws an Error. Takes `O(1)` time.

  */

 PriorityQueue.prototype.min = function() {

   if (this.size() === 0) {

     throw new Error("Queue underflow");

   }

   return this._arr[0].key;

 };

 /**

  * Inserts a new key into the priority queue. If the key already exists in

  * the queue this function returns `false`; otherwise it will return `true`.

  * Takes `O(n)` time.

  *

  * @param {Object} key the key to add

  * @param {Number} priority the initial priority for the key

  */

 PriorityQueue.prototype.add = function(key, priority) {

   var keyIndices = this._keyIndices;

   if (!(key in keyIndices)) {

     var arr = this._arr;

     var index = arr.length;

     keyIndices[key] = index;

     arr.push({key: key, priority: priority});

     this._decrease(index);

     return true;

   }

   return false;

 };

 /**

  * Removes and returns the smallest key in the queue. Takes `O(log n)` time.

  */

 PriorityQueue.prototype.removeMin = function() {

   this._swap(0, this._arr.length - 1);

   var min = this._arr.pop();

   delete this._keyIndices[min.key];

   this._heapify(0);

   return min.key;

 };

 /**

  * Decreases the priority for **key** to **priority**. If the new priority is

  * greater than the previous priority, this function will throw an Error.

  *

  * @param {Object} key the key for which to raise priority

  * @param {Number} priority the new priority for the key

  */

 PriorityQueue.prototype.decrease = function(key, priority) {

   var index = this._keyIndices[key];

   if (priority > this._arr[index].priority) {

     throw new Error("New priority is greater than current priority. " +

         "Key: " + key + " Old: " + this._arr[index].priority + " New: " + priority);

   }

   this._arr[index].priority = priority;

   this._decrease(index);

 };

 PriorityQueue.prototype._heapify = function(i) {

   var arr = this._arr;

   var l = 2 * i,

       r = l + 1,

       largest = i;

   if (l < arr.length) {

     largest = arr[l].priority < arr[largest].priority ? l : largest;

     if (r < arr.length) {

       largest = arr[r].priority < arr[largest].priority ? r : largest;

     }

     if (largest !== i) {

       this._swap(i, largest);

       this._heapify(largest);

     }

   }

 };

 PriorityQueue.prototype._decrease = function(index) {

   var arr = this._arr;

   var priority = arr[index].priority;

   var parent;

   while (index !== 0) {

     parent = index >> 1;

     if (arr[parent].priority < priority) {

       break;

     }

     this._swap(index, parent);

     index = parent;

   }

 };

 PriorityQueue.prototype._swap = function(i, j) {

   var arr = this._arr;

   var keyIndices = this._keyIndices;

   var origArrI = arr[i];

   var origArrJ = arr[j];

   arr[i] = origArrJ;

   arr[j] = origArrI;

   keyIndices[origArrJ.key] = i;

   keyIndices[origArrI.key] = j;

 };

 },{}],7:[function(require,module,exports){

 var util = require('./util');

 module.exports = Set;

 /**

  * Constructs a new Set with an optional set of `initialKeys`.

  *

  * It is important to note that keys are coerced to String for most purposes

  * with this object, similar to the behavior of JavaScript's Object. For

  * example, the following will add only one key:

  *

  *     var s = new Set();

  *     s.add(1);

  *     s.add("1");

  *

  * However, the type of the key is preserved internally so that `keys` returns

  * the original key set uncoerced. For the above example, `keys` would return

  * `[1]`.

  */

 function Set(initialKeys) {

   this._size = 0;

   this._keys = {};

   if (initialKeys) {

     for (var i = 0, il = initialKeys.length; i < il; ++i) {

       this.add(initialKeys[i]);

     }

   }

 }

 /**

  * Returns a new Set that represents the set intersection of the array of given

  * sets.

  */

 Set.intersect = function(sets) {

   if (sets.length === 0) {

     return new Set();

   }

   var result = new Set(!util.isArray(sets[0]) ? sets[0].keys() : sets[0]);

   for (var i = 1, il = sets.length; i < il; ++i) {

     var resultKeys = result.keys(),

         other = !util.isArray(sets[i]) ? sets[i] : new Set(sets[i]);

     for (var j = 0, jl = resultKeys.length; j < jl; ++j) {

       var key = resultKeys[j];

       if (!other.has(key)) {

         result.remove(key);

       }

     }

   }

   return result;

 };

 /**

  * Returns a new Set that represents the set union of the array of given sets.

  */

 Set.union = function(sets) {

   var totalElems = util.reduce(sets, function(lhs, rhs) {

     return lhs + (rhs.size ? rhs.size() : rhs.length);

   }, 0);

   var arr = new Array(totalElems);

   var k = 0;

   for (var i = 0, il = sets.length; i < il; ++i) {

     var cur = sets[i],

         keys = !util.isArray(cur) ? cur.keys() : cur;

     for (var j = 0, jl = keys.length; j < jl; ++j) {

       arr[k++] = keys[j];

     }

   }

   return new Set(arr);

 };

 /**

  * Returns the size of this set in `O(1)` time.

  */

 Set.prototype.size = function() {

   return this._size;

 };

 /**

  * Returns the keys in this set. Takes `O(n)` time.

  */

 Set.prototype.keys = function() {

   return values(this._keys);

 };

 /**

  * Tests if a key is present in this Set. Returns `true` if it is and `false`

  * if not. Takes `O(1)` time.

  */

 Set.prototype.has = function(key) {

   return key in this._keys;

 };

 /**

  * Adds a new key to this Set if it is not already present. Returns `true` if

  * the key was added and `false` if it was already present. Takes `O(1)` time.

  */

 Set.prototype.add = function(key) {

   if (!(key in this._keys)) {

     this._keys[key] = key;

     ++this._size;

     return true;

   }

   return false;

 };

 /**

  * Removes a key from this Set. If the key was removed this function returns

  * `true`. If not, it returns `false`. Takes `O(1)` time.

  */

 Set.prototype.remove = function(key) {

   if (key in this._keys) {

     delete this._keys[key];

     --this._size;

     return true;

   }

   return false;

 };

 /*

  * Returns an array of all values for properties of **o**.

  */

 function values(o) {

   var ks = Object.keys(o),

       len = ks.length,

       result = new Array(len),

       i;

   for (i = 0; i < len; ++i) {

     result[i] = o[ks[i]];

   }

   return result;

 }

 },{"./util":8}],8:[function(require,module,exports){

 /*

  * This polyfill comes from

  * https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/isArray

  */

 if(!Array.isArray) {

   exports.isArray = function (vArg) {

     return Object.prototype.toString.call(vArg) === '[object Array]';

   };

 } else {

   exports.isArray = Array.isArray;

 }

 /*

  * Slightly adapted polyfill from

  * https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/Reduce

  */

 if ('function' !== typeof Array.prototype.reduce) {

   exports.reduce = function(array, callback, opt_initialValue) {

     'use strict';

     if (null === array || 'undefined' === typeof array) {

       // At the moment all modern browsers, that support strict mode, have

       // native implementation of Array.prototype.reduce. For instance, IE8

       // does not support strict mode, so this check is actually useless.

       throw new TypeError(

           'Array.prototype.reduce called on null or undefined');

     }

     if ('function' !== typeof callback) {

       throw new TypeError(callback + ' is not a function');

     }

     var index, value,

         length = array.length >>> 0,

         isValueSet = false;

     if (1 < arguments.length) {

       value = opt_initialValue;

       isValueSet = true;

     }

     for (index = 0; length > index; ++index) {

       if (array.hasOwnProperty(index)) {

         if (isValueSet) {

           value = callback(value, array[index], index, array);

         }

         else {

           value = array[index];

           isValueSet = true;

         }

       }

     }

     if (!isValueSet) {

       throw new TypeError('Reduce of empty array with no initial value');

     }

     return value;

   };

 } else {

   exports.reduce = function(array, callback, opt_initialValue) {

     return array.reduce(callback, opt_initialValue);

   };

 }

 },{}],9:[function(require,module,exports){

 module.exports = '1.1.3';

 },{}],10:[function(require,module,exports){

 require("./d3");

 module.exports = d3;

 (function () { delete this.d3; })(); // unset global

 },{}],11:[function(require,module,exports){

 /*

 Copyright (c) 2012-2013 Chris Pettitt

 Permission is hereby granted, free of charge, to any person obtaining a copy

 of this software and associated documentation files (the "Software"), to deal

 in the Software without restriction, including without limitation the rights

 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell

 copies of the Software, and to permit persons to whom the Software is

 furnished to do so, subject to the following conditions:

 The above copyright notice and this permission notice shall be included in

 all copies or substantial portions of the Software.

 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE

 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,

 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN

 THE SOFTWARE.

 */

 exports.Digraph = require("graphlib").Digraph;

 exports.Graph = require("graphlib").Graph;

 exports.layout = require("./lib/layout");

 exports.version = require("./lib/version");

 },{"./lib/layout":12,"./lib/version":27,"graphlib":28}],12:[function(require,module,exports){

 var util = require('./util'),

     rank = require('./rank'),

     order = require('./order'),

     CGraph = require('graphlib').CGraph,

     CDigraph = require('graphlib').CDigraph;

 module.exports = function() {

   // External configuration

   var config = {

     // How much debug information to include?

     debugLevel: 0,

     // Max number of sweeps to perform in order phase

     orderMaxSweeps: order.DEFAULT_MAX_SWEEPS,

     // Use network simplex algorithm in ranking

     rankSimplex: false,

     // Rank direction. Valid values are (TB, LR)

     rankDir: 'TB'

   };

   // Phase functions

   var position = require('./position')();

   // This layout object

   var self = {};

   self.orderIters = util.propertyAccessor(self, config, 'orderMaxSweeps');

   self.rankSimplex = util.propertyAccessor(self, config, 'rankSimplex');

   self.nodeSep = delegateProperty(position.nodeSep);

   self.edgeSep = delegateProperty(position.edgeSep);

   self.universalSep = delegateProperty(position.universalSep);

   self.rankSep = delegateProperty(position.rankSep);

   self.rankDir = util.propertyAccessor(self, config, 'rankDir');

   self.debugAlignment = delegateProperty(position.debugAlignment);

   self.debugLevel = util.propertyAccessor(self, config, 'debugLevel', function(x) {

     util.log.level = x;

     position.debugLevel(x);

   });

   self.run = util.time('Total layout', run);

   self._normalize = normalize;

   return self;

   /*

    * Constructs an adjacency graph using the nodes and edges specified through

    * config. For each node and edge we add a property `dagre` that contains an

    * object that will hold intermediate and final layout information. Some of

    * the contents include:

    *

    *  1) A generated ID that uniquely identifies the object.

    *  2) Dimension information for nodes (copied from the source node).

    *  3) Optional dimension information for edges.

    *

    * After the adjacency graph is constructed the code no longer needs to use

    * the original nodes and edges passed in via config.

    */

   function initLayoutGraph(inputGraph) {

     var g = new CDigraph();

     inputGraph.eachNode(function(u, value) {

       if (value === undefined) value = {};

       g.addNode(u, {

         width: value.width,

         height: value.height

       });

       if (value.hasOwnProperty('rank')) {

         g.node(u).prefRank = value.rank;

       }

     });

     // Set up subgraphs

     if (inputGraph.parent) {

       inputGraph.nodes().forEach(function(u) {

         g.parent(u, inputGraph.parent(u));

       });

     }

     inputGraph.eachEdge(function(e, u, v, value) {

       if (value === undefined) value = {};

       var newValue = {

         e: e,

         minLen: value.minLen || 1,

         width: value.width || 0,

         height: value.height || 0,

         points: []

       };

       g.addEdge(null, u, v, newValue);

     });

     // Initial graph attributes

     var graphValue = inputGraph.graph() || {};

     g.graph({

       rankDir: graphValue.rankDir || config.rankDir,

       orderRestarts: graphValue.orderRestarts

     });

     return g;

   }

   function run(inputGraph) {

     var rankSep = self.rankSep();

     var g;

     try {

       // Build internal graph

       g = util.time('initLayoutGraph', initLayoutGraph)(inputGraph);

       if (g.order() === 0) {

         return g;

       }

       // Make space for edge labels

       g.eachEdge(function(e, s, t, a) {

         a.minLen *= 2;

       });

       self.rankSep(rankSep / 2);

       // Determine the rank for each node. Nodes with a lower rank will appear

       // above nodes of higher rank.

       util.time('rank.run', rank.run)(g, config.rankSimplex);

       // Normalize the graph by ensuring that every edge is proper (each edge has

       // a length of 1). We achieve this by adding dummy nodes to long edges,

       // thus shortening them.

       util.time('normalize', normalize)(g);

       // Order the nodes so that edge crossings are minimized.

       util.time('order', order)(g, config.orderMaxSweeps);

       // Find the x and y coordinates for every node in the graph.

       util.time('position', position.run)(g);

       // De-normalize the graph by removing dummy nodes and augmenting the

       // original long edges with coordinate information.

       util.time('undoNormalize', undoNormalize)(g);

       // Reverses points for edges that are in a reversed state.

       util.time('fixupEdgePoints', fixupEdgePoints)(g);

       // Restore delete edges and reverse edges that were reversed in the rank

       // phase.

       util.time('rank.restoreEdges', rank.restoreEdges)(g);

       // Construct final result graph and return it

       return util.time('createFinalGraph', createFinalGraph)(g, inputGraph.isDirected());

     } finally {

       self.rankSep(rankSep);

     }

   }

   /*

    * This function is responsible for 'normalizing' the graph. The process of

    * normalization ensures that no edge in the graph has spans more than one

    * rank. To do this it inserts dummy nodes as needed and links them by adding

    * dummy edges. This function keeps enough information in the dummy nodes and

    * edges to ensure that the original graph can be reconstructed later.

    *

    * This method assumes that the input graph is cycle free.

    */

   function normalize(g) {

     var dummyCount = 0;

     g.eachEdge(function(e, s, t, a) {

       var sourceRank = g.node(s).rank;

       var targetRank = g.node(t).rank;

       if (sourceRank + 1 < targetRank) {

         for (var u = s, rank = sourceRank + 1, i = 0; rank < targetRank; ++rank, ++i) {

           var v = '_D' + (++dummyCount);

           var node = {

             width: a.width,

             height: a.height,

             edge: { id: e, source: s, target: t, attrs: a },

             rank: rank,

             dummy: true

           };

           // If this node represents a bend then we will use it as a control

           // point. For edges with 2 segments this will be the center dummy

           // node. For edges with more than two segments, this will be the

           // first and last dummy node.

           if (i === 0) node.index = 0;

           else if (rank + 1 === targetRank) node.index = 1;

           g.addNode(v, node);

           g.addEdge(null, u, v, {});

           u = v;

         }

         g.addEdge(null, u, t, {});

         g.delEdge(e);

       }

     });

   }

   /*

    * Reconstructs the graph as it was before normalization. The positions of

    * dummy nodes are used to build an array of points for the original 'long'

    * edge. Dummy nodes and edges are removed.

    */

   function undoNormalize(g) {

     g.eachNode(function(u, a) {

       if (a.dummy) {

         if ('index' in a) {

           var edge = a.edge;

           if (!g.hasEdge(edge.id)) {

             g.addEdge(edge.id, edge.source, edge.target, edge.attrs);

           }

           var points = g.edge(edge.id).points;

           points[a.index] = { x: a.x, y: a.y, ul: a.ul, ur: a.ur, dl: a.dl, dr: a.dr };

         }

         g.delNode(u);

       }

     });

   }

   /*

    * For each edge that was reversed during the `acyclic` step, reverse its

    * array of points.

    */

   function fixupEdgePoints(g) {

     g.eachEdge(function(e, s, t, a) { if (a.reversed) a.points.reverse(); });

   }

   function createFinalGraph(g, isDirected) {

     var out = isDirected ? new CDigraph() : new CGraph();

     out.graph(g.graph());

     g.eachNode(function(u, value) { out.addNode(u, value); });

     g.eachNode(function(u) { out.parent(u, g.parent(u)); });

     g.eachEdge(function(e, u, v, value) {

       out.addEdge(value.e, u, v, value);

     });

     // Attach bounding box information

     var maxX = 0, maxY = 0;

     g.eachNode(function(u, value) {

       if (!g.children(u).length) {

         maxX = Math.max(maxX, value.x + value.width / 2);

         maxY = Math.max(maxY, value.y + value.height / 2);

       }

     });

     g.eachEdge(function(e, u, v, value) {

       var maxXPoints = Math.max.apply(Math, value.points.map(function(p) { return p.x; }));

       var maxYPoints = Math.max.apply(Math, value.points.map(function(p) { return p.y; }));

       maxX = Math.max(maxX, maxXPoints + value.width / 2);

       maxY = Math.max(maxY, maxYPoints + value.height / 2);

     });

     out.graph().width = maxX;

     out.graph().height = maxY;

     return out;

   }

   /*

    * Given a function, a new function is returned that invokes the given

    * function. The return value from the function is always the `self` object.

    */

   function delegateProperty(f) {

     return function() {

       if (!arguments.length) return f();

       f.apply(null, arguments);

       return self;

     };

   }

 };

 },{"./order":13,"./position":18,"./rank":19,"./util":26,"graphlib":28}],13:[function(require,module,exports){

 var util = require('./util'),

     crossCount = require('./order/crossCount'),

     initLayerGraphs = require('./order/initLayerGraphs'),

     initOrder = require('./order/initOrder'),

     sortLayer = require('./order/sortLayer');

 module.exports = order;

 // The maximum number of sweeps to perform before finishing the order phase.

 var DEFAULT_MAX_SWEEPS = 24;

 order.DEFAULT_MAX_SWEEPS = DEFAULT_MAX_SWEEPS;

 /*

  * Runs the order phase with the specified `graph, `maxSweeps`, and

  * `debugLevel`. If `maxSweeps` is not specified we use `DEFAULT_MAX_SWEEPS`.

  * If `debugLevel` is not set we assume 0.

  */

 function order(g, maxSweeps) {

   if (arguments.length < 2) {

     maxSweeps = DEFAULT_MAX_SWEEPS;

   }

   var restarts = g.graph().orderRestarts || 0;

   var layerGraphs = initLayerGraphs(g);

   // TODO: remove this when we add back support for ordering clusters

   layerGraphs.forEach(function(lg) {

     lg = lg.filterNodes(function(u) { return !g.children(u).length; });

   });

   var iters = 0,

       currentBestCC,

       allTimeBestCC = Number.MAX_VALUE,

       allTimeBest = {};

   function saveAllTimeBest() {

     g.eachNode(function(u, value) { allTimeBest[u] = value.order; });

   }

   for (var j = 0; j < Number(restarts) + 1 && allTimeBestCC !== 0; ++j) {

     currentBestCC = Number.MAX_VALUE;

     initOrder(g, restarts > 0);

     util.log(2, 'Order phase start cross count: ' + g.graph().orderInitCC);

     var i, lastBest, cc;

     for (i = 0, lastBest = 0; lastBest < 4 && i < maxSweeps && currentBestCC > 0; ++i, ++lastBest, ++iters) {

       sweep(g, layerGraphs, i);

       cc = crossCount(g);

       if (cc < currentBestCC) {

         lastBest = 0;

         currentBestCC = cc;

         if (cc < allTimeBestCC) {

           saveAllTimeBest();

           allTimeBestCC = cc;

         }

       }

       util.log(3, 'Order phase start ' + j + ' iter ' + i + ' cross count: ' + cc);

     }

   }

   Object.keys(allTimeBest).forEach(function(u) {

     if (!g.children || !g.children(u).length) {

       g.node(u).order = allTimeBest[u];

     }

   });

   g.graph().orderCC = allTimeBestCC;

   util.log(2, 'Order iterations: ' + iters);

   util.log(2, 'Order phase best cross count: ' + g.graph().orderCC);

 }

 function predecessorWeights(g, nodes) {

   var weights = {};

   nodes.forEach(function(u) {

     weights[u] = g.inEdges(u).map(function(e) {

       return g.node(g.source(e)).order;

     });

   });

   return weights;

 }

 function successorWeights(g, nodes) {

   var weights = {};

   nodes.forEach(function(u) {

     weights[u] = g.outEdges(u).map(function(e) {

       return g.node(g.target(e)).order;

     });

   });

   return weights;

 }

 function sweep(g, layerGraphs, iter) {

   if (iter % 2 === 0) {

     sweepDown(g, layerGraphs, iter);

   } else {

     sweepUp(g, layerGraphs, iter);

   }

 }

 function sweepDown(g, layerGraphs) {

   var cg;

   for (i = 1; i < layerGraphs.length; ++i) {

     cg = sortLayer(layerGraphs[i], cg, predecessorWeights(g, layerGraphs[i].nodes()));

   }

 }

 function sweepUp(g, layerGraphs) {

   var cg;

   for (i = layerGraphs.length - 2; i >= 0; --i) {

     sortLayer(layerGraphs[i], cg, successorWeights(g, layerGraphs[i].nodes()));

   }

 }

 },{"./order/crossCount":14,"./order/initLayerGraphs":15,"./order/initOrder":16,"./order/sortLayer":17,"./util":26}],14:[function(require,module,exports){

 var util = require('../util');

 module.exports = crossCount;

 /*

  * Returns the cross count for the given graph.

  */

 function crossCount(g) {

   var cc = 0;

   var ordering = util.ordering(g);

   for (var i = 1; i < ordering.length; ++i) {

     cc += twoLayerCrossCount(g, ordering[i-1], ordering[i]);

   }

   return cc;

 }

 /*

  * This function searches through a ranked and ordered graph and counts the

  * number of edges that cross. This algorithm is derived from:

  *

  *    W. Barth et al., Bilayer Cross Counting, JGAA, 8(2) 179–194 (2004)

  */

 function twoLayerCrossCount(g, layer1, layer2) {

   var indices = [];

   layer1.forEach(function(u) {

     var nodeIndices = [];

     g.outEdges(u).forEach(function(e) { nodeIndices.push(g.node(g.target(e)).order); });

     nodeIndices.sort(function(x, y) { return x - y; });

     indices = indices.concat(nodeIndices);

   });

   var firstIndex = 1;

   while (firstIndex < layer2.length) firstIndex <<= 1;

   var treeSize = 2 * firstIndex - 1;

   firstIndex -= 1;

   var tree = [];

   for (var i = 0; i < treeSize; ++i) { tree[i] = 0; }

   var cc = 0;

   indices.forEach(function(i) {

     var treeIndex = i + firstIndex;

     ++tree[treeIndex];

     while (treeIndex > 0) {

       if (treeIndex % 2) {

         cc += tree[treeIndex + 1];

       }

       treeIndex = (treeIndex - 1) >> 1;

       ++tree[treeIndex];

     }

   });

   return cc;

 }

 },{"../util":26}],15:[function(require,module,exports){

 var nodesFromList = require('graphlib').filter.nodesFromList,

     /* jshint -W079 */

     Set = require('cp-data').Set;

 module.exports = initLayerGraphs;

 /*

  * This function takes a compound layered graph, g, and produces an array of

  * layer graphs. Each entry in the array represents a subgraph of nodes

  * relevant for performing crossing reduction on that layer.

  */

 function initLayerGraphs(g) {

   var ranks = [];

   function dfs(u) {

     if (u === null) {

       g.children(u).forEach(function(v) { dfs(v); });

       return;

     }

     var value = g.node(u);

     value.minRank = ('rank' in value) ? value.rank : Number.MAX_VALUE;

     value.maxRank = ('rank' in value) ? value.rank : Number.MIN_VALUE;

     var uRanks = new Set();

     g.children(u).forEach(function(v) {

       var rs = dfs(v);

       uRanks = Set.union([uRanks, rs]);

       value.minRank = Math.min(value.minRank, g.node(v).minRank);

       value.maxRank = Math.max(value.maxRank, g.node(v).maxRank);

     });

     if ('rank' in value) uRanks.add(value.rank);

     uRanks.keys().forEach(function(r) {

       if (!(r in ranks)) ranks[r] = [];

       ranks[r].push(u);

     });

     return uRanks;

   }

   dfs(null);

   var layerGraphs = [];

   ranks.forEach(function(us, rank) {

     layerGraphs[rank] = g.filterNodes(nodesFromList(us));

   });

   return layerGraphs;

 }

 },{"cp-data":5,"graphlib":28}],16:[function(require,module,exports){

 var crossCount = require('./crossCount'),

     util = require('../util');

 module.exports = initOrder;

 /*

  * Given a graph with a set of layered nodes (i.e. nodes that have a `rank`

  * attribute) this function attaches an `order` attribute that uniquely

  * arranges each node of each rank. If no constraint graph is provided the

  * order of the nodes in each rank is entirely arbitrary.

  */

 function initOrder(g, random) {

   var layers = [];

   g.eachNode(function(u, value) {

     var layer = layers[value.rank];

     if (g.children && g.children(u).length > 0) return;

     if (!layer) {

       layer = layers[value.rank] = [];

     }

     layer.push(u);

   });

   layers.forEach(function(layer) {

     if (random) {

       util.shuffle(layer);

     }

     layer.forEach(function(u, i) {

       g.node(u).order = i;

     });

   });

   var cc = crossCount(g);

   g.graph().orderInitCC = cc;

   g.graph().orderCC = Number.MAX_VALUE;

 }

 },{"../util":26,"./crossCount":14}],17:[function(require,module,exports){

 var util = require('../util');

 /*

     Digraph = require('graphlib').Digraph,

     topsort = require('graphlib').alg.topsort,

     nodesFromList = require('graphlib').filter.nodesFromList;

 */

 module.exports = sortLayer;

 /*

 function sortLayer(g, cg, weights) {

   var result = sortLayerSubgraph(g, null, cg, weights);

   result.list.forEach(function(u, i) {

     g.node(u).order = i;

   });

   return result.constraintGraph;

 }

 */

 function sortLayer(g, cg, weights) {

   var ordering = [];

   var bs = {};

   g.eachNode(function(u, value) {

     ordering[value.order] = u;

     var ws = weights[u];

     if (ws.length) {

       bs[u] = util.sum(ws) / ws.length;

     }

   });

   var toSort = g.nodes().filter(function(u) { return bs[u] !== undefined; });

   toSort.sort(function(x, y) {

     return bs[x] - bs[y] || g.node(x).order - g.node(y).order;

   });

   for (var i = 0, j = 0, jl = toSort.length; j < jl; ++i) {

     if (bs[ordering[i]] !== undefined) {

       g.node(toSort[j++]).order = i;

     }

   }

 }

 // TOOD: re-enable constrained sorting once we have a strategy for handling

 // undefined barycenters.

 /*

 function sortLayerSubgraph(g, sg, cg, weights) {

   cg = cg ? cg.filterNodes(nodesFromList(g.children(sg))) : new Digraph();

   var nodeData = {};

   g.children(sg).forEach(function(u) {

     if (g.children(u).length) {

       nodeData[u] = sortLayerSubgraph(g, u, cg, weights);

       nodeData[u].firstSG = u;

       nodeData[u].lastSG = u;

     } else {

       var ws = weights[u];

       nodeData[u] = {

         degree: ws.length,

         barycenter: ws.length > 0 ? util.sum(ws) / ws.length : 0,

         list: [u]

       };

     }

   });

   resolveViolatedConstraints(g, cg, nodeData);

   var keys = Object.keys(nodeData);

   keys.sort(function(x, y) {

     return nodeData[x].barycenter - nodeData[y].barycenter;

   });

   var result =  keys.map(function(u) { return nodeData[u]; })

                     .reduce(function(lhs, rhs) { return mergeNodeData(g, lhs, rhs); });

   return result;

 }

 /*

 function mergeNodeData(g, lhs, rhs) {

   var cg = mergeDigraphs(lhs.constraintGraph, rhs.constraintGraph);

   if (lhs.lastSG !== undefined && rhs.firstSG !== undefined) {

     if (cg === undefined) {

       cg = new Digraph();

     }

     if (!cg.hasNode(lhs.lastSG)) { cg.addNode(lhs.lastSG); }

     cg.addNode(rhs.firstSG);

     cg.addEdge(null, lhs.lastSG, rhs.firstSG);

   }

   return {

     degree: lhs.degree + rhs.degree,

     barycenter: (lhs.barycenter * lhs.degree + rhs.barycenter * rhs.degree) /

                 (lhs.degree + rhs.degree),

     list: lhs.list.concat(rhs.list),

     firstSG: lhs.firstSG !== undefined ? lhs.firstSG : rhs.firstSG,

     lastSG: rhs.lastSG !== undefined ? rhs.lastSG : lhs.lastSG,

     constraintGraph: cg

   };

 }

 function mergeDigraphs(lhs, rhs) {

   if (lhs === undefined) return rhs;

   if (rhs === undefined) return lhs;

   lhs = lhs.copy();

   rhs.nodes().forEach(function(u) { lhs.addNode(u); });

   rhs.edges().forEach(function(e, u, v) { lhs.addEdge(null, u, v); });

   return lhs;

 }

 function resolveViolatedConstraints(g, cg, nodeData) {

   // Removes nodes `u` and `v` from `cg` and makes any edges incident on them

   // incident on `w` instead.

   function collapseNodes(u, v, w) {

     // TODO original paper removes self loops, but it is not obvious when this would happen

     cg.inEdges(u).forEach(function(e) {

       cg.delEdge(e);

       cg.addEdge(null, cg.source(e), w);

     });

     cg.outEdges(v).forEach(function(e) {

       cg.delEdge(e);

       cg.addEdge(null, w, cg.target(e));

     });

     cg.delNode(u);

     cg.delNode(v);

   }

   var violated;

   while ((violated = findViolatedConstraint(cg, nodeData)) !== undefined) {

     var source = cg.source(violated),

         target = cg.target(violated);

     var v;

     while ((v = cg.addNode(null)) && g.hasNode(v)) {

       cg.delNode(v);

     }

     // Collapse barycenter and list

     nodeData[v] = mergeNodeData(g, nodeData[source], nodeData[target]);

     delete nodeData[source];

     delete nodeData[target];

     collapseNodes(source, target, v);

     if (cg.incidentEdges(v).length === 0) { cg.delNode(v); }

   }

 }

 function findViolatedConstraint(cg, nodeData) {

   var us = topsort(cg);

   for (var i = 0; i < us.length; ++i) {

     var u = us[i];

     var inEdges = cg.inEdges(u);

     for (var j = 0; j < inEdges.length; ++j) {

       var e = inEdges[j];

       if (nodeData[cg.source(e)].barycenter >= nodeData[u].barycenter) {

         return e;

       }

     }

   }

 }

 */

 },{"../util":26}],18:[function(require,module,exports){

 var util = require('./util');

 /*

  * The algorithms here are based on Brandes and Köpf, "Fast and Simple

  * Horizontal Coordinate Assignment".

  */

 module.exports = function() {

   // External configuration

   var config = {

     nodeSep: 50,

     edgeSep: 10,

     universalSep: null,

     rankSep: 30

   };

   var self = {};

   self.nodeSep = util.propertyAccessor(self, config, 'nodeSep');

   self.edgeSep = util.propertyAccessor(self, config, 'edgeSep');

   // If not null this separation value is used for all nodes and edges

   // regardless of their widths. `nodeSep` and `edgeSep` are ignored with this

   // option.

   self.universalSep = util.propertyAccessor(self, config, 'universalSep');

   self.rankSep = util.propertyAccessor(self, config, 'rankSep');

   self.debugLevel = util.propertyAccessor(self, config, 'debugLevel');

   self.run = run;

   return self;

   function run(g) {

     g = g.filterNodes(util.filterNonSubgraphs(g));

     var layering = util.ordering(g);

     var conflicts = findConflicts(g, layering);

     var xss = {};

     ['u', 'd'].forEach(function(vertDir) {

       if (vertDir === 'd') layering.reverse();

       ['l', 'r'].forEach(function(horizDir) {

         if (horizDir === 'r') reverseInnerOrder(layering);

         var dir = vertDir + horizDir;

         var align = verticalAlignment(g, layering, conflicts, vertDir === 'u' ? 'predecessors' : 'successors');

         xss[dir]= horizontalCompaction(g, layering, align.pos, align.root, align.align);

         if (config.debugLevel >= 3)

           debugPositioning(vertDir + horizDir, g, layering, xss[dir]);

         if (horizDir === 'r') flipHorizontally(xss[dir]);

         if (horizDir === 'r') reverseInnerOrder(layering);

       });

       if (vertDir === 'd') layering.reverse();

     });

     balance(g, layering, xss);

     g.eachNode(function(v) {

       var xs = [];

       for (var alignment in xss) {

         var alignmentX = xss[alignment][v];

         posXDebug(alignment, g, v, alignmentX);

         xs.push(alignmentX);

       }

       xs.sort(function(x, y) { return x - y; });

       posX(g, v, (xs[1] + xs[2]) / 2);

     });

     // Align y coordinates with ranks

     var y = 0, reverseY = g.graph().rankDir === 'BT' || g.graph().rankDir === 'RL';

     layering.forEach(function(layer) {

       var maxHeight = util.max(layer.map(function(u) { return height(g, u); }));

       y += maxHeight / 2;

       layer.forEach(function(u) {

         posY(g, u, reverseY ? -y : y);

       });

       y += maxHeight / 2 + config.rankSep;

     });

     // Translate layout so that top left corner of bounding rectangle has

     // coordinate (0, 0).

     var minX = util.min(g.nodes().map(function(u) { return posX(g, u) - width(g, u) / 2; }));

     var minY = util.min(g.nodes().map(function(u) { return posY(g, u) - height(g, u) / 2; }));

     g.eachNode(function(u) {

       posX(g, u, posX(g, u) - minX);

       posY(g, u, posY(g, u) - minY);

     });

   }

   /*

    * Generate an ID that can be used to represent any undirected edge that is

    * incident on `u` and `v`.

    */

   function undirEdgeId(u, v) {

     return u < v

       ? u.toString().length + ':' + u + '-' + v

       : v.toString().length + ':' + v + '-' + u;

   }

   function findConflicts(g, layering) {

     var conflicts = {}, // Set of conflicting edge ids

         pos = {},       // Position of node in its layer

         prevLayer,

         currLayer,

         k0,     // Position of the last inner segment in the previous layer

         l,      // Current position in the current layer (for iteration up to `l1`)

         k1;     // Position of the next inner segment in the previous layer or

                 // the position of the last element in the previous layer

     if (layering.length <= 2) return conflicts;

     function updateConflicts(v) {

       var k = pos[v];

       if (k < k0 || k > k1) {

         conflicts[undirEdgeId(currLayer[l], v)] = true;

       }

     }

     layering[1].forEach(function(u, i) { pos[u] = i; });

     for (var i = 1; i < layering.length - 1; ++i) {

       prevLayer = layering[i];

       currLayer = layering[i+1];

       k0 = 0;

       l = 0;

       // Scan current layer for next node that is incident to an inner segement

       // between layering[i+1] and layering[i].

       for (var l1 = 0; l1 < currLayer.length; ++l1) {

         var u = currLayer[l1]; // Next inner segment in the current layer or

                                // last node in the current layer

         pos[u] = l1;

         k1 = undefined;

         if (g.node(u).dummy) {

           var uPred = g.predecessors(u)[0];

           // Note: In the case of self loops and sideways edges it is possible

           // for a dummy not to have a predecessor.

           if (uPred !== undefined && g.node(uPred).dummy)

             k1 = pos[uPred];

         }

         if (k1 === undefined && l1 === currLayer.length - 1)

           k1 = prevLayer.length - 1;

         if (k1 !== undefined) {

           for (; l <= l1; ++l) {

             g.predecessors(currLayer[l]).forEach(updateConflicts);

           }

           k0 = k1;

         }

       }

     }

     return conflicts;

   }

   function verticalAlignment(g, layering, conflicts, relationship) {

     var pos = {},   // Position for a node in its layer

         root = {},  // Root of the block that the node participates in

         align = {}; // Points to the next node in the block or, if the last

                     // element in the block, points to the first block's root

     layering.forEach(function(layer) {

       layer.forEach(function(u, i) {

         root[u] = u;

         align[u] = u;

         pos[u] = i;

       });

     });

     layering.forEach(function(layer) {

       var prevIdx = -1;

       layer.forEach(function(v) {

         var related = g[relationship](v), // Adjacent nodes from the previous layer

             mid;                          // The mid point in the related array

         if (related.length > 0) {

           related.sort(function(x, y) { return pos[x] - pos[y]; });

           mid = (related.length - 1) / 2;

           related.slice(Math.floor(mid), Math.ceil(mid) + 1).forEach(function(u) {

             if (align[v] === v) {

               if (!conflicts[undirEdgeId(u, v)] && prevIdx < pos[u]) {

                 align[u] = v;

                 align[v] = root[v] = root[u];

                 prevIdx = pos[u];

               }

             }

           });

         }

       });

     });

     return { pos: pos, root: root, align: align };

   }

   // This function deviates from the standard BK algorithm in two ways. First

   // it takes into account the size of the nodes. Second it includes a fix to

   // the original algorithm that is described in Carstens, "Node and Label

   // Placement in a Layered Layout Algorithm".

   function horizontalCompaction(g, layering, pos, root, align) {

     var sink = {},       // Mapping of node id -> sink node id for class

         maybeShift = {}, // Mapping of sink node id -> { class node id, min shift }

         shift = {},      // Mapping of sink node id -> shift

         pred = {},       // Mapping of node id -> predecessor node (or null)

         xs = {};         // Calculated X positions

     layering.forEach(function(layer) {

       layer.forEach(function(u, i) {

         sink[u] = u;

         maybeShift[u] = {};

         if (i > 0)

           pred[u] = layer[i - 1];

       });

     });

     function updateShift(toShift, neighbor, delta) {

       if (!(neighbor in maybeShift[toShift])) {

         maybeShift[toShift][neighbor] = delta;

       } else {

         maybeShift[toShift][neighbor] = Math.min(maybeShift[toShift][neighbor], delta);

       }

     }

     function placeBlock(v) {

       if (!(v in xs)) {

         xs[v] = 0;

         var w = v;

         do {

           if (pos[w] > 0) {

             var u = root[pred[w]];

             placeBlock(u);

             if (sink[v] === v) {

               sink[v] = sink[u];

             }

             var delta = sep(g, pred[w]) + sep(g, w);

             if (sink[v] !== sink[u]) {

               updateShift(sink[u], sink[v], xs[v] - xs[u] - delta);

             } else {

               xs[v] = Math.max(xs[v], xs[u] + delta);

             }

           }

           w = align[w];

         } while (w !== v);

       }

     }

     // Root coordinates relative to sink

     util.values(root).forEach(function(v) {

       placeBlock(v);

     });

     // Absolute coordinates

     // There is an assumption here that we've resolved shifts for any classes

     // that begin at an earlier layer. We guarantee this by visiting layers in

     // order.

     layering.forEach(function(layer) {

       layer.forEach(function(v) {

         xs[v] = xs[root[v]];

         if (v === root[v] && v === sink[v]) {

           var minShift = 0;

           if (v in maybeShift && Object.keys(maybeShift[v]).length > 0) {

             minShift = util.min(Object.keys(maybeShift[v])

                                  .map(function(u) {

                                       return maybeShift[v][u] + (u in shift ? shift[u] : 0);

                                       }

                                  ));

           }

           shift[v] = minShift;

         }

       });

     });

     layering.forEach(function(layer) {

       layer.forEach(function(v) {

         xs[v] += shift[sink[root[v]]] || 0;

       });

     });

     return xs;

   }

   function findMinCoord(g, layering, xs) {

     return util.min(layering.map(function(layer) {

       var u = layer[0];

       return xs[u];

     }));

   }

   function findMaxCoord(g, layering, xs) {

     return util.max(layering.map(function(layer) {

       var u = layer[layer.length - 1];

       return xs[u];

     }));

   }

   function balance(g, layering, xss) {

     var min = {},                            // Min coordinate for the alignment

         max = {},                            // Max coordinate for the alginment

         smallestAlignment,

         shift = {};                          // Amount to shift a given alignment

     function updateAlignment(v) {

       xss[alignment][v] += shift[alignment];

     }

     var smallest = Number.POSITIVE_INFINITY;

     for (var alignment in xss) {

       var xs = xss[alignment];

       min[alignment] = findMinCoord(g, layering, xs);

       max[alignment] = findMaxCoord(g, layering, xs);

       var w = max[alignment] - min[alignment];

       if (w < smallest) {

         smallest = w;

         smallestAlignment = alignment;

       }

     }

     // Determine how much to adjust positioning for each alignment

     ['u', 'd'].forEach(function(vertDir) {

       ['l', 'r'].forEach(function(horizDir) {

         var alignment = vertDir + horizDir;

         shift[alignment] = horizDir === 'l'

             ? min[smallestAlignment] - min[alignment]

             : max[smallestAlignment] - max[alignment];

       });

     });

     // Find average of medians for xss array

     for (alignment in xss) {

       g.eachNode(updateAlignment);

     }

   }

   function flipHorizontally(xs) {

     for (var u in xs) {

       xs[u] = -xs[u];

     }

   }

   function reverseInnerOrder(layering) {

     layering.forEach(function(layer) {

       layer.reverse();

     });

   }

   function width(g, u) {

     switch (g.graph().rankDir) {

       case 'LR': return g.node(u).height;

       case 'RL': return g.node(u).height;

       default:   return g.node(u).width;

     }

   }

   function height(g, u) {

     switch(g.graph().rankDir) {

       case 'LR': return g.node(u).width;

       case 'RL': return g.node(u).width;

       default:   return g.node(u).height;

     }

   }

   function sep(g, u) {

     if (config.universalSep !== null) {

       return config.universalSep;

     }

     var w = width(g, u);

     var s = g.node(u).dummy ? config.edgeSep : config.nodeSep;

     return (w + s) / 2;

   }

   function posX(g, u, x) {

     if (g.graph().rankDir === 'LR' || g.graph().rankDir === 'RL') {

       if (arguments.length < 3) {

         return g.node(u).y;

       } else {

         g.node(u).y = x;

       }

     } else {

       if (arguments.length < 3) {

         return g.node(u).x;

       } else {

         g.node(u).x = x;

       }

     }

   }

   function posXDebug(name, g, u, x) {

     if (g.graph().rankDir === 'LR' || g.graph().rankDir === 'RL') {

       if (arguments.length < 3) {

         return g.node(u)[name];

       } else {

         g.node(u)[name] = x;

       }

     } else {

       if (arguments.length < 3) {

         return g.node(u)[name];

       } else {

         g.node(u)[name] = x;

       }

     }

   }

   function posY(g, u, y) {

     if (g.graph().rankDir === 'LR' || g.graph().rankDir === 'RL') {

       if (arguments.length < 3) {

         return g.node(u).x;

       } else {

         g.node(u).x = y;

       }

     } else {

       if (arguments.length < 3) {

         return g.node(u).y;

       } else {

         g.node(u).y = y;

       }

     }

   }

   function debugPositioning(align, g, layering, xs) {

     layering.forEach(function(l, li) {

       var u, xU;

       l.forEach(function(v) {

         var xV = xs[v];

         if (u) {

           var s = sep(g, u) + sep(g, v);

           if (xV - xU < s)

             console.log('Position phase: sep violation. Align: ' + align + '. Layer: ' + li + '. ' +

               'U: ' + u + ' V: ' + v + '. Actual sep: ' + (xV - xU) + ' Expected sep: ' + s);

         }

         u = v;

         xU = xV;

       });

     });

   }

 };

 },{"./util":26}],19:[function(require,module,exports){

 var util = require('./util'),

     acyclic = require('./rank/acyclic'),

     initRank = require('./rank/initRank'),

     feasibleTree = require('./rank/feasibleTree'),

     constraints = require('./rank/constraints'),

     simplex = require('./rank/simplex'),

     components = require('graphlib').alg.components,

     filter = require('graphlib').filter;

 exports.run = run;

 exports.restoreEdges = restoreEdges;

 /*

  * Heuristic function that assigns a rank to each node of the input graph with

  * the intent of minimizing edge lengths, while respecting the `minLen`

  * attribute of incident edges.

  *

  * Prerequisites:

  *

  *  * Each edge in the input graph must have an assigned 'minLen' attribute

  */

 function run(g, useSimplex) {

   expandSelfLoops(g);

   // If there are rank constraints on nodes, then build a new graph that

   // encodes the constraints.

   util.time('constraints.apply', constraints.apply)(g);

   expandSidewaysEdges(g);

   // Reverse edges to get an acyclic graph, we keep the graph in an acyclic

   // state until the very end.

   util.time('acyclic', acyclic)(g);

   // Convert the graph into a flat graph for ranking

   var flatGraph = g.filterNodes(util.filterNonSubgraphs(g));

   // Assign an initial ranking using DFS.

   initRank(flatGraph);

   // For each component improve the assigned ranks.

   components(flatGraph).forEach(function(cmpt) {

     var subgraph = flatGraph.filterNodes(filter.nodesFromList(cmpt));

     rankComponent(subgraph, useSimplex);

   });

   // Relax original constraints

   util.time('constraints.relax', constraints.relax(g));

   // When handling nodes with constrained ranks it is possible to end up with

   // edges that point to previous ranks. Most of the subsequent algorithms assume

   // that edges are pointing to successive ranks only. Here we reverse any "back

   // edges" and mark them as such. The acyclic algorithm will reverse them as a

   // post processing step.

   util.time('reorientEdges', reorientEdges)(g);

 }

 function restoreEdges(g) {

   acyclic.undo(g);

 }

 /*

  * Expand self loops into three dummy nodes. One will sit above the incident

  * node, one will be at the same level, and one below. The result looks like:

  *

  *         /--<--x--->--\

  *     node              y

  *         \--<--z--->--/

  *

  * Dummy nodes x, y, z give us the shape of a loop and node y is where we place

  * the label.

  *

  * TODO: consolidate knowledge of dummy node construction.

  * TODO: support minLen = 2

  */

 function expandSelfLoops(g) {

   g.eachEdge(function(e, u, v, a) {

     if (u === v) {

       var x = addDummyNode(g, e, u, v, a, 0, false),

           y = addDummyNode(g, e, u, v, a, 1, true),

           z = addDummyNode(g, e, u, v, a, 2, false);

       g.addEdge(null, x, u, {minLen: 1, selfLoop: true});

       g.addEdge(null, x, y, {minLen: 1, selfLoop: true});

       g.addEdge(null, u, z, {minLen: 1, selfLoop: true});

       g.addEdge(null, y, z, {minLen: 1, selfLoop: true});

       g.delEdge(e);

     }

   });

 }

 function expandSidewaysEdges(g) {

   g.eachEdge(function(e, u, v, a) {

     if (u === v) {

       var origEdge = a.originalEdge,

           dummy = addDummyNode(g, origEdge.e, origEdge.u, origEdge.v, origEdge.value, 0, true);

       g.addEdge(null, u, dummy, {minLen: 1});

       g.addEdge(null, dummy, v, {minLen: 1});

       g.delEdge(e);

     }

   });

 }

 function addDummyNode(g, e, u, v, a, index, isLabel) {

   return g.addNode(null, {

     width: isLabel ? a.width : 0,

     height: isLabel ? a.height : 0,

     edge: { id: e, source: u, target: v, attrs: a },

     dummy: true,

     index: index

   });

 }

 function reorientEdges(g) {

   g.eachEdge(function(e, u, v, value) {

     if (g.node(u).rank > g.node(v).rank) {

       g.delEdge(e);

       value.reversed = true;

       g.addEdge(e, v, u, value);

     }

   });

 }

 function rankComponent(subgraph, useSimplex) {

   var spanningTree = feasibleTree(subgraph);

   if (useSimplex) {

     util.log(1, 'Using network simplex for ranking');

     simplex(subgraph, spanningTree);

   }

   normalize(subgraph);

 }

 function normalize(g) {

   var m = util.min(g.nodes().map(function(u) { return g.node(u).rank; }));

   g.eachNode(function(u, node) { node.rank -= m; });

 }

 },{"./rank/acyclic":20,"./rank/constraints":21,"./rank/feasibleTree":22,"./rank/initRank":23,"./rank/simplex":25,"./util":26,"graphlib":28}],20:[function(require,module,exports){

 var util = require('../util');

 module.exports = acyclic;

 module.exports.undo = undo;

 /*

  * This function takes a directed graph that may have cycles and reverses edges

  * as appropriate to break these cycles. Each reversed edge is assigned a

  * `reversed` attribute with the value `true`.

  *

  * There should be no self loops in the graph.

  */

 function acyclic(g) {

   var onStack = {},

       visited = {},

       reverseCount = 0;

   function dfs(u) {

     if (u in visited) return;

     visited[u] = onStack[u] = true;

     g.outEdges(u).forEach(function(e) {

       var t = g.target(e),

           value;

       if (u === t) {

         console.error('Warning: found self loop "' + e + '" for node "' + u + '"');

       } else if (t in onStack) {

         value = g.edge(e);

         g.delEdge(e);

         value.reversed = true;

         ++reverseCount;

         g.addEdge(e, t, u, value);

       } else {

         dfs(t);

       }

     });

     delete onStack[u];

   }

   g.eachNode(function(u) { dfs(u); });

   util.log(2, 'Acyclic Phase: reversed ' + reverseCount + ' edge(s)');

   return reverseCount;

 }

 /*

  * Given a graph that has had the acyclic operation applied, this function

  * undoes that operation. More specifically, any edge with the `reversed`

  * attribute is again reversed to restore the original direction of the edge.

  */

 function undo(g) {

   g.eachEdge(function(e, s, t, a) {

     if (a.reversed) {

       delete a.reversed;

       g.delEdge(e);

       g.addEdge(e, t, s, a);

     }

   });

 }

 },{"../util":26}],21:[function(require,module,exports){

 exports.apply = function(g) {

   function dfs(sg) {

     var rankSets = {};

     g.children(sg).forEach(function(u) {

       if (g.children(u).length) {

         dfs(u);

         return;

       }

       var value = g.node(u),

           prefRank = value.prefRank;

       if (prefRank !== undefined) {

         if (!checkSupportedPrefRank(prefRank)) { return; }

         if (!(prefRank in rankSets)) {

           rankSets.prefRank = [u];

         } else {

           rankSets.prefRank.push(u);

         }

         var newU = rankSets[prefRank];

         if (newU === undefined) {

           newU = rankSets[prefRank] = g.addNode(null, { originalNodes: [] });

           g.parent(newU, sg);

         }

         redirectInEdges(g, u, newU, prefRank === 'min');

         redirectOutEdges(g, u, newU, prefRank === 'max');

         // Save original node and remove it from reduced graph

         g.node(newU).originalNodes.push({ u: u, value: value, parent: sg });

         g.delNode(u);

       }

     });

     addLightEdgesFromMinNode(g, sg, rankSets.min);

     addLightEdgesToMaxNode(g, sg, rankSets.max);

   }

   dfs(null);

 };

 function checkSupportedPrefRank(prefRank) {

   if (prefRank !== 'min' && prefRank !== 'max' && prefRank.indexOf('same_') !== 0) {

     console.error('Unsupported rank type: ' + prefRank);

     return false;

   }

   return true;

 }

 function redirectInEdges(g, u, newU, reverse) {

   g.inEdges(u).forEach(function(e) {

     var origValue = g.edge(e),

         value;

     if (origValue.originalEdge) {

       value = origValue;

     } else {

       value =  {

         originalEdge: { e: e, u: g.source(e), v: g.target(e), value: origValue },

         minLen: g.edge(e).minLen

       };

     }

     // Do not reverse edges for self-loops.

     if (origValue.selfLoop) {

       reverse = false;

     }

     if (reverse) {

       // Ensure that all edges to min are reversed

       g.addEdge(null, newU, g.source(e), value);

       value.reversed = true;

     } else {

       g.addEdge(null, g.source(e), newU, value);

     }

   });

 }

 function redirectOutEdges(g, u, newU, reverse) {

   g.outEdges(u).forEach(function(e) {

     var origValue = g.edge(e),

         value;

     if (origValue.originalEdge) {

       value = origValue;

     } else {

       value =  {

         originalEdge: { e: e, u: g.source(e), v: g.target(e), value: origValue },

         minLen: g.edge(e).minLen

       };

     }

     // Do not reverse edges for self-loops.

     if (origValue.selfLoop) {

       reverse = false;

     }

     if (reverse) {

       // Ensure that all edges from max are reversed

       g.addEdge(null, g.target(e), newU, value);

       value.reversed = true;

     } else {

       g.addEdge(null, newU, g.target(e), value);

     }

   });

 }

 function addLightEdgesFromMinNode(g, sg, minNode) {

   if (minNode !== undefined) {

     g.children(sg).forEach(function(u) {

       // The dummy check ensures we don't add an edge if the node is involved

       // in a self loop or sideways edge.

       if (u !== minNode && !g.outEdges(minNode, u).length && !g.node(u).dummy) {

         g.addEdge(null, minNode, u, { minLen: 0 });

       }

     });

   }

 }

 function addLightEdgesToMaxNode(g, sg, maxNode) {

   if (maxNode !== undefined) {

     g.children(sg).forEach(function(u) {

       // The dummy check ensures we don't add an edge if the node is involved

       // in a self loop or sideways edge.

       if (u !== maxNode && !g.outEdges(u, maxNode).length && !g.node(u).dummy) {

         g.addEdge(null, u, maxNode, { minLen: 0 });

       }

     });

   }

 }

 /*

  * This function "relaxes" the constraints applied previously by the "apply"

  * function. It expands any nodes that were collapsed and assigns the rank of

  * the collapsed node to each of the expanded nodes. It also restores the

  * original edges and removes any dummy edges pointing at the collapsed nodes.

  *

  * Note that the process of removing collapsed nodes also removes dummy edges

  * automatically.

  */

 exports.relax = function(g) {

   // Save original edges

   var originalEdges = [];

   g.eachEdge(function(e, u, v, value) {

     var originalEdge = value.originalEdge;

     if (originalEdge) {

       originalEdges.push(originalEdge);

     }

   });

   // Expand collapsed nodes

   g.eachNode(function(u, value) {

     var originalNodes = value.originalNodes;

     if (originalNodes) {

       originalNodes.forEach(function(originalNode) {

         originalNode.value.rank = value.rank;

         g.addNode(originalNode.u, originalNode.value);

         g.parent(originalNode.u, originalNode.parent);

       });

       g.delNode(u);

     }

   });

   // Restore original edges

   originalEdges.forEach(function(edge) {

     g.addEdge(edge.e, edge.u, edge.v, edge.value);

   });

 };

 },{}],22:[function(require,module,exports){

 /* jshint -W079 */

 var Set = require('cp-data').Set,

 /* jshint +W079 */

     Digraph = require('graphlib').Digraph,

     util = require('../util');

 module.exports = feasibleTree;

 /*

  * Given an acyclic graph with each node assigned a `rank` attribute, this

  * function constructs and returns a spanning tree. This function may reduce

  * the length of some edges from the initial rank assignment while maintaining

  * the `minLen` specified by each edge.

  *

  * Prerequisites:

  *

  * * The input graph is acyclic

  * * Each node in the input graph has an assigned `rank` attribute

  * * Each edge in the input graph has an assigned `minLen` attribute

  *

  * Outputs:

  *

  * A feasible spanning tree for the input graph (i.e. a spanning tree that

  * respects each graph edge's `minLen` attribute) represented as a Digraph with

  * a `root` attribute on graph.

  *

  * Nodes have the same id and value as that in the input graph.

  *

  * Edges in the tree have arbitrarily assigned ids. The attributes for edges

  * include `reversed`. `reversed` indicates that the edge is a

  * back edge in the input graph.

  */

 function feasibleTree(g) {

   var remaining = new Set(g.nodes()),

       tree = new Digraph();

   if (remaining.size() === 1) {

     var root = g.nodes()[0];

     tree.addNode(root, {});

     tree.graph({ root: root });

     return tree;

   }

   function addTightEdges(v) {

     var continueToScan = true;

     g.predecessors(v).forEach(function(u) {

       if (remaining.has(u) && !slack(g, u, v)) {

         if (remaining.has(v)) {

           tree.addNode(v, {});

           remaining.remove(v);

           tree.graph({ root: v });

         }

         tree.addNode(u, {});

         tree.addEdge(null, u, v, { reversed: true });

         remaining.remove(u);

         addTightEdges(u);

         continueToScan = false;

       }

     });

     g.successors(v).forEach(function(w)  {

       if (remaining.has(w) && !slack(g, v, w)) {

         if (remaining.has(v)) {

           tree.addNode(v, {});

           remaining.remove(v);

           tree.graph({ root: v });

         }

         tree.addNode(w, {});

         tree.addEdge(null, v, w, {});

         remaining.remove(w);

         addTightEdges(w);

         continueToScan = false;

       }

     });

     return continueToScan;

   }

   function createTightEdge() {

     var minSlack = Number.MAX_VALUE;

     remaining.keys().forEach(function(v) {

       g.predecessors(v).forEach(function(u) {

         if (!remaining.has(u)) {

           var edgeSlack = slack(g, u, v);

           if (Math.abs(edgeSlack) < Math.abs(minSlack)) {

             minSlack = -edgeSlack;

           }

         }

       });

       g.successors(v).forEach(function(w) {

         if (!remaining.has(w)) {

           var edgeSlack = slack(g, v, w);

           if (Math.abs(edgeSlack) < Math.abs(minSlack)) {

             minSlack = edgeSlack;

           }

         }

       });

     });

     tree.eachNode(function(u) { g.node(u).rank -= minSlack; });

   }

   while (remaining.size()) {

     var nodesToSearch = !tree.order() ? remaining.keys() : tree.nodes();

     for (var i = 0, il = nodesToSearch.length;

          i < il && addTightEdges(nodesToSearch[i]);

          ++i);

     if (remaining.size()) {

       createTightEdge();

     }

   }

   return tree;

 }

 function slack(g, u, v) {

   var rankDiff = g.node(v).rank - g.node(u).rank;

   var maxMinLen = util.max(g.outEdges(u, v)

                             .map(function(e) { return g.edge(e).minLen; }));

   return rankDiff - maxMinLen;

 }

 },{"../util":26,"cp-data":5,"graphlib":28}],23:[function(require,module,exports){

 var util = require('../util'),

     topsort = require('graphlib').alg.topsort;

 module.exports = initRank;

 /*

  * Assigns a `rank` attribute to each node in the input graph and ensures that

  * this rank respects the `minLen` attribute of incident edges.

  *

  * Prerequisites:

  *

  *  * The input graph must be acyclic

  *  * Each edge in the input graph must have an assigned 'minLen' attribute

  */

 function initRank(g) {

   var sorted = topsort(g);

   sorted.forEach(function(u) {

     var inEdges = g.inEdges(u);

     if (inEdges.length === 0) {

       g.node(u).rank = 0;

       return;

     }

     var minLens = inEdges.map(function(e) {

       return g.node(g.source(e)).rank + g.edge(e).minLen;

     });

     g.node(u).rank = util.max(minLens);

   });

 }

 },{"../util":26,"graphlib":28}],24:[function(require,module,exports){

 module.exports = {

   slack: slack

 };

 /*

  * A helper to calculate the slack between two nodes (`u` and `v`) given a

  * `minLen` constraint. The slack represents how much the distance between `u`

  * and `v` could shrink while maintaining the `minLen` constraint. If the value

  * is negative then the constraint is currently violated.

  *

   This function requires that `u` and `v` are in `graph` and they both have a

   `rank` attribute.

  */

 function slack(graph, u, v, minLen) {

   return Math.abs(graph.node(u).rank - graph.node(v).rank) - minLen;

 }

 },{}],25:[function(require,module,exports){

 var util = require('../util'),

     rankUtil = require('./rankUtil');

 module.exports = simplex;

 function simplex(graph, spanningTree) {

   // The network simplex algorithm repeatedly replaces edges of

   // the spanning tree with negative cut values until no such

   // edge exists.

   initCutValues(graph, spanningTree);

   while (true) {

     var e = leaveEdge(spanningTree);

     if (e === null) break;

     var f = enterEdge(graph, spanningTree, e);

     exchange(graph, spanningTree, e, f);

   }

 }

 /*

  * Set the cut values of edges in the spanning tree by a depth-first

  * postorder traversal.  The cut value corresponds to the cost, in

  * terms of a ranking's edge length sum, of lengthening an edge.

  * Negative cut values typically indicate edges that would yield a

  * smaller edge length sum if they were lengthened.

  */

 function initCutValues(graph, spanningTree) {

   computeLowLim(spanningTree);

   spanningTree.eachEdge(function(id, u, v, treeValue) {

     treeValue.cutValue = 0;

   });

   // Propagate cut values up the tree.

   function dfs(n) {