6 * $Date: 2012-07-02 20:59:27 +0200 (Mon, 02 Jul 2012) $
7 ***************************************************************/
10 * \brief planar biconnected augmentation algorithm with fixed
11 * combinatorial embedding.
16 * This file is part of the Open Graph Drawing Framework (OGDF).
20 * See README.txt in the root directory of the OGDF installation for details.
23 * This program is free software; you can redistribute it and/or
24 * modify it under the terms of the GNU General Public License
25 * Version 2 or 3 as published by the Free Software Foundation;
26 * see the file LICENSE.txt included in the packaging of this file
30 * This program is distributed in the hope that it will be useful,
31 * but WITHOUT ANY WARRANTY; without even the implied warranty of
32 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
33 * GNU General Public License for more details.
36 * You should have received a copy of the GNU General Public
37 * License along with this program; if not, write to the Free
38 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
39 * Boston, MA 02110-1301, USA.
41 * \see http://www.gnu.org/copyleft/gpl.html
42 ***************************************************************/
48 #ifndef OGDF_PLANAR_AUGMENTATION_FIX_H
49 #define OGDF_PLANAR_AUGMENTATION_FIX_H
51 #include <ogdf/module/AugmentationModule.h>
52 #include <ogdf/basic/GraphCopy.h>
53 #include <ogdf/internal/augmentation/PALabel.h>
62 * \brief The algorithm for biconnectivity augmentation with fixed combinatorial embedding.
65 class OGDF_EXPORT PlanarAugmentationFix
: public AugmentationModule
{
68 //! Creates an instance of planar augmentation with fixed embedding.
69 PlanarAugmentationFix() { }
71 ~PlanarAugmentationFix() { }
76 * \brief The implementation of the algorithm call.
78 * \param g is the working graph.
79 * \param L is the list of all new edges.
81 void doCall(Graph
& g
, List
<edge
>& L
);
85 * \brief The embedding of g.
87 CombinatorialEmbedding
* m_pEmbedding
;
90 * \brief The embedding of the actual partial graph.
92 CombinatorialEmbedding
* m_pActEmbedding
;
95 * \brief The working graph.
100 * \brief The inserted edges by the algorithm.
102 List
<edge
>* m_pResult
;
105 * \brief The actual dynamic bc-tree.
107 DynamicBCTree
* m_pBCTree
;
110 * \brief The actual partial graph.
112 GraphCopy m_graphCopy
;
115 * \brief Edge-array required for construction of the graph copy.
117 EdgeArray
<edge
> m_eCopy
;
120 * \brief The list of all labels.
122 List
<pa_label
> m_labels
;
125 * \brief Array that contains iterators to the list of labels
126 * if a node is a parent of a label.
128 NodeArray
< ListIterator
<pa_label
> > m_isLabel
;
131 * \brief Array that contains the label a node belongs to.
133 NodeArray
<pa_label
> m_belongsTo
;
136 * \brief Array that contains the iterator of the label a node belongs to.
138 NodeArray
< ListIterator
<node
> > m_belongsToIt
;
141 * \brief The actual root of the bc-tree.
146 * \brief The main function for planar augmentation.
148 void augment(adjEntry adjOuterFace
);
151 * \brief Modifies the root of the bc-tree.
153 void modifyBCRoot(node oldRoot
, node newRoot
);
156 * \brief Exchanges oldRoot by newRoot and updates data structurs in the bc-tree.
158 void changeBCRoot(node oldRoot
, node newRoot
);
161 * \brief Adds the pendant to a label or creates one (uses followPath()).
163 void reduceChain(node pendant
);
166 * \brief Traverses upwards in the bc-tree, starting at the pendant node.
168 paStopCause
followPath(node v
, node
& last
);
171 * \brief Finds the next matching pendants.
173 bool findMatching(node
& pendant1
, node
& pendant2
, adjEntry
& v1
, adjEntry
& v2
);
176 * \brief Called by findMatching, if a dominating tree was detected.
178 void findMatchingRev(node
& pendant1
, node
& pendant2
, adjEntry
& v1
, adjEntry
& v2
);
181 * \brief Creates a new label.
183 pa_label
newLabel(node cutvertex
, node parent
, node pendant
, paStopCause whyStop
);
186 * \brief Adds pendant \a p to label \a l.
188 void addPendant(node p
, pa_label
& l
);
191 * \brief Inserts the label into the list of labels maintaining decreasing order.
193 ListIterator
<pa_label
> insertLabel(pa_label l
);
196 * \brief Connect the two pendants.
198 void connectPendants(node pendant1
, node pendant2
, adjEntry adjV1
, adjEntry adjV2
);
201 * \brief Connects the remaining label.
203 void connectSingleLabel();
206 * \brief Deletes the pendant.
208 void deletePendant(node pendant
);
211 * \brief Deletes the label.
213 void deleteLabel(pa_label
& l
, bool removePendants
= true);
216 * \brief Removes the label from the list of labels.
218 void removeLabel(pa_label
& l
);
220 }; // class PlanarAugmentationFix