Algorithms

A diagram compiler is a pile of small, well-studied algorithms wearing a trenchcoat. Almost none of them are new: they come from typesetting, from computational geometry, from the graph-drawing literature, and from the statistics of scales. What follows is a map of that territory — grouped by the kind of problem each family solves — and for each one, what Sauvignon actually runs, where it takes the cheap option knowingly, and what it cannot do at all.

Deciding position at all

Before any of the rest: what decides where a thing goes. Sauvignon solves for positions rather than assigning them, which is the choice everything else is downstream of.

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.

foundation/solve.py

Longest path over a DAG not here: The same system of differences read as a scheduling problem — every task starts after its predecessors finish. Layer assignment in graph drawing is this, and so is the critical path in a project plan. Sauvignon's union-find is a different algorithm over the same system of constraints, so the technique is absent but the answers are not.
Cassowary not here: Incremental dual simplex over arbitrary linear constraints, with hard and soft priorities — Badros, Borning & Stuckey (2001), and what Apple's Auto Layout is built on. It buys you constraints Sauvignon cannot state at all, like 2a + b <= c. The price is a solver an order of magnitude larger than a union-find.

Laying out a tree of boxes

The problem CSS spent twenty years on. Sizes flow up from the content, space flows back down, and every interesting question is what happens when the two disagree.

Knuth–Plass total-fit line breaking not here: Score every possible set of breakpoints by how stretched or squeezed the lines are, and use dynamic programming to minimise it over the whole paragraph — Knuth & Plass (1981), the algorithm in TeX. It looks visibly better than greedy over a paragraph, and over a three-word diagram label there is usually only one sensible arrangement anyway.
Reingold–Tilford tree drawing not here: Tidier Drawings of Trees (1981): lay out each subtree independently, then slide siblings together until their contours touch. Walker (1990) extended it beyond binary trees; Buchheim, Jünger & Leipert (2002) showed Walker's was quadratic and restored linear time. A tree in Sauvignon is either nested boxes or a layered graph, and neither packs as tightly as this does.
Treemaps and other space-filling layouts not here: When the tree is the quantity — subdivide a rectangle so area encodes value. A different answer to the same nesting problem, and outside what Sauvignon draws.

Drawing a graph

A different lineage entirely, with its own conferences and its own NP-hard problems: given nodes and the edges between them, decide where everything goes and how the lines get there.

Barycentre crossing reduction in Sauvignon: Order each layer by the average position of a node's neighbours, sweep up and down, repeat. Everyone uses a heuristic because the exact problem is not tractable: the crossing number is NP-complete (Garey & Johnson, 1983), and it stays NP-hard even for two layers with one side's order already fixed (Eades & Wormald, whose median heuristic is a 3-approximation). Four sweeps run inside <graph>; the article covers the framework they sit in.
Brandes–Köpf coordinate assignment not here: Given the order within each layer, place nodes horizontally: align them into blocks from four directions, then average the four results (2002). Graphviz's dot instead solves coordinates as a second network-simplex problem (Gansner, Koutsofios, North & Vo, 1993). Sauvignon straightens with a few local passes, which is cheaper and worse.
Force-directed layout in Sauvignon: Model edges as springs and nodes as particles that repel, then let it relax — Eades' spring embedder (1984) and Fruchterman & Reingold (1991). Kamada & Kawai (1989) reframed it as pulling every pair towards its graph-theoretic distance, and Gansner, Koren & North (2004) solved that by majorization, which is what <network> does. This entry read not here until it was, on two grounds that turned out to be one mistake each: that Sauvignon had no undirected graphs to draw, and that the technique is not deterministic. The first was a gap rather than a reason. The second is true of spring embedders and not of majorization, whose stress falls monotonically from a starting circle in written order — which is what let it live beside committed SVGs that have to compile back byte for byte.
Orthogonal layout not here: Edges as axis-aligned runs, the style of circuit schematics and UML. The classical pipeline fixes topology, then shape, then metrics, with bend minimisation solved as a min-cost flow (Tamassia, 1987). Sauvignon's connectors turn corners but nothing plans the turns globally.
Planarity not here: Whether a graph can be drawn with no crossings at all, and how — testable in linear time since Hopcroft & Tarjan (1974). Nothing here asks the question; the router discovers crossings locally or not at all.
Aesthetics, measured informs the defaults: Not an algorithm but the reason to prefer one. Purchase (1997) put five conventional aesthetics through controlled experiments: reducing edge crossings mattered by far the most, fewer bends and more symmetry helped less, and maximising the minimum angle at a node or snapping to a grid showed no significant effect at all. It is why crossing reduction is the phase worth having even when the coordinate assignment above it stays cheap.

Turning data into a picture

Scales — the part of the Grammar of Graphics that maps a number or a category to a position, a length, or a colour, and tries to do it in a way a reader can decode.

Band scales in Sauvignon: The categorical half: one slot per category, mark in the middle of it, and a padding fraction that decides whether a bar chart breathes. No rounding to get right, and it is what every bar chart stands on — the other half of the ticks article.
Extended Wilkinson tick selection not here: Heckbert optimises one thing — round numbers. Talbot, Lin & Hanrahan (2010) score candidate tick sequences on simplicity, coverage, density and legibility together and search for the best compromise. What you want when axes have to stay good while resizing or animating.
Colour scheme design not here: ColorBrewer (Harrower & Brewer, 2003) is a catalogue rather than an algorithm: sequential, diverging and qualitative schemes, each checked against print, projection, photocopying and colour vision deficiency. Sauvignon generates its palettes instead, and generating is the easier half.
Graphical perception informs the defaults: Cleveland & McGill (1984) ranked encodings by how accurately people read them: position along a common scale first, then length, then angle and slope, with area and shading well behind. It is why the default marks here are bars, points and lines.

The language itself

Not layout at all: what happens between reading the source and having something to lay out.

Expanding a component

Macro expansion for diagrams — interpolation, content projection, and the name capture problem every macro system has to solve.

frontend/components.py

Lowering through intermediate representations in Sauvignon: Parse to a model, lower the model to a scene, render the scene. The ordinary shape of a compiler, and the reason layout never has to know what XML looked like. The architecture page draws the whole pipeline.
Hygienic macro expansion partly: Scheme's answer to a macro capturing a name from where it was used: make capture impossible by construction rather than unlikely by convention. Sauvignon renames ids on expansion, which closes the same hole for the one kind of name it has.

Algorithms

Deciding position at all

Solving positions instead of assigning them

Laying out a tree of boxes

Measure, then place

Breaking text into lines

Handing out slack

Dividing space that isn't there

Drawing a graph

Where a line meets a shape

Drawing a graph of the code

Placing a network

Turning data into a picture

Nice numbers for axis ticks

Generating a palette

The language itself

Expanding a component