d3-sankey - npm Package Compare versions

Comparing version 0.11.0 to 0.12.0

dist/d3-sankey.js

@@ -1,7 +0,7 @@
-// https://github.com/d3/d3-sankey v0.11.0 Copyright 2019 Mike Bostock
+// https://github.com/d3/d3-sankey v0.12.0 Copyright 2019 Mike Bostock
 (function (global, factory) {
-typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports, require('d3-array'), require('d3-collection'), require('d3-shape')) :
-typeof define === 'function' && define.amd ? define(['exports', 'd3-array', 'd3-collection', 'd3-shape'], factory) :
-(global = global || self, factory(global.d3 = global.d3 || {}, global.d3, global.d3, global.d3));
-}(this, function (exports, d3Array, d3Collection, d3Shape) { 'use strict';
+typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports, require('d3-array'), require('d3-shape')) :
+typeof define === 'function' && define.amd ? define(['exports', 'd3-array', 'd3-shape'], factory) :
+(global = global || self, factory(global.d3 = global.d3 || {}, global.d3, global.d3));
+}(this, function (exports, d3Array, d3Shape) { 'use strict';
 
@@ -65,3 +65,3 @@ function targetDepth(d) {
 function find(nodeById, id) {
-  var node = nodeById.get(id);
+  const node = nodeById.get(id);
   if (!node) throw new Error("missing: " + id);
@@ -71,19 +71,35 @@ return node;
 
+function computeLinkBreadths({nodes}) {
+  for (const node of nodes) {
+    let y0 = node.y0;
+    let y1 = y0;
+    for (const link of node.sourceLinks) {
+      link.y0 = y0 + link.width / 2;
+      y0 += link.width;
+    }
+    for (const link of node.targetLinks) {
+      link.y1 = y1 + link.width / 2;
+      y1 += link.width;
+    }
+  }
+}
+
 function Sankey() {
-  var x0 = 0, y0 = 0, x1 = 1, y1 = 1, // extent
-      dx = 24, // nodeWidth
-      py = 8, // nodePadding
-      id = defaultId,
-      align = justify,
-      sort,
-      linkSort,
-      nodes = defaultNodes,
-      links = defaultLinks,
-      iterations = 6;
+  let x0 = 0, y0 = 0, x1 = 1, y1 = 1; // extent
+  let dx = 24; // nodeWidth
+  let py = 8; // nodePadding
+  let id = defaultId;
+  let align = justify;
+  let sort;
+  let linkSort;
+  let nodes = defaultNodes;
+  let links = defaultLinks;
+  let iterations = 6;
 
   function sankey() {
-    var graph = {nodes: nodes.apply(null, arguments), links: links.apply(null, arguments)};
+    const graph = {nodes: nodes.apply(null, arguments), links: links.apply(null, arguments)};
     computeNodeLinks(graph);
     computeNodeValues(graph);
     computeNodeDepths(graph);
+    computeNodeHeights(graph);
     computeNodeBreadths(graph);
@@ -143,14 +159,12 @@ computeLinkBreadths(graph);
 
-  // Populate the sourceLinks and targetLinks for each node.
-  // Also, if the source and target are not objects, assume they are indices.
-  function computeNodeLinks(graph) {
-    graph.nodes.forEach(function(node, i) {
+  function computeNodeLinks({nodes, links}) {
+    for (const [i, node] of nodes.entries()) {
       node.index = i;
       node.sourceLinks = [];
       node.targetLinks = [];
-    });
-    var nodeById = d3Collection.map(graph.nodes, id);
-    graph.links.forEach(function(link, i) {
+    }
+    const nodeById = new Map(nodes.map((d, i) => [id(d, i, nodes), d]));
+    for (const [i, link] of links.entries()) {
       link.index = i;
-      var source = link.source, target = link.target;
+      let {source, target} = link;
       if (typeof source !== "object") source = link.source = find(nodeById, source);
@@ -160,8 +174,7 @@ if (typeof target !== "object") target = link.target = find(nodeById, target);
       target.targetLinks.push(link);
-    });
+    }
   }
 
-  // Compute the value (size) of each node by summing the associated links.
-  function computeNodeValues(graph) {
-    graph.nodes.forEach(function(node) {
+  function computeNodeValues({nodes}) {
+    for (const node of nodes) {
       node.value = Math.max(
@@ -171,185 +184,187 @@ d3Array.sum(node.sourceLinks, value),
       );
-    });
+    }
   }
 
-  // Iteratively assign the depth (x-position) for each node.
-  // Nodes are assigned the maximum depth of incoming neighbors plus one;
-  // nodes with no incoming links are assigned depth zero, while
-  // nodes with no outgoing links are assigned the maximum depth.
-  function computeNodeDepths(graph) {
-    var nodes, next, x, n = graph.nodes.length;
-
-    for (nodes = graph.nodes, next = [], x = 0; nodes.length; ++x, nodes = next, next = []) {
-      if (x > n) throw new Error("circular link");
-      nodes.forEach(function(node) {
+  function computeNodeDepths({nodes}) {
+    const n = nodes.length;
+    let current = new Set(nodes);
+    let next = new Set;
+    let x = 0;
+    while (current.size) {
+      for (const node of current) {
         node.depth = x;
-        node.sourceLinks.forEach(function(link) {
-          if (next.indexOf(link.target) < 0) {
-            next.push(link.target);
-          }
-        });
-      });
+        for (const {target} of node.sourceLinks) {
+          next.add(target);
+        }
+      }
+      if (++x > n) throw new Error("circular link");
+      current = next;
+      next = new Set;
     }
+  }
 
-    for (nodes = graph.nodes, next = [], x = 0; nodes.length; ++x, nodes = next, next = []) {
-      if (x > n) throw new Error("circular link");
-      nodes.forEach(function(node) {
+  function computeNodeHeights({nodes}) {
+    const n = nodes.length;
+    let current = new Set(nodes);
+    let next = new Set;
+    let x = 0;
+    while (current.size) {
+      for (const node of current) {
         node.height = x;
-        node.targetLinks.forEach(function(link) {
-          if (next.indexOf(link.source) < 0) {
-            next.push(link.source);
-          }
-        });
-      });
+        for (const {source} of node.targetLinks) {
+          next.add(source);
+        }
+      }
+      if (++x > n) throw new Error("circular link");
+      current = next;
+      next = new Set;
     }
-
-    var kx = (x1 - x0 - dx) / (x - 1);
-    graph.nodes.forEach(function(node) {
-      node.layer = Math.max(0, Math.min(x - 1, Math.floor(align.call(null, node, x))));
-      node.x1 = (node.x0 = x0 + node.layer * kx) + dx;
-    });
   }
 
-  function computeNodeBreadths(graph) {
-    var columns = d3Collection.nest()
-        .key(function(d) { return d.x0; })
-        .sortKeys(d3Array.ascending)
-        .entries(graph.nodes)
-        .map(function(d) { return d.values; });
-
-    //
-    initializeNodeBreadth();
-    for (var i = 0, n = iterations; i < n; ++i) {
-      const a = Math.pow(0.99, i);
-      const b = (i + 1) / n;
-      reorderLinks(graph);
-      relaxRightToLeft(a);
-      resolveCollisionsTopToBottom(b);
-      resolveCollisionsBottomToTop(b);
-      reorderLinks(graph);
-      relaxLeftToRight(a);
-      resolveCollisionsTopToBottom(b);
-      resolveCollisionsBottomToTop(b);
+  function computeNodeLayers({nodes}) {
+    const x = d3Array.max(nodes, d => d.depth) + 1;
+    const kx = (x1 - x0 - dx) / (x - 1);
+    const columns = new Array(x);
+    for (const node of nodes) {
+      const i = Math.max(0, Math.min(x - 1, Math.floor(align.call(null, node, x))));
+      node.layer = i;
+      node.x0 = x0 + i * kx;
+      node.x1 = node.x0 + dx;
+      if (columns[i]) columns[i].push(node);
+      else columns[i] = [node];
     }
-
-    function initializeNodeBreadth() {
-      var ky = d3Array.min(columns, function(nodes) {
-        return (y1 - y0 - (nodes.length - 1) * py) / d3Array.sum(nodes, value);
-      });
-
-      columns.forEach(function(nodes) {
-        if (sort != null) nodes.sort(sort);
-        let y = y0;
-        nodes.forEach(function(node) {
-          node.y0 = y;
-          node.y1 = y + node.value * ky;
-          y = node.y1 + py;
-        });
-      });
-
-      graph.links.forEach(function(link) {
-        link.width = link.value * ky;
-      });
-
-      if (linkSort != null) graph.nodes.forEach(function(node) {
-        node.sourceLinks.sort(linkSort);
-        node.targetLinks.sort(linkSort);
-      });
+    if (sort) for (const column of columns) {
+      column.sort(sort);
     }
+    return columns;
+  }
 
-    // Reposition each node based on its incoming (target) links.
-    function relaxLeftToRight(alpha) {
-      columns.slice(1).forEach(function(nodes) {
-        nodes.forEach(function(target) {
-          let y = 0;
-          let w = 0;
-          for (const {source, value} of target.targetLinks) {
-            let v = value * (target.layer - source.layer);
-            y += targetTop(source, target) * v;
-            w += v;
-          }
-          if (!(w > 0)) return;
-          let dy = (y / w - target.y0) * alpha;
-          target.y0 += dy;
-          target.y1 += dy;
-        });
-      });
+  function initializeNodeBreadths(columns) {
+    const ky = d3Array.min(columns, c => (y1 - y0 - (c.length - 1) * py) / d3Array.sum(c, value));
+    for (const nodes of columns) {
+      let y = y0;
+      for (const node of nodes) {
+        node.y0 = y;
+        node.y1 = y + node.value * ky;
+        y = node.y1 + py;
+        for (const link of node.sourceLinks) {
+          link.width = link.value * ky;
+        }
+      }
+      y = (y1 - y + py) / (nodes.length + 1);
+      for (let i = 0; i < nodes.length; ++i) {
+        const node = nodes[i];
+        node.y0 += y * (i + 1);
+        node.y1 += y * (i + 1);
+      }
+      reorderLinks(nodes);
     }
+  }
 
-    // Reposition each node based on its outgoing (source) links.
-    function relaxRightToLeft(alpha) {
-      columns.slice(0, -1).reverse().forEach(function(nodes) {
-        nodes.forEach(function(source) {
-          let y = 0;
-          let w = 0;
-          for (const {target, value} of source.sourceLinks) {
-            let v = value * (target.layer - source.layer);
-            y += sourceTop(source, target) * v;
-            w += v;
-          }
-          if (!(w > 0)) return;
-          let dy = (y / w - source.y0) * alpha;
-          source.y0 += dy;
-          source.y1 += dy;
-        });
-      });
+  function computeNodeBreadths(graph) {
+    const columns = computeNodeLayers(graph);
+    initializeNodeBreadths(columns);
+    for (let i = 0; i < iterations; ++i) {
+      const beta = ((i + 1) / iterations) ** 1.5;
+      const alpha = 1 - beta;
+      relaxRightToLeft(columns, alpha, beta);
+      relaxLeftToRight(columns, alpha, beta);
     }
+  }
 
-    // Push any overlapping nodes down.
-    function resolveCollisionsTopToBottom(alpha) {
-      columns.forEach(function(nodes) {
-        var node,
-            dy,
-            y = y0,
-            n = nodes.length,
-            i;
-        if (sort === undefined) nodes.sort(ascendingBreadth);
-        for (i = 0; i < n; ++i) {
-          node = nodes[i];
-          dy = (y - node.y0) * alpha;
-          if (dy > 1e-6) node.y0 += dy, node.y1 += dy;
-          y = node.y1 + py;
+  // Reposition each node based on its incoming (target) links.
+  function relaxLeftToRight(columns, alpha, beta) {
+    for (let i = 1, n = columns.length; i < n; ++i) {
+      const column = columns[i];
+      for (const target of column) {
+        let y = 0;
+        let w = 0;
+        for (const {source, value} of target.targetLinks) {
+          let v = value * (target.layer - source.layer);
+          y += targetTop(source, target) * v;
+          w += v;
         }
-      });
+        if (!(w > 0)) continue;
+        let dy = (y / w - target.y0) * alpha;
+        target.y0 += dy;
+        target.y1 += dy;
+        reorderNodeLinks(target);
+      }
+      if (sort === undefined) column.sort(ascendingBreadth);
+      resolveCollisions(column, beta);
     }
+  }
 
-    // Push any overlapping nodes up.
-    function resolveCollisionsBottomToTop(alpha) {
-      columns.forEach(function(nodes) {
-        var node,
-            dy,
-            y = y1,
-            n = nodes.length,
-            i;
-        if (sort === undefined) nodes.sort(ascendingBreadth);
-        for (i = n - 1; i >= 0; --i) {
-          node = nodes[i];
-          dy = (node.y1 - y) * alpha;
-          if (dy > 1e-6) node.y0 -= dy, node.y1 -= dy;
-          y = node.y0 - py;
+  // Reposition each node based on its outgoing (source) links.
+  function relaxRightToLeft(columns, alpha, beta) {
+    for (let n = columns.length, i = n - 2; i >= 0; --i) {
+      const column = columns[i];
+      for (const source of column) {
+        let y = 0;
+        let w = 0;
+        for (const {target, value} of source.sourceLinks) {
+          let v = value * (target.layer - source.layer);
+          y += sourceTop(source, target) * v;
+          w += v;
         }
-      });
+        if (!(w > 0)) continue;
+        let dy = (y / w - source.y0) * alpha;
+        source.y0 += dy;
+        source.y1 += dy;
+        reorderNodeLinks(source);
+      }
+      if (sort === undefined) column.sort(ascendingBreadth);
+      resolveCollisions(column, beta);
     }
   }
 
-  function reorderLinks(graph) {
-    if (linkSort === undefined) graph.nodes.forEach(function(node) {
-      node.sourceLinks.sort(ascendingTargetBreadth);
-      node.targetLinks.sort(ascendingSourceBreadth);
-    });
+  function resolveCollisions(nodes, alpha) {
+    const i = nodes.length >> 1;
+    const subject = nodes[i];
+    resolveCollisionsBottomToTop(nodes, subject.y0 - py, i - 1, alpha);
+    resolveCollisionsTopToBottom(nodes, subject.y1 + py, i + 1, alpha);
+    resolveCollisionsBottomToTop(nodes, y1, nodes.length - 1, alpha);
+    resolveCollisionsTopToBottom(nodes, y0, 0, alpha);
   }
 
-  function computeLinkBreadths(graph) {
-    reorderLinks(graph);
-    graph.nodes.forEach(function(node) {
-      var y0 = node.y0, y1 = y0;
-      node.sourceLinks.forEach(function(link) {
-        link.y0 = y0 + link.width / 2, y0 += link.width;
-      });
-      node.targetLinks.forEach(function(link) {
-        link.y1 = y1 + link.width / 2, y1 += link.width;
-      });
-    });
+  // Push any overlapping nodes down.
+  function resolveCollisionsTopToBottom(nodes, y, i, alpha) {
+    for (; i < nodes.length; ++i) {
+      const node = nodes[i];
+      const dy = (y - node.y0) * alpha;
+      if (dy > 1e-6) node.y0 += dy, node.y1 += dy;
+      y = node.y1 + py;
+    }
   }
 
+  // Push any overlapping nodes up.
+  function resolveCollisionsBottomToTop(nodes, y, i, alpha) {
+    for (; i >= 0; --i) {
+      const node = nodes[i];
+      const dy = (node.y1 - y) * alpha;
+      if (dy > 1e-6) node.y0 -= dy, node.y1 -= dy;
+      y = node.y0 - py;
+    }
+  }
+
+  function reorderNodeLinks({sourceLinks, targetLinks}) {
+    if (linkSort === undefined) {
+      for (const {source: {sourceLinks}} of targetLinks) {
+        sourceLinks.sort(ascendingTargetBreadth);
+      }
+      for (const {target: {targetLinks}} of sourceLinks) {
+        targetLinks.sort(ascendingSourceBreadth);
+      }
+    }
+  }
+
+  function reorderLinks(nodes) {
+    if (linkSort === undefined) {
+      for (const {sourceLinks, targetLinks} of nodes) {
+        sourceLinks.sort(ascendingTargetBreadth);
+        targetLinks.sort(ascendingSourceBreadth);
+      }
+    }
+  }
+
   // Returns the target.y0 that would produce an ideal link from source to target.
@@ -356,0 +371,0 @@ function targetTop(source, target) {

dist/d3-sankey.min.js

@@ -1,2 +0,2 @@
-// https://github.com/d3/d3-sankey v0.11.0 Copyright 2019 Mike Bostock
-!function(n,t){"object"==typeof exports&&"undefined"!=typeof module?t(exports,require("d3-array"),require("d3-collection"),require("d3-shape")):"function"==typeof define&&define.amd?define(["exports","d3-array","d3-collection","d3-shape"],t):t((n=n||self).d3=n.d3||{},n.d3,n.d3,n.d3)}(this,function(n,t,e,r){"use strict";function o(n){return n.target.depth}function i(n,t){return n.sourceLinks.length?n.depth:t-1}function u(n){return function(){return n}}function c(n,t){return s(n.source,t.source)||n.index-t.index}function f(n,t){return s(n.target,t.target)||n.index-t.index}function s(n,t){return n.y0-t.y0}function a(n){return n.value}function l(n){return n.index}function h(n){return n.nodes}function d(n){return n.links}function y(n,t){var e=n.get(t);if(!e)throw new Error("missing: "+t);return e}function g(n){return[n.source.x1,n.y0]}function k(n){return[n.target.x0,n.y1]}n.sankey=function(){var n,r,o=0,g=0,k=1,p=1,L=24,E=8,v=l,x=i,w=h,m=d,b=6;function M(){var i={nodes:w.apply(null,arguments),links:m.apply(null,arguments)};return function(n){n.nodes.forEach(function(n,t){n.index=t,n.sourceLinks=[],n.targetLinks=[]});var t=e.map(n.nodes,v);n.links.forEach(function(n,e){n.index=e;var r=n.source,o=n.target;"object"!=typeof r&&(r=n.source=y(t,r)),"object"!=typeof o&&(o=n.target=y(t,o)),r.sourceLinks.push(n),o.targetLinks.push(n)})}(i),function(n){n.nodes.forEach(function(n){n.value=Math.max(t.sum(n.sourceLinks,a),t.sum(n.targetLinks,a))})}(i),function(n){var t,e,r,i=n.nodes.length;for(t=n.nodes,e=[],r=0;t.length;++r,t=e,e=[]){if(r>i)throw new Error("circular link");t.forEach(function(n){n.depth=r,n.sourceLinks.forEach(function(n){e.indexOf(n.target)<0&&e.push(n.target)})})}for(t=n.nodes,e=[],r=0;t.length;++r,t=e,e=[]){if(r>i)throw new Error("circular link");t.forEach(function(n){n.height=r,n.targetLinks.forEach(function(n){e.indexOf(n.source)<0&&e.push(n.source)})})}var u=(k-o-L)/(r-1);n.nodes.forEach(function(n){n.layer=Math.max(0,Math.min(r-1,Math.floor(x.call(null,n,r)))),n.x1=(n.x0=o+n.layer*u)+L})}(i),function(o){var i,u=e.nest().key(function(n){return n.x0}).sortKeys(t.ascending).entries(o.nodes).map(function(n){return n.values});i=t.min(u,function(n){return(p-g-(n.length-1)*E)/t.sum(n,a)}),u.forEach(function(t){null!=n&&t.sort(n);let e=g;t.forEach(function(n){n.y0=e,n.y1=e+n.value*i,e=n.y1+E})}),o.links.forEach(function(n){n.width=n.value*i}),null!=r&&o.nodes.forEach(function(n){n.sourceLinks.sort(r),n.targetLinks.sort(r)});for(var c=0,f=b;c<f;++c){const n=Math.pow(.99,c),t=(c+1)/f;j(o),h(n),d(t),y(t),j(o),l(n),d(t),y(t)}function l(n){u.slice(1).forEach(function(t){t.forEach(function(t){let e=0,r=0;for(const{source:n,value:o}of t.targetLinks){let i=o*(t.layer-n.layer);e+=z(n,t)*i,r+=i}if(!(r>0))return;let o=(e/r-t.y0)*n;t.y0+=o,t.y1+=o})})}function h(n){u.slice(0,-1).reverse().forEach(function(t){t.forEach(function(t){let e=0,r=0;for(const{target:n,value:o}of t.sourceLinks){let i=o*(n.layer-t.layer);e+=O(t,n)*i,r+=i}if(!(r>0))return;let o=(e/r-t.y0)*n;t.y0+=o,t.y1+=o})})}function d(t){u.forEach(function(e){var r,o,i,u=g,c=e.length;for(void 0===n&&e.sort(s),i=0;i<c;++i)r=e[i],(o=(u-r.y0)*t)>1e-6&&(r.y0+=o,r.y1+=o),u=r.y1+E})}function y(t){u.forEach(function(e){var r,o,i,u=p,c=e.length;for(void 0===n&&e.sort(s),i=c-1;i>=0;--i)r=e[i],(o=(r.y1-u)*t)>1e-6&&(r.y0-=o,r.y1-=o),u=r.y0-E})}}(i),q(i),i}function j(n){void 0===r&&n.nodes.forEach(function(n){n.sourceLinks.sort(f),n.targetLinks.sort(c)})}function q(n){j(n),n.nodes.forEach(function(n){var t=n.y0,e=t;n.sourceLinks.forEach(function(n){n.y0=t+n.width/2,t+=n.width}),n.targetLinks.forEach(function(n){n.y1=e+n.width/2,e+=n.width})})}function z(n,t){let e=n.y0-(n.sourceLinks.length-1)*E/2;for(const{target:r,width:o}of n.sourceLinks){if(r===t)break;e+=o+E}for(const{source:r,width:o}of t.targetLinks){if(r===n)break;e-=o}return e}function O(n,t){let e=t.y0-(t.targetLinks.length-1)*E/2;for(const{source:r,width:o}of t.targetLinks){if(r===n)break;e+=o+E}for(const{target:r,width:o}of n.sourceLinks){if(r===t)break;e-=o}return e}return M.update=function(n){return q(n),n},M.nodeId=function(n){return arguments.length?(v="function"==typeof n?n:u(n),M):v},M.nodeAlign=function(n){return arguments.length?(x="function"==typeof n?n:u(n),M):x},M.nodeSort=function(t){return arguments.length?(n=t,M):n},M.nodeWidth=function(n){return arguments.length?(L=+n,M):L},M.nodePadding=function(n){return arguments.length?(E=+n,M):E},M.nodes=function(n){return arguments.length?(w="function"==typeof n?n:u(n),M):w},M.links=function(n){return arguments.length?(m="function"==typeof n?n:u(n),M):m},M.linkSort=function(n){return arguments.length?(r=n,M):r},M.size=function(n){return arguments.length?(o=g=0,k=+n[0],p=+n[1],M):[k-o,p-g]},M.extent=function(n){return arguments.length?(o=+n[0][0],k=+n[1][0],g=+n[0][1],p=+n[1][1],M):[[o,g],[k,p]]},M.iterations=function(n){return arguments.length?(b=+n,M):b},M},n.sankeyCenter=function(n){return n.targetLinks.length?n.depth:n.sourceLinks.length?t.min(n.sourceLinks,o)-1:0},n.sankeyLeft=function(n){return n.depth},n.sankeyRight=function(n,t){return t-1-n.height},n.sankeyJustify=i,n.sankeyLinkHorizontal=function(){return r.linkHorizontal().source(g).target(k)},Object.defineProperty(n,"__esModule",{value:!0})});
+// https://github.com/d3/d3-sankey v0.12.0 Copyright 2019 Mike Bostock
+!function(n,t){"object"==typeof exports&&"undefined"!=typeof module?t(exports,require("d3-array"),require("d3-shape")):"function"==typeof define&&define.amd?define(["exports","d3-array","d3-shape"],t):t((n=n||self).d3=n.d3||{},n.d3,n.d3)}(this,function(n,t,e){"use strict";function o(n){return n.target.depth}function r(n,t){return n.sourceLinks.length?n.depth:t-1}function i(n){return function(){return n}}function s(n,t){return u(n.source,t.source)||n.index-t.index}function f(n,t){return u(n.target,t.target)||n.index-t.index}function u(n,t){return n.y0-t.y0}function c(n){return n.value}function l(n){return n.index}function a(n){return n.nodes}function d(n){return n.links}function h(n,t){const e=n.get(t);if(!e)throw new Error("missing: "+t);return e}function g({nodes:n}){for(const t of n){let n=t.y0,e=n;for(const e of t.sourceLinks)e.y0=n+e.width/2,n+=e.width;for(const n of t.targetLinks)n.y1=e+n.width/2,e+=n.width}}function y(n){return[n.source.x1,n.y0]}function k(n){return[n.target.x0,n.y1]}n.sankey=function(){let n,e,o=0,y=0,k=1,p=1,L=24,w=8,x=l,m=r,v=a,b=d,S=6;function M(){const e={nodes:v.apply(null,arguments),links:b.apply(null,arguments)};return function({nodes:n,links:t}){for(const[t,e]of n.entries())e.index=t,e.sourceLinks=[],e.targetLinks=[];const e=new Map(n.map((t,e)=>[x(t,e,n),t]));for(const[n,o]of t.entries()){o.index=n;let{source:t,target:r}=o;"object"!=typeof t&&(t=o.source=h(e,t)),"object"!=typeof r&&(r=o.target=h(e,r)),t.sourceLinks.push(o),r.targetLinks.push(o)}}(e),function({nodes:n}){for(const e of n)e.value=Math.max(t.sum(e.sourceLinks,c),t.sum(e.targetLinks,c))}(e),function({nodes:n}){const t=n.length;let e=new Set(n),o=new Set,r=0;for(;e.size;){for(const n of e){n.depth=r;for(const{target:t}of n.sourceLinks)o.add(t)}if(++r>t)throw new Error("circular link");e=o,o=new Set}}(e),function({nodes:n}){const t=n.length;let e=new Set(n),o=new Set,r=0;for(;e.size;){for(const n of e){n.height=r;for(const{source:t}of n.targetLinks)o.add(t)}if(++r>t)throw new Error("circular link");e=o,o=new Set}}(e),function(e){const r=function({nodes:e}){const r=t.max(e,n=>n.depth)+1,i=(k-o-L)/(r-1),s=new Array(r);for(const n of e){const t=Math.max(0,Math.min(r-1,Math.floor(m.call(null,n,r))));n.layer=t,n.x0=o+t*i,n.x1=n.x0+L,s[t]?s[t].push(n):s[t]=[n]}if(n)for(const t of s)t.sort(n);return s}(e);!function(n){const e=t.min(n,n=>(p-y-(n.length-1)*w)/t.sum(n,c));for(const t of n){let n=y;for(const o of t){o.y0=n,o.y1=n+o.value*e,n=o.y1+w;for(const n of o.sourceLinks)n.width=n.value*e}n=(p-n+w)/(t.length+1);for(let e=0;e<t.length;++e){const o=t[e];o.y0+=n*(e+1),o.y1+=n*(e+1)}P(t)}}(r);for(let n=0;n<S;++n){const t=((n+1)/S)**1.5,e=1-t;j(r,e,t),z(r,e,t)}}(e),g(e),e}function z(t,e,o){for(let r=1,i=t.length;r<i;++r){const i=t[r];for(const n of i){let t=0,o=0;for(const{source:e,value:r}of n.targetLinks){let i=r*(n.layer-e.layer);t+=_(e,n)*i,o+=i}if(!(o>0))continue;let r=(t/o-n.y0)*e;n.y0+=r,n.y1+=r,H(n)}void 0===n&&i.sort(u),E(i,o)}}function j(t,e,o){for(let r=t.length-2;r>=0;--r){const i=t[r];for(const n of i){let t=0,o=0;for(const{target:e,value:r}of n.sourceLinks){let i=r*(e.layer-n.layer);t+=C(n,e)*i,o+=i}if(!(o>0))continue;let r=(t/o-n.y0)*e;n.y0+=r,n.y1+=r,H(n)}void 0===n&&i.sort(u),E(i,o)}}function E(n,t){const e=n.length>>1,o=n[e];A(n,o.y0-w,e-1,t),q(n,o.y1+w,e+1,t),A(n,p,n.length-1,t),q(n,y,0,t)}function q(n,t,e,o){for(;e<n.length;++e){const r=n[e],i=(t-r.y0)*o;i>1e-6&&(r.y0+=i,r.y1+=i),t=r.y1+w}}function A(n,t,e,o){for(;e>=0;--e){const r=n[e],i=(r.y1-t)*o;i>1e-6&&(r.y0-=i,r.y1-=i),t=r.y0-w}}function H({sourceLinks:n,targetLinks:t}){if(void 0===e){for(const{source:{sourceLinks:n}}of t)n.sort(f);for(const{target:{targetLinks:t}}of n)t.sort(s)}}function P(n){if(void 0===e)for(const{sourceLinks:t,targetLinks:e}of n)t.sort(f),e.sort(s)}function _(n,t){let e=n.y0-(n.sourceLinks.length-1)*w/2;for(const{target:o,width:r}of n.sourceLinks){if(o===t)break;e+=r+w}for(const{source:o,width:r}of t.targetLinks){if(o===n)break;e-=r}return e}function C(n,t){let e=t.y0-(t.targetLinks.length-1)*w/2;for(const{source:o,width:r}of t.targetLinks){if(o===n)break;e+=r+w}for(const{target:o,width:r}of n.sourceLinks){if(o===t)break;e-=r}return e}return M.update=function(n){return g(n),n},M.nodeId=function(n){return arguments.length?(x="function"==typeof n?n:i(n),M):x},M.nodeAlign=function(n){return arguments.length?(m="function"==typeof n?n:i(n),M):m},M.nodeSort=function(t){return arguments.length?(n=t,M):n},M.nodeWidth=function(n){return arguments.length?(L=+n,M):L},M.nodePadding=function(n){return arguments.length?(w=+n,M):w},M.nodes=function(n){return arguments.length?(v="function"==typeof n?n:i(n),M):v},M.links=function(n){return arguments.length?(b="function"==typeof n?n:i(n),M):b},M.linkSort=function(n){return arguments.length?(e=n,M):e},M.size=function(n){return arguments.length?(o=y=0,k=+n[0],p=+n[1],M):[k-o,p-y]},M.extent=function(n){return arguments.length?(o=+n[0][0],k=+n[1][0],y=+n[0][1],p=+n[1][1],M):[[o,y],[k,p]]},M.iterations=function(n){return arguments.length?(S=+n,M):S},M},n.sankeyCenter=function(n){return n.targetLinks.length?n.depth:n.sourceLinks.length?t.min(n.sourceLinks,o)-1:0},n.sankeyLeft=function(n){return n.depth},n.sankeyRight=function(n,t){return t-1-n.height},n.sankeyJustify=r,n.sankeyLinkHorizontal=function(){return e.linkHorizontal().source(y).target(k)},Object.defineProperty(n,"__esModule",{value:!0})});

package.json

 {
   "name": "d3-sankey",
-  "version": "0.11.0",
+  "version": "0.12.0",
   "description": "Visualize flow between nodes in a directed acyclic network.",
@@ -30,4 +30,3 @@ "keywords": [
   "dependencies": {
-    "d3-array": "1",
-    "d3-collection": "1",
+    "d3-array": ">=1 <=2",
     "d3-shape": "^1.2.0"
@@ -34,0 +33,0 @@ },

src/sankey.js

@@ -1,3 +0,2 @@
-import {ascending, min, sum} from "d3-array";
-import {map, nest} from "d3-collection";
+import {max, min, sum} from "d3-array";
 import {justify} from "./align.js";
@@ -35,3 +34,3 @@ import constant from "./constant.js";
 function find(nodeById, id) {
-  var node = nodeById.get(id);
+  const node = nodeById.get(id);
   if (!node) throw new Error("missing: " + id);
@@ -41,19 +40,35 @@ return node;
 
+function computeLinkBreadths({nodes}) {
+  for (const node of nodes) {
+    let y0 = node.y0;
+    let y1 = y0;
+    for (const link of node.sourceLinks) {
+      link.y0 = y0 + link.width / 2;
+      y0 += link.width;
+    }
+    for (const link of node.targetLinks) {
+      link.y1 = y1 + link.width / 2;
+      y1 += link.width;
+    }
+  }
+}
+
 export default function Sankey() {
-  var x0 = 0, y0 = 0, x1 = 1, y1 = 1, // extent
-      dx = 24, // nodeWidth
-      py = 8, // nodePadding
-      id = defaultId,
-      align = justify,
-      sort,
-      linkSort,
-      nodes = defaultNodes,
-      links = defaultLinks,
-      iterations = 6;
+  let x0 = 0, y0 = 0, x1 = 1, y1 = 1; // extent
+  let dx = 24; // nodeWidth
+  let py = 8; // nodePadding
+  let id = defaultId;
+  let align = justify;
+  let sort;
+  let linkSort;
+  let nodes = defaultNodes;
+  let links = defaultLinks;
+  let iterations = 6;
 
   function sankey() {
-    var graph = {nodes: nodes.apply(null, arguments), links: links.apply(null, arguments)};
+    const graph = {nodes: nodes.apply(null, arguments), links: links.apply(null, arguments)};
     computeNodeLinks(graph);
     computeNodeValues(graph);
     computeNodeDepths(graph);
+    computeNodeHeights(graph);
     computeNodeBreadths(graph);
@@ -113,14 +128,12 @@ computeLinkBreadths(graph);
 
-  // Populate the sourceLinks and targetLinks for each node.
-  // Also, if the source and target are not objects, assume they are indices.
-  function computeNodeLinks(graph) {
-    graph.nodes.forEach(function(node, i) {
+  function computeNodeLinks({nodes, links}) {
+    for (const [i, node] of nodes.entries()) {
       node.index = i;
       node.sourceLinks = [];
       node.targetLinks = [];
-    });
-    var nodeById = map(graph.nodes, id);
-    graph.links.forEach(function(link, i) {
+    }
+    const nodeById = new Map(nodes.map((d, i) => [id(d, i, nodes), d]));
+    for (const [i, link] of links.entries()) {
       link.index = i;
-      var source = link.source, target = link.target;
+      let {source, target} = link;
       if (typeof source !== "object") source = link.source = find(nodeById, source);
@@ -130,8 +143,7 @@ if (typeof target !== "object") target = link.target = find(nodeById, target);
       target.targetLinks.push(link);
-    });
+    }
   }
 
-  // Compute the value (size) of each node by summing the associated links.
-  function computeNodeValues(graph) {
-    graph.nodes.forEach(function(node) {
+  function computeNodeValues({nodes}) {
+    for (const node of nodes) {
       node.value = Math.max(
@@ -141,185 +153,187 @@ sum(node.sourceLinks, value),
       );
-    });
+    }
   }
 
-  // Iteratively assign the depth (x-position) for each node.
-  // Nodes are assigned the maximum depth of incoming neighbors plus one;
-  // nodes with no incoming links are assigned depth zero, while
-  // nodes with no outgoing links are assigned the maximum depth.
-  function computeNodeDepths(graph) {
-    var nodes, next, x, n = graph.nodes.length;
-
-    for (nodes = graph.nodes, next = [], x = 0; nodes.length; ++x, nodes = next, next = []) {
-      if (x > n) throw new Error("circular link");
-      nodes.forEach(function(node) {
+  function computeNodeDepths({nodes}) {
+    const n = nodes.length;
+    let current = new Set(nodes);
+    let next = new Set;
+    let x = 0;
+    while (current.size) {
+      for (const node of current) {
         node.depth = x;
-        node.sourceLinks.forEach(function(link) {
-          if (next.indexOf(link.target) < 0) {
-            next.push(link.target);
-          }
-        });
-      });
+        for (const {target} of node.sourceLinks) {
+          next.add(target);
+        }
+      }
+      if (++x > n) throw new Error("circular link");
+      current = next;
+      next = new Set;
     }
+  }
 
-    for (nodes = graph.nodes, next = [], x = 0; nodes.length; ++x, nodes = next, next = []) {
-      if (x > n) throw new Error("circular link");
-      nodes.forEach(function(node) {
+  function computeNodeHeights({nodes}) {
+    const n = nodes.length;
+    let current = new Set(nodes);
+    let next = new Set;
+    let x = 0;
+    while (current.size) {
+      for (const node of current) {
         node.height = x;
-        node.targetLinks.forEach(function(link) {
-          if (next.indexOf(link.source) < 0) {
-            next.push(link.source);
-          }
-        });
-      });
+        for (const {source} of node.targetLinks) {
+          next.add(source);
+        }
+      }
+      if (++x > n) throw new Error("circular link");
+      current = next;
+      next = new Set;
     }
-
-    var kx = (x1 - x0 - dx) / (x - 1);
-    graph.nodes.forEach(function(node) {
-      node.layer = Math.max(0, Math.min(x - 1, Math.floor(align.call(null, node, x))));
-      node.x1 = (node.x0 = x0 + node.layer * kx) + dx;
-    });
   }
 
-  function computeNodeBreadths(graph) {
-    var columns = nest()
-        .key(function(d) { return d.x0; })
-        .sortKeys(ascending)
-        .entries(graph.nodes)
-        .map(function(d) { return d.values; });
-
-    //
-    initializeNodeBreadth();
-    for (var i = 0, n = iterations; i < n; ++i) {
-      const a = Math.pow(0.99, i);
-      const b = (i + 1) / n;
-      reorderLinks(graph);
-      relaxRightToLeft(a);
-      resolveCollisionsTopToBottom(b);
-      resolveCollisionsBottomToTop(b);
-      reorderLinks(graph);
-      relaxLeftToRight(a);
-      resolveCollisionsTopToBottom(b);
-      resolveCollisionsBottomToTop(b);
+  function computeNodeLayers({nodes}) {
+    const x = max(nodes, d => d.depth) + 1;
+    const kx = (x1 - x0 - dx) / (x - 1);
+    const columns = new Array(x);
+    for (const node of nodes) {
+      const i = Math.max(0, Math.min(x - 1, Math.floor(align.call(null, node, x))));
+      node.layer = i;
+      node.x0 = x0 + i * kx;
+      node.x1 = node.x0 + dx;
+      if (columns[i]) columns[i].push(node);
+      else columns[i] = [node];
     }
-
-    function initializeNodeBreadth() {
-      var ky = min(columns, function(nodes) {
-        return (y1 - y0 - (nodes.length - 1) * py) / sum(nodes, value);
-      });
-
-      columns.forEach(function(nodes) {
-        if (sort != null) nodes.sort(sort);
-        let y = y0;
-        nodes.forEach(function(node) {
-          node.y0 = y;
-          node.y1 = y + node.value * ky;
-          y = node.y1 + py;
-        });
-      });
-
-      graph.links.forEach(function(link) {
-        link.width = link.value * ky;
-      });
-
-      if (linkSort != null) graph.nodes.forEach(function(node) {
-        node.sourceLinks.sort(linkSort);
-        node.targetLinks.sort(linkSort);
-      });
+    if (sort) for (const column of columns) {
+      column.sort(sort);
     }
+    return columns;
+  }
 
-    // Reposition each node based on its incoming (target) links.
-    function relaxLeftToRight(alpha) {
-      columns.slice(1).forEach(function(nodes) {
-        nodes.forEach(function(target) {
-          let y = 0;
-          let w = 0;
-          for (const {source, value} of target.targetLinks) {
-            let v = value * (target.layer - source.layer);
-            y += targetTop(source, target) * v;
-            w += v;
-          }
-          if (!(w > 0)) return;
-          let dy = (y / w - target.y0) * alpha;
-          target.y0 += dy;
-          target.y1 += dy;
-        });
-      });
+  function initializeNodeBreadths(columns) {
+    const ky = min(columns, c => (y1 - y0 - (c.length - 1) * py) / sum(c, value));
+    for (const nodes of columns) {
+      let y = y0;
+      for (const node of nodes) {
+        node.y0 = y;
+        node.y1 = y + node.value * ky;
+        y = node.y1 + py;
+        for (const link of node.sourceLinks) {
+          link.width = link.value * ky;
+        }
+      }
+      y = (y1 - y + py) / (nodes.length + 1);
+      for (let i = 0; i < nodes.length; ++i) {
+        const node = nodes[i];
+        node.y0 += y * (i + 1);
+        node.y1 += y * (i + 1);
+      }
+      reorderLinks(nodes);
     }
+  }
 
-    // Reposition each node based on its outgoing (source) links.
-    function relaxRightToLeft(alpha) {
-      columns.slice(0, -1).reverse().forEach(function(nodes) {
-        nodes.forEach(function(source) {
-          let y = 0;
-          let w = 0;
-          for (const {target, value} of source.sourceLinks) {
-            let v = value * (target.layer - source.layer);
-            y += sourceTop(source, target) * v;
-            w += v;
-          }
-          if (!(w > 0)) return;
-          let dy = (y / w - source.y0) * alpha;
-          source.y0 += dy;
-          source.y1 += dy;
-        });
-      });
+  function computeNodeBreadths(graph) {
+    const columns = computeNodeLayers(graph);
+    initializeNodeBreadths(columns);
+    for (let i = 0; i < iterations; ++i) {
+      const beta = ((i + 1) / iterations) ** 1.5;
+      const alpha = 1 - beta;
+      relaxRightToLeft(columns, alpha, beta);
+      relaxLeftToRight(columns, alpha, beta);
     }
+  }
 
-    // Push any overlapping nodes down.
-    function resolveCollisionsTopToBottom(alpha) {
-      columns.forEach(function(nodes) {
-        var node,
-            dy,
-            y = y0,
-            n = nodes.length,
-            i;
-        if (sort === undefined) nodes.sort(ascendingBreadth);
-        for (i = 0; i < n; ++i) {
-          node = nodes[i];
-          dy = (y - node.y0) * alpha;
-          if (dy > 1e-6) node.y0 += dy, node.y1 += dy;
-          y = node.y1 + py;
+  // Reposition each node based on its incoming (target) links.
+  function relaxLeftToRight(columns, alpha, beta) {
+    for (let i = 1, n = columns.length; i < n; ++i) {
+      const column = columns[i];
+      for (const target of column) {
+        let y = 0;
+        let w = 0;
+        for (const {source, value} of target.targetLinks) {
+          let v = value * (target.layer - source.layer);
+          y += targetTop(source, target) * v;
+          w += v;
         }
-      });
+        if (!(w > 0)) continue;
+        let dy = (y / w - target.y0) * alpha;
+        target.y0 += dy;
+        target.y1 += dy;
+        reorderNodeLinks(target);
+      }
+      if (sort === undefined) column.sort(ascendingBreadth);
+      resolveCollisions(column, beta);
     }
+  }
 
-    // Push any overlapping nodes up.
-    function resolveCollisionsBottomToTop(alpha) {
-      columns.forEach(function(nodes) {
-        var node,
-            dy,
-            y = y1,
-            n = nodes.length,
-            i;
-        if (sort === undefined) nodes.sort(ascendingBreadth);
-        for (i = n - 1; i >= 0; --i) {
-          node = nodes[i];
-          dy = (node.y1 - y) * alpha;
-          if (dy > 1e-6) node.y0 -= dy, node.y1 -= dy;
-          y = node.y0 - py;
+  // Reposition each node based on its outgoing (source) links.
+  function relaxRightToLeft(columns, alpha, beta) {
+    for (let n = columns.length, i = n - 2; i >= 0; --i) {
+      const column = columns[i];
+      for (const source of column) {
+        let y = 0;
+        let w = 0;
+        for (const {target, value} of source.sourceLinks) {
+          let v = value * (target.layer - source.layer);
+          y += sourceTop(source, target) * v;
+          w += v;
         }
-      });
+        if (!(w > 0)) continue;
+        let dy = (y / w - source.y0) * alpha;
+        source.y0 += dy;
+        source.y1 += dy;
+        reorderNodeLinks(source);
+      }
+      if (sort === undefined) column.sort(ascendingBreadth);
+      resolveCollisions(column, beta);
     }
   }
 
-  function reorderLinks(graph) {
-    if (linkSort === undefined) graph.nodes.forEach(function(node) {
-      node.sourceLinks.sort(ascendingTargetBreadth);
-      node.targetLinks.sort(ascendingSourceBreadth);
-    });
+  function resolveCollisions(nodes, alpha) {
+    const i = nodes.length >> 1;
+    const subject = nodes[i];
+    resolveCollisionsBottomToTop(nodes, subject.y0 - py, i - 1, alpha);
+    resolveCollisionsTopToBottom(nodes, subject.y1 + py, i + 1, alpha);
+    resolveCollisionsBottomToTop(nodes, y1, nodes.length - 1, alpha);
+    resolveCollisionsTopToBottom(nodes, y0, 0, alpha);
   }
 
-  function computeLinkBreadths(graph) {
-    reorderLinks(graph);
-    graph.nodes.forEach(function(node) {
-      var y0 = node.y0, y1 = y0;
-      node.sourceLinks.forEach(function(link) {
-        link.y0 = y0 + link.width / 2, y0 += link.width;
-      });
-      node.targetLinks.forEach(function(link) {
-        link.y1 = y1 + link.width / 2, y1 += link.width;
-      });
-    });
+  // Push any overlapping nodes down.
+  function resolveCollisionsTopToBottom(nodes, y, i, alpha) {
+    for (; i < nodes.length; ++i) {
+      const node = nodes[i];
+      const dy = (y - node.y0) * alpha;
+      if (dy > 1e-6) node.y0 += dy, node.y1 += dy;
+      y = node.y1 + py;
+    }
   }
 
+  // Push any overlapping nodes up.
+  function resolveCollisionsBottomToTop(nodes, y, i, alpha) {
+    for (; i >= 0; --i) {
+      const node = nodes[i];
+      const dy = (node.y1 - y) * alpha;
+      if (dy > 1e-6) node.y0 -= dy, node.y1 -= dy;
+      y = node.y0 - py;
+    }
+  }
+
+  function reorderNodeLinks({sourceLinks, targetLinks}) {
+    if (linkSort === undefined) {
+      for (const {source: {sourceLinks}} of targetLinks) {
+        sourceLinks.sort(ascendingTargetBreadth);
+      }
+      for (const {target: {targetLinks}} of sourceLinks) {
+        targetLinks.sort(ascendingSourceBreadth);
+      }
+    }
+  }
+
+  function reorderLinks(nodes) {
+    if (linkSort === undefined) {
+      for (const {sourceLinks, targetLinks} of nodes) {
+        sourceLinks.sort(ascendingTargetBreadth);
+        targetLinks.sort(ascendingSourceBreadth);
+      }
+    }
+  }
+
   // Returns the target.y0 that would produce an ideal link from source to target.
@@ -326,0 +340,0 @@ function targetTop(source, target) {

No alert changes

Improved metrics

Total package byte prevSize

76682

increased by0.25%

Dependency count

2

decreased by-33.33%

Lines of code

794

increased by6.01%

Dependency changes

• + Addedd3-array@2.12.1(transitive)

• + Addedinternmap@1.0.1(transitive)

• - Removedd3-collection@1

• - Removedd3-array@1.2.4(transitive)

• - Removedd3-collection@1.0.7(transitive)

• Updatedd3-array@>=1 <=2