Open
Graph Drawing
Framework

 v.2012.07
 

ogdf::BoyerMyrvoldPlanar Class Reference

This class implements the extended BoyerMyrvold planarity embedding algorithm. More...

#include <ogdf/internal/planarity/BoyerMyrvoldPlanar.h>

List of all members.

Public Types

enum  enumEmbeddingGrade { doNotEmbed = -3, doNotFind = -2, doFindUnlimited = -1, doFindZero = 0 }
 Denotes the different embedding options. More...

Public Member Functions

 BoyerMyrvoldPlanar (Graph &g, bool bundles, int m_embeddingGrade, bool limitStructures, SListPure< KuratowskiStructure > &output, bool randomDFSTree, bool avoidE2Minors)
 Constructor, for parameters see BoyerMyrvold.
 ~BoyerMyrvoldPlanar ()
 Destructor.
void flipBicomp (int c, int marker, NodeArray< int > &visited, bool wholeGraph, bool deleteFlipFlags)
 Flips all nodes of the bicomp with unique, real, rootchild c as necessary.
BoyerMyrvoldPlanaroperator= (const BoyerMyrvoldPlanar &)
 Assignment operator is undefined!
bool start ()
 Starts the embedding algorithm.

Protected Member Functions

node activeSuccessor (node w, int &direction, int v, int &info)
 Walks upon external face in the given direction starting at w until an active vertex is reached.
adjEntry beforeShortCircuitEdge (node v, int direction)
 Returns underlying former adjEntry, if a short circuit edge in direction of v exists.
node constActiveSuccessor (node w, int direction, int v, int &info)
 Walks upon external face in the given direction (without changing it) until an active vertex is reached.
node constSuccessorOnExternalFace (node v, int direction)
 Returns the successornode on the external face in given direction.
node constSuccessorWithoutShortCircuit (node v, int direction)
 Walks upon external face in direction avoiding short circuit edges.
void createShortCircuitEdge (const node v, const int v_dir, const node w, const int w_dir)
 Creates a short circuit edge from node v with direction v_dir to node w with direction w_dir.
bool embed ()
 Starts the embedding phase, which embeds m_g node by node in descending DFI-order.
void embedBackedges (const node v, const int v_dir, const node w, const int w_dir, const int i)
 Embeds backedges from node v with direction v_dir to node w with direction w_dir.
void embedBackedgesOnlyPlanar (const node v, const int v_dir, const node w, const int w_dir, const int i)
 Links (not embed) backedges from node v with direction v_dir to node w with direction w_dir.
bool externallyActive (node w, int v)
 Checks whether real node w is externally active while embedding node with DFI v.
bool inactive (node w, int v)
 Checks whether real node w is inactive while embedding node with DFI v.
int infoAboutNode (node w, int v)
 Checks all dynamic information about a node w while embedding node with DFI v.
bool internallyActive (node w, int v)
 Checks whether real node w is internally active while embedding node with DFI v.
void mergeBiconnectedComponent (StackPure< int > &stack, const int j)
 Merges the last two biconnected components saved in stack while embedding them.
void mergeBiconnectedComponentOnlyPlanar (StackPure< int > &stack, const int j)
 Merges the last two biconnected components saved in stack without embedding them.
void mergeUnprocessedNodes ()
 Merges unprocessed virtual nodes such as the dfs-roots with their real counterpart.
bool pertinent (node w)
 Checks whether node w is pertinent. w has to be non-virtual.
void postProcessEmbedding ()
 Postprocessing of the graph, so that all virtual vertices are embedded and all bicomps are flipped.
void printNodeInfo (node v)
 Prints informations about node v.
node successorOnExternalFace (node w, int &direction)
 Walks upon external face in the given direction starting at w.
node successorWithoutShortCircuit (node w, int &direction)
 Walks upon external face in given direction avoiding short circuit edges.
int walkdown (const int i, const node v, FindKuratowskis *findKuratowskis)
 Walkdown: Embeds all backedges with DFI i as targetnode to node v.
node walkup (const node v, const node w, const int marker, const edge back)
 Walkup: Builds the pertinent subgraph for the backedge back.
bool wNodesExist (node root, node stopx, node stopy)
 Checks, if one ore more wNodes exist between the two stopping vertices stopx and stopy.

Protected Attributes

NodeArray< adjEntrym_adjParent
 The adjEntry which goes from DFS-parent to current vertex.
const bool m_avoidE2Minors
NodeArray< SListPure< adjEntry > > m_backedgeFlags
 Holds information, if node is the source of a backedge.
