Open
Graph Drawing
Framework

  v. 2023.09 (Elderberry)
 
Overview Class Hierarchy Class Index Class List Members Namespaces Source Files
 

Loading...
Searching...
No Matches
Public Member Functions | Public Attributes | Protected Member Functions | Protected Attributes | Friends | List of all members
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.
 
 KuratowskiStructure (const KuratowskiStructure &orig)
 Copy constructor.
 
 ~KuratowskiStructure ()
 Destructor.
 
void clear ()
 Reset all data members.
 
KuratowskiStructure & operator= (const KuratowskiStructure &orig)
 Assignment.
 

Public Attributes

node R
 The root of the bicomp containing stopX and stopY.
 
node RReal
 Real node of virtual node R.
 
node stopX
 First stopping node.
 
node stopY
 Second stopping node.
 
node V
 The current node to embed.
 
int V_DFI
 DFI of the current node to embed.
 

Protected Member Functions

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

Protected Attributes

SListPure< adjEntry > externalFacePath
 External face path of bicomp containing V in direction CCW.
 
SListPure< edge > externalSubgraph
 A list of all edges in all externally active paths (bundles only)
 
SListPure< ExternE > externE
 List of externally active nodes strictly between x and y for minortypes B and E.
 
ArrayBuffer< adjEntry > highestFacePath
 The whole highestFacePath of the bicomp containing V.
 
SListPure< ArrayBuffer< adjEntry > > highestXYPaths
 The appropriate paths of the highestFacePath for each wNode.
 
SListPure< edge > pertinentSubgraph
 A list of all edges in pertinent paths (bundles only)
 
SListPure< node > stopXEndnodes
 List of all endnodes of paths starting at stopX (only without bundles)
 
SListPure< int > stopXStartnodes
 List of all virtual startnodes of paths starting at stopX (only without bundles)
 
SListPure< node > stopYEndnodes
 List of all endnodes of paths starting at stopY (only without bundles)
 
SListPure< int > stopYStartnodes
 List of all virtual startnodes of paths starting at stopY (only without bundles)
 
SListPure< WInfo > wNodes
 Holds information about all pertinent nodes w of the bicomp containing V.
 
SListPure< ArrayBuffer< adjEntry > > zPaths
 A path from the zNode in minortype D to node V for each highest XY-Path.
 

Friends

class ExtractKuratowskis
 
class FindKuratowskis
 

Detailed Description

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

Definition at line 89 of file FindKuratowskis.h.

Constructor & Destructor Documentation

◆ KuratowskiStructure() [1/2]

ogdf::KuratowskiStructure::KuratowskiStructure ( )
inline

Constructor.

Definition at line 95 of file FindKuratowskis.h.

◆ ~KuratowskiStructure()

ogdf::KuratowskiStructure::~KuratowskiStructure ( )
inline

Destructor.

Definition at line 98 of file FindKuratowskis.h.

◆ KuratowskiStructure() [2/2]

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

Copy constructor.

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

Friends And Related Symbol Documentation

◆ ExtractKuratowskis

friend class ExtractKuratowskis
friend

Definition at line 91 of file FindKuratowskis.h.

◆ FindKuratowskis

friend class FindKuratowskis
friend

Definition at line 90 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 146 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 149 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 160 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 140 of file FindKuratowskis.h.

◆ highestXYPaths

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

The appropriate paths of the highestFacePath for each wNode.

Definition at line 143 of file FindKuratowskis.h.

◆ pertinentSubgraph

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

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

Definition at line 152 of file FindKuratowskis.h.

◆ R

node ogdf::KuratowskiStructure::R

The root of the bicomp containing stopX and stopY.

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

◆ stopX

node ogdf::KuratowskiStructure::stopX

First stopping node.

Definition at line 124 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 167 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 163 of file FindKuratowskis.h.

◆ stopY

node ogdf::KuratowskiStructure::stopY

Second stopping node.

Definition at line 126 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 169 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 165 of file FindKuratowskis.h.

◆ V

node ogdf::KuratowskiStructure::V

The current node to embed.

Definition at line 113 of file FindKuratowskis.h.

◆ V_DFI

int ogdf::KuratowskiStructure::V_DFI

DFI of the current node to embed.

Definition at line 115 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 133 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 157 of file FindKuratowskis.h.

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