Open
Graph Drawing
Framework

 v.2015.05
 

ogdf::BoyerMyrvold Class Reference

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. More...
 
 ~BoyerMyrvold ()
 Destructor. More...
 
virtual bool isPlanar (const Graph &g)
 Returns true, iff a copy of the constant graph g is planar. More...
 
virtual bool isPlanarDestructive (Graph &g)
 Returns true, iff g is planar. More...
 
int numberOfStructures ()
 The number of extracted Structures for statistical purposes. More...
 
virtual bool planarEmbed (Graph &G)
 Returns true, if G is planar, false otherwise. If true, G contains a planar embedding. More...
 
bool planarEmbed (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. More...
 
bool planarEmbed (GraphCopySimple &h, SList< KuratowskiWrapper > &output, int embeddingGrade=BoyerMyrvoldPlanar::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. More...
 
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. More...
 
virtual bool planarEmbedPlanarGraph (Graph &G)
 Constructs a planar embedding of G. G has to be planar! More...
 
void transform (const KuratowskiWrapper &source, KuratowskiSubdivision &target, NodeArray< int > &count, EdgeArray< int > &countEdge)
 Transforms KuratowskiWrapper in KuratowskiSubdivision. More...
 
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. More...
 
- Public Member Functions inherited from ogdf::PlanarityModule
 PlanarityModule ()
 
virtual ~PlanarityModule ()
 

Protected Member Functions

void clear ()
 Deletes BoyerMyrvoldPlanar on heap. More...
 

Protected Attributes

int nOfStructures
 The number of extracted Structures for statistical purposes. More...
 
BoyerMyrvoldPlanarpBMP
 Class BoyerMyrvoldPlanar on heap. More...
 

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:
isPlanarDestructive(G), isPlanar(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 152 of file BoyerMyrvold.h.

Constructor & Destructor Documentation

ogdf::BoyerMyrvold::BoyerMyrvold ( )
inline

Constructor.

Definition at line 166 of file BoyerMyrvold.h.

ogdf::BoyerMyrvold::~BoyerMyrvold ( )
inline

Destructor.

Definition at line 168 of file BoyerMyrvold.h.

Member Function Documentation

void ogdf::BoyerMyrvold::clear ( )
inlineprotected

Deletes BoyerMyrvoldPlanar on heap.

Definition at line 159 of file BoyerMyrvold.h.

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

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.

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

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.

int ogdf::BoyerMyrvold::numberOfStructures ( )
inline

The number of extracted Structures for statistical purposes.

Definition at line 171 of file BoyerMyrvold.h.

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

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

Implements ogdf::PlanarityModule.

Definition at line 185 of file BoyerMyrvold.h.

bool ogdf::BoyerMyrvold::planarEmbed ( 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. The function copies the graph before computation. Use this function, if g must not be changed in the non-planar case.

Parameters
gis the input graph.
outputcontains a number of Kuratowski Subdivisions depending on the other parameters
embeddingGradeis a flag bounding the number of extracted subdivisions
bundlesextracts much more subdivisions, if set
limitStructureslimits the number of Kuratowski Structures to embeddingGrade, if set
randomDFSTreerandomizes Kuratowski extraction through randomizing the DFSTree, if set
avoidE2Minorsavoids all E2-Minors and ensures unique subdivisions, if set
bool ogdf::BoyerMyrvold::planarEmbed ( GraphCopySimple h,
SList< KuratowskiWrapper > &  output,
int  embeddingGrade = BoyerMyrvoldPlanar::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.

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
his the input graph copy.
outputcontains a number of Kuratowski Subdivisions depending on the other parameters
embeddingGradeis a flag bounding the number of extracted subdivisions
bundlesextracts much more subdivisions, if set
limitStructureslimits the number of Kuratowski Structures to embeddingGrade, if set
randomDFSTreerandomizes Kuratowski extraction through randomizing the DFSTree, if set
avoidE2Minorsavoids all E2-Minors and ensures unique subdivisions, if set
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
gis the input graph.
outputcontains a number of Kuratowski Subdivisions depending on the other parameters
embeddingGradeis a flag bounding the number of extracted subdivisions
bundlesextracts much more subdivisions, if set
limitStructureslimits the number of Kuratowski Structures to embeddingGrade, if set
randomDFSTreerandomizes Kuratowski extraction through randomizing the DFSTree, if set
avoidE2Minorsavoids all E2-Minors and ensures unique subdivisions, if set
virtual bool ogdf::BoyerMyrvold::planarEmbedPlanarGraph ( Graph G)
inlinevirtual

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 199 of file BoyerMyrvold.h.

void ogdf::BoyerMyrvold::transform ( const KuratowskiWrapper source,
KuratowskiSubdivision target,
NodeArray< int > &  count,
EdgeArray< int > &  countEdge 
)
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.

Member Data Documentation

int ogdf::BoyerMyrvold::nOfStructures
protected

The number of extracted Structures for statistical purposes.

Definition at line 162 of file BoyerMyrvold.h.

BoyerMyrvoldPlanar* ogdf::BoyerMyrvold::pBMP
protected

Class BoyerMyrvoldPlanar on heap.

Definition at line 156 of file BoyerMyrvold.h.


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