NodeArray< adjEntrym_beforeSCE [2]
 Links for short circuit edges.
const bool m_bundles
 Some parameters... see BoyerMyrvold for further options.
NodeArray< int > m_dfi
 The one and only DFI-NodeArray.
EdgeArray< int > m_edgeType
 Contains the type of each edge.
const int m_embeddingGrade
NodeArray< bool > m_flipped
 Iff true, the node is the root of a bicomp which has to be flipped.
int m_flippedNodes
 The whole number of bicomps, which have to be flipped.
Graphm_g
 Input graph, which can be altered.
NodeArray< int > m_highestSubtreeDFI
 The highest DFI in a subtree with node as root.
NodeArray< int > m_leastAncestor
 The DFI of the least ancestor node over all backedges.
const bool m_limitStructures
NodeArray< adjEntrym_link [2]
 Links to opposite adjacency entries on external face in clockwise resp. ccw order.
NodeArray< int > m_lowPoint
 The lowpoint of each node.
Array< nodem_nodeFromDFI
 Returns appropriate node from given DFI.
SListPure< KuratowskiStructure > & m_output
 Data structure for the kuratowski subdivisions, which will be returned.
NodeArray< SListPure< node > > m_pertinentRoots
 List of virtual bicomp roots, that are pertinent to the current embedded node.
NodeArray< ListIterator< node > > m_pNodeInParent
 Pointer to node contained in the DFSChildList of his parent, if exists.
EdgeArray< nodem_pointsToRoot
 Identifies the rootnode of the child bicomp the given backedge points to.
const bool m_randomDFSTree
NodeArray< nodem_realVertex
 Link to non-virtual vertex of a virtual Vertex.
NodeArray< ListPure< node > > m_separatedDFSChildList
 A list to all separated DFS-children of node.
NodeArray< int > m_visited
 This Array keeps track of all vertices that are visited by current walkup.
NodeArray< int > m_visitedWithBackedge
 Keeps track of all vertices that are visited by the walkup through a specific backedge.

Friends

class BoyerMyrvold
class BoyerMyrvoldInit
class ExtractKuratowskis
class FindKuratowskis

Detailed Description

This class implements the extended BoyerMyrvold planarity embedding algorithm.

Definition at line 88 of file BoyerMyrvoldPlanar.h.


Member Enumeration Documentation

Denotes the different embedding options.

Enumerator:
doNotEmbed 
doNotFind 
doFindUnlimited 
doFindZero 

Definition at line 113 of file BoyerMyrvoldPlanar.h.


Constructor & Destructor Documentation

ogdf::BoyerMyrvoldPlanar::BoyerMyrvoldPlanar ( Graph g,
bool  bundles,
int  m_embeddingGrade,
bool  limitStructures,
SListPure< KuratowskiStructure > &  output,
bool  randomDFSTree,
bool  avoidE2Minors 
)

Constructor, for parameters see BoyerMyrvold.

ogdf::BoyerMyrvoldPlanar::~BoyerMyrvoldPlanar ( )
inline

Destructor.

Definition at line 107 of file BoyerMyrvoldPlanar.h.


Member Function Documentation

node ogdf::BoyerMyrvoldPlanar::activeSuccessor ( node  w,
int &  direction,
int  v,
int &  info 
)
protected

Walks upon external face in the given direction starting at w until an active vertex is reached.

Returns dynamical typeinformation info of that endvertex.

adjEntry ogdf::BoyerMyrvoldPlanar::beforeShortCircuitEdge ( node  v,
int  direction 
)
inlineprotected

Returns underlying former adjEntry, if a short circuit edge in direction of v exists.

Otherwise the common edge is returned. In every case the returned adjEntry points to the targetnode.

Definition at line 255 of file BoyerMyrvoldPlanar.h.

node ogdf::BoyerMyrvoldPlanar::constActiveSuccessor ( node  w,
int  direction,
int  v,
int &  info 
)
inlineprotected

Walks upon external face in the given direction (without changing it) until an active vertex is reached.

Returns dynamical typeinformation info of that endvertex. But does not change the direction.

Definition at line 268 of file BoyerMyrvoldPlanar.h.

node ogdf::BoyerMyrvoldPlanar::constSuccessorOnExternalFace ( node  v,
int  direction 
)
inlineprotected

Returns the successornode on the external face in given direction.

direction is not changed.

Definition at line 236 of file BoyerMyrvoldPlanar.h.

node ogdf::BoyerMyrvoldPlanar::constSuccessorWithoutShortCircuit ( node  v,
int  direction 
)
inlineprotected

