ext/OGDF/src/planarity/BoyerMyrvold.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 wrapper class of the Boyer-Myrvold planarity test
  11  *
  12  * \author Jens Schmidt
  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/BoyerMyrvold.h>
  45 #include <ogdf/planarity/ExtractKuratowskis.h>
  46
  47
  48 namespace ogdf {
  49
  50
  51 // returns true, if g is planar, false otherwise. this is the
  52 // routine, which avoids the overhead of copying the input graph.
  53 // it is therefore not suitable, if your graph must not be changed.
  54 bool BoyerMyrvold::isPlanarDestructive(Graph& g)
  55 {
  56         clear();
  57         nOfStructures = 0;
  58
  59         // less than 9 edges are always planar
  60         if (g.numberOfEdges() < 9) return true;
  61
  62         SListPure<KuratowskiStructure> dummy;
  63         pBMP = new BoyerMyrvoldPlanar(g,false,BoyerMyrvoldPlanar::doNotEmbed,false,
  64                                                                         dummy,false,true);
  65         return pBMP->start();
  66 }
  67
  68
  69 // returns true, if g is planar, false otherwise.
  70 // use this slower routine, if your graph must not be changed.
  71 bool BoyerMyrvold::isPlanar(const Graph& g)
  72 {
  73         clear();
  74         nOfStructures = 0;
  75
  76         // less than 9 edges are always planar
  77         if (g.numberOfEdges() < 9) return true;
  78
  79         Graph h(g);
  80         SListPure<KuratowskiStructure> dummy;
  81         pBMP = new BoyerMyrvoldPlanar(h,false,BoyerMyrvoldPlanar::doNotEmbed,false,
  82                                                                         dummy,false,true);
  83         return pBMP->start();
  84 }
  85
  86
  87 // Transforms KuratowskiWrapper in KuratowskiSubdivision
  88 void BoyerMyrvold::transform(
  89         const KuratowskiWrapper& source,
  90         KuratowskiSubdivision& target,
  91         NodeArray<int>& count,
  92         EdgeArray<int>& countEdge)
  93 {
  94         // init linear counting structure
  95         node kn[6];
  96         int k = 0;
  97         SListConstIterator<edge> itE;
  98         for (itE = source.edgeList.begin(); itE.valid(); ++itE) {
  99                 const edge& e(*itE);
 100                 OGDF_ASSERT(!countEdge[e]);
 101                 countEdge[e] = 1;
 102                 if (++count[e->source()] == 3) kn[k++] = e->source();
 103                 if (++count[e->target()] == 3) kn[k++] = e->target();
 104         }
 105
 106         // transform edgelist of KuratowskiSubdivision to KuratowskiWrapper
 107         OGDF_ASSERT(k==5 || k==6);
 108         node n;
 109         edge e,f,h;
 110         List<edge> L;
 111         if (k==5) { // K5
 112                 kn[5] = 0;
 113                 target.init(10);
 114                 for (int k = 0; k<5; k++) {
 115                         forall_adj_edges(e,kn[k]) {
 116                                 if (!countEdge[e]) continue;
 117                                 n = kn[k];
 118                                 f = e;
 119                                 // traverse degree-2-path
 120                                 while (count[n = f->opposite(n)] == 2) {
 121                                         L.pushBack(f);
 122                                         forall_adj_edges(h,n) {
 123                                                 if (countEdge[h] && h != f) {
 124                                                         f = h;
 125                                                         break;
 126                                                 }
 127                                         }
 128                                 }
 129                                 L.pushBack(f);
 130                                 int i = 0;
 131                                 while (kn[i] != n) i++;
 132                                 if (i > k) {
 133                                         if (k==0) i--;
 134                                         else if (k==1) i+=2;
 135                                         else i += k+2;
 136                                         target[i].conc(L);
 137                                 } else L.clear();
 138                         }
 139                 }
 140         } else { // k33
 141                 target.init(9);
 142                 int touched[6] = { -1, -1, -1, -1, -1, -1}, t=0, i=0;
 143                 for (int k = 0; k<6; k++) {
 144                         if (touched[k] != -1) continue;
 145                         forall_adj_edges(e,kn[k]) {
 146                                 if (!countEdge[e]) continue;
 147                                 n = kn[k];
 148                                 f = e;
 149                                 while(count[n = f->opposite(n)] == 2) {
 150                                         L.pushBack(f);
 151                                         forall_adj_edges(h,n) {
 152                                                 if (countEdge[h] && h != f) {
 153                                                         f = h;
 154                                                         break;
 155                                                 }
 156                                         }
 157                                 }
 158                                 L.pushBack(f);
 159                                 int j = 0;
 160                                 while (kn[j] != n) j++;
 161                                 if (touched[j] == -1)
 162                                         touched[j] = t++;
 163                                 target[i*3 + touched[j]].conc(L);
 164                         }
 165                         i++;
 166                 }
 167         }
 168
 169         // destruct linear counting structure
 170         for (itE = source.edgeList.begin(); itE.valid(); ++itE) {
 171                 const edge& e(*itE);
 172                 countEdge[e] = 0;
 173                 count[e->source()] = 0;
 174                 count[e->target()] = 0;
 175         }
 176 }
 177
 178 // Transforms KuratowskiWrapper-List in KuratowskiSubdivision-List with respect to sieving constraints
 179 void BoyerMyrvold::transform(
 180         const SList<KuratowskiWrapper>& sourceList,
 181         SList<KuratowskiSubdivision>& targetList,
 182         const Graph& g,
 183         const bool onlyDifferent)
 184 {
 185         if (sourceList.empty()) return;
 186         targetList.clear();
 187         NodeArray<int> count(g,0);
 188         EdgeArray<int> countEdge(g,0);
 189         SListConstIterator<KuratowskiWrapper> it;
 190         node lastEmbeddedVertex = NULL;
 191
 192         // transform each KuratowskiWrapper into KuratowskiSubdivision
 193         for (it = sourceList.begin(); it.valid(); ++it) {
 194                 if (!onlyDifferent || (*it).V != lastEmbeddedVertex) {
 195                         lastEmbeddedVertex = (*it).V;
 196                         KuratowskiSubdivision s;
 197                         transform(*it,s,count,countEdge);
 198
 199                         targetList.pushBack(s);
 200                 }
 201         }
 202 }
 203
 204 // returns true, if g is planar, false otherwise. in addition,
 205 // g contains a planar embedding, if planar. if not planar,
 206 // kuratowski subdivisions are added to output.
 207 // use this function, if g may be changed.
 208 // use embeddingGrade to bound the overall number of extracted kuratowski subdivisions;
 209 // use the value 0 to extract no kuratowski subdivision and the value -1 to find as much
 210 // as possible. value -2 doesn't even invoke the FIND-procedure.
 211 bool BoyerMyrvold::planarEmbedDestructive(
 212         Graph& g,
 213         SList<KuratowskiWrapper>& output,
 214         int embeddingGrade,
 215         bool bundles,
 216         bool limitStructures,
 217         bool randomDFSTree,
 218         bool avoidE2Minors)
 219 {
 220         OGDF_ASSERT(embeddingGrade != BoyerMyrvoldPlanar::doNotEmbed);
 221
 222         clear();
 223         SListPure<KuratowskiStructure> dummy;
 224         pBMP = new BoyerMyrvoldPlanar(g,bundles,embeddingGrade,limitStructures,dummy,
 225                                                                         randomDFSTree,avoidE2Minors);
 226         bool planar = pBMP->start();
 227         OGDF_ASSERT(!planar || g.genus()==0);
 228
 229         nOfStructures = dummy.size();
 230
 231         // Kuratowski extraction
 232         if (embeddingGrade > BoyerMyrvoldPlanar::doFindZero ||
 233                                 embeddingGrade == BoyerMyrvoldPlanar::doFindUnlimited) {
 234                 ExtractKuratowskis extract(*pBMP);
 235                 if (bundles) {
 236                         extract.extractBundles(dummy,output);
 237                 } else {
 238                         extract.extract(dummy,output);
 239                 }
 240                 OGDF_ASSERT(planar || !output.empty());
 241         }
 242         return planar;
 243 }
 244
 245 // returns true, if g is planar, false otherwise. in addition,
 246 // h contains a planar embedding, if planar. if not planar, list
 247 // contains a kuratowski subdivision.
 248 // use this slower function, if g must not be changed.
 249 // use embeddingGrade to bound the overall number of extracted kuratowski subdivisions;
 250 // use the value 0 to extract no kuratowski subdivision and the value -1 to find as much
 251 // as possible. value -2 doesn't even invoke the FIND-procedure.
 252 bool BoyerMyrvold::planarEmbed(
 253         Graph& g,
 254         SList<KuratowskiWrapper>& output,
 255         int embeddingGrade,
 256         bool bundles,
 257         bool limitStructures,
 258         bool randomDFSTree,
 259         bool avoidE2Minors)
 260 {
 261         OGDF_ASSERT(embeddingGrade != BoyerMyrvoldPlanar::doNotEmbed);
 262
 263         clear();
 264         GraphCopySimple h(g);
 265         SListPure<KuratowskiStructure> dummy;
 266         pBMP = new BoyerMyrvoldPlanar(h,bundles,embeddingGrade,limitStructures,dummy,
 267                                                                         randomDFSTree,avoidE2Minors);
 268         bool planar = pBMP->start();
 269         OGDF_ASSERT(!planar || h.genus()==0);
 270
 271         nOfStructures = dummy.size();
 272
 273         // Kuratowski extraction
 274         if (embeddingGrade > BoyerMyrvoldPlanar::doFindZero ||
 275                                 embeddingGrade == BoyerMyrvoldPlanar::doFindUnlimited) {
 276                 ExtractKuratowskis extract(*pBMP);
 277                 if (bundles) {
 278                         extract.extractBundles(dummy,output);
 279                 } else {
 280                         extract.extract(dummy,output);
 281                 }
 282                 OGDF_ASSERT(planar || !output.empty());
 283
 284                 // convert kuratowski edges in original graph edges
 285                 if (!output.empty()) {
 286                         SListIterator<KuratowskiWrapper> it;
 287                         SListIterator<edge> itE;
 288                         for (it = output.begin(); it.valid(); ++it) {
 289                                 for (itE = (*it).edgeList.begin(); itE.valid(); ++itE)
 290                                         (*itE) = h.original(*itE);
 291                         }
 292                 }
 293         }
 294
 295         // copy adjacency lists, if planar
 296         if (planar) {
 297                 node v;
 298                 adjEntry adj;
 299                 SListPure<adjEntry> entries;
 300                 forall_nodes(v,g) {
 301                         entries.clear();
 302                         forall_adj(adj,h.copy(v)) {
 303                                 OGDF_ASSERT(adj->theNode() == h.copy(v));
 304                                 edge e = h.original(adj->theEdge());
 305                                 OGDF_ASSERT(e->graphOf() == &g);
 306                                 //if (e->source() == v) {
 307                                 if(adj == adj->theEdge()->adjSource()) {
 308                                         entries.pushBack(e->adjSource());
 309                                         OGDF_ASSERT(e->adjSource()->theNode() == v);
 310                                 } else {
 311                                         entries.pushBack(e->adjTarget());
 312                                         OGDF_ASSERT(e->adjTarget()->theNode() == v);
 313                                 }
 314                         }
 315                         g.sort(v,entries);
 316                 }
 317         }
 318
 319         return planar;
 320 }
 321
 322 // returns true, if graph copy h is planar, false otherwise. in addition,
 323 // h contains a planar embedding, if planar. if not planar, list
 324 // contains a kuratowski subdivision.
 325 // use this slower function, if g must not be changed.
 326 // use embeddingGrade to bound the overall number of extracted kuratowski subdivisions;
 327 // use the value 0 to extract no kuratowski subdivision and the value -1 to find as much
 328 // as possible. value -2 doesn't even invoke the FIND-procedure.
 329 bool BoyerMyrvold::planarEmbed(
 330         //const Graph& g,
 331         GraphCopySimple& h,
 332         SList<KuratowskiWrapper>& output,
 333         int embeddingGrade,
 334         bool bundles,
 335         bool limitStructures,
 336         bool randomDFSTree,
 337         bool avoidE2Minors)
 338 {
 339         OGDF_ASSERT(embeddingGrade != BoyerMyrvoldPlanar::doNotEmbed);
 340
 341         clear();
 342         //OGDF_ASSERT(&h.original() == &g);
 343         SListPure<KuratowskiStructure> dummy;
 344         pBMP = new BoyerMyrvoldPlanar(h,bundles,embeddingGrade,limitStructures,dummy,
 345                                                                         randomDFSTree,avoidE2Minors);
 346         bool planar = pBMP->start();
 347         OGDF_ASSERT(!planar || h.genus()==0);
 348
 349         nOfStructures = dummy.size();
 350
 351         // Kuratowski extraction
 352         if (embeddingGrade > BoyerMyrvoldPlanar::doFindZero ||
 353                                 embeddingGrade == BoyerMyrvoldPlanar::doFindUnlimited) {
 354                 ExtractKuratowskis extract(*pBMP);
 355                 if (bundles) {
 356                         extract.extractBundles(dummy,output);
 357                 } else {
 358                         extract.extract(dummy,output);
 359                 }
 360                 OGDF_ASSERT(planar || !output.empty());
 361
 362                 // convert kuratowski edges in original graph edges
 363                 if (!output.empty()) {
 364                         SListIterator<KuratowskiWrapper> it;
 365                         SListIterator<edge> itE;
 366                         for (it = output.begin(); it.valid(); ++it) {
 367                                 for (itE = (*it).edgeList.begin(); itE.valid(); ++itE)
 368                                         (*itE) = h.original(*itE);
 369                         }
 370                 }
 371         }
 372
 373         return planar;
 374 }
 375
 376 }