# OpenGraph DrawingFramework

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)
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

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.
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.
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
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:
 c is the unique rootchild of the bicomp marker is the value which marks nodes as visited visited is the array containing visiting information wholeGraph Iff true, all bicomps of all connected components will be traversed deleteFlipFlags Iff 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

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:
 i is the DFI of the current vertex to embed v is the virtual node being the root of the bicomp attached to i findKuratowskis collects 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

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 > 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 ogdf::BoyerMyrvoldPlanar::m_beforeSCE[2]
protected

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 ogdf::BoyerMyrvoldPlanar::m_dfi
protected

The one and only DFI-NodeArray.

Definition at line 384 of file BoyerMyrvoldPlanar.h.

 EdgeArray 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.

protected

Definition at line 369 of file BoyerMyrvoldPlanar.h.

 NodeArray 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 ogdf::BoyerMyrvoldPlanar::m_highestSubtreeDFI
protected

The highest DFI in a subtree with node as root.

Definition at line 423 of file BoyerMyrvoldPlanar.h.

 NodeArray 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.

protected

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

Definition at line 392 of file BoyerMyrvoldPlanar.h.

 NodeArray ogdf::BoyerMyrvoldPlanar::m_lowPoint
protected

The lowpoint of each node.

Definition at line 420 of file BoyerMyrvoldPlanar.h.

 Array ogdf::BoyerMyrvoldPlanar::m_nodeFromDFI
protected

Returns appropriate node from given DFI.

Definition at line 387 of file BoyerMyrvoldPlanar.h.

 SListPure& ogdf::BoyerMyrvoldPlanar::m_output
protected

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

Definition at line 464 of file BoyerMyrvoldPlanar.h.

 NodeArray > 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 > 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 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 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 > 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 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 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: