Open
Graph Drawing
Framework

  v.2010.10
 
Overview Class Hierarchy Class Index Class List Members Namespaces Source Files

Public Member Functions | Protected Member Functions | Private Member Functions | Private Attributes

ogdf::PlanarAugmentationFix Class Reference

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

#include <ogdf/augmentation/PlanarAugmentationFix.h>

Inheritance diagram for ogdf::PlanarAugmentationFix:
ogdf::AugmentationModule

List of all members.

Public Member Functions

 PlanarAugmentationFix ()
 Creates an instance of planar augmentation with fixed embedding.
 ~PlanarAugmentationFix ()

Protected Member Functions

void doCall (Graph &g, List< edge > &L)
 The implementation of the algorithm call.

Private Member Functions

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

Private Attributes

CombinatorialEmbedding * m_pEmbedding
 The embedding of g.
CombinatorialEmbedding * m_pActEmbedding
 The embedding of the actual partial graph.
Graph * m_pGraph
 The working graph.
List< edge > * m_pResult
 The inserted edges by the algorithm.
DynamicBCTree * m_pBCTree
 The actual dynamic bc-tree.
GraphCopy m_graphCopy
 The actual partial graph.
EdgeArray< edge > m_eCopy
 Edge-array required for construction of the graph copy.
List< label > m_labels
 The list of all labels.
NodeArray< ListIterator< label > > m_isLabel
 Array that contains iterators to the list of labels if a node is a parent of a label.
NodeArray< label > m_belongsTo
 Array that contains the label a node belongs to.
NodeArray< ListIterator< node > > m_belongsToIt
 Array that contains the iterator of the label a node belongs to.
node m_actBCRoot
 The actual root of the bc-tree.

Detailed Description

The algorithm for biconnectivity augmentation with fixed combinatorial embedding.

Definition at line 76 of file PlanarAugmentationFix.h.

Constructor & Destructor Documentation

ogdf::PlanarAugmentationFix::PlanarAugmentationFix (  )  [inline]

Creates an instance of planar augmentation with fixed embedding.

Definition at line 72 of file PlanarAugmentationFix.h.

ogdf::PlanarAugmentationFix::~PlanarAugmentationFix (  )  [inline]

Definition at line 74 of file PlanarAugmentationFix.h.

Member Function Documentation

void ogdf::PlanarAugmentationFix::addPendant ( node  p,
label &  l 
) [private]

Adds pendant p to label l.

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

The main function for planar augmentation.

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

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

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

Connect the two pendants.

void ogdf::PlanarAugmentationFix::connectSingleLabel (  )  [private]

Connects the remaining label.

void ogdf::PlanarAugmentationFix::deleteLabel ( label &  l,
bool  removePendants = true 
) [private]

Deletes the label.

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

Deletes the pendant.

void ogdf::PlanarAugmentationFix::doCall ( Graph &  g,
List< edge > &  L 
) [protected, virtual]

The implementation of the algorithm call.

Parameters:
g is the working graph.
L is the list of all new edges.

Implements ogdf::AugmentationModule.

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

Finds the next matching pendants.

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

Called by findMatching, if a dominating tree was detected.

paStopCause ogdf::PlanarAugmentationFix::followPath ( node  v,
node &  last 
) [private]

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

ListIterator<label> ogdf::PlanarAugmentationFix::insertLabel ( label  l  )  [private]

Inserts the label into the list of labels maintaining decreasing order.

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

Modifies the root of the bc-tree.

label ogdf::PlanarAugmentationFix::newLabel ( node  cutvertex,
node  parent,
node  pendant,
paStopCause  whyStop 
) [private]

Creates a new label.

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

Adds the pendant to a label or creates one (uses followPath()).

void ogdf::PlanarAugmentationFix::removeLabel ( label &  l  )  [private]

Removes the label from the list of labels.

Member Data Documentation

node ogdf::PlanarAugmentationFix::m_actBCRoot [private]

The actual root of the bc-tree.

Definition at line 147 of file PlanarAugmentationFix.h.

NodeArray<label> ogdf::PlanarAugmentationFix::m_belongsTo [private]

Array that contains the label a node belongs to.

Definition at line 137 of file PlanarAugmentationFix.h.

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

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

Definition at line 142 of file PlanarAugmentationFix.h.

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

Edge-array required for construction of the graph copy.

Definition at line 121 of file PlanarAugmentationFix.h.

GraphCopy ogdf::PlanarAugmentationFix::m_graphCopy [private]

The actual partial graph.

Definition at line 116 of file PlanarAugmentationFix.h.

NodeArray< ListIterator<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 132 of file PlanarAugmentationFix.h.

List<label> ogdf::PlanarAugmentationFix::m_labels [private]

The list of all labels.

Definition at line 126 of file PlanarAugmentationFix.h.

CombinatorialEmbedding* ogdf::PlanarAugmentationFix::m_pActEmbedding [private]

The embedding of the actual partial graph.

Definition at line 96 of file PlanarAugmentationFix.h.

DynamicBCTree* ogdf::PlanarAugmentationFix::m_pBCTree [private]

The actual dynamic bc-tree.

Definition at line 111 of file PlanarAugmentationFix.h.

CombinatorialEmbedding* ogdf::PlanarAugmentationFix::m_pEmbedding [private]

The embedding of g.

Definition at line 91 of file PlanarAugmentationFix.h.

Graph* ogdf::PlanarAugmentationFix::m_pGraph [private]

The working graph.

Definition at line 101 of file PlanarAugmentationFix.h.

List<edge>* ogdf::PlanarAugmentationFix::m_pResult [private]

The inserted edges by the algorithm.

Definition at line 106 of file PlanarAugmentationFix.h.

The documentation for this class was generated from the following file:
© 1999-2010 by oreas GmbH, © 2005-2010 by Technische Universität Dortmund, University of Jena and University of Cologne.

Generated on Wed Oct 20 2010 11:14:11 by doxygen 1.7.1.