ext/OGDF/ogdf/internal/planarity/BoyerMyrvoldInit.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 classes BoyerMyrvoldInit and BucketLowPoint
  11  *
  12  * \author Jens Schmidt
  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 #ifdef _MSC_VER
  45 #pragma once
  46 #endif
  47
  48 #ifndef OGDF_BOYER_MYRVOLD_INIT_H
  49 #define OGDF_BOYER_MYRVOLD_INIT_H
  50
  51
  52 #include <ogdf/internal/planarity/BoyerMyrvoldPlanar.h>
  53 #include <ogdf/basic/List.h>
  54
  55
  56 namespace ogdf {
  57
  58 //! This class is used in the Boyer-Myrvold planarity test for preprocessing purposes.
  59 /**
  60 * Among these is the computation of lowpoints, highestSubtreeDFIs,
  61 * separatedDFSChildList and of course building the DFS-tree.
  62 */
  63 class BoyerMyrvoldInit {
  64         public:
  65                 //! Constructor, the parameter BoyerMyrvoldPlanar is needed
  66                 BoyerMyrvoldInit(BoyerMyrvoldPlanar* pBM);
  67
  68                 //! Destructor
  69                 ~BoyerMyrvoldInit() { }
  70
  71                 //! Creates the DFSTree
  72                 void computeDFS();
  73
  74                 //! Computes lowpoint, highestSubtreeDFI and links virtual to nonvirtual vertices
  75                 void computeLowPoints();
  76
  77                 //! Computes the list of separated DFS children for all nodes
  78                 void computeDFSChildLists();
  79
  80                 // avoid automatic creation of assignment operator
  81                 //! Assignment operator is undefined!
  82                 BoyerMyrvoldInit &operator=(const BoyerMyrvoldInit &);
  83
  84         private:
  85                 //! The input graph
  86                 Graph& m_g;
  87
  88                 //! Some parameters... see BoyerMyrvold.h for further instructions
  89                 const int& m_embeddingGrade;
  90                 const bool& m_randomDFSTree;
  91
  92                 //! Link to non-virtual vertex of a virtual Vertex.
  93                 /** A virtual vertex has negative DFI of the DFS-Child of related non-virtual Vertex
  94                  */
  95                 NodeArray<node>& m_realVertex;
  96
  97                 //! The one and only DFI-Array
  98                 NodeArray<int>& m_dfi;
  99
 100                 //! Returns appropriate node from given DFI
 101                 Array<node>& m_nodeFromDFI;
 102
 103                 //! Links to opposite adjacency entries on external face in clockwise resp. ccw order
 104                 /** m_link[0]=CCW, m_link[1]=CW
 105                  */
 106                 NodeArray<adjEntry> (&m_link)[2];
 107
 108                 //! The adjEntry which goes from DFS-parent to current vertex
 109                 NodeArray<adjEntry>& m_adjParent;
 110
 111                 //! The DFI of the least ancestor node over all backedges
 112                 /** If no backedge exists, the least ancestor is the DFI of that node itself
 113                  */
 114                 NodeArray<int>& m_leastAncestor;
 115
 116                 //! Contains the type of each \a edge
 117                 /** @param 0 = EDGE_UNDEFINED
 118                  * @param 1 = EDGE_SELFLOOP
 119                  * @param 2 = EDGE_BACK
 120                  * @param 3 = EDGE_DFS
 121                  * @param 4 = EDGE_DFS_PARALLEL
 122                  * @param 5 = EDGE_BACK_DELETED
 123                  */
 124                 EdgeArray<int>& m_edgeType;
 125
 126                 //! The lowpoint of each \a node
 127                 NodeArray<int>& m_lowPoint;
 128
 129                 //! The highest DFI in a subtree with \a node as root
 130                 NodeArray<int>& m_highestSubtreeDFI;
 131
 132                 //! A list to all separated DFS-children of \a node
 133                 /** The list is sorted by lowpoint values (in linear time)
 134                 */
 135                 NodeArray<ListPure<node> >& m_separatedDFSChildList;
 136
 137                 //! Pointer to \a node contained in the DFSChildList of his parent, if exists.
 138                 /** If node isn't in list or list doesn't exist, the pointer is set to NULL.
 139                 */
 140                 NodeArray<ListIterator<node> >& m_pNodeInParent;
 141
 142                 //! Creates and links a virtual vertex of the node belonging to \a father
 143                 void createVirtualVertex(const adjEntry father);
 144 };
 145
 146 //! BucketFunction for lowPoint buckets
 147 /** Parameter lowPoint may not be deleted til destruction of this class.
 148 */
 149 class BucketLowPoint : public BucketFunc<node> {
 150         public:
 151                 BucketLowPoint(const NodeArray<int>& lowPoint) :m_pLow(&lowPoint) { }
 152
 153                 //! This function has to be derived from BucketFunc, it gets the buckets from lowPoint-Array
 154                 int getBucket(const node& v) {
 155                         return (*m_pLow)[v];
 156                 }
 157         private:
 158                 //! Stored to be able to get the buckets
 159                 const NodeArray<int>* m_pLow;
 160 };
 161
 162 }
 163
 164
 165 #endif