# `Yog.Layout.Tutte`
[🔗](https://github.com/code-shoily/yog_ex/blob/v1.0.0/lib/yog/layout/tutte.ex#L1)

Tutte embedding (barycentric layout) algorithm for planar graphs in Elixir.

Tutte's embedding theorem states that if a graph is 3-vertex-connected and planar,
pinning its outer boundary to a convex polygon and placing every interior node at
the average (barycenter) of its neighbors' positions yields a planar layout
without any edge crossings.

Rather than solving the large sparse linear system ($Ax = b$) directly via matrix
inversion, this module uses **Gauss-Seidel relaxation** (iterative relaxation),
which runs in pure Elixir without native matrix solver libraries.

## Mathematical Model

1. **Boundary Nodes ($V_b$):** Pinned to a circle or regular polygon centered at $(c_x, c_y)$ with radius $R$.
2. **Interior Nodes ($V_i = V \setminus V_b$):** Positioned iteratively. For each interior node $u$:
   $$x_u = \frac{1}{deg(u)} \sum_{v \in N(u)} x_v$$
   $$y_u = \frac{1}{deg(u)} \sum_{v \in N(u)} y_v$$
   where $N(u)$ is the set of neighbors of $u$, and $deg(u)$ is the degree of $u$.

## Complexities

* **Time Complexity:** $O(I \cdot (V + E))$ where $I$ is iterations, $V$ is nodes, $E$ is edges.
* **Space Complexity:** $O(V)$ auxiliary space.

## References

* [Tutte 1963 - How to Draw a Graph](https://doi.org/10.1112/plms/s3-13.1.743)
* [Wikipedia: Tutte embedding](https://en.wikipedia.org/wiki/Tutte_embedding)

# `layout`

```elixir
@spec layout(Yog.Graph.t() | Yog.DAG.t(), [Yog.Graph.node_id()], keyword()) :: %{
  required(Yog.Graph.node_id()) => {float(), float()}
}
```

Positions nodes using Tutte's barycentric embedding.

Requires a list of `boundary_nodes` (ordered) forming the outer convex boundary polygon.

## Options

  * `:iterations` - Number of relaxation steps to run (default: `100`).
  * `:radius` - Bounding boundary radius (default: `1.0`).
  * `:center` - Center of boundary circle (default: `{0.0, 0.0}`).

## Examples

    iex> graph = Yog.from_unweighted_edges(:undirected, [{1, 2}, {2, 3}, {3, 1}, {1, 4}, {2, 4}, {3, 4}])
    iex> pos = Yog.Layout.Tutte.layout(graph, [1, 2, 3])
    iex> Map.keys(pos) |> Enum.sort()
    [1, 2, 3, 4]

---

*Consult [api-reference.md](api-reference.md) for complete listing*