the sugiyama framework: laying out dags in four phasesthe sugiyama framework: laying out dags in four phases

force-directed layouts (parts 1 and 2) have no sense of "up". that's fine for social networks. but a build pipeline, a class hierarchy or a flowchart has a direction baked in, and you want to see it: arrows pointing down, rows stacked top to bottom, and as few crossings as possible.

that's what the Sugiyama framework does. it's not one algorithm, it's a pipeline of four steps:

   a directed graph (maybe with loops)
     |
  [1] break loops          flip a few edges so nothing loops
     |
  [2] assign layers        give every node a row
     |
  [3] reduce crossings     reorder the nodes within each row
     |
  [4] set positions        pick exact x-coordinates, straighten edges
     |
   a layered drawing

it comes from Sugiyama, Tagawa and Toda in 1981, and it's what runs inside Graphviz dot, dagre and ELK. if you've seen a clean top-down dependency diagram, you've seen it.

the key design choice: each step treats the previous step's output as final. step 3 can't move a node to another row. step 4 can't reorder a row. that keeps every step small and solvable. it's also why a bad early decision sticks.

here is the whole pipeline on a nine-node graph. step through it and watch the crossing count:

step 1: break the loopsstep 1: break the loops

the later steps need every edge to point downward. a loop like b → d → f → g → b makes that impossible, so we flip one edge in each loop. the flipped edges are remembered, and drawn with their real direction at the end (as arrows pointing up).

you want to flip as few edges as possible, since every flipped edge points against the flow. finding the true minimum is too hard, so we use a shortcut: walk the graph depth-first, and whenever an edge leads back to a node you're still in the middle of visiting, it closes a loop. flip it.

   a --> b --> c --> d
         ^           |
         +-----------+   d -> b closes a loop

   walking from a: a, b, c, d. then d -> b.
   b is still "open", so flip that edge.

dagre also has a greedy version that usually flips fewer edges. either is fine when loops are rare, which they usually are.

step 2: assign layersstep 2: assign layers

now every node gets a row number, with one rule: every edge must go from a higher row to a lower one. among the valid choices, prefer short edges, because an edge that skips rows is harder to follow.

the simple way: put each node one row below its deepest parent (longest-path). it's fast and always valid, but it shoves nodes down and makes some edges longer than they need to be.

the better way, and dagre's default, is network simplex, from the Graphviz paper. think of it as: start with any valid layering, then keep shifting groups of nodes up or down whenever that makes the total edge length shorter. stop when nothing improves.

long edges get helper nodeslong edges get helper nodes

after step 2, some edges still skip rows. the next two steps only know how to handle edges between neighboring rows, so each long edge gets a hidden "dummy" node on every row it passes through:

   before:          after:

   row 0:  A        row 0:  A
                             |
   row 1:           row 1:  d1   (dummy)
                             |
   row 2:           row 2:  d2   (dummy)
                             |
   row 3:  B        row 3:  B

now every edge connects neighboring rows. at the end, the dummies disappear and their positions become the bends in the edge. this is how long edges end up drawn as clean lines instead of wild diagonals.

the catch: dummies are real nodes to every step that follows. a graph that looks small but has many long edges can be several times bigger inside.

step 3: reduce crossingsstep 3: reduce crossings

now we choose the left-to-right order inside each row. this decides how many edges cross, so it matters most for readability. it's also the hardest step: finding the perfect order is too slow even for just two rows.

the usual shortcut is the barycenter method. hold one row still. for each node in the next row, average the positions of its neighbors in the fixed row. then sort by that average.

   fixed row:   A=0   B=1   C=2   D=3

   X connects to A and C  ->  (0 + 2) / 2 = 1.0
   Y connects to D        ->  3 / 1       = 3.0
   Z connects to A and B  ->  (0 + 1) / 2 = 0.5

   new order: Z, X, Y

the idea: if your neighbors are mostly on the left, you belong on the left too, so your edges run straight down instead of cutting across.

one pass isn't enough. you sweep down the rows, then back up, several times, and keep whichever order had the fewest crossings. the stepper above shows each sweep.

