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. More... | |
~BoyerMyrvoldInit () | |
Destructor. More... | |
void | computeDFS () |
Creates the DFSTree. More... | |
void | computeDFSChildLists () |
Computes the list of separated DFS children for all nodes. More... | |
void | computeLowPoints () |
Computes lowpoint, highestSubtreeDFI and links virtual to nonvirtual vertices. More... | |
BoyerMyrvoldInit & | operator= (const BoyerMyrvoldInit &) |
Assignment operator is undefined! More... | |
Private Member Functions | |
void | createVirtualVertex (const adjEntry father) |
Creates and links a virtual vertex of the node belonging to father . More... | |
NodeArray (&m_link)[2] | |
Links to opposite adjacency entries on external face in clockwise resp. ccw order. More... | |
Private Attributes | |
NodeArray< adjEntry > & | m_adjParent |
The adjEntry which goes from DFS-parent to current vertex. More... | |
NodeArray< int > & | m_dfi |
The one and only DFI-Array. More... | |
const EdgeArray< int > * | m_edgeCosts |
EdgeArray< BoyerMyrvoldEdgeType > & | m_edgeType |
Contains the type of each edge. More... | |
const int & | m_embeddingGrade |
Some parameters... see BoyerMyrvold.h for further instructions. More... | |
Graph & | m_g |
The input graph. More... | |
NodeArray< int > & | m_highestSubtreeDFI |
The highest DFI in a subtree with node as root. More... | |
NodeArray< int > & | m_leastAncestor |
The DFI of the least ancestor node over all backedges. More... | |
NodeArray< int > & | m_lowPoint |
The lowpoint of each node. More... | |
Array< node > & | m_nodeFromDFI |
Returns appropriate node from given DFI. More... | |
NodeArray< ListIterator< node > > & | m_pNodeInParent |
Pointer to node contained in the DFSChildList of his parent, if exists. More... | |
std::minstd_rand | m_rand |
const double & | m_randomness |
NodeArray< node > & | m_realVertex |
Link to non-virtual vertex of a virtual Vertex. More... | |
NodeArray< ListPure< node > > & | m_separatedDFSChildList |
A list to all separated DFS-children of node. More... | |
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.
|
explicit |
Constructor, the parameter BoyerMyrvoldPlanar is needed.
|
inline |
Destructor.
Definition at line 55 of file BoyerMyrvoldInit.h.
void ogdf::boyer_myrvold::BoyerMyrvoldInit::computeDFS | ( | ) |
Creates the DFSTree.
void ogdf::boyer_myrvold::BoyerMyrvoldInit::computeDFSChildLists | ( | ) |
Computes the list of separated DFS children for all nodes.
void ogdf::boyer_myrvold::BoyerMyrvoldInit::computeLowPoints | ( | ) |
Computes lowpoint, highestSubtreeDFI and links virtual to nonvirtual vertices.
|
private |
Creates and links a virtual vertex of the node belonging to father
.
|
private |
Links to opposite adjacency entries on external face in clockwise resp. ccw order.
m_link[0]=CCW, m_link[1]=CW
BoyerMyrvoldInit& ogdf::boyer_myrvold::BoyerMyrvoldInit::operator= | ( | const BoyerMyrvoldInit & | ) |
Assignment operator is undefined!
The adjEntry which goes from DFS-parent to current vertex.
Definition at line 97 of file BoyerMyrvoldInit.h.
|
private |
The one and only DFI-Array.
Definition at line 86 of file BoyerMyrvoldInit.h.
|
private |
Definition at line 77 of file BoyerMyrvoldInit.h.
|
private |
Contains the type of each edge.
Definition at line 105 of file BoyerMyrvoldInit.h.
|
private |
Some parameters... see BoyerMyrvold.h for further instructions.
Definition at line 75 of file BoyerMyrvoldInit.h.
|
private |
The input graph.
Definition at line 72 of file BoyerMyrvoldInit.h.
|
private |
The highest DFI in a subtree with node as root.
Definition at line 111 of file BoyerMyrvoldInit.h.
|
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.
|
private |
The lowpoint of each node.
Definition at line 108 of file BoyerMyrvoldInit.h.
Returns appropriate node from given DFI.
Definition at line 89 of file BoyerMyrvoldInit.h.
|
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.
|
private |
Definition at line 78 of file BoyerMyrvoldInit.h.
|
private |
Definition at line 76 of file BoyerMyrvoldInit.h.
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.
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.