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

   1 /*
   2  * $Revision: 2555 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-06 12:12:10 +0200 (Fr, 06. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration of class whaInfo.
  11  *
  12  * \author Sebastian Leipert
  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
  49 #ifndef OGDF_WHA_INFO_H
  50 #define OGDF_WHA_INFO_H
  51
  52
  53 #include <ogdf/internal/planarity/PQNodeRoot.h>
  54
  55
  56 namespace ogdf{
  57
  58 /**
  59 The definitions for W_TYPE, B_TYPE, H_TYPE and A_TYPE
  60 describe the type of a node during the computation of the
  61 maximal pertinent sequence. A pertinent node X in the PQ-tree will be
  62 either of type B, W, A or H. Together
  63 with some other information stored at every node the pertinent leaves
  64 in the frontier of X that have to be deleted. For further
  65 description of the types see Jayakumar, Thulasiraman and Swamy 1989.
  66 */
  67
  68 enum whaType {
  69         W_TYPE, B_TYPE, H_TYPE, A_TYPE
  70 };
  71
  72
  73
  74 class whaInfo
  75 {
  76         template<class T, class Y> friend class MaxSequencePQTree;
  77
  78 public:
  79
  80         //The deleteType is set to type b (= keep all leaves in the frontier).
  81         whaInfo() {
  82                 m_a = 0;
  83                 m_h = 0;
  84                 m_w = 0;
  85                 m_deleteType       = B_TYPE;
  86                 m_pertLeafCount   = 0;
  87                 m_notVisitedCount = 0;
  88                 m_aChild          = 0;
  89                 m_hChild1         = 0;
  90                 m_hChild2         = 0;
  91                 m_hChild2Sib      = 0;
  92         }
  93
  94
  95         ~whaInfo() {}
  96
  97
  98         void defaultValues() {
  99                 m_a = 0;
 100                 m_h = 0;
 101                 m_w = 0;
 102                 m_deleteType = B_TYPE;
 103                 m_pertLeafCount = 0;
 104                 m_notVisitedCount = 0;
 105         }
 106
 107
 108 private:
 109
 110
 111         // number of pertinent leaves in the frontier of the node respectively the
 112         // number of leaves that have to be deleted in the frontier of the node to
 113         // make it an empty node.
 114         int m_h;
 115
 116         // number of pertinent leaves in the frontier of the node that have to be
 117         // deleted in order to create a node of type h, that is a node, where a
 118         // permutation of the leaves of the node exist such that the remaining
 119         // pertinent leaves form a consecutive sequence on one end of the permutation.
 120         int m_w;
 121
 122         // number of pertinent leaves in the frontier of the node that have to be
 123         // deleted in order to create a node of type $a$, that is a node, where a
 124         // permutation of the leaves of the node exist such that the remaining
 125         // pertinent leaves form a consecutive somewhere within the permutation.
 126         int m_a;
 127
 128         // deleteType is type of the node being either
 129         // W_TYPE, B_TYPE, H_TYPE or A_TYPE.
 130         whaType m_deleteType;
 131
 132         //the number of pertinent leaves in the frontier of a node.
 133         int m_pertLeafCount;
 134
 135         //counts the number of pertinent children, that have not been
 136         // processed yet during the computation of the w,h,a-numbering.
 137         int m_notVisitedCount;
 138
 139         // a pointer to the child of node that has to be of type a if the
 140         // node itself has been determined to be of type a.
 141         PQNodeRoot *m_aChild;
 142
 143         // a pointer to the child of node that has to be of type h if the
 144         // node itself has been determined to be of type h.
 145         PQNodeRoot *m_hChild1;
 146
 147         // a pointer to the child of node that has to be of type h if the
 148         // node itself has been determined to be of type a and m_aChild does
 149         // contain the empty pointer.
 150         PQNodeRoot *m_hChild2;
 151
 152
 153         // m_hChild2Sib is a pointer to the pertinent sibling of m_hChild2. This
 154         // pointer is necessary if the sequence of pertinent children is not unique.
 155         PQNodeRoot *m_hChild2Sib;
 156
 157         OGDF_NEW_DELETE
 158 };
 159
 160 }
 161
 162 #endif