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

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

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

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

d3.layout.bundle = function() {

  return function(links) {

    var paths = [],

        i = -1,

        n = links.length;

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

    return paths;

  };

};

function d3_layout_bundlePath(link) {

  var start = link.source,

      end = link.target,

      lca = d3_layout_bundleLeastCommonAncestor(start, end),

      points = [start];

  while (start !== lca) {

    start = start.parent;

    points.push(start);

  }

  var k = points.length;

  while (end !== lca) {

    points.splice(k, 0, end);

    end = end.parent;

  }

  return points;

}

function d3_layout_bundleAncestors(node) {

  var ancestors = [],

      parent = node.parent;

  while (parent != null) {

    ancestors.push(node);

    node = parent;

    parent = parent.parent;

  }

  ancestors.push(node);

  return ancestors;

}

function d3_layout_bundleLeastCommonAncestor(a, b) {

  if (a === b) return a;

  var aNodes = d3_layout_bundleAncestors(a),

      bNodes = d3_layout_bundleAncestors(b),

      aNode = aNodes.pop(),

      bNode = bNodes.pop(),

      sharedNode = null;

  while (aNode === bNode) {

    sharedNode = aNode;

    aNode = aNodes.pop();

    bNode = bNodes.pop();

  }

  return sharedNode;

}