Walks upon external face in direction avoiding short circuit edges.

direction is not changed.

Definition at line 245 of file BoyerMyrvoldPlanar.h.

void ogdf::BoyerMyrvoldPlanar::createShortCircuitEdge ( const node  v,
const int  v_dir,
const node  w,
const int  w_dir 
)
protected

Creates a short circuit edge from node v with direction v_dir to node w with direction w_dir.

bool ogdf::BoyerMyrvoldPlanar::embed ( )
protected

Starts the embedding phase, which embeds m_g node by node in descending DFI-order.

Returns true, if graph is planar, false otherwise.

void ogdf::BoyerMyrvoldPlanar::embedBackedges ( const node  v,
const int  v_dir,
const node  w,
const int  w_dir,
const int  i 
)
protected

Embeds backedges from node v with direction v_dir to node w with direction w_dir.

i is the DFI of current embedded node.

void ogdf::BoyerMyrvoldPlanar::embedBackedgesOnlyPlanar ( const node  v,
const int  v_dir,
const node  w,
const int  w_dir,
const int  i 
)
protected

Links (not embed) backedges from node v with direction v_dir to node w with direction w_dir.

i is the DFI of current embedded node.

bool ogdf::BoyerMyrvoldPlanar::externallyActive ( node  w,
int  v 
)
inlineprotected

Checks whether real node w is externally active while embedding node with DFI v.

Definition at line 156 of file BoyerMyrvoldPlanar.h.

void ogdf::BoyerMyrvoldPlanar::flipBicomp ( int  c,
int  marker,
NodeArray< int > &  visited,
bool  wholeGraph,
bool  deleteFlipFlags 
)

Flips all nodes of the bicomp with unique, real, rootchild c as necessary.

Parameters:
cis the unique rootchild of the bicomp
markeris the value which marks nodes as visited
visitedis the array containing visiting information
wholeGraphIff true, all bicomps of all connected components will be traversed
deleteFlipFlagsIff true, the flipping flags will be deleted after flipping
bool ogdf::BoyerMyrvoldPlanar::inactive ( node  w,
int  v 
)
inlineprotected

Checks whether real node w is inactive while embedding node with DFI v.

Definition at line 165 of file BoyerMyrvoldPlanar.h.

int ogdf::BoyerMyrvoldPlanar::infoAboutNode ( node  w,
int  v 
)
inlineprotected

Checks all dynamic information about a node w while embedding node with DFI v.

Returns:
This method returns the following values:
  • 0 = inactive
  • 1 = internallyActive
  • 2 = pertinent and externallyActive
  • 3 = externallyActive and not pertinent

Definition at line 182 of file BoyerMyrvoldPlanar.h.

bool ogdf::BoyerMyrvoldPlanar::internallyActive ( node  w,
int  v 
)
inlineprotected

Checks whether real node w is internally active while embedding node with DFI v.

Definition at line 149 of file BoyerMyrvoldPlanar.h.

void ogdf::BoyerMyrvoldPlanar::mergeBiconnectedComponent ( StackPure< int > &  stack,
const int  j 
)
protected

Merges the last two biconnected components saved in stack while embedding them.

j is the outgoing traversal direction of the current node to embed

void ogdf::BoyerMyrvoldPlanar::mergeBiconnectedComponentOnlyPlanar ( StackPure< int > &  stack,
const int  j 
)
protected

Merges the last two biconnected components saved in stack without embedding them.

j is the outgoing traversal direction of the current node to embed

void ogdf::BoyerMyrvoldPlanar::mergeUnprocessedNodes ( )
protected

Merges unprocessed virtual nodes such as the dfs-roots with their real counterpart.

BoyerMyrvoldPlanar& ogdf::BoyerMyrvoldPlanar::operator= ( const BoyerMyrvoldPlanar )

Assignment operator is undefined!

bool ogdf::BoyerMyrvoldPlanar::pertinent ( node  w)
inlineprotected

Checks whether node w is pertinent. w has to be non-virtual.

Definition at line 142 of file BoyerMyrvoldPlanar.h.

void ogdf::BoyerMyrvoldPlanar::postProcessEmbedding ( )
protected

Postprocessing of the graph, so that all virtual vertices are embedded and all bicomps are flipped.

In addition, embedding steps for parallel edges and self-loops are implemented.

void ogdf::BoyerMyrvoldPlanar::printNodeInfo ( node  v)
inlineprotected

Prints informations about node v.

