Greedy Insert ( GreedyInsertHeuristic )

Baseclasses

Definition

The module GreedyInsertHeuristic proceeds from left to right by successively choosing the next vertex v to be the one which minimizes the number of crossings that edges adjacent to v make with edges adjacent to vertices to the left of v (see Eades and Kelly [EK86]).

General Information

Algorithm
name	Greedy-Insert
long name	Greedy-Insert (Eades,Kelly)
author	P. Eades, D. Kelly

Implementation
author	M. Krüger, Th. Ziegler
date	March 1998
version	1.0

Pre- and Postcondition

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

#include < AGD/GreedyInsertHeuristic.h >

Creation

GreedyInsertHeuristic

M

creates an instance M of type GreedyInsertHeuristic.

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

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.