ogdf::FindKuratowskis Class Reference

This class collects information about Kuratowski Subdivisions which is used for extraction later. More...

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

List of all members.

Public Member Functions
	FindKuratowskis (BoyerMyrvoldPlanar *bm)
	Constructor.
	~FindKuratowskis ()
	Destructor.
void	addKuratowskiStructure (const node currentNode, const node root, const node stopx, const node stopy)
	Adds Kuratowski Structure on current node with root root and stopping nodes stopx and stopy.
SListPure< KuratowskiStructure > &	getAllKuratowskis ()
	Get-method for the list of all KuratowskiStructures.
const SListPure < KuratowskiStructure > &	getAllKuratowskis () const
	Constant get-method for the list of all KuratowskiStructures.
FindKuratowskis &	operator= (const FindKuratowskis &)
	Assignment operator is undefined!
Protected Member Functions
const	NodeArray (&m_link)[2]
	Links to opposite adjacency entries on external face in clockwise resp. ccw order.
node	findRoot (node stopX)
	Finds root node of the bicomp containing the stopping node stopX.
void	extractHighestFacePath (ListPure< adjEntry > &highestFacePath, int marker)
	Extracts the highestFace Path of the bicomp containing both stopping nodes.
void	extractExternalFacePath (SListPure< adjEntry > &externalFacePath, const ListPure< adjEntry > &highestFacePath, int marker, int highMarker)
	Extracts externalFacePath in direction CCW and splits highestFacePath in highestXYPaths.
void	splitInMinorTypes (const SListPure< adjEntry > &externalFacePath, int marker)
	Assign pertinent nodes to the different minortypes and extracts inner externalPaths.
void	extractExternalSubgraph (const node stop, int root, SListPure< int > &externalStartnodes, SListPure< node > &externalEndnodes)
	Extracts external subgraph from node stop to ancestors of node with DFI root (without bundles).
void	extractExternalSubgraphBundles (const node stop, int root, SListPure< edge > &externalSubgraph, int nodeMarker)
	Extracts external subgraph from node stop to ancestors of node with DFI root (with bundles).
void	extractPertinentSubgraph (SListPure< WInfo > &W_All)
	Extracts pertinent subgraph from all wNodes to V (without bundles).
void	extractPertinentSubgraphBundles (const SListPure< WInfo > &W_All, const node V, SListPure< edge > &pertinentSubgraph, int nodeMarker)
	Extracts pertinent subgraph from all wNodes to V (with bundles).
Protected Attributes
BoyerMyrvoldPlanar *	pBM
	Link to class BoyerMyrvoldPlanar.
Graph &	m_g
	Input graph.
const int &	m_embeddingGrade
	The embedding grade.
const bool	m_bundles
	If true, bundles are extracted, otherwise single paths?
NodeArray< WInfo * >	m_getWInfo
	Links appropriate WInfo to node.
SListPure< KuratowskiStructure >	allKuratowskis
	List of all Kuratowski Structures.
KuratowskiStructure	k
	Current Kuratowski Structure.
int	m_nodeMarker
	Value used as marker for visited nodes etc.
NodeArray< int >	m_wasHere
	Array maintaining visited bits on each node.
const NodeArray< node > &	m_realVertex
	Link to non-virtual vertex of a virtual Vertex.
const NodeArray< int > &	m_dfi
	The one and only DFI-NodeArray.
const Array< node > &	m_nodeFromDFI
	Returns appropriate node from given DFI.
const NodeArray< adjEntry > &	m_adjParent
	The adjEntry which goes from DFS-parent to current vertex.
const 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.
const NodeArray< int > &	m_highestSubtreeDFI
	The highest DFI in a subtree with node as root.
const NodeArray< ListPure < node > > &	m_separatedDFSChildList
	A list to all separated DFS-children of node.
const EdgeArray< node > &	m_pointsToRoot
	Identifies the rootnode of the child bicomp the given backedge points to.
