Open Graph Drawing Framework  v.2007.11

Overview Class Hierarchy Class Index Class List Members Namespaces Source Files Search for:

ogdf::SubgraphPlanarizer Class Reference

The planarization approach for crossing minimization. More...

#include <SubgraphPlanarizer.h>

Inheritance diagram for ogdf::SubgraphPlanarizer:

List of all members.

Public Member Functions
	SubgraphPlanarizer ()
	Creates an instance of subgraph planarizer.
void	setSubgraph (PlanarSubgraphModule *pSubgraph)
	Sets the module option for the computation of the planar subgraph.
void	setInserter (EdgeInsertionModule *pInserter)
	Sets the module option for the edge insertion module.
int	permutations ()
	Returns the number of permutations.
void	permutations (int p)
	Sets the number of permutations to p.
bool	setTimeout ()
	Returns the current setting of options setTimeout.
void	setTimeout (bool b)
	Sets the option setTimeout to b.
Protected Member Functions
virtual ReturnType	doCall (PlanRep &PG, int cc, const EdgeArray< int > &cost, const EdgeArray< bool > &forbid, const EdgeArray< unsigned int > &subgraphs, int &crossingNumber)
	Implements the algorithm call.
Private Attributes
ModuleOption < PlanarSubgraphModule >	m_subgraph
	The planar subgraph algorithm.
ModuleOption< EdgeInsertionModule >	m_inserter
	The edge insertion module.
int	m_permutations
	The number of permutations.
bool	m_setTimeout
	The option for setting timeouts in submodules.
Classes
class	CrossingStructure

---

Detailed Description

The planarization approach for crossing minimization.

This crossing minimization module represents a customizable implementation of the planarization approach. This approach consists of two phases. In the first phase, a planar subgraph is computed, and in the second phase, the remaining edges are re-inserted one-by-one, each time with as few crossings as possible; the crossings are then replaced by dummy nodes of degree four, resulting in a planarized representation of the graph.

Both steps, the computation of the planar subgraph and the re-insertion of a single edge, are implemented using module options. Additionaly, the second phase can be repeated several times, each time with a randomly permuted order of the edges to be re-inserted, and taking the solution with the least crossings. This can improve the quality of the solution significantly. More details on the planarization approach can be found in

C. Gutwenger, P. Mutzel: An Experimental Study of Crossing Minimization Heuristics. 11th International Symposium on Graph Drawing 2003, Perugia (GD '03), LNCS 2912, pp. 13-24, 2004.

Optional parameters

Option	Type	Default	Description
permutations	int	1	The number of permutations the (complete) edge insertion phase is repeated.
setTimeout	bool	true	If set to true, the time limit is also passed to submodules; otherwise, a timeout might be checked late when a submodule requires a lot of runtime.

Module options

The various phases of the algorithm can be exchanged by setting module options allowing flexible customization. The algorithm provides the following module options:

Option	Type	Default	Description
subgraph	PlanarSubgraphModule	FastPlanarSubgraph	The module for the computation of the planar subgraph.
inserter	EdgeInsertionModule	VariableEmbeddingInserter	The module used for edge insertion. The edges not contained in the planar subgraph are re-inserted one-by-one, each with as few crossings as possible.

Definition at line 118 of file SubgraphPlanarizer.h.

---

Constructor & Destructor Documentation

ogdf::SubgraphPlanarizer::SubgraphPlanarizer

(

)

Creates an instance of subgraph planarizer.

---

Member Function Documentation

virtual ReturnType ogdf::SubgraphPlanarizer::doCall	(	PlanRep &	PG,
		int	cc,
		const EdgeArray< int > &	cost,
		const EdgeArray< bool > &	forbid,
		const EdgeArray< unsigned int > &	subgraphs,
		int &	crossingNumber
	)			[protected, virtual]

Implements the algorithm call.

Implements ogdf::CrossingMinimizationModule.

void ogdf::SubgraphPlanarizer::setSubgraph

(

PlanarSubgraphModule *

pSubgraph

)

[inline]

Sets the module option for the computation of the planar subgraph.

Definition at line 151 of file SubgraphPlanarizer.h.

void ogdf::SubgraphPlanarizer::setInserter

(

EdgeInsertionModule *

pInserter

)

[inline]

Sets the module option for the edge insertion module.

Definition at line 156 of file SubgraphPlanarizer.h.

int ogdf::SubgraphPlanarizer::permutations

(

)

[inline]

Returns the number of permutations.

Definition at line 161 of file SubgraphPlanarizer.h.

void ogdf::SubgraphPlanarizer::permutations

(

int

p

)

[inline]

Sets the number of permutations to p.

Definition at line 164 of file SubgraphPlanarizer.h.

bool ogdf::SubgraphPlanarizer::setTimeout

(

)

[inline]

Returns the current setting of options setTimeout.

Definition at line 167 of file SubgraphPlanarizer.h.

void ogdf::SubgraphPlanarizer::setTimeout

(

bool

b

)

[inline]

Sets the option setTimeout to b.

Definition at line 170 of file SubgraphPlanarizer.h.

---

Member Data Documentation

ModuleOption<PlanarSubgraphModule> ogdf::SubgraphPlanarizer::m_subgraph [private]

The planar subgraph algorithm.

Definition at line 173 of file SubgraphPlanarizer.h.

ModuleOption<EdgeInsertionModule> ogdf::SubgraphPlanarizer::m_inserter [private]

The edge insertion module.

Definition at line 174 of file SubgraphPlanarizer.h.

int ogdf::SubgraphPlanarizer::m_permutations [private]

The number of permutations.

Definition at line 176 of file SubgraphPlanarizer.h.

bool ogdf::SubgraphPlanarizer::m_setTimeout [private]

The option for setting timeouts in submodules.

Definition at line 177 of file SubgraphPlanarizer.h.

---

The documentation for this class was generated from the following file:

• ogdf/planarity/SubgraphPlanarizer.h

---