Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::PlanarAugmentationFix Class Reference

The algorithm for biconnectivity augmentation with fixed combinatorial embedding. More...

#include <ogdf/augmentation/PlanarAugmentationFix.h>

+ Inheritance diagram for ogdf::PlanarAugmentationFix:

Public Member Functions

 PlanarAugmentationFix ()
 Creates an instance of planar augmentation with fixed embedding. More...
 
 ~PlanarAugmentationFix ()
 Destruction. More...
 
- Public Member Functions inherited from ogdf::AugmentationModule
 AugmentationModule ()
 Initializes an augmentation module. More...
 
virtual ~AugmentationModule ()
 
void call (Graph &G)
 Calls the augmentation module for graph G. More...
 
void call (Graph &G, List< edge > &L)
 Calls the augmentation module for graph G. More...
 
int numberOfAddedEdges () const
 Returns the number of added edges. More...
 
void operator() (Graph &G)
 Calls the augmentation module for graph G. More...
 
void operator() (Graph &G, List< edge > &L)
 Calls the augmentation module for graph G. More...
 

Protected Member Functions

virtual void doCall (Graph &g, List< edge > &list) override
 The implementation of the algorithm call. More...
 

Private Member Functions

void addPendant (node pendant, pa_label &label)
 Adds pendant to label. More...
 
void augment (adjEntry adjOuterFace)
 The main function for planar augmentation. More...
 
void changeBCRoot (node oldRoot, node newRoot)
 Exchanges oldRoot by newRoot and updates data structurs in the bc-tree. More...
 
void connectPendants (node pendant1, node pendant2, adjEntry adjV1, adjEntry adjV2)
 Connects the two pendants. More...
 
void connectSingleLabel ()
 Connects the remaining label. More...
 
void deleteLabel (pa_label &label)
 Deletes the given label. More...
 
void deletePendant (node pendant)
 Deletes the given pendant. More...
 
bool findMatching (node &pendant1, node &pendant2, adjEntry &v1, adjEntry &v2)
 Finds the next matching pendants. More...
 
void findMatchingRev (node &pendant1, node &pendant2, adjEntry &v1, adjEntry &v2)
 Called by findMatching, if a dominating tree was detected. More...
 
PALabel::StopCause followPath (node v, node &last)
 Traverses upwards in the bc-tree, starting at the pendant node v. More...
 
ListIterator< pa_labelinsertLabel (pa_label label)
 Inserts label into the list of labels maintaining decreasing order. More...
 
void modifyBCRoot (node oldRoot, node newRoot)
 Modifies the root of the bc-tree. More...
 
pa_label newLabel (node cutvertex, node parent, node pendant, PALabel::StopCause whyStop)
 Creates a new label. More...
 
void reduceChain (node pendant)
 Adds pendant to a label or creates one. More...
 
void removeLabel (pa_label &label)
 Removes the given label from the list of labels. More...
 

Private Attributes

node m_actBCRoot
 The actual root of the bc-tree. More...
 
NodeArray< pa_labelm_belongsTo
 Array that contains the label a node belongs to. More...
 
NodeArray< ListIterator< node > > m_belongsToIt
 Array that contains the iterator of the label a node belongs to. More...
 
EdgeArray< edgem_eCopy
 Edge-array required for construction of the graph copy. More...
 
GraphCopy m_graphCopy
 The actual partial graph. More...
 
NodeArray< ListIterator< pa_label > > m_isLabel
 Array that contains iterators to the list of labels if a node is a parent of a label. More...
 
List< pa_labelm_labels
 The list of all labels. More...
 
CombinatorialEmbeddingm_pActEmbedding = nullptr
 The embedding of m_graphCopy. More...
 
DynamicBCTreem_pBCTree = nullptr
 The actual dynamic bc-tree. More...
 
CombinatorialEmbeddingm_pEmbedding = nullptr
 The embedding of m_pGraph. More...
 
Graphm_pGraph = nullptr
 The working graph. More...
 
List< edge > * m_pResult = nullptr
 The inserted edges by the algorithm. More...
 

Detailed Description

The algorithm for biconnectivity augmentation with fixed combinatorial embedding.

Definition at line 46 of file PlanarAugmentationFix.h.

Constructor & Destructor Documentation

◆ PlanarAugmentationFix()

ogdf::PlanarAugmentationFix::PlanarAugmentationFix ( )
inline

Creates an instance of planar augmentation with fixed embedding.

Definition at line 50 of file PlanarAugmentationFix.h.

◆ ~PlanarAugmentationFix()

ogdf::PlanarAugmentationFix::~PlanarAugmentationFix ( )
inline

Destruction.

Definition at line 53 of file PlanarAugmentationFix.h.

Member Function Documentation

◆ addPendant()

void ogdf::PlanarAugmentationFix::addPendant ( node  pendant,
pa_label label 
)
private

Adds pendant to label.

◆ augment()

void ogdf::PlanarAugmentationFix::augment ( adjEntry  adjOuterFace)
private

The main function for planar augmentation.

◆ changeBCRoot()

void ogdf::PlanarAugmentationFix::changeBCRoot ( node  oldRoot,
node  newRoot 
)
private