NodeArray< int > &	m_visitedWithBackedge
	Keeps track of all vertices that are visited by the walkup through a specific backedge.
NodeArray< SListPure< adjEntry > > &	m_backedgeFlags
	Holds information, if node is the source of a backedge.
NodeArray< SListPure< node > > &	m_pertinentRoots
	List of virtual bicomp roots, that are pertinent to the current embedded node.

---

Detailed Description

This class collects information about Kuratowski Subdivisions which is used for extraction later.

Precondition:

Graph has to be simple.

Definition at line 200 of file FindKuratowskis.h.

---

Constructor & Destructor Documentation

ogdf::FindKuratowskis::FindKuratowskis

(

BoyerMyrvoldPlanar *

bm

)

Constructor.

ogdf::FindKuratowskis::~FindKuratowskis

(

)

[inline]

Destructor.

Definition at line 205 of file FindKuratowskis.h.

---

Member Function Documentation

void ogdf::FindKuratowskis::addKuratowskiStructure	(	const node	currentNode,
		const node	root,
		const node	stopx,
		const node	stopy
	)

Adds Kuratowski Structure on current node with root root and stopping nodes stopx and stopy.

void ogdf::FindKuratowskis::extractExternalFacePath	(	SListPure< adjEntry > &	externalFacePath,
		const ListPure< adjEntry > &	highestFacePath,
		int	marker,
		int	highMarker
	)			[protected]

Extracts externalFacePath in direction CCW and splits highestFacePath in highestXYPaths.

void ogdf::FindKuratowskis::extractExternalSubgraph	(	const node	stop,
		int	root,
		SListPure< int > &	externalStartnodes,
		SListPure< node > &	externalEndnodes
	)			[protected]

Extracts external subgraph from node stop to ancestors of node with DFI root (without bundles).

void ogdf::FindKuratowskis::extractExternalSubgraphBundles	(	const node	stop,
		int	root,
		SListPure< edge > &	externalSubgraph,
		int	nodeMarker
	)			[protected]

Extracts external subgraph from node stop to ancestors of node with DFI root (with bundles).

void ogdf::FindKuratowskis::extractHighestFacePath	(	ListPure< adjEntry > &	highestFacePath,
		int	marker
	)			[protected]

Extracts the highestFace Path of the bicomp containing both stopping nodes.

void ogdf::FindKuratowskis::extractPertinentSubgraph

(

SListPure< WInfo > &

W_All

)

[protected]

Extracts pertinent subgraph from all wNodes to V (without bundles).

void ogdf::FindKuratowskis::extractPertinentSubgraphBundles	(	const SListPure< WInfo > &	W_All,
		const node	V,
		SListPure< edge > &	pertinentSubgraph,
		int	nodeMarker
	)			[protected]

Extracts pertinent subgraph from all wNodes to V (with bundles).

node ogdf::FindKuratowskis::findRoot

(

node

stopX

)

[protected]

Finds root node of the bicomp containing the stopping node stopX.

SListPure<KuratowskiStructure>& ogdf::FindKuratowskis::getAllKuratowskis

(

)

[inline]

Get-method for the list of all KuratowskiStructures.

Definition at line 215 of file FindKuratowskis.h.

const SListPure<KuratowskiStructure>& ogdf::FindKuratowskis::getAllKuratowskis

(

)

const [inline]

Constant get-method for the list of all KuratowskiStructures.

Definition at line 220 of file FindKuratowskis.h.

const ogdf::FindKuratowskis::NodeArray

(

&

m_link

)

[protected]

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

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

FindKuratowskis& ogdf::FindKuratowskis::operator=

(

const FindKuratowskis &

)

Assignment operator is undefined!

void ogdf::FindKuratowskis::splitInMinorTypes	(	const SListPure< adjEntry > &	externalFacePath,
		int	marker
	)			[protected]

Assign pertinent nodes to the different minortypes and extracts inner externalPaths.

