in src/state/layout/hierarchicalLayout.ts [30:191]
export default function hierarchicalLayout<NodeType, EdgeType>(
state: DiagramMakerData<NodeType, EdgeType>,
layoutConfig: HierarchicalLayoutConfig
): DiagramMakerData<NodeType, EdgeType> {
// Initialize config values with defaults, if needed.
const distanceMin = layoutConfig.distanceMin;
const distanceMax = isNumber(layoutConfig.distanceMax) ? layoutConfig.distanceMax : (3 * distanceMin);
const distanceDeclineRate = isNumber(layoutConfig.distanceDeclineRate) ? layoutConfig.distanceDeclineRate : 0.3;
const initialGravityAngle = isNumber(layoutConfig.gravityAngle)
? normalizeAngle(-layoutConfig.gravityAngle) // As Y-axis points down, the angle must be inverted.
: (Math.PI * 0.5); // Default gravity points straight down.
const gravityStrength = isNumber(layoutConfig.gravityStrength) ? layoutConfig.gravityStrength : 0.0;
// Construct an initial graph without calculated positioning.
const fixedNodeIdSet: { [key: string]: boolean } = {};
layoutConfig.fixedNodeIds.forEach(nodeId => fixedNodeIdSet[nodeId] = true);
const fixedNodes: number[] = [];
const nodeIndex: { [key: string]: number } = {};
const graph: GraphNode[] = values(state.nodes).map((node, index) => {
nodeIndex[node.id] = index;
const graphNode: GraphNode = {
id: node.id,
neighbors: [],
parents: []
};
const position = node.diagramMakerData.position;
const size = node.diagramMakerData.size;
if (fixedNodeIdSet[node.id]) {
graphNode.isFixed = true;
graphNode.x = position.x + size.width / 2;
graphNode.y = position.y + size.height / 2;
fixedNodes.push(index);
}
return graphNode;
});
// Add neighbor information based on DiagramMaker edges.
values(state.edges).forEach((edge) => {
const srcIndex = nodeIndex[edge.src];
const destIndex = nodeIndex[edge.dest];
// Note:
// The directionality of the graph is ignored.
// No matter if we're laying out children nodes around the parent,
// or parent nodes around the child, the same rules spread in both directions.
graph[srcIndex].neighbors.push(destIndex);
graph[destIndex].neighbors.push(srcIndex);
});
// Calculate positioning during BFS traversal.
const nodeStatus: TraversalStatus[] = graph.map(
node => node.isFixed ? TraversalStatus.VISITED : TraversalStatus.NOT_VISITED
);
let currentLayer: number[] = fixedNodes;
let r = distanceMax;
while (currentLayer.length) {
// Mark current layer as VISITED.
currentLayer.forEach((node) => {
nodeStatus[node] = TraversalStatus.VISITED;
});
// Calculate next layer by traversing neighbors of the current layer.
const nextLayer: number[] = [];
currentLayer.forEach((node) => {
graph[node].neighbors.forEach((neighbor) => {
if (nodeStatus[neighbor] === TraversalStatus.VISITED) { return; }
graph[neighbor].parents.push(node);
if (nodeStatus[neighbor] === TraversalStatus.NOT_VISITED) {
nextLayer.push(neighbor);
nodeStatus[neighbor] = TraversalStatus.PROCESSING;
}
});
});
// Position the next layer.
// Start with the nodes that are connected to multiple fixed parents.
// Place them in the centroid of all of their parents.
nextLayer.forEach((node) => {
if (graph[node].parents.length > 1) {
const parentsCount = graph[node].parents.length;
const sumX = graph[node].parents.reduce((sum, parent) => sum + (graph[parent].x as number), 0);
graph[node].x = sumX / parentsCount;
const sumY = graph[node].parents.reduce((sum, parent) => sum + (graph[parent].y as number), 0);
graph[node].y = sumY / parentsCount;
graph[node].isFixed = true;
}
});
// Calculate the fixtures (angles that are already fixed) for each node in the current layer.
const fixtures: NodeDirection[][] = graph.map(node => []);
currentLayer.forEach((node) => {
graph[node].neighbors.forEach((neighbor) => {
if (graph[neighbor].isFixed) {
fixtures[node].push({
angle: getAngle(graph[node], graph[neighbor]),
isFixed: true
});
}
});
sortNodeDirections(fixtures[node]);
});
// Distribute all remaining free-hanging nodes between the fixtures.
currentLayer.forEach((node) => {
let gravityAngle = initialGravityAngle;
const meanOfFixtures = meanOfAngles(fixtures[node].map(fixture => fixture.angle));
if (!isNaN(meanOfFixtures)) {
gravityAngle = normalizeAngle(meanOfFixtures + Math.PI);
}
const freeNodesCount = graph[node].neighbors.length - fixtures[node].length;
const arrangement = arrangeEvenly(freeNodesCount, fixtures[node], gravityAngle);
applyGravity(arrangement, gravityAngle, gravityStrength);
let arrangementIndex = 0;
graph[node].neighbors.forEach((neighbor) => {
if (!graph[neighbor].isFixed) {
while (arrangement[arrangementIndex].isFixed) {
arrangementIndex += 1;
}
const angle = arrangement[arrangementIndex].angle;
graph[neighbor].x = (graph[node].x as number) + Math.cos(angle) * r;
graph[neighbor].y = (graph[node].y as number) + Math.sin(angle) * r;
graph[neighbor].isFixed = true;
arrangementIndex += 1;
}
});
});
// Move on to the next layer.
currentLayer = nextLayer;
r = distanceMin + (r - distanceMin) * (1 - distanceDeclineRate);
}
// Update the original data with the calculated values.
return produce(state, (draftState) => {
graph.forEach((node) => {
if (isFinite(node.x) && isFinite(node.y)) {
const nodeSize = draftState.nodes[node.id].diagramMakerData.size;
const diagramMakerNode = draftState.nodes[node.id].diagramMakerData.position = {
x: (node.x as number) - nodeSize.width / 2,
y: (node.y as number) - nodeSize.height / 2
};
}
});
});
}