export default function hierarchicalLayout()

in src/state/layout/hierarchicalLayout.ts [30:191]

• 98 lines of code
• 14 McCabe index (conditional complexity)

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
        };
      }
    });
  });
}