ext/OGDF/src/decomposition/NonPlanarCore.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 the class NonPlanarCore.
  11  *
  12  * \author Carsten Gutwenger
  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
  44 #include <ogdf/planarity/NonPlanarCore.h>
  45 #include <ogdf/decomposition/StaticSPQRTree.h>
  46 #include <ogdf/basic/extended_graph_alg.h>
  47 #include <ogdf/basic/Queue.h>
  48 #include <ogdf/basic/CombinatorialEmbedding.h>
  49 #include <ogdf/basic/FaceArray.h>
  50
  51
  52 namespace ogdf {
  53
  54
  55 NonPlanarCore::NonPlanarCore(const Graph &G) : m_pOriginal(&G), m_orig(m_graph),
  56         m_real(m_graph,0), m_mincut(m_graph), m_cost(m_graph)
  57 {
  58         if(G.numberOfNodes() <= 4)
  59                 return; // nothing to do; planar graph => empty core
  60
  61         // Build SPQR-tree of graph
  62         StaticSPQRTree T(G);
  63
  64         // mark tree nodes in the core
  65         NodeArray<bool> mark;
  66         markCore(T,mark);
  67
  68         NodeArray<node> map(G,0);
  69         NodeArray<node> mapAux(G,0);
  70         const Graph &tree = T.tree();
  71
  72         node v;
  73         forall_nodes(v,tree) {
  74                 if(mark[v] == false)
  75                         continue;
  76
  77                 Skeleton &S = T.skeleton(v);
  78                 edge e;
  79                 forall_edges(e,S.getGraph()) {
  80                         node src = S.original(e->source());
  81                         node tgt = S.original(e->target());
  82
  83                         if(map[src] == 0) {
  84                                 m_orig[map[src] = m_graph.newNode()] = S.original(e->source());
  85                         }
  86                         if(map[tgt] == 0) {
  87                                 m_orig[map[tgt] = m_graph.newNode()] = S.original(e->target());
  88                         }
  89
  90                         if(S.isVirtual(e)) {
  91                                 node w = S.twinTreeNode(e);
  92                                 if(mark[w] == false) {
  93                                         // new virtual edge in core graph
  94                                         edge eC = m_graph.newEdge(map[src],map[tgt]);
  95                                         traversingPath(S,e,m_mincut[eC],mapAux);
  96                                 }
  97
  98                         } else {
  99                                 // new real edge in core graph
 100                                 edge eC = m_graph.newEdge(map[src],map[tgt]);
 101                                 m_real[eC] = S.realEdge(e);
 102                                 m_mincut[eC].pushBack(S.realEdge(e));
 103                         }
 104                 }
 105         }
 106
 107         edge e;
 108         forall_edges(e, m_graph) {
 109                 m_cost[e] = m_mincut[e].size();
 110         }
 111 }
 112
 113
 114 // This function marks all nodes in the SPQR-tree which induce the
 115 // non-planar core.
 116 void NonPlanarCore::markCore(const SPQRTree &T, NodeArray<bool> &mark)
 117 {
 118         const Graph &tree = T.tree();
 119
 120         // We mark every tree node that belongs to the core
 121         mark.init(tree,true);  // start with all nodes and unmark planar leaves
 122         NodeArray<int> degree(tree);
 123
 124         Queue<node> Q;
 125
 126         node v;
 127         forall_nodes(v,tree) {
 128                 degree[v] = v->degree();
 129                 if(degree[v] <= 1) // also append deg-0 node (T has only one node)
 130                         Q.append(v);
 131         }
 132
 133         while(!Q.empty())
 134         {
 135                 v = Q.pop();
 136
 137                 // if v has a planar skeleton
 138                 if(T.typeOf(v) != SPQRTree::RNode ||
 139                         isPlanar(T.skeleton(v).getGraph()) == true)
 140                 {
 141                         mark[v] = false; // unmark this leaf
 142
 143                         node w = 0;
 144                         adjEntry adj;
 145                         forall_adj(adj,v) {
 146                                 node x = adj->twinNode();
 147                                 if(mark[x] == true) {
 148                                         w = x; break;
 149                                 }
 150                         }
 151
 152                         if(w != 0) {
 153                                 --degree[w];
 154                                 if(degree[w] == 1)
 155                                         Q.append(w);
 156                         }
 157                 }
 158         }
 159 }
 160
 161 struct OGDF_EXPORT QueueEntry
 162 {
 163         QueueEntry(node p, node v) : m_parent(p), m_current(v) { }
 164
 165         node m_parent;
 166         node m_current;
 167 };
 168
 169 void NonPlanarCore::traversingPath(Skeleton &Sv, edge eS, List<edge> &path, NodeArray<node> &mapV)
 170 {
 171         const SPQRTree &T = Sv.owner();
 172
 173         //-----------------------------------------------------
 174         // Build the graph representing the planar st-component
 175         Graph H;
 176         EdgeArray<edge> mapE(H,0);
 177         SListPure<node> nodes;
 178
 179         Queue<QueueEntry> Q;
 180         Q.append(QueueEntry(Sv.treeNode(),Sv.twinTreeNode(eS)));
 181
 182         while(!Q.empty())
 183         {
 184                 QueueEntry x = Q.pop();
 185                 node parent = x.m_parent;
 186                 node current = x.m_current;
 187
 188                 const Skeleton &S = T.skeleton(current);
 189
 190                 edge e;
 191                 forall_edges(e,S.getGraph()) {
 192                         if(S.isVirtual(e) == true)
 193                                 continue;
 194
 195                         node src = S.original(e->source());
 196                         node tgt = S.original(e->target());
 197
 198                         if(mapV[src] == 0) {
 199                                 nodes.pushBack(src);
 200                                 mapV[src] = H.newNode();
 201                         }
 202                         if(mapV[tgt] == 0) {
 203                                 nodes.pushBack(tgt);
 204                                 mapV[tgt] = H.newNode();
 205                         }
 206
 207                         mapE[H.newEdge(mapV[src],mapV[tgt])] = S.realEdge(e);
 208                 }
 209
 210                 adjEntry adj;
 211                 forall_adj(adj,current) {
 212                         node w = adj->twinNode();
 213                         if(w != parent)
 214                                 Q.append(QueueEntry(current,w));
 215                 }
 216         }
 217
 218         // add st-edge
 219         edge e_st = H.newEdge(mapV[Sv.original(eS->source())],mapV[Sv.original(eS->target())]);
 220
 221         // Compute planar embedding of H
 222 #ifdef OGDF_DEBUG
 223         bool ok =
 224 #endif
 225                 planarEmbed(H);
 226         OGDF_ASSERT(ok)
 227         CombinatorialEmbedding E(H);
 228
 229         //---------------------------------
 230         // Compute corresponding dual graph
 231         Graph dual;
 232         FaceArray<node> nodeOf(E);
 233         EdgeArray<adjEntry> primalAdj(dual);
 234
 235         // insert a node in the dual graph for each face in E
 236         face f;
 237         forall_faces(f,E)
 238                 nodeOf[f] = dual.newNode();
 239
 240
 241         node s = nodeOf[E.rightFace(e_st->adjSource())];
 242         node t = nodeOf[E.rightFace(e_st->adjTarget())];
 243
 244         // Insert an edge into the dual graph for each adjacency entry in E.
 245         // The edges are directed from the left face to the right face.
 246         node v;
 247         forall_nodes(v,H)
 248         {
 249                 adjEntry adj;
 250                 forall_adj(adj,v)
 251                 {
 252                         // do not insert edges crossing e_st
 253                         if(adj->theEdge() == e_st)
 254                                 continue;
 255
 256                         node vLeft  = nodeOf[E.leftFace (adj)];
 257                         node vRight = nodeOf[E.rightFace(adj)];
 258
 259                         primalAdj[dual.newEdge(vLeft,vRight)] = adj;
 260                 }
 261         }
 262
 263         //---------------------------
 264         // Find shortest path in dual
 265         NodeArray<edge> spPred(dual,0);
 266         QueuePure<edge> queue;
 267
 268         edge eDual;
 269         forall_adj_edges(eDual,s) {
 270                 if(s == eDual->source())
 271                         queue.append(eDual);
 272         }
 273
 274         // actual search (using bfs on directed dual)
 275         for( ; ; )
 276         {
 277                 // next candidate edge
 278                 edge eCand = queue.pop();
 279                 node v = eCand->target();
 280
 281                 // leads to an unvisited node?
 282                 if (spPred[v] == 0)
 283                 {
 284                         // yes, then we set v's predecessor in search tree
 285                         spPred[v] = eCand;
 286
 287                         // have we reached t ...
 288                         if (v == t)
 289                         {
 290                                 // ... then search is done.
 291                                 // constructed list of used edges (translated to crossed
 292                                 // edges entries in G) from t back to s (including first
 293                                 // and last!)
 294
 295                                 do {
 296                                         edge eDual = spPred[v];
 297                                         edge eG = mapE[primalAdj[eDual]->theEdge()];
 298                                         OGDF_ASSERT(eG != 0)
 299                                         path.pushFront(eG);
 300                                         v = eDual->source();
 301                                 } while(v != s);
 302
 303                                 break;
 304                         }
 305
 306                         // append next candidate edges to queue
 307                         // (all edges leaving v)
 308                         edge e;
 309                         forall_adj_edges(e,v) {
 310                                 if (v == e->source())
 311                                         queue.append(e);
 312                         }
 313                 }
 314         }
 315
 316
 317         //---------
 318         // Clean-up
 319         SListConstIterator<node> it;
 320         for(it = nodes.begin(); it.valid(); ++it)
 321                 mapV[*it] = 0;
 322 }
 323
 324
 325 } // end namespace ogdf