Open
Graph Drawing
Framework

 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

enum  EmbeddingGrade { EmbeddingGrade::doNotEmbed =-3, EmbeddingGrade::doNotFind =-2, EmbeddingGrade::doFindUnlimited =-1, EmbeddingGrade::doFindZero =0 }
 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 int m_embeddingGrade
 
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...
 
NodeArray< adjEntrym_link [2]
 Links to opposite adjacency entries on external face in clockwise resp. ccw order. More...
 
NodeArray< adjEntrym_beforeSCE [2]
 Links for short circuit edges. More...
 
NodeArray< adjEntrym_adjParent
 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

◆ EmbeddingGrade

Denotes the different embedding options.

Enumerator
doNotEmbed 
doNotFind 
doFindUnlimited 
doFindZero 

Definition at line 75 of file BoyerMyrvoldPlanar.h.

Constructor & Destructor Documentation

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

Member Function Documentation

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

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

◆ infoAboutNode()

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

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

Friends And Related Function Documentation

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

Member Data Documentation

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

◆ m_adjParent

NodeArray<adjEntry> ogdf::BoyerMyrvoldPlanar::m_adjParent
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<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 457 of file BoyerMyrvoldPlanar.h.

◆ m_beforeSCE

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

The one and only DFI-NodeArray.

Definition at line 378 of file BoyerMyrvoldPlanar.h.

◆ m_edgeCosts

const EdgeArray<int>* ogdf::BoyerMyrvoldPlanar::m_edgeCosts
protected

Definition at line 359 of file BoyerMyrvoldPlanar.h.

◆ m_edgeType

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

Contains the type of each edge.

Definition at line 404 of file BoyerMyrvoldPlanar.h.

◆ m_embeddingGrade

const int ogdf::BoyerMyrvoldPlanar::m_embeddingGrade
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<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 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<int> 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<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 401 of file BoyerMyrvoldPlanar.h.

◆ m_limitStructures

const bool ogdf::BoyerMyrvoldPlanar::m_limitStructures
protected

Definition at line 356 of file BoyerMyrvoldPlanar.h.

◆ m_link

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

◆ m_lowPoint

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

The lowpoint of each node.

Definition at line 407 of file BoyerMyrvoldPlanar.h.

◆ m_nodeFromDFI

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

Returns appropriate node from given DFI.

Definition at line 381 of file BoyerMyrvoldPlanar.h.

◆ m_numUnembeddedBackedgesInBicomp

NodeArray<int> 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<KuratowskiStructure>& 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<SListPure<node> > 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<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 nullptr.

Definition at line 420 of file BoyerMyrvoldPlanar.h.

◆ m_pointsToRoot

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

◆ m_separatedDFSChildList

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

◆ m_visited

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