import “layout”;
// 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;
}