in packages-ext/recoil-devtools/src/utils/sankey/SankeyGraphLayout.js [228:480]
function layoutPositions<N, L>(
graph: Graph<N, L>,
layoutOptions: PositionLayoutOptions,
maxBreadth: number,
): [number, number] {
const visibleNodes = graph.nodes.filter(node => node.visible);
// Prepare set of depths
const depths: Array<
Array<Node<mixed, mixed>> & {paddingPercent: number, padding: number},
> = d3Collection
.nest()
.key(n => n.depth)
.entries(visibleNodes)
.map(g => g.values);
sortAsc(depths, depth => depth[0]?.depth); // d3.nest().sortKeys() didn't work?
// Calculate node padding and positions
// Start by determining the percentage of each column to use for padding
const {nodePadding} = layoutOptions;
if (typeof nodePadding === 'number') {
for (const depth of depths) {
depth.paddingPercent = Math.max(
(nodePadding * (depth.length - 1)) / maxBreadth,
0.8,
);
}
} else if (nodePadding.charAt(nodePadding.length - 1) === '%') {
for (const depth of depths) {
depth.paddingPercent =
depth.length === 1 ? 0 : +nodePadding.slice(0, -1) / 100;
depth.paddingPercent =
depth.paddingPercent === 1 ? 0.999 : depth.paddingPercent;
}
} else {
throw new Error(
`Unsupported nodePadding parameter: ${String(nodePadding)}`,
);
}
// Calculate maximum breadth, including padding
const maxPosition: number = d3Array.max(
depths.map(
depth =>
d3Array.sum(depth, node => node.value) / (1 - depth.paddingPercent),
),
);
// Calculate node padding for each depth
for (const depth of depths) {
depth.padding =
depth.length === 1
? 0
: (maxPosition * depth.paddingPercent) / (depth.length - 1);
}
// Detect collisions and move nodes to avoid overlap
function collisionDetection() {
for (const depth of depths) {
sortAsc(depth, n => n.position);
// Push overlapping nodes down
let position = 0;
for (const node of depth) {
const delta = position - node.position;
if (delta > 0) {
node.position += delta;
}
position = node.position + node.value + depth.padding;
}
// If they extend past the edge, then push some nodes back
const lastNode = depth[depth.length - 1];
if (lastNode.position + lastNode.value > maxPosition) {
position = maxPosition;
for (const node of [...depth].reverse()) {
const delta = node.position + node.value - position;
if (delta > 0) {
node.position -= delta;
} else {
break;
}
position = node.position - depth.padding;
}
}
}
}
// Assign node link weights
for (const node of visibleNodes) {
const sourceWeight: number = d3Array.sum(node.sourceLinks, l => l.value);
const targetWeight: number = d3Array.sum(node.targetLinks, l => l.value);
node.linkWeight =
sourceWeight + targetWeight * layoutOptions.targetLinksWeight;
}
function layoutLinks() {
for (const depth of depths) {
const padding =
depth.length > 1
? depth.padding
: depth.length === 1
? maxPosition - depth[0].value
: 0;
for (const node of depth) {
sortAsc(node.sourceLinks, link => link.source?.position ?? Infinity);
let trailingPosition = node.position - padding / 2;
let trailingPadding = padding / (node.sourceLinks.length - 1);
let position = node.position;
for (const sourceLink of node.sourceLinks) {
sourceLink.targetDepth = node.depth;
sourceLink.targetPosition = position;
position += sourceLink.value;
// Trailing link to missing node
if (sourceLink.fadeSource) {
sourceLink.sourceDepth = node.depth - 1;
sourceLink.sourcePosition = trailingPosition;
}
trailingPosition += sourceLink.value + trailingPadding;
}
sortAsc(node.targetLinks, link => link.target?.position ?? Infinity);
position = node.position;
trailingPosition = node.position - padding / 2;
trailingPadding = padding / (node.targetLinks.length - 1);
for (const targetLink of node.targetLinks) {
targetLink.sourceDepth = node.depth;
targetLink.sourcePosition = position;
position += targetLink.value;
// Trailing link to missing node
if (targetLink.fadeTarget) {
targetLink.targetDepth = node.depth + 1;
targetLink.targetPosition = trailingPosition;
}
trailingPosition += targetLink.value + trailingPadding;
}
}
}
}
// Give nodes and links an initial position
for (const [i, depth] of depths.entries()) {
// Sort the nodes
layoutOptions.sortNodes === 'ascending' ||
layoutOptions.sortNodes === 'inward'
? sortAsc(depth, node => node.value)
: sortDesc(depth, node => node.value);
if (
layoutOptions.sortNodes === 'outward' ||
layoutOptions.sortNodes === 'inward'
) {
// Arrange nodes for the first depth with large nodes on each end in an
// attempt to avoid links crossing over each other.
const newDepthNodes = [
...depth.filter((_, i) => !(i % 2)),
...depth
.reverse()
.slice(depth.length % 2)
.filter((_, i) => !(i % 2)),
];
for (const [i, node] of newDepthNodes.entries()) {
depth[i] = node;
}
}
if (!i) {
let position = 0;
for (const node of depths[0]) {
node.position = position;
position += node.value + depths[0].padding;
}
} else {
// For each subsequent depth, align the nodes to the right of their sources
// in an attempt for flatter links
for (const node of depth) {
let weightedPosition = 0;
let sourceLinkValue = 0;
let totalWeightedPosition = 0;
let totalSourceLinkValue = 0;
for (const sourceLink of node.sourceLinks) {
const source = sourceLink.source;
if (source == null) {
continue;
}
totalWeightedPosition += source.position * sourceLink.value;
totalSourceLinkValue += sourceLink.value;
// Only provide initial layout for forward links, not back edges
if (source.depth >= node.depth) {
continue;
}
weightedPosition += source.position * sourceLink.value;
sourceLinkValue += sourceLink.value;
}
if (sourceLinkValue) {
node.position = weightedPosition / sourceLinkValue;
} else if (totalSourceLinkValue) {
// If all source links were back-edges, then just average them all
node.position = totalWeightedPosition / totalSourceLinkValue;
} else {
// If there are no source links at all, then average the target links
// This can't happen in a normal Sankey, since all nodes with no
// sources are in the first depth, but it can happen with a butterfly.
let targetLinkValue = 0;
for (const targetLink of node.targetLinks) {
const target = targetLink.target;
if (target == null) {
continue;
}
weightedPosition += target.position * targetLink.value;
targetLinkValue += targetLink.value;
}
node.position = weightedPosition / (targetLinkValue || 1);
}
}
}
}
collisionDetection();
layoutLinks();
// Now iterate on the layout to shift nodes closer to their neighbors
// based on the values of their links
let alpha = 1;
for (let iteration = 0; iteration < layoutOptions.iterations; iteration++) {
alpha *= layoutOptions.alpha;
for (const depth of depths) {
for (const node of depth) {
let delta = 0;
for (const sourceLink of node.sourceLinks) {
// Not back-edges
if (sourceLink.targetDepth > sourceLink.sourceDepth) {
delta +=
(sourceLink.sourcePosition - sourceLink.targetPosition) *
sourceLink.value;
}
}
for (const targetLink of node.targetLinks) {
// Not back-edges
if (targetLink.targetDepth > targetLink.sourceDepth) {
delta +=
(targetLink.targetPosition - targetLink.sourcePosition) *
targetLink.value *
// Weight alignment with target nodes less, to avoid cross-over
layoutOptions.targetLinksWeight;
}
}
delta /= node.linkWeight;
node.position += delta * alpha;
}
}
collisionDetection();
layoutLinks();
}
return [0, maxPosition];
}