step 4: set exact positionsstep 4: set exact positions

we know the order within each row, but not the exact x-coordinates. three wishes pull against each other:

• nodes in a row don't overlap and keep their order
• long edges (the dummy chains) run straight
• parents sit roughly centered over their children

dagre uses Brandes-Köpf (2001). each node tries to line up vertically with its middle neighbor in the next row. that has a lean: toward the left or right, looking up or down. so it computes all four versions and averages them. the leans cancel out and you get a balanced drawing. it's fast, too: linear time.

(the stepper uses a simpler averaging pass here, so its last step won't exactly match dagre.)

where the time goeswhere the time goes

• breaking loops: cheap. its cost is visual: more flipped edges means more arrows pointing up.
• assigning layers: fast in practice. a bad layering makes long edges, which makes the next two steps bigger.
• reducing crossings: usually the most expensive step, and the one where quality varies most. if a layout looks tangled, tune this.
• setting positions: fast. but it pays for every dummy node.

the common enemy is long edges. each one adds a dummy per skipped row, and every later step pays for them. that's why network simplex, which keeps edges short, is worth the extra work.

reading the source: dagrereading the source: dagre

dagre (at commit 4713b59b) maps almost one file to each step:

   step 1  break loops       lib/acyclic.ts   (+ greedy-fas.ts)
   step 2  assign layers     lib/rank/        (network-simplex.ts, util.ts)
   dummies                   lib/normalize.ts
   step 3  reduce crossings  lib/order/       (barycenter.ts, cross-count.ts)
   step 4  set positions     lib/position/bk.ts

   runs them all in order    lib/layout.ts

lib/layout.ts is the best place to start: it calls each step in order, adds and removes the dummies, and flips edges back at the end. here are the key pieces.

step 1, finding loop edges. stack holds the nodes currently being visited. an edge into a node on the stack closes a loop:

function dfsFAS(graph: Graph<GraphLabel, NodeLabel, EdgeLabel>): Edge[] {
    const fas: Edge[] = [];
    const stack: { [key: string]: boolean } = {};
    const visited: { [key: string]: boolean } = {};

    function dfs(v: string): void {
        if (Object.hasOwn(visited, v)) {
            return;
        }
        visited[v] = true;
        stack[v] = true;
        graph.outEdges(v)!.forEach(e => {
            if (Object.hasOwn(stack, e.w)) {
                fas.push(e);
            } else {
                dfs(e.w);
            }
        });
        delete stack[v];
    }

    graph.nodes().forEach(dfs);
    return fas;
}

step 2, longest-path ranking. dagre ranks from the bottom up, so smaller numbers are deeper, and flips it later:

function longestPath(graph: Graph<GraphLabel, NodeLabel, EdgeLabel>): void {
    const visited: { [key: string]: boolean } = {};

    function dfs(v: string): number {
        const label: NodeLabel = graph.node(v);
        if (Object.hasOwn(visited, v)) {
            return label.rank!;
        }
        visited[v] = true;

        const outEdges = graph.outEdges(v);
        const outEdgesMinLens: number[] = outEdges ? outEdges.map(e => {
            if (e == null) {
                return Number.POSITIVE_INFINITY;
            }

            return dfs(e.w) - graph.edge(e).minlen!;
        }) : [];

        let rank: number = applyWithChunking(Math.min, outEdgesMinLens);

        if (rank === Number.POSITIVE_INFINITY) {
            rank = 0;
        }

        return (label.rank = rank);
    }

    graph.sources().forEach(dfs);
}

the dummy nodes. edges that already span one row are skipped. longer ones get a dummy per row. a dummy on the label's row gets the label's size, so labels don't overlap nodes:

function normalizeEdge(graph: Graph<GraphLabel, NodeLabel, EdgeLabel>, e: Edge): void {
    let v: string = e.v;
    let vRank: number = graph.node(v).rank!;
    const w: string = e.w;
    const wRank: number = graph.node(w).rank!;
    const name: string | undefined = e.name;
    const edgeLabel: EdgeLabel = graph.edge(e);
    const labelRank: number | undefined = edgeLabel.labelRank;

    if (wRank === vRank + 1) return;

    graph.removeEdge(e);

    let dummy: string;
    let attrs: Partial<NodeLabel>;
    let i: number;
    for (i = 0, ++vRank; vRank < wRank; ++i, ++vRank) {
        edgeLabel.points = [];
        attrs = {
            width: 0,
            height: 0,
            edgeLabel: edgeLabel,
            edgeObj: e,
            rank: vRank
        };
        dummy = addDummyNode(graph, "edge", attrs, "_d");
        if (vRank === labelRank) {
            attrs.width = edgeLabel.width;
            attrs.height = edgeLabel.height;
            attrs.dummy = "edge-label";
            attrs.labelpos = edgeLabel.labelpos;
        }
        graph.setEdge(v, dummy, {weight: edgeLabel.weight}, name);
        if (i === 0) {
            graph.graph().dummyChains!.push(dummy);
        }
        v = dummy;
    }

    graph.setEdge(v, w, {weight: edgeLabel.weight}, name);
}

step 3, the barycenter. the average is weighted by edge weight. dummies carry heavier edges, which keeps long edges straight:

export default function barycenter(graph: Graph, movable: string[] = []): BarycenterEntry[] {
    return movable.map(v => {
        const inV = graph.inEdges(v);
        if (!inV || !inV.length) {
            return {v: v};
        } else {
            const result = inV.reduce((acc, e) => {
                const edge = graph.edge(e);
                const nodeU = graph.node(e.v);
                return {
                    sum: acc.sum + (edge.weight * nodeU.order),
                    weight: acc.weight + edge.weight
                };
            }, {sum: 0, weight: 0});

            return {
                v: v,
                barycenter: result.sum / result.weight,
                weight: result.weight
            };
        }
    });
}

step 4, brandes-köpf. the last three lines are the merge: pick the narrowest of the four versions, line the others up with it, then average:

function positionX(graph: Graph<GraphLabel, NodeLabel, EdgeLabel>): PositionMap {
    const layering: string[][] = util.buildLayerMatrix(graph);
    const conflicts: Conflicts = Object.assign(
        findType1Conflicts(graph, layering),
        findType2Conflicts(graph, layering));

    const xss: XssMap = {};
    let adjustedLayering: string[][];
    ["u", "d"].forEach(vert => {
        adjustedLayering = vert === "u" ? layering : Object.values(layering).reverse();
        ["l", "r"].forEach(horiz => {
            if (horiz === "r") {
                adjustedLayering = adjustedLayering.map(inner => {
                    return Object.values(inner).reverse();
                });
            }

            const neighborFn = (v: string): string[] => {
                const result = vert === "u" ? graph.predecessors(v) : graph.successors(v);
                return result || [];
            };
            const align: AlignmentResult = verticalAlignment(graph, adjustedLayering, conflicts, neighborFn);
            let xs: PositionMap = horizontalCompaction(graph, adjustedLayering,
                align.root, align.align, horiz === "r");
            if (horiz === "r") {
                xs = util.mapValues(xs, x => -x);
            }
            xss[vert + horiz] = xs;
        });
    });


    const smallestWidth: PositionMap = findSmallestWidthAlignment(graph, xss);
    alignCoordinates(xss, smallestWidth);
    return balance(xss, graph.graph().align);
}

if dagre is too terse, ELK has the same pipeline in Java with more documentation, and Graphviz dot has the original C.

papers to read nextpapers to read next

Gansner, Koutsofios, North and Vo (1993), "A Technique for Drawing Directed Graphs." the Graphviz dot paper. clear, practical, and still how it's done today. read this one first.

Sugiyama, Tagawa and Toda (1981), "Methods for Visual Understanding of Hierarchical System Structures." the original. dense, but it's where the four steps come from.

Brandes and Köpf (2001), "Fast and Simple Horizontal Coordinate Assignment." step 4 in full. short and readable.

next: part 4 moves to trees, where there are no crossings to fight at all. the question becomes how to pack a tree neatly.