Sugiyama.jl

Sugiyama.jl computes a layered ("hierarchical") layout for directed graphs: vertices are grouped into ranks, edge crossings between ranks are heuristically minimized, and coordinates are assigned within each rank. Ranking and crossing minimization follow Gansner, Koutsofios, North & Vo (1993, doi 10.1109/32.221135); coordinate assignment follows Brandes & Köpf (2002, doi 10.1007/3-540-45848-4_3). This implementation is a Julia port of rust-sugiyama.

Graphs are given as an adjacency matrix (or, with Graphs.jl loaded, as an AbstractGraph), and cycles are broken automatically, so any directed graph can be laid out, not just DAGs.

Quick Start

sugiyama (and the SugiyamaLayout callable) take an adjacency matrix and return one Point{2,Float64} per vertex:

using Sugiyama

adj = [0 1 0;
       0 0 1;
       0 0 0]

positions = sugiyama(adj)

3-element Vector{GeometryBasics.Point{2, Float64}}:
 [0.0, 0.0]
 [2.0, 0.0]
 [4.0, 0.0]

Keyword arguments can be used to control node spacing, direction, and the underlying heuristics. Here we do the first two:

positions = SugiyamaLayout(; direction = :down, nodespacing = 3.0)(adj)

3-element Vector{GeometryBasics.Point{2, Float64}}:
 [0.0, -0.0]
 [0.0, -4.0]
 [0.0, -8.0]