Open Graph Drawing Framework  v.2007.11

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

ogdf::BoyerMyrvold Class Reference

Wrapper class used for preprocessing and valid invocation of the planarity test. More...

#include <BoyerMyrvold.h>

List of all members.

Public Member Functions
	BoyerMyrvold ()
	Constructor.
	~BoyerMyrvold ()
	Destructor.
int	numberOfStructures ()
	The number of extracted Structures for statistical purposes.
bool	planarDestructive (Graph &g)
	Returns true, iff g is planar.
bool	planar (const Graph &g)
	Returns true, iff a copy of the constant graph g is planar.
void	transform (const KuratowskiWrapper &source, KuratowskiSubdivision &target, NodeArray< int > &count, EdgeArray< int > &countEdge)
	Transforms KuratowskiWrapper in KuratowskiSubdivision.
void	transform (const SList< KuratowskiWrapper > &sourceList, SList< KuratowskiSubdivision > &targetList, const Graph &g, const bool onlyDifferent=false)
	Transforms KuratowskiWrapper-List in KuratowskiSubdivision-List with respect to sieving constraints.
bool	planarEmbedDestructive (Graph &g, SList< KuratowskiWrapper > &output, int embeddingGrade=BoyerMyrvoldPlanar::doNotFind, bool bundles=false, bool limitStructures=false, bool randomDFSTree=false, bool avoidE2Minors=true)
	Returns an embedding, if g is planar and Kuratowski Subdivisions otherwise.
bool	planarEmbed (Graph &g, SList< KuratowskiWrapper > &list, int embeddingGrade=BoyerMyrvoldPlanar::doNotFind, bool bundles=false, bool limitStructures=false, bool randomDFSTree=false, bool avoidE2Minors=true)
	Returns an embedding, if g is planar and Kuratowski Subdivisions otherwise.
bool	planarEmbed (const Graph &g, GraphCopySimple &h, SList< KuratowskiWrapper > &list, int embeddingGrade=BoyerMyrvoldPlanar::doNotFind, bool bundles=false, bool limitStructures=false, bool randomDFSTree=false, bool avoidE2Minors=true)
	Returns an embedding, if constant graph g is planar and Kuratowski Subdivisions otherwise.
BoyerMyrvoldPlanar &	getBoyerMyrvoldPlanar () const
	Gets the class BoyerMyrvoldPlanar used in last computation.
Protected Member Functions
void	clear ()
	Deletes BoyerMyrvoldPlanar on heap.
bool	euler (const Graph &g)
	Returns true, iff the euler-bound e <= 3*n-6 is satisfied on simple graphs.
Protected Attributes
BoyerMyrvoldPlanar *	pBMP
	Class BoyerMyrvoldPlanar on heap.
int	nOfStructures
	The number of extracted Structures for statistical purposes.

---

Detailed Description

Wrapper class used for preprocessing and valid invocation of the planarity test.

This class is part of the extended Boyer-Myrvold planarity embedding algorithm to simplify invocation besides adding standard parameters (see classes in BoyerMyrvoldInit.h and BoyerMyrvoldPlanar.h). In addition the linear-time Boyer-Myrvold embedding algorithm was extended to extract multiple Kuratowski Subdivisions, whose number can be limited as desired (see classes in FindKuratowskis.h and ExtractKuratowskis.h). Furthermore all extracted subdivisions are unique.

Input graph:
There are no restrictions on the input graph G (except that it has to be finite, but if you do not have infinite RAM, that should do it :) ). In particular, G hasn't to be biconnected nor connected. Self-loops and multigraphs are possible, too.
Note: But if you want to use the extraction of Kuratowski Subdivisions, G has to be simple!

How to use it:
There exist two main functions, consisting of the planarity test itself and the planar embedding algorithm, which embeds the graph on the plane if possible. Each one has a fast but destructive variant, designed to be used on graphs that may be modified and a slower variant, which is for graphs that must not be alterated. Embeddings on the plane are given by a (genus 0) cyclic ordering of adjacency lists in the graph. Functions for constant graphs are available, too, if that makes sense for the function.

Examples:
planarDestructive(G), planar(G):
Tests graph G for planarity with the Boyer-Myrvold planarity test.

planarEmbedDestructive(G), planarEmbed(G), planarEmbed(G,H):
Tests graph G for planarity and returns a planar embedding in G, if G is planar. If G is a constant graph, the embedding is given in the GraphCopySimple H, so that both, the constant input graph and the resulting planar embedding are available.

