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>
