1 d3.sankey = function() {
9 sankey.nodeWidth = function(_) {
10 if (!arguments.length) return nodeWidth;
15 sankey.nodePadding = function(_) {
16 if (!arguments.length) return nodePadding;
21 sankey.nodes = function(_) {
22 if (!arguments.length) return nodes;
27 sankey.links = function(_) {
28 if (!arguments.length) return links;
33 sankey.size = function(_) {
34 if (!arguments.length) return size;
39 sankey.layout = function(iterations) {
42 computeNodeBreadths();
43 computeNodeDepths(iterations);
48 sankey.relayout = function() {
53 sankey.link = function() {
57 var x0 = d.source.x + d.source.dx,
59 xi = d3.interpolateNumber(x0, x1),
61 x3 = xi(1 - curvature),
62 y0 = d.source.y + d.sy + d.dy / 2,
63 y1 = d.target.y + d.ty + d.dy / 2;
64 return "M" + x0 + "," + y0
67 + " " + x1 + "," + y1;
70 link.curvature = function(_) {
71 if (!arguments.length) return curvature;
79 // Populate the sourceLinks and targetLinks for each node.
80 // Also, if the source and target are not objects, assume they are indices.
81 function computeNodeLinks() {
82 nodes.forEach(function(node) {
83 node.sourceLinks = [];
84 node.targetLinks = [];
86 links.forEach(function(link) {
87 var source = link.source,
89 if (typeof source === "number") source = link.source = nodes[link.source];
90 if (typeof target === "number") target = link.target = nodes[link.target];
91 source.sourceLinks.push(link);
92 target.targetLinks.push(link);
96 // Compute the value (size) of each node by summing the associated links.
97 function computeNodeValues() {
98 nodes.forEach(function(node) {
99 node.value = Math.max(
100 d3.sum(node.sourceLinks, value),
101 d3.sum(node.targetLinks, value)
106 // Iteratively assign the breadth (x-position) for each node.
107 // Nodes are assigned the maximum breadth of incoming neighbors plus one;
108 // nodes with no incoming links are assigned breadth zero, while
109 // nodes with no outgoing links are assigned the maximum breadth.
110 function computeNodeBreadths() {
111 var remainingNodes = nodes,
115 while (remainingNodes.length) {
117 remainingNodes.forEach(function(node) {
120 node.sourceLinks.forEach(function(link) {
121 nextNodes.push(link.target);
124 remainingNodes = nextNodes;
130 scaleNodeBreadths((size[0] - nodeWidth) / (x - 1));
133 function moveSourcesRight() {
134 nodes.forEach(function(node) {
135 if (!node.targetLinks.length) {
136 node.x = d3.min(node.sourceLinks, function(d) { return d.target.x; }) - 1;
141 function moveSinksRight(x) {
142 nodes.forEach(function(node) {
143 if (!node.sourceLinks.length) {
149 function scaleNodeBreadths(kx) {
150 nodes.forEach(function(node) {
155 function computeNodeDepths(iterations) {
156 var nodesByBreadth = d3.nest()
157 .key(function(d) { return d.x; })
158 .sortKeys(d3.ascending)
160 .map(function(d) { return d.values; });
163 initializeNodeDepth();
165 for (var alpha = 1; iterations > 0; --iterations) {
166 relaxRightToLeft(alpha *= .99);
168 relaxLeftToRight(alpha);
172 function initializeNodeDepth() {
173 var ky = d3.min(nodesByBreadth, function(nodes) {
174 return (size[1] - (nodes.length - 1) * nodePadding) / d3.sum(nodes, value);
177 nodesByBreadth.forEach(function(nodes) {
178 nodes.forEach(function(node, i) {
180 node.dy = node.value * ky;
184 links.forEach(function(link) {
185 link.dy = link.value * ky;
189 function relaxLeftToRight(alpha) {
190 nodesByBreadth.forEach(function(nodes, breadth) {
191 nodes.forEach(function(node) {
192 if (node.targetLinks.length) {
193 var y = d3.sum(node.targetLinks, weightedSource) / d3.sum(node.targetLinks, value);
194 node.y += (y - center(node)) * alpha;
199 function weightedSource(link) {
200 return center(link.source) * link.value;
204 function relaxRightToLeft(alpha) {
205 nodesByBreadth.slice().reverse().forEach(function(nodes) {
206 nodes.forEach(function(node) {
207 if (node.sourceLinks.length) {
208 var y = d3.sum(node.sourceLinks, weightedTarget) / d3.sum(node.sourceLinks, value);
209 node.y += (y - center(node)) * alpha;
214 function weightedTarget(link) {
215 return center(link.target) * link.value;
219 function resolveCollisions() {
220 nodesByBreadth.forEach(function(nodes) {
227 // Push any overlapping nodes down.
228 nodes.sort(ascendingDepth);
229 for (i = 0; i < n; ++i) {
232 if (dy > 0) node.y += dy;
233 y0 = node.y + node.dy + nodePadding;
236 // If the bottommost node goes outside the bounds, push it back up.
237 dy = y0 - nodePadding - size[1];
241 // Push any overlapping nodes back up.
242 for (i = n - 2; i >= 0; --i) {
244 dy = node.y + node.dy + nodePadding - y0;
245 if (dy > 0) node.y -= dy;
252 function ascendingDepth(a, b) {
257 function computeLinkDepths() {
258 nodes.forEach(function(node) {
259 node.sourceLinks.sort(ascendingTargetDepth);
260 node.targetLinks.sort(ascendingSourceDepth);
262 nodes.forEach(function(node) {
264 node.sourceLinks.forEach(function(link) {
268 node.targetLinks.forEach(function(link) {
274 function ascendingSourceDepth(a, b) {
275 return a.source.y - b.source.y;
278 function ascendingTargetDepth(a, b) {
279 return a.target.y - b.target.y;
283 function center(node) {
284 return node.y + node.dy / 2;
287 function value(link) {