planarEmbedDestructive(G,output,i), planarEmbed(G,output,i):
Tests graph G for planarity and returns a planar embedding, if G is planar. Otherwise up to i kuratowski subdivisions are returned to the list output. Use i = -1 for extraction of all subdivisions.

planarEmbedDestructive(G,output,i), planarEmbed(G,output,i):
Tests graph G for planarity and returns a planar embedding, if G is planar. Otherwise up to i kuratowski subdivisions are returned to the list output. Use i = -1 for extraction of all subdivisions. The extraction algorithm doesn't use sets of bundles instead of subdivisions paths, so this is designed for a fast computation while extracting some, but not a huge amount of Kuratowski Subdivisions.

planarEmbedDestructive(G,output,i,true), planarEmbed(G,output,i,true):
This is the same as above, but now bundles are used to compute much more subdivisions. Naturally the computation is slower than the function above, especially on large graphs.

Complete list of parameters for embedding functions:
e.g. planarEmbedDestructive(

• Graph& g,
  This is the input Graph.
• SList<KuratowskiWrapper>& output,
  All subdivisions are returned in this list.
• int embeddingGrade,
  This flag has 5 options dependent on value i:
  i = -3: no Embedding is computed
  i = -2: no FindKuratowskiProcedure is performed
  i = -1: all Kuratowski Subdivisions are extracted
  i = 0: no Kuratowski Subdivision is extracted, but FindKuratowskiProcedure is started
  i > 0: up to i Kuratowski Subdivisions are extracted.
• bool bundles,
  If bundles are used, some paths between two Kuratowski nodes are replaced by whole bundles of paths. On the one hand much more subdivisions can be extracted on the other computation time growths.
• bool limitStructures,
  If Kuratowski Structures are limited, all subdivisions in that Structures are extracted. Thereby none of the efforts made in FindKuratowskiProcedure are lost, which is creditable in comparison with limiting the number of extracted subdivisions. Note that the number of extracted subdivisions can highly vary.
• bool randomDFSTree,
  Iff true, a completely random DFS-Tree (the list of nodes and the adjacency-lists for each node are permuted at random) is created each time the planarity test is called. This is important for extracting huge amounts of Kuratowski subdivisions of one single Graph, since randomizing the DFSTree yields to new unknown subdivisions. Note that computation time growths up to 20 percent longer.
• bool avoidE2Minors
  Two minortypes, namely E2/AE2 and A, construct identical subdivisions on some graphs. To avoid this, set this flag true, otherwise false.

)

To experience the computation time difference to the PQTree-Planarity test please switch to release-mode, since a lot of slow testroutines and assertions were implemented in debug-mode. Also note the ability to transform KuratowskiWrapperLists to Lists of KuratowskiSubdivision through calling the function transform. Within this transformation is a switch to filter all similar or not similar Kuratowski Subdivisions.

Definition at line 158 of file BoyerMyrvold.h.

---

Constructor & Destructor Documentation

ogdf::BoyerMyrvold::BoyerMyrvold

(

)

[inline]

Constructor.

Definition at line 174 of file BoyerMyrvold.h.

ogdf::BoyerMyrvold::~BoyerMyrvold

(

)

[inline]

Destructor.

Definition at line 176 of file BoyerMyrvold.h.

---

Member Function Documentation

void ogdf::BoyerMyrvold::clear

(

)

[inline, protected]

Deletes BoyerMyrvoldPlanar on heap.

Definition at line 164 of file BoyerMyrvold.h.

bool ogdf::BoyerMyrvold::euler

(

const Graph &

g

)

[inline, protected]

Returns true, iff the euler-bound e <= 3*n-6 is satisfied on simple graphs.

int ogdf::BoyerMyrvold::numberOfStructures

(

)

[inline]

The number of extracted Structures for statistical purposes.

Definition at line 179 of file BoyerMyrvold.h.

bool ogdf::BoyerMyrvold::planarDestructive

(

Graph &

g

)

Returns true, iff g is planar.

This is the routine, which avoids the overhead of copying the input graph. It is therefore not suitable, if your graph must not be alterated!

bool ogdf::BoyerMyrvold::planar

(

const Graph &

g

)

Returns true, iff a copy of the constant graph g is planar.

Use this slower routine, if your graph must not be alterated.

