js/joint.layout.DirectedGraph.js

   1 /*! JointJS v0.9.0 - JavaScript diagramming library  2014-05-13
   2
   3
   4 This Source Code Form is subject to the terms of the Mozilla Public
   5 License, v. 2.0. If a copy of the MPL was not distributed with this
   6 file, You can obtain one at http://mozilla.org/MPL/2.0/.
   7  */
   8 ;(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){
   9 var global=typeof self !== "undefined" ? self : typeof window !== "undefined" ? window : {};/**
  10  * @license
  11  * Copyright (c) 2012-2013 Chris Pettitt
  12  *
  13  * Permission is hereby granted, free of charge, to any person obtaining a copy
  14  * of this software and associated documentation files (the "Software"), to deal
  15  * in the Software without restriction, including without limitation the rights
  16  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  17  * copies of the Software, and to permit persons to whom the Software is
  18  * furnished to do so, subject to the following conditions:
  19  *
  20  * The above copyright notice and this permission notice shall be included in
  21  * all copies or substantial portions of the Software.
  22  *
  23  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  24  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  25  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  26  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  27  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  28  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  29  * THE SOFTWARE.
  30  */
  31 global.dagre = require("./index");
  32
  33 },{"./index":2}],2:[function(require,module,exports){
  34 /*
  35 Copyright (c) 2012-2013 Chris Pettitt
  36
  37 Permission is hereby granted, free of charge, to any person obtaining a copy
  38 of this software and associated documentation files (the "Software"), to deal
  39 in the Software without restriction, including without limitation the rights
  40 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  41 copies of the Software, and to permit persons to whom the Software is
  42 furnished to do so, subject to the following conditions:
  43
  44 The above copyright notice and this permission notice shall be included in
  45 all copies or substantial portions of the Software.
  46
  47 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  48 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  49 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  50 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  51 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  52 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  53 THE SOFTWARE.
  54 */
  55 exports.Digraph = require("graphlib").Digraph;
  56 exports.Graph = require("graphlib").Graph;
  57 exports.layout = require("./lib/layout");
  58 exports.version = require("./lib/version");
  59
  60 },{"./lib/layout":3,"./lib/version":18,"graphlib":24}],3:[function(require,module,exports){
  61 var util = require('./util'),
  62     rank = require('./rank'),
  63     order = require('./order'),
  64     CGraph = require('graphlib').CGraph,
  65     CDigraph = require('graphlib').CDigraph;
  66
  67 module.exports = function() {
  68   // External configuration
  69   var config = {
  70     // How much debug information to include?
  71     debugLevel: 2,
  72     // Max number of sweeps to perform in order phase
  73     orderMaxSweeps: order.DEFAULT_MAX_SWEEPS,
  74     // Use network simplex algorithm in ranking
  75     rankSimplex: false,
  76     // Rank direction. Valid values are (TB, LR)
  77     rankDir: 'TB'
  78   };
  79
  80   // Phase functions
  81   var position = require('./position')();
  82
  83   // This layout object
  84   var self = {};
  85
  86   self.orderIters = util.propertyAccessor(self, config, 'orderMaxSweeps');
  87
  88   self.rankSimplex = util.propertyAccessor(self, config, 'rankSimplex');
  89
  90   self.nodeSep = delegateProperty(position.nodeSep);
  91   self.edgeSep = delegateProperty(position.edgeSep);
  92   self.universalSep = delegateProperty(position.universalSep);
  93   self.rankSep = delegateProperty(position.rankSep);
  94   self.rankDir = util.propertyAccessor(self, config, 'rankDir');
  95   self.debugAlignment = delegateProperty(position.debugAlignment);
  96
  97   self.debugLevel = util.propertyAccessor(self, config, 'debugLevel', function(x) {
  98     util.log.level = x;
  99     position.debugLevel(x);
 100   });
 101
 102   self.run = util.time('Total layout', run);
 103
 104   self._normalize = normalize;
 105
 106   return self;
 107
 108   /*
 109    * Constructs an adjacency graph using the nodes and edges specified through
 110    * config. For each node and edge we add a property `dagre` that contains an
 111    * object that will hold intermediate and final layout information. Some of
 112    * the contents include:
 113    *
 114    *  1) A generated ID that uniquely identifies the object.
 115    *  2) Dimension information for nodes (copied from the source node).
 116    *  3) Optional dimension information for edges.
 117    *
 118    * After the adjacency graph is constructed the code no longer needs to use
 119    * the original nodes and edges passed in via config.
 120    */
 121   function initLayoutGraph(inputGraph) {
 122     var g = new CDigraph();
 123
 124     inputGraph.eachNode(function(u, value) {
 125       if (value === undefined) value = {};
 126       g.addNode(u, {
 127         width: value.width,
 128         height: value.height
 129       });
 130       if (value.hasOwnProperty('rank')) {
 131         g.node(u).prefRank = value.rank;
 132       }
 133     });
 134
 135     // Set up subgraphs
 136     if (inputGraph.parent) {
 137       inputGraph.nodes().forEach(function(u) {
 138         g.parent(u, inputGraph.parent(u));
 139       });
 140     }
 141
 142     inputGraph.eachEdge(function(e, u, v, value) {
 143       if (value === undefined) value = {};
 144       var newValue = {
 145         e: e,
 146         minLen: value.minLen || 1,
 147         width: value.width || 0,
 148         height: value.height || 0,
 149         points: []
 150       };
 151
 152       g.addEdge(null, u, v, newValue);
 153     });
 154
 155     // Initial graph attributes
 156     var graphValue = inputGraph.graph() || {};
 157     g.graph({
 158       rankDir: graphValue.rankDir || config.rankDir,
 159       orderRestarts: graphValue.orderRestarts
 160     });
 161
 162     return g;
 163   }
 164
 165   function run(inputGraph) {
 166     var rankSep = self.rankSep();
 167     var g;
 168     try {
 169       // Build internal graph
 170       g = util.time('initLayoutGraph', initLayoutGraph)(inputGraph);
 171
 172       if (g.order() === 0) {
 173         return g;
 174       }
 175
 176       // Make space for edge labels
 177       g.eachEdge(function(e, s, t, a) {
 178         a.minLen *= 2;
 179       });
 180       self.rankSep(rankSep / 2);
 181
 182       // Determine the rank for each node. Nodes with a lower rank will appear
 183       // above nodes of higher rank.
 184       util.time('rank.run', rank.run)(g, config.rankSimplex);
 185
 186       // Normalize the graph by ensuring that every edge is proper (each edge has
 187       // a length of 1). We achieve this by adding dummy nodes to long edges,
 188       // thus shortening them.
 189       util.time('normalize', normalize)(g);
 190
 191       // Order the nodes so that edge crossings are minimized.
 192       util.time('order', order)(g, config.orderMaxSweeps);
 193
 194       // Find the x and y coordinates for every node in the graph.
 195       util.time('position', position.run)(g);
 196
 197       // De-normalize the graph by removing dummy nodes and augmenting the
 198       // original long edges with coordinate information.
 199       util.time('undoNormalize', undoNormalize)(g);
 200
 201       // Reverses points for edges that are in a reversed state.
 202       util.time('fixupEdgePoints', fixupEdgePoints)(g);
 203
 204       // Restore delete edges and reverse edges that were reversed in the rank
 205       // phase.
 206       util.time('rank.restoreEdges', rank.restoreEdges)(g);
 207
 208       // Construct final result graph and return it
 209       return util.time('createFinalGraph', createFinalGraph)(g, inputGraph.isDirected());
 210     } finally {
 211       self.rankSep(rankSep);
 212     }
 213   }
 214
 215   /*
 216    * This function is responsible for 'normalizing' the graph. The process of
 217    * normalization ensures that no edge in the graph has spans more than one
 218    * rank. To do this it inserts dummy nodes as needed and links them by adding
 219    * dummy edges. This function keeps enough information in the dummy nodes and
 220    * edges to ensure that the original graph can be reconstructed later.
 221    *
 222    * This method assumes that the input graph is cycle free.
 223    */
 224   function normalize(g) {
 225     var dummyCount = 0;
 226     g.eachEdge(function(e, s, t, a) {
 227       var sourceRank = g.node(s).rank;
 228       var targetRank = g.node(t).rank;
 229       if (sourceRank + 1 < targetRank) {
 230         for (var u = s, rank = sourceRank + 1, i = 0; rank < targetRank; ++rank, ++i) {
 231           var v = '_D' + (++dummyCount);
 232           var node = {
 233             width: a.width,
 234             height: a.height,
 235             edge: { id: e, source: s, target: t, attrs: a },
 236             rank: rank,
 237             dummy: true
 238           };
 239
 240           // If this node represents a bend then we will use it as a control
 241           // point. For edges with 2 segments this will be the center dummy
 242           // node. For edges with more than two segments, this will be the
 243           // first and last dummy node.
 244           if (i === 0) node.index = 0;
 245           else if (rank + 1 === targetRank) node.index = 1;
 246
 247           g.addNode(v, node);
 248           g.addEdge(null, u, v, {});
 249           u = v;
 250         }
 251         g.addEdge(null, u, t, {});
 252         g.delEdge(e);
 253       }
 254     });
 255   }
 256
 257   /*
 258    * Reconstructs the graph as it was before normalization. The positions of
 259    * dummy nodes are used to build an array of points for the original 'long'
 260    * edge. Dummy nodes and edges are removed.
 261    */
 262   function undoNormalize(g) {
 263     g.eachNode(function(u, a) {
 264       if (a.dummy) {
 265         if ('index' in a) {
 266           var edge = a.edge;
 267           if (!g.hasEdge(edge.id)) {
 268             g.addEdge(edge.id, edge.source, edge.target, edge.attrs);
 269           }
 270           var points = g.edge(edge.id).points;
 271           points[a.index] = { x: a.x, y: a.y, ul: a.ul, ur: a.ur, dl: a.dl, dr: a.dr };
 272         }
 273         g.delNode(u);
 274       }
 275     });
 276   }
 277
 278   /*
 279    * For each edge that was reversed during the `acyclic` step, reverse its
 280    * array of points.
 281    */
 282   function fixupEdgePoints(g) {
 283     g.eachEdge(function(e, s, t, a) { if (a.reversed) a.points.reverse(); });
 284   }
 285
 286   function createFinalGraph(g, isDirected) {
 287     var out = isDirected ? new CDigraph() : new CGraph();
 288     out.graph(g.graph());
 289     g.eachNode(function(u, value) { out.addNode(u, value); });
 290     g.eachNode(function(u) { out.parent(u, g.parent(u)); });
 291     g.eachEdge(function(e, u, v, value) {
 292       out.addEdge(value.e, u, v, value);
 293     });
 294
 295     // Attach bounding box information
 296     var maxX = 0, maxY = 0;
 297     g.eachNode(function(u, value) {
 298       if (!g.children(u).length) {
 299         maxX = Math.max(maxX, value.x + value.width / 2);
 300         maxY = Math.max(maxY, value.y + value.height / 2);
 301       }
 302     });
 303     g.eachEdge(function(e, u, v, value) {
 304       var maxXPoints = Math.max.apply(Math, value.points.map(function(p) { return p.x; }));
 305       var maxYPoints = Math.max.apply(Math, value.points.map(function(p) { return p.y; }));
 306       maxX = Math.max(maxX, maxXPoints + value.width / 2);
 307       maxY = Math.max(maxY, maxYPoints + value.height / 2);
 308     });
 309     out.graph().width = maxX;
 310     out.graph().height = maxY;
 311
 312     return out;
 313   }
 314
 315   /*
 316    * Given a function, a new function is returned that invokes the given
 317    * function. The return value from the function is always the `self` object.
 318    */
 319   function delegateProperty(f) {
 320     return function() {
 321       if (!arguments.length) return f();
 322       f.apply(null, arguments);
 323       return self;
 324     };
 325   }
 326 };
 327
 328
 329 },{"./order":4,"./position":9,"./rank":10,"./util":17,"graphlib":24}],4:[function(require,module,exports){
 330 var util = require('./util'),
 331     crossCount = require('./order/crossCount'),
 332     initLayerGraphs = require('./order/initLayerGraphs'),
 333     initOrder = require('./order/initOrder'),
 334     sortLayer = require('./order/sortLayer');
 335
 336 module.exports = order;
 337
 338 // The maximum number of sweeps to perform before finishing the order phase.
 339 var DEFAULT_MAX_SWEEPS = 24;
 340 order.DEFAULT_MAX_SWEEPS = DEFAULT_MAX_SWEEPS;
 341
 342 /*
 343  * Runs the order phase with the specified `graph, `maxSweeps`, and
 344  * `debugLevel`. If `maxSweeps` is not specified we use `DEFAULT_MAX_SWEEPS`.
 345  * If `debugLevel` is not set we assume 0.
 346  */
 347 function order(g, maxSweeps) {
 348   if (arguments.length < 2) {
 349     maxSweeps = DEFAULT_MAX_SWEEPS;
 350   }
 351
 352   var restarts = g.graph().orderRestarts || 0;
 353
 354   var layerGraphs = initLayerGraphs(g);
 355   // TODO: remove this when we add back support for ordering clusters
 356   layerGraphs.forEach(function(lg) {
 357     lg = lg.filterNodes(function(u) { return !g.children(u).length; });
 358   });
 359
 360   var iters = 0,
 361       currentBestCC,
 362       allTimeBestCC = Number.MAX_VALUE,
 363       allTimeBest = {};
 364
 365   function saveAllTimeBest() {
 366     g.eachNode(function(u, value) { allTimeBest[u] = value.order; });
 367   }
 368
 369   for (var j = 0; j < Number(restarts) + 1 && allTimeBestCC !== 0; ++j) {
 370     currentBestCC = Number.MAX_VALUE;
 371     initOrder(g, restarts > 0);
 372
 373     util.log(2, 'Order phase start cross count: ' + g.graph().orderInitCC);
 374
 375     var i, lastBest, cc;
 376     for (i = 0, lastBest = 0; lastBest < 4 && i < maxSweeps && currentBestCC > 0; ++i, ++lastBest, ++iters) {
 377       sweep(g, layerGraphs, i);
 378       cc = crossCount(g);
 379       if (cc < currentBestCC) {
 380         lastBest = 0;
 381         currentBestCC = cc;
 382         if (cc < allTimeBestCC) {
 383           saveAllTimeBest();
 384           allTimeBestCC = cc;
 385         }
 386       }
 387       util.log(3, 'Order phase start ' + j + ' iter ' + i + ' cross count: ' + cc);
 388     }
 389   }
 390
 391   Object.keys(allTimeBest).forEach(function(u) {
 392     if (!g.children || !g.children(u).length) {
 393       g.node(u).order = allTimeBest[u];
 394     }
 395   });
 396   g.graph().orderCC = allTimeBestCC;
 397
 398   util.log(2, 'Order iterations: ' + iters);
 399   util.log(2, 'Order phase best cross count: ' + g.graph().orderCC);
 400 }
 401
 402 function predecessorWeights(g, nodes) {
 403   var weights = {};
 404   nodes.forEach(function(u) {
 405     weights[u] = g.inEdges(u).map(function(e) {
 406       return g.node(g.source(e)).order;
 407     });
 408   });
 409   return weights;
 410 }
 411
 412 function successorWeights(g, nodes) {
 413   var weights = {};
 414   nodes.forEach(function(u) {
 415     weights[u] = g.outEdges(u).map(function(e) {
 416       return g.node(g.target(e)).order;
 417     });
 418   });
 419   return weights;
 420 }
 421
 422 function sweep(g, layerGraphs, iter) {
 423   if (iter % 2 === 0) {
 424     sweepDown(g, layerGraphs, iter);
 425   } else {
 426     sweepUp(g, layerGraphs, iter);
 427   }
 428 }
 429
 430 function sweepDown(g, layerGraphs) {
 431   var cg;
 432   for (i = 1; i < layerGraphs.length; ++i) {
 433     cg = sortLayer(layerGraphs[i], cg, predecessorWeights(g, layerGraphs[i].nodes()));
 434   }
 435 }
 436
 437 function sweepUp(g, layerGraphs) {
 438   var cg;
 439   for (i = layerGraphs.length - 2; i >= 0; --i) {
 440     sortLayer(layerGraphs[i], cg, successorWeights(g, layerGraphs[i].nodes()));
 441   }
 442 }
 443
 444 },{"./order/crossCount":5,"./order/initLayerGraphs":6,"./order/initOrder":7,"./order/sortLayer":8,"./util":17}],5:[function(require,module,exports){
 445 var util = require('../util');
 446
 447 module.exports = crossCount;
 448
 449 /*
 450  * Returns the cross count for the given graph.
 451  */
 452 function crossCount(g) {
 453   var cc = 0;
 454   var ordering = util.ordering(g);
 455   for (var i = 1; i < ordering.length; ++i) {
 456     cc += twoLayerCrossCount(g, ordering[i-1], ordering[i]);
 457   }
 458   return cc;
 459 }
 460
 461 /*
 462  * This function searches through a ranked and ordered graph and counts the
 463  * number of edges that cross. This algorithm is derived from:
 464  *
 465  *    W. Barth et al., Bilayer Cross Counting, JGAA, 8(2) 179–194 (2004)
 466  */
 467 function twoLayerCrossCount(g, layer1, layer2) {
 468   var indices = [];
 469   layer1.forEach(function(u) {
 470     var nodeIndices = [];
 471     g.outEdges(u).forEach(function(e) { nodeIndices.push(g.node(g.target(e)).order); });
 472     nodeIndices.sort(function(x, y) { return x - y; });
 473     indices = indices.concat(nodeIndices);
 474   });
 475
 476   var firstIndex = 1;
 477   while (firstIndex < layer2.length) firstIndex <<= 1;
 478
 479   var treeSize = 2 * firstIndex - 1;
 480   firstIndex -= 1;
 481
 482   var tree = [];
 483   for (var i = 0; i < treeSize; ++i) { tree[i] = 0; }
 484
 485   var cc = 0;
 486   indices.forEach(function(i) {
 487     var treeIndex = i + firstIndex;
 488     ++tree[treeIndex];
 489     while (treeIndex > 0) {
 490       if (treeIndex % 2) {
 491         cc += tree[treeIndex + 1];
 492       }
 493       treeIndex = (treeIndex - 1) >> 1;
 494       ++tree[treeIndex];
 495     }
 496   });
 497
 498   return cc;
 499 }
 500
 501 },{"../util":17}],6:[function(require,module,exports){
 502 var nodesFromList = require('graphlib').filter.nodesFromList,
 503     /* jshint -W079 */
 504     Set = require('cp-data').Set;
 505
 506 module.exports = initLayerGraphs;
 507
 508 /*
 509  * This function takes a compound layered graph, g, and produces an array of
 510  * layer graphs. Each entry in the array represents a subgraph of nodes
 511  * relevant for performing crossing reduction on that layer.
 512  */
 513 function initLayerGraphs(g) {
 514   var ranks = [];
 515
 516   function dfs(u) {
 517     if (u === null) {
 518       g.children(u).forEach(function(v) { dfs(v); });
 519       return;
 520     }
 521
 522     var value = g.node(u);
 523     value.minRank = ('rank' in value) ? value.rank : Number.MAX_VALUE;
 524     value.maxRank = ('rank' in value) ? value.rank : Number.MIN_VALUE;
 525     var uRanks = new Set();
 526     g.children(u).forEach(function(v) {
 527       var rs = dfs(v);
 528       uRanks = Set.union([uRanks, rs]);
 529       value.minRank = Math.min(value.minRank, g.node(v).minRank);
 530       value.maxRank = Math.max(value.maxRank, g.node(v).maxRank);
 531     });
 532
 533     if ('rank' in value) uRanks.add(value.rank);
 534
 535     uRanks.keys().forEach(function(r) {
 536       if (!(r in ranks)) ranks[r] = [];
 537       ranks[r].push(u);
 538     });
 539
 540     return uRanks;
 541   }
 542   dfs(null);
 543
 544   var layerGraphs = [];
 545   ranks.forEach(function(us, rank) {
 546     layerGraphs[rank] = g.filterNodes(nodesFromList(us));
 547   });
 548
 549   return layerGraphs;
 550 }
 551
 552 },{"cp-data":19,"graphlib":24}],7:[function(require,module,exports){
 553 var crossCount = require('./crossCount'),
 554     util = require('../util');
 555
 556 module.exports = initOrder;
 557
 558 /*
 559  * Given a graph with a set of layered nodes (i.e. nodes that have a `rank`
 560  * attribute) this function attaches an `order` attribute that uniquely
 561  * arranges each node of each rank. If no constraint graph is provided the
 562  * order of the nodes in each rank is entirely arbitrary.
 563  */
 564 function initOrder(g, random) {
 565   var layers = [];
 566
 567   g.eachNode(function(u, value) {
 568     var layer = layers[value.rank];
 569     if (g.children && g.children(u).length > 0) return;
 570     if (!layer) {
 571       layer = layers[value.rank] = [];
 572     }
 573     layer.push(u);
 574   });
 575
 576   layers.forEach(function(layer) {
 577     if (random) {
 578       util.shuffle(layer);
 579     }
 580     layer.forEach(function(u, i) {
 581       g.node(u).order = i;
 582     });
 583   });
 584
 585   var cc = crossCount(g);
 586   g.graph().orderInitCC = cc;
 587   g.graph().orderCC = Number.MAX_VALUE;
 588 }
 589
 590 },{"../util":17,"./crossCount":5}],8:[function(require,module,exports){
 591 var util = require('../util');
 592 /*
 593     Digraph = require('graphlib').Digraph,
 594     topsort = require('graphlib').alg.topsort,
 595     nodesFromList = require('graphlib').filter.nodesFromList;
 596 */
 597
 598 module.exports = sortLayer;
 599
 600 /*
 601 function sortLayer(g, cg, weights) {
 602   var result = sortLayerSubgraph(g, null, cg, weights);
 603   result.list.forEach(function(u, i) {
 604     g.node(u).order = i;
 605   });
 606   return result.constraintGraph;
 607 }
 608 */
 609
 610 function sortLayer(g, cg, weights) {
 611   var ordering = [];
 612   var bs = {};
 613   g.eachNode(function(u, value) {
 614     ordering[value.order] = u;
 615     var ws = weights[u];
 616     if (ws.length) {
 617       bs[u] = util.sum(ws) / ws.length;
 618     }
 619   });
 620
 621   var toSort = g.nodes().filter(function(u) { return bs[u] !== undefined; });
 622   toSort.sort(function(x, y) {
 623     return bs[x] - bs[y] || g.node(x).order - g.node(y).order;
 624   });
 625
 626   for (var i = 0, j = 0, jl = toSort.length; j < jl; ++i) {
 627     if (bs[ordering[i]] !== undefined) {
 628       g.node(toSort[j++]).order = i;
 629     }
 630   }
 631 }
 632
 633 // TOOD: re-enable constrained sorting once we have a strategy for handling
 634 // undefined barycenters.
 635 /*
 636 function sortLayerSubgraph(g, sg, cg, weights) {
 637   cg = cg ? cg.filterNodes(nodesFromList(g.children(sg))) : new Digraph();
 638
 639   var nodeData = {};
 640   g.children(sg).forEach(function(u) {
 641     if (g.children(u).length) {
 642       nodeData[u] = sortLayerSubgraph(g, u, cg, weights);
 643       nodeData[u].firstSG = u;
 644       nodeData[u].lastSG = u;
 645     } else {
 646       var ws = weights[u];
 647       nodeData[u] = {
 648         degree: ws.length,
 649         barycenter: ws.length > 0 ? util.sum(ws) / ws.length : 0,
 650         list: [u]
 651       };
 652     }
 653   });
 654
 655   resolveViolatedConstraints(g, cg, nodeData);
 656
 657   var keys = Object.keys(nodeData);
 658   keys.sort(function(x, y) {
 659     return nodeData[x].barycenter - nodeData[y].barycenter;
 660   });
 661
 662   var result =  keys.map(function(u) { return nodeData[u]; })
 663                     .reduce(function(lhs, rhs) { return mergeNodeData(g, lhs, rhs); });
 664   return result;
 665 }
 666
 667 /*
 668 function mergeNodeData(g, lhs, rhs) {
 669   var cg = mergeDigraphs(lhs.constraintGraph, rhs.constraintGraph);
 670
 671   if (lhs.lastSG !== undefined && rhs.firstSG !== undefined) {
 672     if (cg === undefined) {
 673       cg = new Digraph();
 674     }
 675     if (!cg.hasNode(lhs.lastSG)) { cg.addNode(lhs.lastSG); }
 676     cg.addNode(rhs.firstSG);
 677     cg.addEdge(null, lhs.lastSG, rhs.firstSG);
 678   }
 679
 680   return {
 681     degree: lhs.degree + rhs.degree,
 682     barycenter: (lhs.barycenter * lhs.degree + rhs.barycenter * rhs.degree) /
 683                 (lhs.degree + rhs.degree),
 684     list: lhs.list.concat(rhs.list),
 685     firstSG: lhs.firstSG !== undefined ? lhs.firstSG : rhs.firstSG,
 686     lastSG: rhs.lastSG !== undefined ? rhs.lastSG : lhs.lastSG,
 687     constraintGraph: cg
 688   };
 689 }
 690
 691 function mergeDigraphs(lhs, rhs) {
 692   if (lhs === undefined) return rhs;
 693   if (rhs === undefined) return lhs;
 694
 695   lhs = lhs.copy();
 696   rhs.nodes().forEach(function(u) { lhs.addNode(u); });
 697   rhs.edges().forEach(function(e, u, v) { lhs.addEdge(null, u, v); });
 698   return lhs;
 699 }
 700
 701 function resolveViolatedConstraints(g, cg, nodeData) {
 702   // Removes nodes `u` and `v` from `cg` and makes any edges incident on them
 703   // incident on `w` instead.
 704   function collapseNodes(u, v, w) {
 705     // TODO original paper removes self loops, but it is not obvious when this would happen
 706     cg.inEdges(u).forEach(function(e) {
 707       cg.delEdge(e);
 708       cg.addEdge(null, cg.source(e), w);
 709     });
 710
 711     cg.outEdges(v).forEach(function(e) {
 712       cg.delEdge(e);
 713       cg.addEdge(null, w, cg.target(e));
 714     });
 715
 716     cg.delNode(u);
 717     cg.delNode(v);
 718   }
 719
 720   var violated;
 721   while ((violated = findViolatedConstraint(cg, nodeData)) !== undefined) {
 722     var source = cg.source(violated),
 723         target = cg.target(violated);
 724
 725     var v;
 726     while ((v = cg.addNode(null)) && g.hasNode(v)) {
 727       cg.delNode(v);
 728     }
 729
 730     // Collapse barycenter and list
 731     nodeData[v] = mergeNodeData(g, nodeData[source], nodeData[target]);
 732     delete nodeData[source];
 733     delete nodeData[target];
 734
 735     collapseNodes(source, target, v);
 736     if (cg.incidentEdges(v).length === 0) { cg.delNode(v); }
 737   }
 738 }
 739
 740 function findViolatedConstraint(cg, nodeData) {
 741   var us = topsort(cg);
 742   for (var i = 0; i < us.length; ++i) {
 743     var u = us[i];
 744     var inEdges = cg.inEdges(u);
 745     for (var j = 0; j < inEdges.length; ++j) {
 746       var e = inEdges[j];
 747       if (nodeData[cg.source(e)].barycenter >= nodeData[u].barycenter) {
 748         return e;
 749       }
 750     }
 751   }
 752 }
 753 */
 754
 755 },{"../util":17}],9:[function(require,module,exports){
 756 var util = require('./util');
 757
 758 /*
 759  * The algorithms here are based on Brandes and Köpf, "Fast and Simple
 760  * Horizontal Coordinate Assignment".
 761  */
 762 module.exports = function() {
 763   // External configuration
 764   var config = {
 765     nodeSep: 50,
 766     edgeSep: 10,
 767     universalSep: null,
 768     rankSep: 30
 769   };
 770
 771   var self = {};
 772
 773   self.nodeSep = util.propertyAccessor(self, config, 'nodeSep');
 774   self.edgeSep = util.propertyAccessor(self, config, 'edgeSep');
 775   // If not null this separation value is used for all nodes and edges
 776   // regardless of their widths. `nodeSep` and `edgeSep` are ignored with this
 777   // option.
 778   self.universalSep = util.propertyAccessor(self, config, 'universalSep');
 779   self.rankSep = util.propertyAccessor(self, config, 'rankSep');
 780   self.debugLevel = util.propertyAccessor(self, config, 'debugLevel');
 781
 782   self.run = run;
 783
 784   return self;
 785
 786   function run(g) {
 787     g = g.filterNodes(util.filterNonSubgraphs(g));
 788
 789     var layering = util.ordering(g);
 790
 791     var conflicts = findConflicts(g, layering);
 792
 793     var xss = {};
 794     ['u', 'd'].forEach(function(vertDir) {
 795       if (vertDir === 'd') layering.reverse();
 796
 797       ['l', 'r'].forEach(function(horizDir) {
 798         if (horizDir === 'r') reverseInnerOrder(layering);
 799
 800         var dir = vertDir + horizDir;
 801         var align = verticalAlignment(g, layering, conflicts, vertDir === 'u' ? 'predecessors' : 'successors');
 802         xss[dir]= horizontalCompaction(g, layering, align.pos, align.root, align.align);
 803
 804         if (config.debugLevel >= 3)
 805           debugPositioning(vertDir + horizDir, g, layering, xss[dir]);
 806
 807         if (horizDir === 'r') flipHorizontally(xss[dir]);
 808
 809         if (horizDir === 'r') reverseInnerOrder(layering);
 810       });
 811
 812       if (vertDir === 'd') layering.reverse();
 813     });
 814
 815     balance(g, layering, xss);
 816
 817     g.eachNode(function(v) {
 818       var xs = [];
 819       for (var alignment in xss) {
 820         var alignmentX = xss[alignment][v];
 821         posXDebug(alignment, g, v, alignmentX);
 822         xs.push(alignmentX);
 823       }
 824       xs.sort(function(x, y) { return x - y; });
 825       posX(g, v, (xs[1] + xs[2]) / 2);
 826     });
 827
 828     // Align y coordinates with ranks
 829     var y = 0, reverseY = g.graph().rankDir === 'BT' || g.graph().rankDir === 'RL';
 830     layering.forEach(function(layer) {
 831       var maxHeight = util.max(layer.map(function(u) { return height(g, u); }));
 832       y += maxHeight / 2;
 833       layer.forEach(function(u) {
 834         posY(g, u, reverseY ? -y : y);
 835       });
 836       y += maxHeight / 2 + config.rankSep;
 837     });
 838
 839     // Translate layout so that top left corner of bounding rectangle has
 840     // coordinate (0, 0).
 841     var minX = util.min(g.nodes().map(function(u) { return posX(g, u) - width(g, u) / 2; }));
 842     var minY = util.min(g.nodes().map(function(u) { return posY(g, u) - height(g, u) / 2; }));
 843     g.eachNode(function(u) {
 844       posX(g, u, posX(g, u) - minX);
 845       posY(g, u, posY(g, u) - minY);
 846     });
 847   }
 848
 849   /*
 850    * Generate an ID that can be used to represent any undirected edge that is
 851    * incident on `u` and `v`.
 852    */
 853   function undirEdgeId(u, v) {
 854     return u < v
 855       ? u.toString().length + ':' + u + '-' + v
 856       : v.toString().length + ':' + v + '-' + u;
 857   }
 858
 859   function findConflicts(g, layering) {
 860     var conflicts = {}, // Set of conflicting edge ids
 861         pos = {},       // Position of node in its layer
 862         prevLayer,
 863         currLayer,
 864         k0,     // Position of the last inner segment in the previous layer
 865         l,      // Current position in the current layer (for iteration up to `l1`)
 866         k1;     // Position of the next inner segment in the previous layer or
 867                 // the position of the last element in the previous layer
 868
 869     if (layering.length <= 2) return conflicts;
 870
 871     function updateConflicts(v) {
 872       var k = pos[v];
 873       if (k < k0 || k > k1) {
 874         conflicts[undirEdgeId(currLayer[l], v)] = true;
 875       }
 876     }
 877
 878     layering[1].forEach(function(u, i) { pos[u] = i; });
 879     for (var i = 1; i < layering.length - 1; ++i) {
 880       prevLayer = layering[i];
 881       currLayer = layering[i+1];
 882       k0 = 0;
 883       l = 0;
 884
 885       // Scan current layer for next node that is incident to an inner segement
 886       // between layering[i+1] and layering[i].
 887       for (var l1 = 0; l1 < currLayer.length; ++l1) {
 888         var u = currLayer[l1]; // Next inner segment in the current layer or
 889                                // last node in the current layer
 890         pos[u] = l1;
 891         k1 = undefined;
 892
 893         if (g.node(u).dummy) {
 894           var uPred = g.predecessors(u)[0];
 895           // Note: In the case of self loops and sideways edges it is possible
 896           // for a dummy not to have a predecessor.
 897           if (uPred !== undefined && g.node(uPred).dummy)
 898             k1 = pos[uPred];
 899         }
 900         if (k1 === undefined && l1 === currLayer.length - 1)
 901           k1 = prevLayer.length - 1;
 902
 903         if (k1 !== undefined) {
 904           for (; l <= l1; ++l) {
 905             g.predecessors(currLayer[l]).forEach(updateConflicts);
 906           }
 907           k0 = k1;
 908         }
 909       }
 910     }
 911
 912     return conflicts;
 913   }
 914
 915   function verticalAlignment(g, layering, conflicts, relationship) {
 916     var pos = {},   // Position for a node in its layer
 917         root = {},  // Root of the block that the node participates in
 918         align = {}; // Points to the next node in the block or, if the last
 919                     // element in the block, points to the first block's root
 920
 921     layering.forEach(function(layer) {
 922       layer.forEach(function(u, i) {
 923         root[u] = u;
 924         align[u] = u;
 925         pos[u] = i;
 926       });
 927     });
 928
 929     layering.forEach(function(layer) {
 930       var prevIdx = -1;
 931       layer.forEach(function(v) {
 932         var related = g[relationship](v), // Adjacent nodes from the previous layer
 933             mid;                          // The mid point in the related array
 934
 935         if (related.length > 0) {
 936           related.sort(function(x, y) { return pos[x] - pos[y]; });
 937           mid = (related.length - 1) / 2;
 938           related.slice(Math.floor(mid), Math.ceil(mid) + 1).forEach(function(u) {
 939             if (align[v] === v) {
 940               if (!conflicts[undirEdgeId(u, v)] && prevIdx < pos[u]) {
 941                 align[u] = v;
 942                 align[v] = root[v] = root[u];
 943                 prevIdx = pos[u];
 944               }
 945             }
 946           });
 947         }
 948       });
 949     });
 950
 951     return { pos: pos, root: root, align: align };
 952   }
 953
 954   // This function deviates from the standard BK algorithm in two ways. First
 955   // it takes into account the size of the nodes. Second it includes a fix to
 956   // the original algorithm that is described in Carstens, "Node and Label
 957   // Placement in a Layered Layout Algorithm".
 958   function horizontalCompaction(g, layering, pos, root, align) {
 959     var sink = {},       // Mapping of node id -> sink node id for class
 960         maybeShift = {}, // Mapping of sink node id -> { class node id, min shift }
 961         shift = {},      // Mapping of sink node id -> shift
 962         pred = {},       // Mapping of node id -> predecessor node (or null)
 963         xs = {};         // Calculated X positions
 964
 965     layering.forEach(function(layer) {
 966       layer.forEach(function(u, i) {
 967         sink[u] = u;
 968         maybeShift[u] = {};
 969         if (i > 0)
 970           pred[u] = layer[i - 1];
 971       });
 972     });
 973
 974     function updateShift(toShift, neighbor, delta) {
 975       if (!(neighbor in maybeShift[toShift])) {
 976         maybeShift[toShift][neighbor] = delta;
 977       } else {
 978         maybeShift[toShift][neighbor] = Math.min(maybeShift[toShift][neighbor], delta);
 979       }
 980     }
 981
 982     function placeBlock(v) {
 983       if (!(v in xs)) {
 984         xs[v] = 0;
 985         var w = v;
 986         do {
 987           if (pos[w] > 0) {
 988             var u = root[pred[w]];
 989             placeBlock(u);
 990             if (sink[v] === v) {
 991               sink[v] = sink[u];
 992             }
 993             var delta = sep(g, pred[w]) + sep(g, w);
 994             if (sink[v] !== sink[u]) {
 995               updateShift(sink[u], sink[v], xs[v] - xs[u] - delta);
 996             } else {
 997               xs[v] = Math.max(xs[v], xs[u] + delta);
 998             }
 999           }
1000           w = align[w];
1001         } while (w !== v);
1002       }
1003     }
1004
1005     // Root coordinates relative to sink
1006     util.values(root).forEach(function(v) {
1007       placeBlock(v);
1008     });
1009
1010     // Absolute coordinates
1011     // There is an assumption here that we've resolved shifts for any classes
1012     // that begin at an earlier layer. We guarantee this by visiting layers in
1013     // order.
1014     layering.forEach(function(layer) {
1015       layer.forEach(function(v) {
1016         xs[v] = xs[root[v]];
1017         if (v === root[v] && v === sink[v]) {
1018           var minShift = 0;
1019           if (v in maybeShift && Object.keys(maybeShift[v]).length > 0) {
1020             minShift = util.min(Object.keys(maybeShift[v])
1021                                  .map(function(u) {
1022                                       return maybeShift[v][u] + (u in shift ? shift[u] : 0);
1023                                       }
1024                                  ));
1025           }
1026           shift[v] = minShift;
1027         }
1028       });
1029     });
1030
1031     layering.forEach(function(layer) {
1032       layer.forEach(function(v) {
1033         xs[v] += shift[sink[root[v]]] || 0;
1034       });
1035     });
1036
1037     return xs;
1038   }
1039
1040   function findMinCoord(g, layering, xs) {
1041     return util.min(layering.map(function(layer) {
1042       var u = layer[0];
1043       return xs[u];
1044     }));
1045   }
1046
1047   function findMaxCoord(g, layering, xs) {
1048     return util.max(layering.map(function(layer) {
1049       var u = layer[layer.length - 1];
1050       return xs[u];
1051     }));
1052   }
1053
1054   function balance(g, layering, xss) {
1055     var min = {},                            // Min coordinate for the alignment
1056         max = {},                            // Max coordinate for the alginment
1057         smallestAlignment,
1058         shift = {};                          // Amount to shift a given alignment
1059
1060     function updateAlignment(v) {
1061       xss[alignment][v] += shift[alignment];
1062     }
1063
1064     var smallest = Number.POSITIVE_INFINITY;
1065     for (var alignment in xss) {
1066       var xs = xss[alignment];
1067       min[alignment] = findMinCoord(g, layering, xs);
1068       max[alignment] = findMaxCoord(g, layering, xs);
1069       var w = max[alignment] - min[alignment];
1070       if (w < smallest) {
1071         smallest = w;
1072         smallestAlignment = alignment;
1073       }
1074     }
1075
1076     // Determine how much to adjust positioning for each alignment
1077     ['u', 'd'].forEach(function(vertDir) {
1078       ['l', 'r'].forEach(function(horizDir) {
1079         var alignment = vertDir + horizDir;
1080         shift[alignment] = horizDir === 'l'
1081             ? min[smallestAlignment] - min[alignment]
1082             : max[smallestAlignment] - max[alignment];
1083       });
1084     });
1085
1086     // Find average of medians for xss array
1087     for (alignment in xss) {
1088       g.eachNode(updateAlignment);
1089     }
1090   }
1091
1092   function flipHorizontally(xs) {
1093     for (var u in xs) {
1094       xs[u] = -xs[u];
1095     }
1096   }
1097
1098   function reverseInnerOrder(layering) {
1099     layering.forEach(function(layer) {
1100       layer.reverse();
1101     });
1102   }
1103
1104   function width(g, u) {
1105     switch (g.graph().rankDir) {
1106       case 'LR': return g.node(u).height;
1107       case 'RL': return g.node(u).height;
1108       default:   return g.node(u).width;
1109     }
1110   }
1111
1112   function height(g, u) {
1113     switch(g.graph().rankDir) {
1114       case 'LR': return g.node(u).width;
1115       case 'RL': return g.node(u).width;
1116       default:   return g.node(u).height;
1117     }
1118   }
1119
1120   function sep(g, u) {
1121     if (config.universalSep !== null) {
1122       return config.universalSep;
1123     }
1124     var w = width(g, u);
1125     var s = g.node(u).dummy ? config.edgeSep : config.nodeSep;
1126     return (w + s) / 2;
1127   }
1128
1129   function posX(g, u, x) {
1130     if (g.graph().rankDir === 'LR' || g.graph().rankDir === 'RL') {
1131       if (arguments.length < 3) {
1132         return g.node(u).y;
1133       } else {
1134         g.node(u).y = x;
1135       }
1136     } else {
1137       if (arguments.length < 3) {
1138         return g.node(u).x;
1139       } else {
1140         g.node(u).x = x;
1141       }
1142     }
1143   }
1144
1145   function posXDebug(name, g, u, x) {
1146     if (g.graph().rankDir === 'LR' || g.graph().rankDir === 'RL') {
1147       if (arguments.length < 3) {
1148         return g.node(u)[name];
1149       } else {
1150         g.node(u)[name] = x;
1151       }
1152     } else {
1153       if (arguments.length < 3) {
1154         return g.node(u)[name];
1155       } else {
1156         g.node(u)[name] = x;
1157       }
1158     }
1159   }
1160
1161   function posY(g, u, y) {
1162     if (g.graph().rankDir === 'LR' || g.graph().rankDir === 'RL') {
1163       if (arguments.length < 3) {
1164         return g.node(u).x;
1165       } else {
1166         g.node(u).x = y;
1167       }
1168     } else {
1169       if (arguments.length < 3) {
1170         return g.node(u).y;
1171       } else {
1172         g.node(u).y = y;
1173       }
1174     }
1175   }
1176
1177   function debugPositioning(align, g, layering, xs) {
1178     layering.forEach(function(l, li) {
1179       var u, xU;
1180       l.forEach(function(v) {
1181         var xV = xs[v];
1182         if (u) {
1183           var s = sep(g, u) + sep(g, v);
1184           if (xV - xU < s)
1185             console.log('Position phase: sep violation. Align: ' + align + '. Layer: ' + li + '. ' +
1186               'U: ' + u + ' V: ' + v + '. Actual sep: ' + (xV - xU) + ' Expected sep: ' + s);
1187         }
1188         u = v;
1189         xU = xV;
1190       });
1191     });
1192   }
1193 };
1194
1195 },{"./util":17}],10:[function(require,module,exports){
1196 var util = require('./util'),
1197     acyclic = require('./rank/acyclic'),
1198     initRank = require('./rank/initRank'),
1199     feasibleTree = require('./rank/feasibleTree'),
1200     constraints = require('./rank/constraints'),
1201     simplex = require('./rank/simplex'),
1202     components = require('graphlib').alg.components,
1203     filter = require('graphlib').filter;
1204
1205 exports.run = run;
1206 exports.restoreEdges = restoreEdges;
1207
1208 /*
1209  * Heuristic function that assigns a rank to each node of the input graph with
1210  * the intent of minimizing edge lengths, while respecting the `minLen`
1211  * attribute of incident edges.
1212  *
1213  * Prerequisites:
1214  *
1215  *  * Each edge in the input graph must have an assigned 'minLen' attribute
1216  */
1217 function run(g, useSimplex) {
1218   expandSelfLoops(g);
1219
1220   // If there are rank constraints on nodes, then build a new graph that
1221   // encodes the constraints.
1222   util.time('constraints.apply', constraints.apply)(g);
1223
1224   expandSidewaysEdges(g);
1225
1226   // Reverse edges to get an acyclic graph, we keep the graph in an acyclic
1227   // state until the very end.
1228   util.time('acyclic', acyclic)(g);
1229
1230   // Convert the graph into a flat graph for ranking
1231   var flatGraph = g.filterNodes(util.filterNonSubgraphs(g));
1232
1233   // Assign an initial ranking using DFS.
1234   initRank(flatGraph);
1235
1236   // For each component improve the assigned ranks.
1237   components(flatGraph).forEach(function(cmpt) {
1238     var subgraph = flatGraph.filterNodes(filter.nodesFromList(cmpt));
1239     rankComponent(subgraph, useSimplex);
1240   });
1241
1242   // Relax original constraints
1243   util.time('constraints.relax', constraints.relax(g));
1244
1245   // When handling nodes with constrained ranks it is possible to end up with
1246   // edges that point to previous ranks. Most of the subsequent algorithms assume
1247   // that edges are pointing to successive ranks only. Here we reverse any "back
1248   // edges" and mark them as such. The acyclic algorithm will reverse them as a
1249   // post processing step.
1250   util.time('reorientEdges', reorientEdges)(g);
1251 }
1252
1253 function restoreEdges(g) {
1254   acyclic.undo(g);
1255 }
1256
1257 /*
1258  * Expand self loops into three dummy nodes. One will sit above the incident
1259  * node, one will be at the same level, and one below. The result looks like:
1260  *
1261  *         /--<--x--->--\
1262  *     node              y
1263  *         \--<--z--->--/
1264  *
1265  * Dummy nodes x, y, z give us the shape of a loop and node y is where we place
1266  * the label.
1267  *
1268  * TODO: consolidate knowledge of dummy node construction.
1269  * TODO: support minLen = 2
1270  */
1271 function expandSelfLoops(g) {
1272   g.eachEdge(function(e, u, v, a) {
1273     if (u === v) {
1274       var x = addDummyNode(g, e, u, v, a, 0, false),
1275           y = addDummyNode(g, e, u, v, a, 1, true),
1276           z = addDummyNode(g, e, u, v, a, 2, false);
1277       g.addEdge(null, x, u, {minLen: 1, selfLoop: true});
1278       g.addEdge(null, x, y, {minLen: 1, selfLoop: true});
1279       g.addEdge(null, u, z, {minLen: 1, selfLoop: true});
1280       g.addEdge(null, y, z, {minLen: 1, selfLoop: true});
1281       g.delEdge(e);
1282     }
1283   });
1284 }
1285
1286 function expandSidewaysEdges(g) {
1287   g.eachEdge(function(e, u, v, a) {
1288     if (u === v) {
1289       var origEdge = a.originalEdge,
1290           dummy = addDummyNode(g, origEdge.e, origEdge.u, origEdge.v, origEdge.value, 0, true);
1291       g.addEdge(null, u, dummy, {minLen: 1});
1292       g.addEdge(null, dummy, v, {minLen: 1});
1293       g.delEdge(e);
1294     }
1295   });
1296 }
1297
1298 function addDummyNode(g, e, u, v, a, index, isLabel) {
1299   return g.addNode(null, {
1300     width: isLabel ? a.width : 0,
1301     height: isLabel ? a.height : 0,
1302     edge: { id: e, source: u, target: v, attrs: a },
1303     dummy: true,
1304     index: index
1305   });
1306 }
1307
1308 function reorientEdges(g) {
1309   g.eachEdge(function(e, u, v, value) {
1310     if (g.node(u).rank > g.node(v).rank) {
1311       g.delEdge(e);
1312       value.reversed = true;
1313       g.addEdge(e, v, u, value);
1314     }
1315   });
1316 }
1317
1318 function rankComponent(subgraph, useSimplex) {
1319   var spanningTree = feasibleTree(subgraph);
1320
1321   if (useSimplex) {
1322     util.log(1, 'Using network simplex for ranking');
1323     simplex(subgraph, spanningTree);
1324   }
1325   normalize(subgraph);
1326 }
1327
1328 function normalize(g) {
1329   var m = util.min(g.nodes().map(function(u) { return g.node(u).rank; }));
1330   g.eachNode(function(u, node) { node.rank -= m; });
1331 }
1332
1333 },{"./rank/acyclic":11,"./rank/constraints":12,"./rank/feasibleTree":13,"./rank/initRank":14,"./rank/simplex":16,"./util":17,"graphlib":24}],11:[function(require,module,exports){
1334 var util = require('../util');
1335
1336 module.exports = acyclic;
1337 module.exports.undo = undo;
1338
1339 /*
1340  * This function takes a directed graph that may have cycles and reverses edges
1341  * as appropriate to break these cycles. Each reversed edge is assigned a
1342  * `reversed` attribute with the value `true`.
1343  *
1344  * There should be no self loops in the graph.
1345  */
1346 function acyclic(g) {
1347   var onStack = {},
1348       visited = {},
1349       reverseCount = 0;
1350
1351   function dfs(u) {
1352     if (u in visited) return;
1353     visited[u] = onStack[u] = true;
1354     g.outEdges(u).forEach(function(e) {
1355       var t = g.target(e),
1356           value;
1357
1358       if (u === t) {
1359         console.error('Warning: found self loop "' + e + '" for node "' + u + '"');
1360       } else if (t in onStack) {
1361         value = g.edge(e);
1362         g.delEdge(e);
1363         value.reversed = true;
1364         ++reverseCount;
1365         g.addEdge(e, t, u, value);
1366       } else {
1367         dfs(t);
1368       }
1369     });
1370
1371     delete onStack[u];
1372   }
1373
1374   g.eachNode(function(u) { dfs(u); });
1375
1376   util.log(2, 'Acyclic Phase: reversed ' + reverseCount + ' edge(s)');
1377
1378   return reverseCount;
1379 }
1380
1381 /*
1382  * Given a graph that has had the acyclic operation applied, this function
1383  * undoes that operation. More specifically, any edge with the `reversed`
1384  * attribute is again reversed to restore the original direction of the edge.
1385  */
1386 function undo(g) {
1387   g.eachEdge(function(e, s, t, a) {
1388     if (a.reversed) {
1389       delete a.reversed;
1390       g.delEdge(e);
1391       g.addEdge(e, t, s, a);
1392     }
1393   });
1394 }
1395
1396 },{"../util":17}],12:[function(require,module,exports){
1397 exports.apply = function(g) {
1398   function dfs(sg) {
1399     var rankSets = {};
1400     g.children(sg).forEach(function(u) {
1401       if (g.children(u).length) {
1402         dfs(u);
1403         return;
1404       }
1405
1406       var value = g.node(u),
1407           prefRank = value.prefRank;
1408       if (prefRank !== undefined) {
1409         if (!checkSupportedPrefRank(prefRank)) { return; }
1410
1411         if (!(prefRank in rankSets)) {
1412           rankSets.prefRank = [u];
1413         } else {
1414           rankSets.prefRank.push(u);
1415         }
1416
1417         var newU = rankSets[prefRank];
1418         if (newU === undefined) {
1419           newU = rankSets[prefRank] = g.addNode(null, { originalNodes: [] });
1420           g.parent(newU, sg);
1421         }
1422
1423         redirectInEdges(g, u, newU, prefRank === 'min');
1424         redirectOutEdges(g, u, newU, prefRank === 'max');
1425
1426         // Save original node and remove it from reduced graph
1427         g.node(newU).originalNodes.push({ u: u, value: value, parent: sg });
1428         g.delNode(u);
1429       }
1430     });
1431
1432     addLightEdgesFromMinNode(g, sg, rankSets.min);
1433     addLightEdgesToMaxNode(g, sg, rankSets.max);
1434   }
1435
1436   dfs(null);
1437 };
1438
1439 function checkSupportedPrefRank(prefRank) {
1440   if (prefRank !== 'min' && prefRank !== 'max' && prefRank.indexOf('same_') !== 0) {
1441     console.error('Unsupported rank type: ' + prefRank);
1442     return false;
1443   }
1444   return true;
1445 }
1446
1447 function redirectInEdges(g, u, newU, reverse) {
1448   g.inEdges(u).forEach(function(e) {
1449     var origValue = g.edge(e),
1450         value;
1451     if (origValue.originalEdge) {
1452       value = origValue;
1453     } else {
1454       value =  {
1455         originalEdge: { e: e, u: g.source(e), v: g.target(e), value: origValue },
1456         minLen: g.edge(e).minLen
1457       };
1458     }
1459
1460     // Do not reverse edges for self-loops.
1461     if (origValue.selfLoop) {
1462       reverse = false;
1463     }
1464
1465     if (reverse) {
1466       // Ensure that all edges to min are reversed
1467       g.addEdge(null, newU, g.source(e), value);
1468       value.reversed = true;
1469     } else {
1470       g.addEdge(null, g.source(e), newU, value);
1471     }
1472   });
1473 }
1474
1475 function redirectOutEdges(g, u, newU, reverse) {
1476   g.outEdges(u).forEach(function(e) {
1477     var origValue = g.edge(e),
1478         value;
1479     if (origValue.originalEdge) {
1480       value = origValue;
1481     } else {
1482       value =  {
1483         originalEdge: { e: e, u: g.source(e), v: g.target(e), value: origValue },
1484         minLen: g.edge(e).minLen
1485       };
1486     }
1487
1488     // Do not reverse edges for self-loops.
1489     if (origValue.selfLoop) {
1490       reverse = false;
1491     }
1492
1493     if (reverse) {
1494       // Ensure that all edges from max are reversed
1495       g.addEdge(null, g.target(e), newU, value);
1496       value.reversed = true;
1497     } else {
1498       g.addEdge(null, newU, g.target(e), value);
1499     }
1500   });
1501 }
1502
1503 function addLightEdgesFromMinNode(g, sg, minNode) {
1504   if (minNode !== undefined) {
1505     g.children(sg).forEach(function(u) {
1506       // The dummy check ensures we don't add an edge if the node is involved
1507       // in a self loop or sideways edge.
1508       if (u !== minNode && !g.outEdges(minNode, u).length && !g.node(u).dummy) {
1509         g.addEdge(null, minNode, u, { minLen: 0 });
1510       }
1511     });
1512   }
1513 }
1514
1515 function addLightEdgesToMaxNode(g, sg, maxNode) {
1516   if (maxNode !== undefined) {
1517     g.children(sg).forEach(function(u) {
1518       // The dummy check ensures we don't add an edge if the node is involved
1519       // in a self loop or sideways edge.
1520       if (u !== maxNode && !g.outEdges(u, maxNode).length && !g.node(u).dummy) {
1521         g.addEdge(null, u, maxNode, { minLen: 0 });
1522       }
1523     });
1524   }
1525 }
1526
1527 /*
1528  * This function "relaxes" the constraints applied previously by the "apply"
1529  * function. It expands any nodes that were collapsed and assigns the rank of
1530  * the collapsed node to each of the expanded nodes. It also restores the
1531  * original edges and removes any dummy edges pointing at the collapsed nodes.
1532  *
1533  * Note that the process of removing collapsed nodes also removes dummy edges
1534  * automatically.
1535  */
1536 exports.relax = function(g) {
1537   // Save original edges
1538   var originalEdges = [];
1539   g.eachEdge(function(e, u, v, value) {
1540     var originalEdge = value.originalEdge;
1541     if (originalEdge) {
1542       originalEdges.push(originalEdge);
1543     }
1544   });
1545
1546   // Expand collapsed nodes
1547   g.eachNode(function(u, value) {
1548     var originalNodes = value.originalNodes;
1549     if (originalNodes) {
1550       originalNodes.forEach(function(originalNode) {
1551         originalNode.value.rank = value.rank;
1552         g.addNode(originalNode.u, originalNode.value);
1553         g.parent(originalNode.u, originalNode.parent);
1554       });
1555       g.delNode(u);
1556     }
1557   });
1558
1559   // Restore original edges
1560   originalEdges.forEach(function(edge) {
1561     g.addEdge(edge.e, edge.u, edge.v, edge.value);
1562   });
1563 };
1564
1565 },{}],13:[function(require,module,exports){
1566 /* jshint -W079 */
1567 var Set = require('cp-data').Set,
1568 /* jshint +W079 */
1569     Digraph = require('graphlib').Digraph,
1570     util = require('../util');
1571
1572 module.exports = feasibleTree;
1573
1574 /*
1575  * Given an acyclic graph with each node assigned a `rank` attribute, this
1576  * function constructs and returns a spanning tree. This function may reduce
1577  * the length of some edges from the initial rank assignment while maintaining
1578  * the `minLen` specified by each edge.
1579  *
1580  * Prerequisites:
1581  *
1582  * * The input graph is acyclic
1583  * * Each node in the input graph has an assigned `rank` attribute
1584  * * Each edge in the input graph has an assigned `minLen` attribute
1585  *
1586  * Outputs:
1587  *
1588  * A feasible spanning tree for the input graph (i.e. a spanning tree that
1589  * respects each graph edge's `minLen` attribute) represented as a Digraph with
1590  * a `root` attribute on graph.
1591  *
1592  * Nodes have the same id and value as that in the input graph.
1593  *
1594  * Edges in the tree have arbitrarily assigned ids. The attributes for edges
1595  * include `reversed`. `reversed` indicates that the edge is a
1596  * back edge in the input graph.
1597  */
1598 function feasibleTree(g) {
1599   var remaining = new Set(g.nodes()),
1600       tree = new Digraph();
1601
1602   if (remaining.size() === 1) {
1603     var root = g.nodes()[0];
1604     tree.addNode(root, {});
1605     tree.graph({ root: root });
1606     return tree;
1607   }
1608
1609   function addTightEdges(v) {
1610     var continueToScan = true;
1611     g.predecessors(v).forEach(function(u) {
1612       if (remaining.has(u) && !slack(g, u, v)) {
1613         if (remaining.has(v)) {
1614           tree.addNode(v, {});
1615           remaining.remove(v);
1616           tree.graph({ root: v });
1617         }
1618
1619         tree.addNode(u, {});
1620         tree.addEdge(null, u, v, { reversed: true });
1621         remaining.remove(u);
1622         addTightEdges(u);
1623         continueToScan = false;
1624       }
1625     });
1626
1627     g.successors(v).forEach(function(w)  {
1628       if (remaining.has(w) && !slack(g, v, w)) {
1629         if (remaining.has(v)) {
1630           tree.addNode(v, {});
1631           remaining.remove(v);
1632           tree.graph({ root: v });
1633         }
1634
1635         tree.addNode(w, {});
1636         tree.addEdge(null, v, w, {});
1637         remaining.remove(w);
1638         addTightEdges(w);
1639         continueToScan = false;
1640       }
1641     });
1642     return continueToScan;
1643   }
1644
1645   function createTightEdge() {
1646     var minSlack = Number.MAX_VALUE;
1647     remaining.keys().forEach(function(v) {
1648       g.predecessors(v).forEach(function(u) {
1649         if (!remaining.has(u)) {
1650           var edgeSlack = slack(g, u, v);
1651           if (Math.abs(edgeSlack) < Math.abs(minSlack)) {
1652             minSlack = -edgeSlack;
1653           }
1654         }
1655       });
1656
1657       g.successors(v).forEach(function(w) {
1658         if (!remaining.has(w)) {
1659           var edgeSlack = slack(g, v, w);
1660           if (Math.abs(edgeSlack) < Math.abs(minSlack)) {
1661             minSlack = edgeSlack;
1662           }
1663         }
1664       });
1665     });
1666
1667     tree.eachNode(function(u) { g.node(u).rank -= minSlack; });
1668   }
1669
1670   while (remaining.size()) {
1671     var nodesToSearch = !tree.order() ? remaining.keys() : tree.nodes();
1672     for (var i = 0, il = nodesToSearch.length;
1673          i < il && addTightEdges(nodesToSearch[i]);
1674          ++i);
1675     if (remaining.size()) {
1676       createTightEdge();
1677     }
1678   }
1679
1680   return tree;
1681 }
1682
1683 function slack(g, u, v) {
1684   var rankDiff = g.node(v).rank - g.node(u).rank;
1685   var maxMinLen = util.max(g.outEdges(u, v)
1686                             .map(function(e) { return g.edge(e).minLen; }));
1687   return rankDiff - maxMinLen;
1688 }
1689
1690 },{"../util":17,"cp-data":19,"graphlib":24}],14:[function(require,module,exports){
1691 var util = require('../util'),
1692     topsort = require('graphlib').alg.topsort;
1693
1694 module.exports = initRank;
1695
1696 /*
1697  * Assigns a `rank` attribute to each node in the input graph and ensures that
1698  * this rank respects the `minLen` attribute of incident edges.
1699  *
1700  * Prerequisites:
1701  *
1702  *  * The input graph must be acyclic
1703  *  * Each edge in the input graph must have an assigned 'minLen' attribute
1704  */
1705 function initRank(g) {
1706   var sorted = topsort(g);
1707
1708   sorted.forEach(function(u) {
1709     var inEdges = g.inEdges(u);
1710     if (inEdges.length === 0) {
1711       g.node(u).rank = 0;
1712       return;
1713     }
1714
1715     var minLens = inEdges.map(function(e) {
1716       return g.node(g.source(e)).rank + g.edge(e).minLen;
1717     });
1718     g.node(u).rank = util.max(minLens);
1719   });
1720 }
1721
1722 },{"../util":17,"graphlib":24}],15:[function(require,module,exports){
1723 module.exports = {
1724   slack: slack
1725 };
1726
1727 /*
1728  * A helper to calculate the slack between two nodes (`u` and `v`) given a
1729  * `minLen` constraint. The slack represents how much the distance between `u`
1730  * and `v` could shrink while maintaining the `minLen` constraint. If the value
1731  * is negative then the constraint is currently violated.
1732  *
1733   This function requires that `u` and `v` are in `graph` and they both have a
1734   `rank` attribute.
1735  */
1736 function slack(graph, u, v, minLen) {
1737   return Math.abs(graph.node(u).rank - graph.node(v).rank) - minLen;
1738 }
1739
1740 },{}],16:[function(require,module,exports){
1741 var util = require('../util'),
1742     rankUtil = require('./rankUtil');
1743
1744 module.exports = simplex;
1745
1746 function simplex(graph, spanningTree) {
1747   // The network simplex algorithm repeatedly replaces edges of
1748   // the spanning tree with negative cut values until no such
1749   // edge exists.
1750   initCutValues(graph, spanningTree);
1751   while (true) {
1752     var e = leaveEdge(spanningTree);
1753     if (e === null) break;
1754     var f = enterEdge(graph, spanningTree, e);
1755     exchange(graph, spanningTree, e, f);
1756   }
1757 }
1758
1759 /*
1760  * Set the cut values of edges in the spanning tree by a depth-first
1761  * postorder traversal.  The cut value corresponds to the cost, in
1762  * terms of a ranking's edge length sum, of lengthening an edge.
1763  * Negative cut values typically indicate edges that would yield a
1764  * smaller edge length sum if they were lengthened.
1765  */
1766 function initCutValues(graph, spanningTree) {
1767   computeLowLim(spanningTree);
1768
1769   spanningTree.eachEdge(function(id, u, v, treeValue) {
1770     treeValue.cutValue = 0;
1771   });
1772
1773   // Propagate cut values up the tree.
1774   function dfs(n) {
1775     var children = spanningTree.successors(n);
1776     for (var c in children) {
1777       var child = children[c];
1778       dfs(child);
1779     }
1780     if (n !== spanningTree.graph().root) {
1781       setCutValue(graph, spanningTree, n);
1782     }
1783   }
1784   dfs(spanningTree.graph().root);
1785 }
1786
1787 /*
1788  * Perform a DFS postorder traversal, labeling each node v with
1789  * its traversal order 'lim(v)' and the minimum traversal number
1790  * of any of its descendants 'low(v)'.  This provides an efficient
1791  * way to test whether u is an ancestor of v since
1792  * low(u) <= lim(v) <= lim(u) if and only if u is an ancestor.
1793  */
1794 function computeLowLim(tree) {
1795   var postOrderNum = 0;
1796
1797   function dfs(n) {
1798     var children = tree.successors(n);
1799     var low = postOrderNum;
1800     for (var c in children) {
1801       var child = children[c];
1802       dfs(child);
1803       low = Math.min(low, tree.node(child).low);
1804     }
1805     tree.node(n).low = low;
1806     tree.node(n).lim = postOrderNum++;
1807   }
1808
1809   dfs(tree.graph().root);
1810 }
1811
1812 /*
1813  * To compute the cut value of the edge parent -> child, we consider
1814  * it and any other graph edges to or from the child.
1815  *          parent
1816  *             |
1817  *           child
1818  *          /      \
1819  *         u        v
1820  */
1821 function setCutValue(graph, tree, child) {
1822   var parentEdge = tree.inEdges(child)[0];
1823
1824   // List of child's children in the spanning tree.
1825   var grandchildren = [];
1826   var grandchildEdges = tree.outEdges(child);
1827   for (var gce in grandchildEdges) {
1828     grandchildren.push(tree.target(grandchildEdges[gce]));
1829   }
1830
1831   var cutValue = 0;
1832
1833   // TODO: Replace unit increment/decrement with edge weights.
1834   var E = 0;    // Edges from child to grandchild's subtree.
1835   var F = 0;    // Edges to child from grandchild's subtree.
1836   var G = 0;    // Edges from child to nodes outside of child's subtree.
1837   var H = 0;    // Edges from nodes outside of child's subtree to child.
1838
1839   // Consider all graph edges from child.
1840   var outEdges = graph.outEdges(child);
1841   var gc;
1842   for (var oe in outEdges) {
1843     var succ = graph.target(outEdges[oe]);
1844     for (gc in grandchildren) {
1845       if (inSubtree(tree, succ, grandchildren[gc])) {
1846         E++;
1847       }
1848     }
1849     if (!inSubtree(tree, succ, child)) {
1850       G++;
1851     }
1852   }
1853
1854   // Consider all graph edges to child.
1855   var inEdges = graph.inEdges(child);
1856   for (var ie in inEdges) {
1857     var pred = graph.source(inEdges[ie]);
1858     for (gc in grandchildren) {
1859       if (inSubtree(tree, pred, grandchildren[gc])) {
1860         F++;
1861       }
1862     }
1863     if (!inSubtree(tree, pred, child)) {
1864       H++;
1865     }
1866   }
1867
1868   // Contributions depend on the alignment of the parent -> child edge
1869   // and the child -> u or v edges.
1870   var grandchildCutSum = 0;
1871   for (gc in grandchildren) {
1872     var cv = tree.edge(grandchildEdges[gc]).cutValue;
1873     if (!tree.edge(grandchildEdges[gc]).reversed) {
1874       grandchildCutSum += cv;
1875     } else {
1876       grandchildCutSum -= cv;
1877     }
1878   }
1879
1880   if (!tree.edge(parentEdge).reversed) {
1881     cutValue += grandchildCutSum - E + F - G + H;
1882   } else {
1883     cutValue -= grandchildCutSum - E + F - G + H;
1884   }
1885
1886   tree.edge(parentEdge).cutValue = cutValue;
1887 }
1888
1889 /*
1890  * Return whether n is a node in the subtree with the given
1891  * root.
1892  */
1893 function inSubtree(tree, n, root) {
1894   return (tree.node(root).low <= tree.node(n).lim &&
1895           tree.node(n).lim <= tree.node(root).lim);
1896 }
1897
1898 /*
1899  * Return an edge from the tree with a negative cut value, or null if there
1900  * is none.
1901  */
1902 function leaveEdge(tree) {
1903   var edges = tree.edges();
1904   for (var n in edges) {
1905     var e = edges[n];
1906     var treeValue = tree.edge(e);
1907     if (treeValue.cutValue < 0) {
1908       return e;
1909     }
1910   }
1911   return null;
1912 }
1913
1914 /*
1915  * The edge e should be an edge in the tree, with an underlying edge
1916  * in the graph, with a negative cut value.  Of the two nodes incident
1917  * on the edge, take the lower one.  enterEdge returns an edge with
1918  * minimum slack going from outside of that node's subtree to inside
1919  * of that node's subtree.
1920  */
1921 function enterEdge(graph, tree, e) {
1922   var source = tree.source(e);
1923   var target = tree.target(e);
1924   var lower = tree.node(target).lim < tree.node(source).lim ? target : source;
1925
1926   // Is the tree edge aligned with the graph edge?
1927   var aligned = !tree.edge(e).reversed;
1928
1929   var minSlack = Number.POSITIVE_INFINITY;
1930   var minSlackEdge;
1931   if (aligned) {
1932     graph.eachEdge(function(id, u, v, value) {
1933       if (id !== e && inSubtree(tree, u, lower) && !inSubtree(tree, v, lower)) {
1934         var slack = rankUtil.slack(graph, u, v, value.minLen);
1935         if (slack < minSlack) {
1936           minSlack = slack;
1937           minSlackEdge = id;
1938         }
1939       }
1940     });
1941   } else {
1942     graph.eachEdge(function(id, u, v, value) {
1943       if (id !== e && !inSubtree(tree, u, lower) && inSubtree(tree, v, lower)) {
1944         var slack = rankUtil.slack(graph, u, v, value.minLen);
1945         if (slack < minSlack) {
1946           minSlack = slack;
1947           minSlackEdge = id;
1948         }
1949       }
1950     });
1951   }
1952
1953   if (minSlackEdge === undefined) {
1954     var outside = [];
1955     var inside = [];
1956     graph.eachNode(function(id) {
1957       if (!inSubtree(tree, id, lower)) {
1958         outside.push(id);
1959       } else {
1960         inside.push(id);
1961       }
1962     });
1963     throw new Error('No edge found from outside of tree to inside');
1964   }
1965
1966   return minSlackEdge;
1967 }
1968
1969 /*
1970  * Replace edge e with edge f in the tree, recalculating the tree root,
1971  * the nodes' low and lim properties and the edges' cut values.
1972  */
1973 function exchange(graph, tree, e, f) {
1974   tree.delEdge(e);
1975   var source = graph.source(f);
1976   var target = graph.target(f);
1977
1978   // Redirect edges so that target is the root of its subtree.
1979   function redirect(v) {
1980     var edges = tree.inEdges(v);
1981     for (var i in edges) {
1982       var e = edges[i];
1983       var u = tree.source(e);
1984       var value = tree.edge(e);
1985       redirect(u);
1986       tree.delEdge(e);
1987       value.reversed = !value.reversed;
1988       tree.addEdge(e, v, u, value);
1989     }
1990   }
1991
1992   redirect(target);
1993
1994   var root = source;
1995   var edges = tree.inEdges(root);
1996   while (edges.length > 0) {
1997     root = tree.source(edges[0]);
1998     edges = tree.inEdges(root);
1999   }
2000
2001   tree.graph().root = root;
2002
2003   tree.addEdge(null, source, target, {cutValue: 0});
2004
2005   initCutValues(graph, tree);
2006
2007   adjustRanks(graph, tree);
2008 }
2009
2010 /*
2011  * Reset the ranks of all nodes based on the current spanning tree.
2012  * The rank of the tree's root remains unchanged, while all other
2013  * nodes are set to the sum of minimum length constraints along
2014  * the path from the root.
2015  */
2016 function adjustRanks(graph, tree) {
2017   function dfs(p) {
2018     var children = tree.successors(p);
2019     children.forEach(function(c) {
2020       var minLen = minimumLength(graph, p, c);
2021       graph.node(c).rank = graph.node(p).rank + minLen;
2022       dfs(c);
2023     });
2024   }
2025
2026   dfs(tree.graph().root);
2027 }
2028
2029 /*
2030  * If u and v are connected by some edges in the graph, return the
2031  * minimum length of those edges, as a positive number if v succeeds
2032  * u and as a negative number if v precedes u.
2033  */
2034 function minimumLength(graph, u, v) {
2035   var outEdges = graph.outEdges(u, v);
2036   if (outEdges.length > 0) {
2037     return util.max(outEdges.map(function(e) {
2038       return graph.edge(e).minLen;
2039     }));
2040   }
2041
2042   var inEdges = graph.inEdges(u, v);
2043   if (inEdges.length > 0) {
2044     return -util.max(inEdges.map(function(e) {
2045       return graph.edge(e).minLen;
2046     }));
2047   }
2048 }
2049
2050 },{"../util":17,"./rankUtil":15}],17:[function(require,module,exports){
2051 /*
2052  * Returns the smallest value in the array.
2053  */
2054 exports.min = function(values) {
2055   return Math.min.apply(Math, values);
2056 };
2057
2058 /*
2059  * Returns the largest value in the array.
2060  */
2061 exports.max = function(values) {
2062   return Math.max.apply(Math, values);
2063 };
2064
2065 /*
2066  * Returns `true` only if `f(x)` is `true` for all `x` in `xs`. Otherwise
2067  * returns `false`. This function will return immediately if it finds a
2068  * case where `f(x)` does not hold.
2069  */
2070 exports.all = function(xs, f) {
2071   for (var i = 0; i < xs.length; ++i) {
2072     if (!f(xs[i])) {
2073       return false;
2074     }
2075   }
2076   return true;
2077 };
2078
2079 /*
2080  * Accumulates the sum of elements in the given array using the `+` operator.
2081  */
2082 exports.sum = function(values) {
2083   return values.reduce(function(acc, x) { return acc + x; }, 0);
2084 };
2085
2086 /*
2087  * Returns an array of all values in the given object.
2088  */
2089 exports.values = function(obj) {
2090   return Object.keys(obj).map(function(k) { return obj[k]; });
2091 };
2092
2093 exports.shuffle = function(array) {
2094   for (i = array.length - 1; i > 0; --i) {
2095     var j = Math.floor(Math.random() * (i + 1));
2096     var aj = array[j];
2097     array[j] = array[i];
2098     array[i] = aj;
2099   }
2100 };
2101
2102 exports.propertyAccessor = function(self, config, field, setHook) {
2103   return function(x) {
2104     if (!arguments.length) return config[field];
2105     config[field] = x;
2106     if (setHook) setHook(x);
2107     return self;
2108   };
2109 };
2110
2111 /*
2112  * Given a layered, directed graph with `rank` and `order` node attributes,
2113  * this function returns an array of ordered ranks. Each rank contains an array
2114  * of the ids of the nodes in that rank in the order specified by the `order`
2115  * attribute.
2116  */
2117 exports.ordering = function(g) {
2118   var ordering = [];
2119   g.eachNode(function(u, value) {
2120     var rank = ordering[value.rank] || (ordering[value.rank] = []);
2121     rank[value.order] = u;
2122   });
2123   return ordering;
2124 };
2125
2126 /*
2127  * A filter that can be used with `filterNodes` to get a graph that only
2128  * includes nodes that do not contain others nodes.
2129  */
2130 exports.filterNonSubgraphs = function(g) {
2131   return function(u) {
2132     return g.children(u).length === 0;
2133   };
2134 };
2135
2136 /*
2137  * Returns a new function that wraps `func` with a timer. The wrapper logs the
2138  * time it takes to execute the function.
2139  *
2140  * The timer will be enabled provided `log.level >= 1`.
2141  */
2142 function time(name, func) {
2143   return function() {
2144     var start = new Date().getTime();
2145     try {
2146       return func.apply(null, arguments);
2147     } finally {
2148       log(1, name + ' time: ' + (new Date().getTime() - start) + 'ms');
2149     }
2150   };
2151 }
2152 time.enabled = false;
2153
2154 exports.time = time;
2155
2156 /*
2157  * A global logger with the specification `log(level, message, ...)` that
2158  * will log a message to the console if `log.level >= level`.
2159  */
2160 function log(level) {
2161   if (log.level >= level) {
2162     console.log.apply(console, Array.prototype.slice.call(arguments, 1));
2163   }
2164 }
2165 log.level = 0;
2166
2167 exports.log = log;
2168
2169 },{}],18:[function(require,module,exports){
2170 module.exports = '0.4.5';
2171
2172 },{}],19:[function(require,module,exports){
2173 exports.Set = require('./lib/Set');
2174 exports.PriorityQueue = require('./lib/PriorityQueue');
2175 exports.version = require('./lib/version');
2176
2177 },{"./lib/PriorityQueue":20,"./lib/Set":21,"./lib/version":23}],20:[function(require,module,exports){
2178 module.exports = PriorityQueue;
2179
2180 /**
2181  * A min-priority queue data structure. This algorithm is derived from Cormen,
2182  * et al., "Introduction to Algorithms". The basic idea of a min-priority
2183  * queue is that you can efficiently (in O(1) time) get the smallest key in
2184  * the queue. Adding and removing elements takes O(log n) time. A key can
2185  * have its priority decreased in O(log n) time.
2186  */
2187 function PriorityQueue() {
2188   this._arr = [];
2189   this._keyIndices = {};
2190 }
2191
2192 /**
2193  * Returns the number of elements in the queue. Takes `O(1)` time.
2194  */
2195 PriorityQueue.prototype.size = function() {
2196   return this._arr.length;
2197 };
2198
2199 /**
2200  * Returns the keys that are in the queue. Takes `O(n)` time.
2201  */
2202 PriorityQueue.prototype.keys = function() {
2203   return this._arr.map(function(x) { return x.key; });
2204 };
2205
2206 /**
2207  * Returns `true` if **key** is in the queue and `false` if not.
2208  */
2209 PriorityQueue.prototype.has = function(key) {
2210   return key in this._keyIndices;
2211 };
2212
2213 /**
2214  * Returns the priority for **key**. If **key** is not present in the queue
2215  * then this function returns `undefined`. Takes `O(1)` time.
2216  *
2217  * @param {Object} key
2218  */
2219 PriorityQueue.prototype.priority = function(key) {
2220   var index = this._keyIndices[key];
2221   if (index !== undefined) {
2222     return this._arr[index].priority;
2223   }
2224 };
2225
2226 /**
2227  * Returns the key for the minimum element in this queue. If the queue is
2228  * empty this function throws an Error. Takes `O(1)` time.
2229  */
2230 PriorityQueue.prototype.min = function() {
2231   if (this.size() === 0) {
2232     throw new Error("Queue underflow");
2233   }
2234   return this._arr[0].key;
2235 };
2236
2237 /**
2238  * Inserts a new key into the priority queue. If the key already exists in
2239  * the queue this function returns `false`; otherwise it will return `true`.
2240  * Takes `O(n)` time.
2241  *
2242  * @param {Object} key the key to add
2243  * @param {Number} priority the initial priority for the key
2244  */
2245 PriorityQueue.prototype.add = function(key, priority) {
2246   var keyIndices = this._keyIndices;
2247   if (!(key in keyIndices)) {
2248     var arr = this._arr;
2249     var index = arr.length;
2250     keyIndices[key] = index;
2251     arr.push({key: key, priority: priority});
2252     this._decrease(index);
2253     return true;
2254   }
2255   return false;
2256 };
2257
2258 /**
2259  * Removes and returns the smallest key in the queue. Takes `O(log n)` time.
2260  */
2261 PriorityQueue.prototype.removeMin = function() {
2262   this._swap(0, this._arr.length - 1);
2263   var min = this._arr.pop();
2264   delete this._keyIndices[min.key];
2265   this._heapify(0);
2266   return min.key;
2267 };
2268
2269 /**
2270  * Decreases the priority for **key** to **priority**. If the new priority is
2271  * greater than the previous priority, this function will throw an Error.
2272  *
2273  * @param {Object} key the key for which to raise priority
2274  * @param {Number} priority the new priority for the key
2275  */
2276 PriorityQueue.prototype.decrease = function(key, priority) {
2277   var index = this._keyIndices[key];
2278   if (priority > this._arr[index].priority) {
2279     throw new Error("New priority is greater than current priority. " +
2280         "Key: " + key + " Old: " + this._arr[index].priority + " New: " + priority);
2281   }
2282   this._arr[index].priority = priority;
2283   this._decrease(index);
2284 };
2285
2286 PriorityQueue.prototype._heapify = function(i) {
2287   var arr = this._arr;
2288   var l = 2 * i,
2289       r = l + 1,
2290       largest = i;
2291   if (l < arr.length) {
2292     largest = arr[l].priority < arr[largest].priority ? l : largest;
2293     if (r < arr.length) {
2294       largest = arr[r].priority < arr[largest].priority ? r : largest;
2295     }
2296     if (largest !== i) {
2297       this._swap(i, largest);
2298       this._heapify(largest);
2299     }
2300   }
2301 };
2302
2303 PriorityQueue.prototype._decrease = function(index) {
2304   var arr = this._arr;
2305   var priority = arr[index].priority;
2306   var parent;
2307   while (index !== 0) {
2308     parent = index >> 1;
2309     if (arr[parent].priority < priority) {
2310       break;
2311     }
2312     this._swap(index, parent);
2313     index = parent;
2314   }
2315 };
2316
2317 PriorityQueue.prototype._swap = function(i, j) {
2318   var arr = this._arr;
2319   var keyIndices = this._keyIndices;
2320   var origArrI = arr[i];
2321   var origArrJ = arr[j];
2322   arr[i] = origArrJ;
2323   arr[j] = origArrI;
2324   keyIndices[origArrJ.key] = i;
2325   keyIndices[origArrI.key] = j;
2326 };
2327
2328 },{}],21:[function(require,module,exports){
2329 var util = require('./util');
2330
2331 module.exports = Set;
2332
2333 /**
2334  * Constructs a new Set with an optional set of `initialKeys`.
2335  *
2336  * It is important to note that keys are coerced to String for most purposes
2337  * with this object, similar to the behavior of JavaScript's Object. For
2338  * example, the following will add only one key:
2339  *
2340  *     var s = new Set();
2341  *     s.add(1);
2342  *     s.add("1");
2343  *
2344  * However, the type of the key is preserved internally so that `keys` returns
2345  * the original key set uncoerced. For the above example, `keys` would return
2346  * `[1]`.
2347  */
2348 function Set(initialKeys) {
2349   this._size = 0;
2350   this._keys = {};
2351
2352   if (initialKeys) {
2353     for (var i = 0, il = initialKeys.length; i < il; ++i) {
2354       this.add(initialKeys[i]);
2355     }
2356   }
2357 }
2358
2359 /**
2360  * Returns a new Set that represents the set intersection of the array of given
2361  * sets.
2362  */
2363 Set.intersect = function(sets) {
2364   if (sets.length === 0) {
2365     return new Set();
2366   }
2367
2368   var result = new Set(!util.isArray(sets[0]) ? sets[0].keys() : sets[0]);
2369   for (var i = 1, il = sets.length; i < il; ++i) {
2370     var resultKeys = result.keys(),
2371         other = !util.isArray(sets[i]) ? sets[i] : new Set(sets[i]);
2372     for (var j = 0, jl = resultKeys.length; j < jl; ++j) {
2373       var key = resultKeys[j];
2374       if (!other.has(key)) {
2375         result.remove(key);
2376       }
2377     }
2378   }
2379
2380   return result;
2381 };
2382
2383 /**
2384  * Returns a new Set that represents the set union of the array of given sets.
2385  */
2386 Set.union = function(sets) {
2387   var totalElems = util.reduce(sets, function(lhs, rhs) {
2388     return lhs + (rhs.size ? rhs.size() : rhs.length);
2389   }, 0);
2390   var arr = new Array(totalElems);
2391
2392   var k = 0;
2393   for (var i = 0, il = sets.length; i < il; ++i) {
2394     var cur = sets[i],
2395         keys = !util.isArray(cur) ? cur.keys() : cur;
2396     for (var j = 0, jl = keys.length; j < jl; ++j) {
2397       arr[k++] = keys[j];
2398     }
2399   }
2400
2401   return new Set(arr);
2402 };
2403
2404 /**
2405  * Returns the size of this set in `O(1)` time.
2406  */
2407 Set.prototype.size = function() {
2408   return this._size;
2409 };
2410
2411 /**
2412  * Returns the keys in this set. Takes `O(n)` time.
2413  */
2414 Set.prototype.keys = function() {
2415   return values(this._keys);
2416 };
2417
2418 /**
2419  * Tests if a key is present in this Set. Returns `true` if it is and `false`
2420  * if not. Takes `O(1)` time.
2421  */
2422 Set.prototype.has = function(key) {
2423   return key in this._keys;
2424 };
2425
2426 /**
2427  * Adds a new key to this Set if it is not already present. Returns `true` if
2428  * the key was added and `false` if it was already present. Takes `O(1)` time.
2429  */
2430 Set.prototype.add = function(key) {
2431   if (!(key in this._keys)) {
2432     this._keys[key] = key;
2433     ++this._size;
2434     return true;
2435   }
2436   return false;
2437 };
2438
2439 /**
2440  * Removes a key from this Set. If the key was removed this function returns
2441  * `true`. If not, it returns `false`. Takes `O(1)` time.
2442  */
2443 Set.prototype.remove = function(key) {
2444   if (key in this._keys) {
2445     delete this._keys[key];
2446     --this._size;
2447     return true;
2448   }
2449   return false;
2450 };
2451
2452 /*
2453  * Returns an array of all values for properties of **o**.
2454  */
2455 function values(o) {
2456   var ks = Object.keys(o),
2457       len = ks.length,
2458       result = new Array(len),
2459       i;
2460   for (i = 0; i < len; ++i) {
2461     result[i] = o[ks[i]];
2462   }
2463   return result;
2464 }
2465
2466 },{"./util":22}],22:[function(require,module,exports){
2467 /*
2468  * This polyfill comes from
2469  * https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/isArray
2470  */
2471 if(!Array.isArray) {
2472   exports.isArray = function (vArg) {
2473     return Object.prototype.toString.call(vArg) === '[object Array]';
2474   };
2475 } else {
2476   exports.isArray = Array.isArray;
2477 }
2478
2479 /*
2480  * Slightly adapted polyfill from
2481  * https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/Reduce
2482  */
2483 if ('function' !== typeof Array.prototype.reduce) {
2484   exports.reduce = function(array, callback, opt_initialValue) {
2485     'use strict';
2486     if (null === array || 'undefined' === typeof array) {
2487       // At the moment all modern browsers, that support strict mode, have
2488       // native implementation of Array.prototype.reduce. For instance, IE8
2489       // does not support strict mode, so this check is actually useless.
2490       throw new TypeError(
2491           'Array.prototype.reduce called on null or undefined');
2492     }
2493     if ('function' !== typeof callback) {
2494       throw new TypeError(callback + ' is not a function');
2495     }
2496     var index, value,
2497         length = array.length >>> 0,
2498         isValueSet = false;
2499     if (1 < arguments.length) {
2500       value = opt_initialValue;
2501       isValueSet = true;
2502     }
2503     for (index = 0; length > index; ++index) {
2504       if (array.hasOwnProperty(index)) {
2505         if (isValueSet) {
2506           value = callback(value, array[index], index, array);
2507         }
2508         else {
2509           value = array[index];
2510           isValueSet = true;
2511         }
2512       }
2513     }
2514     if (!isValueSet) {
2515       throw new TypeError('Reduce of empty array with no initial value');
2516     }
2517     return value;
2518   };
2519 } else {
2520   exports.reduce = function(array, callback, opt_initialValue) {
2521     return array.reduce(callback, opt_initialValue);
2522   };
2523 }
2524
2525 },{}],23:[function(require,module,exports){
2526 module.exports = '1.1.3';
2527
2528 },{}],24:[function(require,module,exports){
2529 exports.Graph = require("./lib/Graph");
2530 exports.Digraph = require("./lib/Digraph");
2531 exports.CGraph = require("./lib/CGraph");
2532 exports.CDigraph = require("./lib/CDigraph");
2533 require("./lib/graph-converters");
2534
2535 exports.alg = {
2536   isAcyclic: require("./lib/alg/isAcyclic"),
2537   components: require("./lib/alg/components"),
2538   dijkstra: require("./lib/alg/dijkstra"),
2539   dijkstraAll: require("./lib/alg/dijkstraAll"),
2540   findCycles: require("./lib/alg/findCycles"),
2541   floydWarshall: require("./lib/alg/floydWarshall"),
2542   postorder: require("./lib/alg/postorder"),
2543   preorder: require("./lib/alg/preorder"),
2544   prim: require("./lib/alg/prim"),
2545   tarjan: require("./lib/alg/tarjan"),
2546   topsort: require("./lib/alg/topsort")
2547 };
2548
2549 exports.converter = {
2550   json: require("./lib/converter/json.js")
2551 };
2552
2553 var filter = require("./lib/filter");
2554 exports.filter = {
2555   all: filter.all,
2556   nodesFromList: filter.nodesFromList
2557 };
2558
2559 exports.version = require("./lib/version");
2560
2561 },{"./lib/CDigraph":26,"./lib/CGraph":27,"./lib/Digraph":28,"./lib/Graph":29,"./lib/alg/components":30,"./lib/alg/dijkstra":31,"./lib/alg/dijkstraAll":32,"./lib/alg/findCycles":33,"./lib/alg/floydWarshall":34,"./lib/alg/isAcyclic":35,"./lib/alg/postorder":36,"./lib/alg/preorder":37,"./lib/alg/prim":38,"./lib/alg/tarjan":39,"./lib/alg/topsort":40,"./lib/converter/json.js":42,"./lib/filter":43,"./lib/graph-converters":44,"./lib/version":46}],25:[function(require,module,exports){
2562 /* jshint -W079 */
2563 var Set = require("cp-data").Set;
2564 /* jshint +W079 */
2565
2566 module.exports = BaseGraph;
2567
2568 function BaseGraph() {
2569   // The value assigned to the graph itself.
2570   this._value = undefined;
2571
2572   // Map of node id -> { id, value }
2573   this._nodes = {};
2574
2575   // Map of edge id -> { id, u, v, value }
2576   this._edges = {};
2577
2578   // Used to generate a unique id in the graph
2579   this._nextId = 0;
2580 }
2581
2582 // Number of nodes
2583 BaseGraph.prototype.order = function() {
2584   return Object.keys(this._nodes).length;
2585 };
2586
2587 // Number of edges
2588 BaseGraph.prototype.size = function() {
2589   return Object.keys(this._edges).length;
2590 };
2591
2592 // Accessor for graph level value
2593 BaseGraph.prototype.graph = function(value) {
2594   if (arguments.length === 0) {
2595     return this._value;
2596   }
2597   this._value = value;
2598 };
2599
2600 BaseGraph.prototype.hasNode = function(u) {
2601   return u in this._nodes;
2602 };
2603
2604 BaseGraph.prototype.node = function(u, value) {
2605   var node = this._strictGetNode(u);
2606   if (arguments.length === 1) {
2607     return node.value;
2608   }
2609   node.value = value;
2610 };
2611
2612 BaseGraph.prototype.nodes = function() {
2613   var nodes = [];
2614   this.eachNode(function(id) { nodes.push(id); });
2615   return nodes;
2616 };
2617
2618 BaseGraph.prototype.eachNode = function(func) {
2619   for (var k in this._nodes) {
2620     var node = this._nodes[k];
2621     func(node.id, node.value);
2622   }
2623 };
2624
2625 BaseGraph.prototype.hasEdge = function(e) {
2626   return e in this._edges;
2627 };
2628
2629 BaseGraph.prototype.edge = function(e, value) {
2630   var edge = this._strictGetEdge(e);
2631   if (arguments.length === 1) {
2632     return edge.value;
2633   }
2634   edge.value = value;
2635 };
2636
2637 BaseGraph.prototype.edges = function() {
2638   var es = [];
2639   this.eachEdge(function(id) { es.push(id); });
2640   return es;
2641 };
2642
2643 BaseGraph.prototype.eachEdge = function(func) {
2644   for (var k in this._edges) {
2645     var edge = this._edges[k];
2646     func(edge.id, edge.u, edge.v, edge.value);
2647   }
2648 };
2649
2650 BaseGraph.prototype.incidentNodes = function(e) {
2651   var edge = this._strictGetEdge(e);
2652   return [edge.u, edge.v];
2653 };
2654
2655 BaseGraph.prototype.addNode = function(u, value) {
2656   if (u === undefined || u === null) {
2657     do {
2658       u = "_" + (++this._nextId);
2659     } while (this.hasNode(u));
2660   } else if (this.hasNode(u)) {
2661     throw new Error("Graph already has node '" + u + "'");
2662   }
2663   this._nodes[u] = { id: u, value: value };
2664   return u;
2665 };
2666
2667 BaseGraph.prototype.delNode = function(u) {
2668   this._strictGetNode(u);
2669   this.incidentEdges(u).forEach(function(e) { this.delEdge(e); }, this);
2670   delete this._nodes[u];
2671 };
2672
2673 // inMap and outMap are opposite sides of an incidence map. For example, for
2674 // Graph these would both come from the _incidentEdges map, while for Digraph
2675 // they would come from _inEdges and _outEdges.
2676 BaseGraph.prototype._addEdge = function(e, u, v, value, inMap, outMap) {
2677   this._strictGetNode(u);
2678   this._strictGetNode(v);
2679
2680   if (e === undefined || e === null) {
2681     do {
2682       e = "_" + (++this._nextId);
2683     } while (this.hasEdge(e));
2684   }
2685   else if (this.hasEdge(e)) {
2686     throw new Error("Graph already has edge '" + e + "'");
2687   }
2688
2689   this._edges[e] = { id: e, u: u, v: v, value: value };
2690   addEdgeToMap(inMap[v], u, e);
2691   addEdgeToMap(outMap[u], v, e);
2692
2693   return e;
2694 };
2695
2696 // See note for _addEdge regarding inMap and outMap.
2697 BaseGraph.prototype._delEdge = function(e, inMap, outMap) {
2698   var edge = this._strictGetEdge(e);
2699   delEdgeFromMap(inMap[edge.v], edge.u, e);
2700   delEdgeFromMap(outMap[edge.u], edge.v, e);
2701   delete this._edges[e];
2702 };
2703
2704 BaseGraph.prototype.copy = function() {
2705   var copy = new this.constructor();
2706   copy.graph(this.graph());
2707   this.eachNode(function(u, value) { copy.addNode(u, value); });
2708   this.eachEdge(function(e, u, v, value) { copy.addEdge(e, u, v, value); });
2709   copy._nextId = this._nextId;
2710   return copy;
2711 };
2712
2713 BaseGraph.prototype.filterNodes = function(filter) {
2714   var copy = new this.constructor();
2715   copy.graph(this.graph());
2716   this.eachNode(function(u, value) {
2717     if (filter(u)) {
2718       copy.addNode(u, value);
2719     }
2720   });
2721   this.eachEdge(function(e, u, v, value) {
2722     if (copy.hasNode(u) && copy.hasNode(v)) {
2723       copy.addEdge(e, u, v, value);
2724     }
2725   });
2726   return copy;
2727 };
2728
2729 BaseGraph.prototype._strictGetNode = function(u) {
2730   var node = this._nodes[u];
2731   if (node === undefined) {
2732     throw new Error("Node '" + u + "' is not in graph");
2733   }
2734   return node;
2735 };
2736
2737 BaseGraph.prototype._strictGetEdge = function(e) {
2738   var edge = this._edges[e];
2739   if (edge === undefined) {
2740     throw new Error("Edge '" + e + "' is not in graph");
2741   }
2742   return edge;
2743 };
2744
2745 function addEdgeToMap(map, v, e) {
2746   (map[v] || (map[v] = new Set())).add(e);
2747 }
2748
2749 function delEdgeFromMap(map, v, e) {
2750   var vEntry = map[v];
2751   vEntry.remove(e);
2752   if (vEntry.size() === 0) {
2753     delete map[v];
2754   }
2755 }
2756
2757
2758 },{"cp-data":19}],26:[function(require,module,exports){
2759 var Digraph = require("./Digraph"),
2760     compoundify = require("./compoundify");
2761
2762 var CDigraph = compoundify(Digraph);
2763
2764 module.exports = CDigraph;
2765
2766 CDigraph.fromDigraph = function(src) {
2767   var g = new CDigraph(),
2768       graphValue = src.graph();
2769
2770   if (graphValue !== undefined) {
2771     g.graph(graphValue);
2772   }
2773
2774   src.eachNode(function(u, value) {
2775     if (value === undefined) {
2776       g.addNode(u);
2777     } else {
2778       g.addNode(u, value);
2779     }
2780   });
2781   src.eachEdge(function(e, u, v, value) {
2782     if (value === undefined) {
2783       g.addEdge(null, u, v);
2784     } else {
2785       g.addEdge(null, u, v, value);
2786     }
2787   });
2788   return g;
2789 };
2790
2791 CDigraph.prototype.toString = function() {
2792   return "CDigraph " + JSON.stringify(this, null, 2);
2793 };
2794
2795 },{"./Digraph":28,"./compoundify":41}],27:[function(require,module,exports){
2796 var Graph = require("./Graph"),
2797     compoundify = require("./compoundify");
2798
2799 var CGraph = compoundify(Graph);
2800
2801 module.exports = CGraph;
2802
2803 CGraph.fromGraph = function(src) {
2804   var g = new CGraph(),
2805       graphValue = src.graph();
2806
2807   if (graphValue !== undefined) {
2808     g.graph(graphValue);
2809   }
2810
2811   src.eachNode(function(u, value) {
2812     if (value === undefined) {
2813       g.addNode(u);
2814     } else {
2815       g.addNode(u, value);
2816     }
2817   });
2818   src.eachEdge(function(e, u, v, value) {
2819     if (value === undefined) {
2820       g.addEdge(null, u, v);
2821     } else {
2822       g.addEdge(null, u, v, value);
2823     }
2824   });
2825   return g;
2826 };
2827
2828 CGraph.prototype.toString = function() {
2829   return "CGraph " + JSON.stringify(this, null, 2);
2830 };
2831
2832 },{"./Graph":29,"./compoundify":41}],28:[function(require,module,exports){
2833 /*
2834  * This file is organized with in the following order:
2835  *
2836  * Exports
2837  * Graph constructors
2838  * Graph queries (e.g. nodes(), edges()
2839  * Graph mutators
2840  * Helper functions
2841  */
2842
2843 var util = require("./util"),
2844     BaseGraph = require("./BaseGraph"),
2845 /* jshint -W079 */
2846     Set = require("cp-data").Set;
2847 /* jshint +W079 */
2848
2849 module.exports = Digraph;
2850
2851 /*
2852  * Constructor to create a new directed multi-graph.
2853  */
2854 function Digraph() {
2855   BaseGraph.call(this);
2856
2857   /*! Map of sourceId -> {targetId -> Set of edge ids} */
2858   this._inEdges = {};
2859
2860   /*! Map of targetId -> {sourceId -> Set of edge ids} */
2861   this._outEdges = {};
2862 }
2863
2864 Digraph.prototype = new BaseGraph();
2865 Digraph.prototype.constructor = Digraph;
2866
2867 /*
2868  * Always returns `true`.
2869  */
2870 Digraph.prototype.isDirected = function() {
2871   return true;
2872 };
2873
2874 /*
2875  * Returns all successors of the node with the id `u`. That is, all nodes
2876  * that have the node `u` as their source are returned.
2877  *
2878  * If no node `u` exists in the graph this function throws an Error.
2879  *
2880  * @param {String} u a node id
2881  */
2882 Digraph.prototype.successors = function(u) {
2883   this._strictGetNode(u);
2884   return Object.keys(this._outEdges[u])
2885                .map(function(v) { return this._nodes[v].id; }, this);
2886 };
2887
2888 /*
2889  * Returns all predecessors of the node with the id `u`. That is, all nodes
2890  * that have the node `u` as their target are returned.
2891  *
2892  * If no node `u` exists in the graph this function throws an Error.
2893  *
2894  * @param {String} u a node id
2895  */
2896 Digraph.prototype.predecessors = function(u) {
2897   this._strictGetNode(u);
2898   return Object.keys(this._inEdges[u])
2899                .map(function(v) { return this._nodes[v].id; }, this);
2900 };
2901
2902 /*
2903  * Returns all nodes that are adjacent to the node with the id `u`. In other
2904  * words, this function returns the set of all successors and predecessors of
2905  * node `u`.
2906  *
2907  * @param {String} u a node id
2908  */
2909 Digraph.prototype.neighbors = function(u) {
2910   return Set.union([this.successors(u), this.predecessors(u)]).keys();
2911 };
2912
2913 /*
2914  * Returns all nodes in the graph that have no in-edges.
2915  */
2916 Digraph.prototype.sources = function() {
2917   var self = this;
2918   return this._filterNodes(function(u) {
2919     // This could have better space characteristics if we had an inDegree function.
2920     return self.inEdges(u).length === 0;
2921   });
2922 };
2923
2924 /*
2925  * Returns all nodes in the graph that have no out-edges.
2926  */
2927 Digraph.prototype.sinks = function() {
2928   var self = this;
2929   return this._filterNodes(function(u) {
2930     // This could have better space characteristics if we have an outDegree function.
2931     return self.outEdges(u).length === 0;
2932   });
2933 };
2934
2935 /*
2936  * Returns the source node incident on the edge identified by the id `e`. If no
2937  * such edge exists in the graph this function throws an Error.
2938  *
2939  * @param {String} e an edge id
2940  */
2941 Digraph.prototype.source = function(e) {
2942   return this._strictGetEdge(e).u;
2943 };
2944
2945 /*
2946  * Returns the target node incident on the edge identified by the id `e`. If no
2947  * such edge exists in the graph this function throws an Error.
2948  *
2949  * @param {String} e an edge id
2950  */
2951 Digraph.prototype.target = function(e) {
2952   return this._strictGetEdge(e).v;
2953 };
2954
2955 /*
2956  * Returns an array of ids for all edges in the graph that have the node
2957  * `target` as their target. If the node `target` is not in the graph this
2958  * function raises an Error.
2959  *
2960  * Optionally a `source` node can also be specified. This causes the results
2961  * to be filtered such that only edges from `source` to `target` are included.
2962  * If the node `source` is specified but is not in the graph then this function
2963  * raises an Error.
2964  *
2965  * @param {String} target the target node id
2966  * @param {String} [source] an optional source node id
2967  */
2968 Digraph.prototype.inEdges = function(target, source) {
2969   this._strictGetNode(target);
2970   var results = Set.union(util.values(this._inEdges[target])).keys();
2971   if (arguments.length > 1) {
2972     this._strictGetNode(source);
2973     results = results.filter(function(e) { return this.source(e) === source; }, this);
2974   }
2975   return results;
2976 };
2977
2978 /*
2979  * Returns an array of ids for all edges in the graph that have the node
2980  * `source` as their source. If the node `source` is not in the graph this
2981  * function raises an Error.
2982  *
2983  * Optionally a `target` node may also be specified. This causes the results
2984  * to be filtered such that only edges from `source` to `target` are included.
2985  * If the node `target` is specified but is not in the graph then this function
2986  * raises an Error.
2987  *
2988  * @param {String} source the source node id
2989  * @param {String} [target] an optional target node id
2990  */
2991 Digraph.prototype.outEdges = function(source, target) {
2992   this._strictGetNode(source);
2993   var results = Set.union(util.values(this._outEdges[source])).keys();
2994   if (arguments.length > 1) {
2995     this._strictGetNode(target);
2996     results = results.filter(function(e) { return this.target(e) === target; }, this);
2997   }
2998   return results;
2999 };
3000
3001 /*
3002  * Returns an array of ids for all edges in the graph that have the `u` as
3003  * their source or their target. If the node `u` is not in the graph this
3004  * function raises an Error.
3005  *
3006  * Optionally a `v` node may also be specified. This causes the results to be
3007  * filtered such that only edges between `u` and `v` - in either direction -
3008  * are included. IF the node `v` is specified but not in the graph then this
3009  * function raises an Error.
3010  *
3011  * @param {String} u the node for which to find incident edges
3012  * @param {String} [v] option node that must be adjacent to `u`
3013  */
3014 Digraph.prototype.incidentEdges = function(u, v) {
3015   if (arguments.length > 1) {
3016     return Set.union([this.outEdges(u, v), this.outEdges(v, u)]).keys();
3017   } else {
3018     return Set.union([this.inEdges(u), this.outEdges(u)]).keys();
3019   }
3020 };
3021
3022 /*
3023  * Returns a string representation of this graph.
3024  */
3025 Digraph.prototype.toString = function() {
3026   return "Digraph " + JSON.stringify(this, null, 2);
3027 };
3028
3029 /*
3030  * Adds a new node with the id `u` to the graph and assigns it the value
3031  * `value`. If a node with the id is already a part of the graph this function
3032  * throws an Error.
3033  *
3034  * @param {String} u a node id
3035  * @param {Object} [value] an optional value to attach to the node
3036  */
3037 Digraph.prototype.addNode = function(u, value) {
3038   u = BaseGraph.prototype.addNode.call(this, u, value);
3039   this._inEdges[u] = {};
3040   this._outEdges[u] = {};
3041   return u;
3042 };
3043
3044 /*
3045  * Removes a node from the graph that has the id `u`. Any edges incident on the
3046  * node are also removed. If the graph does not contain a node with the id this
3047  * function will throw an Error.
3048  *
3049  * @param {String} u a node id
3050  */
3051 Digraph.prototype.delNode = function(u) {
3052   BaseGraph.prototype.delNode.call(this, u);
3053   delete this._inEdges[u];
3054   delete this._outEdges[u];
3055 };
3056
3057 /*
3058  * Adds a new edge to the graph with the id `e` from a node with the id `source`
3059  * to a node with an id `target` and assigns it the value `value`. This graph
3060  * allows more than one edge from `source` to `target` as long as the id `e`
3061  * is unique in the set of edges. If `e` is `null` the graph will assign a
3062  * unique identifier to the edge.
3063  *
3064  * If `source` or `target` are not present in the graph this function will
3065  * throw an Error.
3066  *
3067  * @param {String} [e] an edge id
3068  * @param {String} source the source node id
3069  * @param {String} target the target node id
3070  * @param {Object} [value] an optional value to attach to the edge
3071  */
3072 Digraph.prototype.addEdge = function(e, source, target, value) {
3073   return BaseGraph.prototype._addEdge.call(this, e, source, target, value,
3074                                            this._inEdges, this._outEdges);
3075 };
3076
3077 /*
3078  * Removes an edge in the graph with the id `e`. If no edge in the graph has
3079  * the id `e` this function will throw an Error.
3080  *
3081  * @param {String} e an edge id
3082  */
3083 Digraph.prototype.delEdge = function(e) {
3084   BaseGraph.prototype._delEdge.call(this, e, this._inEdges, this._outEdges);
3085 };
3086
3087 // Unlike BaseGraph.filterNodes, this helper just returns nodes that
3088 // satisfy a predicate.
3089 Digraph.prototype._filterNodes = function(pred) {
3090   var filtered = [];
3091   this.eachNode(function(u) {
3092     if (pred(u)) {
3093       filtered.push(u);
3094     }
3095   });
3096   return filtered;
3097 };
3098
3099
3100 },{"./BaseGraph":25,"./util":45,"cp-data":19}],29:[function(require,module,exports){
3101 /*
3102  * This file is organized with in the following order:
3103  *
3104  * Exports
3105  * Graph constructors
3106  * Graph queries (e.g. nodes(), edges()
3107  * Graph mutators
3108  * Helper functions
3109  */
3110
3111 var util = require("./util"),
3112     BaseGraph = require("./BaseGraph"),
3113 /* jshint -W079 */
3114     Set = require("cp-data").Set;
3115 /* jshint +W079 */
3116
3117 module.exports = Graph;
3118
3119 /*
3120  * Constructor to create a new undirected multi-graph.
3121  */
3122 function Graph() {
3123   BaseGraph.call(this);
3124
3125   /*! Map of nodeId -> { otherNodeId -> Set of edge ids } */
3126   this._incidentEdges = {};
3127 }
3128
3129 Graph.prototype = new BaseGraph();
3130 Graph.prototype.constructor = Graph;
3131
3132 /*
3133  * Always returns `false`.
3134  */
3135 Graph.prototype.isDirected = function() {
3136   return false;
3137 };
3138
3139 /*
3140  * Returns all nodes that are adjacent to the node with the id `u`.
3141  *
3142  * @param {String} u a node id
3143  */
3144 Graph.prototype.neighbors = function(u) {
3145   this._strictGetNode(u);
3146   return Object.keys(this._incidentEdges[u])
3147                .map(function(v) { return this._nodes[v].id; }, this);
3148 };
3149
3150 /*
3151  * Returns an array of ids for all edges in the graph that are incident on `u`.
3152  * If the node `u` is not in the graph this function raises an Error.
3153  *
3154  * Optionally a `v` node may also be specified. This causes the results to be
3155  * filtered such that only edges between `u` and `v` are included. If the node
3156  * `v` is specified but not in the graph then this function raises an Error.
3157  *
3158  * @param {String} u the node for which to find incident edges
3159  * @param {String} [v] option node that must be adjacent to `u`
3160  */
3161 Graph.prototype.incidentEdges = function(u, v) {
3162   this._strictGetNode(u);
3163   if (arguments.length > 1) {
3164     this._strictGetNode(v);
3165     return v in this._incidentEdges[u] ? this._incidentEdges[u][v].keys() : [];
3166   } else {
3167     return Set.union(util.values(this._incidentEdges[u])).keys();
3168   }
3169 };
3170
3171 /*
3172  * Returns a string representation of this graph.
3173  */
3174 Graph.prototype.toString = function() {
3175   return "Graph " + JSON.stringify(this, null, 2);
3176 };
3177
3178 /*
3179  * Adds a new node with the id `u` to the graph and assigns it the value
3180  * `value`. If a node with the id is already a part of the graph this function
3181  * throws an Error.
3182  *
3183  * @param {String} u a node id
3184  * @param {Object} [value] an optional value to attach to the node
3185  */
3186 Graph.prototype.addNode = function(u, value) {
3187   u = BaseGraph.prototype.addNode.call(this, u, value);
3188   this._incidentEdges[u] = {};
3189   return u;
3190 };
3191
3192 /*
3193  * Removes a node from the graph that has the id `u`. Any edges incident on the
3194  * node are also removed. If the graph does not contain a node with the id this
3195  * function will throw an Error.
3196  *
3197  * @param {String} u a node id
3198  */
3199 Graph.prototype.delNode = function(u) {
3200   BaseGraph.prototype.delNode.call(this, u);
3201   delete this._incidentEdges[u];
3202 };
3203
3204 /*
3205  * Adds a new edge to the graph with the id `e` between a node with the id `u`
3206  * and a node with an id `v` and assigns it the value `value`. This graph
3207  * allows more than one edge between `u` and `v` as long as the id `e`
3208  * is unique in the set of edges. If `e` is `null` the graph will assign a
3209  * unique identifier to the edge.
3210  *
3211  * If `u` or `v` are not present in the graph this function will throw an
3212  * Error.
3213  *
3214  * @param {String} [e] an edge id
3215  * @param {String} u the node id of one of the adjacent nodes
3216  * @param {String} v the node id of the other adjacent node
3217  * @param {Object} [value] an optional value to attach to the edge
3218  */
3219 Graph.prototype.addEdge = function(e, u, v, value) {
3220   return BaseGraph.prototype._addEdge.call(this, e, u, v, value,
3221                                            this._incidentEdges, this._incidentEdges);
3222 };
3223
3224 /*
3225  * Removes an edge in the graph with the id `e`. If no edge in the graph has
3226  * the id `e` this function will throw an Error.
3227  *
3228  * @param {String} e an edge id
3229  */
3230 Graph.prototype.delEdge = function(e) {
3231   BaseGraph.prototype._delEdge.call(this, e, this._incidentEdges, this._incidentEdges);
3232 };
3233
3234
3235 },{"./BaseGraph":25,"./util":45,"cp-data":19}],30:[function(require,module,exports){
3236 /* jshint -W079 */
3237 var Set = require("cp-data").Set;
3238 /* jshint +W079 */
3239
3240 module.exports = components;
3241
3242 /**
3243  * Finds all [connected components][] in a graph and returns an array of these
3244  * components. Each component is itself an array that contains the ids of nodes
3245  * in the component.
3246  *
3247  * This function only works with undirected Graphs.
3248  *
3249  * [connected components]: http://en.wikipedia.org/wiki/Connected_component_(graph_theory)
3250  *
3251  * @param {Graph} g the graph to search for components
3252  */
3253 function components(g) {
3254   var results = [];
3255   var visited = new Set();
3256
3257   function dfs(v, component) {
3258     if (!visited.has(v)) {
3259       visited.add(v);
3260       component.push(v);
3261       g.neighbors(v).forEach(function(w) {
3262         dfs(w, component);
3263       });
3264     }
3265   }
3266
3267   g.nodes().forEach(function(v) {
3268     var component = [];
3269     dfs(v, component);
3270     if (component.length > 0) {
3271       results.push(component);
3272     }
3273   });
3274
3275   return results;
3276 }
3277
3278 },{"cp-data":19}],31:[function(require,module,exports){
3279 var PriorityQueue = require("cp-data").PriorityQueue;
3280
3281 module.exports = dijkstra;
3282
3283 /**
3284  * This function is an implementation of [Dijkstra's algorithm][] which finds
3285  * the shortest path from **source** to all other nodes in **g**. This
3286  * function returns a map of `u -> { distance, predecessor }`. The distance
3287  * property holds the sum of the weights from **source** to `u` along the
3288  * shortest path or `Number.POSITIVE_INFINITY` if there is no path from
3289  * **source**. The predecessor property can be used to walk the individual
3290  * elements of the path from **source** to **u** in reverse order.
3291  *
3292  * This function takes an optional `weightFunc(e)` which returns the
3293  * weight of the edge `e`. If no weightFunc is supplied then each edge is
3294  * assumed to have a weight of 1. This function throws an Error if any of
3295  * the traversed edges have a negative edge weight.
3296  *
3297  * This function takes an optional `incidentFunc(u)` which returns the ids of
3298  * all edges incident to the node `u` for the purposes of shortest path
3299  * traversal. By default this function uses the `g.outEdges` for Digraphs and
3300  * `g.incidentEdges` for Graphs.
3301  *
3302  * This function takes `O((|E| + |V|) * log |V|)` time.
3303  *
3304  * [Dijkstra's algorithm]: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
3305  *
3306  * @param {Graph} g the graph to search for shortest paths from **source**
3307  * @param {Object} source the source from which to start the search
3308  * @param {Function} [weightFunc] optional weight function
3309  * @param {Function} [incidentFunc] optional incident function
3310  */
3311 function dijkstra(g, source, weightFunc, incidentFunc) {
3312   var results = {},
3313       pq = new PriorityQueue();
3314
3315   function updateNeighbors(e) {
3316     var incidentNodes = g.incidentNodes(e),
3317         v = incidentNodes[0] !== u ? incidentNodes[0] : incidentNodes[1],
3318         vEntry = results[v],
3319         weight = weightFunc(e),
3320         distance = uEntry.distance + weight;
3321
3322     if (weight < 0) {
3323       throw new Error("dijkstra does not allow negative edge weights. Bad edge: " + e + " Weight: " + weight);
3324     }
3325
3326     if (distance < vEntry.distance) {
3327       vEntry.distance = distance;
3328       vEntry.predecessor = u;
3329       pq.decrease(v, distance);
3330     }
3331   }
3332
3333   weightFunc = weightFunc || function() { return 1; };
3334   incidentFunc = incidentFunc || (g.isDirected()
3335       ? function(u) { return g.outEdges(u); }
3336       : function(u) { return g.incidentEdges(u); });
3337
3338   g.eachNode(function(u) {
3339     var distance = u === source ? 0 : Number.POSITIVE_INFINITY;
3340     results[u] = { distance: distance };
3341     pq.add(u, distance);
3342   });
3343
3344   var u, uEntry;
3345   while (pq.size() > 0) {
3346     u = pq.removeMin();
3347     uEntry = results[u];
3348     if (uEntry.distance === Number.POSITIVE_INFINITY) {
3349       break;
3350     }
3351
3352     incidentFunc(u).forEach(updateNeighbors);
3353   }
3354
3355   return results;
3356 }
3357
3358 },{"cp-data":19}],32:[function(require,module,exports){
3359 var dijkstra = require("./dijkstra");
3360
3361 module.exports = dijkstraAll;
3362
3363 /**
3364  * This function finds the shortest path from each node to every other
3365  * reachable node in the graph. It is similar to [alg.dijkstra][], but
3366  * instead of returning a single-source array, it returns a mapping of
3367  * of `source -> alg.dijksta(g, source, weightFunc, incidentFunc)`.
3368  *
3369  * This function takes an optional `weightFunc(e)` which returns the
3370  * weight of the edge `e`. If no weightFunc is supplied then each edge is
3371  * assumed to have a weight of 1. This function throws an Error if any of
3372  * the traversed edges have a negative edge weight.
3373  *
3374  * This function takes an optional `incidentFunc(u)` which returns the ids of
3375  * all edges incident to the node `u` for the purposes of shortest path
3376  * traversal. By default this function uses the `outEdges` function on the
3377  * supplied graph.
3378  *
3379  * This function takes `O(|V| * (|E| + |V|) * log |V|)` time.
3380  *
3381  * [alg.dijkstra]: dijkstra.js.html#dijkstra
3382  *
3383  * @param {Graph} g the graph to search for shortest paths from **source**
3384  * @param {Function} [weightFunc] optional weight function
3385  * @param {Function} [incidentFunc] optional incident function
3386  */
3387 function dijkstraAll(g, weightFunc, incidentFunc) {
3388   var results = {};
3389   g.eachNode(function(u) {
3390     results[u] = dijkstra(g, u, weightFunc, incidentFunc);
3391   });
3392   return results;
3393 }
3394
3395 },{"./dijkstra":31}],33:[function(require,module,exports){
3396 var tarjan = require("./tarjan");
3397
3398 module.exports = findCycles;
3399
3400 /*
3401  * Given a Digraph **g** this function returns all nodes that are part of a
3402  * cycle. Since there may be more than one cycle in a graph this function
3403  * returns an array of these cycles, where each cycle is itself represented
3404  * by an array of ids for each node involved in that cycle.
3405  *
3406  * [alg.isAcyclic][] is more efficient if you only need to determine whether
3407  * a graph has a cycle or not.
3408  *
3409  * [alg.isAcyclic]: isAcyclic.js.html#isAcyclic
3410  *
3411  * @param {Digraph} g the graph to search for cycles.
3412  */
3413 function findCycles(g) {
3414   return tarjan(g).filter(function(cmpt) { return cmpt.length > 1; });
3415 }
3416
3417 },{"./tarjan":39}],34:[function(require,module,exports){
3418 module.exports = floydWarshall;
3419
3420 /**
3421  * This function is an implementation of the [Floyd-Warshall algorithm][],
3422  * which finds the shortest path from each node to every other reachable node
3423  * in the graph. It is similar to [alg.dijkstraAll][], but it handles negative
3424  * edge weights and is more efficient for some types of graphs. This function
3425  * returns a map of `source -> { target -> { distance, predecessor }`. The
3426  * distance property holds the sum of the weights from `source` to `target`
3427  * along the shortest path of `Number.POSITIVE_INFINITY` if there is no path
3428  * from `source`. The predecessor property can be used to walk the individual
3429  * elements of the path from `source` to `target` in reverse order.
3430  *
3431  * This function takes an optional `weightFunc(e)` which returns the
3432  * weight of the edge `e`. If no weightFunc is supplied then each edge is
3433  * assumed to have a weight of 1.
3434  *
3435  * This function takes an optional `incidentFunc(u)` which returns the ids of
3436  * all edges incident to the node `u` for the purposes of shortest path
3437  * traversal. By default this function uses the `outEdges` function on the
3438  * supplied graph.
3439  *
3440  * This algorithm takes O(|V|^3) time.
3441  *
3442  * [Floyd-Warshall algorithm]: https://en.wikipedia.org/wiki/Floyd-Warshall_algorithm
3443  * [alg.dijkstraAll]: dijkstraAll.js.html#dijkstraAll
3444  *
3445  * @param {Graph} g the graph to search for shortest paths from **source**
3446  * @param {Function} [weightFunc] optional weight function
3447  * @param {Function} [incidentFunc] optional incident function
3448  */
3449 function floydWarshall(g, weightFunc, incidentFunc) {
3450   var results = {},
3451       nodes = g.nodes();
3452
3453   weightFunc = weightFunc || function() { return 1; };
3454   incidentFunc = incidentFunc || (g.isDirected()
3455       ? function(u) { return g.outEdges(u); }
3456       : function(u) { return g.incidentEdges(u); });
3457
3458   nodes.forEach(function(u) {
3459     results[u] = {};
3460     results[u][u] = { distance: 0 };
3461     nodes.forEach(function(v) {
3462       if (u !== v) {
3463         results[u][v] = { distance: Number.POSITIVE_INFINITY };
3464       }
3465     });
3466     incidentFunc(u).forEach(function(e) {
3467       var incidentNodes = g.incidentNodes(e),
3468           v = incidentNodes[0] !== u ? incidentNodes[0] : incidentNodes[1],
3469           d = weightFunc(e);
3470       if (d < results[u][v].distance) {
3471         results[u][v] = { distance: d, predecessor: u };
3472       }
3473     });
3474   });
3475
3476   nodes.forEach(function(k) {
3477     var rowK = results[k];
3478     nodes.forEach(function(i) {
3479       var rowI = results[i];
3480       nodes.forEach(function(j) {
3481         var ik = rowI[k];
3482         var kj = rowK[j];
3483         var ij = rowI[j];
3484         var altDistance = ik.distance + kj.distance;
3485         if (altDistance < ij.distance) {
3486           ij.distance = altDistance;
3487           ij.predecessor = kj.predecessor;
3488         }
3489       });
3490     });
3491   });
3492
3493   return results;
3494 }
3495
3496 },{}],35:[function(require,module,exports){
3497 var topsort = require("./topsort");
3498
3499 module.exports = isAcyclic;
3500
3501 /*
3502  * Given a Digraph **g** this function returns `true` if the graph has no
3503  * cycles and returns `false` if it does. This algorithm returns as soon as it
3504  * detects the first cycle.
3505  *
3506  * Use [alg.findCycles][] if you need the actual list of cycles in a graph.
3507  *
3508  * [alg.findCycles]: findCycles.js.html#findCycles
3509  *
3510  * @param {Digraph} g the graph to test for cycles
3511  */
3512 function isAcyclic(g) {
3513   try {
3514     topsort(g);
3515   } catch (e) {
3516     if (e instanceof topsort.CycleException) return false;
3517     throw e;
3518   }
3519   return true;
3520 }
3521
3522 },{"./topsort":40}],36:[function(require,module,exports){
3523 /* jshint -W079 */
3524 var Set = require("cp-data").Set;
3525 /* jshint +W079 */
3526
3527 module.exports = postorder;
3528
3529 // Postorder traversal of g, calling f for each visited node. Assumes the graph
3530 // is a tree.
3531 function postorder(g, root, f) {
3532   var visited = new Set();
3533   if (g.isDirected()) {
3534     throw new Error("This function only works for undirected graphs");
3535   }
3536   function dfs(u, prev) {
3537     if (visited.has(u)) {
3538       throw new Error("The input graph is not a tree: " + g);
3539     }
3540     visited.add(u);
3541     g.neighbors(u).forEach(function(v) {
3542       if (v !== prev) dfs(v, u);
3543     });
3544     f(u);
3545   }
3546   dfs(root);
3547 }
3548
3549 },{"cp-data":19}],37:[function(require,module,exports){
3550 /* jshint -W079 */
3551 var Set = require("cp-data").Set;
3552 /* jshint +W079 */
3553
3554 module.exports = preorder;
3555
3556 // Preorder traversal of g, calling f for each visited node. Assumes the graph
3557 // is a tree.
3558 function preorder(g, root, f) {
3559   var visited = new Set();
3560   if (g.isDirected()) {
3561     throw new Error("This function only works for undirected graphs");
3562   }
3563   function dfs(u, prev) {
3564     if (visited.has(u)) {
3565       throw new Error("The input graph is not a tree: " + g);
3566     }
3567     visited.add(u);
3568     f(u);
3569     g.neighbors(u).forEach(function(v) {
3570       if (v !== prev) dfs(v, u);
3571     });
3572   }
3573   dfs(root);
3574 }
3575
3576 },{"cp-data":19}],38:[function(require,module,exports){
3577 var Graph = require("../Graph"),
3578     PriorityQueue = require("cp-data").PriorityQueue;
3579
3580 module.exports = prim;
3581
3582 /**
3583  * [Prim's algorithm][] takes a connected undirected graph and generates a
3584  * [minimum spanning tree][]. This function returns the minimum spanning
3585  * tree as an undirected graph. This algorithm is derived from the description
3586  * in "Introduction to Algorithms", Third Edition, Cormen, et al., Pg 634.
3587  *
3588  * This function takes a `weightFunc(e)` which returns the weight of the edge
3589  * `e`. It throws an Error if the graph is not connected.
3590  *
3591  * This function takes `O(|E| log |V|)` time.
3592  *
3593  * [Prim's algorithm]: https://en.wikipedia.org/wiki/Prim's_algorithm
3594  * [minimum spanning tree]: https://en.wikipedia.org/wiki/Minimum_spanning_tree
3595  *
3596  * @param {Graph} g the graph used to generate the minimum spanning tree
3597  * @param {Function} weightFunc the weight function to use
3598  */
3599 function prim(g, weightFunc) {
3600   var result = new Graph(),
3601       parents = {},
3602       pq = new PriorityQueue(),
3603       u;
3604
3605   function updateNeighbors(e) {
3606     var incidentNodes = g.incidentNodes(e),
3607         v = incidentNodes[0] !== u ? incidentNodes[0] : incidentNodes[1],
3608         pri = pq.priority(v);
3609     if (pri !== undefined) {
3610       var edgeWeight = weightFunc(e);
3611       if (edgeWeight < pri) {
3612         parents[v] = u;
3613         pq.decrease(v, edgeWeight);
3614       }
3615     }
3616   }
3617
3618   if (g.order() === 0) {
3619     return result;
3620   }
3621
3622   g.eachNode(function(u) {
3623     pq.add(u, Number.POSITIVE_INFINITY);
3624     result.addNode(u);
3625   });
3626
3627   // Start from an arbitrary node
3628   pq.decrease(g.nodes()[0], 0);
3629
3630   var init = false;
3631   while (pq.size() > 0) {
3632     u = pq.removeMin();
3633     if (u in parents) {
3634       result.addEdge(null, u, parents[u]);
3635     } else if (init) {
3636       throw new Error("Input graph is not connected: " + g);
3637     } else {
3638       init = true;
3639     }
3640
3641     g.incidentEdges(u).forEach(updateNeighbors);
3642   }
3643
3644   return result;
3645 }
3646
3647 },{"../Graph":29,"cp-data":19}],39:[function(require,module,exports){
3648 module.exports = tarjan;
3649
3650 /**
3651  * This function is an implementation of [Tarjan's algorithm][] which finds
3652  * all [strongly connected components][] in the directed graph **g**. Each
3653  * strongly connected component is composed of nodes that can reach all other
3654  * nodes in the component via directed edges. A strongly connected component
3655  * can consist of a single node if that node cannot both reach and be reached
3656  * by any other specific node in the graph. Components of more than one node
3657  * are guaranteed to have at least one cycle.
3658  *
3659  * This function returns an array of components. Each component is itself an
3660  * array that contains the ids of all nodes in the component.
3661  *
3662  * [Tarjan's algorithm]: http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm
3663  * [strongly connected components]: http://en.wikipedia.org/wiki/Strongly_connected_component
3664  *
3665  * @param {Digraph} g the graph to search for strongly connected components
3666  */
3667 function tarjan(g) {
3668   if (!g.isDirected()) {
3669     throw new Error("tarjan can only be applied to a directed graph. Bad input: " + g);
3670   }
3671
3672   var index = 0,
3673       stack = [],
3674       visited = {}, // node id -> { onStack, lowlink, index }
3675       results = [];
3676
3677   function dfs(u) {
3678     var entry = visited[u] = {
3679       onStack: true,
3680       lowlink: index,
3681       index: index++
3682     };
3683     stack.push(u);
3684
3685     g.successors(u).forEach(function(v) {
3686       if (!(v in visited)) {
3687         dfs(v);
3688         entry.lowlink = Math.min(entry.lowlink, visited[v].lowlink);
3689       } else if (visited[v].onStack) {
3690         entry.lowlink = Math.min(entry.lowlink, visited[v].index);
3691       }
3692     });
3693
3694     if (entry.lowlink === entry.index) {
3695       var cmpt = [],
3696           v;
3697       do {
3698         v = stack.pop();
3699         visited[v].onStack = false;
3700         cmpt.push(v);
3701       } while (u !== v);
3702       results.push(cmpt);
3703     }
3704   }
3705
3706   g.nodes().forEach(function(u) {
3707     if (!(u in visited)) {
3708       dfs(u);
3709     }
3710   });
3711
3712   return results;
3713 }
3714
3715 },{}],40:[function(require,module,exports){
3716 module.exports = topsort;
3717 topsort.CycleException = CycleException;
3718
3719 /*
3720  * Given a graph **g**, this function returns an ordered list of nodes such
3721  * that for each edge `u -> v`, `u` appears before `v` in the list. If the
3722  * graph has a cycle it is impossible to generate such a list and
3723  * **CycleException** is thrown.
3724  *
3725  * See [topological sorting](https://en.wikipedia.org/wiki/Topological_sorting)
3726  * for more details about how this algorithm works.
3727  *
3728  * @param {Digraph} g the graph to sort
3729  */
3730 function topsort(g) {
3731   if (!g.isDirected()) {
3732     throw new Error("topsort can only be applied to a directed graph. Bad input: " + g);
3733   }
3734
3735   var visited = {};
3736   var stack = {};
3737   var results = [];
3738
3739   function visit(node) {
3740     if (node in stack) {
3741       throw new CycleException();
3742     }
3743
3744     if (!(node in visited)) {
3745       stack[node] = true;
3746       visited[node] = true;
3747       g.predecessors(node).forEach(function(pred) {
3748         visit(pred);
3749       });
3750       delete stack[node];
3751       results.push(node);
3752     }
3753   }
3754
3755   var sinks = g.sinks();
3756   if (g.order() !== 0 && sinks.length === 0) {
3757     throw new CycleException();
3758   }
3759
3760   g.sinks().forEach(function(sink) {
3761     visit(sink);
3762   });
3763
3764   return results;
3765 }
3766
3767 function CycleException() {}
3768
3769 CycleException.prototype.toString = function() {
3770   return "Graph has at least one cycle";
3771 };
3772
3773 },{}],41:[function(require,module,exports){
3774 // This file provides a helper function that mixes-in Dot behavior to an
3775 // existing graph prototype.
3776
3777 /* jshint -W079 */
3778 var Set = require("cp-data").Set;
3779 /* jshint +W079 */
3780
3781 module.exports = compoundify;
3782
3783 // Extends the given SuperConstructor with the ability for nodes to contain
3784 // other nodes. A special node id `null` is used to indicate the root graph.
3785 function compoundify(SuperConstructor) {
3786   function Constructor() {
3787     SuperConstructor.call(this);
3788
3789     // Map of object id -> parent id (or null for root graph)
3790     this._parents = {};
3791
3792     // Map of id (or null) -> children set
3793     this._children = {};
3794     this._children[null] = new Set();
3795   }
3796
3797   Constructor.prototype = new SuperConstructor();
3798   Constructor.prototype.constructor = Constructor;
3799
3800   Constructor.prototype.parent = function(u, parent) {
3801     this._strictGetNode(u);
3802
3803     if (arguments.length < 2) {
3804       return this._parents[u];
3805     }
3806
3807     if (u === parent) {
3808       throw new Error("Cannot make " + u + " a parent of itself");
3809     }
3810     if (parent !== null) {
3811       this._strictGetNode(parent);
3812     }
3813
3814     this._children[this._parents[u]].remove(u);
3815     this._parents[u] = parent;
3816     this._children[parent].add(u);
3817   };
3818
3819   Constructor.prototype.children = function(u) {
3820     if (u !== null) {
3821       this._strictGetNode(u);
3822     }
3823     return this._children[u].keys();
3824   };
3825
3826   Constructor.prototype.addNode = function(u, value) {
3827     u = SuperConstructor.prototype.addNode.call(this, u, value);
3828     this._parents[u] = null;
3829     this._children[u] = new Set();
3830     this._children[null].add(u);
3831     return u;
3832   };
3833
3834   Constructor.prototype.delNode = function(u) {
3835     // Promote all children to the parent of the subgraph
3836     var parent = this.parent(u);
3837     this._children[u].keys().forEach(function(child) {
3838       this.parent(child, parent);
3839     }, this);
3840
3841     this._children[parent].remove(u);
3842     delete this._parents[u];
3843     delete this._children[u];
3844
3845     return SuperConstructor.prototype.delNode.call(this, u);
3846   };
3847
3848   Constructor.prototype.copy = function() {
3849     var copy = SuperConstructor.prototype.copy.call(this);
3850     this.nodes().forEach(function(u) {
3851       copy.parent(u, this.parent(u));
3852     }, this);
3853     return copy;
3854   };
3855
3856   Constructor.prototype.filterNodes = function(filter) {
3857     var self = this,
3858         copy = SuperConstructor.prototype.filterNodes.call(this, filter);
3859
3860     var parents = {};
3861     function findParent(u) {
3862       var parent = self.parent(u);
3863       if (parent === null || copy.hasNode(parent)) {
3864         parents[u] = parent;
3865         return parent;
3866       } else if (parent in parents) {
3867         return parents[parent];
3868       } else {
3869         return findParent(parent);
3870       }
3871     }
3872
3873     copy.eachNode(function(u) { copy.parent(u, findParent(u)); });
3874
3875     return copy;
3876   };
3877
3878   return Constructor;
3879 }
3880
3881 },{"cp-data":19}],42:[function(require,module,exports){
3882 var Graph = require("../Graph"),
3883     Digraph = require("../Digraph"),
3884     CGraph = require("../CGraph"),
3885     CDigraph = require("../CDigraph");
3886
3887 exports.decode = function(nodes, edges, Ctor) {
3888   Ctor = Ctor || Digraph;
3889
3890   if (typeOf(nodes) !== "Array") {
3891     throw new Error("nodes is not an Array");
3892   }
3893
3894   if (typeOf(edges) !== "Array") {
3895     throw new Error("edges is not an Array");
3896   }
3897
3898   if (typeof Ctor === "string") {
3899     switch(Ctor) {
3900       case "graph": Ctor = Graph; break;
3901       case "digraph": Ctor = Digraph; break;
3902       case "cgraph": Ctor = CGraph; break;
3903       case "cdigraph": Ctor = CDigraph; break;
3904       default: throw new Error("Unrecognized graph type: " + Ctor);
3905     }
3906   }
3907
3908   var graph = new Ctor();
3909
3910   nodes.forEach(function(u) {
3911     graph.addNode(u.id, u.value);
3912   });
3913
3914   // If the graph is compound, set up children...
3915   if (graph.parent) {
3916     nodes.forEach(function(u) {
3917       if (u.children) {
3918         u.children.forEach(function(v) {
3919           graph.parent(v, u.id);
3920         });
3921       }
3922     });
3923   }
3924
3925   edges.forEach(function(e) {
3926     graph.addEdge(e.id, e.u, e.v, e.value);
3927   });
3928
3929   return graph;
3930 };
3931
3932 exports.encode = function(graph) {
3933   var nodes = [];
3934   var edges = [];
3935
3936   graph.eachNode(function(u, value) {
3937     var node = {id: u, value: value};
3938     if (graph.children) {
3939       var children = graph.children(u);
3940       if (children.length) {
3941         node.children = children;
3942       }
3943     }
3944     nodes.push(node);
3945   });
3946
3947   graph.eachEdge(function(e, u, v, value) {
3948     edges.push({id: e, u: u, v: v, value: value});
3949   });
3950
3951   var type;
3952   if (graph instanceof CDigraph) {
3953     type = "cdigraph";
3954   } else if (graph instanceof CGraph) {
3955     type = "cgraph";
3956   } else if (graph instanceof Digraph) {
3957     type = "digraph";
3958   } else if (graph instanceof Graph) {
3959     type = "graph";
3960   } else {
3961     throw new Error("Couldn't determine type of graph: " + graph);
3962   }
3963
3964   return { nodes: nodes, edges: edges, type: type };
3965 };
3966
3967 function typeOf(obj) {
3968   return Object.prototype.toString.call(obj).slice(8, -1);
3969 }
3970
3971 },{"../CDigraph":26,"../CGraph":27,"../Digraph":28,"../Graph":29}],43:[function(require,module,exports){
3972 /* jshint -W079 */
3973 var Set = require("cp-data").Set;
3974 /* jshint +W079 */
3975
3976 exports.all = function() {
3977   return function() { return true; };
3978 };
3979
3980 exports.nodesFromList = function(nodes) {
3981   var set = new Set(nodes);
3982   return function(u) {
3983     return set.has(u);
3984   };
3985 };
3986
3987 },{"cp-data":19}],44:[function(require,module,exports){
3988 var Graph = require("./Graph"),
3989     Digraph = require("./Digraph");
3990
3991 // Side-effect based changes are lousy, but node doesn't seem to resolve the
3992 // requires cycle.
3993
3994 /**
3995  * Returns a new directed graph using the nodes and edges from this graph. The
3996  * new graph will have the same nodes, but will have twice the number of edges:
3997  * each edge is split into two edges with opposite directions. Edge ids,
3998  * consequently, are not preserved by this transformation.
3999  */
4000 Graph.prototype.toDigraph =
4001 Graph.prototype.asDirected = function() {
4002   var g = new Digraph();
4003   this.eachNode(function(u, value) { g.addNode(u, value); });
4004   this.eachEdge(function(e, u, v, value) {
4005     g.addEdge(null, u, v, value);
4006     g.addEdge(null, v, u, value);
4007   });
4008   return g;
4009 };
4010
4011 /**
4012  * Returns a new undirected graph using the nodes and edges from this graph.
4013  * The new graph will have the same nodes, but the edges will be made
4014  * undirected. Edge ids are preserved in this transformation.
4015  */
4016 Digraph.prototype.toGraph =
4017 Digraph.prototype.asUndirected = function() {
4018   var g = new Graph();
4019   this.eachNode(function(u, value) { g.addNode(u, value); });
4020   this.eachEdge(function(e, u, v, value) {
4021     g.addEdge(e, u, v, value);
4022   });
4023   return g;
4024 };
4025
4026 },{"./Digraph":28,"./Graph":29}],45:[function(require,module,exports){
4027 // Returns an array of all values for properties of **o**.
4028 exports.values = function(o) {
4029   var ks = Object.keys(o),
4030       len = ks.length,
4031       result = new Array(len),
4032       i;
4033   for (i = 0; i < len; ++i) {
4034     result[i] = o[ks[i]];
4035   }
4036   return result;
4037 };
4038
4039 },{}],46:[function(require,module,exports){
4040 module.exports = '0.7.4';
4041
4042 },{}]},{},[1])
4043 ;
4044 joint.layout.DirectedGraph = {
4045
4046     layout: function(graph, opt) {
4047
4048         opt = opt || {};
4049
4050         var inputGraph = this._prepareData(graph);
4051         var runner = dagre.layout();
4052
4053         if (opt.debugLevel) { runner.debugLevel(opt.debugLevel); }
4054         if (opt.rankDir) { runner.rankDir(opt.rankDir); }
4055         if (opt.rankSep) { runner.rankSep(opt.rankSep); }
4056         if (opt.edgeSep) { runner.edgeSep(opt.edgeSep); }
4057         if (opt.nodeSep) { runner.nodeSep(opt.nodeSep); }
4058
4059         var layoutGraph = runner.run(inputGraph);
4060
4061         layoutGraph.eachNode(function(u, value) {
4062             if (!value.dummy) {
4063                 graph.get('cells').get(u).set('position', {
4064                     x: value.x - value.width/2,
4065                     y: value.y - value.height/2
4066                 });
4067             }
4068         });
4069
4070         if (opt.setLinkVertices) {
4071
4072             layoutGraph.eachEdge(function(e, u, v, value) {
4073                 var link = graph.get('cells').get(e);
4074                 if (link) {
4075                     graph.get('cells').get(e).set('vertices', value.points);
4076                 }
4077             });
4078         }
4079
4080         return { width: layoutGraph.graph().width, height: layoutGraph.graph().height };
4081     },
4082
4083     _prepareData: function(graph) {
4084         var dagreGraph = new dagre.Digraph();
4085
4086         // For each element.
4087         _.each(graph.getElements(), function(cell) {
4088
4089             if (dagreGraph.hasNode(cell.id)) return;
4090
4091             dagreGraph.addNode(cell.id, {
4092                 width: cell.get('size').width,
4093                 height: cell.get('size').height,
4094                 rank: cell.get('rank')
4095             });
4096         });
4097
4098         // For each link.
4099         _.each(graph.getLinks(), function(cell) {
4100
4101             if (dagreGraph.hasEdge(cell.id)) return;
4102
4103             var sourceId = cell.get('source').id;
4104             var targetId = cell.get('target').id;
4105
4106             dagreGraph.addEdge(cell.id, sourceId, targetId, { minLen: cell.get('minLen') || 1 });
4107         });
4108
4109         return dagreGraph;
4110     }
4111 };