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

#include <ogdf/planarity/BoyerMyrvold.h>

Inheritance diagram for ogdf::BoyerMyrvold:

Public Member Functions
	BoyerMyrvold ()
	Constructor.

	~BoyerMyrvold ()
	Destructor.

virtual bool	isPlanar (const Graph &g) override
	Returns true, iff a copy of the constant graph `g` is planar.

virtual bool	isPlanarDestructive (Graph &g) override
	Returns true, iff `g` is planar.

int	numberOfStructures ()
	The number of extracted Structures for statistical purposes.

virtual bool	planarEmbed (Graph &G) override
	Returns true, if G is planar, false otherwise. If true, G contains a planar embedding.

bool	planarEmbed (Graph &g, SList< KuratowskiWrapper > &output, BoyerMyrvoldPlanar::EmbeddingGrade embeddingGrade=BoyerMyrvoldPlanar::EmbeddingGrade::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 > &output, int embeddingGrade, 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 (GraphCopySimple &h, SList< KuratowskiWrapper > &output, BoyerMyrvoldPlanar::EmbeddingGrade embeddingGrade=BoyerMyrvoldPlanar::EmbeddingGrade::doNotFind, bool bundles=false, bool limitStructures=false, bool randomDFSTree=false, bool avoidE2Minors=true)
	Returns an embedding, if graph copy `h` is planar and Kuratowski Subdivisions otherwise.

bool	planarEmbed (GraphCopySimple &h, SList< KuratowskiWrapper > &output, int embeddingGrade, bool bundles=false, bool limitStructures=false, bool randomDFSTree=false, bool avoidE2Minors=true)
	Returns an embedding, if graph copy `h` is planar and Kuratowski Subdivisions otherwise.

bool	planarEmbedDestructive (Graph &g, SList< KuratowskiWrapper > &output, BoyerMyrvoldPlanar::EmbeddingGrade embeddingGrade=BoyerMyrvoldPlanar::EmbeddingGrade::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	planarEmbedDestructive (Graph &g, SList< KuratowskiWrapper > &output, int embeddingGrade, bool bundles=false, bool limitStructures=false, bool randomDFSTree=false, bool avoidE2Minors=true)
	Returns an embedding, if `g` is planar and Kuratowski Subdivisions otherwise.

virtual bool	planarEmbedPlanarGraph (Graph &G) override
	Constructs a planar embedding of G. `G` has to be 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.

void	transform (const SList< KuratowskiWrapper > &sourceList, SList< KuratowskiSubdivision > &targetList, const GraphCopySimple &h, const bool onlyDifferent=false)
	Transforms KuratowskiWrapper-List in KuratowskiSubdivision-List with respect to sieving constraints.

Public Member Functions inherited from ogdf::PlanarityModule
	PlanarityModule ()

virtual	~PlanarityModule ()

Protected Member Functions
void	clear ()
	Deletes BoyerMyrvoldPlanar on heap.

Protected Attributes
int	nOfStructures
	The number of extracted Structures for statistical purposes.

BoyerMyrvoldPlanar *	pBMP
	Class BoyerMyrvoldPlanar on heap.

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 altered. 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:
BoyerMyrvold::isPlanarDestructive(G), BoyerMyrvold::isPlanar(G):
Tests graph G for planarity with the Boyer-Myrvold planarity test.

BoyerMyrvold::planarEmbedDestructive(G), BoyerMyrvold::planarEmbed(G), BoyerMyrvold::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.

BoyerMyrvold::planarEmbedDestructive(G,output,i), BoyerMyrvold::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.

BoyerMyrvold::planarEmbedDestructive(G,output,i), BoyerMyrvold::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.

BoyerMyrvold::planarEmbedDestructive(G,output,i,true), BoyerMyrvold::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 138 of file BoyerMyrvold.h.

Constructor & Destructor Documentation

◆ BoyerMyrvold()

ogdf::BoyerMyrvold::BoyerMyrvold ( )

inline

Constructor.

Definition at line 154 of file BoyerMyrvold.h.

◆ ~BoyerMyrvold()

ogdf::BoyerMyrvold::~BoyerMyrvold ( )

inline

Destructor.

Definition at line 160 of file BoyerMyrvold.h.

Member Function Documentation

◆ clear()

void ogdf::BoyerMyrvold::clear ( )

inlineprotected

Deletes BoyerMyrvoldPlanar on heap.

Definition at line 144 of file BoyerMyrvold.h.

◆ isPlanar()

virtual bool ogdf::BoyerMyrvold::isPlanar ( const Graph & g )

overridevirtual

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

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

Implements ogdf::PlanarityModule.

◆ isPlanarDestructive()

virtual bool ogdf::BoyerMyrvold::isPlanarDestructive ( Graph & g )

overridevirtual

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!

Implements ogdf::PlanarityModule.

◆ numberOfStructures()

int ogdf::BoyerMyrvold::numberOfStructures ( )

inline

The number of extracted Structures for statistical purposes.

Definition at line 163 of file BoyerMyrvold.h.

◆ planarEmbed() [1/5]

virtual bool ogdf::BoyerMyrvold::planarEmbed ( Graph & G )

inlineoverridevirtual

Returns true, if G is planar, false otherwise. If true, G contains a planar embedding.

Implements ogdf::PlanarityModule.

Definition at line 177 of file BoyerMyrvold.h.

◆ planarEmbed() [2/5]

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

inline

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

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

Definition at line 260 of file BoyerMyrvold.h.

◆ planarEmbed() [3/5]

bool ogdf::BoyerMyrvold::planarEmbed	(	Graph &	g,
		SList< KuratowskiWrapper > &	output,
		int	embeddingGrade,
		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

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

◆ planarEmbed() [4/5]

bool ogdf::BoyerMyrvold::planarEmbed	(	GraphCopySimple &	h,
		SList< KuratowskiWrapper > &	output,
		BoyerMyrvoldPlanar::EmbeddingGrade	embeddingGrade = `BoyerMyrvoldPlanar::EmbeddingGrade::doNotFind`,
		bool	bundles = `false`,
		bool	limitStructures = `false`,
		bool	randomDFSTree = `false`,
		bool	avoidE2Minors = `true`
	)

inline

Returns an embedding, if graph copy h is planar and Kuratowski Subdivisions otherwise.

If h 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

h	is the input graph copy.
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

Definition at line 285 of file BoyerMyrvold.h.

◆ planarEmbed() [5/5]

bool ogdf::BoyerMyrvold::planarEmbed	(	GraphCopySimple &	h,
		SList< KuratowskiWrapper > &	output,
		int	embeddingGrade,
		bool	bundles = `false`,
		bool	limitStructures = `false`,
		bool	randomDFSTree = `false`,
		bool	avoidE2Minors = `true`
	)

Returns an embedding, if graph copy h is planar and Kuratowski Subdivisions otherwise.

If h 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

h	is the input graph copy.
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

◆ planarEmbedDestructive() [1/2]

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

inline

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

Definition at line 234 of file BoyerMyrvold.h.

◆ planarEmbedDestructive() [2/2]

bool ogdf::BoyerMyrvold::planarEmbedDestructive	(	Graph &	g,
		SList< KuratowskiWrapper > &	output,
		int	embeddingGrade,
		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

◆ planarEmbedPlanarGraph()

virtual bool ogdf::BoyerMyrvold::planarEmbedPlanarGraph ( Graph & G )

inlineoverridevirtual

Constructs a planar embedding of G. G has to be planar!

Returns true if the embedding was successful. Returns false, if the given graph was non-planar (and leaves the graph in an at least partially deleted state)

This routine is slightly faster than planarEmbed, but requires G to be planar. If G is not planar, the graph will be destroyed while trying to embed it!

Implements ogdf::PlanarityModule.

Definition at line 191 of file BoyerMyrvold.h.

◆ transform() [1/3]

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

Transforms KuratowskiWrapper in KuratowskiSubdivision.

◆ transform() [2/3]

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.

This method is called if BoyerMyrvold::planarEmbed was called with the Graph g previously.

◆ transform() [3/3]

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

inline

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

This method is called if BoyerMyrvold::planarEmbed was called with the GraphCopySimple h previously.

Definition at line 212 of file BoyerMyrvold.h.

Member Data Documentation

◆ nOfStructures

int ogdf::BoyerMyrvold::nOfStructures

protected

The number of extracted Structures for statistical purposes.

Definition at line 150 of file BoyerMyrvold.h.

◆ pBMP

BoyerMyrvoldPlanar* ogdf::BoyerMyrvold::pBMP

protected

Class BoyerMyrvoldPlanar on heap.

Definition at line 141 of file BoyerMyrvold.h.

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

include/ogdf/planarity/BoyerMyrvold.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ BoyerMyrvold()

◆ ~BoyerMyrvold()

Member Function Documentation

◆ clear()

◆ isPlanar()

◆ isPlanarDestructive()

◆ numberOfStructures()

◆ planarEmbed() [1/5]

◆ planarEmbed() [2/5]

◆ planarEmbed() [3/5]

◆ planarEmbed() [4/5]

◆ planarEmbed() [5/5]

◆ planarEmbedDestructive() [1/2]

◆ planarEmbedDestructive() [2/2]

◆ planarEmbedPlanarGraph()

◆ transform() [1/3]

◆ transform() [2/3]

◆ transform() [3/3]

Member Data Documentation

◆ nOfStructures

◆ pBMP

Open
Graph Drawing
Framework