Open
Graph Drawing
Framework

  v. 2023.09 (Elderberry)
 
Overview Class Hierarchy Class Index Class List Members Namespaces Source Files
 

Loading...
Searching...
No Matches
Public Member Functions | Private Member Functions | Private Attributes | List of all members
ogdf::boyer_myrvold::BoyerMyrvoldInit Class Reference

This class is used in the Boyer-Myrvold planarity test for preprocessing purposes. More...

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

Public Member Functions

 BoyerMyrvoldInit (BoyerMyrvoldPlanar *pBM)
 Constructor, the parameter BoyerMyrvoldPlanar is needed.
 
 ~BoyerMyrvoldInit ()
 Destructor.
 
void computeDFS ()
 Creates the DFSTree.
 
void computeDFSChildLists ()
 Computes the list of separated DFS children for all nodes.
 
void computeLowPoints ()
 Computes lowpoint, highestSubtreeDFI and links virtual to nonvirtual vertices.
 
BoyerMyrvoldInit & operator= (const BoyerMyrvoldInit &)
 Assignment operator is undefined!
 

Private Member Functions

void createVirtualVertex (const adjEntry father)
 Creates and links a virtual vertex of the node belonging to father.
 
 NodeArray (&m_link)[2]
 Links to opposite adjacency entries on external face in clockwise resp. ccw order.
 

Private Attributes

NodeArray< adjEntry > & m_adjParent
 The adjEntry which goes from DFS-parent to current vertex.
 
NodeArray< int > & m_dfi
 The one and only DFI-Array.
 
const EdgeArray< int > * m_edgeCosts
 
EdgeArray< BoyerMyrvoldEdgeType > & m_edgeType
 Contains the type of each edge.
 
const int & m_embeddingGrade
 Some parameters... see BoyerMyrvold.h for further instructions.
 
Graph & m_g
 The input graph.
 
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.
 
NodeArray< int > & m_lowPoint
 The lowpoint of each node.
 
Array< node > & m_nodeFromDFI
 Returns appropriate node from given DFI.
 
NodeArray< ListIterator< node > > & m_pNodeInParent
 Pointer to node contained in the DFSChildList of his parent, if exists.
 
std::minstd_rand m_rand
 
const double & m_randomness
 
NodeArray< node > & m_realVertex
 Link to non-virtual vertex of a virtual Vertex.
 
NodeArray< ListPure< node > > & m_separatedDFSChildList
 A list to all separated DFS-children of node.
 

Detailed Description

This class is used in the Boyer-Myrvold planarity test for preprocessing purposes.

Among these is the computation of lowpoints, highestSubtreeDFIs, separatedDFSChildList and of course building the DFS-tree.

Definition at line 49 of file BoyerMyrvoldInit.h.

Constructor & Destructor Documentation

◆ BoyerMyrvoldInit()

ogdf::boyer_myrvold::BoyerMyrvoldInit::BoyerMyrvoldInit ( BoyerMyrvoldPlanar *  pBM)
explicit

Constructor, the parameter BoyerMyrvoldPlanar is needed.

◆ ~BoyerMyrvoldInit()

ogdf::boyer_myrvold::BoyerMyrvoldInit::~BoyerMyrvoldInit ( )
inline

Destructor.

Definition at line 55 of file BoyerMyrvoldInit.h.

Member Function Documentation

◆ computeDFS()

void ogdf::boyer_myrvold::BoyerMyrvoldInit::computeDFS ( )

Creates the DFSTree.

◆ computeDFSChildLists()

void ogdf::boyer_myrvold::BoyerMyrvoldInit::computeDFSChildLists ( )

Computes the list of separated DFS children for all nodes.

◆ computeLowPoints()

void ogdf::boyer_myrvold::BoyerMyrvoldInit::computeLowPoints ( )

Computes lowpoint, highestSubtreeDFI and links virtual to nonvirtual vertices.

◆ createVirtualVertex()