void ogdf::BoyerMyrvold::transform	(	const KuratowskiWrapper &	source,
		KuratowskiSubdivision &	target,
		NodeArray< int > &	count,
		EdgeArray< int > &	countEdge
	)

Transforms KuratowskiWrapper in KuratowskiSubdivision.

void ogdf::BoyerMyrvold::transform	(	const SList< KuratowskiWrapper > &	sourceList,
		SList< KuratowskiSubdivision > &	targetList,
		const Graph &	g,
		const bool	onlyDifferent = false
	)

Transforms KuratowskiWrapper-List in KuratowskiSubdivision-List with respect to sieving constraints.

bool ogdf::BoyerMyrvold::planarEmbedDestructive	(	Graph &	g,
		SList< KuratowskiWrapper > &	output,
		int	embeddingGrade = BoyerMyrvoldPlanar::doNotFind,
		bool	bundles = false,
		bool	limitStructures = false,
		bool	randomDFSTree = false,
		bool	avoidE2Minors = true
	)

Returns an embedding, if g is planar and Kuratowski Subdivisions otherwise.

If g is planar, the adjLists of g specify a planar embedding. Use this function, if g may be changed.

Parameters:

	g	is the input graph.
	output	contains a number of Kuratowski Subdivisions depending on the other parameters
	embeddingGrade	is a flag bounding the number of extracted subdivisions
	bundles	extracts much more subdivisions, if set
	limitStructures	limits the number of Kuratowski Structures to embeddingGrade, if set
	randomDFSTree	randomizes Kuratowski extraction through randomizing the DFSTree, if set
	avoidE2Minors	avoids all E2-Minors and ensures unique subdivisions, if set

bool ogdf::BoyerMyrvold::planarEmbed	(	Graph &	g,
		SList< KuratowskiWrapper > &	list,
		int	embeddingGrade = BoyerMyrvoldPlanar::doNotFind,
		bool	bundles = false,
		bool	limitStructures = false,
		bool	randomDFSTree = false,
		bool	avoidE2Minors = true
	)

Returns an embedding, if g is planar and Kuratowski Subdivisions otherwise.

If g is planar, the adjLists of g specify a planar embedding. The function copies the graph before computation. Use this function, if g must not be changed in the non-planar case.

Parameters:

	output	contains a number of Kuratowski Subdivisions depending on the other parameters
	embeddingGrade	is a flag bounding the number of extracted subdivisions
	bundles	extracts much more subdivisions, if set
	limiStructures	limits the number of Kuratowski Structures to embeddingGrade, if set
	randomDFSTree	randomizes Kuratowski extraction through randomizing the DFSTree, if set
	avoidE2Minors	avoids all E2-Minors and ensures unique subdivisions, if set

bool ogdf::BoyerMyrvold::planarEmbed	(	const Graph &	g,
		GraphCopySimple &	h,
		SList< KuratowskiWrapper > &	list,
		int	embeddingGrade = BoyerMyrvoldPlanar::doNotFind,
		bool	bundles = false,
		bool	limitStructures = false,
		bool	randomDFSTree = false,
		bool	avoidE2Minors = true
	)

Returns an embedding, if constant graph g is planar and Kuratowski Subdivisions otherwise.

If g is planar, the adjLists of h specify a planar embedding. The function copies the graph before computation. Use this function, if g must not be changed.

Parameters:

	output	contains a number of Kuratowski Subdivisions depending on the other parameters
	embeddingGrade	is a flag bounding the number of extracted subdivisions
	bundles	extracts much more subdivisions, if set
	limiStructures	limits the number of Kuratowski Structures to embeddingGrade, if set
	randomDFSTree	randomizes Kuratowski extraction through randomizing the DFSTree, if set
	avoidE2Minors	avoids all E2-Minors and ensures unique subdivisions, if set

BoyerMyrvoldPlanar& ogdf::BoyerMyrvold::getBoyerMyrvoldPlanar

(

)

const [inline]

Gets the class BoyerMyrvoldPlanar used in last computation.

Definition at line 267 of file BoyerMyrvold.h.

---

Member Data Documentation

BoyerMyrvoldPlanar* ogdf::BoyerMyrvold::pBMP [protected]

Class BoyerMyrvoldPlanar on heap.

Definition at line 161 of file BoyerMyrvold.h.

int ogdf::BoyerMyrvold::nOfStructures [protected]

The number of extracted Structures for statistical purposes.

Definition at line 170 of file BoyerMyrvold.h.

---

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

• ogdf/planarity/BoyerMyrvold.h

---