Multipartite layout algorithm for positioning graph nodes in parallel layers.

Arranges nodes in straight parallel lines (either vertical columns or horizontal rows) based on their partition/layer membership. This layout is standard for bipartite graphs, feedforward neural network visualizations, flow networks, or any layered hierarchical relationships.

Mathematical Model

Given a list of layers $L = [L_0, L_1, \dots, L_{M-1}]$, where each $L_j$ is a list of node IDs, a bounding space of size $W \times H$, and center $(c_x, c_y)$:

If :align is :vertical (default):

1. The $x$-coordinate for all nodes in layer $L_j$ is: $$ x_j = \left(c_x - \frac{W}{2}\right) + \frac{j \cdot W}{M - 1} $$ (or $c_x$ if $M = 1$).
2. For the $i$-th node in layer $L_j$ (where $0 \le i < K$ and $K = |L_j|$): $$ y_i = \left(c_y - \frac{H}{2}\right) + \frac{i \cdot H}{K - 1} $$ (or $c_y$ if $K = 1$).

If :align is :horizontal:

1. The $y$-coordinate for all nodes in layer $L_j$ is: $$ y_j = \left(c_y - \frac{H}{2}\right) + \frac{j \cdot H}{M - 1} $$ (or $c_y$ if $M = 1$).
2. For the $i$-th node in layer $L_j$ (where $0 \le i < K$ and $K = |L_j|$): $$ x_i = \left(c_x - \frac{W}{2}\right) + \frac{i \cdot W}{K - 1} $$ (or $c_x$ if $K = 1$).

Complexities

• Time Complexity: $O(V)$ where $V$ is the number of nodes.
• Space Complexity: $O(V)$ auxiliary space.