Exchanges oldRoot by newRoot and updates data structurs in the bc-tree.

◆ connectPendants()

void ogdf::PlanarAugmentationFix::connectPendants ( node  pendant1,
node  pendant2,
adjEntry  adjV1,
adjEntry  adjV2 
)
private

Connects the two pendants.

◆ connectSingleLabel()

void ogdf::PlanarAugmentationFix::connectSingleLabel ( )
private

Connects the remaining label.

◆ deleteLabel()

void ogdf::PlanarAugmentationFix::deleteLabel ( pa_label label)
private

Deletes the given label.

◆ deletePendant()

void ogdf::PlanarAugmentationFix::deletePendant ( node  pendant)
private

Deletes the given pendant.

◆ doCall()

virtual void ogdf::PlanarAugmentationFix::doCall ( Graph g,
List< edge > &  list 
)
overrideprotectedvirtual

The implementation of the algorithm call.

Parameters
gis the working graph.
listis the list of all new edges.

Implements ogdf::AugmentationModule.

◆ findMatching()

bool ogdf::PlanarAugmentationFix::findMatching ( node pendant1,
node pendant2,
adjEntry v1,
adjEntry v2 
)
private

Finds the next matching pendants.

◆ findMatchingRev()

void ogdf::PlanarAugmentationFix::findMatchingRev ( node pendant1,
node pendant2,
adjEntry v1,
adjEntry v2 
)
private

Called by findMatching, if a dominating tree was detected.

◆ followPath()

PALabel::StopCause ogdf::PlanarAugmentationFix::followPath ( node  v,
node last 
)
private

Traverses upwards in the bc-tree, starting at the pendant node v.

◆ insertLabel()

ListIterator<pa_label> ogdf::PlanarAugmentationFix::insertLabel ( pa_label  label)
private

Inserts label into the list of labels maintaining decreasing order.

◆ modifyBCRoot()

void ogdf::PlanarAugmentationFix::modifyBCRoot ( node  oldRoot,
node  newRoot 
)
private

Modifies the root of the bc-tree.

◆ newLabel()

pa_label ogdf::PlanarAugmentationFix::newLabel ( node  cutvertex,
node  parent,
node  pendant,
PALabel::StopCause  whyStop 
)
private

Creates a new label.

◆ reduceChain()

void ogdf::PlanarAugmentationFix::reduceChain ( node  pendant)
private

Adds pendant to a label or creates one.

◆ removeLabel()

void ogdf::PlanarAugmentationFix::removeLabel ( pa_label label)
private

Removes the given label from the list of labels.

Member Data Documentation

◆ m_actBCRoot

node ogdf::PlanarAugmentationFix::m_actBCRoot
private

The actual root of the bc-tree.

Definition at line 99 of file PlanarAugmentationFix.h.

◆ m_belongsTo

NodeArray<pa_label> ogdf::PlanarAugmentationFix::m_belongsTo
private

Array that contains the label a node belongs to.

Definition at line 93 of file PlanarAugmentationFix.h.

◆ m_belongsToIt

NodeArray<ListIterator<node> > ogdf::PlanarAugmentationFix::m_belongsToIt
private

Array that contains the iterator of the label a node belongs to.

Definition at line 96 of file PlanarAugmentationFix.h.

◆ m_eCopy

EdgeArray<edge> ogdf::PlanarAugmentationFix::m_eCopy
private

Edge-array required for construction of the graph copy.

Definition at line 84 of file PlanarAugmentationFix.h.

◆ m_graphCopy

GraphCopy ogdf::PlanarAugmentationFix::m_graphCopy
private

The actual partial graph.

Definition at line 81 of file PlanarAugmentationFix.h.

◆ m_isLabel

NodeArray<ListIterator<pa_label> > ogdf::PlanarAugmentationFix::m_isLabel
private

Array that contains iterators to the list of labels if a node is a parent of a label.

Definition at line 90 of file PlanarAugmentationFix.h.

◆ m_labels

List<pa_label> ogdf::PlanarAugmentationFix::m_labels
private

The list of all labels.

Definition at line 87 of file PlanarAugmentationFix.h.

◆ m_pActEmbedding

CombinatorialEmbedding* ogdf::PlanarAugmentationFix::m_pActEmbedding = nullptr
private

The embedding of m_graphCopy.

Definition at line 69 of file PlanarAugmentationFix.h.

◆ m_pBCTree

DynamicBCTree* ogdf::PlanarAugmentationFix::m_pBCTree = nullptr
private

The actual dynamic bc-tree.

Definition at line 78 of file PlanarAugmentationFix.h.

◆ m_pEmbedding

CombinatorialEmbedding* ogdf::PlanarAugmentationFix::m_pEmbedding = nullptr
private

The embedding of m_pGraph.

Definition at line 66 of file PlanarAugmentationFix.h.

◆ m_pGraph

Graph* ogdf::PlanarAugmentationFix::m_pGraph = nullptr
private

The working graph.

Definition at line 72 of file PlanarAugmentationFix.h.

◆ m_pResult

List<edge>* ogdf::PlanarAugmentationFix::m_pResult = nullptr
private

The inserted edges by the algorithm.

Definition at line 75 of file PlanarAugmentationFix.h.


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