OpenGraph DrawingFramework

v. 2022.02 (Dogwood)

ogdf::BoyerMyrvoldPlanar Class Reference

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

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

Public Types

Denotes the different embedding options. More...

Public Member Functions

BoyerMyrvoldPlanar (Graph &g, bool bundles, EmbeddingGrade embeddingGrade, bool limitStructures, SListPure< KuratowskiStructure > &output, double randomness, bool avoidE2Minors, bool extractSubgraph, const EdgeArray< int > *edgeCosts=nullptr)
Constructor, for parameters see BoyerMyrvold. More...

BoyerMyrvoldPlanar (Graph &g, bool bundles, int embeddingGrade, bool limitStructures, SListPure< KuratowskiStructure > &output, double randomness, bool avoidE2Minors, bool extractSubgraph, const EdgeArray< int > *edgeCosts=nullptr)
Constructor, for parameters see BoyerMyrvold. More...

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

BoyerMyrvoldPlanaroperator= (const BoyerMyrvoldPlanar &)
Assignment operator is undefined! More...

void seed (const std::minstd_rand rand)
Seeds the random generator for performing a random DFS. If this method is never called the random generator will be seeded by a value extracted from the global random generator. More...

bool start ()
Starts the embedding algorithm. More...

Static Public Attributes

const static int DirectionCCW
Direction for counterclockwise traversal. More...

const static int DirectionCW
Direction for clockwise traversal. More...

Protected Member Functions

Methods for Walkup and Walkdown
bool pertinent (node w) const
Checks whether node w is pertinent. w has to be non-virtual. More...

bool internallyActive (node w, int v) const
Checks whether real node w is internally active while embedding node with DFI v. More...

bool externallyActive (node w, int v) const
Checks whether real node w is externally active while embedding node with DFI v. More...

bool inactive (node w, int v)
Checks whether real node w is inactive while embedding node with DFI v. More...

int infoAboutNode (node w, int v) const
Checks all dynamic information about a node w while embedding node with DFI v. More...

node successorOnExternalFace (node w, int &direction) const
Walks upon external face in the given direction starting at w. More...

node successorWithoutShortCircuit (node w, int &direction)
Walks upon external face in given direction avoiding short circuit edges. More...

node constSuccessorOnExternalFace (node v, int direction)
Returns the successornode on the external face in given direction. More...

node constSuccessorWithoutShortCircuit (node v, int direction) const
Walks upon external face in direction avoiding short circuit edges. More...

adjEntry beforeShortCircuitEdge (node v, int direction) const
Returns underlying former adjEntry, if a short circuit edge in direction of v exists. More...

node activeSuccessor (node w, int &direction, int v, int &info) const
Walks upon external face in the given direction starting at w until an active vertex is reached. More...

node constActiveSuccessor (node w, int direction, int v, int &info) const
Walks upon external face in the given direction (without changing it) until an active vertex is reached. More...

bool wNodesExist (node root, node stopx, node stopy) const
Checks, if one ore more wNodes exist between the two stopping vertices stopx and stopy. More...

void printNodeInfo (node v)
Prints informations about node v. More...

void mergeBiconnectedComponent (ArrayBuffer< int > &stack)
Merges the last two biconnected components saved in stack. Embeds them iff m_embeddingGrade != EmbeddingGrade::doNotEmbed. More...

void embedBackedges (const node v, const int v_dir, const node w, const int w_dir)
Links (and embeds iff m_embeddingGrade != EmbeddingGrade::doNotEmbed) backedges from node v with direction v_dir to node w with direction w_dir. More...

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

node walkup (const node v, const node w, const int marker, const edge back)
Walkup: Builds the pertinent subgraph for the backedge back. More...

int walkdown (const int i, const node v, FindKuratowskis *findKuratowskis)
Walkdown: Embeds all backedges with DFI i as targetnode to node v. More...

void mergeUnprocessedNodes ()
Merges unprocessed virtual nodes such as the dfs-roots with their real counterpart. More...

void postProcessEmbedding ()
Postprocessing of the graph, so that all virtual vertices are embedded and all bicomps are flipped. More...

bool embed ()
Starts the embedding phase, which embeds m_g node by node in descending DFI-order. More...

Protected Attributes

bool m_extractSubgraph = true
Flag for extracting a planar subgraph instead of testing for planarity. More...

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

Graphm_g
Input graph, which can be altered. More...

Some parameters... see BoyerMyrvold for further options
const bool m_bundles

const bool m_limitStructures

const double m_randomness

const bool m_avoidE2Minors

