Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::FindKuratowskis Class Reference

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. More...
 
 ~FindKuratowskis ()
 Destructor. More...
 
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. More...
 
SListPure< KuratowskiStructure > & getAllKuratowskis ()
 Get-method for the list of all KuratowskiStructures. More...
 
const SListPure< KuratowskiStructure > & getAllKuratowskis () const
 Constant get-method for the list of all KuratowskiStructures. More...
 
FindKuratowskisoperator= (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. More...
 
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) More...
 
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) More...
 
void extractHighestFacePath (ArrayBuffer< adjEntry > &highestFacePath, int marker)
 Extracts the highestFace Path of the bicomp containing both stopping nodes. More...
 
void extractPertinentSubgraph (SListPure< WInfo > &W_All)
 Extracts pertinent subgraph from all wNodes to V (without bundles) More...
 
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) More...
 
node findRoot (node stopX) const
 Finds root node of the bicomp containing the stopping node stopX. More...
 
const NodeArray (&m_link)[2]
 Links to opposite adjacency entries on external face in clockwise resp. ccw order. More...
 
void splitInMinorTypes (const SListPure< adjEntry > &externalFacePath, int marker)
 Assign pertinent nodes to the different minortypes and extracts inner externalPaths. More...
 

Protected Attributes

SListPure< KuratowskiStructureallKuratowskis
 List of all Kuratowski Structures. More...
 
KuratowskiStructure k
 Current Kuratowski Structure. More...
 
const NodeArray< adjEntry > & m_adjParent
 The adjEntry which goes from DFS-parent to current vertex. More...
 
NodeArray< SListPure< adjEntry > > & m_backedgeFlags
 Holds information, if node is the source of a backedge. More...
 
const bool m_bundles
 If true, bundles are extracted, otherwise single paths? More...
 
const NodeArray< int > & m_dfi
 The one and only DFI-NodeArray. More...
 
EdgeArray< BoyerMyrvoldEdgeType > & m_edgeType
 Contains the type of each edge. More...
 
const int & m_embeddingGrade
 The embedding grade. More...
 
Graphm_g
 Input graph. More...
 
NodeArray< WInfo * > m_getWInfo
 Links appropriate WInfo to node. More...
 
const NodeArray< int > & m_highestSubtreeDFI
 The highest DFI in a subtree with node as root. More...
 
const NodeArray< int > & m_leastAncestor
 The DFI of the least ancestor node over all backedges. More...
 
NodeArray< int > & m_lowPoint
 The lowpoint of each node. More...
 
const Array< node > & m_nodeFromDFI
 Returns appropriate node from given DFI. More...
 
int m_nodeMarker
 Value used as marker for visited nodes etc. More...
 
NodeArray< int > & m_numUnembeddedBackedgesInBicomp
 Stores for each (virtual) bicomp root how many backedges to its bicomp still have to be embedded. More...
 
NodeArray< SListPure< node > > & m_pertinentRoots
 List of virtual bicomp roots, that are pertinent to the current embedded node. More...
 
const EdgeArray< node > & m_pointsToRoot
 Identifies the rootnode of the child bicomp the given backedge points to. More...
 
const NodeArray< node > & m_realVertex
 Link to non-virtual vertex of a virtual Vertex. More...
 
const NodeArray< ListPure< node > > & m_separatedDFSChildList
 A list to all separated DFS-children of node. More...
 
NodeArray< int > m_wasHere
 Array maintaining visited bits on each node. More...
 
BoyerMyrvoldPlanarpBM
 Link to class BoyerMyrvoldPlanar. More...
 

Detailed Description

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

Precondition
Graph has to be simple.

Definition at line 183 of file FindKuratowskis.h.

Constructor & Destructor Documentation

◆ FindKuratowskis()

ogdf::FindKuratowskis::FindKuratowskis ( BoyerMyrvoldPlanar bm)
explicit

Constructor.

◆ ~FindKuratowskis()

ogdf::FindKuratowskis::~FindKuratowskis ( )
inline

Destructor.

Definition at line 188 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 198 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 203 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 226 of file FindKuratowskis.h.

◆ k

KuratowskiStructure ogdf::FindKuratowskis::k
protected

Current Kuratowski Structure.

Definition at line 229 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 255 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 290 of file FindKuratowskis.h.

◆ m_bundles

const bool ogdf::FindKuratowskis::m_bundles
protected

If true, bundles are extracted, otherwise single paths?

Definition at line 220 of file FindKuratowskis.h.

◆ m_dfi

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

The one and only DFI-NodeArray.

Definition at line 244 of file FindKuratowskis.h.

◆ m_edgeType

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

Contains the type of each edge.

Definition at line 263 of file FindKuratowskis.h.

◆ m_embeddingGrade

const int& ogdf::FindKuratowskis::m_embeddingGrade
protected

The embedding grade.

Definition at line 217 of file FindKuratowskis.h.

◆ m_g

Graph& ogdf::FindKuratowskis::m_g
protected

Input graph.

Definition at line 214 of file FindKuratowskis.h.

◆ m_getWInfo

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

Links appropriate WInfo to node.

Definition at line 223 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 269 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 260 of file FindKuratowskis.h.

◆ m_lowPoint

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

The lowpoint of each node.

Definition at line 266 of file FindKuratowskis.h.

◆ m_nodeFromDFI

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

Returns appropriate node from given DFI.

Definition at line 247 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 234 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 284 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 293 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 277 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 241 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 274 of file FindKuratowskis.h.

◆ m_wasHere

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

Array maintaining visited bits on each node.

Definition at line 236 of file FindKuratowskis.h.

◆ pBM

BoyerMyrvoldPlanar* ogdf::FindKuratowskis::pBM
protected

Link to class BoyerMyrvoldPlanar.

Definition at line 211 of file FindKuratowskis.h.


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