1 (function(){d3.layout = {};
2 d3.layout.chord = function() {
16 groupIndex = d3.range(n),
28 k = 0, i = -1; while (++i < n) {
29 x = 0, j = -1; while (++j < n) {
33 subgroupIndex.push(d3.range(n));
39 groupIndex.sort(function(a, b) {
40 return sortGroups(groupSums[a], groupSums[b]);
46 subgroupIndex.forEach(function(d, i) {
47 d.sort(function(a, b) {
48 return sortSubgroups(matrix[i][a], matrix[i][b]);
53 // Convert the sum to scaling factor for [0, 2pi].
54 // TODO Allow start and end angle to be specified.
55 // TODO Allow padding to be specified as percentage?
56 k = (2 * Math.PI - padding * n) / k;
58 // Compute the start and end angle for each group and subgroup.
59 x = 0, i = -1; while (++i < n) {
60 x0 = x, j = -1; while (++j < n) {
61 var di = groupIndex[i],
62 dj = subgroupIndex[i][j],
64 subgroups[di + "-" + dj] = {
81 // Generate chords for each (non-empty) subgroup-subgroup link.
82 i = -1; while (++i < n) {
83 j = i - 1; while (++j < n) {
84 var source = subgroups[i + "-" + j],
85 target = subgroups[j + "-" + i];
86 if (source.value || target.value) {
95 if (sortChords) resort();
99 chords.sort(function(a, b) {
100 a = Math.min(a.source.value, a.target.value);
101 b = Math.min(b.source.value, b.target.value);
102 return sortChords(a, b);
106 chord.matrix = function(x) {
107 if (!arguments.length) return matrix;
108 n = (matrix = x) && matrix.length;
109 chords = groups = null;
113 chord.padding = function(x) {
114 if (!arguments.length) return padding;
116 chords = groups = null;
120 chord.sortGroups = function(x) {
121 if (!arguments.length) return sortGroups;
123 chords = groups = null;
127 chord.sortSubgroups = function(x) {
128 if (!arguments.length) return sortSubgroups;
134 chord.sortChords = function(x) {
135 if (!arguments.length) return sortChords;
137 if (chords) resort();
141 chord.chords = function() {
142 if (!chords) relayout();
146 chord.groups = function() {
147 if (!groups) relayout();
153 // A rudimentary force layout using Gauss-Seidel.
154 d3.layout.force = function() {
156 event = d3.dispatch("tick"),
166 var n = distances.length,
171 l, // current distance
175 // gauss-seidel relaxation
176 for (i = 0; i < n; ++i) {
182 if (l = Math.sqrt(x * x + y * y)) {
183 l = alpha / (o.distance * o.distance) * (l - distance * o.distance) / l;
197 event.tick.dispatch({type: "tick"});
199 // simulated annealing, basically
200 return (alpha *= .99) < .005;
203 force.on = function(type, listener) {
204 event[type].add(listener);
208 force.nodes = function(x) {
209 if (!arguments.length) return nodes;
214 force.links = function(x) {
215 if (!arguments.length) return links;
220 force.size = function(x) {
221 if (!arguments.length) return size;
226 force.distance = function(d) {
227 if (!arguments.length) return distance;
232 force.start = function() {
243 for (i = 0; i < n; ++i) {
245 o.x = o.x || Math.random() * w;
246 o.y = o.y || Math.random() * h;
249 for (j = 0; j < n; ++j) {
250 paths[i][j] = Infinity;
255 for (i = 0; i < m; ++i) {
257 paths[o.source][o.target] = 1;
258 paths[o.target][o.source] = 1;
259 o.source = nodes[o.source];
260 o.target = nodes[o.target];
264 for (k = 0; k < n; ++k) {
265 for (i = 0; i < n; ++i) {
266 for (j = 0; j < n; ++j) {
267 paths[i][j] = Math.min(paths[i][j], paths[i][k] + paths[k][j]);
273 for (i = 0; i < n; ++i) {
274 for (j = i + 1; j < n; ++j) {
278 distance: paths[i][j] * paths[i][j]
283 distances.sort(function(a, b) {
284 return a.distance - b.distance;
291 force.resume = function() {
297 force.stop = function() {
302 // use `node.call(force.drag)` to make nodes draggable
303 force.drag = function() {
307 .on("mouseover", function(d) { d.fixed = true; })
308 .on("mouseout", function(d) { if (d != node) d.fixed = false; })
309 .on("mousedown", mousedown);
312 .on("mousemove", mousemove)
313 .on("mouseup", mouseup);
315 function mousedown(d) {
316 (node = d).fixed = true;
318 d3.event.preventDefault();
321 function mousemove() {
323 var m = d3.svg.mouse(element);
326 force.resume(); // restart annealing
333 node = element = null;
341 d3.layout.partition = function() {
342 var hierarchy = d3.layout.hierarchy(),
343 size = [1, 1]; // width, height
345 function position(node, x, dx, dy) {
346 var children = node.children;
348 node.y = node.depth * dy;
358 position(c = children[i], x, d = c.value * dx, dy);
364 function depth(node) {
365 var children = node.children,
370 while (++i < n) d = Math.max(d, depth(children[i]));
375 function partition(d, i) {
376 var nodes = hierarchy.call(this, d, i);
377 position(nodes[0], 0, size[0], size[1] / depth(nodes[0]));
381 partition.sort = d3.rebind(partition, hierarchy.sort);
382 partition.children = d3.rebind(partition, hierarchy.children);
383 partition.value = d3.rebind(partition, hierarchy.value);
385 partition.size = function(x) {
386 if (!arguments.length) return size;
393 d3.layout.pie = function() {
397 endAngle = 2 * Math.PI;
399 function pie(data, i) {
401 // Compute the start angle.
402 var a = +(typeof startAngle == "function"
403 ? startAngle.apply(this, arguments)
406 // Compute the angular range (end - start).
407 var k = (typeof endAngle == "function"
408 ? endAngle.apply(this, arguments)
409 : endAngle) - startAngle;
411 // Optionally sort the data.
412 var index = d3.range(data.length);
413 if (sort != null) index.sort(function(i, j) {
414 return sort(data[i], data[j]);
417 // Compute the numeric values for each data element.
418 var values = data.map(value);
420 // Convert k into a scale factor from value to angle, using the sum.
421 k /= values.reduce(function(p, d) { return p + d; }, 0);
424 var arcs = index.map(function(i) {
426 value: d = values[i],
432 // Return the arcs in the original data's order.
433 return data.map(function(d, i) {
434 return arcs[index[i]];
439 * Specifies the value function *x*, which returns a nonnegative numeric value
440 * for each datum. The default value function is `Number`. The value function
441 * is passed two arguments: the current datum and the current index.
443 pie.value = function(x) {
444 if (!arguments.length) return value;
450 * Specifies a sort comparison operator *x*. The comparator is passed two data
451 * elements from the data array, a and b; it returns a negative value if a is
452 * less than b, a positive value if a is greater than b, and zero if a equals
455 pie.sort = function(x) {
456 if (!arguments.length) return sort;
462 * Specifies the overall start angle of the pie chart. Defaults to 0. The
463 * start angle can be specified either as a constant or as a function; in the
464 * case of a function, it is evaluated once per array (as opposed to per
467 pie.startAngle = function(x) {
468 if (!arguments.length) return startAngle;
474 * Specifies the overall end angle of the pie chart. Defaults to 2Ď€. The
475 * end angle can be specified either as a constant or as a function; in the
476 * case of a function, it is evaluated once per array (as opposed to per
479 pie.endAngle = function(x) {
480 if (!arguments.length) return endAngle;
487 // data is two-dimensional array of x,y; we populate y0
488 // TODO perhaps make the `x`, `y` and `y0` structure customizable
489 d3.layout.stack = function() {
490 var order = "default",
493 function stack(data) {
500 // compute the order of series
501 var index = d3_layout_stackOrders[order](data);
503 // set y0 on the baseline
504 d3_layout_stackOffsets[offset](data, index);
506 // propagate offset to other series
507 for (j = 0; j < m; ++j) {
508 for (i = 1, y0 = data[index[0]][j].y0; i < n; ++i) {
509 data[index[i]][j].y0 = y0 += data[index[i - 1]][j].y;
516 stack.order = function(x) {
517 if (!arguments.length) return order;
522 stack.offset = function(x) {
523 if (!arguments.length) return offset;
531 var d3_layout_stackOrders = {
533 "inside-out": function(data) {
537 max = data.map(d3_layout_stackMaxIndex),
538 sums = data.map(d3_layout_stackReduceSum),
539 index = d3.range(n).sort(function(a, b) { return max[a] - max[b]; }),
544 for (i = 0; i < n; i++) {
554 return bottoms.reverse().concat(tops);
557 "reverse": function(data) {
558 return d3.range(data.length).reverse();
561 "default": function(data) {
562 return d3.range(data.length);
567 var d3_layout_stackOffsets = {
569 "silhouette": function(data, index) {
577 for (j = 0; j < m; ++j) {
578 for (i = 0, o = 0; i < n; i++) o += data[i][j].y;
579 if (o > max) max = o;
582 for (j = 0, i = index[0]; j < m; ++j) {
583 data[i][j].y0 = (max - sums[j]) / 2;
587 "wiggle": function(data, index) {
604 data[i0][0].y0 = o = o0 = 0;
605 for (j = 1; j < m; ++j) {
606 for (i = 0, s1 = 0; i < n; ++i) s1 += data[i][j].y;
607 for (i = 0, s2 = 0, dx = x[j].x - x[j - 1].x; i < n; ++i) {
608 for (k = 0, ii = index[i], s3 = (data[ii][j].y - data[ii][j - 1].y) / (2 * dx); k < i; ++k) {
609 s3 += (data[ik = index[k]][j].y - data[ik][j - 1].y) / dx;
611 s2 += s3 * data[ii][j].y;
613 data[i0][j].y0 = o -= s1 ? s2 / s1 * dx : 0;
616 for (j = 0; j < m; ++j) data[i0][j].y0 -= o0;
619 "zero": function(data, index) {
623 for (; j < m; ++j) data[i0][j].y0 = 0;
628 function d3_layout_stackReduceSum(d) {
629 return d.reduce(d3_layout_stackSum, 0);
632 function d3_layout_stackMaxIndex(array) {
639 if ((k = array[i].y) > v) {
647 function d3_layout_stackSum(p, d) {
650 d3.layout.hierarchy = function() {
651 var sort = d3_layout_hierarchySort,
652 children = d3_layout_hierarchyChildren,
653 value = d3_layout_hierarchyValue;
655 // Recursively compute the node depth and value.
656 // Also converts the data representation into a standard hierarchy structure.
657 function recurse(data, depth, nodes) {
658 var datas = children.call(hierarchy, data, depth),
659 node = {depth: depth, data: data};
664 c = node.children = [],
668 d = recurse(datas[i], j, nodes);
669 if (d.value > 0) { // ignore NaN, negative, etc.
675 if (sort) c.sort(sort);
678 node.value = value.call(hierarchy, data, depth);
683 // Recursively re-evaluates the node value.
684 function revalue(node, depth) {
685 var children = node.children,
691 while (++i < n) v += revalue(children[i], j);
693 v = value.call(hierarchy, node.data, depth);
695 return node.value = v;
698 function hierarchy(d) {
700 recurse(d, 0, nodes);
704 hierarchy.sort = function(x) {
705 if (!arguments.length) return sort;
710 hierarchy.children = function(x) {
711 if (!arguments.length) return children;
716 hierarchy.value = function(x) {
717 if (!arguments.length) return value;
722 // Re-evaluates the `value` property for the specified hierarchy.
723 hierarchy.revalue = function(root) {
731 function d3_layout_hierarchyChildren(d) {
735 function d3_layout_hierarchyValue(d) {
739 function d3_layout_hierarchySort(a, b) {
740 return b.value - a.value;
742 // Squarified Treemaps by Mark Bruls, Kees Huizing, and Jarke J. van Wijk
743 d3.layout.treemap = function() {
744 var hierarchy = d3.layout.hierarchy(),
746 size = [1, 1], // width, height
750 // Recursively compute the node area based on value & scale.
751 function scale(node, k) {
752 var children = node.children;
753 node.area = node.value * k;
757 while (++i < n) scale(children[i], k);
761 // Recursively arranges the specified node's children into squarified rows.
762 function squarify(node) {
763 if (!node.children) return;
764 var rect = {x: node.x, y: node.y, dx: node.dx, dy: node.dy},
766 children = node.children.slice(), // copy-on-write
768 best = Infinity, // the best row score so far
769 score, // the current row score
770 u = Math.min(rect.dx, rect.dy), // initial orientation
773 while ((n = children.length) > 0) {
774 row.push(child = children[n - 1]);
775 row.area += child.area;
776 if ((score = worst(row, u)) <= best) { // continue with this orientation
779 } else { // abort, and try a different orientation
780 row.area -= row.pop().area;
781 position(row, u, rect, false);
782 u = Math.min(rect.dx, rect.dy);
783 row.length = row.area = 0;
788 position(row, u, rect, true);
789 row.length = row.area = 0;
791 node.children.forEach(squarify);
794 // Recursively resizes the specified node's children into existing rows.
795 // Preserves the existing layout!
796 function stickify(node) {
797 if (!node.children) return;
798 var rect = {x: node.x, y: node.y, dx: node.dx, dy: node.dy},
799 children = node.children.slice(), // copy-on-write
803 while (child = children.pop()) {
805 row.area += child.area;
806 if (child.z != null) {
807 position(row, child.z ? rect.dx : rect.dy, rect, !children.length);
808 row.length = row.area = 0;
811 node.children.forEach(stickify);
814 // Computes the score for the specified row, as the worst aspect ratio.
815 function worst(row, u) {
824 if (r < rmin) rmin = r;
825 if (r > rmax) rmax = r;
829 return Math.max((u * rmax) / s, s / (u * rmin));
832 // Positions the specified row of nodes. Modifies `rect`.
833 function position(row, u, rect, flush) {
838 v = u ? round(row.area / u) : 0,
840 if (u == rect.dx) { // horizontal subdivision
841 if (flush || v > rect.dy) v = rect.dy; // over+underflow
847 x += o.dx = round(o.area / v);
850 o.dx += rect.x + rect.dx - x; // rounding error
853 } else { // vertical subdivision
854 if (flush || v > rect.dx) v = rect.dx; // over+underflow
860 y += o.dy = round(o.area / v);
863 o.dy += rect.y + rect.dy - y; // rounding error
869 function treemap(d) {
870 var nodes = stickies || hierarchy(d),
876 if (stickies) hierarchy.revalue(root);
877 scale(root, size[0] * size[1] / root.value);
878 (stickies ? stickify : squarify)(root);
879 if (sticky) stickies = nodes;
883 treemap.sort = d3.rebind(treemap, hierarchy.sort);
884 treemap.children = d3.rebind(treemap, hierarchy.children);
885 treemap.value = d3.rebind(treemap, hierarchy.value);
887 treemap.size = function(x) {
888 if (!arguments.length) return size;
893 treemap.round = function(x) {
894 if (!arguments.length) return round != Number;
895 round = x ? Math.round : Number;
899 treemap.sticky = function(x) {
900 if (!arguments.length) return sticky;