Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::KuratowskiStructure Class Reference

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...
 
KuratowskiStructureoperator= (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< adjEntryexternalFacePath
 External face path of bicomp containing V in direction CCW. More...
 
SListPure< edgeexternalSubgraph
 A list of all edges in all externally active paths (bundles only) More...
 
SListPure< ExternEexternE
 List of externally active nodes strictly between x and y for minortypes B and E. More...
 
ArrayBuffer< adjEntryhighestFacePath
 The whole highestFacePath of the bicomp containing V. More...
 
SListPure< ArrayBuffer< adjEntry > > highestXYPaths
 The appropriate paths of the highestFacePath for each wNode. More...
 
SListPure< edgepertinentSubgraph
 A list of all edges in pertinent paths (bundles only) More...
 
SListPure< nodestopXEndnodes
 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< nodestopYEndnodes
 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< WInfowNodes
 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 92 of file FindKuratowskis.h.

Constructor & Destructor Documentation

◆ KuratowskiStructure() [1/2]

ogdf::KuratowskiStructure::KuratowskiStructure ( )
inline

Constructor.

Definition at line 97 of file FindKuratowskis.h.

◆ ~KuratowskiStructure()

ogdf::KuratowskiStructure::~KuratowskiStructure ( )
inline

Destructor.

Definition at line 99 of file FindKuratowskis.h.

◆ KuratowskiStructure() [2/2]

ogdf::KuratowskiStructure::KuratowskiStructure ( const KuratowskiStructure orig)
inline

Copy constructor.

Definition at line 102 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 107 of file FindKuratowskis.h.

Friends And Related Function Documentation

◆ ExtractKuratowskis

friend class ExtractKuratowskis
friend

Definition at line 94 of file FindKuratowskis.h.

◆ FindKuratowskis

friend class FindKuratowskis
friend

Definition at line 93 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 149 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 152 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 163 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 143 of file FindKuratowskis.h.

◆ highestXYPaths

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

The appropriate paths of the highestFacePath for each wNode.

Definition at line 146 of file FindKuratowskis.h.

◆ pertinentSubgraph

SListPure<edge> ogdf::KuratowskiStructure::pertinentSubgraph
protected

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

Definition at line 155 of file FindKuratowskis.h.

◆ R

node ogdf::KuratowskiStructure::R

The root of the bicomp containing stopX and stopY.

Definition at line 121 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 125 of file FindKuratowskis.h.

◆ stopX

node ogdf::KuratowskiStructure::stopX

First stopping node.

Definition at line 127 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 170 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 166 of file FindKuratowskis.h.

◆ stopY

node ogdf::KuratowskiStructure::stopY

Second stopping node.

Definition at line 129 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 172 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 168 of file FindKuratowskis.h.

◆ V

node ogdf::KuratowskiStructure::V

The current node to embed.

Definition at line 116 of file FindKuratowskis.h.

◆ V_DFI

int ogdf::KuratowskiStructure::V_DFI

DFI of the current node to embed.

Definition at line 118 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 136 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 160 of file FindKuratowskis.h.


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