A Kuratowski Structure is a special graph structure containing severals subdivisions. More...

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

Public Member Functions
	KuratowskiStructure ()
	Constructor. More...

	KuratowskiStructure (const KuratowskiStructure &orig)
	Copy constructor. More...

	~KuratowskiStructure ()
	Destructor. More...

void	clear ()
	Reset all data members. More...

KuratowskiStructure &	operator= (const KuratowskiStructure &orig)
	Assignment. More...

Public Attributes
node	R
	The root of the bicomp containing `stopX` and `stopY`. More...

node	RReal
	Real node of virtual node R. More...

node	stopX
	First stopping node. More...

node	stopY
	Second stopping node. More...

node	V
	The current node to embed. More...

int	V_DFI
	DFI of the current node to embed. More...

Protected Member Functions
void	copy (const KuratowskiStructure &orig)
	Copies class. More...

void	copyPointer (const KuratowskiStructure &orig, SListPure< WInfo > &list)
	Used in copy constructor. More...

Protected Attributes
SListPure< adjEntry >	externalFacePath
	External face path of bicomp containing V in direction CCW. More...

SListPure< edge >	externalSubgraph
	A list of all edges in all externally active paths (bundles only) More...

SListPure< ExternE >	externE
	List of externally active nodes strictly between x and y for minortypes B and E. More...

ArrayBuffer< adjEntry >	highestFacePath
	The whole highestFacePath of the bicomp containing V. More...

SListPure< ArrayBuffer< adjEntry > >	highestXYPaths
	The appropriate paths of the highestFacePath for each wNode. More...

SListPure< edge >	pertinentSubgraph
	A list of all edges in pertinent paths (bundles only) More...

SListPure< node >	stopXEndnodes
	List of all endnodes of paths starting at stopX (only without bundles) More...

SListPure< int >	stopXStartnodes
	List of all virtual startnodes of paths starting at stopX (only without bundles) More...

SListPure< node >	stopYEndnodes
	List of all endnodes of paths starting at stopY (only without bundles) More...

SListPure< int >	stopYStartnodes
	List of all virtual startnodes of paths starting at stopY (only without bundles) More...

SListPure< WInfo >	wNodes
	Holds information about all pertinent nodes w of the bicomp containing V. More...

SListPure< ArrayBuffer< adjEntry > >	zPaths
	A path from the zNode in minortype D to node V for each highest XY-Path. More...

Friends
class	ExtractKuratowskis

class	FindKuratowskis

Detailed Description

A Kuratowski Structure is a special graph structure containing severals subdivisions.

Definition at line 96 of file FindKuratowskis.h.

Constructor & Destructor Documentation

◆ KuratowskiStructure() [1/2]

ogdf::KuratowskiStructure::KuratowskiStructure ( )

inline

Constructor.

Definition at line 102 of file FindKuratowskis.h.

◆ ~KuratowskiStructure()

ogdf::KuratowskiStructure::~KuratowskiStructure ( )

inline

Destructor.

Definition at line 105 of file FindKuratowskis.h.

◆ KuratowskiStructure() [2/2]

ogdf::KuratowskiStructure::KuratowskiStructure ( const KuratowskiStructure & orig )

inline

Copy constructor.

Definition at line 108 of file FindKuratowskis.h.

Member Function Documentation

◆ clear()

void ogdf::KuratowskiStructure::clear ( )

Reset all data members.

◆ copy()

void ogdf::KuratowskiStructure::copy ( const KuratowskiStructure & orig )

protected

Copies class.

◆ copyPointer()

void ogdf::KuratowskiStructure::copyPointer	(	const KuratowskiStructure &	orig,
		SListPure< WInfo > &	list
	)

protected

Used in copy constructor.

◆ operator=()

KuratowskiStructure& ogdf::KuratowskiStructure::operator= ( const KuratowskiStructure & orig )

inline

Assignment.

Definition at line 111 of file FindKuratowskis.h.

Friends And Related Function Documentation

◆ ExtractKuratowskis

friend class ExtractKuratowskis

friend

Definition at line 98 of file FindKuratowskis.h.

◆ FindKuratowskis

friend class FindKuratowskis

friend

Definition at line 97 of file FindKuratowskis.h.

Member Data Documentation

◆ externalFacePath

SListPure<adjEntry> ogdf::KuratowskiStructure::externalFacePath

protected

External face path of bicomp containing V in direction CCW.

Definition at line 153 of file FindKuratowskis.h.

◆ externalSubgraph

SListPure<edge> ogdf::KuratowskiStructure::externalSubgraph

