Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::PlanarAugmentation Class Reference

The algorithm for planar biconnectivity augmentation (Mutzel, Fialko). More...

#include <ogdf/augmentation/PlanarAugmentation.h>

+ Inheritance diagram for ogdf::PlanarAugmentation:

Public Member Functions

 PlanarAugmentation ()
 Creates an instance of the planar augmentation algorithm. More...
 
 ~PlanarAugmentation ()
 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 and updates the label-order. More...
 
node adjToCutvertex (node v, node cutvertex=nullptr)
 Returns a node that belongs to bc-node v and is adjacent to cutvertex. More...
 
void augment ()
 The main function for planar augmentation. More...
 
bool connectCondition (pa_label a, pa_label b)
 Checks if the pendants of label a and label b can be connected without creating a new pendant. More...
 
void connectInsideLabel (pa_label &label)
 Connects the only pendant of label with a computed ancestor. More...
 
void connectLabels (pa_label first, pa_label second)
 Inserts edges between pendants of label first and second. More...
 
edge connectPendants (node pendant1, node pendant2)
 Connects two pendants. More...
 
void deleteLabel (pa_label &label, bool removePendants=true)
 Deletes label. More...
 
void deletePendant (node pendant, bool removeFromLabel=true)
 Deletes the pendant pendant, and, if removeFromLabel is true, removes it from the corresponding label and updates the label-order. More...
 
node findLastBefore (node pendant, node ancestor)
 Traverses from pendant to ancestor and returns the last node before ancestor on the path. More...
 
bool findMatching (pa_label &first, pa_label &second)
 Finds two matching labels, so all pendants can be connected without losing planarity. More...
 
PALabel::StopCause followPath (node v, node &last)
 Traverses to the root and checks several stop conditions. More...
 
ListIterator< pa_labelinsertLabel (pa_label label)
 Inserts label into m_labels by decreasing order. More...
 
void joinPendants (pa_label &label)
 Connects all pendants of label with new edges. More...
 
void makeConnectedByPendants ()
 Makes the graph connected by new edges between pendants of the connected components. More...
 
void modifyBCRoot (node oldRoot, node newRoot)
 Modifies the root of the BC-Tree that newRoot replaces oldRoot. More...
 
pa_label newLabel (node cutvertex, node pendant, PALabel::StopCause whyStop)
 Creates a new label and inserts it into m_labels. More...
 
bool planarityCheck (node v1, node v2)
 Checks planarity for a new edge (v1, v2) in the original graph. More...
 
void reduceChain (node pendant, pa_label labelOld=nullptr)
 Traverses to the root and creates a label or updates one. More...
 
void removeAllPendants (pa_label &label)
 Removes all pendants of label. More...
 
void terminate ()
 Cleanup. More...
 
void updateAdjNonChildren (node newBlock, SList< node > &path)
 Updates m_adjNonChildren. More...
 
void updateNewEdges (const SList< edge > &newEdges)
 Major updates caused by the new edges. More...
 

Private Attributes

NodeArray< SList< adjEntry > > m_adjNonChildren
 Stores for each node of the bc-tree the children that have an adjacent bc-node that doesn't belong to the same parent-node. More...
 
NodeArray< pa_labelm_belongsTo
 The label a BC-Node belongs to. More...
 
NodeArray< ListIterator< pa_label > > m_isLabel
 The list iterator in m_labels if the node in the BC-Tree is a label. More...
 
List< pa_labelm_labels
 The list of all labels, sorted by size (decreasing). More...
 
int m_nPlanarityTests = 0
 The number of planarity tests. More...
 
DynamicBCTreem_pBCTree = nullptr
 The corresponding BC-Tree. More...
 
List< nodem_pendants
 The list of all pendants (leaves in the BC-Tree). More...
 
List< nodem_pendantsToDel
 The list of pendants that has to be deleted after each reduceChain. 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 planar biconnectivity augmentation (Mutzel, Fialko).

The class PlanarAugmentation implements an augmentation algorithm that augments a graph to a biconnected graph. In addition, if the graph was planar before augmentation, the resulting graph will be biconnected and planar. The algorithm uses (dynamic) BC-trees and achieves biconnectivity by inserting edges between nodes of pendants (that are leaves in the bc-tree). The guaranteed approximation-quality is 5/3.

The implementation is based on the following publication:

Sergej Fialko, Petra Mutzel: A New Approximation Algorithm for the Planar Augmentation Problem. Proc. SODA 1998, pp. 260-269.

Definition at line 59 of file PlanarAugmentation.h.

Constructor & Destructor Documentation

◆ PlanarAugmentation()

ogdf::PlanarAugmentation::PlanarAugmentation ( )
inline

Creates an instance of the planar augmentation algorithm.

Definition at line 63 of file PlanarAugmentation.h.

◆ ~PlanarAugmentation()

ogdf::PlanarAugmentation::~PlanarAugmentation ( )
inline

Destruction.

Definition at line 66 of file PlanarAugmentation.h.

Member Function Documentation

◆ addPendant()

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

Adds pendant to label and updates the label-order.

◆ adjToCutvertex()

node ogdf::PlanarAugmentation::adjToCutvertex ( node  v,
node  cutvertex = nullptr 
)
private

Returns a node that belongs to bc-node v and is adjacent to cutvertex.

Parameters
vis a node in the BC-Tree.
cutvertexis the last cut-vertex found.
Returns
a node of the original graph.

◆ augment()

void ogdf::PlanarAugmentation::augment ( )
private

The main function for planar augmentation.

◆ connectCondition()

bool ogdf::PlanarAugmentation::connectCondition ( pa_label  a,
pa_label  b 
)
private

Checks if the pendants of label a and label b can be connected without creating a new pendant.

◆ connectInsideLabel()

