Skip to content

Commit 915be32

Browse files
mbostockmbostock
committed
Merge branch 'tree'
2 parents a262ba7 + 597443b commit 915be32

14 files changed

Lines changed: 924 additions & 4 deletions

File tree

‎Makefile‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -105,6 +105,7 @@ d3.layout.js: \
105105
src/layout/pie.js \
106106
src/layout/stack.js \
107107
src/layout/hierarchy.js \
108+
src/layout/tree.js \
108109
src/layout/treemap.js \
109110
src/end.js
110111

‎d3.js‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
(function(){d3 = {version: "1.9.1"}; // semver
1+
(function(){d3 = {version: "1.10.0"}; // semver
22
if (!Date.now) Date.now = function() {
33
return +new Date();
44
};

‎d3.layout.js‎

Lines changed: 238 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -739,6 +739,244 @@ function d3_layout_hierarchyValue(d) {
739739
function d3_layout_hierarchySort(a, b) {
740740
return b.value - a.value;
741741
}
742+
// Node-link tree diagram using the Reingold-Tilford "tidy" algorithm
743+
d3.layout.tree = function() {
744+
var hierarchy = d3.layout.hierarchy(),
745+
separation = d3_layout_treeSeparation,
746+
size = [1, 1]; // width, height
747+
748+
function tree(d, i) {
749+
var nodes = hierarchy.call(this, d, i),
750+
root = nodes[0];
751+
752+
function firstWalk(node, previousSibling) {
753+
var children = node.children,
754+
layout = node._tree;
755+
if (children) {
756+
var n = children.length,
757+
firstChild = children[0],
758+
previousChild,
759+
ancestor = firstChild,
760+
child,
761+
i = -1;
762+
while (++i < n) {
763+
child = children[i];
764+
firstWalk(child, previousChild);
765+
ancestor = apportion(child, previousChild, ancestor);
766+
previousChild = child;
767+
}
768+
d3_layout_treeShift(node);
769+
var midpoint = .5 * (firstChild._tree.prelim + child._tree.prelim);
770+
if (previousSibling) {
771+
layout.prelim = previousSibling._tree.prelim + separation(node, previousSibling);
772+
layout.mod = layout.prelim - midpoint;
773+
} else {
774+
layout.prelim = midpoint;
775+
}
776+
} else {
777+
if (previousSibling) {
778+
layout.prelim = previousSibling._tree.prelim + separation(node, previousSibling);
779+
}
780+
}
781+
}
782+
783+
function secondWalk(node, x) {
784+
node.x = node._tree.prelim + x;
785+
var children = node.children;
786+
if (children) {
787+
var i = -1,
788+
n = children.length;
789+
x += node._tree.mod;
790+
while (++i < n) {
791+
secondWalk(children[i], x);
792+
}
793+
}
794+
}
795+
796+
function apportion(node, previousSibling, ancestor) {
797+
if (previousSibling) {
798+
var vip = node,
799+
vop = node,
800+
vim = previousSibling,
801+
vom = node.parent.children[0],
802+
sip = vip._tree.mod,
803+
sop = vop._tree.mod,
804+
sim = vim._tree.mod,
805+
som = vom._tree.mod,
806+
shift;
807+
while (vim = d3_layout_treeRight(vim), vip = d3_layout_treeLeft(vip), vim && vip) {
808+
vom = d3_layout_treeLeft(vom);
809+
vop = d3_layout_treeRight(vop);
810+
vop._tree.ancestor = node;
811+
shift = vim._tree.prelim + sim - vip._tree.prelim - sip + separation(vim, vip);
812+
if (shift > 0) {
813+
d3_layout_treeMove(d3_layout_treeAncestor(vim, node, ancestor), node, shift);
814+
sip += shift;
815+
sop += shift;
816+
}
817+
sim += vim._tree.mod;
818+
sip += vip._tree.mod;
819+
som += vom._tree.mod;
820+
sop += vop._tree.mod;
821+
}
822+
if (vim && !d3_layout_treeRight(vop)) {
823+
vop._tree.thread = vim;
824+
vop._tree.mod += sim - sop;
825+
}
826+
if (vip && !d3_layout_treeLeft(vom)) {
827+
vom._tree.thread = vip;
828+
vom._tree.mod += sip - som;
829+
ancestor = node;
830+
}
831+
}
832+
return ancestor;
833+
}
834+
835+
// Initialize temporary layout variables.
836+
d3_layout_treeVisitAfter(root, function(node, previousSibling) {
837+
node._tree = {
838+
ancestor: node,
839+
prelim: 0,
840+
mod: 0,
841+
change: 0,
842+
shift: 0,
843+
number: previousSibling ? previousSibling._tree.number + 1 : 0
844+
};
845+
});
846+
847+
// Compute the layout using Buchheim et al.'s algorithm.
848+
firstWalk(root);
849+
secondWalk(root, -root._tree.prelim);
850+
851+
// Compute the left-most, right-most, and depth-most nodes for extents.
852+
var left = d3_layout_treeSearch(root, d3_layout_treeLeftmost),
853+
right = d3_layout_treeSearch(root, d3_layout_treeRightmost),
854+
deep = d3_layout_treeSearch(root, d3_layout_treeDeepest),
855+
x0 = left.x - separation(left, right) / 2,
856+
x1 = right.x + separation(right, left) / 2,
857+
y1 = deep.depth;
858+
859+
// Clear temporary layout variables; transform x and y.
860+
d3_layout_treeVisitAfter(root, function(node) {
861+
node.x = (node.x - x0) / (x1 - x0) * size[0];
862+
node.y = node.depth / y1 * size[1];
863+
delete node._tree;
864+
});
865+
866+
return nodes;
867+
}
868+
869+
tree.sort = d3.rebind(tree, hierarchy.sort);
870+
tree.children = d3.rebind(tree, hierarchy.children);
871+
tree.value = d3.rebind(tree, hierarchy.value);
872+
873+
tree.separation = function(x) {
874+
if (!arguments.length) return separation;
875+
separation = x;
876+
return tree;
877+
};
878+
879+
tree.size = function(x) {
880+
if (!arguments.length) return size;
881+
size = x;
882+
return tree;
883+
};
884+
885+
return tree;
886+
};
887+
888+
function d3_layout_treeSeparation(a, b) {
889+
return a.parent == b.parent ? 1 : 2;
890+
}
891+
892+
// function d3_layout_treeSeparationRadial(a, b) {
893+
// return (a.parent == b.parent ? 1 : 2) / a.depth;
894+
// }
895+
896+
function d3_layout_treeLeft(node) {
897+
return node.children ? node.children[0] : node._tree.thread;
898+
}
899+
900+
function d3_layout_treeRight(node) {
901+
return node.children ? node.children[node.children.length - 1] : node._tree.thread;
902+
}
903+
904+
function d3_layout_treeSearch(node, compare) {
905+
var children = node.children;
906+
if (children) {
907+
var child,
908+
n = children.length,
909+
i = -1;
910+
while (++i < n) {
911+
if (compare(child = d3_layout_treeSearch(children[i], compare), node) > 0) {
912+
node = child;
913+
}
914+
}
915+
}
916+
return node;
917+
}
918+
919+
function d3_layout_treeRightmost(a, b) {
920+
return a.x - b.x;
921+
}
922+
923+
function d3_layout_treeLeftmost(a, b) {
924+
return b.x - a.x;
925+
}
926+
927+
function d3_layout_treeDeepest(a, b) {
928+
return a.depth - b.depth;
929+
}
930+
931+
function d3_layout_treeVisitAfter(node, callback) {
932+
function visit(node, previousSibling) {
933+
var children = node.children;
934+
if (children) {
935+
var child,
936+
previousChild = null,
937+
i = -1,
938+
n = children.length;
939+
while (++i < n) {
940+
child = children[i];
941+
visit(child, previousChild);
942+
previousChild = child;
943+
}
944+
}
945+
callback(node, previousSibling);
946+
}
947+
visit(node, null);
948+
}
949+
950+
function d3_layout_treeShift(node) {
951+
var shift = 0,
952+
change = 0,
953+
children = node.children,
954+
i = children.length,
955+
child;
956+
while (--i >= 0) {
957+
child = children[i]._tree;
958+
child.prelim += shift;
959+
child.mod += shift;
960+
shift += child.shift + (change += child.change);
961+
}
962+
}
963+
964+
function d3_layout_treeMove(ancestor, node, shift) {
965+
ancestor = ancestor._tree;
966+
node = node._tree;
967+
var change = shift / (node.number - ancestor.number);
968+
ancestor.change += change;
969+
node.change -= change;
970+
node.shift += shift;
971+
node.prelim += shift;
972+
node.mod += shift;
973+
}
974+
975+
function d3_layout_treeAncestor(vim, node, ancestor) {
976+
return vim._tree.ancestor.parent == node.parent
977+
? vim._tree.ancestor
978+
: ancestor;
979+
}
742980
// Squarified Treemaps by Mark Bruls, Kees Huizing, and Jarke J. van Wijk
743981
d3.layout.treemap = function() {
744982
var hierarchy = d3.layout.hierarchy(),

‎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.

‎d3.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/index.html‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -35,6 +35,8 @@
3535
<li><a href="stream/stream.html">stream</a></li>
3636
<li><a href="stream/stack.html">stack</a></li>
3737
<li><a href="symbol-map/symbol-map.html">symbol-map</a></li>
38+
<li><a href="tree/tree.html">tree</a></li>
39+
<li><a href="tree/tree-radial.html">tree-radial</a></li>
3840
<li><a href="treemap/treemap.html">treemap</a></li>
3941
<li><a href="voronoi/voronoi.html">voronoi</a></li>
4042
<li><a href="zoom/zoom.html">zoom</a></li>

0 commit comments

Comments
 (0)