const EdgeArray< int > * m_edgeCosts

std::minstd_rand m_rand

Members from BoyerMyrvoldInit
NodeArray< nodem_realVertex
Link to non-virtual vertex of a virtual Vertex. More...

NodeArray< int > m_dfi
The one and only DFI-NodeArray. More...

Array< nodem_nodeFromDFI
Returns appropriate node from given DFI. More...

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

Links for short circuit edges. More...

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

NodeArray< int > m_leastAncestor
The DFI of the least ancestor node over all backedges. More...

EdgeArray< BoyerMyrvoldEdgeTypem_edgeType
Contains the type of each edge. More...

NodeArray< int > m_lowPoint
The lowpoint of each node. More...

NodeArray< int > m_highestSubtreeDFI
The highest DFI in a subtree with node as root. More...

NodeArray< ListPure< node > > m_separatedDFSChildList
A list to all separated DFS-children of node. More...

NodeArray< ListIterator< node > > m_pNodeInParent
Pointer to node contained in the DFSChildList of his parent, if exists. More...

Members for Walkup and Walkdown
NodeArray< int > m_visited
This Array keeps track of all vertices that are visited by current walkup. More...

EdgeArray< nodem_pointsToRoot
Identifies the rootnode of the child bicomp the given backedge points to. More...

NodeArray< edgem_visitedWithBackedge
Stores for each (real) non-root vertex v with which backedge it was visited during the walkup. More...

NodeArray< int > m_numUnembeddedBackedgesInBicomp
Stores for each (virtual) bicomp root how many backedges to its bicomp still have to be embedded. More...

NodeArray< bool > m_flipped
Iff true, the node is the root of a bicomp which has to be flipped. More...

NodeArray< SListPure< adjEntry > > m_backedgeFlags
Holds information, if node is the source of a backedge. More...

NodeArray< SListPure< node > > m_pertinentRoots
List of virtual bicomp roots, that are pertinent to the current embedded node. More...

SListPure< KuratowskiStructure > & m_output
Data structure for the Kuratowski subdivisions, which will be returned. More...

Friends

class boyer_myrvold::BoyerMyrvoldInit

class BoyerMyrvold

class ExtractKuratowskis

class FindKuratowskis

Detailed Description

This class implements the extended BoyerMyrvold planarity embedding algorithm.

Definition at line 60 of file BoyerMyrvoldPlanar.h.

Member Enumeration Documentation

 strong

Denotes the different embedding options.

Enumerator
doNotEmbed
doNotFind
doFindUnlimited
doFindZero

Definition at line 75 of file BoyerMyrvoldPlanar.h.

◆ BoyerMyrvoldPlanar() [1/2]

 ogdf::BoyerMyrvoldPlanar::BoyerMyrvoldPlanar ( Graph & g, bool bundles, int embeddingGrade, bool limitStructures, SListPure< KuratowskiStructure > & output, double randomness, bool avoidE2Minors, bool extractSubgraph, const EdgeArray< int > * edgeCosts = nullptr )

Constructor, for parameters see BoyerMyrvold.

◆ BoyerMyrvoldPlanar() [2/2]

 ogdf::BoyerMyrvoldPlanar::BoyerMyrvoldPlanar ( Graph & g, bool bundles, EmbeddingGrade embeddingGrade, bool limitStructures, SListPure< KuratowskiStructure > & output, double randomness, bool avoidE2Minors, bool extractSubgraph, const EdgeArray< int > * edgeCosts = nullptr )
inline

Constructor, for parameters see BoyerMyrvold.

Definition at line 95 of file BoyerMyrvoldPlanar.h.

◆ activeSuccessor()

 node ogdf::BoyerMyrvoldPlanar::activeSuccessor ( node w, int & direction, int v, int & info ) const
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.

◆ beforeShortCircuitEdge()

 adjEntry ogdf::BoyerMyrvoldPlanar::beforeShortCircuitEdge ( node v, int direction ) const
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 251 of file BoyerMyrvoldPlanar.h.

◆ constActiveSuccessor()

 node ogdf::BoyerMyrvoldPlanar::constActiveSuccessor ( node w, int direction, int v, int & info ) const
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 264 of file BoyerMyrvoldPlanar.h.

◆ constSuccessorOnExternalFace()

 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 232 of file BoyerMyrvoldPlanar.h.

◆ constSuccessorWithoutShortCircuit()

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

Walks upon external face in direction avoiding short circuit edges.

direction is not changed.

Definition at line 241 of file BoyerMyrvoldPlanar.h.

