airflow-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From bo...@apache.org
Subject [08/16] incubator-airflow git commit: [AIRFLOW-2691] Manage JS dependencies via npm
Date Sun, 22 Jul 2018 07:24:39 GMT
http://git-wip-us.apache.org/repos/asf/incubator-airflow/blob/5a7f0b2e/airflow/www_rbac/static/dagre-d3.js
----------------------------------------------------------------------
diff --git a/airflow/www_rbac/static/dagre-d3.js b/airflow/www_rbac/static/dagre-d3.js
deleted file mode 100644
index 2da7cdd..0000000
--- a/airflow/www_rbac/static/dagre-d3.js
+++ /dev/null
@@ -1,5007 +0,0 @@
-;(function e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);throw new Error("Cannot find module '"+o+"'")}var f=n[o]={exports:{}};t[o][0].call(f.exports,function(e){var n=t[o][1][e];return s(n?n:e)},f,f.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<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,
-  Graph: require('graphlib').Graph,
-  Renderer: require('./lib/Renderer'),
-  json: require('graphlib').converter.json,
-  layout: require('dagre').layout,
-  version: require('./lib/version'),
-  debug: require('dagre').debug
-};
-
-},{"./lib/Renderer":3,"./lib/version":4,"dagre":11,"graphlib":29}],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.zoomSetup(defaultZoomSetup);
-  this.zoom(defaultZoom);
-  this.transition(defaultTransition);
-  this.postLayout(defaultPostLayout);
-  this.postRender(defaultPostRender);
-
-  this.edgeInterpolate('bundle');
-  this.edgeTension(0.95);
-  this.zoom_obj = null;
-}
-
-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.zoomSetup = function(zoomSetup) {
-  if (!arguments.length) { return this._zoomSetup; }
-  this._zoomSetup = bind(zoomSetup, this);
-  return this;
-};
-
-Renderer.prototype.zoom = function(zoom) {
-  if (!arguments.length) { return this._zoom; }
-  if (zoom) {
-    this._zoom = bind(zoom, this);
-  } else {
-    delete this._zoom;
-  }
-  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, orgSvg) {
-  // First copy the input graph so that it is not changed by the rendering
-  // process.
-  graph = copyAndInitGraph(graph);
-
-  // Create zoom elements
-  var svg = this._zoomSetup(graph, orgSvg);
-
-  // 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);
-
-  // Copy useDef attribute from input graph to output graph
-  graph.eachNode(function(u, a) {
-    if (a.useDef) {
-      result.node(u).useDef = a.useDef;
-    }
-  });
-
-  // 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, orgSvg);
-
-  this._postRender(result, svg);
-
-  return result;
-};
-
-function copyAndInitGraph(graph) {
-  var copy = graph.copy();
-
-  if (copy.graph() === undefined) {
-    copy.graph({});
-  }
-
-  if (!('arrowheadFix' in copy.graph())) {
-    copy.graph().arrowheadFix = true;
-  }
-
-  // Init labels if they were not present in the source graph
-  copy.nodes().forEach(function(u) {
-    var value = copyObject(copy.node(u));
-    copy.node(u, value);
-    if (!('label' in value)) { value.label = ''; }
-  });
-
-  copy.edges().forEach(function(e) {
-    var value = copyObject(copy.edge(e));
-    copy.edge(e, value);
-    if (!('label' in value)) { value.label = ''; }
-  });
-
-  return copy;
-}
-
-function copyObject(obj) {
-  var copy = {};
-  for (var k in obj) {
-    copy[k] = obj[k];
-  }
-  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) {
-    var attrs = g.node(u),
-        domNode = d3.select(this);
-    addLabel(attrs, domNode, true, 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), false, 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; });
-
-  var DEFAULT_ARROWHEAD = 'url(#arrowhead)',
-      createArrowhead = DEFAULT_ARROWHEAD;
-  if (!g.isDirected()) {
-    createArrowhead = null;
-  } else if (g.graph().arrowheadFix !== 'false' && g.graph().arrowheadFix !== false) {
-    createArrowhead = function() {
-      var strokeColor = d3.select(this).style('stroke');
-      if (strokeColor) {
-        var id = 'arrowhead-' + strokeColor.replace(/[^a-zA-Z0-9]/g, '_');
-        getOrMakeArrowhead(root, id).style('fill', strokeColor);
-        return 'url(#' + id + ')';
-      }
-      return DEFAULT_ARROWHEAD;
-    };
-  }
-
-  svgEdgePaths
-    .enter()
-      .append('g')
-        .attr('class', 'edgePath enter')
-        .append('path')
-          .style('opacity', 0);
-
-  svgEdgePaths
-    .selectAll('path')
-    .each(function(e) { applyStyle(g.edge(e).style, d3.select(this)); })
-    .attr('marker-end', createArrowhead);
-
-  this._transition(svgEdgePaths.exit())
-      .style('opacity', 0)
-      .remove();
-
-  return svgEdgePaths;
-};
-
-function defaultPositionNodes(g, svgNodes) {
-  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 isEllipse(obj) {
-  return Object.prototype.toString.call(obj) === '[object SVGEllipseElement]';
-}
-
-function isCircle(obj) {
-  return Object.prototype.toString.call(obj) === '[object SVGCircleElement]';
-}
-
-function isPolygon(obj) {
-  return Object.prototype.toString.call(obj) === '[object SVGPolygonElement]';
-}
-
-function intersectNode(nd, p1, root) {
-  if (nd.useDef) {
-    var definedFig = root.select('defs #' + nd.useDef).node();
-    if (definedFig) {
-      var outerFig = definedFig.childNodes[0];
-      if (isCircle(outerFig) || isEllipse(outerFig)) {
-        return intersectEllipse(nd, outerFig, p1);
-      } else if (isPolygon(outerFig)) {
-        return intersectPolygon(nd, outerFig, p1);
-      }
-    }
-  }
-  // TODO: use bpodgursky's shortening algorithm here
-  return intersectRect(nd, p1);
-}
-
-function defaultPositionEdgePaths(g, svgEdgePaths, root) {
-  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(intersectNode(source, p0, root));
-    points.push(intersectNode(target, p1, root));
-
-    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;
-}
-
-// Setup dom for zooming
-function defaultZoomSetup(graph, svg) {
-  var root = svg.property('ownerSVGElement');
-  // If the svg node is the root, we get null, so set to svg.
-  if (!root) {
-    root = svg;
-  } else {
-    root = d3.select(root);
-  }
-
-  if (root.select('rect.overlay').empty()) {
-    // Create an overlay for capturing mouse events that don't touch foreground
-    root.insert('rect', ':first-child')
-      .attr('class', 'overlay')
-      .attr('width', '100%')
-      .attr('height', '100%')
-      .style('fill', 'none')
-      .style('pointer-events', 'all');
-
-    // Capture the zoom behaviour from the svg
-    svg = svg.append('g')
-      .attr('class', 'zoom');
-
-    if (this._zoom) {
-      root.call(this._zoom(graph, svg));
-    }
-  }
-
-  return svg;
-}
-
-// By default allow pan and zoom
-function defaultZoom(graph, svg) {
-
-  this.zoom_obj = d3.behavior.zoom().on('zoom', function() {
-    svg.attr('transform', 'translate(' + d3.event.translate + ')scale(' + d3.event.scale + ')');
-  });
-  return this.zoom_obj;
-}
-
-function defaultPostLayout() {
-  // Do nothing
-}
-
-function defaultPostRender(graph, root) {
-  if (graph.isDirected()) {
-    // Fill = #333 is for backwards compatibility
-    getOrMakeArrowhead(root, 'arrowhead')
-      .attr('fill', '#333');
-  }
-}
-
-function getOrMakeArrowhead(root, id) {
-  var search = root.select('#' + id);
-  if (!search.empty()) { return search; }
-
-  var defs = root.select('defs');
-  if (defs.empty()) {
-    defs = root.append('svg:defs');
-  }
-
-  var marker =
-    defs
-      .append('svg:marker')
-        .attr('id', id)
-        .attr('viewBox', '0 0 10 10')
-        .attr('refX', 8)
-        .attr('refY', 5)
-        .attr('markerUnits', 'strokeWidth')
-        .attr('markerWidth', 8)
-        .attr('markerHeight', 5)
-        .attr('orient', 'auto');
-
-  marker
-    .append('svg:path')
-      .attr('d', 'M 0 0 L 10 5 L 0 10 z');
-
-  return marker;
-}
-
-function addLabel(node, root, addingNode, marginX, marginY) {
-  // If the node has 'useDef' meta data, we rely on that
-  if (node.useDef) {
-    root.append('use').attr('xlink:href', '#' + node.useDef);
-    return;
-  }
-  // Add the rect first so that it appears behind the label
-  var label = node.label;
-  var rect = root.append('rect');
-  if (node.width) {
-    rect.attr('width', node.width);
-  }
-  if (node.height) {
-    rect.attr('height', node.height);
-  }
-
-  var labelSvg = root.append('g'),
-      innerLabelSvg;
-
-  if (label[0] === '<') {
-    addForeignObjectLabel(label, labelSvg);
-    // No margin for HTML elements
-    marginX = marginY = 0;
-  } else {
-    innerLabelSvg = addTextLabel(label,
-                                 labelSvg,
-                                 Math.floor(node.labelCols),
-                                 node.labelCut);
-    applyStyle(node.labelStyle, innerLabelSvg);
-  }
-
-  var labelBBox = labelSvg.node().getBBox();
-  labelSvg.attr('transform',
-                'translate(' + (-labelBBox.width / 2) + ',' + (-labelBBox.height / 2) + ')');
-
-  var bbox = root.node().getBBox();
-
-  rect
-    .attr('rx', node.rx ? node.rx : 5)
-    .attr('ry', node.ry ? node.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)
-    .attr('fill', '#fff');
-
-  if (addingNode) {
-    applyStyle(node.style, rect);
-
-    if (node.fill) {
-      rect.style('fill', node.fill);
-    }
-
-    if (node.stroke) {
-      rect.style('stroke', node.stroke);
-    }
-
-    if (node['stroke-width']) {
-      rect.style('stroke-width', node['stroke-width'] + 'px');
-    }
-
-    if (node['stroke-dasharray']) {
-      rect.style('stroke-dasharray', node['stroke-dasharray']);
-    }
-
-    if (node.href) {
-      root
-        .attr('class', root.attr('class') + ' clickable')
-        .on('click', function() {
-          window.open(node.href);
-        });
-    }
-  }
-}
-
-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]);
-  }
-
-  return node;
-}
-
-// 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(new 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;
-
-  // 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 intersectEllipse(node, ellipseOrCircle, point) {
-  // Formulae from: http://mathworld.wolfram.com/Ellipse-LineIntersection.html
-
-  var cx = node.x;
-  var cy = node.y;
-  var rx, ry;
-
-  if (isCircle(ellipseOrCircle)) {
-    rx = ry = ellipseOrCircle.r.baseVal.value;
-  } else {
-    rx = ellipseOrCircle.rx.baseVal.value;
-    ry = ellipseOrCircle.ry.baseVal.value;
-  }
-
-  var px = cx - point.x;
-  var py = cy - point.y;
-
-  var det = Math.sqrt(rx * rx * py * py + ry * ry * px * px);
-
-  var dx = Math.abs(rx * ry * px / det);
-  if (point.x < cx) {
-    dx = -dx;
-  }
-  var dy = Math.abs(rx * ry * py / det);
-  if (point.y < cy) {
-    dy = -dy;
-  }
-
-  return {x: cx + dx, y: cy + dy};
-}
-
-function sameSign(r1, r2) {
-  return r1 * r2 > 0;
-}
-
-// Add point to the found intersections, but check first that it is unique.
-function addPoint(x, y, intersections) {
-  if (!intersections.some(function (elm) { return elm[0] === x && elm[1] === y; })) {
-    intersections.push([x, y]);
-  }
-}
-
-function intersectLine(x1, y1, x2, y2, x3, y3, x4, y4, intersections) {
-  // Algorithm from J. Avro, (ed.) Graphics Gems, No 2, Morgan Kaufmann, 1994, p7 and p473.
-
-  var a1, a2, b1, b2, c1, c2;
-  var r1, r2 , r3, r4;
-  var denom, offset, num;
-  var x, y;
-
-  // Compute a1, b1, c1, where line joining points 1 and 2 is F(x,y) = a1 x + b1 y + c1 = 0.
-  a1 = y2 - y1;
-  b1 = x1 - x2;
-  c1 = (x2 * y1) - (x1 * y2);
-
-  // Compute r3 and r4.
-  r3 = ((a1 * x3) + (b1 * y3) + c1);
-  r4 = ((a1 * x4) + (b1 * y4) + c1);
-
-  // Check signs of r3 and r4. If both point 3 and point 4 lie on
-  // same side of line 1, the line segments do not intersect.
-  if ((r3 !== 0) && (r4 !== 0) && sameSign(r3, r4)) {
-    return /*DONT_INTERSECT*/;
-  }
-
-  // Compute a2, b2, c2 where line joining points 3 and 4 is G(x,y) = a2 x + b2 y + c2 = 0
-  a2 = y4 - y3;
-  b2 = x3 - x4;
-  c2 = (x4 * y3) - (x3 * y4);
-
-  // Compute r1 and r2
-  r1 = (a2 * x1) + (b2 * y1) + c2;
-  r2 = (a2 * x2) + (b2 * y2) + c2;
-
-  // Check signs of r1 and r2. If both point 1 and point 2 lie
-  // on same side of second line segment, the line segments do
-  // not intersect.
-  if ((r1 !== 0) && (r2 !== 0) && (sameSign(r1, r2))) {
-    return /*DONT_INTERSECT*/;
-  }
-
-  // Line segments intersect: compute intersection point.
-  denom = (a1 * b2) - (a2 * b1);
-  if (denom === 0) {
-    return /*COLLINEAR*/;
-  }
-
-  offset = Math.abs(denom / 2);
-
-  // The denom/2 is to get rounding instead of truncating. It
-  // is added or subtracted to the numerator, depending upon the
-  // sign of the numerator.
-  num = (b1 * c2) - (b2 * c1);
-  x = (num < 0) ? ((num - offset) / denom) : ((num + offset) / denom);
-
-  num = (a2 * c1) - (a1 * c2);
-  y = (num < 0) ? ((num - offset) / denom) : ((num + offset) / denom);
-
-  // lines_intersect
-  addPoint(x, y, intersections);
-}
-
-function intersectPolygon(node, polygon, point) {
-  var x1 = node.x;
-  var y1 = node.y;
-  var x2 = point.x;
-  var y2 = point.y;
-
-  var intersections = [];
-  var points = polygon.points;
-
-  var minx = 100000, miny = 100000;
-  for (var j = 0; j < points.numberOfItems; j++) {
-    var p = points.getItem(j);
-    minx = Math.min(minx, p.x);
-    miny = Math.min(miny, p.y);
-  }
-
-  var left = x1 - node.width / 2 - minx;
-  var top =  y1 - node.height / 2 - miny;
-
-  for (var i = 0; i < points.numberOfItems; i++) {
-    var p1 = points.getItem(i);
-    var p2 = points.getItem(i < points.numberOfItems - 1 ? i + 1 : 0);
-    intersectLine(x1, y1, x2, y2, left + p1.x, top + p1.y, left + p2.x, top + p2.y, intersections);
-  }
-
-  if (intersections.length === 1) {
-    return {x: intersections[0][0], y: intersections[0][1]};
-  }
-
-  if (intersections.length > 1) {
-    // More intersections, find the one nearest to edge end point
-    intersections.sort(function(p, q) {
-      var pdx = p[0] - point.x,
-         pdy = p[1] - point.y,
-         distp = Math.sqrt(pdx * pdx + pdy * pdy),
-
-         qdx = q[0] - point.x,
-         qdy = q[1] - point.y,
-         distq = Math.sqrt(qdx * qdx + qdy * qdy);
-
-      return (distp < distq) ? -1 : (distp === distq ? 0 : 1);
-    });
-    return {x: intersections[0][0], y: intersections[0][1]};
-  } else {
-    console.log('NO INTERSECTION FOUND, RETURN NODE CENTER', node);
-    return node;
-  }
-}
-
-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);
-  };
-}
-
-function applyStyle(style, domNode) {
-  if (style) {
-    var currStyle = domNode.attr('style') || '';
-    domNode.attr('style', currStyle + '; ' + style);
-  }
-}
-
-},{"d3":10,"dagre":11}],4:[function(require,module,exports){
-module.exports = '0.2.9';
-
-},{}],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");
-exports.debug = require("./lib/debug");
-
-},{"./lib/debug":12,"./lib/layout":13,"./lib/version":28,"graphlib":29}],12:[function(require,module,exports){
-'use strict';
-
-var util = require('./util');
-
-/**
- * Renders a graph in a stringified DOT format that indicates the ordering of
- * nodes by layer. Circles represent normal nodes. Diamons represent dummy
- * nodes. While we try to put nodes in clusters, it appears that graphviz
- * does not respect this because we're later using subgraphs for ordering nodes
- * in each layer.
- */
-exports.dotOrdering = function(g) {
-  var ordering = util.ordering(g.filterNodes(util.filterNonSubgraphs(g)));
-  var result = 'digraph {';
-
-  function dfs(u) {
-    var children = g.children(u);
-    if (children.length) {
-      result += 'subgraph cluster_' + u + ' {';
-      result += 'label="' + u + '";';
-      children.forEach(function(v) {
-        dfs(v);
-      });
-      result += '}';
-    } else {
-      result += u;
-      if (g.node(u).dummy) {
-        result += ' [shape=diamond]';
-      }
-      result += ';';
-    }
-  }
-
-  g.children(null).forEach(dfs);
-
-  ordering.forEach(function(layer) {
-    result += 'subgraph { rank=same; edge [style="invis"];';
-    result += layer.join('->');
-    result += '}';
-  });
-
-  g.eachEdge(function(e, u, v) {
-    result += u + '->' + v + ';';
-  });
-
-  result += '}';
-
-  return result;
-};
-
-},{"./util":27}],13:[function(require,module,exports){
-'use strict';
-
-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":14,"./position":19,"./rank":20,"./util":27,"graphlib":29}],14:[function(require,module,exports){
-'use strict';
-
-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 (var i = 1; i < layerGraphs.length; ++i) {
-    cg = sortLayer(layerGraphs[i], cg, predecessorWeights(g, layerGraphs[i].nodes()));
-  }
-}
-
-function sweepUp(g, layerGraphs) {
-  var cg;
-  for (var i = layerGraphs.length - 2; i >= 0; --i) {
-    sortLayer(layerGraphs[i], cg, successorWeights(g, layerGraphs[i].nodes()));
-  }
-}
-
-},{"./order/crossCount":15,"./order/initLayerGraphs":16,"./order/initOrder":17,"./order/sortLayer":18,"./util":27}],15:[function(require,module,exports){
-'use strict';
-
-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":27}],16:[function(require,module,exports){
-'use strict';
-
-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":29}],17:[function(require,module,exports){
-'use strict';
-
-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":27,"./crossCount":15}],18:[function(require,module,exports){
-'use strict';
-
-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) {
-  weights = adjustWeights(g, weights);
-  var result = sortLayerSubgraph(g, null, cg, weights);
-
-  result.list.forEach(function(u, i) {
-    g.node(u).order = i;
-  });
-  return result.constraintGraph;
-}
-
-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: util.sum(ws) / ws.length,
-        order: g.node(u).order,
-        orderCount: 1,
-        list: [u]
-      };
-    }
-  });
-
-  resolveViolatedConstraints(g, cg, nodeData);
-
-  var keys = Object.keys(nodeData);
-  keys.sort(function(x, y) {
-    return nodeData[x].barycenter - nodeData[y].barycenter ||
-           nodeData[x].order - nodeData[y].order;
-  });
-
-  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),
-    order: (lhs.order * lhs.orderCount + rhs.order * rhs.orderCount) /
-           (lhs.orderCount + rhs.orderCount),
-    orderCount: lhs.orderCount + rhs.orderCount,
-    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;
-      }
-    }
-  }
-}
-
-// Adjust weights so that they fall in the range of 0..|N|-1. If a node has no
-// weight assigned then set its adjusted weight to its current position. This
-// allows us to better retain the origiinal position of nodes without neighbors.
-function adjustWeights(g, weights) {
-  var minW = Number.MAX_VALUE,
-      maxW = 0,
-      adjusted = {};
-  g.eachNode(function(u) {
-    if (g.children(u).length) return;
-
-    var ws = weights[u];
-    if (ws.length) {
-      minW = Math.min(minW, util.min(ws));
-      maxW = Math.max(maxW, util.max(ws));
-    }
-  });
-
-  var rangeW = (maxW - minW);
-  g.eachNode(function(u) {
-    if (g.children(u).length) return;
-
-    var ws = weights[u];
-    if (!ws.length) {
-      adjusted[u] = [g.node(u).order];
-    } else {
-      adjusted[u] = ws.map(function(w) {
-        if (rangeW) {
-          return (w - minW) * (g.order() - 1) / rangeW;
-        } else {
-          return g.order() - 1 / 2;
-        }
-      });
-    }
-  });
-
-  return adjusted;
-}
-
-},{"../util":27,"graphlib":29}],19:[function(require,module,exports){
-'use strict';
-
-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":27}],20:[function(require,module,exports){
-'use strict';
-
-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":21,"./rank/constraints":22,"./rank/feasibleTree":23,"./rank/initRank":24,"./rank/simplex":26,"./util":27,"graphlib":29}],21:[function(require,module,exports){
-'use strict';
-
-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":27}],22:[function(require,module,exports){
-'use strict';
-
-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);
-  });
-};
-
-},{}],23:[function(require,module,exports){
-'use strict';
-
-/* 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":27,"cp-data":5,"graphlib":29}],24:[function(require,module,exports){
-'use strict';
-
-var util = require

<TRUNCATED>


Mime
View raw message