Crate gen_sugiyama 

The implementation roughly follows sugiyamas algorithm for creating a layered graph layout.

Usually Sugiyamas algorithm consists of 4 Phases:

1. Remove Cycles
2. Assign each vertex to a rank/layer
3. Reorder vertices in each rank to reduce crossings
4. Calculate the final coordinates.

Currently, phase 2 to 4 are implemented, Cycle removal might be added at a later time.

The whole algorithm roughly follows the 1993 paper “A technique for drawing directed graphs” by Gansner et al. It can be found here.

See the submodules for each phase for more details on the implementation and references used.

Modules

types

Structs

Config

Used to configure parameters of the graph layout.

Edge

Vertex

Enums

CrossingMinimization

Defines the heuristic used for crossing minimization. During crossing minimization, the vertices of one layer are ordered, so they’re as close to neighboring vertices as possible.

RankingType

Defines the Ranking type, i.e. how vertices are placed on each layer.

Constants

VERTEX_SPACING_DEFAULT

Functions

assign_coordinates

Assigns final coordinates to vertices using the computed algorithm state and a label dimensions map. This can be called multiple times with different size maps to create different layout variants.

run_sugiyama_algorithm

Runs the Sugiyama algorithm and returns the layers and vertex graph. This is the computationally expensive part that only needs to be run once.