◆ createShortCircuitEdge()

 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.

◆ embed()

 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.

◆ embedBackedges()

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

Links (and embeds iff m_embeddingGrade != EmbeddingGrade::doNotEmbed) backedges from node v with direction v_dir to node w with direction w_dir.

◆ externallyActive()

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

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

Definition at line 154 of file BoyerMyrvoldPlanar.h.

◆ flipBicomp()

 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

◆ inactive()

 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 162 of file BoyerMyrvoldPlanar.h.

 int ogdf::BoyerMyrvoldPlanar::infoAboutNode ( node w, int v ) const
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 178 of file BoyerMyrvoldPlanar.h.

◆ internallyActive()

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

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

Definition at line 148 of file BoyerMyrvoldPlanar.h.

◆ mergeBiconnectedComponent()

 void ogdf::BoyerMyrvoldPlanar::mergeBiconnectedComponent ( ArrayBuffer< int > & stack )
protected

Merges the last two biconnected components saved in stack. Embeds them iff m_embeddingGrade != EmbeddingGrade::doNotEmbed.

◆ mergeUnprocessedNodes()

 void ogdf::BoyerMyrvoldPlanar::mergeUnprocessedNodes ( )
protected

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

◆ operator=()

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

Assignment operator is undefined!

◆ pertinent()

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

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

Definition at line 142 of file BoyerMyrvoldPlanar.h.

◆ postProcessEmbedding()

 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.

◆ printNodeInfo()

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

Prints informations about node v.

Definition at line 293 of file BoyerMyrvoldPlanar.h.

◆ seed()

 void ogdf::BoyerMyrvoldPlanar::seed ( const std::minstd_rand rand )
inline

Seeds the random generator for performing a random DFS. If this method is never called the random generator will be seeded by a value extracted from the global random generator.

Definition at line 133 of file BoyerMyrvoldPlanar.h.

◆ start()

 bool ogdf::BoyerMyrvoldPlanar::start ( )

Starts the embedding algorithm.

◆ successorOnExternalFace()

 node ogdf::BoyerMyrvoldPlanar::successorOnExternalFace ( node w, int & direction ) const
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 200 of file BoyerMyrvoldPlanar.h.

◆ successorWithoutShortCircuit()

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

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

Definition at line 215 of file BoyerMyrvoldPlanar.h.

◆ walkdown()

 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

◆ walkup()

 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.

◆ wNodesExist()

 bool ogdf::BoyerMyrvoldPlanar::wNodesExist ( node root, node stopx, node stopy ) const
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 271 of file BoyerMyrvoldPlanar.h.

◆ boyer_myrvold::BoyerMyrvoldInit

 friend class boyer_myrvold::BoyerMyrvoldInit
friend

Definition at line 63 of file BoyerMyrvoldPlanar.h.

◆ BoyerMyrvold

 friend class BoyerMyrvold
friend

Definition at line 62 of file BoyerMyrvoldPlanar.h.

◆ ExtractKuratowskis

 friend class ExtractKuratowskis
friend

Definition at line 65 of file BoyerMyrvoldPlanar.h.

◆ FindKuratowskis

 friend class FindKuratowskis
friend

Definition at line 64 of file BoyerMyrvoldPlanar.h.

◆ DirectionCCW

 const static int ogdf::BoyerMyrvoldPlanar::DirectionCCW
static

Direction for counterclockwise traversal.

Definition at line 69 of file BoyerMyrvoldPlanar.h.

◆ DirectionCW

 const static int ogdf::BoyerMyrvoldPlanar::DirectionCW
static

Direction for clockwise traversal.

Definition at line 72 of file BoyerMyrvoldPlanar.h.

protected

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

Definition at line 396 of file BoyerMyrvoldPlanar.h.

◆ m_avoidE2Minors

 const bool ogdf::BoyerMyrvoldPlanar::m_avoidE2Minors
protected

Definition at line 358 of file BoyerMyrvoldPlanar.h.

◆ m_backedgeFlags

 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 457 of file BoyerMyrvoldPlanar.h.

◆ m_beforeSCE

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

Definition at line 393 of file BoyerMyrvoldPlanar.h.

◆ m_bundles

 const bool ogdf::BoyerMyrvoldPlanar::m_bundles
protected

Definition at line 354 of file BoyerMyrvoldPlanar.h.

◆ m_dfi

 NodeArray ogdf::BoyerMyrvoldPlanar::m_dfi
protected

The one and only DFI-NodeArray.

Definition at line 378 of file BoyerMyrvoldPlanar.h.

