1 // Implements a hierarchical layout using the cluster (or dendogram) algorithm.

     2 d3.layout.cluster = function() {

     3   var hierarchy = d3.layout.hierarchy().sort(null).value(null),

     4       separation = d3_layout_treeSeparation,

     5       size = [1, 1]; // width, height

     6 

     7   function cluster(d, i) {

     8     var nodes = hierarchy.call(this, d, i),

     9         root = nodes[0],

    10         previousNode,

    11         x = 0,

    12         kx,

    13         ky;

    14 

    15     // First walk, computing the initial x & y values.

    16     d3_layout_treeVisitAfter(root, function(node) {

    17       var children = node.children;

    18       if (children && children.length) {

    19         node.x = d3_layout_clusterX(children);

    20         node.y = d3_layout_clusterY(children);

    21       } else {

    22         node.x = previousNode ? x += separation(node, previousNode) : 0;

    23         node.y = 0;

    24         previousNode = node;

    25       }

    26     });

    27 

    28     // Compute the left-most, right-most, and depth-most nodes for extents.

    29     var left = d3_layout_clusterLeft(root),

    30         right = d3_layout_clusterRight(root),

    31         x0 = left.x - separation(left, right) / 2,

    32         x1 = right.x + separation(right, left) / 2;

    33 

    34     // Second walk, normalizing x & y to the desired size.

    35     d3_layout_treeVisitAfter(root, function(node) {

    36       node.x = (node.x - x0) / (x1 - x0) * size[0];

    37       node.y = (1 - node.y / root.y) * size[1];

    38     });

    39 

    40     return nodes;

    41   }

    42 

    43   cluster.separation = function(x) {

    44     if (!arguments.length) return separation;

    45     separation = x;

    46     return cluster;

    47   };

    48 

    49   cluster.size = function(x) {

    50     if (!arguments.length) return size;

    51     size = x;

    52     return cluster;

    53   };

    54 

    55   return d3_layout_hierarchyRebind(cluster, hierarchy);

    56 };

    57 

    58 function d3_layout_clusterY(children) {

    59   return 1 + d3.max(children, function(child) {

    60     return child.y;

    61   });

    62 }

    63 

    64 function d3_layout_clusterX(children) {

    65   return children.reduce(function(x, child) {

    66     return x + child.x;

    67   }, 0) / children.length;

    68 }

    69 

    70 function d3_layout_clusterLeft(node) {

    71   var children = node.children;

    72   return children && children.length ? d3_layout_clusterLeft(children[0]) : node;

    73 }

    74 

    75 function d3_layout_clusterRight(node) {

    76   var children = node.children, n;

    77   return children && (n = children.length) ? d3_layout_clusterRight(children[n - 1]) : node;

    78 }