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

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

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 &)=delete

Protected Member Functions
void	extractExternalFacePath (SListPure< adjEntry > &externalFacePath, const ArrayBuffer< adjEntry > &highestFacePath, int marker, int highMarker)
	Extracts externalFacePath in direction CCW and splits highestFacePath in highestXYPaths.

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	extractHighestFacePath (ArrayBuffer< adjEntry > &highestFacePath, int marker)
	Extracts the highestFace Path of the bicomp containing both stopping nodes.

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)

node	findRoot (node stopX) const
	Finds root node of the bicomp containing the stopping node `stopX`.

const	NodeArray (&m_link)[2]
	Links to opposite adjacency entries on external face in clockwise resp. ccw order.

void	splitInMinorTypes (const SListPure< adjEntry > &externalFacePath, int marker)
	Assign pertinent nodes to the different minortypes and extracts inner externalPaths.

Protected Attributes
SListPure< KuratowskiStructure >	allKuratowskis
	List of all Kuratowski Structures.

KuratowskiStructure	k
	Current Kuratowski Structure.

const NodeArray< adjEntry > &	m_adjParent
	The adjEntry which goes from DFS-parent to current vertex.

NodeArray< SListPure< adjEntry > > &	m_backedgeFlags
	Holds information, if node is the source of a backedge.

const bool	m_bundles
	If true, bundles are extracted, otherwise single paths?

const NodeArray< int > &	m_dfi
	The one and only DFI-NodeArray.

EdgeArray< BoyerMyrvoldEdgeType > &	m_edgeType
	Contains the type of each edge.

const int &	m_embeddingGrade
	The embedding grade.

Graph &	m_g
	Input graph.

NodeArray< WInfo * >	m_getWInfo
	Links appropriate WInfo to node.

const NodeArray< int > &	m_highestSubtreeDFI
	The highest DFI in a subtree with node as root.

const NodeArray< int > &	m_leastAncestor
	The DFI of the least ancestor node over all backedges.

NodeArray< int > &	m_lowPoint
	The lowpoint of each node.

const Array< node > &	m_nodeFromDFI
	Returns appropriate node from given DFI.

int	m_nodeMarker
	Value used as marker for visited nodes etc.

NodeArray< int > &	m_numUnembeddedBackedgesInBicomp
	Stores for each (virtual) bicomp root how many backedges to its bicomp still have to be embedded.

NodeArray< SListPure< node > > &	m_pertinentRoots
	List of virtual bicomp roots, that are pertinent to the current embedded node.

const EdgeArray< node > &	m_pointsToRoot
	Identifies the rootnode of the child bicomp the given backedge points to.

const NodeArray< node > &	m_realVertex
	Link to non-virtual vertex of a virtual Vertex.

const NodeArray< ListPure< node > > &	m_separatedDFSChildList
	A list to all separated DFS-children of node.

NodeArray< int >	m_wasHere
	Array maintaining visited bits on each node.

BoyerMyrvoldPlanar *	pBM
	Link to class BoyerMyrvoldPlanar.

Detailed Description

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

Precondition: Graph has to be simple.

Definition at line 180 of file FindKuratowskis.h.

Constructor & Destructor Documentation

◆ FindKuratowskis()

ogdf::FindKuratowskis::FindKuratowskis ( BoyerMyrvoldPlanar * bm )

explicit

Constructor.

◆ ~FindKuratowskis()

ogdf::FindKuratowskis::~FindKuratowskis ( )

inline

Destructor.

Definition at line 186 of file FindKuratowskis.h.

Member Function Documentation

◆ addKuratowskiStructure()

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.

◆ extractExternalFacePath()

void ogdf::FindKuratowskis::extractExternalFacePath	(	SListPure< adjEntry > &	externalFacePath,
		const ArrayBuffer< adjEntry > &	highestFacePath,
		int	marker,
		int	highMarker
	)

protected

Extracts externalFacePath in direction CCW and splits highestFacePath in highestXYPaths.

◆ extractExternalSubgraph()

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)

◆ extractExternalSubgraphBundles()

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)

◆ extractHighestFacePath()

void ogdf::FindKuratowskis::extractHighestFacePath	(	ArrayBuffer< adjEntry > &	highestFacePath,
		int	marker
	)

protected

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

◆ extractPertinentSubgraph()

void ogdf::FindKuratowskis::extractPertinentSubgraph ( SListPure< WInfo > & W_All )

protected

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

◆ extractPertinentSubgraphBundles()

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)

◆ findRoot()

node ogdf::FindKuratowskis::findRoot ( node stopX ) const

protected

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

◆ getAllKuratowskis() [1/2]

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

inline

Get-method for the list of all KuratowskiStructures.

Definition at line 193 of file FindKuratowskis.h.

◆ getAllKuratowskis() [2/2]

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

inline

Constant get-method for the list of all KuratowskiStructures.

Definition at line 196 of file FindKuratowskis.h.

◆ NodeArray()

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

◆ operator=()

FindKuratowskis & ogdf::FindKuratowskis::operator= ( const FindKuratowskis & )

delete

◆ splitInMinorTypes()

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

