|
|||
|
|
|
|||
|
|
#include <PlanarAugmentation.h>
Public Member Functions | |
| PlanarAugmentation () | |
| Creates an instance of the planar augmentation algorithm. | |
| ~PlanarAugmentation () | |
Protected Member Functions | |
| void | doCall (Graph &G, List< edge > &L) |
| The implementation of the algorithm call. | |
Private Member Functions | |
| void | augment () |
| The main function for planar augmentation. | |
| void | makeConnectedByPendants () |
| ;akes the graph connected by new edges between pendants of the connected components | |
| void | reduceChain (node p, label labelOld=0) |
| Is called for every pendant-node. It traverses to the root and creates a label or updates one. | |
| paStopCause | followPath (node v, node &last) |
| Is called in reduceChain. It traverses to the root and checks several stop conditions. | |
| bool | planarityCheck (node v1, node v2) |
| Checks planarity for a new edge (v1,v2) in the original graph. | |
| node | adjToCutvertex (node v, node cutvertex=0) |
| Returns a node that belongs to bc-node v and is adjacent to the cutvertex. | |
| node | findLastBefore (node pendant, node ancestor) |
| Traverses from pendant to ancestor and returns the last node before ancestor on the path. | |
| void | deletePendant (node p, bool removeFromLabel=true) |
| Deletes the pendant p, removes it from the corresponding label and updates the label-order. | |
| void | addPendant (node p, label &l) |
| Adds a pendant p to the label l and updates the label-order. | |
| edge | connectPendants (node pendant1, node pendant2) |
| Connects two pendants. | |
| void | removeAllPendants (label &l) |
| Removes all pendants of a label. | |
| void | joinPendants (label &l) |
| Connects all pendants of label l with new edges. | |
| void | connectInsideLabel (label &l) |
| Connects the only pendant of l with a computed ancestor. | |
| ListIterator< label > | insertLabel (label l) |
| Inserts label l into m_labels by decreasing order. | |
| void | deleteLabel (label &l, bool removePendants=true) |
| deletes label l. | |
| void | connectLabels (label first, label second) |
| Inserts edges between pendants of label first and second. first.size() is gerater than second.size() or equal. | |
| label | newLabel (node cutvertex, node p, paStopCause whyStop) |
| Creates a new label and inserts it into m_labels. | |
| bool | findMatching (label &first, label &second) |
| Finds two matching labels, so all pendants can be connected without losing planarity. | |
| bool | connectCondition (label a, label b) |
| Checks if the pendants of label a and label b can be connected without creating a new pendant. | |
| void | updateAdjNonChildren (node newBlock, SList< node > &path) |
| Updates the adjNonChildren-data. | |
| void | modifyBCRoot (node oldRoot, node newRoot) |
| Modifies the root of the BC-Tree that newRoot replaces oldRoot. | |
| void | updateNewEdges (SList< edge > *newEdges) |
| Major updates caused by the new edges. | |
| void | terminate () |
| Cleanup. | |
Private Attributes | |
| int | m_nPlanarityTests |
| Counts the number of planarity tests. | |
| Graph * | m_pGraph |
| The working graph. | |
| DynamicBCTree * | m_pBCTree |
| The corresponding BC-Tree. | |
| List< edge > * | m_pResult |
| The inserted edges by the algorithm. | |
| List< label > | m_labels |
| The list of all labels, sorted by size (decreasing). | |
| List< node > | m_pendants |
| The list of all pendants (leaves in the BC-Tree). | |
| List< node > | m_pendantsToDel |
| The list of pendants that has to be deleted after each reduceChain. | |
| NodeArray< label > | m_belongsTo |
| The label a BC-Node belongs to. | |
| NodeArray< ListIterator< label > > | m_isLabel |
| The list iterator in m_labels if the node in the BC-Tree is a label. | |
| 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. | |
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 171 of file PlanarAugmentation.h.
| ogdf::PlanarAugmentation::PlanarAugmentation | ( | ) | [inline] |
Creates an instance of the planar augmentation algorithm.
Definition at line 175 of file PlanarAugmentation.h.
| ogdf::PlanarAugmentation::~PlanarAugmentation | ( | ) | [inline] |
Definition at line 177 of file PlanarAugmentation.h.
The implementation of the algorithm call.
| G | is the working graph. | |
| L | is the list of all new edges. |
Implements ogdf::AugmentationModule.
| void ogdf::PlanarAugmentation::augment | ( | ) | [private] |
The main function for planar augmentation.
| void ogdf::PlanarAugmentation::makeConnectedByPendants | ( | ) | [private] |
;akes the graph connected by new edges between pendants of the connected components
Is called for every pendant-node. It traverses to the root and creates a label or updates one.
| p | is a pendant in the BC-Tree. | |
| labelOld | is the old label of p. |
| paStopCause ogdf::PlanarAugmentation::followPath | ( | node | v, | |
| node & | last | |||
| ) | [private] |
Is called in reduceChain. It traverses to the root and checks several stop conditions.
| v | is a node of the BC-Tree. | |
| last | is the last found C-vertex in the BC-Tree, is modified by the method. |
Checks planarity for a new edge (v1,v2) in the original graph.
| v1,\ | v2 are nodes of the original graph. |
Returns a node that belongs to bc-node v and is adjacent to the cutvertex.
| v | is a node in the BC-Tree. | |
| cutvertex | is the last cutvertex found. |
Traverses from pendant to ancestor and returns the last node before ancestor on the path.
| void ogdf::PlanarAugmentation::deletePendant | ( | node | p, | |
| bool | removeFromLabel = true | |||
| ) | [private] |
Deletes the pendant p, removes it from the corresponding label and updates the label-order.
Adds a pendant p to the label l and updates the label-order.
Connects two pendants.
| void ogdf::PlanarAugmentation::removeAllPendants | ( | label & | l | ) | [private] |
Removes all pendants of a label.
| void ogdf::PlanarAugmentation::joinPendants | ( | label & | l | ) | [private] |
Connects all pendants of label l with new edges.
| void ogdf::PlanarAugmentation::connectInsideLabel | ( | label & | l | ) | [private] |
Connects the only pendant of l with a computed ancestor.
| ListIterator<label> ogdf::PlanarAugmentation::insertLabel | ( | label | l | ) | [private] |
Inserts label l into m_labels by decreasing order.
| void ogdf::PlanarAugmentation::deleteLabel | ( | label & | l, | |
| bool | removePendants = true | |||
| ) | [private] |
deletes label l.
Inserts edges between pendants of label first and second. first.size() is gerater than second.size() or equal.
| label ogdf::PlanarAugmentation::newLabel | ( | node | cutvertex, | |
| node | p, | |||
| paStopCause | whyStop | |||
| ) | [private] |
Creates a new label and inserts it into m_labels.
Finds two matching labels, so all pendants can be connected without losing planarity.
| first | is the label with maximum size, modified by the function. | |
| second | is the matching label, modified by the function: 0 if no matching is found. |
Checks if the pendants of label a and label b can be connected without creating a new pendant.
| void ogdf::PlanarAugmentation::updateAdjNonChildren | ( | node | newBlock, | |
| SList< node > & | path | |||
| ) | [private] |
Updates the adjNonChildren-data.
| newBlock | is a new created block of the BC-Tree. | |
| path | is the path in the BC-Tree between the two connected nodes. |
Modifies the root of the BC-Tree that newRoot replaces oldRoot.
Major updates caused by the new edges.
| newEdges | is a list of all new edges. |
| void ogdf::PlanarAugmentation::terminate | ( | ) | [private] |
Cleanup.
int ogdf::PlanarAugmentation::m_nPlanarityTests [private] |
Graph* ogdf::PlanarAugmentation::m_pGraph [private] |
DynamicBCTree* ogdf::PlanarAugmentation::m_pBCTree [private] |
List<edge>* ogdf::PlanarAugmentation::m_pResult [private] |
List<label> ogdf::PlanarAugmentation::m_labels [private] |
The list of all labels, sorted by size (decreasing).
Definition at line 212 of file PlanarAugmentation.h.
List<node> ogdf::PlanarAugmentation::m_pendants [private] |
The list of all pendants (leaves in the BC-Tree).
Definition at line 216 of file PlanarAugmentation.h.
List<node> ogdf::PlanarAugmentation::m_pendantsToDel [private] |
The list of pendants that has to be deleted after each reduceChain.
Definition at line 221 of file PlanarAugmentation.h.
NodeArray<label> ogdf::PlanarAugmentation::m_belongsTo [private] |
NodeArray< ListIterator<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 230 of file PlanarAugmentation.h.
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 dependancies beteween bc-nodes. The adjacencies in the bc-tree won't be updated.
Definition at line 239 of file PlanarAugmentation.h.
