6 * $Date: 2012-07-03 09:54:22 +0200 (Tue, 03 Jul 2012) $
7 ***************************************************************/
10 * \brief Declaration of class SubgraphPlanarizer.
12 * \author Hoi-Ming Wong
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 ***************************************************************/
43 #ifndef OGDF_SUBGRAPH_UPWARD_PLANARIZER_H
44 #define OGDF_SUBGRAPH_UPWARD_PLANARIZER_H
47 #include <ogdf/basic/ModuleOption.h>
48 #include <ogdf/module/AcyclicSubgraphModule.h>
49 #include <ogdf/module/FUPSModule.h>
50 #include <ogdf/module/UpwardEdgeInserterModule.h>
51 #include <ogdf/module/UpwardPlanarizerModule.h>
52 #include <ogdf/upward/UpwardPlanRep.h>
53 #include <ogdf/upward/FUPSSimple.h>
54 #include <ogdf/upward/FixedEmbeddingUpwardEdgeInserter.h>
55 #include <ogdf/decomposition/BCTree.h>
56 #include <ogdf/module/AcyclicSubgraphModule.h>
57 #include <ogdf/layered/GreedyCycleRemoval.h>
64 class OGDF_EXPORT SubgraphUpwardPlanarizer
: public UpwardPlanarizerModule
68 //! Creates an instance of subgraph planarizer.
69 SubgraphUpwardPlanarizer()
73 m_subgraph
.set(new FUPSSimple());
74 m_inserter
.set(new FixedEmbeddingUpwardEdgeInserter());
75 m_acyclicMod
.set(new GreedyCycleRemoval());
78 //! Sets the module option for the computation of the feasible upward planar subgraph.
79 void setSubgraph(FUPSModule
*FUPS
) {
83 //! Sets the module option for the edge insertion module.
84 void setInserter(UpwardEdgeInserterModule
*pInserter
) {
85 m_inserter
.set(pInserter
);
88 //! Sets the module option for acyclic subgraph module.
89 void setAcyclicSubgraphModule(AcyclicSubgraphModule
*acyclicMod
) {
90 m_acyclicMod
.set(acyclicMod
);
93 int runs() {return m_runs
;}
94 void runs(int n
) {m_runs
= n
;}
98 virtual ReturnType
doCall(UpwardPlanRep
&UPR
,
99 const EdgeArray
<int> &cost
,
100 const EdgeArray
<bool> &forbid
);
102 ModuleOption
<FUPSModule
> m_subgraph
; //!< The upward planar subgraph algorithm.
103 ModuleOption
<UpwardEdgeInserterModule
> m_inserter
; //!< The edge insertion module.
104 ModuleOption
<AcyclicSubgraphModule
> m_acyclicMod
; //!<The acyclic subgraph module.
109 void constructComponentGraphs(BCTree
&BC
, NodeArray
<GraphCopy
> &biComps
);
111 //! traversion the BTree and merge the component to a common graph
112 void dfsMerge(const GraphCopy
&GC
,
114 NodeArray
<GraphCopy
> &biComps
,
115 NodeArray
<UpwardPlanRep
> &uprs
,
116 UpwardPlanRep
&UPR_res
,
119 NodeArray
<bool> &nodesDone
);
122 //! add UPR to UPR_res.
123 void merge(const GraphCopy
&GC
,
124 UpwardPlanRep
&UPR_res
,
125 const GraphCopy
&block
,