ogdf::BoyerMyrvoldInit Class Reference

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

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

List of all members.

Public Member Functions
	BoyerMyrvoldInit (BoyerMyrvoldPlanar *pBM)
	Constructor, the parameter BoyerMyrvoldPlanar is needed.
	~BoyerMyrvoldInit ()
	Destructor.
void	computeDFS ()
	Creates the DFSTree.
void	computeLowPoints ()
	Computes lowpoint, highestSubtreeDFI and links virtual to nonvirtual vertices.
void	computeDFSChildLists ()
	Computes the list of separated DFS children for all nodes.
BoyerMyrvoldInit &	operator= (const BoyerMyrvoldInit &)
	Assignment operator is undefined!
Private Member Functions
	NodeArray (&m_link)[2]
	Links to opposite adjacency entries on external face in clockwise resp. ccw order.
void	createVirtualVertex (const adjEntry father)
	Creates and links a virtual vertex of the node belonging to father.
Private Attributes
Graph &	m_g
	The input graph.
const int &	m_embeddingGrade
	Some parameters... see BoyerMyrvold.h for further instructions.
const bool &	m_randomDFSTree
NodeArray< node > &	m_realVertex
	Link to non-virtual vertex of a virtual Vertex.
NodeArray< int > &	m_dfi
	The one and only DFI-Array.
Array< node > &	m_nodeFromDFI
	Returns appropriate node from given DFI.
NodeArray< adjEntry > &	m_adjParent
	The adjEntry which goes from DFS-parent to current vertex.
NodeArray< int > &	m_leastAncestor
	The DFI of the least ancestor node over all backedges.
EdgeArray< int > &	m_edgeType
	Contains the type of each edge.
NodeArray< int > &	m_lowPoint
	The lowpoint of each node.
NodeArray< int > &	m_highestSubtreeDFI
	The highest DFI in a subtree with node as root.
NodeArray< ListPure< node > > &	m_separatedDFSChildList
	A list to all separated DFS-children of node.
NodeArray< ListIterator< node > > &	m_pNodeInParent
	Pointer to node contained in the DFSChildList of his parent, if exists.

---

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

---

Constructor & Destructor Documentation

ogdf::BoyerMyrvoldInit::BoyerMyrvoldInit

(

BoyerMyrvoldPlanar *

pBM

)

Constructor, the parameter BoyerMyrvoldPlanar is needed.

ogdf::BoyerMyrvoldInit::~BoyerMyrvoldInit

(

)

[inline]

Destructor.

Definition at line 78 of file BoyerMyrvoldInit.h.

---

Member Function Documentation

void ogdf::BoyerMyrvoldInit::computeDFS

(

)

Creates the DFSTree.

void ogdf::BoyerMyrvoldInit::computeDFSChildLists

(

)

Computes the list of separated DFS children for all nodes.

void ogdf::BoyerMyrvoldInit::computeLowPoints

(

)

Computes lowpoint, highestSubtreeDFI and links virtual to nonvirtual vertices.

void ogdf::BoyerMyrvoldInit::createVirtualVertex

(

const adjEntry

father

)

[private]

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

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

BoyerMyrvoldInit& ogdf::BoyerMyrvoldInit::operator=

(

const BoyerMyrvoldInit &

)

Assignment operator is undefined!

---

Member Data Documentation

NodeArray<adjEntry>& ogdf::BoyerMyrvoldInit::m_adjParent [private]

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

Definition at line 118 of file BoyerMyrvoldInit.h.

NodeArray<int>& ogdf::BoyerMyrvoldInit::m_dfi [private]

The one and only DFI-Array.

Definition at line 107 of file BoyerMyrvoldInit.h.

EdgeArray<int>& ogdf::BoyerMyrvoldInit::m_edgeType [private]

Contains the type of each edge.

Parameters:

	0	= EDGE_UNDEFINED
	1	= EDGE_SELFLOOP
	2	= EDGE_BACK
	3	= EDGE_DFS
	4	= EDGE_DFS_PARALLEL
	5	= EDGE_BACK_DELETED

Definition at line 133 of file BoyerMyrvoldInit.h.

const int& ogdf::BoyerMyrvoldInit::m_embeddingGrade [private]

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

Definition at line 98 of file BoyerMyrvoldInit.h.

Graph& ogdf::BoyerMyrvoldInit::m_g [private]

The input graph.

Definition at line 95 of file BoyerMyrvoldInit.h.

NodeArray<int>& ogdf::BoyerMyrvoldInit::m_highestSubtreeDFI [private]

The highest DFI in a subtree with node as root.

Definition at line 139 of file BoyerMyrvoldInit.h.

NodeArray<int>& ogdf::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 123 of file BoyerMyrvoldInit.h.

NodeArray<int>& ogdf::BoyerMyrvoldInit::m_lowPoint [private]

The lowpoint of each node.

Definition at line 136 of file BoyerMyrvoldInit.h.

Array<node>& ogdf::BoyerMyrvoldInit::m_nodeFromDFI [private]

Returns appropriate node from given DFI.

Definition at line 110 of file BoyerMyrvoldInit.h.

NodeArray<ListIterator<node> >& ogdf::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 NULL.

Definition at line 149 of file BoyerMyrvoldInit.h.

const bool& ogdf::BoyerMyrvoldInit::m_randomDFSTree [private]

Definition at line 99 of file BoyerMyrvoldInit.h.

NodeArray<node>& ogdf::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 104 of file BoyerMyrvoldInit.h.

NodeArray<ListPure<node> >& ogdf::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 144 of file BoyerMyrvoldInit.h.

---

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

• ogdf/internal/planarity/BoyerMyrvoldInit.h