---

Member Data Documentation

SListPure<KuratowskiStructure> ogdf::FindKuratowskis::allKuratowskis [protected]

List of all Kuratowski Structures.

Definition at line 245 of file FindKuratowskis.h.

KuratowskiStructure ogdf::FindKuratowskis::k [protected]

Current Kuratowski Structure.

Definition at line 248 of file FindKuratowskis.h.

const NodeArray<adjEntry>& ogdf::FindKuratowskis::m_adjParent [protected]

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

Definition at line 274 of file FindKuratowskis.h.

NodeArray<SListPure<adjEntry> >& ogdf::FindKuratowskis::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 314 of file FindKuratowskis.h.

const bool ogdf::FindKuratowskis::m_bundles [protected]

If true, bundles are extracted, otherwise single paths?

Definition at line 239 of file FindKuratowskis.h.

const NodeArray<int>& ogdf::FindKuratowskis::m_dfi [protected]

The one and only DFI-NodeArray.

Definition at line 263 of file FindKuratowskis.h.

EdgeArray<int>& ogdf::FindKuratowskis::m_edgeType [protected]

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 289 of file FindKuratowskis.h.

const int& ogdf::FindKuratowskis::m_embeddingGrade [protected]

The embedding grade.

Definition at line 236 of file FindKuratowskis.h.

Graph& ogdf::FindKuratowskis::m_g [protected]

Input graph.

Definition at line 233 of file FindKuratowskis.h.

NodeArray<WInfo*> ogdf::FindKuratowskis::m_getWInfo [protected]

Links appropriate WInfo to node.

Definition at line 242 of file FindKuratowskis.h.

const NodeArray<int>& ogdf::FindKuratowskis::m_highestSubtreeDFI [protected]

The highest DFI in a subtree with node as root.

Definition at line 295 of file FindKuratowskis.h.

const NodeArray<int>& ogdf::FindKuratowskis::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 279 of file FindKuratowskis.h.

NodeArray<int>& ogdf::FindKuratowskis::m_lowPoint [protected]

The lowpoint of each node.

Definition at line 292 of file FindKuratowskis.h.

const Array<node>& ogdf::FindKuratowskis::m_nodeFromDFI [protected]

Returns appropriate node from given DFI.

Definition at line 266 of file FindKuratowskis.h.

int ogdf::FindKuratowskis::m_nodeMarker [protected]

Value used as marker for visited nodes etc.

Used during computation of the external face path and the highest x-y-path

Definition at line 253 of file FindKuratowskis.h.

NodeArray<SListPure<node> >& ogdf::FindKuratowskis::m_pertinentRoots [protected]

List of virtual bicomp roots, that are pertinent to the current embedded node.

Definition at line 317 of file FindKuratowskis.h.

const EdgeArray<node>& ogdf::FindKuratowskis::m_pointsToRoot [protected]

Identifies the rootnode of the child bicomp the given backedge points to.

Definition at line 303 of file FindKuratowskis.h.

const NodeArray<node>& ogdf::FindKuratowskis::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 260 of file FindKuratowskis.h.

const NodeArray<ListPure<node> >& ogdf::FindKuratowskis::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 300 of file FindKuratowskis.h.

NodeArray<int>& ogdf::FindKuratowskis::m_visitedWithBackedge [protected]

Keeps track of all vertices that are visited by the walkup through a specific backedge.

This is done in order to refer to the unique child-bicomp of v.

Definition at line 308 of file FindKuratowskis.h.

NodeArray<int> ogdf::FindKuratowskis::m_wasHere [protected]

Array maintaining visited bits on each node.

Definition at line 255 of file FindKuratowskis.h.

BoyerMyrvoldPlanar* ogdf::FindKuratowskis::pBM [protected]

Link to class BoyerMyrvoldPlanar.

Definition at line 230 of file FindKuratowskis.h.

---

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

• ogdf/internal/planarity/FindKuratowskis.h