6 * $Date: 2012-07-12 01:02:21 +0200 (Do, 12. Jul 2012) $
7 ***************************************************************/
10 * \brief declaration of class MMVariableEmbeddingInserter
12 * \author Carsten Gutwenger
15 * This file is part of the Open Graph Drawing Framework (OGDF).
19 * See README.txt in the root directory of the OGDF installation for details.
22 * This program is free software; you can redistribute it and/or
23 * modify it under the terms of the GNU General Public License
24 * Version 2 or 3 as published by the Free Software Foundation;
25 * see the file LICENSE.txt included in the packaging of this file
29 * This program is distributed in the hope that it will be useful,
30 * but WITHOUT ANY WARRANTY; without even the implied warranty of
31 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
32 * GNU General Public License for more details.
35 * You should have received a copy of the GNU General Public
36 * License along with this program; if not, write to the Free
37 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
38 * Boston, MA 02110-1301, USA.
40 * \see http://www.gnu.org/copyleft/gpl.html
41 ***************************************************************/
47 #ifndef OGDF_MM_VARIABLE_EMBEDDING_INSERTER_H
48 #define OGDF_MM_VARIABLE_EMBEDDING_INSERTER_H
52 #include <ogdf/module/MMEdgeInsertionModule.h>
53 #include <ogdf/basic/CombinatorialEmbedding.h>
54 #include <ogdf/basic/FaceArray.h>
55 #include <ogdf/basic/tuples.h>
61 class OGDF_EXPORT NodeSet
;
62 class OGDF_EXPORT StaticPlanarSPQRTree
;
65 //! Minor-monotone edge insertion with variable embedding.
66 class OGDF_EXPORT MMVariableEmbeddingInserter
: public MMEdgeInsertionModule
69 //! Creates a minor-monotone fixed embedding inserter.
70 MMVariableEmbeddingInserter();
73 virtual ~MMVariableEmbeddingInserter() { }
76 //! Sets the remove-reinsert option for postprocessing.
77 void removeReinsert(RemoveReinsertType rrOption
) {
78 m_rrOption
= rrOption
;
81 //! Returns the current setting of the remove-reinsert option.
82 RemoveReinsertType
removeReinsert() const {
87 //! Sets the portion of most crossed edges used during postprocessing.
89 * The value is only used if the remove-reinsert option is set to rrMostCrossed.
90 * The number of edges used in postprocessing is then
91 * number of edges * percentMostCrossed() / 100.
93 void percentMostCrossed(double percent
) {
94 m_percentMostCrossed
= percent
;
97 //! Returns the current setting of the option percentMostCrossed.
98 double percentMostCrossed() const {
99 return m_percentMostCrossed
;
105 class ExpandedSkeleton
;
107 typedef PlanRepExpansion::Crossing Crossing
;
109 struct AnchorNodeInfo
{
110 AnchorNodeInfo() { m_adj_1
= m_adj_2
= 0; }
111 AnchorNodeInfo(adjEntry adj
) {
115 AnchorNodeInfo(adjEntry adj_1
, adjEntry adj_2
) {
124 enum PathType
{ pathToEdge
= 0, pathToSource
= 1, pathToTarget
= 2 };
128 m_addPartLeft(3), m_addPartRight(3),
130 m_src(0,2,0), m_tgt(0,2,0),
134 Array
<SList
<adjEntry
> > m_addPartLeft
;
135 Array
<SList
<adjEntry
> > m_addPartRight
;
136 Array
<List
<Crossing
> > m_paths
;
137 Array
<AnchorNodeInfo
> m_src
;
138 Array
<AnchorNodeInfo
> m_tgt
;
143 * \brief Implementation of algorithm call.
145 * @param PG is the input planarized expansion and will also receive the result.
146 * @param origEdges is the list of original edges (edges in the original graph
147 * of \a PG) that have to be inserted.
148 * @param forbiddenEdgeOrig points to an edge array indicating if an original edge is
149 * forbidden to be crossed.
152 PlanRepExpansion
&PG
,
153 const List
<edge
> &origEdges
,
154 const EdgeArray
<bool> *forbiddenEdgeOrig
);
157 * \brief Collects all anchor nodes (including dummies) of a node.
159 * @param v is the current node when traversing all copy nodes of an original node
160 * that are connected in a tree-wise manner.
161 * @param nodes is assigned the set of anchor nodes.
162 * @param nsParent is the parent node split.
164 void collectAnchorNodes(
167 const PlanRepExpansion::NodeSplit
*nsParent
) const;
170 * \brief Finds the set of anchor nodes of \a src and \a tgt.
172 * @param src is a node in \a PG representing an original node.
173 * @param tgt is a node in \a PG representing an original node.
174 * @param sources ia assigned the set of anchor nodes of \a src's original node.
175 * @param targets ia assigned the set of anchor nodes of \a tgt's original node.
177 void findSourcesAndTargets(
180 NodeSet
&targets
) const;
183 * \brief Returns all anchor nodes of \a vOrig in n\a nodes.
185 * @param vOrig is a node in the original graph.
186 * @param nodes ia assigned the set of anchor nodes.
190 NodeSet
&nodes
) const;
192 static node
commonDummy(
197 * \brief Computes insertion path \a eip.
199 * The possible start and end nodes of the insertion path have to be stored in
200 * \a m_pSources and \a m_pTargets.
201 * @param eip is assigned the insertion path (the crossed edges).
202 * @param vStart is assigned the start point of the insertion path.
203 * @param vEnd is assigned the end point of the insertion path.
205 void insert(List
<Crossing
> &eip
, AnchorNodeInfo
&vStart
, AnchorNodeInfo
&vEnd
);
207 node
prepareAnchorNode(
208 const AnchorNodeInfo
&anchor
,
213 void preprocessInsertionPath(
214 const AnchorNodeInfo
&srcInfo
,
215 const AnchorNodeInfo
&tgtInfo
,
232 AnchorNodeInfo
&infoSrc
,
233 SListPure
<node
> &pseudos
);
235 void insertWithCommonDummy(
242 * \brief Implements vertex case of recursive path search in BC-tree.
244 * @param v is the node in the graph currently visited during BC-tree traversal.
245 * @param parent is the parent block in DFS-traversal.
246 * @param eip is (step-by-step) assigned the insertion path (crossed edges).
247 * @param vStart is assigned the start point of \a eip.
248 * @param vEnd is assigned the end point of \a eip.
250 bool dfsVertex(node v
,
253 AnchorNodeInfo
&vStart
,
254 AnchorNodeInfo
&vEnd
);
257 * \brief Implements block case of recursive path search in BC-tree.
259 * @param i is the block in the graph currently visited during BC-tree traversal.
260 * @param parent is the parent node in DFS-traversal.
261 * @param repS is assigned the representative (nodein the graph) of a source node.
262 * @param eip is (step-by-step) assigned the insertion path (crossed edges).
263 * @param vStart is assigned the start point of \a eip.
264 * @param vEnd is assigned the end point of \a eip.
270 AnchorNodeInfo
&vStart
,
271 AnchorNodeInfo
&vEnd
);
273 bool pathSearch(node v
, edge parent
, const Block
&BC
, List
<edge
> &path
);
276 * \brief Computes optimal insertion path in block \a BC.
278 * @param BC is the block.
279 * @param L is assigned the insertion path (the crossed edges).
280 * @param srcInfo is assigned the start point of the insertion path.
281 * @param tgtInfo is assigned the end point of the insertion path.
286 AnchorNodeInfo
&srcInfo
,
287 AnchorNodeInfo
&tgtInfo
);
297 ExpandedSkeleton
&Exp
);
299 void contractSplitIfReq(node u
);
303 PlanRepExpansion::nodeSplit ns_0
);
305 void writeEip(const List
<Crossing
> &eip
);
307 RemoveReinsertType m_rrOption
; //!< The remove-reinsert option.
308 double m_percentMostCrossed
; //!< The percentMostCrossed option.
310 PlanRepExpansion
*m_pPG
; //!< Pointer to the planarized expansion.
312 NodeSet
*m_pSources
; //!< The set of possible start nodes of an insertion path.
313 NodeSet
*m_pTargets
; //!< The set of possible end nodes of an insertion path.
315 NodeArray
<SList
<int> > m_compV
; //!< The list of blocks containing a node \a v.
316 Array
<SList
<node
> > m_nodeB
; //!< The list of nodes in block \a i.
317 Array
<SList
<edge
> > m_edgeB
; //!< The list of edges in block \a i.
318 NodeArray
<node
> m_GtoBC
; //!< Maps a node in the planarized expansion to the corresponding node in block.
320 bool m_conFinished
; //!< Stores if a possible target node in a block has already been found.
321 const EdgeArray
<bool> *m_forbiddenEdgeOrig
;
324 } // end namespace ogdf