ext/OGDF/ogdf/planarity/BoyerMyrvold.h

   1 /*
   2  * $Revision: 2609 $
   3  *
   4  * last checkin:
   5  *   $Author: klein $
   6  *   $Date: 2012-07-16 09:59:18 +0200 (Mo, 16. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration of the wrapper class of the Boyer-Myrvold planarity test
  11  *
  12  * \author Jens Schmidt, Markus Chimani
  13  *
  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
  45 #ifdef _MSC_VER
  46 #pragma once
  47 #endif
  48
  49 #ifndef OGDF_BOYER_MYRVOLD_H
  50 #define OGDF_BOYER_MYRVOLD_H
  51
  52 #include <ogdf/module/PlanarityModule.h>
  53 #include <ogdf/internal/planarity/BoyerMyrvoldPlanar.h>
  54 #include <ogdf/planarity/ExtractKuratowskis.h>
  55 #include <ogdf/basic/GraphCopy.h>
  56 #include <ogdf/planarity/KuratowskiSubdivision.h>
  57
  58 namespace ogdf {
  59
  60 class KuratowskiWrapper;
  61
  62 //! Wrapper class used for preprocessing and valid invocation of the planarity test.
  63 /** This class is part of the extended Boyer-Myrvold planarity embedding algorithm
  64  * to simplify invocation besides adding standard parameters (see classes in
  65  * \a BoyerMyrvoldInit.h and \a BoyerMyrvoldPlanar.h). In addition the linear-time
  66  * Boyer-Myrvold embedding algorithm was extended to extract multiple Kuratowski
  67  * Subdivisions, whose number can be limited as desired (see classes in
  68  * \a FindKuratowskis.h and \a ExtractKuratowskis.h). Furthermore all extracted
  69  * subdivisions are unique.
  70  *
  71  * <b>Input graph:</b>\n
  72  * There are no restrictions on the input graph \a G (except that it has to be finite,
  73  * but if you do not have infinite RAM, that should do it :) ). In particular, \a G hasn't
  74  * to be biconnected nor connected. Self-loops and multigraphs are possible, too.\n
  75  * Note: But if you want to use the extraction of Kuratowski Subdivisions, \a G has to be simple!
  76  *
  77  * <b>How to use it:</b>\n
  78  * There exist two main functions, consisting of the planarity test itself and the
  79  * planar embedding algorithm, which embeds the graph on the plane if possible.
  80  * Each one has a fast but destructive variant, designed to
  81  * be used on graphs that may be modified and a slower variant, which is for graphs
  82  * that must not be altered. Embeddings on the plane are given by a (genus 0)
  83  * cyclic ordering of adjacency lists in the graph. Functions for constant graphs
  84  * are available, too, if that makes sense for the function.
  85  *
  86  * <b>Examples:</b>\n
  87  * \a isPlanarDestructive(G), \a isPlanar(G):\n
  88  * Tests graph \a G for planarity with the Boyer-Myrvold planarity test.
  89  *
  90  * \a planarEmbedDestructive(G), \a planarEmbed(G), \a planarEmbed(G,H):\n
  91  * Tests graph \a G for planarity and returns a planar embedding in G,
  92  * if \a G is planar. If G is a constant graph, the embedding is given in the GraphCopySimple
  93  * \a H, so that both, the constant input graph and the resulting planar embedding are available.
  94  *
  95  * \a planarEmbedDestructive(G,output,i), \a planarEmbed(G,output,i):\n
  96  * Tests graph \a G for planarity and returns a planar embedding,
  97  * if \a G is planar. Otherwise up to \a i Kuratowski subdivisions are returned to the list
  98  * \a output. Use \a i = -1 for extraction of all subdivisions.
  99  *
 100  * \a planarEmbedDestructive(G,output,i), \a planarEmbed(G,output,i):\n
 101  * Tests graph \a G for planarity and returns a planar embedding,
 102  * if \a G is planar. Otherwise up to \a i Kuratowski subdivisions are returned to the list
 103  * \a output. Use \a i = -1 for extraction of all subdivisions. The extraction algorithm
 104  * doesn't use sets of \a bundles instead of subdivisions paths, so this is designed for
 105  * a fast computation while extracting some, but not a huge amount of Kuratowski Subdivisions.
 106  *
 107  * \a planarEmbedDestructive(G,output,i,true), \a planarEmbed(G,output,i,true):\n
 108  * This is the same as above, but now \a bundles are used to compute much more subdivisions.
 109  * Naturally the computation is slower than the function above, especially on large graphs.
 110  *
 111  * <b>Complete list of parameters for embedding functions:</b>\n
 112  * e.g. \a planarEmbedDestructive(
 113  * - <b>Graph& g,</b>\n
 114  * This is the input Graph.
 115  * - <b>SList<KuratowskiWrapper>& output,</b>\n
 116  * All subdivisions are returned in this list.
 117  * - <b>int embeddingGrade,</b>\n
 118  * This flag has 5 options dependent on value \a i: \n
 119  * \a i = -3: no Embedding is computed\n
 120  * \a i = -2: no FindKuratowskiProcedure is performed\n
 121  * \a i = -1: all Kuratowski Subdivisions are extracted\n
 122  * \a i =  0: no Kuratowski Subdivision is extracted, but FindKuratowskiProcedure is started\n
 123  * \a i >  0: up to \a i Kuratowski Subdivisions are extracted.
 124  * - <b>bool bundles,</b>\n
 125  * If \a bundles are used, some paths between two Kuratowski nodes are replaced by whole
 126  * bundles of paths. On the one hand much more subdivisions can be extracted on the other
 127  * computation time growths.
 128  * - <b>bool limitStructures,</b>\n
 129  * If Kuratowski Structures are \a limited, all subdivisions in that Structures are extracted.
 130  * Thereby none of the efforts made in FindKuratowskiProcedure are lost, which is creditable
 131  * in comparison with limiting the number of extracted subdivisions. Note that the number
 132  * of extracted subdivisions can highly vary.
 133  * - <b>bool randomDFSTree,</b>\n
 134  * Iff \a true, a completely random DFS-Tree (the list of nodes and the adjacency-lists for
 135  * each node are permuted at random) is created each time the planarity test is called.
 136  * This is important for extracting huge amounts of Kuratowski subdivisions of
 137  * one single Graph, since randomizing the DFSTree yields to new unknown subdivisions.
 138  * Note that computation time growths up to 20 percent longer.
 139  * - <b>bool avoidE2Minors</b>\n
 140  * Two minortypes, namely \a E2/AE2 and \a A, construct identical subdivisions on some graphs.
 141  * To avoid this, set this flag \a true, otherwise \a false.
 142  *
 143  * )
 144  *
 145  * To experience the computation time difference to the PQTree-Planarity test please
 146  * switch to release-mode, since a lot of slow testroutines and assertions
 147  * were implemented in debug-mode. Also note the ability to transform KuratowskiWrapperLists
 148  * to Lists of KuratowskiSubdivision through calling the function \a transform. Within
 149  * this transformation is a switch to filter all similar or not similar Kuratowski
 150  * Subdivisions.
 151  */
 152 class OGDF_EXPORT BoyerMyrvold : public PlanarityModule
 153 {
 154 protected:
 155         //! Class BoyerMyrvoldPlanar on heap
 156         BoyerMyrvoldPlanar* pBMP;
 157
 158         //! Deletes BoyerMyrvoldPlanar on heap
 159         void clear() { delete pBMP; }
 160
 161         //! The number of extracted Structures for statistical purposes
 162         int nOfStructures;
 163
 164 public:
 165         //! Constructor
 166         BoyerMyrvold() { pBMP = 0; }
 167         //! Destructor
 168         ~BoyerMyrvold() { clear(); }
 169
 170         //! The number of extracted Structures for statistical purposes
 171         int numberOfStructures() { return nOfStructures; }
 172
 173         //! Returns true, iff \a g is planar
 174         /** This is the routine, which avoids the overhead of copying the input graph.
 175          * It is therefore not suitable, if your graph must not be alterated!
 176          */
 177         virtual bool isPlanarDestructive(Graph& g);
 178
 179         //! Returns true, iff a copy of the constant graph \a g is planar
 180         /** Use this slower routine, if your graph must not be alterated.
 181          */
 182         virtual bool isPlanar(const Graph& g);
 183
 184         //! Returns true, if G is planar, false otherwise. If true, G contains a planar embedding.
 185         virtual bool planarEmbed(Graph &G) {
 186                 SList<KuratowskiWrapper> list;
 187                 return planarEmbed(G,list);
 188         }
 189
 190         //! Constructs a planar embedding of G. \a G \b has to be planar!
 191         /**
 192          * Returns true if the embedding was successful.
 193          * Returns false, if the given graph was non-planar (and leaves the
 194          * graph in an at least partially deleted state)
 195          *
 196          * This routine is slightly faster than planarEmbed, but requires \a G to be planar.
 197          * If \a G is not planar, the graph will be destroyed while trying to embed it!
 198          */
 199         virtual bool planarEmbedPlanarGraph(Graph &G) {
 200                 SList<KuratowskiWrapper> list;
 201                 return planarEmbedDestructive(G,list);
 202         }
 203
 204
 205
 206
 207         //! Transforms KuratowskiWrapper in KuratowskiSubdivision
 208         void transform(
 209                 const KuratowskiWrapper& source,
 210                 KuratowskiSubdivision& target,
 211                 NodeArray<int>& count,
 212                 EdgeArray<int>& countEdge);
 213
 214         //! Transforms KuratowskiWrapper-List in KuratowskiSubdivision-List with respect to sieving constraints
 215         void transform(
 216                 const SList<KuratowskiWrapper>& sourceList,
 217                 SList<KuratowskiSubdivision>& targetList,
 218                 const Graph& g,
 219                 const bool onlyDifferent = false);
 220
 221
 222
 223         //! Returns an embedding, if \a g is planar and Kuratowski Subdivisions otherwise
 224         /** If \a g is planar, the adjLists of \a g specify a planar embedding.
 225          * Use this function, if \a g may be changed.
 226          * @param g is the input graph.
 227          * @param output contains a number of Kuratowski Subdivisions depending on the other parameters
 228          * @param embeddingGrade is a flag bounding the number of extracted subdivisions
 229          * @param bundles extracts much more subdivisions, if set
 230          * @param limitStructures limits the number of Kuratowski Structures to \a embeddingGrade, if set
 231          * @param randomDFSTree randomizes Kuratowski extraction through randomizing the DFSTree, if set
 232          * @param avoidE2Minors avoids all \a E2-Minors and ensures unique subdivisions, if set
 233          */
 234         bool planarEmbedDestructive(
 235                 Graph& g,
 236                 SList<KuratowskiWrapper>& output,
 237                 int embeddingGrade = BoyerMyrvoldPlanar::doNotFind,
 238                 bool bundles = false,
 239                 bool limitStructures = false,
 240                 bool randomDFSTree = false,
 241                 bool avoidE2Minors = true);
 242
 243         //! Returns an embedding, if \a g is planar and Kuratowski Subdivisions otherwise
 244         /** If \a g is planar, the adjLists of \a g specify a planar embedding. The function
 245          * copies the graph before computation. Use this function, if \a g must not be changed in
 246          * the non-planar case.
 247          * @param g is the input graph.
 248          * @param output contains a number of Kuratowski Subdivisions depending on the other parameters
 249          * @param embeddingGrade is a flag bounding the number of extracted subdivisions
 250          * @param bundles extracts much more subdivisions, if set
 251          * @param limitStructures limits the number of Kuratowski Structures to \a embeddingGrade, if set
 252          * @param randomDFSTree randomizes Kuratowski extraction through randomizing the DFSTree, if set
 253          * @param avoidE2Minors avoids all \a E2-Minors and ensures unique subdivisions, if set
 254          */
 255         bool planarEmbed(
 256                 Graph& g,
 257                 SList<KuratowskiWrapper>& output,
 258                 int embeddingGrade = BoyerMyrvoldPlanar::doNotFind,
 259                 bool bundles = false,
 260                 bool limitStructures = false,
 261                 bool randomDFSTree = false,
 262                 bool avoidE2Minors = true);
 263
 264         //! Returns an embedding, if graph copy \a h is planar and Kuratowski Subdivisions otherwise
 265         /** If \a h is planar, the adjLists of \a h specify a planar embedding. The function
 266          * copies the graph before computation. Use this function, if \a g must not be changed.
 267          * @param h is the input graph copy.
 268          * @param output contains a number of Kuratowski Subdivisions depending on the other parameters
 269          * @param embeddingGrade is a flag bounding the number of extracted subdivisions
 270          * @param bundles extracts much more subdivisions, if set
 271          * @param limitStructures limits the number of Kuratowski Structures to \a embeddingGrade, if set
 272          * @param randomDFSTree randomizes Kuratowski extraction through randomizing the DFSTree, if set
 273          * @param avoidE2Minors avoids all \a E2-Minors and ensures unique subdivisions, if set
 274          */
 275         bool planarEmbed(
 276                 //const Graph& g,
 277                 GraphCopySimple& h,
 278                 SList<KuratowskiWrapper>& output,
 279                 int embeddingGrade = BoyerMyrvoldPlanar::doNotFind,
 280                 bool bundles = false,
 281                 bool limitStructures = false,
 282                 bool randomDFSTree = false,
 283                 bool avoidE2Minors = true);
 284 };
 285
 286 }
 287
 288 #endif