ext/OGDF/src/decomposition/PlanarSPQRTree.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 PlanarSPQRTree
  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/decomposition/PlanarSPQRTree.h>
  45 #include <ogdf/basic/extended_graph_alg.h>
  46
  47
  48 namespace ogdf {
  49
  50 //-------------------------------------------------------------------
  51 //                           PlanarSPQRTree
  52 //-------------------------------------------------------------------
  53
  54 //
  55 // initialization: additionally embeds skeleton graphs or adpots embedding
  56 // given by original graph
  57 void PlanarSPQRTree::init(bool isEmbedded)
  58 {
  59         if (isEmbedded) {
  60                 adoptEmbedding();
  61
  62         } else {
  63
  64                 node v;
  65                 forall_nodes(v,tree())
  66                         planarEmbed(skeleton(v).getGraph());
  67         }
  68 }
  69
  70
  71 void PlanarSPQRTree::adoptEmbedding()
  72 {
  73         OGDF_ASSERT_IF(dlExtendedChecking, originalGraph().representsCombEmbedding());
  74
  75         // ordered list of adjacency entries (for one original node) in all
  76         // skeletons (where this node occurs)
  77         NodeArray<SListPure<adjEntry> > adjEdges(tree());
  78         // copy in skeleton of current original node
  79         NodeArray<node> currentCopy(tree(),0);
  80         NodeArray<adjEntry> lastAdj(tree(),0);
  81         SListPure<node> current; // currently processed nodes
  82
  83         node vOrig;
  84         forall_nodes(vOrig,originalGraph())
  85         {
  86                 adjEntry adjOrig;
  87                 forall_adj(adjOrig,vOrig)
  88                 {
  89                         edge            eOrig = adjOrig->theEdge();
  90                         const Skeleton &S     = skeletonOfReal(eOrig);
  91                         edge            eCopy = copyOfReal(eOrig);
  92
  93                         adjEntry adjCopy = (S.original(eCopy->source()) == vOrig) ?
  94                                 eCopy->adjSource() : eCopy->adjTarget();
  95
  96                         setPosInEmbedding(adjEdges,currentCopy,lastAdj,current,S,adjCopy);
  97                 }
  98
  99                 SListConstIterator<node> it;
 100                 for(it = current.begin(); it.valid(); ++it) {
 101                         node vT = *it;
 102
 103                         skeleton(vT).getGraph().sort(currentCopy[vT],adjEdges[vT]);
 104
 105                         adjEdges[vT].clear();
 106                         currentCopy[vT] = 0;
 107                 }
 108
 109                 current.clear();
 110         }
 111 }
 112
 113
 114 void PlanarSPQRTree::setPosInEmbedding(
 115         NodeArray<SListPure<adjEntry> > &adjEdges,
 116         NodeArray<node> &currentCopy,
 117         NodeArray<adjEntry> &lastAdj,
 118         SListPure<node> &current,
 119         const Skeleton &S,
 120         adjEntry adj)
 121 {
 122         node vT = S.treeNode();
 123
 124         adjEdges[vT].pushBack(adj);
 125
 126         node vCopy = adj->theNode();
 127         node vOrig = S.original(vCopy);
 128
 129         if(currentCopy[vT] == 0) {
 130                 currentCopy[vT] = vCopy;
 131                 current.pushBack(vT);
 132
 133                 adjEntry adjVirt;
 134                 forall_adj(adjVirt,vCopy) {
 135                         edge eCopy = S.twinEdge(adjVirt->theEdge());
 136                         if (eCopy == 0) continue;
 137                         if (adjVirt == adj) {
 138                                 lastAdj[vT] = adj;
 139                                 continue;
 140                         }
 141
 142                         const Skeleton &STwin = skeleton(S.twinTreeNode(adjVirt->theEdge()));
 143
 144                         adjEntry adjCopy = (STwin.original(eCopy->source()) == vOrig) ?
 145                                 eCopy->adjSource() : eCopy->adjTarget();
 146
 147                         setPosInEmbedding(adjEdges,currentCopy,lastAdj,current,
 148                                 STwin, adjCopy);
 149                 }
 150
 151         } else if (lastAdj[vT] != 0 && lastAdj[vT] != adj) {
 152                 adjEntry adjVirt = lastAdj[vT];
 153                 edge eCopy = S.twinEdge(adjVirt->theEdge());
 154
 155                 const Skeleton &STwin = skeleton(S.twinTreeNode(adjVirt->theEdge()));
 156
 157                 adjEntry adjCopy = (STwin.original(eCopy->source()) == vOrig) ?
 158                         eCopy->adjSource() : eCopy->adjTarget();
 159
 160                 setPosInEmbedding(adjEdges,currentCopy,lastAdj,current,
 161                         STwin, adjCopy);
 162
 163                 lastAdj[vT] = 0;
 164         }
 165
 166 }
 167
 168
 169 //
 170 // embed original graph according to embedding of skeletons
 171 //
 172 // The procedure also handles the case when some (real or virtual)
 173 // edges are reversed (used in upward-planarity algorithms)
 174 void PlanarSPQRTree::embed(Graph &G)
 175 {
 176         OGDF_ASSERT(&G == &originalGraph());
 177
 178         const Skeleton &S = skeleton(rootNode());
 179         const Graph &M = S.getGraph();
 180
 181         node v;
 182         forall_nodes(v,M)
 183         {
 184                 node vOrig = S.original(v);
 185                 SListPure<adjEntry> adjEdges;
 186
 187                 adjEntry adj;
 188                 forall_adj(adj,v) {
 189                         edge e = adj->theEdge();
 190                         edge eOrig = S.realEdge(e);
 191
 192                         if (eOrig != 0) {
 193                                 adjEntry adjOrig = (vOrig == eOrig->source()) ?
 194                                         eOrig->adjSource() : eOrig->adjTarget();
 195                                 OGDF_ASSERT(adjOrig->theNode() == S.original(v));
 196                                 adjEdges.pushBack(adjOrig);
 197
 198                         } else {
 199                                 node wT    = S.twinTreeNode(e);
 200                                 edge eTwin = S.twinEdge(e);
 201                                 expandVirtualEmbed(wT,
 202                                         (vOrig == skeleton(wT).original(eTwin->source())) ?
 203                                         eTwin->adjSource() : eTwin->adjTarget(),
 204                                         adjEdges);
 205                         }
 206                 }
 207
 208                 G.sort(vOrig,adjEdges);
 209         }
 210
 211         edge e;
 212         forall_adj_edges(e,rootNode()) {
 213                 node wT = e->target();
 214                 if (wT != rootNode())
 215                         createInnerVerticesEmbed(G, wT);
 216         }
 217 }
 218
 219
 220 void PlanarSPQRTree::expandVirtualEmbed(node vT,
 221         adjEntry adjVirt,
 222         SListPure<adjEntry> &adjEdges)
 223 {
 224         const Skeleton &S = skeleton(vT);
 225
 226         node v = adjVirt->theNode();
 227         node vOrig = S.original(v);
 228
 229         adjEntry adj;
 230         for (adj = adjVirt->cyclicSucc(); adj != adjVirt; adj = adj->cyclicSucc())
 231         {
 232                 edge e = adj->theEdge();
 233                 edge eOrig = S.realEdge(e);
 234
 235                 if (eOrig != 0) {
 236                         adjEntry adjOrig = (vOrig == eOrig->source()) ?
 237                                 eOrig->adjSource() : eOrig->adjTarget();
 238                         OGDF_ASSERT(adjOrig->theNode() == S.original(v));
 239                         adjEdges.pushBack(adjOrig);
 240
 241                 } else {
 242                         node wT    = S.twinTreeNode(e);
 243                         edge eTwin = S.twinEdge(e);
 244                         expandVirtualEmbed(wT,
 245                                 (vOrig == skeleton(wT).original(eTwin->source())) ?
 246                                 eTwin->adjSource() : eTwin->adjTarget(),
 247                                 adjEdges);
 248                 }
 249         }
 250 }
 251
 252
 253 void PlanarSPQRTree::createInnerVerticesEmbed(Graph &G, node vT)
 254 {
 255         const Skeleton &S = skeleton(vT);
 256         const Graph& M = S.getGraph();
 257
 258         node src = S.referenceEdge()->source();
 259         node tgt = S.referenceEdge()->target();
 260
 261         node v;
 262         forall_nodes(v,M)
 263         {
 264                 if (v == src || v == tgt) continue;
 265
 266                 node vOrig = S.original(v);
 267                 SListPure<adjEntry> adjEdges;
 268
 269                 adjEntry adj;
 270                 forall_adj(adj,v) {
 271                         edge e = adj->theEdge();
 272                         edge eOrig = S.realEdge(e);
 273
 274                         if (eOrig != 0) {
 275                                 adjEntry adjOrig = (vOrig == eOrig->source()) ?
 276                                         eOrig->adjSource() : eOrig->adjTarget();
 277                                 OGDF_ASSERT(adjOrig->theNode() == S.original(v));
 278                                 adjEdges.pushBack(adjOrig);
 279                         } else {
 280                                 node wT    = S.twinTreeNode(e);
 281                                 edge eTwin = S.twinEdge(e);
 282                                 expandVirtualEmbed(wT,
 283                                         (vOrig == skeleton(wT).original(eTwin->source())) ?
 284                                         eTwin->adjSource() : eTwin->adjTarget(),
 285                                         adjEdges);
 286                         }
 287                 }
 288
 289                 G.sort(vOrig,adjEdges);
 290         }
 291
 292         edge e;
 293         forall_adj_edges(e,vT) {
 294                 node wT = e->target();
 295                 if (wT != vT)
 296                         createInnerVerticesEmbed(G, wT);
 297         }
 298 }
 299
 300
 301
 302 //
 303 // basic update functions for manipulating embeddings
 304
 305 //   reversing the skeleton of an R- or P-node
 306 void PlanarSPQRTree::reverse(node vT)
 307 {
 308         skeleton(vT).getGraph().reverseAdjEdges();
 309 }
 310
 311
 312 //   swapping two adjacency entries in the skeleton of a P-node
 313 void PlanarSPQRTree::swap(node vT, adjEntry adj1, adjEntry adj2)
 314 {
 315         OGDF_ASSERT(typeOf(vT) == PNode);
 316
 317         Graph &M = skeleton(vT).getGraph();
 318
 319         M.swapAdjEdges(adj1,adj2);
 320         M.swapAdjEdges(adj1->twin(),adj2->twin());
 321 }
 322
 323
 324 //   swapping two edges in the skeleton of a P-node
 325 void PlanarSPQRTree::swap(node vT, edge e1, edge e2)
 326 {
 327         OGDF_ASSERT(typeOf(vT) == PNode);
 328
 329         if (e1->source() == e2->source())
 330                 swap(vT,e1->adjSource(),e2->adjSource());
 331         else
 332                 swap(vT,e1->adjSource(),e2->adjTarget());
 333 }
 334
 335
 336 //
 337 // number of possible embeddings of original graph
 338 //
 339 double PlanarSPQRTree::numberOfEmbeddings(node vT) const
 340 {
 341         double num = 1.0;
 342
 343         switch(typeOf(vT)) {
 344         case RNode:
 345                 num = 2; break;
 346         case PNode:
 347                 //node vFirst = skeleton(vT).getGraph().firstNode();
 348                 for (int i = skeleton(vT).getGraph().firstNode()->degree()-1; i >= 2; --i)
 349                         num *= i;
 350                 break;
 351         case SNode:
 352                 break;
 353         }
 354
 355         edge e;
 356         forall_adj_edges(e,vT) {
 357                 node wT = e->target();
 358                 if(wT != vT)
 359                         num *= numberOfEmbeddings(wT);
 360         }
 361
 362         return num;
 363 }
 364
 365
 366
 367 //
 368 // randomly embed skeleton graphs
 369 //
 370 void PlanarSPQRTree::randomEmbed()
 371 {
 372         node vT;
 373         forall_nodes(vT,tree()) {
 374                 if (typeOf(vT) == RNode) {
 375                         int doReverse = randomNumber(0,1);
 376
 377                         if (doReverse == 1)
 378                                 reverse(vT);
 379
 380                 } else if (typeOf(vT) == PNode) {
 381                         const Skeleton &S = skeleton(vT);
 382                         adjEntry adjRef = S.referenceEdge()->adjSource();
 383
 384                         SList<adjEntry> adjEdges;
 385                         adjEntry adj;
 386                         for (adj = adjRef->cyclicSucc(); adj != adjRef; adj = adj->cyclicSucc())
 387                                 adjEdges.pushBack(adj);
 388
 389                         adjEdges.permute();
 390
 391                         adj = adjRef->cyclicSucc();
 392                         SListConstIterator<adjEntry> it;
 393                         for (it = adjEdges.begin(); it.valid(); ++it)
 394                         {
 395                                 adjEntry adjNext = *it;
 396                                 if (adjNext != adj) {
 397                                         swap(vT,adj,adjNext);
 398                                         adj = adjNext;
 399                                 }
 400                                 adj = adj->cyclicSucc();
 401                         }
 402                 }
 403         }
 404 }
 405
 406
 407 } // end namespace ogdf