Notebooks · lib/graphlayout

Layered graph layout

layered(g) places the nodes of a directed graph in layers, the way Graphviz's dot does (Sugiyama, Tagawa and Toda, 1981; Gansner, Koutsofios, North and Vo, 1993), and routes every edge between them. The input is a LayoutInput: each node's size, each edge's ends, and for each edge whether it runs against the direction of the layers (a value carried to the next pass of a loop), how much it wants to be straight, where it leaves its source and enters its target, and the size of its label. The output is a Layered: each node's center, each edge's route as a polyline, and each label's center.

Layers run down the page (the rank axis is y, growing downward); a caller that wants them left to right swaps the sizes on the way in and the coordinates on the way out. The four phases:

Cycles. A depth-first search from each node in order turns every edge that closes a cycle around; so does every edge the caller marks back. The rest of the layout sees a graph with no cycles.
Ranks. Longest path: a node's rank is one more than the largest rank of the nodes with an edge into it. A node with no edge in is then moved down to one rank above the nearest node it points to, so it is not left at the top, far from what it feeds.
Order. An edge that spans several ranks gets a dummy node on each rank between, so every edge joins adjacent ranks. The nodes of each rank are ordered by barycenter sweeps, down then up, twelve in all: each node goes to the mean position of its neighbors on the rank before. The order with the fewest crossings is kept; then two neighbors on a rank change places while that removes crossings (the transpose step).
Coordinates. Each node wants to sit at the weighted mean of its neighbors' positions (an edge's weight is larger between dummies, so a long edge runs straight). On each rank the positions nearest those wishes that keep the order and the gaps are found exactly, by pool-adjacent-violators (a least-squares fit under ordering constraints). Sweeps alternate down and up.

The output is deterministic: no hash, no random choice, ties broken by node index.

Used with import graphlayout.

Look inside this program

Atlas
The program’s map: every function and which calls which.
There’s no recorded run of this program yet.

This program declares a record type (LayoutInput), and records run only in compiled C for now, so the Run buttons here are off. Open it in the workbench and use its C tab to compile it.

Shift+Enter in a cell runs it and moves to the next. Running a cell runs every cell above it too, as one program.

[1]lines 45–1165

#| What `layered` needs: node sizes and edges.
#: w          each node's size across the rank axis (its width)
#: h          each node's size along the rank axis (its height)
#: efrom      each edge's source node
#: eto        each edge's target node
#: eback      1 when the edge is drawn against the ranks (the target comes first)
#: eweight    how much the edge wants to be straight, 1 by default
#: elen       the least number of ranks the edge spans, 1 by default
#: sport      where the edge leaves its source: an offset from the source's center, across
#: tport      where it enters its target, the same way
#: label_w    the size of the edge's label (0 for none)
#: label_h    its height
#: node_gap   the least space between two nodes of a rank
#: rank_gap   the space between two ranks
#: hint       where each node was across in an earlier layout (its center), when `hinted` is 1
#: hinted     1 for a node that should stay where it was: its order in its rank
#:            against the other hinted nodes is kept, and it sits at its hint
#:            unless the gaps push it
#: sides      1 when an edge may leave or enter a node from its side (toward a
#:            lane beside it); 0 for always from the node's foot to the next
#:            node's head
record LayoutInput {
    w: Arr
    h: Arr
    efrom: Arr
    eto: Arr
    eback: Arr
    eweight: Arr
    elen: Arr
    sport: Arr
    tport: Arr
    label_w: Arr
    label_h: Arr
    node_gap: Num
    rank_gap: Num
    hint: Arr
    hinted: Arr
    sides: Num
}

#| Where `layered` put the nodes and the edges.
#: x          each node's center across
#: y          each node's center along the ranks (down)
#: rank       each node's rank
#: order      each node's place in its rank
#: reversed   1 for an edge the layout turned around (its route still runs from its source to its target)
#: route_start where each edge's route begins in route_x, route_y; one more entry than edges
#: label_x    the center of each edge's label
#: label_y    the same, along the ranks
#: width      the extent of the drawing across
#: height     its extent along the ranks
#: crossings  the number of edge crossings between adjacent ranks
record Layered {
    x: Arr
    y: Arr
    rank: Arr
    order: Arr
    reversed: Arr
    route_start: Arr
    route_x: Arr

#| What `layered` needs: node sizes and edges.
#: w          each node's size across the rank axis (its width)
#: h          each node's size along the rank axis (its height)
#: efrom      each edge's source node
#: eto        each edge's target node
#: eback      1 when the edge is drawn against the ranks (the target comes first)
#: eweight    how much the edge wants to be straight, 1 by default
#: elen       the least number of ranks the edge spans, 1 by default
#: sport      where the edge leaves its source: an offset from the source's center, across
#: tport      where it enters its target, the same way
#: label_w    the size of the edge's label (0 for none)
#: label_h    its height
#: node_gap   the least space between two nodes of a rank
#: rank_gap   the space between two ranks
#: hint       where each node was across in an earlier layout (its center), when `hinted` is 1
#: hinted     1 for a node that should stay where it was: its order in its rank
#:            against the other hinted nodes is kept, and it sits at its hint
#:            unless the gaps push it
#: sides      1 when an edge may leave or enter a node from its side (toward a
#:            lane beside it); 0 for always from the node's foot to the next
#:            node's head
record LayoutInput {
    w: Arr
    h: Arr
    efrom: Arr
    eto: Arr
    eback: Arr
    eweight: Arr
    elen: Arr
    sport: Arr
    tport: Arr
    label_w: Arr
    label_h: Arr
    node_gap: Num
    rank_gap: Num
    hint: Arr
    hinted: Arr
    sides: Num
}

#| Where `layered` put the nodes and the edges.
#: x          each node's center across
#: y          each node's center along the ranks (down)
#: rank       each node's rank
#: order      each node's place in its rank
#: reversed   1 for an edge the layout turned around (its route still runs from its source to its target)
#: route_start where each edge's route begins in route_x, route_y; one more entry than edges
#: label_x    the center of each edge's label
#: label_y    the same, along the ranks
#: width      the extent of the drawing across
#: height     its extent along the ranks
#: crossings  the number of edge crossings between adjacent ranks
record Layered {
    x: Arr
    y: Arr
    rank: Arr
    order: Arr
    reversed: Arr
    route_start: Arr
    route_x: Arr