ext/OGDF/src/planarity/FastPlanarSubgraph.cpp

   1 /*
   2  * $Revision: 2565 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-07 17:14:54 +0200 (Sa, 07. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Implementation of the FastPlanarSubgraph.
  11  *
  12  * Class is derived from base class PlanarSubgraphModule
  13  * and implements the interface for the Planarization algorithm
  14  * based on PQ-trees.
  15  *
  16  * \author Sebastian Leipert
  17  *
  18  * \par License:
  19  * This file is part of the Open Graph Drawing Framework (OGDF).
  20  *
  21  * \par
  22  * Copyright (C)<br>
  23  * See README.txt in the root directory of the OGDF installation for details.
  24  *
  25  * \par
  26  * This program is free software; you can redistribute it and/or
  27  * modify it under the terms of the GNU General Public License
  28  * Version 2 or 3 as published by the Free Software Foundation;
  29  * see the file LICENSE.txt included in the packaging of this file
  30  * for details.
  31  *
  32  * \par
  33  * This program is distributed in the hope that it will be useful,
  34  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  35  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  36  * GNU General Public License for more details.
  37  *
  38  * \par
  39  * You should have received a copy of the GNU General Public
  40  * License along with this program; if not, write to the Free
  41  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  42  * Boston, MA 02110-1301, USA.
  43  *
  44  * \see  http://www.gnu.org/copyleft/gpl.html
  45  ***************************************************************/
  46
  47
  48 #include <ogdf/basic/basic.h>
  49 #include <ogdf/basic/Array.h>
  50 #include <ogdf/basic/SList.h>
  51 #include <ogdf/basic/simple_graph_alg.h>
  52 #include <ogdf/basic/extended_graph_alg.h>
  53 #include <ogdf/internal/planarity/PlanarSubgraphPQTree.h>
  54 #include <ogdf/internal/planarity/PlanarLeafKey.h>
  55 #include <ogdf/planarity/FastPlanarSubgraph.h>
  56
  57
  58 namespace ogdf{
  59
  60 // Prepares the planarity test and the planar embedding
  61 Module::ReturnType FastPlanarSubgraph::doCall(
  62         const Graph &G,
  63         const List<edge> & /*preferedEdges*/,
  64         List<edge> &delEdges,
  65         const EdgeArray<int>  *pCost,
  66         bool /*preferedImplyPlanar*/)
  67 {
  68
  69         delEdges.clear();
  70
  71         if (G.numberOfEdges() < 9)
  72                 return retOptimal;
  73
  74
  75         node v;
  76         NodeArray<node> tableNodes(G,0);
  77         EdgeArray<edge> tableEdges(G,0);
  78         NodeArray<bool> mark(G,0);
  79
  80         EdgeArray<int> componentID(G);
  81
  82
  83         // Determine Biconnected Components
  84         int bcCount = biconnectedComponents(G,componentID);
  85
  86         // Determine edges per biconnected component
  87         Array<SList<edge> > blockEdges(0,bcCount-1);
  88         edge e;
  89         forall_edges(e,G)
  90         {
  91                 if (!e->isSelfLoop())
  92                         blockEdges[componentID[e]].pushFront(e);
  93         }
  94
  95         // Determine nodes per biconnected component.
  96         Array<SList<node> > blockNodes(0,bcCount-1);
  97         int i;
  98         for (i = 0; i < bcCount; i++)
  99         {
 100                 SListIterator<edge> it;
 101                 for (it = blockEdges[i].begin(); it.valid(); ++it)
 102                 {
 103                         e = *it;
 104                         if (!mark[e->source()])
 105                         {
 106                                 blockNodes[i].pushBack(e->source());
 107                                 mark[e->source()] = true;
 108                         }
 109                         if (!mark[e->target()])
 110                         {
 111                                 blockNodes[i].pushBack(e->target());
 112                                 mark[e->target()] = true;
 113                         }
 114                 }
 115                 SListIterator<node> itn;
 116                 for (itn = blockNodes[i].begin(); itn.valid(); ++itn)
 117                         mark[*itn] = false;
 118         }
 119
 120
 121         // Perform Planarization for every biconnected component
 122
 123         if (bcCount == 1) {
 124                 if (G.numberOfEdges() > 4)
 125                         computeDelEdges(G,pCost,0,delEdges);
 126
 127         } else {
 128                 for (i = 0; i < bcCount; i++)
 129                 {
 130                         Graph C;
 131
 132                         SListIterator<node> itn;
 133                         for (itn = blockNodes[i].begin(); itn.valid(); ++ itn)
 134                         {
 135                                 v = *itn;
 136                                 node w = C.newNode();
 137                                 tableNodes[v] = w;
 138                         }
 139
 140
 141                         SListIterator<edge> it;
 142                         for (it = blockEdges[i].begin(); it.valid(); ++it)
 143                         {
 144                                 e = *it;
 145                                 edge f = C.newEdge(tableNodes[e->source()],tableNodes[e->target()]);
 146                                 tableEdges[e] = f;
 147                         }
 148
 149                         // Construct a translation table for the edges.
 150                         // Necessary, since edges are deleted in a new graph.
 151                         // that represents the biconnectedcomponent of the original graph.
 152                         EdgeArray<edge> backTableEdges(C,0);
 153                         for (it = blockEdges[i].begin(); it.valid(); ++it)
 154                                 backTableEdges[tableEdges[*it]] = *it;
 155
 156                         // gets the deletec Edges of the biconnected component
 157                         List<edge> delEdgesOfBC;
 158
 159
 160                         if (C.numberOfEdges() > 4)
 161                                 computeDelEdges(C,pCost,&backTableEdges,delEdgesOfBC);
 162
 163                         // get the original edges that are deleted and
 164                         // put them on the list delEdges.
 165                         while (!delEdgesOfBC.empty())
 166                                 delEdges.pushBack(backTableEdges[delEdgesOfBC.popFrontRet()]);
 167
 168                 }
 169         }
 170
 171         return retFeasible;
 172 }
 173
 174
 175 void FastPlanarSubgraph::computeDelEdges(
 176         const Graph &G,
 177         const EdgeArray<int>  *pCost,
 178         const EdgeArray<edge> *backTableEdges,
 179         List<edge> &delEdges)
 180 {
 181         if (m_nRuns <= 0)
 182         {
 183                 // Compute st-numbering
 184                 NodeArray<int> numbering(G,0);
 185                 stNumber(G,numbering);
 186
 187                 planarize(G,numbering,delEdges);
 188
 189         } else {
 190                 int bestSolution = INT_MAX;
 191
 192                 for(int i = 1; i <= m_nRuns && bestSolution > 1; ++i)
 193                 {
 194                         List<edge> currentDelEdges;
 195
 196                         // Compute (randomized) st-numbering
 197                         NodeArray<int> numbering(G,0);
 198                         stNumber(G,numbering,0,0,true);
 199
 200                         planarize(G,numbering,currentDelEdges);
 201
 202                         if(pCost == 0)
 203                         {
 204                                 int currentSolution = currentDelEdges.size();
 205
 206                                 if(currentSolution < bestSolution) {
 207                                         bestSolution = currentSolution;
 208                                         delEdges.clear();
 209                                         delEdges.conc(currentDelEdges);
 210                                 }
 211
 212                         } else {
 213                                 int currentSolution = 0;
 214                                 ListConstIterator<edge> it;
 215                                 for(it = currentDelEdges.begin(); it.valid(); ++it)
 216                                         if(backTableEdges != 0)
 217                                                 currentSolution += (*pCost)[(*backTableEdges)[*it]];
 218                                         else
 219                                                 currentSolution += (*pCost)[*it];
 220
 221                                 if(currentSolution < bestSolution) {
 222                                         bestSolution = currentSolution;
 223                                         delEdges.clear();
 224                                         delEdges.conc(currentDelEdges);
 225
 226                                 }
 227                         }
 228                 }
 229         }
 230 }
 231
 232
 233
 234 // Performs a planarity test on a biconnected component
 235 // of G. numbering contains an st-numbering of the component.
 236 void FastPlanarSubgraph::planarize(
 237         const Graph &G,
 238         NodeArray<int> &numbering,
 239         List<edge> &delEdges)
 240 {
 241         node v;
 242
 243         NodeArray<SListPure<PlanarLeafKey<whaInfo*>* > > inLeaves(G);
 244         NodeArray<SListPure<PlanarLeafKey<whaInfo*>* > > outLeaves(G);
 245         Array<node> table(G.numberOfNodes()+1);
 246
 247         forall_nodes(v,G)
 248         {
 249                 edge e;
 250                 forall_adj_edges(e,v)
 251                 {
 252                         if (numbering[e->opposite(v)] > numbering[v])
 253                                 // sideeffect: ignores selfloops
 254                         {
 255                                 PlanarLeafKey<whaInfo*>* L = OGDF_NEW PlanarLeafKey<whaInfo*>(e);
 256                                 inLeaves[v].pushFront(L);
 257                         }
 258                 }
 259                 table[numbering[v]] = v;
 260         }
 261
 262         forall_nodes(v,G)
 263         {
 264                 SListIterator<PlanarLeafKey<whaInfo*>* > it;
 265                 for (it = inLeaves[v].begin(); it.valid(); ++it)
 266                 {
 267                         PlanarLeafKey<whaInfo*>* L = *it;
 268                         outLeaves[L->userStructKey()->opposite(v)].pushFront(L);
 269                 }
 270         }
 271
 272         SList<PQLeafKey<edge,whaInfo*,bool>*> totalEliminatedKeys;
 273
 274         PlanarSubgraphPQTree T;
 275         T.Initialize(inLeaves[table[1]]);
 276         for (int i = 2; i < G.numberOfNodes(); i++)
 277         {
 278                 SList<PQLeafKey<edge,whaInfo*,bool>*> eliminatedKeys;
 279                 T.Reduction(outLeaves[table[i]],eliminatedKeys);
 280
 281                 totalEliminatedKeys.conc(eliminatedKeys);
 282                 T.ReplaceRoot(inLeaves[table[i]]);
 283                 T.emptyAllPertinentNodes();
 284         }
 285
 286
 287         SListIterator<PQLeafKey<edge,whaInfo*,bool>* > it;
 288         for (it = totalEliminatedKeys.begin(); it.valid(); ++it)
 289         {
 290                 edge e = (*it)->userStructKey();
 291                 delEdges.pushBack(e);
 292         }
 293
 294         //cleanup
 295         forall_nodes(v,G)
 296         {
 297                 while (!inLeaves[v].empty())
 298                 {
 299                         PlanarLeafKey<whaInfo*>* L = inLeaves[v].popFrontRet();
 300                         delete L;
 301                 }
 302         }
 303
 304         T.Cleanup();    // Explicit call for destructor necessary. This allows to call virtual
 305                                         // funtion CleanNode for freeing node information class.
 306 }
 307
 308
 309 }