sankey.js 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566
  1. d3.sankey = function() {
  2. var sankey = {},
  3. nodeWidth = 24,
  4. nodePadding = 8,
  5. size = [1, 1],
  6. nodes = [],
  7. links = [],
  8. components = [];
  9. sankey.nodeWidth = function(_) {
  10. if (!arguments.length) return nodeWidth;
  11. nodeWidth = +_;
  12. return sankey;
  13. };
  14. sankey.nodePadding = function(_) {
  15. if (!arguments.length) return nodePadding;
  16. nodePadding = +_;
  17. return sankey;
  18. };
  19. sankey.nodes = function(_) {
  20. if (!arguments.length) return nodes;
  21. nodes = _;
  22. return sankey;
  23. };
  24. sankey.links = function(_) {
  25. if (!arguments.length) return links;
  26. links = _;
  27. return sankey;
  28. };
  29. sankey.size = function(_) {
  30. if (!arguments.length) return size;
  31. size = _;
  32. return sankey;
  33. };
  34. sankey.layout = function(iterations) {
  35. computeNodeLinks();
  36. computeNodeValues();
  37. computeNodeStructure();
  38. computeNodeBreadths();
  39. computeNodeDepths(iterations);
  40. computeLinkDepths();
  41. return sankey;
  42. };
  43. sankey.relayout = function() {
  44. computeLinkDepths();
  45. return sankey;
  46. };
  47. sankey.reversibleLink = function() {
  48. var curvature = .5;
  49. // Used when source is behind target, the first and last paths are simple
  50. // lines at the start and end node while the second path is the spline
  51. function forwardLink(part, d) {
  52. var x0 = d.source.x + d.source.dx,
  53. x1 = d.target.x,
  54. xi = d3.interpolateNumber(x0, x1),
  55. x2 = xi(curvature),
  56. x3 = xi(1 - curvature),
  57. y0 = d.source.y + d.sy,
  58. y1 = d.target.y + d.ty,
  59. y2 = d.source.y + d.sy + d.dy,
  60. y3 = d.target.y + d.ty + d.dy;
  61. switch (part) {
  62. case 0:
  63. return "M" + x0 + "," + y0 + "L" + x0 + "," + (y0 + d.dy);
  64. case 1:
  65. return "M" + x0 + "," + y0
  66. + "C" + x2 + "," + y0 + " " + x3 + "," + y1 + " " + x1 + "," + y1
  67. + "L" + x1 + "," + y3
  68. + "C" + x3 + "," + y3 + " " + x2 + "," + y2 + " " + x0 + "," + y2
  69. + "Z";
  70. case 2:
  71. return "M" + x1 + "," + y1 + "L" + x1 + "," + (y1 + d.dy);
  72. }
  73. }
  74. // Used for self loops and when the source is actually in front of the
  75. // target; the first element is a turning path from the source to the
  76. // destination, the second element connects the two twists and the last
  77. // twists into the target element.
  78. //
  79. //
  80. // /--Target
  81. // \----------------------\
  82. // Source--/
  83. //
  84. function backwardLink(part, d) {
  85. var curveExtension = 30;
  86. var curveDepth = 15;
  87. function getDir(d) {
  88. return d.source.y + d.sy > d.target.y + d.ty ? -1 : 1;
  89. }
  90. function p(x, y) {
  91. return x + "," + y + " ";
  92. }
  93. var dt = getDir(d) * curveDepth,
  94. x0 = d.source.x + d.source.dx,
  95. y0 = d.source.y + d.sy,
  96. x1 = d.target.x,
  97. y1 = d.target.y + d.ty;
  98. switch (part) {
  99. case 0:
  100. return "M" + p(x0, y0) +
  101. "C" + p(x0, y0) +
  102. p(x0 + curveExtension, y0) +
  103. p(x0 + curveExtension, y0 + dt) +
  104. "L" + p(x0 + curveExtension, y0 + dt + d.dy) +
  105. "C" + p(x0 + curveExtension, y0 + d.dy) +
  106. p(x0, y0 + d.dy) +
  107. p(x0, y0 + d.dy) +
  108. "Z";
  109. case 1:
  110. return "M" + p(x0 + curveExtension, y0 + dt) +
  111. "C" + p(x0 + curveExtension, y0 + 3 * dt) +
  112. p(x1 - curveExtension, y1 - 3 * dt) +
  113. p(x1 - curveExtension, y1 - dt) +
  114. "L" + p(x1 - curveExtension, y1 - dt + d.dy) +
  115. "C" + p(x1 - curveExtension, y1 - 3 * dt + d.dy) +
  116. p(x0 + curveExtension, y0 + 3 * dt + d.dy) +
  117. p(x0 + curveExtension, y0 + dt + d.dy) +
  118. "Z";
  119. case 2:
  120. return "M" + p(x1 - curveExtension, y1 - dt) +
  121. "C" + p(x1 - curveExtension, y1) +
  122. p(x1, y1) +
  123. p(x1, y1) +
  124. "L" + p(x1, y1 + d.dy) +
  125. "C" + p(x1, y1 + d.dy) +
  126. p(x1 - curveExtension, y1 + d.dy) +
  127. p(x1 - curveExtension, y1 + d.dy - dt) +
  128. "Z";
  129. }
  130. }
  131. return function(part) {
  132. return function(d) {
  133. if (d.source.x < d.target.x) {
  134. return forwardLink(part, d);
  135. } else {
  136. return backwardLink(part, d);
  137. }
  138. }
  139. }
  140. };
  141. // The standard link path using a constant width spline that needs a
  142. // single path element.
  143. sankey.link = function() {
  144. var curvature = .5;
  145. function link(d) {
  146. var x0 = d.source.x + d.source.dx,
  147. x1 = d.target.x,
  148. xi = d3.interpolateNumber(x0, x1),
  149. x2 = xi(curvature),
  150. x3 = xi(1 - curvature),
  151. y0 = d.source.y + d.sy + d.dy / 2,
  152. y1 = d.target.y + d.ty + d.dy / 2;
  153. return "M" + x0 + "," + y0
  154. + "C" + x2 + "," + y0
  155. + " " + x3 + "," + y1
  156. + " " + x1 + "," + y1;
  157. }
  158. link.curvature = function(_) {
  159. if (!arguments.length) return curvature;
  160. curvature = +_;
  161. return link;
  162. };
  163. return link;
  164. };
  165. // Populate the sourceLinks and targetLinks for each node.
  166. // Also, if the source and target are not objects, assume they are indices.
  167. function computeNodeLinks() {
  168. console.log('DBG:sankey:computeNodeLinks: 1: ', {nodes, links})
  169. nodes.forEach(function(node) {
  170. node.sourceLinks = [];
  171. node.targetLinks = [];
  172. });
  173. links.forEach(function(link) {
  174. var source = link.source,
  175. target = link.target;
  176. source = (typeof source === "number") ? nodes[source] : nodes.find(node => node.name === source);
  177. target = (typeof target === "number") ? nodes[target] : nodes.find(node => node.name === target);
  178. link.source = source
  179. link.target = target
  180. source.sourceLinks.push(link);
  181. target.targetLinks.push(link);
  182. });
  183. console.log('DBG:sankey:computeNodeLinks: 2:', {nodes, links})
  184. }
  185. // Compute the value (size) of each node by summing the associated links.
  186. function computeNodeValues() {
  187. nodes.forEach(function(node) {
  188. if (!(node.value)) //if not already given
  189. node.value = Math.max(
  190. d3.sum(node.sourceLinks, value),
  191. d3.sum(node.targetLinks, value)
  192. );
  193. });
  194. }
  195. // Take the list of nodes and create a DAG of supervertices, each consisting
  196. // of a strongly connected component of the graph
  197. //
  198. // Based off:
  199. // http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm
  200. function computeNodeStructure() {
  201. var nodeStack = [],
  202. index = 0;
  203. nodes.forEach(function(node) {
  204. if (!node.index) {
  205. connect(node);
  206. }
  207. });
  208. function connect(node) {
  209. node.index = index++;
  210. node.lowIndex = node.index;
  211. node.onStack = true;
  212. nodeStack.push(node);
  213. if (node.sourceLinks) {
  214. node.sourceLinks.forEach(function(sourceLink){
  215. var target = sourceLink.target;
  216. if (!target.hasOwnProperty('index')) {
  217. connect(target);
  218. node.lowIndex = Math.min(node.lowIndex, target.lowIndex);
  219. } else if (target.onStack) {
  220. node.lowIndex = Math.min(node.lowIndex, target.index);
  221. }
  222. });
  223. if (node.lowIndex === node.index) {
  224. var component = [], currentNode;
  225. do {
  226. currentNode = nodeStack.pop()
  227. currentNode.onStack = false;
  228. component.push(currentNode);
  229. } while (currentNode != node);
  230. components.push({
  231. root: node,
  232. scc: component
  233. });
  234. }
  235. }
  236. }
  237. components.forEach(function(component, i){
  238. component.index = i;
  239. component.scc.forEach(function(node) {
  240. node.component = i;
  241. });
  242. });
  243. }
  244. // Assign the breadth (x-position) for each strongly connected component,
  245. // followed by assigning breadth within the component.
  246. function computeNodeBreadths() {
  247. layerComponents();
  248. components.forEach(function(component, i){
  249. bfs(component.root, function(node){
  250. var result = node.sourceLinks
  251. .filter(function(sourceLink){
  252. return sourceLink.target.component == i;
  253. })
  254. .map(function(sourceLink){
  255. return sourceLink.target;
  256. });
  257. return result;
  258. });
  259. });
  260. var max = 0;
  261. var componentsByBreadth = d3.nest()
  262. .key(function(d) { return d.x; })
  263. .sortKeys(d3.ascending)
  264. .entries(components)
  265. .map(function(d) { return d.values; });
  266. var max = -1, nextMax = -1;
  267. componentsByBreadth.forEach(function(c){
  268. c.forEach(function(component){
  269. component.x = max + 1;
  270. component.scc.forEach(function(node){
  271. if (node.layer) node.x=node.layer;
  272. else node.x = component.x + node.x;
  273. nextMax = Math.max(nextMax, node.x);
  274. });
  275. });
  276. max = nextMax;
  277. });
  278. nodes
  279. .filter(function(node) {
  280. var outLinks = node.sourceLinks.filter(function(link){ return link.source.name != link.target.name; });
  281. return (outLinks.length == 0);
  282. })
  283. .forEach(function(node) { node.x = (node.layer)?node.x:max; })
  284. scaleNodeBreadths((size[0] - nodeWidth) / Math.max(max, 1));
  285. function flatten(a) {
  286. return [].concat.apply([], a);
  287. }
  288. function layerComponents() {
  289. var remainingComponents = components,
  290. nextComponents,
  291. visitedIndex,
  292. x = 0;
  293. while (remainingComponents.length) {
  294. nextComponents = [];
  295. visitedIndex = {};
  296. remainingComponents.forEach(function(component) {
  297. component.x = x;
  298. component.scc.forEach(function(n) {
  299. n.sourceLinks.forEach(function(l) {
  300. if (!visitedIndex.hasOwnProperty(l.target.component) &&
  301. l.target.component != component.index) {
  302. nextComponents.push(components[l.target.component]);
  303. visitedIndex[l.target.component] = true;
  304. }
  305. })
  306. });
  307. });
  308. remainingComponents = nextComponents;
  309. ++x;
  310. }
  311. }
  312. function bfs(node, extractTargets) {
  313. var queue = [node], currentCount = 1, nextCount = 0;
  314. var x = 0;
  315. while(currentCount > 0) {
  316. var currentNode = queue.shift();
  317. currentCount--;
  318. if (!currentNode.hasOwnProperty('x')) {
  319. currentNode.x = x;
  320. currentNode.dx = nodeWidth;
  321. var targets = extractTargets(currentNode);
  322. queue = queue.concat(targets);
  323. nextCount += targets.length;
  324. }
  325. if (currentCount == 0) { // level change
  326. x++;
  327. currentCount = nextCount;
  328. nextCount = 0;
  329. }
  330. }
  331. }
  332. //extra code for fixed layout - x part
  333. if (fixedlayout.length>0) {
  334. sankey.nodes().forEach(function(d,i){
  335. d.x=fixedlayout[i][0];
  336. })
  337. }
  338. }
  339. function moveSourcesRight() {
  340. nodes.forEach(function(node) {
  341. if (!node.targetLinks.length) {
  342. node.x = d3.min(node.sourceLinks, function(d) { return d.target.x; }) - 1;
  343. }
  344. });
  345. }
  346. function moveSinksRight(x) {
  347. nodes.forEach(function(node) {
  348. if (!node.sourceLinks.length) {
  349. node.x = x - 1;
  350. }
  351. });
  352. }
  353. function scaleNodeBreadths(kx) {
  354. nodes.forEach(function(node) {
  355. node.x *= kx;
  356. });
  357. }
  358. function computeNodeDepths(iterations) {
  359. var nodesByBreadth = d3.nest()
  360. .key(function(d) { return d.x; })
  361. .sortKeys(d3.ascending)
  362. .entries(nodes)
  363. .map(function(d) { return d.values; });
  364. initializeNodeDepth();
  365. resolveCollisions();
  366. for (var alpha = 1; iterations > 0; --iterations) {
  367. relaxRightToLeft(alpha *= .99);
  368. resolveCollisions();
  369. relaxLeftToRight(alpha);
  370. resolveCollisions();
  371. }
  372. function initializeNodeDepth() {
  373. var ky = d3.min(nodesByBreadth, function(nodes) {
  374. return (size[1] - (nodes.length - 1) * nodePadding) / d3.sum(nodes, value);
  375. });
  376. nodesByBreadth.forEach(function(nodes) {
  377. nodes.forEach(function(node, i) {
  378. node.y = i;
  379. node.dy = node.value * ky;
  380. });
  381. });
  382. links.forEach(function(link) {
  383. link.dy = link.value * ky;
  384. });
  385. }
  386. function relaxLeftToRight(alpha) {
  387. nodesByBreadth.forEach(function(nodes, breadth) {
  388. nodes.forEach(function(node) {
  389. if (node.targetLinks.length) {
  390. var y = d3.sum(node.targetLinks, weightedSource) / d3.sum(node.targetLinks, value);
  391. node.y += (y - center(node)) * alpha;
  392. }
  393. });
  394. });
  395. function weightedSource(link) {
  396. return center(link.source) * link.value;
  397. }
  398. }
  399. function relaxRightToLeft(alpha) {
  400. nodesByBreadth.slice().reverse().forEach(function(nodes) {
  401. nodes.forEach(function(node) {
  402. if (node.sourceLinks.length) {
  403. var y = d3.sum(node.sourceLinks, weightedTarget) / d3.sum(node.sourceLinks, value);
  404. node.y += (y - center(node)) * alpha;
  405. }
  406. });
  407. });
  408. function weightedTarget(link) {
  409. return center(link.target) * link.value;
  410. }
  411. }
  412. function resolveCollisions() {
  413. nodesByBreadth.forEach(function(nodes) {
  414. var node,
  415. dy,
  416. y0 = 0,
  417. n = nodes.length,
  418. i;
  419. // Push any overlapping nodes down.
  420. nodes.sort(ascendingDepth);
  421. for (i = 0; i < n; ++i) {
  422. node = nodes[i];
  423. dy = y0 - node.y;
  424. if (dy > 0) node.y += dy;
  425. y0 = node.y + node.dy + nodePadding;
  426. }
  427. // If the bottommost node goes outside the bounds, push it back up.
  428. dy = y0 - nodePadding - size[1];
  429. if (dy > 0) {
  430. y0 = node.y -= dy;
  431. // Push any overlapping nodes back up.
  432. for (i = n - 2; i >= 0; --i) {
  433. node = nodes[i];
  434. dy = node.y + node.dy + nodePadding - y0;
  435. if (dy > 0) node.y -= dy;
  436. y0 = node.y;
  437. }
  438. }
  439. });
  440. }
  441. function ascendingDepth(a, b) {
  442. return a.y - b.y;
  443. }
  444. //extra code for fixed layout - y part
  445. if (fixedlayout.length>0) {
  446. sankey.nodes().forEach(function(d,i){
  447. d.y=fixedlayout[i][1];
  448. })
  449. }
  450. }
  451. function computeLinkDepths() {
  452. nodes.forEach(function(node) {
  453. if (parallelrendering) {}
  454. else node.sourceLinks.sort(ascendingTargetDepth);
  455. node.targetLinks.sort(ascendingSourceDepth);
  456. });
  457. nodes.forEach(function(node) {
  458. var sy = 0, ty = 0;
  459. node.sourceLinks.forEach(function(link) {
  460. link.sy = sy;
  461. sy += link.dy;
  462. });
  463. node.targetLinks.forEach(function(link) {
  464. link.ty = ty;
  465. ty += link.dy;
  466. });
  467. });
  468. function ascendingSourceDepth(a, b) {
  469. return a.source.y - b.source.y;
  470. }
  471. function ascendingTargetDepth(a, b) {
  472. return a.target.y - b.target.y;
  473. }
  474. }
  475. function center(node) {
  476. return node.y + node.dy / 2;
  477. }
  478. function value(link) {
  479. return link.value;
  480. }
  481. return sankey;
  482. };