6 * $Date: 2012-07-15 22:39:24 +0200 (So, 15. Jul 2012) $
7 ***************************************************************/
10 * \brief Implements class SubgraphPlanarizer.
12 * \author Markus Chimani
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 #include <ogdf/planarity/SubgraphPlanarizer.h>
44 #include <ogdf/planarity/FastPlanarSubgraph.h>
45 #include <ogdf/planarity/VariableEmbeddingInserter.h>
50 SubgraphPlanarizer::SubgraphPlanarizer()
52 FastPlanarSubgraph
* s
= new FastPlanarSubgraph();
56 VariableEmbeddingInserter
* i
= new VariableEmbeddingInserter();
57 i
->removeReinsert(VariableEmbeddingInserter::rrAll
);
64 Module::ReturnType
SubgraphPlanarizer::doCall(PlanRep
&PG
,
66 const EdgeArray
<int> &cost
,
67 const EdgeArray
<bool> &forbid
,
68 const EdgeArray
<unsigned int> &subgraphs
,
71 OGDF_ASSERT(m_permutations
>= 1);
73 OGDF_ASSERT(!(useSubgraphs()) || useCost()); // ersetze durch exception handling
79 m_subgraph
.get().timeLimit(m_timeLimit
);
81 List
<edge
> deletedEdges
;
83 EdgeArray
<int> costPG(PG
);
86 costPG
[e
] = cost
[PG
.original(e
)];
87 ReturnType retValue
= m_subgraph
.get().call(PG
, costPG
, deletedEdges
);
88 if(isSolution(retValue
) == false)
91 for(ListIterator
<edge
> it
= deletedEdges
.begin(); it
.valid(); ++it
)
92 *it
= PG
.original(*it
);
94 bool foundSolution
= false;
96 for(int i
= 1; i
<= m_permutations
; ++i
)
98 const int nG
= PG
.numberOfNodes();
100 for(ListConstIterator
<edge
> it
= deletedEdges
.begin(); it
.valid(); ++it
)
101 PG
.delCopy(PG
.copy(*it
));
103 deletedEdges
.permute();
106 m_inserter
.get().timeLimit(
107 (m_timeLimit
>= 0) ? max(0.0,m_timeLimit
- usedTime(startTime
)) : -1);
113 ret
= m_inserter
.get().call(PG
, cost
, forbid
, deletedEdges
, subgraphs
);
115 ret
= m_inserter
.get().call(PG
, cost
, forbid
, deletedEdges
);
117 ret
= m_inserter
.get().call(PG
, forbid
, deletedEdges
);
121 ret
= m_inserter
.get().call(PG
, cost
, deletedEdges
, subgraphs
);
123 ret
= m_inserter
.get().call(PG
, cost
, deletedEdges
);
125 ret
= m_inserter
.get().call(PG
, deletedEdges
);
128 if(isSolution(ret
) == false)
129 continue; // no solution found, that's bad...
132 crossingNumber
= PG
.numberOfNodes() - nG
;
136 forall_nodes(n
, PG
) {
137 if(PG
.original(n
) == 0) { // dummy found -> calc cost
138 edge e1
= PG
.original(n
->firstAdj()->theEdge());
139 edge e2
= PG
.original(n
->lastAdj()->theEdge());
141 int subgraphCounter
= 0;
142 for(int i
=0; i
<32; i
++) {
143 if(((subgraphs
[e1
] & (1<<i
))!=0) && ((subgraphs
[e2
] & (1<<i
)) != 0))
146 crossingNumber
+= (subgraphCounter
*cost
[e1
] * cost
[e2
]);
148 crossingNumber
+= cost
[e1
] * cost
[e2
];
153 if(i
== 1 || crossingNumber
< cs
.weightedCrossingNumber()) {
154 foundSolution
= true;
155 cs
.init(PG
, crossingNumber
);
158 if(localLogMode() == LM_STATISTIC
) {
159 if(m_permutations
<= 200 ||
160 i
<= 10 || (i
<= 30 && (i
% 2) == 0) || (i
> 30 && i
<= 100 && (i
% 5) == 0) || ((i
% 10) == 0))
161 sout() << "\t" << cs
.weightedCrossingNumber();
166 if(m_timeLimit
>= 0 && usedTime(startTime
) >= m_timeLimit
) {
167 if(foundSolution
== false)
168 return retTimeoutInfeasible
; // not able to find a solution...
173 cs
.restore(PG
,cc
); // restore best solution in PG
174 crossingNumber
= cs
.weightedCrossingNumber();
176 OGDF_ASSERT(isPlanar(PG
) == true);
182 void SubgraphPlanarizer::CrossingStructure::init(PlanRep
&PG
, int weightedCrossingNumber
)
184 m_weightedCrossingNumber
= weightedCrossingNumber
;
185 m_crossings
.init(PG
.original());
188 NodeArray
<int> index(PG
,-1);
192 index
[v
] = m_numCrossings
++;
197 if(PG
.original(ePG
->source()) != 0) {
198 edge e
= PG
.original(ePG
);
199 ListConstIterator
<edge
> it
= PG
.chain(e
).begin();
200 for(++it
; it
.valid(); ++it
) {
201 //cout << index[(*it)->source()] << " ";
202 m_crossings
[e
].pushBack(index
[(*it
)->source()]);
208 void SubgraphPlanarizer::CrossingStructure::restore(PlanRep
&PG
, int cc
)
212 Array
<node
> id2Node(0,m_numCrossings
-1,0);
214 SListPure
<edge
> edges
;
217 for(SListConstIterator
<edge
> itE
= edges
.begin(); itE
.valid(); ++itE
)
220 edge e
= PG
.original(ePG
);
222 SListConstIterator
<int> it
;
223 for(it
= m_crossings
[e
].begin(); it
.valid(); ++it
)
225 node x
= id2Node
[*it
];
228 node y
= ePG
->source();
233 PG
.moveTarget(ePGOld
, x
);
234 PG
.moveSource(ePG
, x
);