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

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 52 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 58 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 100 of file BoyerMyrvoldInit.h.

◆ m_dfi

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

private

The one and only DFI-Array.

Definition at line 89 of file BoyerMyrvoldInit.h.

◆ m_edgeCosts

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

private

Definition at line 80 of file BoyerMyrvoldInit.h.

◆ m_edgeType

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

private

Contains the type of each edge.

Definition at line 108 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 78 of file BoyerMyrvoldInit.h.

◆ m_g

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

private

The input graph.

Definition at line 75 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 114 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 105 of file BoyerMyrvoldInit.h.

◆ m_lowPoint

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

private

The lowpoint of each node.

Definition at line 111 of file BoyerMyrvoldInit.h.

◆ m_nodeFromDFI

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

private

Returns appropriate node from given DFI.

Definition at line 92 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 124 of file BoyerMyrvoldInit.h.

◆ m_rand

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

private

Definition at line 81 of file BoyerMyrvoldInit.h.

◆ m_randomness

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

private

Definition at line 79 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 86 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 119 of file BoyerMyrvoldInit.h.

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

include/ogdf/planarity/boyer_myrvold/BoyerMyrvoldInit.h

OpenGraph DrawingFramework

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ BoyerMyrvoldInit()

◆ ~BoyerMyrvoldInit()

Member Function Documentation

◆ computeDFS()

◆ computeDFSChildLists()

◆ computeLowPoints()

◆ createVirtualVertex()

◆ NodeArray()

◆ operator=()

Member Data Documentation

◆ m_adjParent

◆ m_dfi

◆ m_edgeCosts

◆ m_edgeType

◆ m_embeddingGrade

◆ m_g

◆ m_highestSubtreeDFI

◆ m_leastAncestor

◆ m_lowPoint

◆ m_nodeFromDFI

◆ m_pNodeInParent

◆ m_rand

◆ m_randomness

◆ m_realVertex

◆ m_separatedDFSChildList

Open
Graph Drawing
Framework