← Algorithms

Solving positions instead of assigning them

Why a diagram engine reaches for a union-find, and how "hard beats soft" falls out of it for free.

In the code: foundation/solve.py

Most layout engines walk a tree and hand out coordinates: you are at x=40, you are at x=140. Sauvignon does not. It writes down what it knows about relative positions and then solves for the rest.

The trick is that almost everything you want to say about a diagram, on one axis, is the same shape of statement:

pos[a] = pos[b] + offset

"Second child sits 20px below the first." "These two share a left edge." "Space these evenly." All of it. That is a difference constraint, and a system made only of difference constraints is much easier than general linear algebra: you never need a simplex solver, just bookkeeping.

Union-find, but weighted

Two variables related by a difference constraint have a fixed offset forever. So group them: each connected group has one representative ("root"), and every member stores its offset from that root. That is a weighted union-find (also called a union-find with potentials, or a disjoint-set with offsets).

Each variable stores off[v] = pos[v] − pos[parent[v]]. To find a variable's root you walk up the parent chain, summing offsets as you go — that sum is its position relative to the root.

To relate a and b, find both roots. If they differ, hang one root under the other with exactly the offset that makes the new constraint true:

parent[rb] = ra
off[rb]    = (off_a − off_b) − delta

If the roots are already the same, no linking is possible — the relationship is already implied. All you can do is check it: if the implied offset disagrees with what is being asserted, the diagram is over-constrained, and that is an author error worth reporting.

Both axes are solved this way, independently. That independence is cheap and fast, and it is also the engine's ceiling — see the end of this article.

Path compression has to carry the offsets

The classic union-find optimisation is to re-point every node you walked past straight at the root. Here you cannot just re-point them, because each node's stored offset is relative to its old parent. Re-pointing without fixing the offset silently corrupts every position downstream.

So the walk records each node together with its running offset, and the second pass rewrites each one to be relative to the root:

for node, offset_to_node in path:
    parent[node] = root
    off[node] = total_offset − offset_to_node

This is the one genuinely fiddly line in the solver, and the reason the find operation is written as two passes rather than a tidy recursion.

Hard beats soft, for free

Here is the part that makes the whole design worth it. Sauvignon adds constraints in two tiers:

• hard — explicit relations you wrote: <align>, <distribute>. Added first. If two disagree, that is an error.
• soft — the structural tree: each child offset from its container. Added afterwards, and skipped wherever it would contradict something already established.

That is about six lines of code, and it buys the language its most distinctive behaviour: an explicit relation overrides the default placement rather than fighting it. Because both tiers live in one pool, a node can be stacked, aligned, and connected at once — and you can align two elements in different parents, which a strict layout tree cannot express at all.

<diagram padding="16">
  <row gap="60" align="start">
    <column gap="10">
      <rect id="a1" width="86">soft</rect>
      <rect id="a2" width="86">soft</rect>
    </column>
    <column gap="10">
      <rect id="b1" width="86">soft</rect>
      <rect id="b2" width="86">soft</rect>
    </column>
  </row>
  <align of="a2 b1" edge="center-y"/>
</diagram>

Nothing in those two columns knows about the other. The <align> is a hard constraint that reaches across both, and the structural constraint that would have contradicted it is quietly dropped.

The ceiling

Difference constraints are equalities on independent axes. That is the whole vocabulary, and it forecloses two things:

• inequalities and optimisation — no "at least 20px apart", no force-directed or otherwise optimised placement. Real constraint layout systems (Cassowary, as used by Apple's Auto Layout, or the IPSep-CoLa solver behind graph layout in Dunnart) handle inequalities and minimise an objective.
• coupled axes — nothing like "on a circle", because x and y never meet.

That is why Sauvignon has no automatic tree or graph layout. It is also contained: the solver is one small module, so a stronger engine could be dropped in without touching the front-end, the IRs, or the renderer.

Further reading. Tarjan's Efficiency of a Good But Not Linear Set Union Algorithm (1975) for union-find and why path compression matters; Badros, Borning & Stuckey, The Cassowary Linear Arithmetic Constraint Solving Algorithm (2001) for what the next tier up looks like.