Sifting Heuristic ( SiftingHeuristic )

Baseclasses

Definition

The sifting heuristic [Rud93,MSM00] works as follows: First, an order of the vertices on the changeable layer is determined. Then, the vertices are sifted in that order. Sifting a vertex v means to put it on a position which minimizes the number of crossings, whereby the ordering of all other vertices remains fixed.

General Information

Algorithm
name	Sifting
long name	Sifting (Matuszewski et al.)
author	C. Matuszewski, R. Schönfeld, P. Molitor

Implementation
author	C. Gutwenger
date	June 1999
version	1.0

Pre- and Postcondition

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

Optional Parameters Instances of SiftingHeuristic provide the following optional parameters:

$\bullet$

SiftingHeuristic::Strategy strategy = desc_degree
determines the order in which vertices are sifted. Possible settings are left_to_right, desc_degree (with descending number of neighbors on the fixed layer) and random (in random order).

#include < AGD/SiftingHeuristic.h >

Types

SiftingHeuristic::Strategy
	the strategy for sifting vertices.

Creation

SiftingHeuristic

M

creates an instance M of type SiftingHeuristic.

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()

Access to Options

Strategy	M.strategy()
void	M.strategy(Strategy s)

Implementation

Let n_L denote the number of nodes on the changeable layer and m_L the number of edges between the fixed and the changeable layer. The algorithm computes in a preprocessing step a so-called crossing matrix, which takes time $\protectO$(n_Lm_L). The actual crossing reduction algorithm takes time $\protectO$(n_L²). Both steps are implemented in the call()-method. The init()-method takes time $\protectO$(n), where n is the number of nodes in the input graph.