Interface Sugiyama<Ops>

the operator used to layout a Graph using the sugiyama layered method

The algorithm is roughly comprised of three steps:

  1. Layering - in this step, every node is assigned a non-negative integer later such that children are guaranteed to have higher layers than their parents. (modified with layering)
  2. Decross - in the step, nodes in each layer are reordered to minimize the number of crossings. (modified with decross)
  3. Coord - in the step, the nodes are assigned x and y coordinates that respect their layer, layer ordering, and size. (modified with coord and nodeSize)

The algorithm is based off ideas presented in K. Sugiyama et al. [1979], but described by S. Hong. The sugiyama layout can be configured with different algorithms for each stage of the layout. For each stage there should be adecuate choices for methods that balance speed and quality for your desired layout. In the absence of those, any function that meets the interface for that stage is valid.

Create with sugiyama.

Remarks

If one wants even more control over the algorithm, each step is broken down in the source code and can be achieved by calling an exported utility function. If one wants to call certain pieces incrementally, or adjust how things are called, it's recommended to look at the source and call each component function successively.

interface Sugiyama<Ops extends SugiyamaOps = SugiyamaOps> {
    coord<NewCoord extends Coord<never, never>>(
        crd: NewCoord,
    ): Sugiyama<U<Ops, "coord", NewCoord>>;
    coord(): Ops["coord"];
    decross<NewDecross extends Decross<never, never>>(
        dec: NewDecross,
    ): Sugiyama<U<Ops, "decross", NewDecross>>;
    decross(): Ops["decross"];
    gap(val: readonly [number, number]): Sugiyama<Ops>;
    gap(): readonly [number, number];
    layering<NewLayering extends Layering<never, never>>(
        layer: NewLayering,
    ): Sugiyama<U<Ops, "layering", NewLayering>>;
    layering(): Ops["layering"];
    nodeSize<NewNodeSize extends NodeSize>(
        acc: NewNodeSize,
    ): Sugiyama<U<Ops, "nodeSize", NewNodeSize>>;
    nodeSize(): Ops["nodeSize"];
    tweaks<const NewTweaks extends readonly Tweak<never, never>[]>(
        val: NewTweaks,
    ): Sugiyama<U<Ops, "tweaks", NewTweaks>>;
    tweaks(): Ops["tweaks"];
    (graph: Ops extends SugiyamaOps<N, L> ? Graph<N, L> : never): LayoutResult;
}

Type Parameters

Methods

coord decross gap layering nodeSize tweaks

Methods

coord

  • coord<NewCoord extends Coord<never, never>>(
        crd: NewCoord,
    ): Sugiyama<U<Ops, "coord", NewCoord>>

  • set the Coord operator

    The final stage is coordinate assignment, which takes a layered graph with nodes in the correct order, and assigns them x coordinates.

    There are four built-in coordinate assignment operators:

    • coordSimplex - This assigns x coordinates based on a simplex minimization that tries to produce long vertical edges. It usually produces attractive layouts in a reasonable amount of time.
    • coordQuad - This uses a quadratic optimization that tries to minimize the curvature of lines, but usually produces worse layouts than the simplex variant.
    • coordGreedy - If either of the above methods take too long, this uses a heuristic to assign x coordinates meaning it will run more quickly, but usually produce slightly worse layouts.
    • coordTopological - This is a coordinate assignment tailored for a topological layout. It can use a simplex or quadratic optimization to create a topological layout.

    You can also supply any function that satisfies the Coord interface. See that documentation for more information about implementing your own coordinate assignment operator.

    (default: coordSimplex)

    Type Parameters

    • NewCoord extends Coord<never, never>

    Parameters

    Returns Sugiyama<U<Ops, "coord", NewCoord>>

    Example

    const layout = sugiyama().coord(coordQuad());
  • coord(): Ops["coord"]

  • get the current Coord.

    Returns Ops["coord"]

decross

  • decross<NewDecross extends Decross<never, never>>(
        dec: NewDecross,
    ): Sugiyama<U<Ops, "decross", NewDecross>>

  • set the Decross operator

    The decross operator takes a layered graph with extra nodes for long paths, and reorders nodes along a layer to minimize the number of edge crossings (or other desired properties).

    There are three built-in decrossing operators:

    • decrossOpt - This optimally minimizes edge crossings, but due to the complex nature of the task, only works for reasonably small graphs.
    • decrossTwoLayer - This is a heuristic method for decrossing minimization that tries to strike a balance between a small number of edge crossings, and reasonable running time.
    • decrossDfs - This is a very cheap decrossing operator that orders nodes via a depth first search. It's mostly used for DecrossTwoLayer#inits of the two-layer operator.

    You can also supply any function that satisfies the Decross interface. See that documentation for more information about implementing your own decrossing operator.

    (default: decrossTwoLayer)

    Type Parameters

    • NewDecross extends Decross<never, never>

    Parameters

    Returns Sugiyama<U<Ops, "decross", NewDecross>>

    Example

    const layout = sugiyama().decross(decrossOpt());
  • decross(): Ops["decross"]

  • get the current Decross.

    Returns Ops["decross"]

gap

layering

  • layering<NewLayering extends Layering<never, never>>(
        layer: NewLayering,
    ): Sugiyama<U<Ops, "layering", NewLayering>>

  • set the Layering operator

    The layering operator takes the graph, and assigns each node layer that respects

    There are three built-in layering operators:

    • layeringSimplex - This minimizes the overall length of edges, and is reasonably fast for most graphs. Minimizing edges also tends to make the next steps faster.
    • layeringLongestPath - This minimizes the height of the overall graph.
    • layeringTopological - This creates a topological ordering, which inherently minimizes the width of the graph, but will only produce good layouts with other topological operators.

    You can also supply any function that satisfies the Layering interface. See that documentation for more information about implementing your own layering operator.

    (default: layeringSimplex)

    Type Parameters

    • NewLayering extends Layering<never, never>

    Parameters

    Returns Sugiyama<U<Ops, "layering", NewLayering>>

    Example

    const layout = sugiyama().layering(layeringLongestPath());
  • layering(): Ops["layering"]

  • get the current Layering.

    Returns Ops["layering"]

nodeSize

tweaks

Settings

Member Visibility

On This Page

Methods