Definition at line 295 of file BoyerMyrvoldPlanar.h.

bool ogdf::BoyerMyrvoldPlanar::start ( )

Starts the embedding algorithm.

node ogdf::BoyerMyrvoldPlanar::successorOnExternalFace ( node  w,
int &  direction 
)
inlineprotected

Walks upon external face in the given direction starting at w.

If none of the bicomps has been flipped then CW = clockwise and CCW = counterclockwise holds. In general, the traversaldirection could have been changed due to flipped components. If this occurs, the traversaldirection is flipped.

Definition at line 206 of file BoyerMyrvoldPlanar.h.

node ogdf::BoyerMyrvoldPlanar::successorWithoutShortCircuit ( node  w,
int &  direction 
)
inlineprotected

Walks upon external face in given direction avoiding short circuit edges.

Definition at line 220 of file BoyerMyrvoldPlanar.h.

int ogdf::BoyerMyrvoldPlanar::walkdown ( const int  i,
const node  v,
FindKuratowskis findKuratowskis 
)
protected

Walkdown: Embeds all backedges with DFI i as targetnode to node v.

Parameters:
iis the DFI of the current vertex to embed
vis the virtual node being the root of the bicomp attached to i
findKuratowskiscollects information in order to extract Kuratowski Subdivisions later
Returns:
1, iff the embedding process found a stopping configuration
node ogdf::BoyerMyrvoldPlanar::walkup ( const node  v,
const node  w,
const int  marker,
const edge  back 
)
protected

Walkup: Builds the pertinent subgraph for the backedge back.

back is the backedge between nodes v and w. v is the current node to embed. All visited nodes are marked with value marker. The Function returns the last traversed node.

bool ogdf::BoyerMyrvoldPlanar::wNodesExist ( node  root,
node  stopx,
node  stopy 
)
inlineprotected

Checks, if one ore more wNodes exist between the two stopping vertices stopx and stopy.

The node root is root of the bicomp containing the stopping vertices

Definition at line 275 of file BoyerMyrvoldPlanar.h.


Friends And Related Function Documentation

friend class BoyerMyrvold
friend

Definition at line 90 of file BoyerMyrvoldPlanar.h.

friend class BoyerMyrvoldInit
friend

Definition at line 91 of file BoyerMyrvoldPlanar.h.

friend class ExtractKuratowskis
friend

Definition at line 93 of file BoyerMyrvoldPlanar.h.

friend class FindKuratowskis
friend

Definition at line 92 of file BoyerMyrvoldPlanar.h.


Member Data Documentation

NodeArray<adjEntry> ogdf::BoyerMyrvoldPlanar::m_adjParent
protected

The adjEntry which goes from DFS-parent to current vertex.

Definition at line 402 of file BoyerMyrvoldPlanar.h.

const bool ogdf::BoyerMyrvoldPlanar::m_avoidE2Minors
protected

Definition at line 372 of file BoyerMyrvoldPlanar.h.

NodeArray<SListPure<adjEntry> > ogdf::BoyerMyrvoldPlanar::m_backedgeFlags
protected

Holds information, if node is the source of a backedge.

This information refers to the adjEntries on the targetnode and is used during the walkdown

Definition at line 458 of file BoyerMyrvoldPlanar.h.

NodeArray<adjEntry> ogdf::BoyerMyrvoldPlanar::m_beforeSCE[2]
protected

Links for short circuit edges.

If short circuit edges are introduced, the former adjEntries to the neighbors have to be saved here for embedding and merging purposes. If there is no short circuit edge, this adjEntry is NULL.

Definition at line 399 of file BoyerMyrvoldPlanar.h.

const bool ogdf::BoyerMyrvoldPlanar::m_bundles
protected

Some parameters... see BoyerMyrvold for further options.

Definition at line 368 of file BoyerMyrvoldPlanar.h.

NodeArray<int> ogdf::BoyerMyrvoldPlanar::m_dfi
protected

The one and only DFI-NodeArray.

Definition at line 384 of file BoyerMyrvoldPlanar.h.

EdgeArray<int> ogdf::BoyerMyrvoldPlanar::m_edgeType
protected

Contains the type of each edge.

Parameters:
0= EDGE_UNDEFINED
1= EDGE_SELFLOOP
2= EDGE_BACK
3= EDGE_DFS
4= EDGE_DFS_PARALLEL
5= EDGE_BACK_DELETED

Definition at line 417 of file BoyerMyrvoldPlanar.h.

const int ogdf::BoyerMyrvoldPlanar::m_embeddingGrade
protected

