Sugiyama's Algorithm ( SugiyamaLayout )

Baseclasses

Definition

The class SugiyamaLayout represents a general framework for drawing graphs with the hierarchical drawing method suggested by Sugiyama, Tagawa, and Toda [STT81]. This method works in three phases:

1. We partition the nodes into levels using a RankAssignment module. Then, we build a proper hierarchy, that is, we reverse and split edges until each edge is directed downwards and connects two nodes on neighbored layers. The newly introduced nodes are called dummy nodes and represent edge bends in the final drawing.
2. We reorder the nodes on each layer in order to reduce the number of edge crossings. This is achieved by iteratively calling a TwoLayerCrossMin module. The layers are alternately traversed top-down and bottom-up, until the total number of crossings does not decrease anymore.
3. We call a HierarchyLayoutModule to compute the final layout of the hierarchy. This module assigns coordinates to nodes and bend points to edges.

The algorithm is modified such that the above process can be repeated several times. Each repetition (except for the first) starts with a random order of the nodes on each layer. Since the total process of k-layer crossing minimization used here is a heuristic, each repetition may stop with a different total number of crossings. The algorithm chooses the result with the fewest number of crossings. If option transpose is set to true, a fine tuning step is performed after each traversal, which tries to reduce obvious crossings. In particular, the resulting ordering of the vertices on each layer is locally optimal with respect to transposition of adjacent vertices (see also [GKNV93]).

General Information

Algorithm
name	Sugiyama
long name	Sugiyama
author	K. Sugiyama, S. Tagawa, M. Toda

Implementation
author	C. Gutwenger, M. Krüger
date	March 1998
version	2.0

Pre- and Postcondition

precondition	=	{ noselfloops, directed }
postcondition(PRE)	=	$\emptyset$

Exchangeable Modules Instances of type SugiyamaLayout provide the following module options:

$\bullet$

ranking
a RankAssignment option used to compute the ranking.

guaranteed precondition:	{noselfloops, directed}
required postcondition:	$\emptyset$
initial module:	LongestPathRanking

$\bullet$

cross_min
a TwoLayerCrossMin option used in the crossing reduction phase.

guaranteed precondition:	{noselfloops, directed},$\emptyset$
required postcondition:	$\emptyset$
initial module:	BarycenterHeuristic

$\bullet$

comp_coord
a HierarchyLayoutModule option used to compute the final layout.

guaranteed precondition:	$\emptyset$
required postcondition:	$\emptyset$
initial module:	FastHierarchyLayout

Optional Parameters Instances of SugiyamaLayout provide the following optional parameters:

$\bullet$

bool init_order = true
if set to true, an initial order of the nodes on each layer is determined by a depth-first-search traversal. If the graph represents a forest the initial order has already no crossings.

$\bullet$

int runs = 3
determines, how many times the crossing minimization is repeated. Each repetition (except for the first) starts with randomly permuted nodes on each layer. Deterministic behaviour can be achieved by setting runs to 1.

$\bullet$

int fails = 4
determines, how many times the total number of crossings after a complete top down or bottom up traversal may not decrease before one repetition is stopped.

$\bullet$

bool transpose = true
if set to true, an additional fine tuning step is performed after each traversal, which tries to reduce the total number of crossings by switching adjacent vertices on the same layer.

#include < AGD/SugiyamaLayout.h >

Creation

SugiyamaLayout

L

creates an instance L of type SugiyamaLayout.

Operations

void	L.ext_call(const leda_graph& G, leda_node_array<int>& rank, LayoutInterface& A)
		calls L for graph G with layout interface A. Uses the level assignment defined by rank.
void	L.reduce_crossings(GraphCopy& GC, Hierarchy& H)
		calls only the crossing reduction step for graph copy GC and hierarchy H.
int	L.number_of_crossings()	returns the number of crossings in the layout produced by a preceding call.

Standard Interface (Inherited Methods) The detailed description of these methods can be found in the manual entries of the base class (LayoutModule).

bool	L.check(const graph& G, AgdKey& p)
void	L.call(const graph& G, LayoutInterface& A)

Access to Options

bool	L.set_ranking(const RankAssignment& M)
bool	L.set_cross_min(const TwoLayerCrossMin& M)
bool	L.set_comp_coord(const HierarchyLayoutModule& M)
bool	L.init_order()
void	L.init_order(bool b)
int	L.runs()
void	L.runs(int n)
int	L.fails()
void	L.fails(int n)
bool	L.transpose()
void	L.transpose(bool b)

Example

Example 1: We use only the crossing reduction phase of the Sugiyama algorithm with the Split heuristic and our own level assignment.

#include <LEDA/graphwin.h>
#include <AGD/SugiyamaLayout.h>
#include <AGD/SplitHeuristic.h>
#include <AGD/DfsRanking.h>
#include <AGD/Hierarchy.h>
#include <AGD/GraphCopy.h>

void reduce_crossings(graph& G)
{
  node_array<int> rank(G);

  // assign a non-negative level to each node in G
  // we simply use a rank assignment module
  DfsRanking().call(G,rank);

  // build the hierarchy
  GraphCopy GC(G);
  Hierarchy H(GC,rank);

  // call crossing minimization
  SugiyamaLayout sugiyama;
  sugiyama.set_cross_min(SplitHeuristic());
  sugiyama.reduce_crossings(GC,H);

  // the positions of the nodes (in GC) on each layer
  // can now be accessed via H
}

Example 2: We compute a layout in a GraphWin with our own level assignment.

#include <LEDA/graphwin.h>
#include <AGD/SugiyamaLayout.h>
#include <AGD/DfsRanking.h>

void call_with_ranking(GraphWin& GW)
{
  graph& G = GW.get_graph();
  node_array<int> rank(G);

  // assign a non-negative level to each node in G
  // we simply use a rank assignment module
  DfsRanking().call(G,rank);

  // compute layout in GW
  GraphWinInterface A(GW);
  SugiyamaLayout sugiyama;
  sugiyama.ext_call(G,rank,A);
}