void ogdf::PlanarAugmentation::connectInsideLabel ( pa_label label)
private

Connects the only pendant of label with a computed ancestor.

◆ connectLabels()

void ogdf::PlanarAugmentation::connectLabels ( pa_label  first,
pa_label  second 
)
private

Inserts edges between pendants of label first and second.

Precondition
first.size() is greater than second.size() or equal.

◆ connectPendants()

edge ogdf::PlanarAugmentation::connectPendants ( node  pendant1,
node  pendant2 
)
private

Connects two pendants.

Returns
the new edge in the original graph.

◆ deleteLabel()

void ogdf::PlanarAugmentation::deleteLabel ( pa_label label,
bool  removePendants = true 
)
private

Deletes label.

◆ deletePendant()

void ogdf::PlanarAugmentation::deletePendant ( node  pendant,
bool  removeFromLabel = true 
)
private

Deletes the pendant pendant, and, if removeFromLabel is true, removes it from the corresponding label and updates the label-order.

◆ doCall()

virtual void ogdf::PlanarAugmentation::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.

◆ findLastBefore()

node ogdf::PlanarAugmentation::findLastBefore ( node  pendant,
node  ancestor 
)
private

Traverses from pendant to ancestor and returns the last node before ancestor on the path.

◆ findMatching()

bool ogdf::PlanarAugmentation::findMatching ( pa_label first,
pa_label second 
)
private

Finds two matching labels, so all pendants can be connected without losing planarity.

Parameters
firstis the label with maximum size, modified by the function.
secondis the matching label, modified by the function: 0 if no matching is found.
Returns
true iff a matching label is found.

◆ followPath()

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

Traverses to the root and checks several stop conditions.

Is called by reduceChain.

Parameters
vis a node of the BC-Tree.
lastis the last found C-vertex in the BC-Tree, is modified by the method.
Returns
the stop-cause.

◆ insertLabel()

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

Inserts label into m_labels by decreasing order.

Returns
the corresponding list iterator.

◆ joinPendants()

void ogdf::PlanarAugmentation::joinPendants ( pa_label label)
private

Connects all pendants of label with new edges.

◆ makeConnectedByPendants()

void ogdf::PlanarAugmentation::makeConnectedByPendants ( )
private

Makes the graph connected by new edges between pendants of the connected components.

◆ modifyBCRoot()

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

Modifies the root of the BC-Tree that newRoot replaces oldRoot.

◆ newLabel()

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

Creates a new label and inserts it into m_labels.

◆ planarityCheck()

bool ogdf::PlanarAugmentation::planarityCheck ( node  v1,
node  v2 
)
private

Checks planarity for a new edge (v1, v2) in the original graph.

Parameters
v1is a node in the original graph.
v2is a node in the original graph.
Returns
true iff the graph (including the new edge) is planar.

◆ reduceChain()

void ogdf::PlanarAugmentation::reduceChain ( node  pendant,
pa_label  labelOld = nullptr 
)
private

Traverses to the root and creates a label or updates one.

Is called for every pendant node.

Parameters
pendantis a pendant in the BC-Tree.
labelOldis the old label of pendant.

◆ removeAllPendants()

void ogdf::PlanarAugmentation::removeAllPendants ( pa_label label)
private

Removes all pendants of label.

◆ terminate()

void ogdf::PlanarAugmentation::terminate ( )
private

Cleanup.

◆ updateAdjNonChildren()

void ogdf::PlanarAugmentation::updateAdjNonChildren ( node  newBlock,
SList< node > &  path 
)
private

Updates m_adjNonChildren.

Parameters
newBlockis a new created block of the BC-Tree.
pathis the path in the BC-Tree between the two connected nodes.

◆ updateNewEdges()

void ogdf::PlanarAugmentation::updateNewEdges ( const SList< edge > &  newEdges)
private

Major updates caused by the new edges.

Parameters
newEdgesis a list of all new edges.

Member Data Documentation

◆ m_adjNonChildren

NodeArray<SList<adjEntry> > ogdf::PlanarAugmentation::m_adjNonChildren
private

Stores for each node of the bc-tree the children that have an adjacent bc-node that doesn't belong to the same parent-node.

This is necessary because the bc-tree uses an union-find-data-structure to store dependencies between bc-nodes. The adjacencies in the bc-tree won't be updated.

Definition at line 113 of file PlanarAugmentation.h.

◆ m_belongsTo

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

The label a BC-Node belongs to.

Definition at line 101 of file PlanarAugmentation.h.

◆ m_isLabel

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

The list iterator in m_labels if the node in the BC-Tree is a label.

Definition at line 104 of file PlanarAugmentation.h.

◆ m_labels

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

The list of all labels, sorted by size (decreasing).

Definition at line 92 of file PlanarAugmentation.h.

◆ m_nPlanarityTests

int ogdf::PlanarAugmentation::m_nPlanarityTests = 0
private

The number of planarity tests.

Definition at line 80 of file PlanarAugmentation.h.

◆ m_pBCTree

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

The corresponding BC-Tree.

Definition at line 86 of file PlanarAugmentation.h.

◆ m_pendants

List<node> ogdf::PlanarAugmentation::m_pendants
private

The list of all pendants (leaves in the BC-Tree).

Definition at line 95 of file PlanarAugmentation.h.

◆ m_pendantsToDel

List<node> ogdf::PlanarAugmentation::m_pendantsToDel
private

The list of pendants that has to be deleted after each reduceChain.

Definition at line 98 of file PlanarAugmentation.h.

◆ m_pGraph

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

The working graph.

Definition at line 83 of file PlanarAugmentation.h.

◆ m_pResult

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

The inserted edges by the algorithm.

Definition at line 89 of file PlanarAugmentation.h.


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