1 // Implements hierarchical edge bundling using Holten's algorithm. For each

     2 // input link, a path is computed that travels through the tree, up the parent

     3 // hierarchy to the least common ancestor, and then back down to the destination

     4 // node. Each path is simply an array of nodes.

     5 d3.layout.bundle = function() {

     6   return function(links) {

     7     var paths = [],

     8         i = -1,

     9         n = links.length;

    10     while (++i < n) paths.push(d3_layout_bundlePath(links[i]));

    11     return paths;

    12   };

    13 };

    14 

    15 function d3_layout_bundlePath(link) {

    16   var start = link.source,

    17       end = link.target,

    18       lca = d3_layout_bundleLeastCommonAncestor(start, end),

    19       points = [start];

    20   while (start !== lca) {

    21     start = start.parent;

    22     points.push(start);

    23   }

    24   var k = points.length;

    25   while (end !== lca) {

    26     points.splice(k, 0, end);

    27     end = end.parent;

    28   }

    29   return points;

    30 }

    31 

    32 function d3_layout_bundleAncestors(node) {

    33   var ancestors = [],

    34       parent = node.parent;

    35   while (parent != null) {

    36     ancestors.push(node);

    37     node = parent;

    38     parent = parent.parent;

    39   }

    40   ancestors.push(node);

    41   return ancestors;

    42 }

    43 

    44 function d3_layout_bundleLeastCommonAncestor(a, b) {

    45   if (a === b) return a;

    46   var aNodes = d3_layout_bundleAncestors(a),

    47       bNodes = d3_layout_bundleAncestors(b),

    48       aNode = aNodes.pop(),

    49       bNode = bNodes.pop(),

    50       sharedNode = null;

    51   while (aNode === bNode) {

    52     sharedNode = aNode;

    53     aNode = aNodes.pop();

    54     bNode = bNodes.pop();

    55   }

    56   return sharedNode;

    57 }