ext/OGDF/src/planarity/SubgraphPlanarizer.cpp

   1 /*
   2  * $Revision: 2599 $
   3  *
   4  * last checkin:
   5  *   $Author: chimani $
   6  *   $Date: 2012-07-15 22:39:24 +0200 (So, 15. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Implements class SubgraphPlanarizer.
  11  *
  12  * \author Markus Chimani
  13  *
  14  * \par License:
  15  * This file is part of the Open Graph Drawing Framework (OGDF).
  16  *
  17  * \par
  18  * Copyright (C)<br>
  19  * See README.txt in the root directory of the OGDF installation for details.
  20  *
  21  * \par
  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
  26  * for details.
  27  *
  28  * \par
  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.
  33  *
  34  * \par
  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.
  39  *
  40  * \see  http://www.gnu.org/copyleft/gpl.html
  41  ***************************************************************/
  42
  43 #include <ogdf/planarity/SubgraphPlanarizer.h>
  44 #include <ogdf/planarity/FastPlanarSubgraph.h>
  45 #include <ogdf/planarity/VariableEmbeddingInserter.h>
  46
  47 namespace ogdf
  48 {
  49
  50 SubgraphPlanarizer::SubgraphPlanarizer()
  51 {
  52         FastPlanarSubgraph* s= new FastPlanarSubgraph();
  53         s->runs(100);
  54         m_subgraph.set(s);
  55
  56         VariableEmbeddingInserter* i = new VariableEmbeddingInserter();
  57         i->removeReinsert(VariableEmbeddingInserter::rrAll);
  58         m_inserter.set(i);
  59
  60         m_permutations = 1;
  61         m_setTimeout = true;
  62 }
  63
  64 Module::ReturnType SubgraphPlanarizer::doCall(PlanRep &PG,
  65         int cc,
  66         const EdgeArray<int>  &cost,
  67         const EdgeArray<bool> &forbid,
  68         const EdgeArray<unsigned int>  &subgraphs,
  69         int& crossingNumber)
  70 {
  71         OGDF_ASSERT(m_permutations >= 1);
  72
  73         OGDF_ASSERT(!(useSubgraphs()) || useCost()); // ersetze durch exception handling
  74
  75         double startTime;
  76         usedTime(startTime);
  77
  78         if(m_setTimeout)
  79                 m_subgraph.get().timeLimit(m_timeLimit);
  80
  81         List<edge> deletedEdges;
  82         PG.initCC(cc);
  83         EdgeArray<int> costPG(PG);
  84         edge e;
  85         forall_edges(e,PG)
  86                 costPG[e] = cost[PG.original(e)];
  87         ReturnType retValue = m_subgraph.get().call(PG, costPG, deletedEdges);
  88         if(isSolution(retValue) == false)
  89                 return retValue;
  90
  91         for(ListIterator<edge> it = deletedEdges.begin(); it.valid(); ++it)
  92                 *it = PG.original(*it);
  93
  94         bool foundSolution = false;
  95         CrossingStructure cs;
  96         for(int i = 1; i <= m_permutations; ++i)
  97         {
  98                 const int nG = PG.numberOfNodes();
  99
 100                 for(ListConstIterator<edge> it = deletedEdges.begin(); it.valid(); ++it)
 101                         PG.delCopy(PG.copy(*it));
 102
 103                 deletedEdges.permute();
 104
 105                 if(m_setTimeout)
 106                         m_inserter.get().timeLimit(
 107                                 (m_timeLimit >= 0) ? max(0.0,m_timeLimit - usedTime(startTime)) : -1);
 108
 109                 ReturnType ret;
 110                 if(useForbid()) {
 111                         if(useCost()) {
 112                                 if(useSubgraphs())
 113                                         ret = m_inserter.get().call(PG, cost, forbid, deletedEdges, subgraphs);
 114                                 else
 115                                         ret = m_inserter.get().call(PG, cost, forbid, deletedEdges);
 116                         } else
 117                                 ret = m_inserter.get().call(PG, forbid, deletedEdges);
 118                 } else {
 119                         if(useCost()) {
 120                                 if(useSubgraphs())
 121                                         ret = m_inserter.get().call(PG, cost, deletedEdges, subgraphs);
 122                                 else
 123                                         ret = m_inserter.get().call(PG, cost, deletedEdges);
 124                         } else
 125                                 ret = m_inserter.get().call(PG, deletedEdges);
 126                 }
 127
 128                 if(isSolution(ret) == false)
 129                         continue; // no solution found, that's bad...
 130
 131                 if(!useCost())
 132                         crossingNumber = PG.numberOfNodes() - nG;
 133                 else {
 134                         crossingNumber = 0;
 135                         node n;
 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());
 140                                         if(useSubgraphs()) {
 141                                                 int subgraphCounter = 0;
 142                                                 for(int i=0; i<32; i++) {
 143                                                         if(((subgraphs[e1] & (1<<i))!=0) && ((subgraphs[e2] & (1<<i)) != 0))
 144                                                                 subgraphCounter++;
 145                                                 }
 146                                                 crossingNumber += (subgraphCounter*cost[e1] * cost[e2]);
 147                                         } else
 148                                                 crossingNumber += cost[e1] * cost[e2];
 149                                 }
 150                         }
 151                 }
 152
 153                 if(i == 1 || crossingNumber < cs.weightedCrossingNumber()) {
 154                         foundSolution = true;
 155                         cs.init(PG, crossingNumber);
 156                 }
 157
 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();
 162                 }
 163
 164                 PG.initCC(cc);
 165
 166                 if(m_timeLimit >= 0 && usedTime(startTime) >= m_timeLimit) {
 167                         if(foundSolution == false)
 168                                 return retTimeoutInfeasible; // not able to find a solution...
 169                         break;
 170                 }
 171         }
 172
 173         cs.restore(PG,cc); // restore best solution in PG
 174         crossingNumber = cs.weightedCrossingNumber();
 175
 176         OGDF_ASSERT(isPlanar(PG) == true);
 177
 178         return retFeasible;
 179 }
 180
 181
 182 void SubgraphPlanarizer::CrossingStructure::init(PlanRep &PG, int weightedCrossingNumber)
 183 {
 184         m_weightedCrossingNumber = weightedCrossingNumber;
 185         m_crossings.init(PG.original());
 186
 187         m_numCrossings = 0;
 188         NodeArray<int> index(PG,-1);
 189         node v;
 190         forall_nodes(v,PG)
 191                 if(PG.isDummy(v))
 192                         index[v] = m_numCrossings++;
 193
 194         edge ePG;
 195         forall_edges(ePG,PG)
 196         {
 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()]);
 203                         }
 204                 }
 205         }
 206 }
 207
 208 void SubgraphPlanarizer::CrossingStructure::restore(PlanRep &PG, int cc)
 209 {
 210         //PG.initCC(cc);
 211
 212         Array<node> id2Node(0,m_numCrossings-1,0);
 213
 214         SListPure<edge> edges;
 215         PG.allEdges(edges);
 216
 217         for(SListConstIterator<edge> itE = edges.begin(); itE.valid(); ++itE)
 218         {
 219                 edge ePG = *itE;
 220                 edge e = PG.original(ePG);
 221
 222                 SListConstIterator<int> it;
 223                 for(it = m_crossings[e].begin(); it.valid(); ++it)
 224                 {
 225                         node x = id2Node[*it];
 226                         edge ePGOld = ePG;
 227                         ePG = PG.split(ePG);
 228                         node y = ePG->source();
 229
 230                         if(x == 0) {
 231                                 id2Node[*it] = y;
 232                         } else {
 233                                 PG.moveTarget(ePGOld, x);
 234                                 PG.moveSource(ePG, x);
 235                                 PG.delNode(y);
 236                         }
 237                 }
 238         }
 239 }
 240
 241 } // namspace ogdf