flink-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From u..@apache.org
Subject [50/84] [abbrv] flink-web git commit: Rebuild website
Date Wed, 18 Jan 2017 14:00:50 GMT
http://git-wip-us.apache.org/repos/asf/flink-web/blob/61adc137/content/visualizer/js/dagre-d3.js
----------------------------------------------------------------------
diff --git a/content/visualizer/js/dagre-d3.js b/content/visualizer/js/dagre-d3.js
new file mode 100755
index 0000000..482ce82
--- /dev/null
+++ b/content/visualizer/js/dagre-d3.js
@@ -0,0 +1,4560 @@
+;(function e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);throw new Error("Cannot find module '"+o+"'")}var f=n[o]={exports:{}};t[o][0].call(f.exports,function(e){var n=t[o][1][e];return s(n?n:e)},f,f.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return s})({1:[function(require,module,exports){
+var global=self;/**
+ * @license
+ * Copyright (c) 2012-2013 Chris Pettitt
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+ * THE SOFTWARE.
+ */
+global.dagreD3 = require('./index');
+
+},{"./index":2}],2:[function(require,module,exports){
+/**
+ * @license
+ * Copyright (c) 2012-2013 Chris Pettitt
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+ * THE SOFTWARE.
+ */
+module.exports =  {
+  Digraph: require('graphlib').Digraph,
+  Renderer: require('./lib/Renderer'),
+  json: require('graphlib').converter.json,
+  layout: require('dagre').layout,
+  version: require('./lib/version')
+};
+
+},{"./lib/Renderer":3,"./lib/version":4,"dagre":11,"graphlib":28}],3:[function(require,module,exports){
+var layout = require('dagre').layout;
+
+var d3;
+try { d3 = require('d3'); } catch (_) { d3 = window.d3; }
+
+module.exports = Renderer;
+
+function Renderer() {
+  // Set up defaults...
+  this._layout = layout();
+
+  this.drawNodes(defaultDrawNodes);
+  this.drawEdgeLabels(defaultDrawEdgeLabels);
+  this.drawEdgePaths(defaultDrawEdgePaths);
+  this.positionNodes(defaultPositionNodes);
+  this.positionEdgeLabels(defaultPositionEdgeLabels);
+  this.positionEdgePaths(defaultPositionEdgePaths);
+  this.transition(defaultTransition);
+  this.postLayout(defaultPostLayout);
+  this.postRender(defaultPostRender);
+
+  this.edgeInterpolate('bundle');
+  this.edgeTension(0.95);
+}
+
+Renderer.prototype.layout = function(layout) {
+  if (!arguments.length) { return this._layout; }
+  this._layout = layout;
+  return this;
+};
+
+Renderer.prototype.drawNodes = function(drawNodes) {
+  if (!arguments.length) { return this._drawNodes; }
+  this._drawNodes = bind(drawNodes, this);
+  return this;
+};
+
+Renderer.prototype.drawEdgeLabels = function(drawEdgeLabels) {
+  if (!arguments.length) { return this._drawEdgeLabels; }
+  this._drawEdgeLabels = bind(drawEdgeLabels, this);
+  return this;
+};
+
+Renderer.prototype.drawEdgePaths = function(drawEdgePaths) {
+  if (!arguments.length) { return this._drawEdgePaths; }
+  this._drawEdgePaths = bind(drawEdgePaths, this);
+  return this;
+};
+
+Renderer.prototype.positionNodes = function(positionNodes) {
+  if (!arguments.length) { return this._positionNodes; }
+  this._positionNodes = bind(positionNodes, this);
+  return this;
+};
+
+Renderer.prototype.positionEdgeLabels = function(positionEdgeLabels) {
+  if (!arguments.length) { return this._positionEdgeLabels; }
+  this._positionEdgeLabels = bind(positionEdgeLabels, this);
+  return this;
+};
+
+Renderer.prototype.positionEdgePaths = function(positionEdgePaths) {
+  if (!arguments.length) { return this._positionEdgePaths; }
+  this._positionEdgePaths = bind(positionEdgePaths, this);
+  return this;
+};
+
+Renderer.prototype.transition = function(transition) {
+  if (!arguments.length) { return this._transition; }
+  this._transition = bind(transition, this);
+  return this;
+};
+
+Renderer.prototype.postLayout = function(postLayout) {
+  if (!arguments.length) { return this._postLayout; }
+  this._postLayout = bind(postLayout, this);
+  return this;
+};
+
+Renderer.prototype.postRender = function(postRender) {
+  if (!arguments.length) { return this._postRender; }
+  this._postRender = bind(postRender, this);
+  return this;
+};
+
+Renderer.prototype.edgeInterpolate = function(edgeInterpolate) {
+  if (!arguments.length) { return this._edgeInterpolate; }
+  this._edgeInterpolate = edgeInterpolate;
+  return this;
+};
+
+Renderer.prototype.edgeTension = function(edgeTension) {
+  if (!arguments.length) { return this._edgeTension; }
+  this._edgeTension = edgeTension;
+  return this;
+};
+
+Renderer.prototype.run = function(graph, svg) {
+  // First copy the input graph so that it is not changed by the rendering
+  // process.
+  graph = copyAndInitGraph(graph);
+
+  // Create layers
+  svg
+    .selectAll('g.edgePaths, g.edgeLabels, g.nodes')
+    .data(['edgePaths', 'edgeLabels', 'nodes'])
+    .enter()
+      .append('g')
+      .attr('class', function(d) { return d; });
+
+
+  // Create node and edge roots, attach labels, and capture dimension
+  // information for use with layout.
+  var svgNodes = this._drawNodes(graph, svg.select('g.nodes'));
+  var svgEdgeLabels = this._drawEdgeLabels(graph, svg.select('g.edgeLabels'));
+
+  svgNodes.each(function(u) { calculateDimensions(this, graph.node(u)); });
+  svgEdgeLabels.each(function(e) { calculateDimensions(this, graph.edge(e)); });
+
+  // Now apply the layout function
+  var result = runLayout(graph, this._layout);
+
+  // Run any user-specified post layout processing
+  this._postLayout(result, svg);
+
+  var svgEdgePaths = this._drawEdgePaths(graph, svg.select('g.edgePaths'));
+
+  // Apply the layout information to the graph
+  this._positionNodes(result, svgNodes);
+  this._positionEdgeLabels(result, svgEdgeLabels);
+  this._positionEdgePaths(result, svgEdgePaths);
+
+  this._postRender(result, svg);
+
+  return result;
+};
+
+function copyAndInitGraph(graph) {
+  var copy = graph.copy();
+
+  // Init labels if they were not present in the source graph
+  copy.nodes().forEach(function(u) {
+    var value = copy.node(u);
+    if (value === undefined) {
+      value = {};
+      copy.node(u, value);
+    }
+    if (!('label' in value)) { value.label = ''; }
+  });
+
+  copy.edges().forEach(function(e) {
+    var value = copy.edge(e);
+    if (value === undefined) {
+      value = {};
+      copy.edge(e, value);
+    }
+    if (!('label' in value)) { value.label = ''; }
+  });
+
+  return copy;
+}
+
+function calculateDimensions(group, value) {
+  var bbox = group.getBBox();
+  value.width = bbox.width;
+  value.height = bbox.height;
+}
+
+function runLayout(graph, layout) {
+  var result = layout.run(graph);
+
+  // Copy labels to the result graph
+  graph.eachNode(function(u, value) { result.node(u).label = value.label; });
+  graph.eachEdge(function(e, u, v, value) { result.edge(e).label = value.label; });
+
+  return result;
+}
+
+function defaultDrawNodes(g, root) {
+  var nodes = g.nodes().filter(function(u) { return !isComposite(g, u); });
+
+  var svgNodes = root
+    .selectAll('g.node')
+    .classed('enter', false)
+    .data(nodes, function(u) { return u; });
+
+  svgNodes.selectAll('*').remove();
+
+  svgNodes
+    .enter()
+      .append('g')
+        .style('opacity', 0)
+        .attr('class', 'node enter');
+
+  svgNodes.each(function(u) { addLabel(g.node(u), d3.select(this), 10, 10); });
+
+  this._transition(svgNodes.exit())
+      .style('opacity', 0)
+      .remove();
+
+  return svgNodes;
+}
+
+function defaultDrawEdgeLabels(g, root) {
+  var svgEdgeLabels = root
+    .selectAll('g.edgeLabel')
+    .classed('enter', false)
+    .data(g.edges(), function (e) { return e; });
+
+  svgEdgeLabels.selectAll('*').remove();
+
+  svgEdgeLabels
+    .enter()
+      .append('g')
+        .style('opacity', 0)
+        .attr('class', 'edgeLabel enter');
+
+  svgEdgeLabels.each(function(e) { addLabel(g.edge(e), d3.select(this), 0, 0); });
+
+  this._transition(svgEdgeLabels.exit())
+      .style('opacity', 0)
+      .remove();
+
+  return svgEdgeLabels;
+}
+
+var defaultDrawEdgePaths = function(g, root) {
+  var svgEdgePaths = root
+    .selectAll('g.edgePath')
+    .classed('enter', false)
+    .data(g.edges(), function(e) { return e; });
+
+  svgEdgePaths
+    .enter()
+      .append('g')
+        .attr('class', 'edgePath enter')
+        .append('path')
+          .style('opacity', 0)
+          .attr('marker-end', 'url(#arrowhead)');
+
+  this._transition(svgEdgePaths.exit())
+      .style('opacity', 0)
+      .remove();
+
+  return svgEdgePaths;
+};
+
+function defaultPositionNodes(g, svgNodes, svgNodesEnter) {
+  function transform(u) {
+    var value = g.node(u);
+    return 'translate(' + value.x + ',' + value.y + ')';
+  }
+
+  // For entering nodes, position immediately without transition
+  svgNodes.filter('.enter').attr('transform', transform);
+
+  this._transition(svgNodes)
+      .style('opacity', 1)
+      .attr('transform', transform);
+}
+
+function defaultPositionEdgeLabels(g, svgEdgeLabels) {
+  function transform(e) {
+    var value = g.edge(e);
+    var point = findMidPoint(value.points);
+    return 'translate(' + point.x + ',' + point.y + ')';
+  }
+
+  // For entering edge labels, position immediately without transition
+  svgEdgeLabels.filter('.enter').attr('transform', transform);
+
+  this._transition(svgEdgeLabels)
+    .style('opacity', 1)
+    .attr('transform', transform);
+}
+
+function defaultPositionEdgePaths(g, svgEdgePaths) {
+  var interpolate = this._edgeInterpolate,
+      tension = this._edgeTension;
+
+  function calcPoints(e) {
+    var value = g.edge(e);
+    var source = g.node(g.incidentNodes(e)[0]);
+    var target = g.node(g.incidentNodes(e)[1]);
+    var points = value.points.slice();
+
+    var p0 = points.length === 0 ? target : points[0];
+    var p1 = points.length === 0 ? source : points[points.length - 1];
+
+    points.unshift(intersectRect(source, p0));
+    // TODO: use bpodgursky's shortening algorithm here
+    points.push(intersectRect(target, p1));
+
+    return d3.svg.line()
+      .x(function(d) { return d.x; })
+      .y(function(d) { return d.y; })
+      .interpolate(interpolate)
+      .tension(tension)
+      (points);
+  }
+
+  svgEdgePaths.filter('.enter').selectAll('path')
+      .attr('d', calcPoints);
+
+  this._transition(svgEdgePaths.selectAll('path'))
+      .attr('d', calcPoints)
+      .style('opacity', 1);
+}
+
+// By default we do not use transitions
+function defaultTransition(selection) {
+  return selection;
+}
+
+function defaultPostLayout() {
+  // Do nothing
+}
+
+function defaultPostRender(graph, root) {
+  if (graph.isDirected() && root.select('#arrowhead').empty()) {
+    root
+      .append('svg:defs')
+        .append('svg:marker')
+          .attr('id', 'arrowhead')
+          .attr('viewBox', '0 0 10 10')
+          .attr('refX', 8)
+          .attr('refY', 5)
+          .attr('markerUnits', 'strokewidth')
+          .attr('markerWidth', 8)
+          .attr('markerHeight', 5)
+          .attr('orient', 'auto')
+          .attr('style', 'fill: #333')
+          .append('svg:path')
+            .attr('d', 'M 0 0 L 10 5 L 0 10 z');
+  }
+}
+
+function addLabel(node, root, marginX, marginY) {
+  // Add the rect first so that it appears behind the label
+  var label = node.label;
+  var rect = root.append('rect');
+  var labelSvg = root.append('g');
+
+  if (label[0] === '<') {
+    addForeignObjectLabel(label, labelSvg);
+    // No margin for HTML elements
+    marginX = marginY = 0;
+  } else {
+    addTextLabel(label,
+                 labelSvg,
+                 Math.floor(node.labelCols),
+                 node.labelCut);
+  }
+
+  var bbox = root.node().getBBox();
+
+  labelSvg.attr('transform',
+             'translate(' + (-bbox.width / 2) + ',' + (-bbox.height / 2) + ')');
+
+  rect
+    .attr('rx', 5)
+    .attr('ry', 5)
+    .attr('x', -(bbox.width / 2 + marginX))
+    .attr('y', -(bbox.height / 2 + marginY))
+    .attr('width', bbox.width + 2 * marginX)
+    .attr('height', bbox.height + 2 * marginY);
+}
+
+function addForeignObjectLabel(label, root) {
+  var fo = root
+    .append('foreignObject')
+      .attr('width', '100000');
+
+  var w, h;
+  fo
+    .append('xhtml:div')
+      .style('float', 'left')
+      // TODO find a better way to get dimensions for foreignObjects...
+      .html(function() { return label; })
+      .each(function() {
+        w = this.clientWidth;
+        h = this.clientHeight;
+      });
+
+  fo
+    .attr('width', w)
+    .attr('height', h);
+}
+
+function addTextLabel(label, root, labelCols, labelCut) {
+  if (labelCut === undefined) labelCut = "false";
+  labelCut = (labelCut.toString().toLowerCase() === "true");
+
+  var node = root
+    .append('text')
+    .attr('text-anchor', 'left');
+
+  label = label.replace(/\\n/g, "\n");
+
+  var arr = labelCols ? wordwrap(label, labelCols, labelCut) : label;
+  arr = arr.split("\n");
+  for (var i = 0; i < arr.length; i++) {
+    node
+      .append('tspan')
+        .attr('dy', '1em')
+        .attr('x', '1')
+        .text(arr[i]);
+  }
+}
+
+// Thanks to
+// http://james.padolsey.com/javascript/wordwrap-for-javascript/
+function wordwrap (str, width, cut, brk) {
+     brk = brk || '\n';
+     width = width || 75;
+     cut = cut || false;
+
+     if (!str) { return str; }
+
+     var regex = '.{1,' +width+ '}(\\s|$)' + (cut ? '|.{' +width+ '}|.+$' : '|\\S+?(\\s|$)');
+
+     return str.match( RegExp(regex, 'g') ).join( brk );
+}
+
+function findMidPoint(points) {
+  var midIdx = points.length / 2;
+  if (points.length % 2) {
+    return points[Math.floor(midIdx)];
+  } else {
+    var p0 = points[midIdx - 1];
+    var p1 = points[midIdx];
+    return {x: (p0.x + p1.x) / 2, y: (p0.y + p1.y) / 2};
+  }
+}
+
+function intersectRect(rect, point) {
+  var x = rect.x;
+  var y = rect.y;
+
+  // For now we only support rectangles
+
+  // Rectangle intersection algorithm from:
+  // http://math.stackexchange.com/questions/108113/find-edge-between-two-boxes
+  var dx = point.x - x;
+  var dy = point.y - y;
+  var w = rect.width / 2;
+  var h = rect.height / 2;
+
+  var sx, sy;
+  if (Math.abs(dy) * w > Math.abs(dx) * h) {
+    // Intersection is top or bottom of rect.
+    if (dy < 0) {
+      h = -h;
+    }
+    sx = dy === 0 ? 0 : h * dx / dy;
+    sy = h;
+  } else {
+    // Intersection is left or right of rect.
+    if (dx < 0) {
+      w = -w;
+    }
+    sx = w;
+    sy = dx === 0 ? 0 : w * dy / dx;
+  }
+
+  return {x: x + sx, y: y + sy};
+}
+
+function isComposite(g, u) {
+  return 'children' in g && g.children(u).length;
+}
+
+function bind(func, thisArg) {
+  // For some reason PhantomJS occassionally fails when using the builtin bind,
+  // so we check if it is available and if not, use a degenerate polyfill.
+  if (func.bind) {
+    return func.bind(thisArg);
+  }
+
+  return function() {
+    return func.apply(thisArg, arguments);
+  };
+}
+
+},{"d3":10,"dagre":11}],4:[function(require,module,exports){
+module.exports = '0.1.5';
+
+},{}],5:[function(require,module,exports){
+exports.Set = require('./lib/Set');
+exports.PriorityQueue = require('./lib/PriorityQueue');
+exports.version = require('./lib/version');
+
+},{"./lib/PriorityQueue":6,"./lib/Set":7,"./lib/version":9}],6:[function(require,module,exports){
+module.exports = PriorityQueue;
+
+/**
+ * A min-priority queue data structure. This algorithm is derived from Cormen,
+ * et al., "Introduction to Algorithms". The basic idea of a min-priority
+ * queue is that you can efficiently (in O(1) time) get the smallest key in
+ * the queue. Adding and removing elements takes O(log n) time. A key can
+ * have its priority decreased in O(log n) time.
+ */
+function PriorityQueue() {
+  this._arr = [];
+  this._keyIndices = {};
+}
+
+/**
+ * Returns the number of elements in the queue. Takes `O(1)` time.
+ */
+PriorityQueue.prototype.size = function() {
+  return this._arr.length;
+};
+
+/**
+ * Returns the keys that are in the queue. Takes `O(n)` time.
+ */
+PriorityQueue.prototype.keys = function() {
+  return this._arr.map(function(x) { return x.key; });
+};
+
+/**
+ * Returns `true` if **key** is in the queue and `false` if not.
+ */
+PriorityQueue.prototype.has = function(key) {
+  return key in this._keyIndices;
+};
+
+/**
+ * Returns the priority for **key**. If **key** is not present in the queue
+ * then this function returns `undefined`. Takes `O(1)` time.
+ *
+ * @param {Object} key
+ */
+PriorityQueue.prototype.priority = function(key) {
+  var index = this._keyIndices[key];
+  if (index !== undefined) {
+    return this._arr[index].priority;
+  }
+};
+
+/**
+ * Returns the key for the minimum element in this queue. If the queue is
+ * empty this function throws an Error. Takes `O(1)` time.
+ */
+PriorityQueue.prototype.min = function() {
+  if (this.size() === 0) {
+    throw new Error("Queue underflow");
+  }
+  return this._arr[0].key;
+};
+
+/**
+ * Inserts a new key into the priority queue. If the key already exists in
+ * the queue this function returns `false`; otherwise it will return `true`.
+ * Takes `O(n)` time.
+ *
+ * @param {Object} key the key to add
+ * @param {Number} priority the initial priority for the key
+ */
+PriorityQueue.prototype.add = function(key, priority) {
+  var keyIndices = this._keyIndices;
+  if (!(key in keyIndices)) {
+    var arr = this._arr;
+    var index = arr.length;
+    keyIndices[key] = index;
+    arr.push({key: key, priority: priority});
+    this._decrease(index);
+    return true;
+  }
+  return false;
+};
+
+/**
+ * Removes and returns the smallest key in the queue. Takes `O(log n)` time.
+ */
+PriorityQueue.prototype.removeMin = function() {
+  this._swap(0, this._arr.length - 1);
+  var min = this._arr.pop();
+  delete this._keyIndices[min.key];
+  this._heapify(0);
+  return min.key;
+};
+
+/**
+ * Decreases the priority for **key** to **priority**. If the new priority is
+ * greater than the previous priority, this function will throw an Error.
+ *
+ * @param {Object} key the key for which to raise priority
+ * @param {Number} priority the new priority for the key
+ */
+PriorityQueue.prototype.decrease = function(key, priority) {
+  var index = this._keyIndices[key];
+  if (priority > this._arr[index].priority) {
+    throw new Error("New priority is greater than current priority. " +
+        "Key: " + key + " Old: " + this._arr[index].priority + " New: " + priority);
+  }
+  this._arr[index].priority = priority;
+  this._decrease(index);
+};
+
+PriorityQueue.prototype._heapify = function(i) {
+  var arr = this._arr;
+  var l = 2 * i,
+      r = l + 1,
+      largest = i;
+  if (l < arr.length) {
+    largest = arr[l].priority < arr[largest].priority ? l : largest;
+    if (r < arr.length) {
+      largest = arr[r].priority < arr[largest].priority ? r : largest;
+    }
+    if (largest !== i) {
+      this._swap(i, largest);
+      this._heapify(largest);
+    }
+  }
+};
+
+PriorityQueue.prototype._decrease = function(index) {
+  var arr = this._arr;
+  var priority = arr[index].priority;
+  var parent;
+  while (index !== 0) {
+    parent = index >> 1;
+    if (arr[parent].priority < priority) {
+      break;
+    }
+    this._swap(index, parent);
+    index = parent;
+  }
+};
+
+PriorityQueue.prototype._swap = function(i, j) {
+  var arr = this._arr;
+  var keyIndices = this._keyIndices;
+  var origArrI = arr[i];
+  var origArrJ = arr[j];
+  arr[i] = origArrJ;
+  arr[j] = origArrI;
+  keyIndices[origArrJ.key] = i;
+  keyIndices[origArrI.key] = j;
+};
+
+},{}],7:[function(require,module,exports){
+var util = require('./util');
+
+module.exports = Set;
+
+/**
+ * Constructs a new Set with an optional set of `initialKeys`.
+ *
+ * It is important to note that keys are coerced to String for most purposes
+ * with this object, similar to the behavior of JavaScript's Object. For
+ * example, the following will add only one key:
+ *
+ *     var s = new Set();
+ *     s.add(1);
+ *     s.add("1");
+ *
+ * However, the type of the key is preserved internally so that `keys` returns
+ * the original key set uncoerced. For the above example, `keys` would return
+ * `[1]`.
+ */
+function Set(initialKeys) {
+  this._size = 0;
+  this._keys = {};
+
+  if (initialKeys) {
+    for (var i = 0, il = initialKeys.length; i < il; ++i) {
+      this.add(initialKeys[i]);
+    }
+  }
+}
+
+/**
+ * Returns a new Set that represents the set intersection of the array of given
+ * sets.
+ */
+Set.intersect = function(sets) {
+  if (sets.length === 0) {
+    return new Set();
+  }
+
+  var result = new Set(!util.isArray(sets[0]) ? sets[0].keys() : sets[0]);
+  for (var i = 1, il = sets.length; i < il; ++i) {
+    var resultKeys = result.keys(),
+        other = !util.isArray(sets[i]) ? sets[i] : new Set(sets[i]);
+    for (var j = 0, jl = resultKeys.length; j < jl; ++j) {
+      var key = resultKeys[j];
+      if (!other.has(key)) {
+        result.remove(key);
+      }
+    }
+  }
+
+  return result;
+};
+
+/**
+ * Returns a new Set that represents the set union of the array of given sets.
+ */
+Set.union = function(sets) {
+  var totalElems = util.reduce(sets, function(lhs, rhs) {
+    return lhs + (rhs.size ? rhs.size() : rhs.length);
+  }, 0);
+  var arr = new Array(totalElems);
+
+  var k = 0;
+  for (var i = 0, il = sets.length; i < il; ++i) {
+    var cur = sets[i],
+        keys = !util.isArray(cur) ? cur.keys() : cur;
+    for (var j = 0, jl = keys.length; j < jl; ++j) {
+      arr[k++] = keys[j];
+    }
+  }
+
+  return new Set(arr);
+};
+
+/**
+ * Returns the size of this set in `O(1)` time.
+ */
+Set.prototype.size = function() {
+  return this._size;
+};
+
+/**
+ * Returns the keys in this set. Takes `O(n)` time.
+ */
+Set.prototype.keys = function() {
+  return values(this._keys);
+};
+
+/**
+ * Tests if a key is present in this Set. Returns `true` if it is and `false`
+ * if not. Takes `O(1)` time.
+ */
+Set.prototype.has = function(key) {
+  return key in this._keys;
+};
+
+/**
+ * Adds a new key to this Set if it is not already present. Returns `true` if
+ * the key was added and `false` if it was already present. Takes `O(1)` time.
+ */
+Set.prototype.add = function(key) {
+  if (!(key in this._keys)) {
+    this._keys[key] = key;
+    ++this._size;
+    return true;
+  }
+  return false;
+};
+
+/**
+ * Removes a key from this Set. If the key was removed this function returns
+ * `true`. If not, it returns `false`. Takes `O(1)` time.
+ */
+Set.prototype.remove = function(key) {
+  if (key in this._keys) {
+    delete this._keys[key];
+    --this._size;
+    return true;
+  }
+  return false;
+};
+
+/*
+ * Returns an array of all values for properties of **o**.
+ */
+function values(o) {
+  var ks = Object.keys(o),
+      len = ks.length,
+      result = new Array(len),
+      i;
+  for (i = 0; i < len; ++i) {
+    result[i] = o[ks[i]];
+  }
+  return result;
+}
+
+},{"./util":8}],8:[function(require,module,exports){
+/*
+ * This polyfill comes from
+ * https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/isArray
+ */
+if(!Array.isArray) {
+  exports.isArray = function (vArg) {
+    return Object.prototype.toString.call(vArg) === '[object Array]';
+  };
+} else {
+  exports.isArray = Array.isArray;
+}
+
+/*
+ * Slightly adapted polyfill from
+ * https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/Reduce
+ */
+if ('function' !== typeof Array.prototype.reduce) {
+  exports.reduce = function(array, callback, opt_initialValue) {
+    'use strict';
+    if (null === array || 'undefined' === typeof array) {
+      // At the moment all modern browsers, that support strict mode, have
+      // native implementation of Array.prototype.reduce. For instance, IE8
+      // does not support strict mode, so this check is actually useless.
+      throw new TypeError(
+          'Array.prototype.reduce called on null or undefined');
+    }
+    if ('function' !== typeof callback) {
+      throw new TypeError(callback + ' is not a function');
+    }
+    var index, value,
+        length = array.length >>> 0,
+        isValueSet = false;
+    if (1 < arguments.length) {
+      value = opt_initialValue;
+      isValueSet = true;
+    }
+    for (index = 0; length > index; ++index) {
+      if (array.hasOwnProperty(index)) {
+        if (isValueSet) {
+          value = callback(value, array[index], index, array);
+        }
+        else {
+          value = array[index];
+          isValueSet = true;
+        }
+      }
+    }
+    if (!isValueSet) {
+      throw new TypeError('Reduce of empty array with no initial value');
+    }
+    return value;
+  };
+} else {
+  exports.reduce = function(array, callback, opt_initialValue) {
+    return array.reduce(callback, opt_initialValue);
+  };
+}
+
+},{}],9:[function(require,module,exports){
+module.exports = '1.1.3';
+
+},{}],10:[function(require,module,exports){
+require("./d3");
+module.exports = d3;
+(function () { delete this.d3; })(); // unset global
+
+},{}],11:[function(require,module,exports){
+/*
+Copyright (c) 2012-2013 Chris Pettitt
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+*/
+exports.Digraph = require("graphlib").Digraph;
+exports.Graph = require("graphlib").Graph;
+exports.layout = require("./lib/layout");
+exports.version = require("./lib/version");
+
+},{"./lib/layout":12,"./lib/version":27,"graphlib":28}],12:[function(require,module,exports){
+var util = require('./util'),
+    rank = require('./rank'),
+    order = require('./order'),
+    CGraph = require('graphlib').CGraph,
+    CDigraph = require('graphlib').CDigraph;
+
+module.exports = function() {
+  // External configuration
+  var config = {
+    // How much debug information to include?
+    debugLevel: 0,
+    // Max number of sweeps to perform in order phase
+    orderMaxSweeps: order.DEFAULT_MAX_SWEEPS,
+    // Use network simplex algorithm in ranking
+    rankSimplex: false,
+    // Rank direction. Valid values are (TB, LR)
+    rankDir: 'TB'
+  };
+
+  // Phase functions
+  var position = require('./position')();
+
+  // This layout object
+  var self = {};
+
+  self.orderIters = util.propertyAccessor(self, config, 'orderMaxSweeps');
+
+  self.rankSimplex = util.propertyAccessor(self, config, 'rankSimplex');
+
+  self.nodeSep = delegateProperty(position.nodeSep);
+  self.edgeSep = delegateProperty(position.edgeSep);
+  self.universalSep = delegateProperty(position.universalSep);
+  self.rankSep = delegateProperty(position.rankSep);
+  self.rankDir = util.propertyAccessor(self, config, 'rankDir');
+  self.debugAlignment = delegateProperty(position.debugAlignment);
+
+  self.debugLevel = util.propertyAccessor(self, config, 'debugLevel', function(x) {
+    util.log.level = x;
+    position.debugLevel(x);
+  });
+
+  self.run = util.time('Total layout', run);
+
+  self._normalize = normalize;
+
+  return self;
+
+  /*
+   * Constructs an adjacency graph using the nodes and edges specified through
+   * config. For each node and edge we add a property `dagre` that contains an
+   * object that will hold intermediate and final layout information. Some of
+   * the contents include:
+   *
+   *  1) A generated ID that uniquely identifies the object.
+   *  2) Dimension information for nodes (copied from the source node).
+   *  3) Optional dimension information for edges.
+   *
+   * After the adjacency graph is constructed the code no longer needs to use
+   * the original nodes and edges passed in via config.
+   */
+  function initLayoutGraph(inputGraph) {
+    var g = new CDigraph();
+
+    inputGraph.eachNode(function(u, value) {
+      if (value === undefined) value = {};
+      g.addNode(u, {
+        width: value.width,
+        height: value.height
+      });
+      if (value.hasOwnProperty('rank')) {
+        g.node(u).prefRank = value.rank;
+      }
+    });
+
+    // Set up subgraphs
+    if (inputGraph.parent) {
+      inputGraph.nodes().forEach(function(u) {
+        g.parent(u, inputGraph.parent(u));
+      });
+    }
+
+    inputGraph.eachEdge(function(e, u, v, value) {
+      if (value === undefined) value = {};
+      var newValue = {
+        e: e,
+        minLen: value.minLen || 1,
+        width: value.width || 0,
+        height: value.height || 0,
+        points: []
+      };
+
+      g.addEdge(null, u, v, newValue);
+    });
+
+    // Initial graph attributes
+    var graphValue = inputGraph.graph() || {};
+    g.graph({
+      rankDir: graphValue.rankDir || config.rankDir,
+      orderRestarts: graphValue.orderRestarts
+    });
+
+    return g;
+  }
+
+  function run(inputGraph) {
+    var rankSep = self.rankSep();
+    var g;
+    try {
+      // Build internal graph
+      g = util.time('initLayoutGraph', initLayoutGraph)(inputGraph);
+
+      if (g.order() === 0) {
+        return g;
+      }
+
+      // Make space for edge labels
+      g.eachEdge(function(e, s, t, a) {
+        a.minLen *= 2;
+      });
+      self.rankSep(rankSep / 2);
+
+      // Determine the rank for each node. Nodes with a lower rank will appear
+      // above nodes of higher rank.
+      util.time('rank.run', rank.run)(g, config.rankSimplex);
+
+      // Normalize the graph by ensuring that every edge is proper (each edge has
+      // a length of 1). We achieve this by adding dummy nodes to long edges,
+      // thus shortening them.
+      util.time('normalize', normalize)(g);
+
+      // Order the nodes so that edge crossings are minimized.
+      util.time('order', order)(g, config.orderMaxSweeps);
+
+      // Find the x and y coordinates for every node in the graph.
+      util.time('position', position.run)(g);
+
+      // De-normalize the graph by removing dummy nodes and augmenting the
+      // original long edges with coordinate information.
+      util.time('undoNormalize', undoNormalize)(g);
+
+      // Reverses points for edges that are in a reversed state.
+      util.time('fixupEdgePoints', fixupEdgePoints)(g);
+
+      // Restore delete edges and reverse edges that were reversed in the rank
+      // phase.
+      util.time('rank.restoreEdges', rank.restoreEdges)(g);
+
+      // Construct final result graph and return it
+      return util.time('createFinalGraph', createFinalGraph)(g, inputGraph.isDirected());
+    } finally {
+      self.rankSep(rankSep);
+    }
+  }
+
+  /*
+   * This function is responsible for 'normalizing' the graph. The process of
+   * normalization ensures that no edge in the graph has spans more than one
+   * rank. To do this it inserts dummy nodes as needed and links them by adding
+   * dummy edges. This function keeps enough information in the dummy nodes and
+   * edges to ensure that the original graph can be reconstructed later.
+   *
+   * This method assumes that the input graph is cycle free.
+   */
+  function normalize(g) {
+    var dummyCount = 0;
+    g.eachEdge(function(e, s, t, a) {
+      var sourceRank = g.node(s).rank;
+      var targetRank = g.node(t).rank;
+      if (sourceRank + 1 < targetRank) {
+        for (var u = s, rank = sourceRank + 1, i = 0; rank < targetRank; ++rank, ++i) {
+          var v = '_D' + (++dummyCount);
+          var node = {
+            width: a.width,
+            height: a.height,
+            edge: { id: e, source: s, target: t, attrs: a },
+            rank: rank,
+            dummy: true
+          };
+
+          // If this node represents a bend then we will use it as a control
+          // point. For edges with 2 segments this will be the center dummy
+          // node. For edges with more than two segments, this will be the
+          // first and last dummy node.
+          if (i === 0) node.index = 0;
+          else if (rank + 1 === targetRank) node.index = 1;
+
+          g.addNode(v, node);
+          g.addEdge(null, u, v, {});
+          u = v;
+        }
+        g.addEdge(null, u, t, {});
+        g.delEdge(e);
+      }
+    });
+  }
+
+  /*
+   * Reconstructs the graph as it was before normalization. The positions of
+   * dummy nodes are used to build an array of points for the original 'long'
+   * edge. Dummy nodes and edges are removed.
+   */
+  function undoNormalize(g) {
+    g.eachNode(function(u, a) {
+      if (a.dummy) {
+        if ('index' in a) {
+          var edge = a.edge;
+          if (!g.hasEdge(edge.id)) {
+            g.addEdge(edge.id, edge.source, edge.target, edge.attrs);
+          }
+          var points = g.edge(edge.id).points;
+          points[a.index] = { x: a.x, y: a.y, ul: a.ul, ur: a.ur, dl: a.dl, dr: a.dr };
+        }
+        g.delNode(u);
+      }
+    });
+  }
+
+  /*
+   * For each edge that was reversed during the `acyclic` step, reverse its
+   * array of points.
+   */
+  function fixupEdgePoints(g) {
+    g.eachEdge(function(e, s, t, a) { if (a.reversed) a.points.reverse(); });
+  }
+
+  function createFinalGraph(g, isDirected) {
+    var out = isDirected ? new CDigraph() : new CGraph();
+    out.graph(g.graph());
+    g.eachNode(function(u, value) { out.addNode(u, value); });
+    g.eachNode(function(u) { out.parent(u, g.parent(u)); });
+    g.eachEdge(function(e, u, v, value) {
+      out.addEdge(value.e, u, v, value);
+    });
+
+    // Attach bounding box information
+    var maxX = 0, maxY = 0;
+    g.eachNode(function(u, value) {
+      if (!g.children(u).length) {
+        maxX = Math.max(maxX, value.x + value.width / 2);
+        maxY = Math.max(maxY, value.y + value.height / 2);
+      }
+    });
+    g.eachEdge(function(e, u, v, value) {
+      var maxXPoints = Math.max.apply(Math, value.points.map(function(p) { return p.x; }));
+      var maxYPoints = Math.max.apply(Math, value.points.map(function(p) { return p.y; }));
+      maxX = Math.max(maxX, maxXPoints + value.width / 2);
+      maxY = Math.max(maxY, maxYPoints + value.height / 2);
+    });
+    out.graph().width = maxX;
+    out.graph().height = maxY;
+
+    return out;
+  }
+
+  /*
+   * Given a function, a new function is returned that invokes the given
+   * function. The return value from the function is always the `self` object.
+   */
+  function delegateProperty(f) {
+    return function() {
+      if (!arguments.length) return f();
+      f.apply(null, arguments);
+      return self;
+    };
+  }
+};
+
+
+},{"./order":13,"./position":18,"./rank":19,"./util":26,"graphlib":28}],13:[function(require,module,exports){
+var util = require('./util'),
+    crossCount = require('./order/crossCount'),
+    initLayerGraphs = require('./order/initLayerGraphs'),
+    initOrder = require('./order/initOrder'),
+    sortLayer = require('./order/sortLayer');
+
+module.exports = order;
+
+// The maximum number of sweeps to perform before finishing the order phase.
+var DEFAULT_MAX_SWEEPS = 24;
+order.DEFAULT_MAX_SWEEPS = DEFAULT_MAX_SWEEPS;
+
+/*
+ * Runs the order phase with the specified `graph, `maxSweeps`, and
+ * `debugLevel`. If `maxSweeps` is not specified we use `DEFAULT_MAX_SWEEPS`.
+ * If `debugLevel` is not set we assume 0.
+ */
+function order(g, maxSweeps) {
+  if (arguments.length < 2) {
+    maxSweeps = DEFAULT_MAX_SWEEPS;
+  }
+
+  var restarts = g.graph().orderRestarts || 0;
+
+  var layerGraphs = initLayerGraphs(g);
+  // TODO: remove this when we add back support for ordering clusters
+  layerGraphs.forEach(function(lg) {
+    lg = lg.filterNodes(function(u) { return !g.children(u).length; });
+  });
+
+  var iters = 0,
+      currentBestCC,
+      allTimeBestCC = Number.MAX_VALUE,
+      allTimeBest = {};
+
+  function saveAllTimeBest() {
+    g.eachNode(function(u, value) { allTimeBest[u] = value.order; });
+  }
+
+  for (var j = 0; j < Number(restarts) + 1 && allTimeBestCC !== 0; ++j) {
+    currentBestCC = Number.MAX_VALUE;
+    initOrder(g, restarts > 0);
+
+    util.log(2, 'Order phase start cross count: ' + g.graph().orderInitCC);
+
+    var i, lastBest, cc;
+    for (i = 0, lastBest = 0; lastBest < 4 && i < maxSweeps && currentBestCC > 0; ++i, ++lastBest, ++iters) {
+      sweep(g, layerGraphs, i);
+      cc = crossCount(g);
+      if (cc < currentBestCC) {
+        lastBest = 0;
+        currentBestCC = cc;
+        if (cc < allTimeBestCC) {
+          saveAllTimeBest();
+          allTimeBestCC = cc;
+        }
+      }
+      util.log(3, 'Order phase start ' + j + ' iter ' + i + ' cross count: ' + cc);
+    }
+  }
+
+  Object.keys(allTimeBest).forEach(function(u) {
+    if (!g.children || !g.children(u).length) {
+      g.node(u).order = allTimeBest[u];
+    }
+  });
+  g.graph().orderCC = allTimeBestCC;
+
+  util.log(2, 'Order iterations: ' + iters);
+  util.log(2, 'Order phase best cross count: ' + g.graph().orderCC);
+}
+
+function predecessorWeights(g, nodes) {
+  var weights = {};
+  nodes.forEach(function(u) {
+    weights[u] = g.inEdges(u).map(function(e) {
+      return g.node(g.source(e)).order;
+    });
+  });
+  return weights;
+}
+
+function successorWeights(g, nodes) {
+  var weights = {};
+  nodes.forEach(function(u) {
+    weights[u] = g.outEdges(u).map(function(e) {
+      return g.node(g.target(e)).order;
+    });
+  });
+  return weights;
+}
+
+function sweep(g, layerGraphs, iter) {
+  if (iter % 2 === 0) {
+    sweepDown(g, layerGraphs, iter);
+  } else {
+    sweepUp(g, layerGraphs, iter);
+  }
+}
+
+function sweepDown(g, layerGraphs) {
+  var cg;
+  for (i = 1; i < layerGraphs.length; ++i) {
+    cg = sortLayer(layerGraphs[i], cg, predecessorWeights(g, layerGraphs[i].nodes()));
+  }
+}
+
+function sweepUp(g, layerGraphs) {
+  var cg;
+  for (i = layerGraphs.length - 2; i >= 0; --i) {
+    sortLayer(layerGraphs[i], cg, successorWeights(g, layerGraphs[i].nodes()));
+  }
+}
+
+},{"./order/crossCount":14,"./order/initLayerGraphs":15,"./order/initOrder":16,"./order/sortLayer":17,"./util":26}],14:[function(require,module,exports){
+var util = require('../util');
+
+module.exports = crossCount;
+
+/*
+ * Returns the cross count for the given graph.
+ */
+function crossCount(g) {
+  var cc = 0;
+  var ordering = util.ordering(g);
+  for (var i = 1; i < ordering.length; ++i) {
+    cc += twoLayerCrossCount(g, ordering[i-1], ordering[i]);
+  }
+  return cc;
+}
+
+/*
+ * This function searches through a ranked and ordered graph and counts the
+ * number of edges that cross. This algorithm is derived from:
+ *
+ *    W. Barth et al., Bilayer Cross Counting, JGAA, 8(2) 179–194 (2004)
+ */
+function twoLayerCrossCount(g, layer1, layer2) {
+  var indices = [];
+  layer1.forEach(function(u) {
+    var nodeIndices = [];
+    g.outEdges(u).forEach(function(e) { nodeIndices.push(g.node(g.target(e)).order); });
+    nodeIndices.sort(function(x, y) { return x - y; });
+    indices = indices.concat(nodeIndices);
+  });
+
+  var firstIndex = 1;
+  while (firstIndex < layer2.length) firstIndex <<= 1;
+
+  var treeSize = 2 * firstIndex - 1;
+  firstIndex -= 1;
+
+  var tree = [];
+  for (var i = 0; i < treeSize; ++i) { tree[i] = 0; }
+
+  var cc = 0;
+  indices.forEach(function(i) {
+    var treeIndex = i + firstIndex;
+    ++tree[treeIndex];
+    while (treeIndex > 0) {
+      if (treeIndex % 2) {
+        cc += tree[treeIndex + 1];
+      }
+      treeIndex = (treeIndex - 1) >> 1;
+      ++tree[treeIndex];
+    }
+  });
+
+  return cc;
+}
+
+},{"../util":26}],15:[function(require,module,exports){
+var nodesFromList = require('graphlib').filter.nodesFromList,
+    /* jshint -W079 */
+    Set = require('cp-data').Set;
+
+module.exports = initLayerGraphs;
+
+/*
+ * This function takes a compound layered graph, g, and produces an array of
+ * layer graphs. Each entry in the array represents a subgraph of nodes
+ * relevant for performing crossing reduction on that layer.
+ */
+function initLayerGraphs(g) {
+  var ranks = [];
+
+  function dfs(u) {
+    if (u === null) {
+      g.children(u).forEach(function(v) { dfs(v); });
+      return;
+    }
+
+    var value = g.node(u);
+    value.minRank = ('rank' in value) ? value.rank : Number.MAX_VALUE;
+    value.maxRank = ('rank' in value) ? value.rank : Number.MIN_VALUE;
+    var uRanks = new Set();
+    g.children(u).forEach(function(v) {
+      var rs = dfs(v);
+      uRanks = Set.union([uRanks, rs]);
+      value.minRank = Math.min(value.minRank, g.node(v).minRank);
+      value.maxRank = Math.max(value.maxRank, g.node(v).maxRank);
+    });
+
+    if ('rank' in value) uRanks.add(value.rank);
+
+    uRanks.keys().forEach(function(r) {
+      if (!(r in ranks)) ranks[r] = [];
+      ranks[r].push(u);
+    });
+
+    return uRanks;
+  }
+  dfs(null);
+
+  var layerGraphs = [];
+  ranks.forEach(function(us, rank) {
+    layerGraphs[rank] = g.filterNodes(nodesFromList(us));
+  });
+
+  return layerGraphs;
+}
+
+},{"cp-data":5,"graphlib":28}],16:[function(require,module,exports){
+var crossCount = require('./crossCount'),
+    util = require('../util');
+
+module.exports = initOrder;
+
+/*
+ * Given a graph with a set of layered nodes (i.e. nodes that have a `rank`
+ * attribute) this function attaches an `order` attribute that uniquely
+ * arranges each node of each rank. If no constraint graph is provided the
+ * order of the nodes in each rank is entirely arbitrary.
+ */
+function initOrder(g, random) {
+  var layers = [];
+
+  g.eachNode(function(u, value) {
+    var layer = layers[value.rank];
+    if (g.children && g.children(u).length > 0) return;
+    if (!layer) {
+      layer = layers[value.rank] = [];
+    }
+    layer.push(u);
+  });
+
+  layers.forEach(function(layer) {
+    if (random) {
+      util.shuffle(layer);
+    }
+    layer.forEach(function(u, i) {
+      g.node(u).order = i;
+    });
+  });
+
+  var cc = crossCount(g);
+  g.graph().orderInitCC = cc;
+  g.graph().orderCC = Number.MAX_VALUE;
+}
+
+},{"../util":26,"./crossCount":14}],17:[function(require,module,exports){
+var util = require('../util');
+/*
+    Digraph = require('graphlib').Digraph,
+    topsort = require('graphlib').alg.topsort,
+    nodesFromList = require('graphlib').filter.nodesFromList;
+*/
+
+module.exports = sortLayer;
+
+/*
+function sortLayer(g, cg, weights) {
+  var result = sortLayerSubgraph(g, null, cg, weights);
+  result.list.forEach(function(u, i) {
+    g.node(u).order = i;
+  });
+  return result.constraintGraph;
+}
+*/
+
+function sortLayer(g, cg, weights) {
+  var ordering = [];
+  var bs = {};
+  g.eachNode(function(u, value) {
+    ordering[value.order] = u;
+    var ws = weights[u];
+    if (ws.length) {
+      bs[u] = util.sum(ws) / ws.length;
+    }
+  });
+
+  var toSort = g.nodes().filter(function(u) { return bs[u] !== undefined; });
+  toSort.sort(function(x, y) {
+    return bs[x] - bs[y] || g.node(x).order - g.node(y).order;
+  });
+
+  for (var i = 0, j = 0, jl = toSort.length; j < jl; ++i) {
+    if (bs[ordering[i]] !== undefined) {
+      g.node(toSort[j++]).order = i;
+    }
+  }
+}
+
+// TOOD: re-enable constrained sorting once we have a strategy for handling
+// undefined barycenters.
+/*
+function sortLayerSubgraph(g, sg, cg, weights) {
+  cg = cg ? cg.filterNodes(nodesFromList(g.children(sg))) : new Digraph();
+
+  var nodeData = {};
+  g.children(sg).forEach(function(u) {
+    if (g.children(u).length) {
+      nodeData[u] = sortLayerSubgraph(g, u, cg, weights);
+      nodeData[u].firstSG = u;
+      nodeData[u].lastSG = u;
+    } else {
+      var ws = weights[u];
+      nodeData[u] = {
+        degree: ws.length,
+        barycenter: ws.length > 0 ? util.sum(ws) / ws.length : 0,
+        list: [u]
+      };
+    }
+  });
+
+  resolveViolatedConstraints(g, cg, nodeData);
+
+  var keys = Object.keys(nodeData);
+  keys.sort(function(x, y) {
+    return nodeData[x].barycenter - nodeData[y].barycenter;
+  });
+
+  var result =  keys.map(function(u) { return nodeData[u]; })
+                    .reduce(function(lhs, rhs) { return mergeNodeData(g, lhs, rhs); });
+  return result;
+}
+
+/*
+function mergeNodeData(g, lhs, rhs) {
+  var cg = mergeDigraphs(lhs.constraintGraph, rhs.constraintGraph);
+
+  if (lhs.lastSG !== undefined && rhs.firstSG !== undefined) {
+    if (cg === undefined) {
+      cg = new Digraph();
+    }
+    if (!cg.hasNode(lhs.lastSG)) { cg.addNode(lhs.lastSG); }
+    cg.addNode(rhs.firstSG);
+    cg.addEdge(null, lhs.lastSG, rhs.firstSG);
+  }
+
+  return {
+    degree: lhs.degree + rhs.degree,
+    barycenter: (lhs.barycenter * lhs.degree + rhs.barycenter * rhs.degree) /
+                (lhs.degree + rhs.degree),
+    list: lhs.list.concat(rhs.list),
+    firstSG: lhs.firstSG !== undefined ? lhs.firstSG : rhs.firstSG,
+    lastSG: rhs.lastSG !== undefined ? rhs.lastSG : lhs.lastSG,
+    constraintGraph: cg
+  };
+}
+
+function mergeDigraphs(lhs, rhs) {
+  if (lhs === undefined) return rhs;
+  if (rhs === undefined) return lhs;
+
+  lhs = lhs.copy();
+  rhs.nodes().forEach(function(u) { lhs.addNode(u); });
+  rhs.edges().forEach(function(e, u, v) { lhs.addEdge(null, u, v); });
+  return lhs;
+}
+
+function resolveViolatedConstraints(g, cg, nodeData) {
+  // Removes nodes `u` and `v` from `cg` and makes any edges incident on them
+  // incident on `w` instead.
+  function collapseNodes(u, v, w) {
+    // TODO original paper removes self loops, but it is not obvious when this would happen
+    cg.inEdges(u).forEach(function(e) {
+      cg.delEdge(e);
+      cg.addEdge(null, cg.source(e), w);
+    });
+
+    cg.outEdges(v).forEach(function(e) {
+      cg.delEdge(e);
+      cg.addEdge(null, w, cg.target(e));
+    });
+
+    cg.delNode(u);
+    cg.delNode(v);
+  }
+
+  var violated;
+  while ((violated = findViolatedConstraint(cg, nodeData)) !== undefined) {
+    var source = cg.source(violated),
+        target = cg.target(violated);
+
+    var v;
+    while ((v = cg.addNode(null)) && g.hasNode(v)) {
+      cg.delNode(v);
+    }
+
+    // Collapse barycenter and list
+    nodeData[v] = mergeNodeData(g, nodeData[source], nodeData[target]);
+    delete nodeData[source];
+    delete nodeData[target];
+
+    collapseNodes(source, target, v);
+    if (cg.incidentEdges(v).length === 0) { cg.delNode(v); }
+  }
+}
+
+function findViolatedConstraint(cg, nodeData) {
+  var us = topsort(cg);
+  for (var i = 0; i < us.length; ++i) {
+    var u = us[i];
+    var inEdges = cg.inEdges(u);
+    for (var j = 0; j < inEdges.length; ++j) {
+      var e = inEdges[j];
+      if (nodeData[cg.source(e)].barycenter >= nodeData[u].barycenter) {
+        return e;
+      }
+    }
+  }
+}
+*/
+
+},{"../util":26}],18:[function(require,module,exports){
+var util = require('./util');
+
+/*
+ * The algorithms here are based on Brandes and Köpf, "Fast and Simple
+ * Horizontal Coordinate Assignment".
+ */
+module.exports = function() {
+  // External configuration
+  var config = {
+    nodeSep: 50,
+    edgeSep: 10,
+    universalSep: null,
+    rankSep: 30
+  };
+
+  var self = {};
+
+  self.nodeSep = util.propertyAccessor(self, config, 'nodeSep');
+  self.edgeSep = util.propertyAccessor(self, config, 'edgeSep');
+  // If not null this separation value is used for all nodes and edges
+  // regardless of their widths. `nodeSep` and `edgeSep` are ignored with this
+  // option.
+  self.universalSep = util.propertyAccessor(self, config, 'universalSep');
+  self.rankSep = util.propertyAccessor(self, config, 'rankSep');
+  self.debugLevel = util.propertyAccessor(self, config, 'debugLevel');
+
+  self.run = run;
+
+  return self;
+
+  function run(g) {
+    g = g.filterNodes(util.filterNonSubgraphs(g));
+
+    var layering = util.ordering(g);
+
+    var conflicts = findConflicts(g, layering);
+
+    var xss = {};
+    ['u', 'd'].forEach(function(vertDir) {
+      if (vertDir === 'd') layering.reverse();
+
+      ['l', 'r'].forEach(function(horizDir) {
+        if (horizDir === 'r') reverseInnerOrder(layering);
+
+        var dir = vertDir + horizDir;
+        var align = verticalAlignment(g, layering, conflicts, vertDir === 'u' ? 'predecessors' : 'successors');
+        xss[dir]= horizontalCompaction(g, layering, align.pos, align.root, align.align);
+
+        if (config.debugLevel >= 3)
+          debugPositioning(vertDir + horizDir, g, layering, xss[dir]);
+
+        if (horizDir === 'r') flipHorizontally(xss[dir]);
+
+        if (horizDir === 'r') reverseInnerOrder(layering);
+      });
+
+      if (vertDir === 'd') layering.reverse();
+    });
+
+    balance(g, layering, xss);
+
+    g.eachNode(function(v) {
+      var xs = [];
+      for (var alignment in xss) {
+        var alignmentX = xss[alignment][v];
+        posXDebug(alignment, g, v, alignmentX);
+        xs.push(alignmentX);
+      }
+      xs.sort(function(x, y) { return x - y; });
+      posX(g, v, (xs[1] + xs[2]) / 2);
+    });
+
+    // Align y coordinates with ranks
+    var y = 0, reverseY = g.graph().rankDir === 'BT' || g.graph().rankDir === 'RL';
+    layering.forEach(function(layer) {
+      var maxHeight = util.max(layer.map(function(u) { return height(g, u); }));
+      y += maxHeight / 2;
+      layer.forEach(function(u) {
+        posY(g, u, reverseY ? -y : y);
+      });
+      y += maxHeight / 2 + config.rankSep;
+    });
+
+    // Translate layout so that top left corner of bounding rectangle has
+    // coordinate (0, 0).
+    var minX = util.min(g.nodes().map(function(u) { return posX(g, u) - width(g, u) / 2; }));
+    var minY = util.min(g.nodes().map(function(u) { return posY(g, u) - height(g, u) / 2; }));
+    g.eachNode(function(u) {
+      posX(g, u, posX(g, u) - minX);
+      posY(g, u, posY(g, u) - minY);
+    });
+  }
+
+  /*
+   * Generate an ID that can be used to represent any undirected edge that is
+   * incident on `u` and `v`.
+   */
+  function undirEdgeId(u, v) {
+    return u < v
+      ? u.toString().length + ':' + u + '-' + v
+      : v.toString().length + ':' + v + '-' + u;
+  }
+
+  function findConflicts(g, layering) {
+    var conflicts = {}, // Set of conflicting edge ids
+        pos = {},       // Position of node in its layer
+        prevLayer,
+        currLayer,
+        k0,     // Position of the last inner segment in the previous layer
+        l,      // Current position in the current layer (for iteration up to `l1`)
+        k1;     // Position of the next inner segment in the previous layer or
+                // the position of the last element in the previous layer
+
+    if (layering.length <= 2) return conflicts;
+
+    function updateConflicts(v) {
+      var k = pos[v];
+      if (k < k0 || k > k1) {
+        conflicts[undirEdgeId(currLayer[l], v)] = true;
+      }
+    }
+
+    layering[1].forEach(function(u, i) { pos[u] = i; });
+    for (var i = 1; i < layering.length - 1; ++i) {
+      prevLayer = layering[i];
+      currLayer = layering[i+1];
+      k0 = 0;
+      l = 0;
+
+      // Scan current layer for next node that is incident to an inner segement
+      // between layering[i+1] and layering[i].
+      for (var l1 = 0; l1 < currLayer.length; ++l1) {
+        var u = currLayer[l1]; // Next inner segment in the current layer or
+                               // last node in the current layer
+        pos[u] = l1;
+        k1 = undefined;
+
+        if (g.node(u).dummy) {
+          var uPred = g.predecessors(u)[0];
+          // Note: In the case of self loops and sideways edges it is possible
+          // for a dummy not to have a predecessor.
+          if (uPred !== undefined && g.node(uPred).dummy)
+            k1 = pos[uPred];
+        }
+        if (k1 === undefined && l1 === currLayer.length - 1)
+          k1 = prevLayer.length - 1;
+
+        if (k1 !== undefined) {
+          for (; l <= l1; ++l) {
+            g.predecessors(currLayer[l]).forEach(updateConflicts);
+          }
+          k0 = k1;
+        }
+      }
+    }
+
+    return conflicts;
+  }
+
+  function verticalAlignment(g, layering, conflicts, relationship) {
+    var pos = {},   // Position for a node in its layer
+        root = {},  // Root of the block that the node participates in
+        align = {}; // Points to the next node in the block or, if the last
+                    // element in the block, points to the first block's root
+
+    layering.forEach(function(layer) {
+      layer.forEach(function(u, i) {
+        root[u] = u;
+        align[u] = u;
+        pos[u] = i;
+      });
+    });
+
+    layering.forEach(function(layer) {
+      var prevIdx = -1;
+      layer.forEach(function(v) {
+        var related = g[relationship](v), // Adjacent nodes from the previous layer
+            mid;                          // The mid point in the related array
+
+        if (related.length > 0) {
+          related.sort(function(x, y) { return pos[x] - pos[y]; });
+          mid = (related.length - 1) / 2;
+          related.slice(Math.floor(mid), Math.ceil(mid) + 1).forEach(function(u) {
+            if (align[v] === v) {
+              if (!conflicts[undirEdgeId(u, v)] && prevIdx < pos[u]) {
+                align[u] = v;
+                align[v] = root[v] = root[u];
+                prevIdx = pos[u];
+              }
+            }
+          });
+        }
+      });
+    });
+
+    return { pos: pos, root: root, align: align };
+  }
+
+  // This function deviates from the standard BK algorithm in two ways. First
+  // it takes into account the size of the nodes. Second it includes a fix to
+  // the original algorithm that is described in Carstens, "Node and Label
+  // Placement in a Layered Layout Algorithm".
+  function horizontalCompaction(g, layering, pos, root, align) {
+    var sink = {},       // Mapping of node id -> sink node id for class
+        maybeShift = {}, // Mapping of sink node id -> { class node id, min shift }
+        shift = {},      // Mapping of sink node id -> shift
+        pred = {},       // Mapping of node id -> predecessor node (or null)
+        xs = {};         // Calculated X positions
+
+    layering.forEach(function(layer) {
+      layer.forEach(function(u, i) {
+        sink[u] = u;
+        maybeShift[u] = {};
+        if (i > 0)
+          pred[u] = layer[i - 1];
+      });
+    });
+
+    function updateShift(toShift, neighbor, delta) {
+      if (!(neighbor in maybeShift[toShift])) {
+        maybeShift[toShift][neighbor] = delta;
+      } else {
+        maybeShift[toShift][neighbor] = Math.min(maybeShift[toShift][neighbor], delta);
+      }
+    }
+
+    function placeBlock(v) {
+      if (!(v in xs)) {
+        xs[v] = 0;
+        var w = v;
+        do {
+          if (pos[w] > 0) {
+            var u = root[pred[w]];
+            placeBlock(u);
+            if (sink[v] === v) {
+              sink[v] = sink[u];
+            }
+            var delta = sep(g, pred[w]) + sep(g, w);
+            if (sink[v] !== sink[u]) {
+              updateShift(sink[u], sink[v], xs[v] - xs[u] - delta);
+            } else {
+              xs[v] = Math.max(xs[v], xs[u] + delta);
+            }
+          }
+          w = align[w];
+        } while (w !== v);
+      }
+    }
+
+    // Root coordinates relative to sink
+    util.values(root).forEach(function(v) {
+      placeBlock(v);
+    });
+
+    // Absolute coordinates
+    // There is an assumption here that we've resolved shifts for any classes
+    // that begin at an earlier layer. We guarantee this by visiting layers in
+    // order.
+    layering.forEach(function(layer) {
+      layer.forEach(function(v) {
+        xs[v] = xs[root[v]];
+        if (v === root[v] && v === sink[v]) {
+          var minShift = 0;
+          if (v in maybeShift && Object.keys(maybeShift[v]).length > 0) {
+            minShift = util.min(Object.keys(maybeShift[v])
+                                 .map(function(u) {
+                                      return maybeShift[v][u] + (u in shift ? shift[u] : 0);
+                                      }
+                                 ));
+          }
+          shift[v] = minShift;
+        }
+      });
+    });
+
+    layering.forEach(function(layer) {
+      layer.forEach(function(v) {
+        xs[v] += shift[sink[root[v]]] || 0;
+      });
+    });
+
+    return xs;
+  }
+
+  function findMinCoord(g, layering, xs) {
+    return util.min(layering.map(function(layer) {
+      var u = layer[0];
+      return xs[u];
+    }));
+  }
+
+  function findMaxCoord(g, layering, xs) {
+    return util.max(layering.map(function(layer) {
+      var u = layer[layer.length - 1];
+      return xs[u];
+    }));
+  }
+
+  function balance(g, layering, xss) {
+    var min = {},                            // Min coordinate for the alignment
+        max = {},                            // Max coordinate for the alginment
+        smallestAlignment,
+        shift = {};                          // Amount to shift a given alignment
+
+    function updateAlignment(v) {
+      xss[alignment][v] += shift[alignment];
+    }
+
+    var smallest = Number.POSITIVE_INFINITY;
+    for (var alignment in xss) {
+      var xs = xss[alignment];
+      min[alignment] = findMinCoord(g, layering, xs);
+      max[alignment] = findMaxCoord(g, layering, xs);
+      var w = max[alignment] - min[alignment];
+      if (w < smallest) {
+        smallest = w;
+        smallestAlignment = alignment;
+      }
+    }
+
+    // Determine how much to adjust positioning for each alignment
+    ['u', 'd'].forEach(function(vertDir) {
+      ['l', 'r'].forEach(function(horizDir) {
+        var alignment = vertDir + horizDir;
+        shift[alignment] = horizDir === 'l'
+            ? min[smallestAlignment] - min[alignment]
+            : max[smallestAlignment] - max[alignment];
+      });
+    });
+
+    // Find average of medians for xss array
+    for (alignment in xss) {
+      g.eachNode(updateAlignment);
+    }
+  }
+
+  function flipHorizontally(xs) {
+    for (var u in xs) {
+      xs[u] = -xs[u];
+    }
+  }
+
+  function reverseInnerOrder(layering) {
+    layering.forEach(function(layer) {
+      layer.reverse();
+    });
+  }
+
+  function width(g, u) {
+    switch (g.graph().rankDir) {
+      case 'LR': return g.node(u).height;
+      case 'RL': return g.node(u).height;
+      default:   return g.node(u).width;
+    }
+  }
+
+  function height(g, u) {
+    switch(g.graph().rankDir) {
+      case 'LR': return g.node(u).width;
+      case 'RL': return g.node(u).width;
+      default:   return g.node(u).height;
+    }
+  }
+
+  function sep(g, u) {
+    if (config.universalSep !== null) {
+      return config.universalSep;
+    }
+    var w = width(g, u);
+    var s = g.node(u).dummy ? config.edgeSep : config.nodeSep;
+    return (w + s) / 2;
+  }
+
+  function posX(g, u, x) {
+    if (g.graph().rankDir === 'LR' || g.graph().rankDir === 'RL') {
+      if (arguments.length < 3) {
+        return g.node(u).y;
+      } else {
+        g.node(u).y = x;
+      }
+    } else {
+      if (arguments.length < 3) {
+        return g.node(u).x;
+      } else {
+        g.node(u).x = x;
+      }
+    }
+  }
+
+  function posXDebug(name, g, u, x) {
+    if (g.graph().rankDir === 'LR' || g.graph().rankDir === 'RL') {
+      if (arguments.length < 3) {
+        return g.node(u)[name];
+      } else {
+        g.node(u)[name] = x;
+      }
+    } else {
+      if (arguments.length < 3) {
+        return g.node(u)[name];
+      } else {
+        g.node(u)[name] = x;
+      }
+    }
+  }
+
+  function posY(g, u, y) {
+    if (g.graph().rankDir === 'LR' || g.graph().rankDir === 'RL') {
+      if (arguments.length < 3) {
+        return g.node(u).x;
+      } else {
+        g.node(u).x = y;
+      }
+    } else {
+      if (arguments.length < 3) {
+        return g.node(u).y;
+      } else {
+        g.node(u).y = y;
+      }
+    }
+  }
+
+  function debugPositioning(align, g, layering, xs) {
+    layering.forEach(function(l, li) {
+      var u, xU;
+      l.forEach(function(v) {
+        var xV = xs[v];
+        if (u) {
+          var s = sep(g, u) + sep(g, v);
+          if (xV - xU < s)
+            console.log('Position phase: sep violation. Align: ' + align + '. Layer: ' + li + '. ' +
+              'U: ' + u + ' V: ' + v + '. Actual sep: ' + (xV - xU) + ' Expected sep: ' + s);
+        }
+        u = v;
+        xU = xV;
+      });
+    });
+  }
+};
+
+},{"./util":26}],19:[function(require,module,exports){
+var util = require('./util'),
+    acyclic = require('./rank/acyclic'),
+    initRank = require('./rank/initRank'),
+    feasibleTree = require('./rank/feasibleTree'),
+    constraints = require('./rank/constraints'),
+    simplex = require('./rank/simplex'),
+    components = require('graphlib').alg.components,
+    filter = require('graphlib').filter;
+
+exports.run = run;
+exports.restoreEdges = restoreEdges;
+
+/*
+ * Heuristic function that assigns a rank to each node of the input graph with
+ * the intent of minimizing edge lengths, while respecting the `minLen`
+ * attribute of incident edges.
+ *
+ * Prerequisites:
+ *
+ *  * Each edge in the input graph must have an assigned 'minLen' attribute
+ */
+function run(g, useSimplex) {
+  expandSelfLoops(g);
+
+  // If there are rank constraints on nodes, then build a new graph that
+  // encodes the constraints.
+  util.time('constraints.apply', constraints.apply)(g);
+
+  expandSidewaysEdges(g);
+
+  // Reverse edges to get an acyclic graph, we keep the graph in an acyclic
+  // state until the very end.
+  util.time('acyclic', acyclic)(g);
+
+  // Convert the graph into a flat graph for ranking
+  var flatGraph = g.filterNodes(util.filterNonSubgraphs(g));
+
+  // Assign an initial ranking using DFS.
+  initRank(flatGraph);
+
+  // For each component improve the assigned ranks.
+  components(flatGraph).forEach(function(cmpt) {
+    var subgraph = flatGraph.filterNodes(filter.nodesFromList(cmpt));
+    rankComponent(subgraph, useSimplex);
+  });
+
+  // Relax original constraints
+  util.time('constraints.relax', constraints.relax(g));
+
+  // When handling nodes with constrained ranks it is possible to end up with
+  // edges that point to previous ranks. Most of the subsequent algorithms assume
+  // that edges are pointing to successive ranks only. Here we reverse any "back
+  // edges" and mark them as such. The acyclic algorithm will reverse them as a
+  // post processing step.
+  util.time('reorientEdges', reorientEdges)(g);
+}
+
+function restoreEdges(g) {
+  acyclic.undo(g);
+}
+
+/*
+ * Expand self loops into three dummy nodes. One will sit above the incident
+ * node, one will be at the same level, and one below. The result looks like:
+ *
+ *         /--<--x--->--\
+ *     node              y
+ *         \--<--z--->--/
+ *
+ * Dummy nodes x, y, z give us the shape of a loop and node y is where we place
+ * the label.
+ *
+ * TODO: consolidate knowledge of dummy node construction.
+ * TODO: support minLen = 2
+ */
+function expandSelfLoops(g) {
+  g.eachEdge(function(e, u, v, a) {
+    if (u === v) {
+      var x = addDummyNode(g, e, u, v, a, 0, false),
+          y = addDummyNode(g, e, u, v, a, 1, true),
+          z = addDummyNode(g, e, u, v, a, 2, false);
+      g.addEdge(null, x, u, {minLen: 1, selfLoop: true});
+      g.addEdge(null, x, y, {minLen: 1, selfLoop: true});
+      g.addEdge(null, u, z, {minLen: 1, selfLoop: true});
+      g.addEdge(null, y, z, {minLen: 1, selfLoop: true});
+      g.delEdge(e);
+    }
+  });
+}
+
+function expandSidewaysEdges(g) {
+  g.eachEdge(function(e, u, v, a) {
+    if (u === v) {
+      var origEdge = a.originalEdge,
+          dummy = addDummyNode(g, origEdge.e, origEdge.u, origEdge.v, origEdge.value, 0, true);
+      g.addEdge(null, u, dummy, {minLen: 1});
+      g.addEdge(null, dummy, v, {minLen: 1});
+      g.delEdge(e);
+    }
+  });
+}
+
+function addDummyNode(g, e, u, v, a, index, isLabel) {
+  return g.addNode(null, {
+    width: isLabel ? a.width : 0,
+    height: isLabel ? a.height : 0,
+    edge: { id: e, source: u, target: v, attrs: a },
+    dummy: true,
+    index: index
+  });
+}
+
+function reorientEdges(g) {
+  g.eachEdge(function(e, u, v, value) {
+    if (g.node(u).rank > g.node(v).rank) {
+      g.delEdge(e);
+      value.reversed = true;
+      g.addEdge(e, v, u, value);
+    }
+  });
+}
+
+function rankComponent(subgraph, useSimplex) {
+  var spanningTree = feasibleTree(subgraph);
+
+  if (useSimplex) {
+    util.log(1, 'Using network simplex for ranking');
+    simplex(subgraph, spanningTree);
+  }
+  normalize(subgraph);
+}
+
+function normalize(g) {
+  var m = util.min(g.nodes().map(function(u) { return g.node(u).rank; }));
+  g.eachNode(function(u, node) { node.rank -= m; });
+}
+
+},{"./rank/acyclic":20,"./rank/constraints":21,"./rank/feasibleTree":22,"./rank/initRank":23,"./rank/simplex":25,"./util":26,"graphlib":28}],20:[function(require,module,exports){
+var util = require('../util');
+
+module.exports = acyclic;
+module.exports.undo = undo;
+
+/*
+ * This function takes a directed graph that may have cycles and reverses edges
+ * as appropriate to break these cycles. Each reversed edge is assigned a
+ * `reversed` attribute with the value `true`.
+ *
+ * There should be no self loops in the graph.
+ */
+function acyclic(g) {
+  var onStack = {},
+      visited = {},
+      reverseCount = 0;
+  
+  function dfs(u) {
+    if (u in visited) return;
+    visited[u] = onStack[u] = true;
+    g.outEdges(u).forEach(function(e) {
+      var t = g.target(e),
+          value;
+
+      if (u === t) {
+        console.error('Warning: found self loop "' + e + '" for node "' + u + '"');
+      } else if (t in onStack) {
+        value = g.edge(e);
+        g.delEdge(e);
+        value.reversed = true;
+        ++reverseCount;
+        g.addEdge(e, t, u, value);
+      } else {
+        dfs(t);
+      }
+    });
+
+    delete onStack[u];
+  }
+
+  g.eachNode(function(u) { dfs(u); });
+
+  util.log(2, 'Acyclic Phase: reversed ' + reverseCount + ' edge(s)');
+
+  return reverseCount;
+}
+
+/*
+ * Given a graph that has had the acyclic operation applied, this function
+ * undoes that operation. More specifically, any edge with the `reversed`
+ * attribute is again reversed to restore the original direction of the edge.
+ */
+function undo(g) {
+  g.eachEdge(function(e, s, t, a) {
+    if (a.reversed) {
+      delete a.reversed;
+      g.delEdge(e);
+      g.addEdge(e, t, s, a);
+    }
+  });
+}
+
+},{"../util":26}],21:[function(require,module,exports){
+exports.apply = function(g) {
+  function dfs(sg) {
+    var rankSets = {};
+    g.children(sg).forEach(function(u) {
+      if (g.children(u).length) {
+        dfs(u);
+        return;
+      }
+
+      var value = g.node(u),
+          prefRank = value.prefRank;
+      if (prefRank !== undefined) {
+        if (!checkSupportedPrefRank(prefRank)) { return; }
+
+        if (!(prefRank in rankSets)) {
+          rankSets.prefRank = [u];
+        } else {
+          rankSets.prefRank.push(u);
+        }
+
+        var newU = rankSets[prefRank];
+        if (newU === undefined) {
+          newU = rankSets[prefRank] = g.addNode(null, { originalNodes: [] });
+          g.parent(newU, sg);
+        }
+
+        redirectInEdges(g, u, newU, prefRank === 'min');
+        redirectOutEdges(g, u, newU, prefRank === 'max');
+
+        // Save original node and remove it from reduced graph
+        g.node(newU).originalNodes.push({ u: u, value: value, parent: sg });
+        g.delNode(u);
+      }
+    });
+
+    addLightEdgesFromMinNode(g, sg, rankSets.min);
+    addLightEdgesToMaxNode(g, sg, rankSets.max);
+  }
+
+  dfs(null);
+};
+
+function checkSupportedPrefRank(prefRank) {
+  if (prefRank !== 'min' && prefRank !== 'max' && prefRank.indexOf('same_') !== 0) {
+    console.error('Unsupported rank type: ' + prefRank);
+    return false;
+  }
+  return true;
+}
+
+function redirectInEdges(g, u, newU, reverse) {
+  g.inEdges(u).forEach(function(e) {
+    var origValue = g.edge(e),
+        value;
+    if (origValue.originalEdge) {
+      value = origValue;
+    } else {
+      value =  {
+        originalEdge: { e: e, u: g.source(e), v: g.target(e), value: origValue },
+        minLen: g.edge(e).minLen
+      };
+    }
+
+    // Do not reverse edges for self-loops.
+    if (origValue.selfLoop) {
+      reverse = false;
+    }
+
+    if (reverse) {
+      // Ensure that all edges to min are reversed
+      g.addEdge(null, newU, g.source(e), value);
+      value.reversed = true;
+    } else {
+      g.addEdge(null, g.source(e), newU, value);
+    }
+  });
+}
+
+function redirectOutEdges(g, u, newU, reverse) {
+  g.outEdges(u).forEach(function(e) {
+    var origValue = g.edge(e),
+        value;
+    if (origValue.originalEdge) {
+      value = origValue;
+    } else {
+      value =  {
+        originalEdge: { e: e, u: g.source(e), v: g.target(e), value: origValue },
+        minLen: g.edge(e).minLen
+      };
+    }
+
+    // Do not reverse edges for self-loops.
+    if (origValue.selfLoop) {
+      reverse = false;
+    }
+
+    if (reverse) {
+      // Ensure that all edges from max are reversed
+      g.addEdge(null, g.target(e), newU, value);
+      value.reversed = true;
+    } else {
+      g.addEdge(null, newU, g.target(e), value);
+    }
+  });
+}
+
+function addLightEdgesFromMinNode(g, sg, minNode) {
+  if (minNode !== undefined) {
+    g.children(sg).forEach(function(u) {
+      // The dummy check ensures we don't add an edge if the node is involved
+      // in a self loop or sideways edge.
+      if (u !== minNode && !g.outEdges(minNode, u).length && !g.node(u).dummy) {
+        g.addEdge(null, minNode, u, { minLen: 0 });
+      }
+    });
+  }
+}
+
+function addLightEdgesToMaxNode(g, sg, maxNode) {
+  if (maxNode !== undefined) {
+    g.children(sg).forEach(function(u) {
+      // The dummy check ensures we don't add an edge if the node is involved
+      // in a self loop or sideways edge.
+      if (u !== maxNode && !g.outEdges(u, maxNode).length && !g.node(u).dummy) {
+        g.addEdge(null, u, maxNode, { minLen: 0 });
+      }
+    });
+  }
+}
+
+/*
+ * This function "relaxes" the constraints applied previously by the "apply"
+ * function. It expands any nodes that were collapsed and assigns the rank of
+ * the collapsed node to each of the expanded nodes. It also restores the
+ * original edges and removes any dummy edges pointing at the collapsed nodes.
+ *
+ * Note that the process of removing collapsed nodes also removes dummy edges
+ * automatically.
+ */
+exports.relax = function(g) {
+  // Save original edges
+  var originalEdges = [];
+  g.eachEdge(function(e, u, v, value) {
+    var originalEdge = value.originalEdge;
+    if (originalEdge) {
+      originalEdges.push(originalEdge);
+    }
+  });
+
+  // Expand collapsed nodes
+  g.eachNode(function(u, value) {
+    var originalNodes = value.originalNodes;
+    if (originalNodes) {
+      originalNodes.forEach(function(originalNode) {
+        originalNode.value.rank = value.rank;
+        g.addNode(originalNode.u, originalNode.value);
+        g.parent(originalNode.u, originalNode.parent);
+      });
+      g.delNode(u);
+    }
+  });
+
+  // Restore original edges
+  originalEdges.forEach(function(edge) {
+    g.addEdge(edge.e, edge.u, edge.v, edge.value);
+  });
+};
+
+},{}],22:[function(require,module,exports){
+/* jshint -W079 */
+var Set = require('cp-data').Set,
+/* jshint +W079 */
+    Digraph = require('graphlib').Digraph,
+    util = require('../util');
+
+module.exports = feasibleTree;
+
+/*
+ * Given an acyclic graph with each node assigned a `rank` attribute, this
+ * function constructs and returns a spanning tree. This function may reduce
+ * the length of some edges from the initial rank assignment while maintaining
+ * the `minLen` specified by each edge.
+ *
+ * Prerequisites:
+ *
+ * * The input graph is acyclic
+ * * Each node in the input graph has an assigned `rank` attribute
+ * * Each edge in the input graph has an assigned `minLen` attribute
+ *
+ * Outputs:
+ *
+ * A feasible spanning tree for the input graph (i.e. a spanning tree that
+ * respects each graph edge's `minLen` attribute) represented as a Digraph with
+ * a `root` attribute on graph.
+ *
+ * Nodes have the same id and value as that in the input graph.
+ *
+ * Edges in the tree have arbitrarily assigned ids. The attributes for edges
+ * include `reversed`. `reversed` indicates that the edge is a
+ * back edge in the input graph.
+ */
+function feasibleTree(g) {
+  var remaining = new Set(g.nodes()),
+      tree = new Digraph();
+
+  if (remaining.size() === 1) {
+    var root = g.nodes()[0];
+    tree.addNode(root, {});
+    tree.graph({ root: root });
+    return tree;
+  }
+
+  function addTightEdges(v) {
+    var continueToScan = true;
+    g.predecessors(v).forEach(function(u) {
+      if (remaining.has(u) && !slack(g, u, v)) {
+        if (remaining.has(v)) {
+          tree.addNode(v, {});
+          remaining.remove(v);
+          tree.graph({ root: v });
+        }
+
+        tree.addNode(u, {});
+        tree.addEdge(null, u, v, { reversed: true });
+        remaining.remove(u);
+        addTightEdges(u);
+        continueToScan = false;
+      }
+    });
+
+    g.successors(v).forEach(function(w)  {
+      if (remaining.has(w) && !slack(g, v, w)) {
+        if (remaining.has(v)) {
+          tree.addNode(v, {});
+          remaining.remove(v);
+          tree.graph({ root: v });
+        }
+
+        tree.addNode(w, {});
+        tree.addEdge(null, v, w, {});
+        remaining.remove(w);
+        addTightEdges(w);
+        continueToScan = false;
+      }
+    });
+    return continueToScan;
+  }
+
+  function createTightEdge() {
+    var minSlack = Number.MAX_VALUE;
+    remaining.keys().forEach(function(v) {
+      g.predecessors(v).forEach(function(u) {
+        if (!remaining.has(u)) {
+          var edgeSlack = slack(g, u, v);
+          if (Math.abs(edgeSlack) < Math.abs(minSlack)) {
+            minSlack = -edgeSlack;
+          }
+        }
+      });
+
+      g.successors(v).forEach(function(w) {
+        if (!remaining.has(w)) {
+          var edgeSlack = slack(g, v, w);
+          if (Math.abs(edgeSlack) < Math.abs(minSlack)) {
+            minSlack = edgeSlack;
+          }
+        }
+      });
+    });
+
+    tree.eachNode(function(u) { g.node(u).rank -= minSlack; });
+  }
+
+  while (remaining.size()) {
+    var nodesToSearch = !tree.order() ? remaining.keys() : tree.nodes();
+    for (var i = 0, il = nodesToSearch.length;
+         i < il && addTightEdges(nodesToSearch[i]);
+         ++i);
+    if (remaining.size()) {
+      createTightEdge();
+    }
+  }
+
+  return tree;
+}
+
+function slack(g, u, v) {
+  var rankDiff = g.node(v).rank - g.node(u).rank;
+  var maxMinLen = util.max(g.outEdges(u, v)
+                            .map(function(e) { return g.edge(e).minLen; }));
+  return rankDiff - maxMinLen;
+}
+
+},{"../util":26,"cp-data":5,"graphlib":28}],23:[function(require,module,exports){
+var util = require('../util'),
+    topsort = require('graphlib').alg.topsort;
+
+module.exports = initRank;
+
+/*
+ * Assigns a `rank` attribute to each node in the input graph and ensures that
+ * this rank respects the `minLen` attribute of incident edges.
+ *
+ * Prerequisites:
+ *
+ *  * The input graph must be acyclic
+ *  * Each edge in the input graph must have an assigned 'minLen' attribute
+ */
+function initRank(g) {
+  var sorted = topsort(g);
+
+  sorted.forEach(function(u) {
+    var inEdges = g.inEdges(u);
+    if (inEdges.length === 0) {
+      g.node(u).rank = 0;
+      return;
+    }
+
+    var minLens = inEdges.map(function(e) {
+      return g.node(g.source(e)).rank + g.edge(e).minLen;
+    });
+    g.node(u).rank = util.max(minLens);
+  });
+}
+
+},{"../util":26,"graphlib":28}],24:[function(require,module,exports){
+module.exports = {
+  slack: slack
+};
+
+/*
+ * A helper to calculate the slack between two nodes (`u` and `v`) given a
+ * `minLen` constraint. The slack represents how much the distance between `u`
+ * and `v` could shrink while maintaining the `minLen` constraint. If the value
+ * is negative then the constraint is currently violated.
+ *
+  This function requires that `u` and `v` are in `graph` and they both have a
+  `rank` attribute.
+ */
+function slack(graph, u, v, minLen) {
+  return Math.abs(graph.node(u).rank - graph.node(v).rank) - minLen;
+}
+
+},{}],25:[function(require,module,exports){
+var util = require('../util'),
+    rankUtil = require('./rankUtil');
+
+module.exports = simplex;
+
+function simplex(graph, spanningTree) {
+  // The network simplex algorithm repeatedly replaces edges of
+  // the spanning tree with negative cut values until no such
+  // edge exists.
+  initCutValues(graph, spanningTree);
+  while (true) {
+    var e = leaveEdge(spanningTree);
+    if (e === null) break;
+    var f = enterEdge(graph, spanningTree, e);
+    exchange(graph, spanningTree, e, f);
+  }
+}
+
+/*
+ * Set the cut values of edges in the spanning tree by a depth-first
+ * postorder traversal.  The cut value corresponds to the cost, in
+ * terms of a ranking's edge length sum, of lengthening an edge.
+ * Negative cut values typically indicate edges that would yield a
+ * smaller edge length sum if they were lengthened.
+ */
+function initCutValues(graph, spanningTree) {
+  computeLowLim(spanningTree);
+
+  spanningTree.eachEdge(function(id, u, v, treeValue) {
+    treeValue.cutValue = 0;
+  });
+
+  // Propagate cut values up the tree.
+  function dfs(n) {
+    var children = spanningTree.successors(n);
+    for (var c in children) {
+      var child = children[c];
+      dfs(child);
+    }
+    if (n !== spanningTree.graph().root) {
+      setCutValue(graph, spanningTree, n);
+    }
+  }
+  dfs(spanningTree.graph().root);
+}
+
+/*
+ * Perform a DFS postorder traversal, labeling each node v with
+ * its traversal order 'lim(v)' and the minimum traversal number
+ * of any of its descendants 'low(v)'.  This provides an efficient
+ * way to test whether u is an ancestor of v since
+ * low(u) <= lim(v) <= lim(u) if and only if u is an ancestor.
+ */
+function computeLowLim(tree) {
+  var postOrderNum = 0;
+  
+  function dfs(n) {
+    var children = tree.successors(n);
+    var low = postOrderNum;
+    for (var c in children) {
+      var child = children[c];
+      dfs(child);
+      low = Math.min(low, tree.node(child).low);
+    }
+    tree.node(n).low = low;
+    tree.node(n).lim = postOrderNum++;
+  }
+
+  dfs(tree.graph().root);
+}
+
+/*
+ * To compute the cut value of the edge parent -> child, we consider
+ * it and any other graph edges to or from the child.
+ *          parent
+ *             |
+ *           child
+ *          /      \
+ *         u        v
+ */
+function setCutValue(graph, tree, child) {
+  var parentEdge = tree.inEdges(child)[0];
+
+  // List of child's children in the spanning tree.
+  var grandchildren = [];
+  var grandchildEdges = tree.outEdges(child);
+  for (var gce in grandchildEdges) {
+    grandchildren.push(tree.target(grandchildEdges[gce]));
+  }
+
+  var cutValue = 0;
+
+  // TODO: Replace unit increment/decrement with edge weights.
+  var E = 0;    // Edges from child to grandchild's subtree.
+  var F = 0;    // Edges to child from grandchild's subtree.
+  var G = 0;    // Edges from child to nodes outside of child's subtree.
+  var H = 0;    // Edges from nodes outside of child's subtree to child.
+
+  // Consider all graph edges from child.
+  var outEdges = graph.outEdges(child);
+  var gc;
+  for (var oe in outEdges) {
+    var succ = graph.target(outEdges[oe]);
+    for (gc in grandchildren) {
+      if (inSubtree(tree, succ, grandchildren[gc])) {
+        E++;
+      }
+    }
+    if (!inSubtree(tree, succ, child)) {
+      G++;
+    }
+  }
+
+  // Consider all graph edges to child.
+  var inEdges = graph.inEdges(child);
+  for (var ie in inEdges) {
+    var pred = graph.source(inEdges[ie]);
+    for (gc in grandchildren) {
+      if (inSubtree(tree, pred, grandchildren[gc])) {
+        F++;
+      }
+    }
+    if (!inSubtree(tree, pred, child)) {
+      H++;
+    }
+  }
+
+  // Contributions depend on the alignment of the parent -> child edge
+  // and the child -> u or v edges.
+  var grandchildCutSum = 0;
+  for (gc in grandchildren) {
+    var cv = tree.edge(grandchildEdges[gc]).cutValue;
+    if (!tree.edge(grandchildEdges[gc]).reversed) {
+      grandchildCutSum += cv;
+    } else {
+      grandchildCutSum -= cv;
+    }
+  }
+
+  if (!tree.edge(parentEdge).reversed) {
+    cutValue += grandchildCutSum - E + F - G + H;
+  } else {
+    cutValue -= grandchildCutSum - E + F - G + H;
+  }
+
+  tree.edge(parentEdge).cutValue = cutValue;
+}
+
+/*
+ * Return whether n is a node in the subtree with the given
+ * root.
+ */
+function inSubtree(tree, n, root) {
+  return (tree.node(root).low <= tree.node(n).lim &&
+          tree.node(n).lim <= tree.node(root).lim);
+}
+
+/*
+ * Return an edge from the tree with a negative cut value, or null if there
+ * is none.
+ */
+function leaveEdge(tree) {
+  var edges = tree.edges();
+  for (var n in edges) {
+    var e = edges[n];
+    var treeValue = tree.edge(e);
+    if (treeValue.cutValue < 0) {
+      return e;
+    }
+  }
+  return null;
+}
+
+/*
+ * The edge e should be an edge in the tree, with an underlying edge
+ * in the graph, with a negative cut value.  Of the two nodes incident
+ * on the edge, take the lower one.  enterEdge returns an edge with
+ * minimum slack going from outside of that node's subtree to inside
+ * of that node's subtree.
+ */
+function enterEdge(graph, tree, e) {
+  var source = tree.source(e);
+  var target = tree.target(e);
+  var lower = tree.node(target).lim < tree.node(source).lim ? target : source;
+
+  // Is the tree edge aligned with the graph edge?
+  var aligned = !tree.edge(e).reversed;
+
+  var minSlack = Number.POSITIVE_INFINITY;
+  var minSlackEdge;
+  if (aligned) {
+    graph.eachEdge(function(id, u, v, value) {
+      if (id !== e && inSubtree(tree, u, lower) && !inSubtree(tree, v, lower)) {
+        var slack = rankUtil.slack(graph, u, v, value.minLen);
+        if (slack < minSlack) {
+          minSlack = slack;
+          minSlackEdge = id;
+        }
+      }
+    });
+  } else {
+    graph.eachEdge(function(id, u, v, value) {
+      if (id !== e && !inSubtree(tree, u, lower) && inSubtree(tree, v, lower)) {
+        var slack = rankUtil.slack(graph, u, v, value.minLen);
+        if (slack < minSlack) {
+          minSlack = slack;
+          minSlackEdge = id;
+        }
+      }
+    });
+  }
+
+  if (minSlackEdge === undefined) {
+    var outside = [];
+    var inside = [];
+    graph.eachNode(function(id) {
+      if (!inSubtree(tree, id, lower)) {
+        outside.push(id);
+      } else {
+        inside.push(id);
+      }
+    });
+    throw new Error('No edge found from outside of tree to inside');
+  }
+
+  return minSlackEdge;
+}
+
+/*
+ * Replace edge e with edge f in the tree, recalculating the tree root,
+ * the nodes' low and lim properties and the edges' cut values.
+ */
+function exchange(graph, tree, e, f) {
+  tree.delEdge(e);
+  var source = graph.source(f);
+  var target = graph.target(f);
+
+  // Redirect edges so that target is the root of its subtree.
+  function redirect(v) {
+    var edges = tree.inEdges(v);
+    for (var i in edges) {
+      var e = edges[i];
+      var u = tree.source(e);
+      var value = tree.edge(e);
+      redirect(u);
+      tree.delEdge(e);
+      value.reversed = !value.reversed;
+      tree.addEdge(e, v, u, value);
+    }
+  }
+
+  redirect(target);
+
+  var root = source;
+  var edges = tree.inEdges(root);
+  while (edges.length > 0) {
+    root = tree.source(edges[0]);
+    edges = tree.inEdges(root);
+  }
+
+  tree.graph().root = root;
+
+  tree.addEdge(null, source, target, {cutValue: 0});
+
+  initCutValues(graph, tree);
+
+  adjustRanks(graph, tree);
+}
+
+/*
+ * Reset the ranks of all nodes based on the current spanning tree.
+ * The rank of the tree's root remains unchanged, while all other
+ * nodes are set to the sum of minimum length constraints along
+ * the path from the root.
+ */
+function adjustRanks(graph, tree) {
+  function dfs(p) {
+    var children = tree.successors(p);
+    children.forEach(function(c) {
+      var minLen = minimumLength(graph, p, c);
+      graph.node(c).rank = graph.node(p).rank + minLen;
+      dfs(c);
+    });
+  }
+
+  dfs(tree.graph().root);
+}
+
+/*
+ * If u and v are connected by some edges in the graph, return the
+ * minimum length of those edges, as a positive number if v succeeds
+ * u and as a negative number if v precedes u.
+ */
+function minimumLength(graph, u, v) {
+  var outEdges = graph.outEdges(u, v);
+  if (outEdges.length > 0) {
+    return util.max(outEdges.map(function(e) {
+      return graph.edge(e).minLen;
+    }));
+  }
+
+  var inEdges = graph.inEdges(u, v);
+  if (inEdges.length > 0) {
+    return -util.max(inEdges.map(function(e) {
+      return graph.edge(e).minLen;
+    }));
+  }
+}
+
+},{"../util":26,"./rankUtil":24}],26:[function(require,module,exports){
+/*
+ * Returns the smallest value in the array.
+ */
+exports.min = function(values) {
+  return Math.min.apply(Math, values);
+};
+
+/*
+ * Returns the largest value in the array.
+ */
+exports.max = function(values) {
+  return Math.max.apply(Math, values);
+};
+
+/*
+ * Returns `true` only if `f(x)` is `true` for all `x` in `xs`. Otherwise
+ * returns `false`. This function will return immediately if it finds a
+ * case where `f(x)` does not hold.
+ */
+exports.all = function(xs, f) {
+  for (var i = 0; i < xs.length; ++i) {
+    if (!f(xs[i])) {
+      return false;
+    }
+  }
+  return true;
+};
+
+/*
+ * Accumulates the sum of elements in the given array using the `+` operator.
+ */
+exports.sum = function(values) {
+  return values.reduce(function(acc, x) { return acc + x; }, 0);
+};
+
+/*
+ * Returns an array of all values in the given object.
+ */
+exports.values = function(obj) {
+  return Object.keys(obj).map(function(k) { return obj[k]; });
+};
+
+exports.shuffle = function(array) {
+  for (i = array.length - 1; i > 0; --i) {
+    var j = Math.floor(Math.random() * (i + 1));
+    var aj = array[j];
+    array[j] = array[i];
+    array[i] = aj;
+  }
+};
+
+exports.propertyAccessor = function(self, config, field, setHook) {
+  return function(x) {
+    if (!arguments.length) return config[field];
+    config[field] = x;
+    if (setHook) setHook(x);
+    return self;
+  };
+};
+
+/*
+ * Given a layered, directed graph with `rank` and `order` node attributes,
+ * this function returns an array of ordered ranks. Each rank contains an array
+ * of the ids of the nodes in that rank in the order

<TRUNCATED>

Mime
View raw message