ext/OGDF/src/planarity/BoothLueker.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 the Booth-Lueker planarity test.
  11  *
  12  * Implements planarity test and planar embedding algorithm.
  13  *
  14  * \author Sebastian Leipert
  15  *
  16  * \par License:
  17  * This file is part of the Open Graph Drawing Framework (OGDF).
  18  *
  19  * \par
  20  * Copyright (C)<br>
  21  * See README.txt in the root directory of the OGDF installation for details.
  22  *
  23  * \par
  24  * This program is free software; you can redistribute it and/or
  25  * modify it under the terms of the GNU General Public License
  26  * Version 2 or 3 as published by the Free Software Foundation;
  27  * see the file LICENSE.txt included in the packaging of this file
  28  * for details.
  29  *
  30  * \par
  31  * This program is distributed in the hope that it will be useful,
  32  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  33  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  34  * GNU General Public License for more details.
  35  *
  36  * \par
  37  * You should have received a copy of the GNU General Public
  38  * License along with this program; if not, write to the Free
  39  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  40  * Boston, MA 02110-1301, USA.
  41  *
  42  * \see  http://www.gnu.org/copyleft/gpl.html
  43  ***************************************************************/
  44
  45
  46 #include <ogdf/basic/basic.h>
  47 #include <ogdf/basic/Array.h>
  48 #include <ogdf/basic/NodeArray.h>
  49 #include <ogdf/basic/SList.h>
  50 #include <ogdf/basic/simple_graph_alg.h>
  51 #include <ogdf/basic/extended_graph_alg.h>
  52 #include <ogdf/internal/planarity/PlanarPQTree.h>
  53 #include <ogdf/internal/planarity/PlanarLeafKey.h>
  54 #include <ogdf/planarity/BoothLueker.h>
  55 #include <ogdf/internal/planarity/EmbedPQTree.h>
  56
  57
  58 namespace ogdf{
  59
  60 bool BoothLueker::isPlanarDestructive(Graph &G)
  61 {
  62         bool ret = preparation(G,false);
  63         m_parallelEdges.init();
  64         m_isParallel.init();
  65
  66         return ret;
  67 }
  68
  69 bool BoothLueker::isPlanar(const Graph &G)
  70 {
  71         Graph Gp(G);
  72         bool ret = preparation(Gp,false);
  73         m_parallelEdges.init();
  74         m_isParallel.init();
  75
  76         return ret;
  77 }
  78
  79 // Prepares the planarity test and the planar embedding
  80 // Parallel edges:  do not need to be ignored, they can be handled
  81 // by the planarity test.
  82 // Selfloops: need to be ignored.
  83 bool BoothLueker::preparation(Graph &G, bool embed)
  84 {
  85         if (G.numberOfEdges() < 9 && !embed)
  86                 return true;
  87         else if (G.numberOfEdges() < 3 && embed)
  88                 return true;
  89
  90         node v;
  91         edge e;
  92
  93         SListPure<node> selfLoops;
  94         makeLoopFree(G,selfLoops);
  95
  96         prepareParallelEdges(G);
  97
  98         int  isolated = 0;
  99         forall_nodes(v,G)
 100                 if (v->degree() == 0)
 101                         isolated++;
 102
 103         if (((G.numberOfNodes()-isolated) > 2) &&
 104                 ((3*(G.numberOfNodes()-isolated) -6) < (G.numberOfEdges() - m_parallelCount)))
 105                 return false;
 106
 107         bool planar = true;
 108
 109         NodeArray<node> tableNodes(G,0);
 110         EdgeArray<edge> tableEdges(G,0);
 111         NodeArray<bool> mark(G,0);
 112
 113         EdgeArray<int> componentID(G);
 114
 115         // Determine Biconnected Components
 116         int bcCount = biconnectedComponents(G,componentID);
 117
 118         // Determine edges per biconnected component
 119         Array<SList<edge> > blockEdges(0,bcCount-1);
 120         forall_edges(e,G)
 121         {
 122                 blockEdges[componentID[e]].pushFront(e);
 123         }
 124
 125         // Determine nodes per biconnected component.
 126         Array<SList<node> > blockNodes(0,bcCount-1);
 127         int i;
 128         for (i = 0; i < bcCount; i++)
 129         {
 130                 SListIterator<edge> it;
 131                 for (it = blockEdges[i].begin(); it.valid(); ++it)
 132                 {
 133                         e = *it;
 134                         if (!mark[e->source()])
 135                         {
 136                                 blockNodes[i].pushBack(e->source());
 137                                 mark[e->source()] = true;
 138                         }
 139                         if (!mark[e->target()])
 140                         {
 141                                 blockNodes[i].pushBack(e->target());
 142                                 mark[e->target()] = true;
 143                         }
 144                 }
 145                 SListIterator<node> itn;
 146                 for (itn = blockNodes[i].begin(); itn.valid(); ++itn)
 147                         mark[*itn] = false;
 148         }
 149
 150         // Perform Planarity Test for every biconnected component
 151
 152         if (bcCount == 1)
 153         {
 154                 if (G.numberOfEdges() >= 2)
 155                 {
 156                         // Compute st-numbering
 157                         NodeArray<int> numbering(G,0);
 158 #ifdef OGDF_DEBUG
 159                         int n =
 160 #endif
 161                                 stNumber(G,numbering);
 162                         OGDF_ASSERT_IF(dlConsistencyChecks,testSTnumber(G,numbering,n))
 163
 164                         EdgeArray<edge> backTableEdges(G,0);
 165                         forall_edges(e,G)
 166                                 backTableEdges[e] = e;
 167
 168                         if (embed)
 169                                 planar = doEmbed(G,numbering,backTableEdges,backTableEdges);
 170                         else
 171                                 planar = doTest(G,numbering);
 172                 }
 173         }
 174         else
 175         {
 176                 NodeArray<SListPure<adjEntry> > entireEmbedding(G);
 177                 for (i = 0; i < bcCount; i++)
 178                 {
 179                         Graph C;
 180
 181                         SListIterator<node> itn;
 182                         for (itn = blockNodes[i].begin(); itn.valid(); ++ itn)
 183                         {
 184                                 v = *itn;
 185                                 node w = C.newNode();
 186                                 tableNodes[v] = w;
 187                         }
 188
 189                         NodeArray<node> backTableNodes(C,0);
 190                         if (embed)
 191                         {
 192                                 for (itn = blockNodes[i].begin(); itn.valid(); ++ itn)
 193                                         backTableNodes[tableNodes[*itn]] = *itn;
 194                         }
 195
 196                         SListIterator<edge> it;
 197                         for (it = blockEdges[i].begin(); it.valid(); ++it)
 198                         {
 199                                 e = *it;
 200                                 edge f = C.newEdge(tableNodes[e->source()],tableNodes[e->target()]);
 201                                 tableEdges[e] = f;
 202                         }
 203
 204                         EdgeArray<edge> backTableEdges(C,0);
 205                         for (it = blockEdges[i].begin(); it.valid(); ++it)
 206                                 backTableEdges[tableEdges[*it]] = *it;
 207
 208                         if (C.numberOfEdges() >= 2)
 209                         {
 210                                 // Compute st-numbering
 211                                 NodeArray<int> numbering(C,0);
 212 #ifdef OGDF_DEBUG
 213                                 int n =
 214 #endif
 215                                         stNumber(C,numbering);
 216                                 OGDF_ASSERT_IF(dlConsistencyChecks,testSTnumber(C,numbering,n))
 217
 218                                 if (embed)
 219                                         planar = doEmbed(C,numbering,backTableEdges,tableEdges);
 220                                 else
 221                                         planar = doTest(C,numbering);
 222
 223                                 if (!planar)
 224                                         break;
 225                         }
 226
 227                         if (embed)
 228                         {
 229                                 forall_nodes(v,C)
 230                                 {
 231                                         node w = backTableNodes[v];
 232                                         adjEntry a;
 233                                         forall_adj(a,v)
 234                                         {
 235                                                 edge e = backTableEdges[a->theEdge()];
 236                                                 adjEntry adj = (e->adjSource()->theNode() == w)?
 237                                                                                 e->adjSource() : e->adjTarget();
 238                                                 entireEmbedding[w].pushBack(adj);
 239                                         }
 240                                 }
 241                         }
 242                 }
 243
 244                 if (planar && embed)
 245                 {
 246                         forall_nodes(v,G)
 247                                 G.sort(v,entireEmbedding[v]);
 248                 }
 249
 250         }
 251
 252         while (!selfLoops.empty())
 253         {
 254                 v = selfLoops.popFrontRet();
 255                 G.newEdge(v,v);
 256         }
 257
 258         OGDF_ASSERT_IF(dlConsistencyChecks,
 259                 planar == false || embed == false || G.representsCombEmbedding())
 260
 261         return planar;
 262 }
 263
 264
 265 // Performs a planarity test on a biconnected component
 266 // of G. numbering contains an st-numbering of the component.
 267 bool BoothLueker::doTest(Graph &G,NodeArray<int> &numbering)
 268 {
 269         bool planar = true;
 270
 271         NodeArray<SListPure<PlanarLeafKey<IndInfo*>* > > inLeaves(G);
 272         NodeArray<SListPure<PlanarLeafKey<IndInfo*>* > > outLeaves(G);
 273         Array<node> table(G.numberOfNodes()+1);
 274
 275         node v;
 276         forall_nodes(v,G)
 277         {
 278                 edge e;
 279                 forall_adj_edges(e,v)
 280                 {
 281                         if (numbering[e->opposite(v)] > numbering[v])
 282                                 //sideeffect: loops are ignored
 283                         {
 284                                 PlanarLeafKey<IndInfo*>* L = OGDF_NEW PlanarLeafKey<IndInfo*>(e);
 285                                 inLeaves[v].pushFront(L);
 286                         }
 287                 }
 288                 table[numbering[v]] = v;
 289         }
 290
 291         forall_nodes(v,G)
 292         {
 293                 SListIterator<PlanarLeafKey<IndInfo*>* > it;
 294                 for (it = inLeaves[v].begin(); it.valid(); ++it)
 295                 {
 296                         PlanarLeafKey<IndInfo*>* L = *it;
 297                         outLeaves[L->userStructKey()->opposite(v)].pushFront(L);
 298                 }
 299         }
 300
 301         PlanarPQTree T;
 302
 303         T.Initialize(inLeaves[table[1]]);
 304         for (int i = 2; i < G.numberOfNodes(); i++)
 305         {
 306                 if (T.Reduction(outLeaves[table[i]]))
 307                 {
 308                         T.ReplaceRoot(inLeaves[table[i]]);
 309                         T.emptyAllPertinentNodes();
 310
 311                 }
 312                 else
 313                 {
 314                         planar = false;
 315                         break;
 316                 }
 317         }
 318         if (planar)
 319                 T.emptyAllPertinentNodes();
 320
 321
 322         // Cleanup
 323         forall_nodes(v,G)
 324         {
 325                 while (!inLeaves[v].empty())
 326                 {
 327                         PlanarLeafKey<IndInfo*>* L = inLeaves[v].popFrontRet();
 328                         delete L;
 329                 }
 330         }
 331
 332         return planar;
 333 }
 334
 335
 336 // Performs a planarity test on a biconnected component
 337 // of G and embedds it planar.
 338 // numbering contains an st-numbering of the component.
 339 bool BoothLueker::doEmbed(
 340         Graph &G,
 341         NodeArray<int>  &numbering,
 342         EdgeArray<edge> &backTableEdges,
 343         EdgeArray<edge> &forwardTableEdges)
 344 {
 345
 346         NodeArray<SListPure<PlanarLeafKey<IndInfo*>* > > inLeaves(G);
 347         NodeArray<SListPure<PlanarLeafKey<IndInfo*>* > > outLeaves(G);
 348         NodeArray<SListPure<edge> > frontier(G);
 349         NodeArray<SListPure<node> > opposed(G);
 350         NodeArray<SListPure<node> > nonOpposed(G);
 351         Array<node> table(G.numberOfNodes()+1);
 352         Array<bool> toReverse(1,G.numberOfNodes()+1,false);
 353
 354         node v;
 355         forall_nodes(v,G)
 356         {
 357                 edge e;
 358
 359                 forall_adj_edges(e,v)
 360                 {
 361                         if (numbering[e->opposite(v)] > numbering[v])
 362                         {
 363                                 PlanarLeafKey<IndInfo*>* L = OGDF_NEW PlanarLeafKey<IndInfo*>(e);
 364                                 inLeaves[v].pushFront(L);
 365                         }
 366                 }
 367                 table[numbering[v]] = v;
 368         }
 369
 370         forall_nodes(v,G)
 371         {
 372                 SListIterator<PlanarLeafKey<IndInfo*>* > it;
 373                 for (it = inLeaves[v].begin(); it.valid(); ++it)
 374                 {
 375                         PlanarLeafKey<IndInfo*>* L = *it;
 376                         outLeaves[L->userStructKey()->opposite(v)].pushFront(L);
 377                 }
 378         }
 379
 380         EmbedPQTree T;
 381
 382         T.Initialize(inLeaves[table[1]]);
 383         int i;
 384         for (i = 2; i <= G.numberOfNodes(); i++)
 385         {
 386                 if (T.Reduction(outLeaves[table[i]]))
 387                 {
 388                         T.ReplaceRoot(inLeaves[table[i]], frontier[table[i]], opposed[table[i]], nonOpposed[table[i]], table[i]);
 389                         T.emptyAllPertinentNodes();
 390                 }
 391                 else
 392                 {
 393                         // Cleanup
 394                         forall_nodes(v,G)
 395                         {
 396                                 while (!inLeaves[v].empty())
 397                                 {
 398                                         PlanarLeafKey<IndInfo*>* L = inLeaves[v].popFrontRet();
 399                                         delete L;
 400                                 }
 401                         }
 402                         return false;
 403                 }
 404         }
 405
 406         // Reverse adjacency lists if necessary
 407         // This gives an upward embedding
 408         for (i = G.numberOfNodes(); i >= 2; i--)
 409         {
 410                 if (toReverse[i])
 411                 {
 412                         while (!nonOpposed[table[i]].empty())
 413                         {
 414                                 v = nonOpposed[table[i]].popFrontRet();
 415                                 toReverse[numbering[v]] =  true;
 416                         }
 417                         frontier[table[i]].reverse();
 418                 }
 419                 else
 420                 {
 421                         while (!opposed[table[i]].empty())
 422                         {
 423                                 v = opposed[table[i]].popFrontRet();
 424                                 toReverse[numbering[v]] =  true;
 425                         }
 426                 }
 427                 nonOpposed[table[i]].clear();
 428                 opposed[table[i]].clear();
 429         }
 430
 431         // Compute the entire embedding
 432         NodeArray<SListPure<adjEntry> > entireEmbedding(G);
 433         forall_nodes(v,G)
 434         {
 435                 while (!frontier[v].empty())
 436                 {
 437                         edge e = frontier[v].popFrontRet();
 438                         entireEmbedding[v].pushBack(
 439                                 (e->adjSource()->theNode() == v)? e->adjSource() : e->adjTarget());
 440                 }
 441         }
 442
 443         NodeArray<bool> mark(G,false);
 444         NodeArray<SListIterator<adjEntry> > adjMarker(G,0);
 445         forall_nodes(v,G)
 446                 adjMarker[v] = entireEmbedding[v].begin();
 447         v = table[G.numberOfNodes()];
 448         entireEmbed(G,entireEmbedding,adjMarker,mark,v);
 449
 450         NodeArray<SListPure<adjEntry> > newEntireEmbedding(G);
 451         if (m_parallelCount > 0)
 452         {
 453                 forall_nodes(v,G)
 454                 {
 455                         //adjEntry a;
 456                         SListIterator<adjEntry> it;
 457                         for(it=entireEmbedding[v].begin();it.valid();it++)
 458                         {
 459                                 edge e = (*it)->theEdge(); // edge in biconnected component
 460                                 edge trans = backTableEdges[e]; // edge in original graph.
 461                                 if (!m_parallelEdges[trans].empty())
 462                                 {
 463                                         // This original edge is the reference edge
 464                                         // of a bundle of parallel edges
 465
 466                                         ListIterator<edge> it;
 467                                         // If v is source of e, insert the parallel edges
 468                                         // in the order stored in the list.
 469                                         if (e->adjSource()->theNode() == v)
 470                                         {
 471                                                 adjEntry adj = e->adjSource();
 472                                                 newEntireEmbedding[v].pushBack(adj);
 473                                                 for (it = m_parallelEdges[trans].begin(); it.valid(); it++)
 474                                                 {
 475                                                         edge parallel = forwardTableEdges[*it];
 476                                                         adjEntry adj = parallel->adjSource()->theNode() == v ?
 477                                                                 parallel->adjSource() : parallel->adjTarget();
 478                                                         newEntireEmbedding[v].pushBack(adj);
 479                                                 }
 480                                         }
 481                                         else
 482                                         // v is target of e, insert the parallel edges
 483                                         // in the opposite order stored in the list.
 484                                         // This keeps the embedding.
 485                                         {
 486                                                 for (it = m_parallelEdges[trans].rbegin(); it.valid(); it--)
 487                                                 {
 488                                                         edge parallel = forwardTableEdges[*it];
 489                                                         adjEntry adj = parallel->adjSource()->theNode() == v ?
 490                                                                 parallel->adjSource() : parallel->adjTarget();
 491                                                         newEntireEmbedding[v].pushBack(adj);
 492                                                 }
 493                                                 adjEntry adj = e->adjTarget();
 494                                                 newEntireEmbedding[v].pushBack(adj);
 495                                         }
 496                                 }
 497                                 else if (!m_isParallel[trans])
 498                                         // normal non-multi-edge
 499                                 {
 500                                         adjEntry adj = e->adjSource()->theNode() == v?
 501                                                                         e->adjSource() : e->adjTarget();
 502                                         newEntireEmbedding[v].pushBack(adj);
 503                                 }
 504                                 // else e is a multi-edge but not the reference edge
 505                         }
 506                 }
 507
 508                 forall_nodes(v,G)
 509                         G.sort(v,newEntireEmbedding[v]);
 510         }
 511         else
 512         {
 513                 forall_nodes(v,G)
 514                         G.sort(v,entireEmbedding[v]);
 515         }
 516
 517
 518         //cleanup
 519         forall_nodes(v,G)
 520         {
 521                 while (!inLeaves[v].empty())
 522                 {
 523                         PlanarLeafKey<IndInfo*>* L = inLeaves[v].popFrontRet();
 524                         delete L;
 525                 }
 526         }
 527
 528         return true;
 529 }
 530
 531 // Used by doEmbed. Computes an entire embedding from an
 532 // upward embedding.
 533 void BoothLueker::entireEmbed(
 534         Graph &G,
 535         NodeArray<SListPure<adjEntry> > &entireEmbedding,
 536         NodeArray<SListIterator<adjEntry> > &adjMarker,
 537         NodeArray<bool> &mark,
 538         node v)
 539 {
 540         mark[v] = true;
 541         SListIterator<adjEntry> it;
 542         for (it = adjMarker[v]; it.valid(); ++it)
 543         {
 544                 adjEntry a = *it;
 545                 edge e = a->theEdge();
 546                 adjEntry adj = (e->adjSource()->theNode() == v)?
 547                                                 e->adjTarget() : e->adjSource();
 548                 node w = adj->theNode();
 549                 entireEmbedding[w].pushFront(adj);
 550                 if (!mark[w])
 551                         entireEmbed(G,entireEmbedding,adjMarker,mark,w);
 552         }
 553 }
 554
 555
 556
 557 void BoothLueker::prepareParallelEdges(Graph &G)
 558 {
 559         edge e;
 560
 561         // Stores for one reference edge all parallel edges.
 562         m_parallelEdges.init(G);
 563         // Is true for any multiedge, except for the reference edge.
 564         m_isParallel.init(G,false);
 565         getParallelFreeUndirected(G,m_parallelEdges);
 566         m_parallelCount = 0;
 567         forall_edges(e,G)
 568         {
 569                 if (!m_parallelEdges[e].empty())
 570                 {
 571                         ListIterator<edge> it;
 572                         for (it = m_parallelEdges[e].begin(); it.valid(); it++)
 573                         {
 574                                 m_isParallel[*it] = true;
 575                                 m_parallelCount++;
 576                         }
 577                 }
 578         }
 579 }
 580
 581
 582 }