Median Heuristic ( MedianHeuristic )

Baseclasses

Definition

The class MedianHeuristic implements the two layer crossing minimization heuristic Median. It reorders the nodes on the changeable layer according to the median weight [EW86]

$Median(v) = \left\{\begin{array}{cl} \frac{1}{2} \left(P(w_{\lfloor\frac{n}{2}... ...eil})\right) & \mbox{ if }n\geq1\\ 0.0 & \mbox{ otherwise} \end{array}\right.$
where v is a node on the changeable layer, and w₁,..., w_n is the sequence of neighbors of v on the fixed layer ordered according to the position P.

General Information

Algorithm
name	Median
long name	Median (Eades, Wormald)
author	P. Eades, N. Wormald

Implementation
author	C. Gutwenger
date	February 1998
version	1.0

Pre- and Postcondition

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

#include < AGD/MedianHeuristic.h >

Creation

MedianHeuristic

M

creates an instance M of type MedianHeuristic.

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 median 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.