Ranking to Minimize Edge Lengths ( OptNodeRanking )

Baseclasses

Definition

The OptNodeRanking module computes the following ranking of a graph G = (V, E): First, a feedback set R $\subset$ E is computed, that is, the graph G' = /V, E') resulting from G by reversing all edges in R is acyclic. In this step, self-loops are simply ignored. For this purpose, we use a subgraph module that computes a maximal acyclic subgraph (that also implies a feedback set R). Then, we compute a ranking that is defined as the optimal solution of the following optimization problem

min$\sum\limits_{(v,w)\in E'}^{}$(y(w) - y(v)) s.t.
	y(w) - y(v)	> =	1	for all (v, w) $\in$ E'
	x(v) $\in$ {0, 1}			for all v $\in$ V

where y(v) is the rank of vertex v. The resulting ranking minimizes the total edge lengths (the sum of the spans of all edges) and therefore the number of dummy vertices, which have to be created in order to build a proper hierarchy when used with the Sugiyama algorithm. This method for computing a ranking has been suggested by Gansner et al. in [GKNV93], where is also shown, how to solve the integer linear program in polynomial time.

General Information

Algorithm
name	Optimal Node Ranking
long name	Optimal Node Ranking
author	E. R. Gansner, E. Koutsofios, S. C. North, K. P. Vo

Implementation
author	C. Gutwenger
date	June 1999
version	1.0

Pre- and Postcondition

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

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

$\bullet$

subgraph
an SubgraphModule option used for computing a maximal acyclic subgraph.

guaranteed precondition:	{directed}
required postcondition:	$\{\emph{ directed, maximal{\_}acyclic }\}$
initial module:	LEDAMakeAcyclic

#include < AGD/OptNodeRanking.h >

Creation

OptNodeRanking

R

creates an instance R of type OptNodeRanking.

Operations

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

bool	R.check(const leda_graph& G, AgdKey& p)
void	R.call(const leda_graph& G, leda_node_array<int>& rank)

Access to Options

bool

R.set_subgraph(const SubgraphModule& M)

Implementation

The integrality condition in the integer linear program (ILP) can be omitted if it is solved with the simplex algorithm, because the constraint matrix is unimodular (see [GKNV93]). Therefore, we solve the relaxation of the ILP with an LP-solver, what gives us the optimal solution of the ILP.