◆ allKuratowskis

SListPure<KuratowskiStructure> ogdf::FindKuratowskis::allKuratowskis

protected

List of all Kuratowski Structures.

Definition at line 219 of file FindKuratowskis.h.

◆ k

KuratowskiStructure ogdf::FindKuratowskis::k

protected

Current Kuratowski Structure.

Definition at line 222 of file FindKuratowskis.h.

◆ m_adjParent

const NodeArray<adjEntry>& ogdf::FindKuratowskis::m_adjParent

protected

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

Definition at line 248 of file FindKuratowskis.h.

◆ m_backedgeFlags

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

◆ m_bundles

const bool ogdf::FindKuratowskis::m_bundles

protected

If true, bundles are extracted, otherwise single paths?

Definition at line 213 of file FindKuratowskis.h.

◆ m_dfi

const NodeArray<int>& ogdf::FindKuratowskis::m_dfi

protected

The one and only DFI-NodeArray.

Definition at line 237 of file FindKuratowskis.h.

◆ m_edgeType

EdgeArray<BoyerMyrvoldEdgeType>& ogdf::FindKuratowskis::m_edgeType

protected

Contains the type of each edge.

Definition at line 256 of file FindKuratowskis.h.

◆ m_embeddingGrade

const int& ogdf::FindKuratowskis::m_embeddingGrade

protected

The embedding grade.

Definition at line 210 of file FindKuratowskis.h.

◆ m_g

Graph& ogdf::FindKuratowskis::m_g

protected

Input graph.

Definition at line 207 of file FindKuratowskis.h.

◆ m_getWInfo

NodeArray<WInfo*> ogdf::FindKuratowskis::m_getWInfo

protected

Links appropriate WInfo to node.

Definition at line 216 of file FindKuratowskis.h.

◆ m_highestSubtreeDFI

const NodeArray<int>& ogdf::FindKuratowskis::m_highestSubtreeDFI

protected

The highest DFI in a subtree with node as root.

Definition at line 262 of file FindKuratowskis.h.

◆ m_leastAncestor

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

◆ m_lowPoint

NodeArray<int>& ogdf::FindKuratowskis::m_lowPoint

protected

The lowpoint of each node.

Definition at line 259 of file FindKuratowskis.h.

◆ m_nodeFromDFI

const Array<node>& ogdf::FindKuratowskis::m_nodeFromDFI

protected

Returns appropriate node from given DFI.

Definition at line 240 of file FindKuratowskis.h.

◆ m_nodeMarker

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

◆ m_numUnembeddedBackedgesInBicomp

NodeArray<int>& ogdf::FindKuratowskis::m_numUnembeddedBackedgesInBicomp

protected

Stores for each (virtual) bicomp root how many backedges to its bicomp still have to be embedded.

The value is set during the walkup, and it is used and decreased while embedding backedges during the walkdown.

Definition at line 277 of file FindKuratowskis.h.

◆ m_pertinentRoots

NodeArray<SListPure<node> >& ogdf::FindKuratowskis::m_pertinentRoots

protected

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

Definition at line 286 of file FindKuratowskis.h.

◆ m_pointsToRoot

const EdgeArray<node>& ogdf::FindKuratowskis::m_pointsToRoot

protected

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

Definition at line 270 of file FindKuratowskis.h.

◆ m_realVertex

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

◆ m_separatedDFSChildList

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

◆ m_wasHere

NodeArray<int> ogdf::FindKuratowskis::m_wasHere

protected

Array maintaining visited bits on each node.

Definition at line 229 of file FindKuratowskis.h.

◆ pBM

BoyerMyrvoldPlanar* ogdf::FindKuratowskis::pBM

protected

Link to class BoyerMyrvoldPlanar.

Definition at line 204 of file FindKuratowskis.h.

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

include/ogdf/planarity/boyer_myrvold/FindKuratowskis.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ FindKuratowskis()

◆ ~FindKuratowskis()

Member Function Documentation

◆ addKuratowskiStructure()

◆ extractExternalFacePath()

◆ extractExternalSubgraph()

◆ extractExternalSubgraphBundles()

◆ extractHighestFacePath()

◆ extractPertinentSubgraph()

◆ extractPertinentSubgraphBundles()

◆ findRoot()

◆ getAllKuratowskis() [1/2]

◆ getAllKuratowskis() [2/2]

◆ NodeArray()

◆ operator=()

◆ splitInMinorTypes()

Member Data Documentation

◆ allKuratowskis

◆ k

◆ m_adjParent

◆ m_backedgeFlags

◆ m_bundles

◆ m_dfi

◆ m_edgeType

◆ m_embeddingGrade

◆ m_g

◆ m_getWInfo

◆ m_highestSubtreeDFI

◆ m_leastAncestor

◆ m_lowPoint

◆ m_nodeFromDFI

◆ m_nodeMarker

◆ m_numUnembeddedBackedgesInBicomp

◆ m_pertinentRoots

◆ m_pointsToRoot

◆ m_realVertex

◆ m_separatedDFSChildList

◆ m_wasHere

◆ pBM

Open
Graph Drawing
Framework