Interactive Sugiyama Layout ( InteractiveSugiyama )

Definition

The class InteractiveSugiyama is a modified version of the Sugiyama algorithm. It allows to add nodes and edges to a given Sugiyama layout such that the changes between the given layout and the new Sugiyama layout are small.

The idea is that we are given a directed graph and draw it using the Sugiyama algorithm. Afterwards nodes and edges are added to the graph. These new nodes and edges are inserted into the given Sugiyama layout in such a way that the ranking of the old nodes and the relative ordering of the old nodes and edges in each layer is preserved in the new Sugiyama Layout.

General Information

Algorithm
name	Interactive Sugiyama
long name	Interactive Sugiyama
author	T. Ziegler

Implementation
author	T. Ziegler
date	January 2001
version	0.1

#include < AGD/isugiyama.h >

Creation

InteractiveSugiyama

IS

creates an instance of InteractiveSugiyama and initializes the options of the underlying Sugiyama algorithm to the default values.

Operations

a) Layout operations

int	IS.redraw(const graph& G)	applies the standard Sugiyama algorithm to G and computes the corresponding internal data structures for IS. IS.redraw() should be called for G before calling IS.update() for G.
int	IS.redraw(const graph& G, const node_map<int>& node_rank)
		applies the standard Sugiyama algorithm to G with the ranking information given in node_rank and computes the corresponding internal data structures for IS. IS.redraw() should be called for G before calling IS.update() for G.
int	IS.update(const graph& G)	inserts the nodes and edges that were added to G since the last application of IS.redraw(), respectively IS.update(). If IS.redraw() was not called for G before or edges or nodes were deleted IS.redraw() is called.

b) Access operations

int	IS.number_of_crossings()	returns the number of crossings in the layout.
int	IS.node_rank(node v)	returns the rank of node v.
int	IS.node_pos(node v)	returns the position of node v in its layer.
const node_map<int>&	IS.node_rank()	returns a reference to the ranking information of the nodes of G.
const node_map<int>&	IS.node_pos()	returns a reference to the position information of the nodes of G.
list<two_tuple<int,int> >	IS.edge_positions(edge e)	returns the positions of the bends of edge e in the layers between the layer of the source node and the target node of e. The first elements of the two_tuples are the layers and the second elements the position in the layer.

c) Access operations to Sugiyama options

int	IS.ranking()
int	IS.cross_min()
int	IS.cycle_removal()
int	IS.width()
int	IS.runs()
int	IS.fails()
bool	IS.init_order()
bool	IS.transpose()
double	IS.node_dist()
double	IS.level_dist()
bool	IS.fixed_level_dist()

d) Update operations for Sugiyama options

void	IS.ranking(int ra)
void	IS.cross_min(int cm)
void	IS.cycle_removal(int cr)
void	IS.width(int w)
void	IS.runs(int ru)
void	IS.fails(int fa)
void	IS.init_order(bool i)
void	IS.transpose(bool t)
void	IS.node_dist(double n)
void	IS.level_dist(double l)
void	IS.fixed_level_dist(bool fi)
void	IS.set_options(int ranking, int cross_min, int cycle_removal, int width, int runs, int fails, bool init_order, bool transpose, double node_dist, double level_dist, bool fixed_level_dist)

Implementation

The update operation first inserts the new nodes and afterwards the new edges. The layer of a new node depends on the layers of the source nodes of the incoming edges and the layers of the target nodes of the outgoing edges. The position of the new node in its layer depends on the average position of the neighbors. The new edges are inserted in such a way that the number of crossings is minimized. This is done by a shortest path computation in an auxiliary graph.