Layouts

A layout algorithm is a structured approach to rendering information: specifically it solves the problem of where do things go.

You’re looking at a web page right now organized by layout algorithms that implement the CSS Box Model. This page benefits from layout tree construction, box size calculation, flow layout algorithms and positioning algorithms.

I find layout algorithms really interesting. They drive so much of how we interact with the digital world, and when they work well they seem amost magical.

So I thought today I’d take a look at a class of layout algorithms called hierarchical layout algorithms. These represent information that can be encoded in a graph, like a tree or diagram.

The problem is, given a set of nodes and edges:

{
    nodes: ["🐄", "🥛", "🧀", "🧈"],
    edges: [
        {in: "🐄", out: "🥛"},
        {in: "🥛", out: "🧀"},
        {in: "🥛", out: "🧈"},
    ]
}

How do we generate something like this?

Drawing the diagram is easy enough in javascript if you know the coordinates— but how do you know the right coordinates?

The industry standard is something called Sugiyama, but implementing it can be thousands of lines of code— see the Javascript implementation, Dagre, for more on that.

Because of space and brain constraints, we’ll look at a common simpler option: the Reingold-Tilford algorithm.

Reingold-Tilford

Reingold-Tilford requires us to do four passes over the data:

1. Assign initial coordinates
2. Resolve conflicts between subtrees
3. Apply modifiers to the final coordinates
4. Normalize coordinates

Before we do the first step we need to construct a Tree structure:

Then assigning initial coordinates is as simple as walking through the tree recursively and

1. Calculate the depth of each node
2. Calculate a position that is in the center of its children

Let’s walk through the steps:

If you click to try it again, we’ll redo the same example but with 6 extra items and 10 additional edges. You’ll see that because of items having parents at multiple depths, it can be tricky to get a pleasing layout.

You’ll notice the arrows aren’t great— here I’m skipping the conflict resolution part of the algorithm— and also RT is known to not be great at optimally clear layouts (that’s why the state of the art is Sugiyama).

In another post (or maybe just extending this one in the future) we’ll look at the solution: resolving conflicts with modifiers and normalizing coordinates.