Barycenter Heuristic ( BarycenterHeuristic )

Baseclasses

Definition

The class BarycenterHeuristic implements the two layer crossing minimization heuristic Barycenter. It reorders the nodes on the changeable layer according to the barycenter weight [STT81]

$Bary(v) = \left\{\begin{array}{cl} \frac{\sum_{\displaystyle w\in adj(v)}\disp... ...& \mbox{ if }adj(v)\neq\emptyset\\ 0.0 & \mbox{ otherwise} \end{array}\right.$
where v is a node on the changeable layer, adj(v) is the set of neighbors of v on the fixed layer, and pos(w) is the position of w on the fixed layer.

General Information

Algorithm
name	Barycenter
long name	Barycenter (Sugiyama et al.)
author	K. Sugiyama, S. Tagawa, M. Toda

Implementation
author	C. Gutwenger
date	February 1998
version	1.0

Pre- and Postcondition

precondition	=	$\emptyset$
postcondition(PRE)	=	$\emptyset$

#include < AGD/BarycenterHeuristic.h >

Creation

BarycenterHeuristic

M

creates an instance M of type BarycenterHeuristic.

Operations

Standard Interface (Inherited Methods)

The detailed description of these methods can be found in the manual entries of the base class (TwoLayerCrossMin).

bool	M.check(const leda_graph& G, const Layer& L, AgdKey& p)
void	M.init(const leda_graph& G, const Hierarchy& H)
void	M.call(const leda_graph& G, Layer& L)
void	M.cleanup()

Implementation

We use a randomized quicksort for sorting the nodes on the layer according to the barycenter weight. The init() function takes time $\protectO$(n), and the call() function takes expected time $\protectO$(m_L + n_Llogn_L), where n is the number of nodes in the input graph, n_L is the number of nodes on the changeable layer and m_L is the number of edges between the fixed and the changeable layer.