← Algorithms

Drawing a graph of the code

Layered graph drawing, transitive reduction, and the four connector problems this exercise made the engine solve.

In the code: site/build.py

The dependency diagrams on the architecture page are generated from the package's real import graph. When they were built, Sauvignon had no automatic graph layout — it placed what you told it to place — so the generator had to do the layout itself. That turned into a small, instructive tour of a very well-studied problem, and a list of things the engine could not do.

The engine has since grown a <graph> container that runs the whole recipe below, and the generator now uses it: everything about where a module goes was deleted and handed over. What survived, and what the handover cost, is the next section.

The standard recipe

Nearly every "boxes and arrows, flowing one way" picture you have seen comes from the same 1981 paper by Sugiyama, Tagawa and Toda. The framework has four phases:

1. Make it acyclic. Reverse a minimal set of edges. (Import graphs are already acyclic, or should be — if not, you have found a bug.)
2. Assign layers. Put each node in a row such that every edge points downward.
3. Reduce crossings. Order the nodes within each row.
4. Assign coordinates. Turn those orderings into x positions.

The generator used to do a simplified 1, 2 and 4, and skip 3 entirely — which was affordable only because the graph it draws has nine nodes. (The chart package's eleven is where it stopped being affordable, which is why that one is drawn as bands instead.) It now does none of them: <graph> does all four, including the crossing reduction the generator never had.

What the handover kept, and what it cost

The <graph> container runs all four phases. Cycles are broken by reversing the back edges a depth-first search finds; layers come from longest-path-from-a-source for the reason the next section gives; ordering is barycentre sweeps; coordinates are a local relaxation. Give it marks and connect them and it decides where they go:

<diagram padding="16">
  <graph gap="26" row-gap="34">
    <rect id="parse" label="parse"/>
    <rect id="model" label="model"/>
    <rect id="layout" label="layout"/>
    <rect id="scene" label="scene"/>
    <rect id="render" label="render"/>
  </graph>
  <connect from="parse" to="model"/>
  <connect from="model" to="layout"/>
  <connect from="model" to="scene"/>
  <connect from="layout" to="render"/>
  <connect from="scene" to="render"/>
</diagram>

Nothing in that source says where anything goes. The diamond, the row the two middle nodes share, and the straight spine down the outside are all read off the five <connect> elements.

What the generator kept is the part that was never about position. The transitive reduction below is a statement about which edges are worth drawing, and the band diagrams are its fallback when a package has too many modules to draw as a graph at all. Neither is something a layout container should have an opinion about, so neither moved.

For a while one thing did not hand over cleanly. Every generated edge is marked routing="curved", but a curve was drawn blind to obstacles — its arc bulges off the straight chord toward the elbow corner and would cut clean through a box sitting between its ends. So the generator could not simply curve everything: an edge spanning more than one row had to be left straight, because only a straight edge was routed around what lay in its way. Deciding which was which meant the generator still had to know the layering, purely to pick connector styling — a wart, and the honest name for it was that routing="curved" bypassed obstacle avoidance.

So that is what got fixed, in the engine rather than the generator. A curve whose arc would cross a shape now falls back to exactly the route a straight edge gets — the visibility-graph detour described below — drawn as the rounded poly-line that route already renders as. A curve going around a box and a straight edge going around the same box come out identically, which is right, because there is only one good way around. The decision is made before ports are handed out, so a curve that ends up detouring does not reserve a slot on its source that it will not use. With that, the generator marks every edge curved and the leftover layering is gone: an adjacent-row edge stays a tidy arc, the two-row connect → base detours down the gap between avoid and tracks on its own, and nothing here computes a row number to tell them apart.

The conversion also paid for itself immediately, in the way these things usually do — by breaking. Handing the ordering to barycentre sweeps put a crossing into this very diagram that the hand-rolled generator never had, because a node with no neighbour in the layer being sorted against was ranked by its own index, and an index in one layer is not comparable with a barycentre in another. One node with something to sort by stepped in front of every node that was merely holding still. Nodes with no barycentre now genuinely keep their slot and the rest are ranked among the slots they already occupy. The bug was in the engine, not the generator, and nothing but a real graph was ever going to find it.

Layering: which direction you measure from matters

The obvious layering is "longest path from a leaf": a node sits one above the deepest thing it depends on. It is easy, and for the layout package it produced a diagram where connect — a side branch that only resolve uses — was stranded two rows below it, forcing a long edge across the picture.

Measuring from the other end, "longest path from a source" (a module nothing imports), pulls each node as close to its dependants as the graph allows. connect moves up beside measure, and the long edge drops to the bottom of the picture where it crosses nothing. The height is unchanged; what improves is total edge length, and what it costs is a little width.

<graph> layers the same way, so this finding survived the handover rather than having to be made twice.

Neither is optimal. The principled choice is network simplex layering from the Graphviz paper, which minimises total weighted edge length; Coffman–Graham is the classic alternative when you want to bound the width.

Draw only the edges that say something

Before drawing, take the transitive reduction: drop any edge already implied by a longer path. resolve really does import base, but it also imports measure, which reaches base via tracks — so the direct arrow adds no information and costs you a line across three rows.

For a DAG the transitive reduction is unique, which is what makes this safe to do automatically. It removed five of the layout package's fifteen edges here, and with them most of the mess.

The long edge, and two ways to route it

Even after reduction, one edge spans two rows. That is not a failure of layering — it is unavoidable. This graph is a diamond whose two sides have different lengths (resolve → measure → tracks → base is three hops, resolve → connect → base is two), so no assignment of rows can make every edge span exactly one. Such a graph is not proper, and a single curve drawn straight from connect to base would cut through whatever sits between them.

The textbook fix is Sugiyama's, and it is beautifully blunt: make the graph proper by force. Insert a virtual vertex (a dummy node) in every row a long edge crosses, and treat the edge as a chain of single-row segments. The dummies take part in crossing reduction and coordinate assignment like real nodes, so the long edge is routed around obstacles as a side effect of the ordinary algorithm; at draw time you join the chain into one spline.

The generator did exactly that for a while — a 1×1 unpainted box reserving a routing slot — and it worked, but it left a small blemish. Two adjacent chain segments are two separate connectors, and each independently chose which side of the tiny dummy to attach to. One met its top, the next left from its right, so the "single" edge cornered visibly at the dummy instead of flowing through it.

Then the engine itself gained obstacle avoidance — the visibility-graph routing described below — and the blemish became beside the point. A connector now routes around any box in its way on its own, whether it was asked for a straight line or a curve. So the generator stopped hand-rolling dummies and marked the long edge like every other.

Avoidance alone only squeezes round what is there, though. The rows a long edge passed were packed as if it did not exist, so in a tall graph of wide boxes there was no gap to squeeze through, and a route that found none was drawn straight through the boxes in its way. So the engine now takes the textbook step itself. An edge that skips rows gets a lane on each row it passes: a placeholder, ordered and straightened with the nodes and then dropped, so the gap is already there when the router comes to look for it. The chain blemish cannot come back, because the lane is never drawn and the edge is still one connector. And in a downward graph a curve leaves by the bottom and comes in by the top, as the flow reads, rather than by whichever sides happen to face: connect → base keeps its lane between force and graph and enters base's top, while the adjacent-row edges stay as tidy curves.

It is a small illustration of the whole point of this site — a limitation documented as a gap, then closed in the engine, then leaned on by the very tool that first worked around it, and then found to have been closed only halfway.

Ports, which used to be a gap

When two connectors attached to the same side of the same shape they arrived at exactly the same point, arrowheads stacked on top of each other. The fix is port assignment: spread the attachments along the side, and order them so they do not cross.

The Eclipse Layout Kernel models the whole spectrum explicitly, with port constraints running from FREE (the engine picks side and position) through FIXED_SIDE and FIXED_ORDER to FIXED_POS (the author places every one). Graphviz exposes a coarser version through compass points on headport and tailport.

Sauvignon now implements both ends of that spectrum. If you pin an anchor, it is an exact point and stays put — quantum-circuit wires depend on that. If you say nothing, the engine picks the side and then spaces the attachments along it at (i+1)/(n+1), ordering them by where the far end sits along that side's axis. That ordering rule is the same barycentre idea crossing reduction uses to order nodes within a row, and it is enough to keep the fan-out from a single box crossing-free.

The nice property of (i+1)/(n+1) is that one connector gets 1/2 — exactly the named anchor. So nothing moves until two connectors genuinely collide, and every diagram that never had the problem renders byte-for-byte as before.

Obstacle avoidance, the last big one

A connector is clipped to its own endpoints' shapes but knew nothing about anything else, so it would happily cross a third box. The classical fix is a visibility graph:

1. grow every obstacle by a clearance margin and take the corners of the grown rectangles as candidate waypoints — the shortest obstacle-free path between two points always turns at a corner, never in open space;
2. join every pair of points whose connecting segment misses all obstacles;
3. take the shortest path across that graph.

Because a visibility-graph shortest path is already taut, it turns only where it must. Sauvignon runs Dijkstra over it, and the whole thing is guarded by the cheapest possible test: if the direct line is already clear, none of it runs. That is the overwhelmingly common case, which is why a quadratic algorithm is affordable here at all. Past forty obstacles it declines to try rather than grinding.

The path comes back as a poly-line with sharp corners, which the renderer then rounds into a smooth curve so it matches the ordinary curved edges — a purely cosmetic pass over the corners, with the radius kept under the routing clearance so the rounded curve stays inside the margin the route stood off.

Several judgement calls turned out to matter more than the algorithm.

What counts as an obstacle. Two rules, and getting either wrong is visible.

The first: whatever is actually drawn — marks, charts, and the panel a <contains> paints. Not the set of things with an id, which is the tempting shortcut because the router already has that dictionary to hand. It is wrong in both directions. A box with no id is drawn but nameless, so routes went straight through it; and naming a plain <row> — to <align> it, say — turned an invisible grouping container into a solid wall that unrelated connectors detoured around. A row is grouping, not geometry.

The second: not a shape enclosing one of the endpoints — a connector legitimately crosses the panel it starts inside, and treating the group as solid would send every edge on an absurd tour around its own parent.

Which side to leave by. The attachment side comes from the ray between the two centres, which is cheap, stable, and completely blind to what sits in between. On a near-diagonal it is close to a coin toss: in one of this site's own diagrams the vertical axis won by four percent, and the winning direction was the one with a neighbouring box six pixels away, so the route left north, immediately turned, and doubled back — six points and a 102° bend to cover a distance a straight line covers in two.

So when a route needs a detour at all, the engine now tries leaving by the other plausible side as well and keeps whichever costs less, counting bends before length. Only when the first answer was already imperfect: a connector that got a clean straight line the first time is never reconsidered, which is what keeps this from quietly re-routing every diagram that was already fine.

This is the coarse end of what the Eclipse Layout Kernel calls port constraints. FREE there means the engine picks the side and the position along it; Sauvignon now picks position always, and side only when the obvious side did not work out.

When not to route. A pinned from-anchor or to-anchor opts out entirely. This was not a guess: switching avoidance on changed exactly one of the forty example renders, and it was the quantum circuit, whose qubit wires were suddenly detouring around the gates that are supposed to sit on them. An explicit anchor means the author is specifying geometry, so the engine should not second-guess it. With that rule, all forty renders are unchanged.

Where the route meets the shape. A detour's attachment point is dead centre on the facing edge — but it then sets off at a steep angle toward a waypoint off to one side, and the eye follows that diagonal back to the nearest corner and reads the connector as attached there. It is a convincing illusion: the fix is not to move the attachment, which is already right, but to leave the shape along a short perpendicular stub before turning. Orthogonal routers do the same, and it pays twice over, since the arrowhead then sits on a square approach.

The stub has to be told about the obstacles too, which is not obvious until it bites. It is added after routing, so it starts out knowing nothing about what the router just carefully steered around — and a neighbour a few pixels away sits well inside its reach. It now shrinks until it is clear, and is dropped entirely only if even a short one is blocked.

That is the second time the same mistake has been made here. Nudging apart two routes that share a corridor had exactly this shape: a correction applied on top of a finished route, moving it back into something the route had avoided. Any pass that adjusts a path after the fact has to re-check what the path was avoiding, and it is worth saying plainly because the bug is invisible until the geometry happens to be tight.

When the routes are worked out. A detour leaves the elements' own extent — that is the entire point of it — and so does a label stepped off its line. If connectors are resolved while emitting the scene, as they originally were, the canvas has already been sized from the elements alone and anything reaching past them is simply cut off at the edge of the drawing. So routing now happens during framing instead: resolve the connectors, take the bounds of everything drawn, and size the canvas around that. Routing is a pure function of the boxes, so when the whole picture has to shift to make room, the routes shift with it — no re-routing required, just a translation.

There is a subtlety in the segment test, too. "Does this line cross that box" must mean the interior: a route hugging the clearance boundary runs exactly along an edge, and if grazing counted as a hit the router would refuse its own best answer. Liang-Barsky clipping gives this cleanly — a collinear segment leaves an empty parameter window.

Nudging, the same problem along the middle

Ports fixed stacking at a connector's ends. Two connectors between the same pair of shapes still traced the same line for their whole length: only the topmost was visible, and the labels sat on top of each other. libavoid calls separating these nudging.

The test for "these need separating" has to be overlap, not intersection. Two routes that merely cross are fine — that is an ordinary diagram. Only routes running along one another are a problem. So: are the two segments collinear, and do they share more than a single point? Segments meeting end to end, or crossing at right angles, must both come out false.

Routes are then grouped by that relation and each group fanned out symmetrically about where it was, so a lone connector never moves and an odd group keeps its middle member exactly in place.

Two traps, both of which produced a worse diagram before they were fixed, and both invisible until the geometry was printed out.

Putting the ends back. After shifting a route sideways its ends no longer touch their shapes, so they are projected back onto the outline. Project them along a ray aimed at the neighbouring point and the ray is barely deflected by a few pixels of shift — it lands where the endpoint already was, cancelling the nudge entirely. Aim the ray at the shifted endpoint itself and a rectangle's edge returns it unchanged while a curved outline pulls it the short way back on.

Facing the same way. A request and its reply run between the same two shapes in opposite directions. Each route's normal is derived from its own direction, so those normals oppose, and shifting one by +d and the other by −d moves them both the same way: they cancel and land back on top of each other. Since that is precisely the case nudging exists for, the direction has to be made canonical first — flip it to a consistent hemisphere before taking the normal, so every route in a group shares one frame.

That closes the connector gaps this exercise opened: ports, obstacle avoidance, arrowheads on curves, and now nudging. What remains is the ceiling described elsewhere — the solver's, not the router's.

Putting the labels somewhere

An edge label goes mid-edge, which is right until the text is wider than the gap it sits in — then it laps over the very shapes its connector joins. Sliding it along the edge cannot rescue that: the whole edge is shorter than the label. It has to leave the line.

Label placement is its own literature, and the honest summary is that the optimal assignment is NP-hard. The practical treatment is a search over candidate positions scored by conflict — Christensen, Marks and Shieber's An Empirical Study of Algorithms for Point-Feature Label Placement (1995) is the standard comparison, and it finds that even simple strategies capture most of the available quality.

So: generate candidates (a few points either side of the middle, each at several lifts clear of the line), score each by the area it overlaps with the shapes and with the labels already placed, and take the first that collides with nothing. If none is clean, keep the cheapest — a label should land somewhere rather than be dropped.

The ordering matters more than the scoring. Candidates are tried with the natural placement first, so a label with nothing in its way does not move at all. That is what let this ship without disturbing a single existing diagram: across all forty-one examples no label collides, so every one takes its first candidate and renders exactly as before.

It is greedy and order-dependent, and a genuinely crowded diagram will still produce a compromise rather than the best arrangement. That is the accepted trade here, not an oversight.

Arrowheads, which were the same problem in miniature

An arrowhead is a rigid shape about nine units long, but an SVG marker is oriented by the tangent at the single vertex it attaches to. On a curve those disagree: the head points along the tangent at its tip while the line beneath it is still bending. It is invisible enough with a filled triangle and obvious the moment the head is drawn as two lines.

Graphviz's answer is to shorten the spline by the arrowhead's length and draw the head on the straight stub that remains, so the two share exactly one direction. Sauvignon now does this: split the cubic with de Casteljau at the parameter where the remaining arc length equals the head's reach, and finish with a straight segment to the true endpoint.

Two details make it tidy. A cubic's arc length has no closed form, so the split parameter is found by walking the curve in chords and interpolating within the step that crosses the target. And to measure back from the far end you simply reverse the control points — the reversed curve is the same curve, so the answer maps onto 1 − t exactly. If the whole curve is shorter than the head, nothing is trimmed; shortening it anyway would turn the path inside out.

Further reading. Sugiyama, Tagawa & Toda, Methods for Visual Understanding of Hierarchical System Structures (1981); Gansner, Koutsofios, North & Vo, A Technique for Drawing Directed Graphs (1993) — the dot paper, and still the best single description of the whole pipeline; Brandes & Köpf, Fast and Simple Horizontal Coordinate Assignment (2002); Wybrow, Marriott & Stuckey, Orthogonal Connector Routing (2009).