Definition at line 369 of file BoyerMyrvoldPlanar.h.

NodeArray<bool> ogdf::BoyerMyrvoldPlanar::m_flipped
protected

Iff true, the node is the root of a bicomp which has to be flipped.

The DFS-child of every bicomp root vertex is unique. if a bicomp is flipped, this DFS-child is marked to check whether the bicomp has to be flipped or not.

Definition at line 452 of file BoyerMyrvoldPlanar.h.

int ogdf::BoyerMyrvoldPlanar::m_flippedNodes
protected

The whole number of bicomps, which have to be flipped.

Definition at line 375 of file BoyerMyrvoldPlanar.h.

Graph& ogdf::BoyerMyrvoldPlanar::m_g
protected

Input graph, which can be altered.

Definition at line 365 of file BoyerMyrvoldPlanar.h.

NodeArray<int> ogdf::BoyerMyrvoldPlanar::m_highestSubtreeDFI
protected

The highest DFI in a subtree with node as root.

Definition at line 423 of file BoyerMyrvoldPlanar.h.

NodeArray<int> ogdf::BoyerMyrvoldPlanar::m_leastAncestor
protected

The DFI of the least ancestor node over all backedges.

If no backedge exists, the least ancestor is the DFI of that node itself

Definition at line 407 of file BoyerMyrvoldPlanar.h.

const bool ogdf::BoyerMyrvoldPlanar::m_limitStructures
protected

Definition at line 370 of file BoyerMyrvoldPlanar.h.

NodeArray<adjEntry> ogdf::BoyerMyrvoldPlanar::m_link[2]
protected

Links to opposite adjacency entries on external face in clockwise resp. ccw order.

m_link[0]=CCW, m_link[1]=CW

Definition at line 392 of file BoyerMyrvoldPlanar.h.

NodeArray<int> ogdf::BoyerMyrvoldPlanar::m_lowPoint
protected

The lowpoint of each node.

Definition at line 420 of file BoyerMyrvoldPlanar.h.

Array<node> ogdf::BoyerMyrvoldPlanar::m_nodeFromDFI
protected

Returns appropriate node from given DFI.

Definition at line 387 of file BoyerMyrvoldPlanar.h.

SListPure<KuratowskiStructure>& ogdf::BoyerMyrvoldPlanar::m_output
protected

Data structure for the kuratowski subdivisions, which will be returned.

Definition at line 464 of file BoyerMyrvoldPlanar.h.

NodeArray<SListPure<node> > ogdf::BoyerMyrvoldPlanar::m_pertinentRoots
protected

List of virtual bicomp roots, that are pertinent to the current embedded node.

Definition at line 461 of file BoyerMyrvoldPlanar.h.

NodeArray<ListIterator<node> > ogdf::BoyerMyrvoldPlanar::m_pNodeInParent
protected

Pointer to node contained in the DFSChildList of his parent, if exists.

If node isn't in list or list doesn't exist, the pointer is set to NULL.

Definition at line 433 of file BoyerMyrvoldPlanar.h.

EdgeArray<node> ogdf::BoyerMyrvoldPlanar::m_pointsToRoot
protected

Identifies the rootnode of the child bicomp the given backedge points to.

Definition at line 440 of file BoyerMyrvoldPlanar.h.

const bool ogdf::BoyerMyrvoldPlanar::m_randomDFSTree
protected

Definition at line 371 of file BoyerMyrvoldPlanar.h.

NodeArray<node> ogdf::BoyerMyrvoldPlanar::m_realVertex
protected

Link to non-virtual vertex of a virtual Vertex.

A virtual vertex has negative DFI of the DFS-Child of related non-virtual Vertex

Definition at line 381 of file BoyerMyrvoldPlanar.h.

NodeArray<ListPure<node> > ogdf::BoyerMyrvoldPlanar::m_separatedDFSChildList
protected

A list to all separated DFS-children of node.

The list is sorted by lowpoint values (in linear time)

Definition at line 428 of file BoyerMyrvoldPlanar.h.

NodeArray<int> ogdf::BoyerMyrvoldPlanar::m_visited
protected

This Array keeps track of all vertices that are visited by current walkup.

Definition at line 437 of file BoyerMyrvoldPlanar.h.

NodeArray<int> ogdf::BoyerMyrvoldPlanar::m_visitedWithBackedge
protected

Keeps track of all vertices that are visited by the walkup through a specific backedge.

This is done in order to refer to the unique child-bicomp of v.

Definition at line 445 of file BoyerMyrvoldPlanar.h.


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