Spring layout algorithm (Fruchterman-Reingold force-directed) for positioning graph nodes in Elixir.
This algorithm models a graph as a physical system of particles (nodes) and springs (edges) to reach an aesthetically pleasing layout by minimizing the total system energy. Nodes repel each other like electrically charged particles, while edges pull connected nodes closer like springs.
Mathematical Model
Given a graph $G = (V, E)$ in a 2D space of size $W \times H$, the algorithm simulates two competing forces:
- Repulsive Force ($f_r$): Pushes every pair of nodes $(u, v)$ apart to prevent overlap and ensure spacing. $$ f_r(d) = \frac{k^2}{d} $$ where $d$ is the Euclidean distance between $u$ and $v$.
- Attractive Force ($f_a$): Pulls connected nodes $(u, v) \in E$ together to reflect topological proximity. $$ f_a(d) = \frac{d^2}{k} \cdot w $$ where $w$ is the optional edge weight multiplier.
Parameters
- Optimal Node Distance ($k$): Represents the target spacing between nodes. It is calculated based on the bounding box size: $$ k = \sqrt{\frac{W \cdot H}{|V|}} $$
- Cooling Schedule: A maximum displacement limit ("temperature" $T$) decays linearly with each iteration to stabilize the simulation: $$ T_i = T_{\text{initial}} \cdot \left(1 - \frac{i}{I}\right) $$ where $i$ is the current iteration and $I$ is the maximum number of iterations.
Complexities
- Time Complexity: $O(I \cdot (V^2 + E))$ per simulation run, where $I$ is the number of iterations (default
50), $V$ is the number of nodes, and $E$ is the number of edges. - Space Complexity: $O(V + E)$ auxiliary space to store displacements and positions.
References
Summary
Functions
Positions nodes using a force-directed model.
Functions
@spec layout( Yog.Graph.t(), keyword() ) :: %{required(Yog.Graph.node_id()) => {float(), float()}}
Positions nodes using a force-directed model.
Options
:width- The width of the layout space (default:1.0).:height- The height of the layout space (default:1.0).:center- The{x, y}coordinates of the center (default:{0.0, 0.0}).:iterations- Number of iterations to run the simulation (default:50).:k- Optimal distance between nodes. If not provided, computed assqrt(width * height / V).:initial_temp- Initial temperature/step limit (default:0.1).:weight- Boolean indicating whether to respect edge weights (default:true).:fixed- List of node IDs that should not move during simulation (default:[]).:initial_pos- Map ofnode_id => {x, y}coordinates to use as initial layout. If not provided, random positions are used.:seed- Seed for random positioning generator.:barnes_hut- Boolean indicating whether to use the Barnes-Hut approximation to reduce repulsive force computation complexity from $O(V^2)$ to $O(V log V)$ (default:false).:theta- The Barnes-Hut threshold parameter $ heta$. A value of0.0yields exact computation, while higher values (e.g.,0.5or1.0) trade layout quality for performance (default:0.5).
Examples
iex> graph = Yog.undirected() |> Yog.add_nodes_from([1, 2, 3]) |> Yog.add_edges!([{1, 2, 10}, {2, 3, 5}])
iex> pos = Yog.Layout.Spring.layout(graph, iterations: 10)
iex> Map.keys(pos) |> Enum.sort()
[1, 2, 3]
iex> graph = Yog.undirected() |> Yog.add_nodes_from([1, 2, 3]) |> Yog.add_edges!([{1, 2, 10}, {2, 3, 5}])
iex> pos_bh = Yog.Layout.Spring.layout(graph, iterations: 10, barnes_hut: true, theta: 0.5)
iex> Map.keys(pos_bh) |> Enum.sort()
[1, 2, 3]