Skip to content

Commit 60b6a3d

Browse files
mbostockmbostock
committed
Simplify cluster layout.
The `cluster` layout is now more similar to the `tree` layout, using a separation function rather than a group property. In addition, the breadth and depth properties are replaced with x and y, respectively, and scaled according to the size of the layout. I've updated the examples to make them more consistent, as well, including the pretty Bézier curves. In a future commit I'd like to take some of the duplicate code in the examples and move that into reusable methods.
1 parent 776f332 commit 60b6a3d

7 files changed

Lines changed: 157 additions & 207 deletions

File tree

‎d3.layout.js‎

Lines changed: 49 additions & 77 deletions
Original file line numberDiff line numberDiff line change
@@ -742,64 +742,40 @@ function d3_layout_hierarchySort(a, b) {
742742
// Implements a hierarchical layout using the cluster (or dendogram) algorithm.
743743
d3.layout.cluster = function() {
744744
var hierarchy = d3.layout.hierarchy(),
745-
group = 0;
745+
separation = d3_layout_treeSeparation,
746+
size = [1, 1]; // width, height
746747

747748
function cluster(d, i) {
748749
var nodes = hierarchy.call(this, d, i),
749750
root = nodes[0],
750-
leafCount = 0,
751-
leafIndex = .5 - group / 2;
752-
753-
/* Count the leaf nodes and compute the depth of descendants. */
754-
var p = undefined;
755-
d3_layout_clusterVisitAfter(root, function(n) {
756-
if (n.children) {
757-
n.depth = 1 + d3.max(n.children, function(n) { return n.depth; });
758-
} else {
759-
if (group && (p != n.parent)) {
760-
p = n.parent;
761-
leafCount += group;
762-
}
763-
leafCount++;
764-
n.depth = 0;
765-
}
766-
});
767-
var breadth = 1 / leafCount;
768-
var depth = 1 / root.depth;
769-
770-
/* Compute the unit breadth and depth of each node. */
771-
var p = undefined;
772-
d3_layout_clusterVisitAfter(root, function(n) {
773-
if (n.children) {
774-
n.breadth = d3_layout_clusterMean(n.children, function(n) { return n.breadth; });
751+
previousNode,
752+
x = 0,
753+
kx,
754+
ky;
755+
756+
// First walk, computing the initial x & y values.
757+
d3_layout_treeVisitAfter(root, function(node) {
758+
if (node.children) {
759+
node.x = d3_layout_clusterX(node.children);
760+
node.y = d3_layout_clusterY(node.children);
775761
} else {
776-
if (group && (p != n.parent)) {
777-
p = n.parent;
778-
leafIndex += group;
779-
}
780-
n.breadth = breadth * leafIndex++;
762+
node.x = previousNode ? x += separation(node, previousNode) : 0;
763+
node.y = 0;
764+
previousNode = node;
781765
}
782-
n.depth = 1 - n.depth * depth;
783766
});
784767

785-
/* Compute breadth and depth ranges for space-filling layouts. */
786-
d3_layout_clusterVisitAfter(root, function(n) {
787-
n.minBreadth = n.children
788-
? n.children[0].minBreadth
789-
: (n.breadth - breadth / 2);
790-
n.maxBreadth = n.children
791-
? n.children[n.children.length - 1].maxBreadth
792-
: (n.breadth + breadth / 2);
793-
});
794-
d3_layout_clusterVisitBefore(root, function(n) {
795-
n.minDepth = n.parent
796-
? n.parent.maxDepth
797-
: 0;
798-
n.maxDepth = n.parent
799-
? (n.depth + root.depth)
800-
: (n.minDepth + 2 * root.depth);
768+
// Compute the left-most, right-most, and depth-most nodes for extents.
769+
var left = d3_layout_clusterLeft(root),
770+
right = d3_layout_clusterRight(root),
771+
x0 = left.x - separation(left, right) / 2,
772+
x1 = right.x + separation(right, left) / 2;
773+
774+
// Second walk, normalizing x & y to the desired size.
775+
d3_layout_treeVisitAfter(root, function(node) {
776+
node.x = (node.x - x0) / (x1 - x0) * size[0];
777+
node.y = (1 - node.y / root.y) * size[1];
801778
});
802-
root.minDepth = -depth;
803779

804780
return nodes;
805781
}
@@ -808,45 +784,41 @@ d3.layout.cluster = function() {
808784
cluster.children = d3.rebind(cluster, hierarchy.children);
809785
cluster.value = d3.rebind(cluster, hierarchy.value);
810786

811-
cluster.group = function(x) {
812-
if (!arguments.length) return group;
813-
group = x;
787+
cluster.separation = function(x) {
788+
if (!arguments.length) return separation;
789+
separation = x;
790+
return cluster;
791+
};
792+
793+
cluster.size = function(x) {
794+
if (!arguments.length) return size;
795+
size = x;
814796
return cluster;
815797
};
816798

817799
return cluster;
818800
};
819801

820-
d3_layout_clusterVisitAfter = d3_layout_treeVisitAfter;
802+
function d3_layout_clusterY(children) {
803+
return 1 + d3.max(children, function(child) {
804+
return child.y;
805+
});
806+
}
821807

822-
function d3_layout_clusterVisitBefore(node, callback) {
823-
function visit(node, previousSibling) {
824-
callback(node, previousSibling);
825-
var children = node.children;
826-
if (children) {
827-
var child,
828-
previousChild = null,
829-
i = -1,
830-
n = children.length;
831-
while (++i < n) {
832-
child = children[i];
833-
visit(child, previousChild);
834-
previousChild = child;
835-
}
836-
}
837-
}
838-
visit(node, null);
808+
function d3_layout_clusterX(children) {
809+
return children.reduce(function(x, child) {
810+
return x + child.x;
811+
}, 0) / children.length;
839812
}
840813

841-
function d3_layout_clusterSum(array, f) {
842-
var o = {};
843-
return array.reduce(f
844-
? function(p, d, i) { o.index = i; return p + f.call(o, d); }
845-
: function(p, d) { return p + d; }, 0);
814+
function d3_layout_clusterLeft(node) {
815+
var children = node.children;
816+
return children ? d3_layout_clusterLeft(children[0]) : node;
846817
}
847818

848-
function d3_layout_clusterMean(array, f) {
849-
return d3_layout_clusterSum(array, f) / array.length;
819+
function d3_layout_clusterRight(node) {
820+
var children = node.children;
821+
return children ? d3_layout_clusterRight(children[children.length - 1]) : node;
850822
}
851823
// Node-link tree diagram using the Reingold-Tilford "tidy" algorithm
852824
d3.layout.tree = function() {

‎d3.layout.min.js‎

Lines changed: 1 addition & 1 deletion
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎examples/cluster/cluster-radial.js‎

Lines changed: 18 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -1,47 +1,43 @@
1-
var w = 800,
2-
h = 800,
3-
m = 120;
1+
var r = 960 / 2;
42

53
var cluster = d3.layout.cluster()
4+
.size([360, r - 120])
65
.sort(null)
7-
.group(true)
86
.children(function(d) { return isNaN(d.value) ? d3.entries(d.value) : null; });
97

108
var vis = d3.select("#chart").append("svg:svg")
11-
.attr("width", w + 2 * m)
12-
.attr("height", h + 2 * m)
9+
.attr("width", r * 2)
10+
.attr("height", r * 2)
1311
.append("svg:g")
14-
.attr("transform", "translate(" + (w / 2 + m) + "," + (h / 2 + m) +")");
12+
.attr("transform", "translate(" + r + "," + r + ")");
1513

1614
d3.json("flare.json", function(json) {
1715
var nodes = cluster(d3.entries(json)[0]);
1816

1917
var link = vis.selectAll("g.link")
2018
.data(nodes)
2119
.enter().append("svg:g")
22-
.attr("class", "link")
23-
.selectAll("line")
24-
.data(children)
25-
.enter();
20+
.attr("class", "link");
2621

27-
link.append("svg:path")
22+
link.selectAll("path")
23+
.data(children)
24+
.enter().append("svg:path")
2825
.attr("d", path);
2926

3027
var node = vis.selectAll("g.node")
3128
.data(nodes)
3229
.enter().append("svg:g")
3330
.attr("class", "node")
34-
.attr("transform", function(d) { return "translate(" + x(d) + "," + y(d) + ")rotate(" + (a(d)-90) + ")"; })
31+
.attr("transform", function(d) { return "rotate(" + (d.x - 90) + ")translate(" + d.y + ")"; })
3532

3633
node.append("svg:circle")
3734
.attr("r", 4.5);
3835

3936
node.append("svg:text")
40-
.attr("dx", function(d) { return a(d) < 180 ? 8 : -8; })
37+
.attr("dx", function(d) { return d.x < 180 ? 8 : -8; })
4138
.attr("dy", ".31em")
42-
.attr("text-anchor", function(d) { return a(d) < 180 ? "start" : "end"; })
43-
.attr("transform", function(d) { return a(d) < 180 ? null : "rotate(180)"; })
44-
//.attr("transform", function(d) { return "rotate(" + (a(d.breadth) - 90) + ")"; })
39+
.attr("text-anchor", function(d) { return d.x < 180 ? "start" : "end"; })
40+
.attr("transform", function(d) { return d.x < 180 ? null : "rotate(180)"; })
4541
.text(function(d) { return d.data.key; });
4642

4743
// Returns parent+child objects for any children of `d`.
@@ -56,20 +52,18 @@ d3.json("flare.json", function(json) {
5652

5753
// Computes a pretty Bézier curve from parent to child. TODO reusable helper?
5854
function path(d) {
59-
var depth = (d.parent.depth + d.child.depth) / 2,
55+
var y0 = (d.parent.y + d.child.y) / 2,
6056
p0 = d.parent,
6157
p3 = d.child,
62-
p1 = {breadth: p0.breadth, depth: depth},
63-
p2 = {breadth: p3.breadth, depth: depth};
58+
p1 = {x: p0.x, y: y0},
59+
p2 = {x: p3.x, y: y0};
6460
return "M" + x(p0) + "," + y(p0)
6561
+ "C" + x(p1) + "," + y(p1)
6662
+ " " + x(p2) + "," + y(p2)
6763
+ " " + x(p3) + "," + y(p3);
6864
}
6965

7066
// Radial scales for x and y.
71-
function a(d) { return d.breadth * 360; }
72-
function r(d) { return d.depth * w / 2; }
73-
function x(d) { return r(d) * Math.cos((a(d) - 90) / 180 * Math.PI); }
74-
function y(d) { return r(d) * Math.sin((a(d) - 90) / 180 * Math.PI); }
67+
function x(d) { return d.y * Math.cos((d.x - 90) / 180 * Math.PI); }
68+
function y(d) { return d.y * Math.sin((d.x - 90) / 180 * Math.PI); }
7569
});

‎examples/cluster/cluster.js‎

Lines changed: 23 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -1,15 +1,13 @@
1-
var w = 200,
2-
h = 2200,
3-
x = d3.scale.linear().range([0, w]),
4-
y = d3.scale.linear().range([0, h]);
1+
var w = 960,
2+
h = 2200;
53

64
var cluster = d3.layout.cluster()
5+
.size([h, w - 160])
76
.sort(null)
8-
.group(true)
97
.children(function(d) { return isNaN(d.value) ? d3.entries(d.value) : null; });
108

119
var vis = d3.select("#chart").append("svg:svg")
12-
.attr("width", w + 40 + 120)
10+
.attr("width", w)
1311
.attr("height", h)
1412
.append("svg:g")
1513
.attr("transform", "translate(40, 0)");
@@ -20,27 +18,18 @@ d3.json("flare.json", function(json) {
2018
var link = vis.selectAll("g.link")
2119
.data(nodes)
2220
.enter().append("svg:g")
23-
.attr("class", "link")
24-
.selectAll("line")
21+
.attr("class", "link");
22+
23+
link.selectAll("path")
2524
.data(children)
26-
.enter();
27-
28-
link.append("svg:line")
29-
.attr("x1", function(d) { return x(d.parent.depth); })
30-
.attr("y1", function(d) { return y(d.parent.breadth); })
31-
.attr("x2", function(d) { return x(d.parent.depth); })
32-
.attr("y2", function(d) { return y(d.child.breadth); });
33-
link.append("svg:line")
34-
.attr("x1", function(d) { return x(d.parent.depth); })
35-
.attr("y1", function(d) { return y(d.child.breadth); })
36-
.attr("x2", function(d) { return x(d.child.depth); })
37-
.attr("y2", function(d) { return y(d.child.breadth); });
25+
.enter().append("svg:path")
26+
.attr("d", path);
3827

3928
var node = vis.selectAll("g.node")
4029
.data(nodes)
4130
.enter().append("svg:g")
4231
.attr("class", "node")
43-
.attr("transform", function(d) { return "translate(" + x(d.depth) + "," + y(d.breadth) + ")"; })
32+
.attr("transform", function(d) { return "translate(" + d.y + "," + d.x + ")"; })
4433

4534
node.append("svg:circle")
4635
.attr("r", 4.5);
@@ -60,4 +49,17 @@ d3.json("flare.json", function(json) {
6049
};
6150
});
6251
}
52+
53+
// Computes a pretty Bézier curve from parent to child. TODO reusable helper?
54+
function path(d) {
55+
var y = (d.parent.y + d.child.y) / 2,
56+
p0 = d.parent,
57+
p3 = d.child,
58+
p1 = {x: p0.x, y: y},
59+
p2 = {x: p3.x, y: y};
60+
return "M" + p0.y + "," + p0.x
61+
+ "C" + p1.y + "," + p1.x
62+
+ " " + p2.y + "," + p2.x
63+
+ " " + p3.y + "," + p3.x;
64+
}
6365
});

‎examples/tree/tree-radial.js‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -32,13 +32,13 @@ d3.json("flare.json", function(json) {
3232
.attr("transform", function(d) { return "rotate(" + (d.x - 90) + ")translate(" + d.y + ")"; })
3333

3434
node.append("svg:circle")
35-
.attr("r", 5);
35+
.attr("r", 4.5);
3636

3737
node.append("svg:text")
3838
.attr("dx", function(d) { return d.x < 180 ? 8 : -8; })
3939
.attr("dy", ".31em")
4040
.attr("text-anchor", function(d) { return d.x < 180 ? "start" : "end"; })
41-
.attr("transform", function(d) { return (d.x < 180) ^ (d.children) ? null : "rotate(180)"; })
41+
.attr("transform", function(d) { return d.x < 180 ? null : "rotate(180)"; })
4242
.text(function(d) { return d.data.key; });
4343

4444
// Returns parent+child objects for any children of `d`.

‎examples/tree/tree.js‎

Lines changed: 17 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -20,13 +20,10 @@ d3.json("flare.json", function(json) {
2020
.enter().append("svg:g")
2121
.attr("class", "link");
2222

23-
link.selectAll("line")
23+
link.selectAll("path")
2424
.data(children)
25-
.enter().append("svg:line")
26-
.attr("x1", function(d) { return d.parent.y; })
27-
.attr("y1", function(d) { return d.parent.x; })
28-
.attr("x2", function(d) { return d.child.y; })
29-
.attr("y2", function(d) { return d.child.x; });
25+
.enter().append("svg:path")
26+
.attr("d", path);
3027

3128
var node = vis.selectAll("g.node")
3229
.data(nodes)
@@ -35,7 +32,7 @@ d3.json("flare.json", function(json) {
3532
.attr("transform", function(d) { return "translate(" + d.y + "," + d.x + ")"; })
3633

3734
node.append("svg:circle")
38-
.attr("r", 5);
35+
.attr("r", 4.5);
3936

4037
node.append("svg:text")
4138
.attr("dx", function(d) { return d.children ? -8 : 8; })
@@ -52,4 +49,17 @@ d3.json("flare.json", function(json) {
5249
};
5350
});
5451
}
52+
53+
// Computes a pretty Bézier curve from parent to child. TODO reusable helper?
54+
function path(d) {
55+
var y = (d.parent.y + d.child.y) / 2,
56+
p0 = d.parent,
57+
p3 = d.child,
58+
p1 = {x: p0.x, y: y},
59+
p2 = {x: p3.x, y: y};
60+
return "M" + p0.y + "," + p0.x
61+
+ "C" + p1.y + "," + p1.x
62+
+ " " + p2.y + "," + p2.x
63+
+ " " + p3.y + "," + p3.x;
64+
}
5565
});

0 commit comments

Comments
 (0)