ext/OGDF/src/planarity/MaximumPlanarSubgraph.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 Implementation of class MaximumPlanarSubgraph
  11  *
  12  * \author Karsten Klein
  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  #ifdef USE_ABACUS
  44
  45  #include <ogdf/planarity/MaximumPlanarSubgraph.h>
  46  #include <ogdf/cluster/MaximumCPlanarSubgraph.h>
  47  #include <ogdf/basic/extended_graph_alg.h>
  48  #include <ogdf/basic/simple_graph_alg.h>
  49
  50  namespace ogdf {
  51
  52 Module::ReturnType MaximumPlanarSubgraph::doCall(
  53         const Graph &G,
  54         const List<edge> &preferedEdges,
  55         List<edge> &delEdges,
  56         const EdgeArray<int>  *pCost,
  57         bool preferredImplyPlanar)
  58 {
  59         if (G.numberOfEdges() < 9)
  60                 return retOptimal;
  61
  62         //if the graph is planar, we don't have to do anything
  63         if (isPlanar(G))
  64                 return retOptimal;
  65
  66         //---------
  67         //Exact ILP
  68         MaximumCPlanarSubgraph mc;
  69         List<nodePair> addEdges;
  70
  71         delEdges.clear();
  72
  73         node v;
  74         NodeArray<node> tableNodes(G,0);
  75         EdgeArray<edge> tableEdges(G,0);
  76         NodeArray<bool> mark(G,0);
  77
  78         EdgeArray<int> componentID(G);
  79
  80         // Determine biconnected components
  81         int bcCount = biconnectedComponents(G,componentID);
  82
  83         // Determine edges per biconnected component
  84         Array<SList<edge> > blockEdges(0,bcCount-1);
  85         edge e;
  86         forall_edges(e,G)
  87         {
  88                 if (!e->isSelfLoop())
  89                         blockEdges[componentID[e]].pushFront(e);
  90         }
  91
  92         // Determine nodes per biconnected component.
  93         Array<SList<node> > blockNodes(0,bcCount-1);
  94         int i;
  95         for (i = 0; i < bcCount; i++)
  96         {
  97                 SListIterator<edge> it;
  98                 for (it = blockEdges[i].begin(); it.valid(); ++it)
  99                 {
 100                         e = *it;
 101                         if (!mark[e->source()])
 102                         {
 103                                 blockNodes[i].pushBack(e->source());
 104                                 mark[e->source()] = true;
 105                         }
 106                         if (!mark[e->target()])
 107                         {
 108                                 blockNodes[i].pushBack(e->target());
 109                                 mark[e->target()] = true;
 110                         }
 111                 }
 112                 SListIterator<node> itn;
 113                 for (itn = blockNodes[i].begin(); itn.valid(); ++itn)
 114                         mark[*itn] = false;
 115         }
 116
 117
 118         // Perform computation for every biconnected component
 119         ReturnType mr;
 120
 121         if (bcCount == 1) {
 122                 ClusterGraph CG(G);
 123                 mr = mc.call(CG, delEdges, addEdges);
 124
 125                 return mr;
 126         }
 127         else
 128         {
 129                 for (i = 0; i < bcCount; i++)
 130                 {
 131                         Graph C;
 132
 133                         SListIterator<node> itn;
 134                         for (itn = blockNodes[i].begin(); itn.valid(); ++ itn)
 135                         {
 136                                 v = *itn;
 137                                 node w = C.newNode();
 138                                 tableNodes[v] = w;
 139                         }
 140
 141
 142                         SListIterator<edge> it;
 143                         for (it = blockEdges[i].begin(); it.valid(); ++it)
 144                         {
 145                                 e = *it;
 146                                 edge f = C.newEdge(tableNodes[e->source()],tableNodes[e->target()]);
 147                                 tableEdges[e] = f;
 148                         }
 149
 150                         // Construct a translation table for the edges.
 151                         // Necessary, since edges are deleted in a new graph
 152                         // that represents the current biconnected component
 153                         // of the original graph.
 154                         EdgeArray<edge> backTableEdges(C,0);
 155                         for (it = blockEdges[i].begin(); it.valid(); ++it)
 156                                 backTableEdges[tableEdges[*it]] = *it;
 157
 158                         // The deleted edges of the biconnected component
 159                         List<edge> delEdgesOfBC;
 160
 161                         ClusterGraph CG(C);
 162                         mr = mc.call(CG, delEdgesOfBC, addEdges);
 163                         // Abort if no optimal solution found, i.e., feasible is also not allowed
 164                         if (mr != retOptimal)
 165                                 return mr;
 166
 167                         // Get the original edges that are deleted and
 168                         // put them on the list delEdges.
 169                         while (!delEdgesOfBC.empty())
 170                                 delEdges.pushBack(backTableEdges[delEdgesOfBC.popFrontRet()]);
 171
 172                 }
 173         }
 174         return mr;
 175 }//docall for graph
 176
 177 } //end namespace ogdf
 178
 179 #endif //USE_ABACUS