◆ m_edgeCosts

 const EdgeArray* ogdf::BoyerMyrvoldPlanar::m_edgeCosts
protected

Definition at line 359 of file BoyerMyrvoldPlanar.h.

◆ m_edgeType

 EdgeArray ogdf::BoyerMyrvoldPlanar::m_edgeType
protected

Contains the type of each edge.

Definition at line 404 of file BoyerMyrvoldPlanar.h.

protected

Definition at line 355 of file BoyerMyrvoldPlanar.h.

◆ m_extractSubgraph

 bool ogdf::BoyerMyrvoldPlanar::m_extractSubgraph = true
protected

Flag for extracting a planar subgraph instead of testing for planarity.

Definition at line 364 of file BoyerMyrvoldPlanar.h.

◆ m_flipped

 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 451 of file BoyerMyrvoldPlanar.h.

◆ m_flippedNodes

 int ogdf::BoyerMyrvoldPlanar::m_flippedNodes
protected

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

Definition at line 367 of file BoyerMyrvoldPlanar.h.

◆ m_g

 Graph& ogdf::BoyerMyrvoldPlanar::m_g
protected

Input graph, which can be altered.

Definition at line 350 of file BoyerMyrvoldPlanar.h.

◆ m_highestSubtreeDFI

 NodeArray ogdf::BoyerMyrvoldPlanar::m_highestSubtreeDFI
protected

The highest DFI in a subtree with node as root.

Definition at line 410 of file BoyerMyrvoldPlanar.h.

◆ m_leastAncestor

 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 401 of file BoyerMyrvoldPlanar.h.

◆ m_limitStructures

 const bool ogdf::BoyerMyrvoldPlanar::m_limitStructures
protected

Definition at line 356 of file BoyerMyrvoldPlanar.h.

protected

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

Definition at line 386 of file BoyerMyrvoldPlanar.h.

◆ m_lowPoint

 NodeArray ogdf::BoyerMyrvoldPlanar::m_lowPoint
protected

The lowpoint of each node.

Definition at line 407 of file BoyerMyrvoldPlanar.h.

◆ m_nodeFromDFI

 Array ogdf::BoyerMyrvoldPlanar::m_nodeFromDFI
protected

Returns appropriate node from given DFI.

Definition at line 381 of file BoyerMyrvoldPlanar.h.

◆ m_numUnembeddedBackedgesInBicomp

 NodeArray ogdf::BoyerMyrvoldPlanar::m_numUnembeddedBackedgesInBicomp
protected

Stores for each (virtual) bicomp root how many backedges to its bicomp still have to be embedded.

The value is set during the walkup, and it is used and decreased while embedding backedges during the walkdown.

Definition at line 444 of file BoyerMyrvoldPlanar.h.

◆ m_output

 SListPure& ogdf::BoyerMyrvoldPlanar::m_output
protected

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

Definition at line 463 of file BoyerMyrvoldPlanar.h.

◆ m_pertinentRoots

 NodeArray > ogdf::BoyerMyrvoldPlanar::m_pertinentRoots
protected

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

Definition at line 460 of file BoyerMyrvoldPlanar.h.

◆ m_pNodeInParent

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

Definition at line 420 of file BoyerMyrvoldPlanar.h.

◆ m_pointsToRoot

 EdgeArray ogdf::BoyerMyrvoldPlanar::m_pointsToRoot
protected

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

Definition at line 430 of file BoyerMyrvoldPlanar.h.

◆ m_rand

 std::minstd_rand ogdf::BoyerMyrvoldPlanar::m_rand
protected

Definition at line 360 of file BoyerMyrvoldPlanar.h.

◆ m_randomness

 const double ogdf::BoyerMyrvoldPlanar::m_randomness
protected

Definition at line 357 of file BoyerMyrvoldPlanar.h.

◆ m_realVertex

 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 375 of file BoyerMyrvoldPlanar.h.

◆ m_separatedDFSChildList

 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 415 of file BoyerMyrvoldPlanar.h.

◆ m_visited

 NodeArray ogdf::BoyerMyrvoldPlanar::m_visited
protected

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

Definition at line 427 of file BoyerMyrvoldPlanar.h.

◆ m_visitedWithBackedge

 NodeArray ogdf::BoyerMyrvoldPlanar::m_visitedWithBackedge
protected

Stores for each (real) non-root vertex v with which backedge it was visited during the walkup.

This is done to later identify the root vertex of the bicomp v belongs to.

Definition at line 437 of file BoyerMyrvoldPlanar.h.

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