ext/OGDF/ogdf/internal/planarity/FindKuratowskis.h

   1 /*
   2  * $Revision: 2523 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-02 20:59:27 +0200 (Mon, 02 Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration of the class FindKuratowskis
  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 #ifdef _MSC_VER
  45 #pragma once
  46 #endif
  47
  48 #ifndef OGDF_FIND_KURATOWSKIS_H
  49 #define OGDF_FIND_KURATOWSKIS_H
  50
  51 #include <ogdf/internal/planarity/BoyerMyrvoldPlanar.h>
  52
  53
  54 namespace ogdf {
  55
  56
  57 //! List of externally active nodes strictly between x and y for minortypes \a B and \a E
  58 /** In case of extracting without bundles, all external paths and lists of their start-
  59  * and endnodes are added.
  60  */
  61 struct ExternE {
  62         node theNode;
  63         SListPure<int> startnodes;
  64         SListPure<node> endnodes;
  65         SListPure<SListPure<edge> > externalPaths;
  66 };
  67
  68 //! Saves information about a pertinent node w between two stopping vertices.
  69 /** In particular links to appropriate highest-XY-Path and z-nodes are maintained
  70  */
  71 struct WInfo {
  72         public:
  73                 node w;
  74
  75                 //!  All possible base minortypes on w
  76                 enum enumMinorType {
  77                         A=0x0001, // minor A
  78                         B=0x0002, // minor B
  79                         C=0x0004, // minor C
  80                         D=0x0008, // minor D
  81                         E=0x0010  // minor E
  82                 };
  83                 int minorType;
  84
  85                 SListPure<adjEntry>* highestXYPath;
  86                 SListPure<adjEntry>* zPath;
  87
  88                 bool pxAboveStopX;
  89                 bool pyAboveStopY;
  90
  91                 SListPure<SListPure<edge> > pertinentPaths;
  92
  93                 SListIterator<ExternE> externEStart;
  94                 SListIterator<ExternE> externEEnd;
  95                 node firstExternEAfterW;
  96 };
  97
  98 //! A Kuratowski Structure is a special graph structure containing severals subdivisions
  99 class OGDF_EXPORT KuratowskiStructure {
 100                 friend class FindKuratowskis;
 101                 friend class ExtractKuratowskis;
 102         public:
 103                 //! Constructor
 104                 KuratowskiStructure() { }
 105                 //! Destructor
 106                 ~KuratowskiStructure() { }
 107
 108                 //! Copy constructor
 109                 KuratowskiStructure(const KuratowskiStructure& orig) {
 110                         copy(orig);
 111                 }
 112
 113                 //! Assignment
 114                 KuratowskiStructure& operator=(const KuratowskiStructure& orig) {
 115                         copy(orig);
 116                         return *this;
 117                 }
 118
 119                 //! Reset all data members
 120                 void clear();
 121
 122                 //! The current node to embed
 123                 node V;
 124                 //! DFI of the current node to embed
 125                 int V_DFI;
 126
 127                 //! The root of the bicomp containing \a stopX and \a stopY
 128                 node R;
 129                 //! Real node of virtual node \a R.
 130                 /** This is redundant, but virtual node will be deleted later on
 131                  */
 132                 node RReal;
 133                 //! First stopping node
 134                 node stopX;
 135                 //! Second stopping node
 136                 node stopY;
 137
 138         protected:
 139                 //! Holds information about all pertinent nodes \a w of the bicomp containing \a V
 140                 /** Those were not embedded because of the two stopping nodes. In addition,
 141                  * links to the highest-XY-path and the z-nodes of w and the minortype is saved.
 142                  */
 143                 SListPure<WInfo> wNodes;
 144
 145                 //! The whole highestFacePath of the bicomp containing \a V
 146                 /** The construct the highestFacePath, delete all edges of \a V except the two
 147                  * edges on the external face. The highestFacePath is the path starting at the
 148                  * first external edge along the unique face back to \a V.
 149                  */
 150                 ListPure<adjEntry> highestFacePath;
 151
 152                 //! The appropriate paths of the highestFacePath for each wNode
 153                 SListPure<SListPure<adjEntry> > highestXYPaths;
 154
 155                 //! External face path of bicomp containing \a V in direction CCW
 156                 SListPure<adjEntry> externalFacePath;
 157
 158                 //! A list of all edges in all externally active paths (bundles only)
 159                 SListPure<edge> externalSubgraph;
 160
 161                 //! A list of all edges in pertinent paths (bundles only)
 162                 SListPure<edge> pertinentSubgraph;
 163
 164                 //! A path from the \a zNode in minortype \a D to node \a V for each highest XY-Path
 165                 /** zNodes are cut-vertices not contained in the external face path
 166                  */
 167                 SListPure<SListPure<adjEntry> > zPaths;
 168
 169                 //! List of externally active nodes strictly between x and y for minortypes \a B and \a E
 170                 SListPure<ExternE> externE;
 171
 172                 //! List of all virtual startnodes of paths starting at \a stopX (only without bundles)
 173                 SListPure<int> stopXStartnodes;
 174                 //! List of all virtual startnodes of paths starting at \a stopY (only without bundles)
 175                 SListPure<int> stopYStartnodes;
 176                 //! List of all endnodes of paths starting at \a stopX (only without bundles)
 177                 SListPure<node> stopXEndnodes;
 178                 //! List of all endnodes of paths starting at \a stopY (only without bundles)
 179                 SListPure<node> stopYEndnodes;
 180
 181                 //! Copies class
 182                 void copy(const KuratowskiStructure& orig);
 183                 //! Used in copy constructor
 184                 void copyPointer(const KuratowskiStructure& orig, SListPure<WInfo>& list);
 185 };
 186
 187 //! This class collects information about Kuratowski Subdivisions which is used for extraction later.
 188 /** \pre Graph has to be simple.
 189  */
 190 class FindKuratowskis {
 191         public:
 192                 //! Constructor
 193                 FindKuratowskis(BoyerMyrvoldPlanar* bm);
 194                 //! Destructor
 195                 ~FindKuratowskis() { }
 196
 197                 //! Adds Kuratowski Structure on current node with root \a root and stopping nodes \a stopx and \a stopy
 198                 void addKuratowskiStructure(
 199                                                 const node currentNode,
 200                                                 const node root,
 201                                                 const node stopx,
 202                                                 const node stopy);
 203
 204                 //! Get-method for the list of all KuratowskiStructures
 205                 inline SListPure<KuratowskiStructure>& getAllKuratowskis() {
 206                         return allKuratowskis;
 207                 }
 208
 209                 //! Constant get-method for the list of all KuratowskiStructures
 210                 inline const SListPure<KuratowskiStructure>& getAllKuratowskis() const {
 211                         return allKuratowskis;
 212                 }
 213
 214                 // avoid automatic creation of assignment operator
 215                 //! Assignment operator is undefined!
 216                 FindKuratowskis &operator=(const FindKuratowskis &);
 217
 218         protected:
 219                 //! Link to class BoyerMyrvoldPlanar
 220                 BoyerMyrvoldPlanar* pBM;
 221
 222                 //! Input graph
 223                 Graph& m_g;
 224
 225                 //! The embedding grade
 226                 const int& m_embeddingGrade;
 227
 228                 //! If true, bundles are extracted, otherwise single paths?
 229                 const bool m_bundles;
 230
 231                 //! Links appropriate \a WInfo to node
 232                 NodeArray<WInfo*> m_getWInfo;
 233
 234                 //! List of all Kuratowski Structures
 235                 SListPure<KuratowskiStructure> allKuratowskis;
 236
 237                 //! Current Kuratowski Structure
 238                 KuratowskiStructure k;
 239
 240                 //! Value used as marker for visited nodes etc.
 241                 /** Used during computation of the external face path and the highest x-y-path
 242                  */
 243                 int m_nodeMarker;
 244                 //! Array maintaining visited bits on each node
 245                 NodeArray<int> m_wasHere;
 246
 247                 //! Link to non-virtual vertex of a virtual Vertex.
 248                 /** A virtual vertex has negative DFI of the DFS-Child of related non-virtual Vertex
 249                  */
 250                 const NodeArray<node>& m_realVertex;
 251
 252                 //! The one and only DFI-NodeArray
 253                 const NodeArray<int>& m_dfi;
 254
 255                 //! Returns appropriate node from given DFI
 256                 const Array<node>& m_nodeFromDFI;
 257
 258                 //! Links to opposite adjacency entries on external face in clockwise resp. ccw order
 259                 /** m_link[0]=CCW, m_link[1]=CW
 260                  */
 261                 const NodeArray<adjEntry>(& m_link)[2];
 262
 263                 //! The adjEntry which goes from DFS-parent to current vertex
 264                 const NodeArray<adjEntry>& m_adjParent;
 265
 266                 //! The DFI of the least ancestor node over all backedges
 267                 /** If no backedge exists, the least ancestor is the DFI of that node itself
 268                  */
 269                 const NodeArray<int>& m_leastAncestor;
 270
 271                 //! Contains the type of each \a edge
 272                 /** @param 0 = EDGE_UNDEFINED
 273                  * @param 1 = EDGE_SELFLOOP
 274                  * @param 2 = EDGE_BACK
 275                  * @param 3 = EDGE_DFS
 276                  * @param 4 = EDGE_DFS_PARALLEL
 277                  * @param 5 = EDGE_BACK_DELETED
 278                  */
 279                 EdgeArray<int>& m_edgeType;
 280
 281                 //! The lowpoint of each \a node
 282                 NodeArray<int>& m_lowPoint;
 283
 284                 //! The highest DFI in a subtree with \a node as root
 285                 const NodeArray<int>& m_highestSubtreeDFI;
 286
 287                 //! A list to all separated DFS-children of \a node
 288                 /** The list is sorted by lowpoint values (in linear time)
 289                 */
 290                 const NodeArray<ListPure<node> >& m_separatedDFSChildList;
 291
 292                 //! Identifies the rootnode of the child bicomp the given backedge points to
 293                 const EdgeArray<node>& m_pointsToRoot;
 294
 295                 //! Keeps track of all vertices that are visited by the walkup through a specific backedge
 296                 /** This is done in order to refer to the unique child-bicomp of v.
 297                  */
 298                 NodeArray<int>& m_visitedWithBackedge;
 299
 300                 //! Holds information, if node is the source of a backedge.
 301                 /** This information refers to the adjEntries on the targetnode
 302                  * and is used during the walkdown
 303                  */
 304                 NodeArray<SListPure<adjEntry> >& m_backedgeFlags;
 305
 306                 //! List of virtual bicomp roots, that are pertinent to the current embedded node
 307                 NodeArray<SListPure<node> >& m_pertinentRoots;
 308
 309                 //! Finds root node of the bicomp containing the stopping node \a stopX
 310                 node findRoot(node stopX);
 311
 312                 //! Extracts the highestFace Path of the bicomp containing both stopping nodes
 313                 void extractHighestFacePath(ListPure<adjEntry>& highestFacePath, int marker);
 314
 315                 //! Extracts externalFacePath in direction CCW and splits highestFacePath in highestXYPaths
 316                 void extractExternalFacePath(
 317                                         SListPure<adjEntry>& externalFacePath,
 318                                         const ListPure<adjEntry>& highestFacePath,
 319                                         int marker,
 320                                         int highMarker);
 321
 322                 //! Assign pertinent nodes to the different minortypes and extracts inner externalPaths
 323                 void splitInMinorTypes(
 324                                 const SListPure<adjEntry>& externalFacePath,
 325                                 int marker);
 326
 327                 //! Extracts external subgraph from node \a stop to ancestors of node with DFI \a root (without bundles)
 328                 void extractExternalSubgraph(
 329                                 const node stop,
 330                                 int root,
 331                                 SListPure<int>& externalStartnodes,
 332                                 SListPure<node>& externalEndnodes);
 333                 //! Extracts external subgraph from node \a stop to ancestors of node with DFI \a root (with bundles)
 334                 void extractExternalSubgraphBundles(
 335                                 const node stop,
 336                                 int root,
 337                                 SListPure<edge>& externalSubgraph,
 338                                 int nodeMarker);
 339
 340                 //! Extracts pertinent subgraph from all wNodes to \a V (without bundles)
 341                 void extractPertinentSubgraph(
 342                                 SListPure<WInfo>& W_All/*,
 343                                 const node V*/);
 344                 //! Extracts pertinent subgraph from all wNodes to \a V (with bundles)
 345                 void extractPertinentSubgraphBundles(
 346                                 const SListPure<WInfo>& W_All,
 347                                 const node V,
 348                                 SListPure<edge>& pertinentSubgraph,
 349                                 int nodeMarker);
 350 };
 351
 352 }
 353
 354 #endif