ext/OGDF/src/upward/FeasibleUpwardPlanarSubgraph.cpp

   1 /*
   2  * $Revision: 2559 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-06 15:04:28 +0200 (Fr, 06. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Implements class UpwardPlanarSubgraphSimple which computes
  11  * an upward planar subgraph of a single-source acyclic digraph
  12  *
  13  * \author Hoi-Ming Wong
  14  *
  15  * \par License:
  16  * This file is part of the Open Graph Drawing Framework (OGDF).
  17  *
  18  * \par
  19  * Copyright (C)<br>
  20  * See README.txt in the root directory of the OGDF installation for details.
  21  *
  22  * \par
  23  * This program is free software; you can redistribute it and/or
  24  * modify it under the terms of the GNU General Public License
  25  * Version 2 or 3 as published by the Free Software Foundation;
  26  * see the file LICENSE.txt included in the packaging of this file
  27  * for details.
  28  *
  29  * \par
  30  * This program is distributed in the hope that it will be useful,
  31  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  32  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  33  * GNU General Public License for more details.
  34  *
  35  * \par
  36  * You should have received a copy of the GNU General Public
  37  * License along with this program; if not, write to the Free
  38  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  39  * Boston, MA 02110-1301, USA.
  40  *
  41  * \see  http://www.gnu.org/copyleft/gpl.html
  42  ***************************************************************/
  43
  44 #include <ogdf/upward/FeasibleUpwardPlanarSubgraph.h>
  45 #include <ogdf/upward/UpwardPlanarModule.h>
  46 #include <ogdf/upward/FaceSinkGraph.h>
  47 #include <ogdf/basic/simple_graph_alg.h>
  48
  49 namespace ogdf {
  50
  51
  52 Module::ReturnType FeasibleUpwardPlanarSubgraph::call(
  53         Graph &G,
  54         GraphCopy &FUPS,
  55         adjEntry &extFaceHandle,
  56         List<edge> &delEdges,
  57         bool multisources,
  58         int runs)
  59 {
  60
  61 #ifdef OGDF_DEBUG
  62         UpwardPlanarModule upMod;
  63         OGDF_ASSERT(!upMod.upwardPlanarityTest(G));
  64 #endif
  65
  66         delEdges.clear();
  67
  68         //current fups, its embedding and the removed edges
  69         GraphCopy FUPS_cur;
  70         List<edge> delEdges_cur;
  71
  72         call(G, FUPS, extFaceHandle, delEdges, multisources);
  73
  74         for (int i = 1; i < runs; ++i) {
  75                 adjEntry extFaceHandle_cur;
  76                 call(G, FUPS_cur, extFaceHandle_cur, delEdges_cur, multisources);
  77
  78                 // use new result??
  79                 if (delEdges_cur.size() < delEdges.size()) {
  80                         FUPS = FUPS_cur;
  81                         extFaceHandle = FUPS.copy(FUPS_cur.original(extFaceHandle_cur->theEdge()))->adjSource();
  82                         delEdges = delEdges_cur;
  83                 }
  84         }
  85         return Module::retFeasible;
  86 }
  87
  88
  89 Module::ReturnType FeasibleUpwardPlanarSubgraph::call(
  90         const Graph &G,
  91         GraphCopy &FUPS,
  92         adjEntry &extFaceHandle,
  93         List<edge> &delEdges,
  94         bool multisources)
  95 {
  96         FUPS = GraphCopy(G);
  97         delEdges.clear();
  98         node s_orig;
  99         hasSingleSource(G, s_orig);
 100         List<edge> nonTreeEdges_orig;
 101         getSpanTree(FUPS, nonTreeEdges_orig, true, multisources);
 102         CombinatorialEmbedding Gamma(FUPS);
 103         nonTreeEdges_orig.permute(); // random order
 104
 105         //insert nonTreeEdges
 106         UpwardPlanarModule upMod;
 107         while (!nonTreeEdges_orig.empty()) {
 108                 // make identical copy GC of Fups
 109                 //and insert e_orig in GC
 110                 GraphCopy GC = FUPS;
 111                 edge e_orig = nonTreeEdges_orig.popFrontRet();
 112                 //node a = GC.copy(e_orig->source());
 113                 //node b = GC.copy(e_orig->target());
 114                 GC.newEdge(e_orig);
 115
 116                 if (upMod.upwardPlanarEmbed(GC)) { //upward embedded the fups and check feasibility
 117                         CombinatorialEmbedding Beta(GC);
 118
 119                         //choose a arbitrary feasibel ext. face
 120                         FaceSinkGraph fsg(Beta, GC.copy(s_orig));
 121                         SList<face> ext_faces;
 122                         fsg.possibleExternalFaces(ext_faces);
 123                         OGDF_ASSERT(!ext_faces.empty());
 124                         Beta.setExternalFace(ext_faces.front());
 125
 126                         GraphCopy M = GC; // use a identical copy of GC to constrcut the merge graph of GC
 127                         adjEntry extFaceHandle_cur = getAdjEntry(Beta, GC.copy(s_orig), Beta.externalFace());
 128                         adjEntry adj_orig = GC.original(extFaceHandle_cur->theEdge())->adjSource();
 129
 130                         if (constructMergeGraph(M, adj_orig, nonTreeEdges_orig)) {
 131                                 FUPS = GC;
 132                                 extFaceHandle = FUPS.copy(GC.original(extFaceHandle_cur->theEdge()))->adjSource();
 133                                 continue;
 134                         }
 135                         else {
 136                                 //Beta is not feasible
 137                                 delEdges.pushBack(e_orig);
 138                         }
 139                 }
 140                 else {
 141                         // not ok, GC is not feasible
 142                         delEdges.pushBack(e_orig);
 143                 }
 144         }
 145
 146         return Module::retFeasible;
 147 }
 148
 149
 150 void FeasibleUpwardPlanarSubgraph::getSpanTree(GraphCopy &GC, List<edge> &delEdges, bool random, bool multisource)
 151 {
 152         delEdges.clear();
 153         if (GC.numberOfNodes() == 1)
 154                 return; // nothing to do
 155         node s;
 156         hasSingleSource(GC, s);
 157         NodeArray<bool> visited(GC, false);
 158         EdgeArray<bool> isTreeEdge(GC,false);
 159         List<node> toDo;
 160
 161         // the original graph is a multisource graph. The sources are connected with the super source s.
 162         // so do not delete the incident edges of s
 163         if (multisource){
 164                 // put all incident edges of the source to treeEdges
 165                 adjEntry adj;
 166                 forall_adj(adj, s) {
 167                         isTreeEdge[adj->theEdge()] = true;
 168                         visited[adj->theEdge()->target()];
 169                         toDo.pushBack(adj->theEdge()->target());
 170                 }
 171         }
 172         else
 173                 toDo.pushBack(s);
 174
 175
 176         //traversing with dfs
 177         forall_listiterators(node, it, toDo) {
 178                 node start = *it;
 179                 adjEntry adj;
 180                 forall_adj(adj, start) {
 181                         node v = adj->theEdge()->target();
 182                         if (!visited[v])
 183                                 dfs_visit(GC, adj->theEdge(), visited, isTreeEdge, random);
 184                 }
 185         }
 186
 187         // delete all non tree edgesEdges to obtain a span tree
 188         List<edge> l;
 189         edge e;
 190         forall_edges(e, GC) {
 191                 if (!isTreeEdge[e])
 192                         l.pushBack(e);
 193         }
 194         while (!l.empty()) {
 195                 e = l.popFrontRet();
 196                 delEdges.pushBack(GC.original(e));
 197                 GC.delCopy(e);
 198         }
 199 }
 200
 201
 202
 203 void FeasibleUpwardPlanarSubgraph::dfs_visit(
 204         const Graph &G,
 205         edge e,
 206         NodeArray<bool> &visited,
 207         EdgeArray<bool> &treeEdges,
 208         bool random)
 209 {
 210         treeEdges[e] = true;
 211         List<edge> elist;
 212         G.outEdges(e->target(), elist);
 213         if (!elist.empty()) {
 214                 if (random)
 215                         elist.permute();
 216                 ListIterator<edge> it;
 217                 for (it = elist.begin(); it.valid(); ++it) {
 218                         edge ee = *it;
 219                         if (!visited[ee->target()])
 220                                 dfs_visit(G, ee, visited, treeEdges, random);
 221                 }
 222         }
 223         visited[e->target()] = true;
 224 }
 225
 226
 227 bool FeasibleUpwardPlanarSubgraph::constructMergeGraph(
 228         GraphCopy &M,
 229         adjEntry adj_orig,
 230         const List<edge> &orig_edges)
 231 {
 232         CombinatorialEmbedding Beta(M);
 233
 234         //set ext. face of Beta
 235         adjEntry ext_adj = M.copy(adj_orig->theEdge())->adjSource();
 236         Beta.setExternalFace(Beta.rightFace(ext_adj));
 237
 238         FaceSinkGraph fsg(Beta, M.copy(adj_orig->theNode()));
 239         SList<node> aug_nodes;
 240         SList<edge> aug_edges;
 241         SList<face> fList;
 242         fsg.possibleExternalFaces(fList); // use this method to call the methode checkForest()
 243         node v_ext = fsg.faceNodeOf(Beta.externalFace());
 244
 245         OGDF_ASSERT(v_ext != 0);
 246
 247         fsg.stAugmentation(v_ext, M, aug_nodes, aug_edges);
 248
 249         //add the deleted edges
 250         forall_listiterators(edge, it, orig_edges) {
 251                 node a = M.copy((*it)->source());
 252                 node b = M.copy((*it)->target());
 253                 M.newEdge(a, b);
 254         }
 255         return (isAcyclic(M));
 256 }
 257
 258
 259
 260
 261 } // end namespace ogdf
 262