Next: Layout of Hierarchies Up: Two Layer Crossing Minimization Previous: Greedy Switch ( GreedySwitchHeuristic Contents Index

Optimal Crossing Minimization ( OptCrossMin )

Baseclasses

$\begin{picture}(8,4) \thicklines \put(0,3){\framebox (5.5,1){\bf AGDModule}}... ...{\vector(0,-1){1}}\put(2.5,0){\framebox (6,1){\bf OptCrossMin}} \end{picture}$

Definition

The class OptCrossMin implements an optimal two layer crossing minimization based on a branch & cut algorithm for the linear ordering problem [GJR84]. It reorders the nodes on the changeable layer such that the number of crossings is minimum.

General Information

Algorithm

name Opt. Cross. Min.

long name Optimal Crossing Minimization

author M. Grötschel, M. Jünger, G. Reinelt

Implementation

author M. Elf

date September 1998

version

Pre- and Postcondition

precondition = $\emptyset$

postcondition(PRE) = $\emptyset$

#include < AGD/OptCrossMin.h >

Creation

OptCrossMin M creates an instance M of type OptCrossMin.

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

Next: Layout of Hierarchies Up: Two Layer Crossing Minimization Previous: Greedy Switch ( GreedySwitchHeuristic Contents Index

Algorithm
name	Opt. Cross. Min.
long name	Optimal Crossing Minimization
author	M. Grötschel, M. Jünger, G. Reinelt

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