6 * $Date: 2012-07-06 15:04:28 +0200 (Fr, 06. Jul 2012) $
7 ***************************************************************/
10 * \brief Implements class MMSubgraphPlanarizer.
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 ***************************************************************/
43 #include <ogdf/planarity/MMSubgraphPlanarizer.h>
44 #include <ogdf/planarity/FastPlanarSubgraph.h>
45 #include <ogdf/planarity/MMFixedEmbeddingInserter.h>
51 MMSubgraphPlanarizer::MMSubgraphPlanarizer()
53 FastPlanarSubgraph
*s
= new FastPlanarSubgraph();
57 MMFixedEmbeddingInserter
*pInserter
= new MMFixedEmbeddingInserter();
58 pInserter
->removeReinsert(MMEdgeInsertionModule::rrAll
);
59 m_inserter
.set(pInserter
);
65 Module::ReturnType
MMSubgraphPlanarizer::doCall(PlanRepExpansion
&PG
,
67 const EdgeArray
<bool> *forbid
,
72 OGDF_ASSERT(m_permutations
>= 1);
74 List
<edge
> deletedEdges
;
80 List
<edge
> preferedEdges
;
83 edge eOrig
= PG
.originalEdge(e
);
84 if(eOrig
&& (*forbid
)[eOrig
])
85 preferedEdges
.pushBack(e
);
88 retValue
= m_subgraph
.get().call(PG
, preferedEdges
, deletedEdges
, true);
91 retValue
= m_subgraph
.get().call(PG
, deletedEdges
);
94 if(isSolution(retValue
) == false)
97 for(ListIterator
<edge
> it
= deletedEdges
.begin(); it
.valid(); ++it
)
98 *it
= PG
.originalEdge(*it
);
102 for(int i
= 1; i
<= m_permutations
; ++i
)
104 for(ListConstIterator
<edge
> it
= deletedEdges
.begin(); it
.valid(); ++it
)
105 PG
.delCopy(PG
.copy(*it
));
107 deletedEdges
.permute();
110 m_inserter
.get().call(PG
, deletedEdges
, *forbid
);
112 m_inserter
.get().call(PG
, deletedEdges
);
114 crossingNumber
= PG
.computeNumberOfCrossings();
116 if(i
== 1 || crossingNumber
< bestcr
) {
117 bestcr
= crossingNumber
;
118 numNS
= PG
.numberOfNodeSplits();
119 numSN
= PG
.numberOfSplittedNodes();
125 crossingNumber
= bestcr
;