protected

A list of all edges in all externally active paths (bundles only)

Definition at line 156 of file FindKuratowskis.h.

◆ externE

SListPure<ExternE> ogdf::KuratowskiStructure::externE

protected

List of externally active nodes strictly between x and y for minortypes B and E.

Definition at line 167 of file FindKuratowskis.h.

◆ highestFacePath

ArrayBuffer<adjEntry> ogdf::KuratowskiStructure::highestFacePath

protected

The whole highestFacePath of the bicomp containing V.

The construct the highestFacePath, delete all edges of V except the two edges on the external face. The highestFacePath is the path starting at the first external edge along the unique face back to V.

Definition at line 147 of file FindKuratowskis.h.

◆ highestXYPaths

SListPure<ArrayBuffer<adjEntry> > ogdf::KuratowskiStructure::highestXYPaths

protected

The appropriate paths of the highestFacePath for each wNode.

Definition at line 150 of file FindKuratowskis.h.

◆ pertinentSubgraph

SListPure<edge> ogdf::KuratowskiStructure::pertinentSubgraph

protected

A list of all edges in pertinent paths (bundles only)

Definition at line 159 of file FindKuratowskis.h.

◆ R

node ogdf::KuratowskiStructure::R

The root of the bicomp containing stopX and stopY.

Definition at line 125 of file FindKuratowskis.h.

◆ RReal

node ogdf::KuratowskiStructure::RReal

Real node of virtual node R.

This is redundant, but virtual node will be deleted later on

Definition at line 129 of file FindKuratowskis.h.

◆ stopX

node ogdf::KuratowskiStructure::stopX

First stopping node.

Definition at line 131 of file FindKuratowskis.h.

◆ stopXEndnodes

SListPure<node> ogdf::KuratowskiStructure::stopXEndnodes

protected

List of all endnodes of paths starting at stopX (only without bundles)

Definition at line 174 of file FindKuratowskis.h.

◆ stopXStartnodes

SListPure<int> ogdf::KuratowskiStructure::stopXStartnodes

protected

List of all virtual startnodes of paths starting at stopX (only without bundles)

Definition at line 170 of file FindKuratowskis.h.

◆ stopY

node ogdf::KuratowskiStructure::stopY

Second stopping node.

Definition at line 133 of file FindKuratowskis.h.

◆ stopYEndnodes

SListPure<node> ogdf::KuratowskiStructure::stopYEndnodes

protected

List of all endnodes of paths starting at stopY (only without bundles)

Definition at line 176 of file FindKuratowskis.h.

◆ stopYStartnodes

SListPure<int> ogdf::KuratowskiStructure::stopYStartnodes

protected

List of all virtual startnodes of paths starting at stopY (only without bundles)

Definition at line 172 of file FindKuratowskis.h.

◆ V

node ogdf::KuratowskiStructure::V

The current node to embed.

Definition at line 120 of file FindKuratowskis.h.

◆ V_DFI

int ogdf::KuratowskiStructure::V_DFI

DFI of the current node to embed.

Definition at line 122 of file FindKuratowskis.h.

◆ wNodes

SListPure<WInfo> ogdf::KuratowskiStructure::wNodes

protected

Holds information about all pertinent nodes w of the bicomp containing V.

Those were not embedded because of the two stopping nodes. In addition, links to the highest-XY-path and the z-nodes of w and the minortype is saved.

Definition at line 140 of file FindKuratowskis.h.

◆ zPaths

SListPure<ArrayBuffer<adjEntry> > ogdf::KuratowskiStructure::zPaths

protected

A path from the zNode in minortype D to node V for each highest XY-Path.

zNodes are cut-vertices not contained in the external face path

Definition at line 164 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

Public Attributes

Protected Member Functions

Protected Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

◆ KuratowskiStructure() [1/2]

◆ ~KuratowskiStructure()

◆ KuratowskiStructure() [2/2]

Member Function Documentation

◆ clear()

◆ copy()

◆ copyPointer()

◆ operator=()

Friends And Related Function Documentation

◆ ExtractKuratowskis

◆ FindKuratowskis

Member Data Documentation

◆ externalFacePath

◆ externalSubgraph

◆ externE

◆ highestFacePath

◆ highestXYPaths

◆ pertinentSubgraph

◆ R

◆ RReal

◆ stopX

◆ stopXEndnodes

◆ stopXStartnodes

◆ stopY

◆ stopYEndnodes

◆ stopYStartnodes

◆ V

◆ V_DFI

◆ wNodes

◆ zPaths

Open
Graph Drawing
Framework