Open Graph Drawing Framework  v.2007.11

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

ogdf::FastPlanarSubgraph Class Reference

Computation of a planar subgraph using PQ-trees. More...

#include <FastPlanarSubgraph.h>

Inheritance diagram for ogdf::FastPlanarSubgraph:

List of all members.

Public Member Functions
	FastPlanarSubgraph ()
	Creates an instance of the fast planar subgraph algorithm.
	~FastPlanarSubgraph ()
void	runs (int nRuns)
	Sets the number of randomized runs to nRuns.
int	runs () const
	Returns the current number of randomized runs.
Protected Member Functions
ReturnType	doCall (const Graph &G, const List< edge > &preferedEdges, List< edge > &delEdges, const EdgeArray< int > *pCost, bool preferedImplyPlanar)
	Returns true, if G is planar, false otherwise.
Private Member Functions
void	computeDelEdges (const Graph &G, const EdgeArray< int > *pCost, const EdgeArray< edge > *backTableEdges, List< edge > &delEdges)
	Computes the list of edges to be deleted in G.
void	planarize (const Graph &G, NodeArray< int > &numbering, List< edge > &delEdges)
	Performs a planarization on a biconnected component pf G.
Private Attributes
int	m_nRuns
	The number of runs for randomization.

---

Detailed Description

Computation of a planar subgraph using PQ-trees.

Literature: Jayakumar, Thulasiraman, Swamy 1989

Optional Parameters

Option	Type	Default	Description
runs	int	0	the number of randomized runs performed by the algorithm; the best solution is picked among all the runs. If runs is 0, one deterministic run is performed.

Observe that this algorithm by theory does not compute a maximal planar subgraph. It is however the fastest known good heuristic.

Definition at line 86 of file FastPlanarSubgraph.h.

---

Constructor & Destructor Documentation

ogdf::FastPlanarSubgraph::FastPlanarSubgraph

(

)

[inline]

Creates an instance of the fast planar subgraph algorithm.

Definition at line 90 of file FastPlanarSubgraph.h.

ogdf::FastPlanarSubgraph::~FastPlanarSubgraph

(

)

[inline]

Definition at line 95 of file FastPlanarSubgraph.h.

---

Member Function Documentation

void ogdf::FastPlanarSubgraph::runs

(

int

nRuns

)

[inline]

Sets the number of randomized runs to nRuns.

Definition at line 101 of file FastPlanarSubgraph.h.

int ogdf::FastPlanarSubgraph::runs

(

)

const [inline]

Returns the current number of randomized runs.

Definition at line 106 of file FastPlanarSubgraph.h.

ReturnType ogdf::FastPlanarSubgraph::doCall	(	const Graph &	G,
		const List< edge > &	preferedEdges,
		List< edge > &	delEdges,
		const EdgeArray< int > *	pCost,
		bool	preferedImplyPlanar
	)			[protected, virtual]

Returns true, if G is planar, false otherwise.

Todo:

Add timeout support (limit number of runs when timeout is reached).

Implements ogdf::PlanarSubgraphModule.

void ogdf::FastPlanarSubgraph::computeDelEdges	(	const Graph &	G,
		const EdgeArray< int > *	pCost,
		const EdgeArray< edge > *	backTableEdges,
		List< edge > &	delEdges
	)			[private]

Computes the list of edges to be deleted in G.

Also performs randomization of the planarization algorithm.

void ogdf::FastPlanarSubgraph::planarize	(	const Graph &	G,
		NodeArray< int > &	numbering,
		List< edge > &	delEdges
	)			[private]

Performs a planarization on a biconnected component pf G.

The numbering contains an st-numbering of the component.

---

Member Data Documentation

int ogdf::FastPlanarSubgraph::m_nRuns [private]

The number of runs for randomization.

Definition at line 124 of file FastPlanarSubgraph.h.

---

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

• ogdf/planarity/FastPlanarSubgraph.h

---