6 * $Date: 2012-07-02 20:59:27 +0200 (Mon, 02 Jul 2012) $
7 ***************************************************************/
10 * \brief Declaration of class MultiEdgeApproxInserter.
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_MULTI_EDGE_APPROX_INSERTER_H
48 #define OGDF_MULTI_EDGE_APPROX_INSERTER_H
51 #include <ogdf/module/EdgeInsertionModule.h>
52 #include <ogdf/decomposition/StaticPlanarSPQRTree.h>
58 class OGDF_EXPORT MultiEdgeApproxInserter
: public EdgeInsertionModule
61 //! Creates an instance of multi-edge inserter.
62 MultiEdgeApproxInserter();
64 ~MultiEdgeApproxInserter() { }
67 //! Sets the remove-reinsert postprocessing method.
68 void removeReinsertFix(RemoveReinsertType rrOption
) {
69 m_rrOptionFix
= rrOption
;
72 //! Returns the current setting of the remove-reinsert postprocessing method.
73 RemoveReinsertType
removeReinsertFix() const {
77 //! Sets the remove-reinsert postprocessing method.
78 void removeReinsertVar(RemoveReinsertType rrOption
) {
79 m_rrOptionVar
= rrOption
;
82 //! Returns the current setting of the remove-reinsert postprocessing method.
83 RemoveReinsertType
removeReinsertVar() const {
87 //! Sets the option <i>percentMostCrossed</i> to \a percent.
89 * This option determines the portion of most crossed edges used if the remove-reinsert
90 * method is set to #rrMostCrossed. This portion is number of edges * percentMostCrossed() / 100.
92 void percentMostCrossedFix(double percent
) {
93 m_percentMostCrossedFix
= percent
;
96 //! Returns the current setting of option percentMostCrossed.
97 double percentMostCrossedFix() const {
98 return m_percentMostCrossedFix
;
101 //! Sets the option <i>percentMostCrossedVar</i> to \a percent.
103 * This option determines the portion of most crossed edges used if the remove-reinsert
104 * method (variable embedding) is set to #rrMostCrossed. This portion is number of edges * percentMostCrossed() / 100.
106 void percentMostCrossedVar(double percent
) {
107 m_percentMostCrossedVar
= percent
;
110 //! Returns the current setting of option percentMostCrossed (variable embedding).
111 double percentMostCrossedVar() const {
112 return m_percentMostCrossedVar
;
115 void statistics(bool b
) {
119 bool statistics() const {
123 int sumInsertionCosts() const { return m_sumInsertionCosts
; }
124 int sumFEInsertionCosts() const { return m_sumFEInsertionCosts
; }
127 enum PathDir
{ pdLeft
, pdRight
, pdNone
};
128 static PathDir s_oppDir
[3];
131 class EmbeddingPreference
;
134 VertexBlock(node v
, int b
) : m_vertex(v
), m_block(b
) { }
140 //! Implements the algorithm call.
143 const List
<edge
> &origEdges
,
144 bool forbidCrossingGens
,
145 const EdgeArray
<int> *costOrig
,
146 const EdgeArray
<bool> *forbiddenEdgeOrig
,
147 const EdgeArray
<unsigned int> *edgeSubGraph
);
149 MultiEdgeApproxInserter::Block
*constructBlock(int i
);
150 node
copy(node vOrig
, int b
);
152 static bool dfsPathSPQR(node v
, node v2
, edge eParent
, List
<edge
> &path
);
153 int computePathSPQR(int b
, node v
, node w
, int k
);
155 bool dfsPathVertex(node v
, int parent
, int k
, node t
);
156 bool dfsPathBlock(int b
, node parent
, int k
, node t
);
157 void computePathBC(int k
);
159 void embedBlock(int b
, int m
);
160 void recFlipPref(adjEntry adjP
, NodeArray
<EmbeddingPreference
> &pi_pick
, const NodeArray
<bool> &visited
, StaticPlanarSPQRTree
&spqr
);
164 RemoveReinsertType m_rrOptionFix
; //!< The remove-reinsert method for fixed embedding.
165 RemoveReinsertType m_rrOptionVar
; //!< The remove-reinsert method for variable embedding.
166 double m_percentMostCrossedFix
; //!< The portion of most crossed edges considered (fixed embedding).
167 double m_percentMostCrossedVar
; //!< The portion of most crossed edges considered (variable embedding).
168 bool m_statistics
; // !< Generates further statistic information.
170 PlanRep
*m_pPG
; // pointer to plan-rep passed in call
171 const EdgeArray
<int> *m_costOrig
;
173 NodeArray
<SList
<int> > m_compV
; // m_compV[v] = list of blocks containing v
174 Array
<SList
<node
> > m_verticesB
; // m_verticesB[i] = list of vertices in block i
175 Array
<SList
<edge
> > m_edgesB
; // edgesB[i] = list of edges in block i
176 NodeArray
<node
> m_GtoBC
; // temporary mapping of nodes in PG to copies in block
177 NodeArray
<SList
<VertexBlock
> > m_copyInBlocks
; // mapping of nodes in PG to copies in block
179 Array
<edge
> m_edge
; // array of edges to be inserted
180 Array
<List
<VertexBlock
> > m_pathBCs
; // insertion path in BC-tree for each edge
181 Array
<int> m_insertionCosts
; // computed insertion costs for each edge
182 Array
<Block
*> m_block
; // array of blocks
184 // statistics of last run
185 int m_sumInsertionCosts
;
186 int m_sumFEInsertionCosts
;
189 void constructDual(const PlanRep
&PG
);
190 int findShortestPath(node s
, node t
);
192 ConstCombinatorialEmbedding m_E
;
194 FaceArray
<node
> m_faceNode
;
195 AdjEntryArray
<adjEntry
> m_primalAdj
;
200 } // end namespace ogdf