void ogdf::boyer_myrvold::BoyerMyrvoldInit::createVirtualVertex ( const adjEntry  father)
private

Creates and links a virtual vertex of the node belonging to father.

◆ NodeArray()

ogdf::boyer_myrvold::BoyerMyrvoldInit::NodeArray ( &  m_link)
private

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

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

◆ operator=()

BoyerMyrvoldInit & ogdf::boyer_myrvold::BoyerMyrvoldInit::operator= ( const BoyerMyrvoldInit &  )

Assignment operator is undefined!

Member Data Documentation

◆ m_adjParent

NodeArray<adjEntry>& ogdf::boyer_myrvold::BoyerMyrvoldInit::m_adjParent
private

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

Definition at line 97 of file BoyerMyrvoldInit.h.

◆ m_dfi

NodeArray<int>& ogdf::boyer_myrvold::BoyerMyrvoldInit::m_dfi
private

The one and only DFI-Array.

Definition at line 86 of file BoyerMyrvoldInit.h.

◆ m_edgeCosts

const EdgeArray<int>* ogdf::boyer_myrvold::BoyerMyrvoldInit::m_edgeCosts
private

Definition at line 77 of file BoyerMyrvoldInit.h.

◆ m_edgeType

EdgeArray<BoyerMyrvoldEdgeType>& ogdf::boyer_myrvold::BoyerMyrvoldInit::m_edgeType
private

Contains the type of each edge.

Definition at line 105 of file BoyerMyrvoldInit.h.

◆ m_embeddingGrade

const int& ogdf::boyer_myrvold::BoyerMyrvoldInit::m_embeddingGrade
private

Some parameters... see BoyerMyrvold.h for further instructions.

Definition at line 75 of file BoyerMyrvoldInit.h.

◆ m_g

Graph& ogdf::boyer_myrvold::BoyerMyrvoldInit::m_g
private

The input graph.

Definition at line 72 of file BoyerMyrvoldInit.h.

◆ m_highestSubtreeDFI

NodeArray<int>& ogdf::boyer_myrvold::BoyerMyrvoldInit::m_highestSubtreeDFI
private

The highest DFI in a subtree with node as root.

Definition at line 111 of file BoyerMyrvoldInit.h.

◆ m_leastAncestor

NodeArray<int>& ogdf::boyer_myrvold::BoyerMyrvoldInit::m_leastAncestor
private

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 102 of file BoyerMyrvoldInit.h.

◆ m_lowPoint

NodeArray<int>& ogdf::boyer_myrvold::BoyerMyrvoldInit::m_lowPoint
private

The lowpoint of each node.

Definition at line 108 of file BoyerMyrvoldInit.h.

◆ m_nodeFromDFI

Array<node>& ogdf::boyer_myrvold::BoyerMyrvoldInit::m_nodeFromDFI
private

Returns appropriate node from given DFI.

Definition at line 89 of file BoyerMyrvoldInit.h.

◆ m_pNodeInParent

NodeArray<ListIterator<node> >& ogdf::boyer_myrvold::BoyerMyrvoldInit::m_pNodeInParent
private

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 121 of file BoyerMyrvoldInit.h.

◆ m_rand

std::minstd_rand ogdf::boyer_myrvold::BoyerMyrvoldInit::m_rand
private

Definition at line 78 of file BoyerMyrvoldInit.h.

◆ m_randomness

const double& ogdf::boyer_myrvold::BoyerMyrvoldInit::m_randomness
private

Definition at line 76 of file BoyerMyrvoldInit.h.

◆ m_realVertex

NodeArray<node>& ogdf::boyer_myrvold::BoyerMyrvoldInit::m_realVertex
private

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 83 of file BoyerMyrvoldInit.h.

◆ m_separatedDFSChildList

NodeArray<ListPure<node> >& ogdf::boyer_myrvold::BoyerMyrvoldInit::m_separatedDFSChildList
private

A list to all separated DFS-children of node.

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

Definition at line 116 of file BoyerMyrvoldInit.h.

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