ext/OGDF/src/energybased/WSPD.h

   1 /*
   2  * $Revision: 2559 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-06 15:04:28 +0200 (Fr, 06. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration of class WSPD (well-separated pair decomposition).
  11  *
  12  * \author Martin Gronemann
  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 #ifndef OGDF_WSPD_H
  44 #define OGDF_WSPD_H
  45
  46 #include "LinearQuadtree.h"
  47
  48 namespace ogdf {
  49
  50 //! class for storing per node information
  51 struct WSPDNodeInfo
  52 {
  53         __uint32 numWSNodes; // total count of pairs where is either the first or second node
  54         __uint32 firstEntry; // the first pair in the nodes chain
  55         __uint32 lastEntry;  // the last pair in the nodes chain
  56 };
  57
  58
  59 //! class for storing per pair information
  60 struct WSPDPairInfo
  61 {
  62         __uint32 a;             // first node of the pair
  63         __uint32 b;             // second node of the pair
  64         __uint32 a_next;// next pair in the chain of the first node
  65         __uint32 b_next;// next pair in the chain of the second node
  66 };
  67
  68
  69 //! class for the Well-Separated-Pairs-Decomposition (WSPD)
  70 class WSPD
  71 {
  72 public:
  73         typedef LinearQuadtree::NodeID NodeID;
  74
  75         //! the constructor. allocates the mem
  76         WSPD(__uint32 maxNumNodes);
  77
  78         //! destructor
  79         ~WSPD(void);
  80
  81         //! returns the max number of nodes. (Equals the max number of nodes in the lin quadtree)
  82         inline __uint32 maxNumNodes() const
  83         {
  84                 return m_maxNumNodes;
  85         }
  86
  87         //! returns the number of well separated nodes for node a
  88         inline __uint32 numWSNodes(NodeID a) const
  89         {
  90                 return m_nodeInfo[a].numWSNodes;
  91         }
  92
  93         //! returns the total number of pairs
  94         inline __uint32 numPairs() const
  95         {
  96                 return m_numPairs;
  97         }
  98
  99         //! returns the maximum number of pairs
 100         inline __uint32 maxNumPairs() const
 101         {
 102                 return m_maxNumPairs;
 103         }
 104
 105         //! resets the array
 106         void clear();
 107
 108         //! add a well separated pair (a, b)
 109         void addWSP(NodeID a, NodeID b)
 110         {
 111                 // get the index of a free element
 112                 __uint32 e_index = m_numPairs++;
 113
 114                 // get the pair entry
 115                 WSPDPairInfo& e = pairInfo(e_index);
 116
 117                 // (a,b) is the pair we are adding
 118                 e.a = a;
 119                 e.b = b;
 120
 121                 // get the node info
 122                 WSPDNodeInfo& aInfo = nodeInfo(a);
 123                 WSPDNodeInfo& bInfo = nodeInfo(b);
 124
 125                 // if a is part of at least one pair
 126                 if (aInfo.numWSNodes)
 127                 {
 128                         // adjust the links
 129                         WSPDPairInfo& a_e = pairInfo(aInfo.lastEntry);
 130                         // check which one is a
 131                         if (a==a_e.a)
 132                                 a_e.a_next = e_index;
 133                         else
 134                                 a_e.b_next = e_index;
 135                 } else
 136                 {
 137                         // this pair is the first for a => set the firstEntry link
 138                         aInfo.firstEntry = e_index;
 139                 }
 140
 141                 // same for b: if a is part of at least one pair
 142                 if (bInfo.numWSNodes)
 143                 {
 144                         // adjust the links
 145                         WSPDPairInfo& b_e = pairInfo(bInfo.lastEntry);
 146                         // check which one is b
 147                         if (b==b_e.a)
 148                                 b_e.a_next = e_index;
 149                         else
 150                                 b_e.b_next = e_index;
 151                 } else
 152                 {
 153                         // this pair is the first for b => set the firstEntry link
 154                         bInfo.firstEntry = e_index;
 155                 }
 156                 // and the lastEntry link
 157                 aInfo.lastEntry = e_index;
 158                 bInfo.lastEntry = e_index;
 159                 // one more pair for each node
 160                 aInfo.numWSNodes++;
 161                 bInfo.numWSNodes++;
 162         }
 163
 164         //! returns the PairInfo by index
 165         inline WSPDPairInfo& pairInfo(__uint32 pairIndex) const
 166         {
 167                 return m_pairs[pairIndex];
 168         }
 169
 170         //! returns the NodeInfo by index
 171         inline WSPDNodeInfo& nodeInfo(NodeID node) const
 172         {
 173                 return m_nodeInfo[node];
 174         }
 175
 176         //! returns the index of the next pair of curr for node a
 177         inline __uint32 nextPair(__uint32 currPairIndex, NodeID a) const
 178         {
 179                 const WSPDPairInfo& currInfo = pairInfo(currPairIndex);
 180                 if (currInfo.a == a)
 181                         return currInfo.a_next;
 182                 return currInfo.b_next;
 183         }
 184
 185         //! returns the other node a is paired with in pair with the given index
 186         inline __uint32 wsNodeOfPair(__uint32 currPairIndex, NodeID a) const
 187         {
 188                 const WSPDPairInfo& currInfo = pairInfo(currPairIndex);
 189                 if (currInfo.a == a)
 190                         return currInfo.b;
 191                 return currInfo.a;
 192         }
 193
 194         //! returns the index of the first pair of node node
 195         inline __uint32 firstPairEntry(NodeID node) const
 196         {
 197                 return m_nodeInfo[node].firstEntry;
 198         }
 199
 200         // returns the size excluding small member vars (for profiling only)
 201         unsigned long sizeInBytes() const;
 202
 203 private:
 204         //! allocates all memory
 205         void allocate();
 206
 207         //! releases all memory
 208         void deallocate();
 209
 210         //! the max number of nodes. (Equals the max number of nodes in the lin quadtree)
 211         __uint32 m_maxNumNodes;
 212
 213         //! the array which holds the wspd information for one quadtree node
 214         WSPDNodeInfo* m_nodeInfo;
 215
 216         //! the array containing all pairs
 217         WSPDPairInfo* m_pairs;
 218
 219         //! the total number of pairs
 220         __uint32 m_numPairs;
 221
 222         //! the upper bound for the number of pairs
 223         __uint32 m_maxNumPairs;
 224 };
 225
 226 } // end of namespace ogdf
 227
 228 #endif
 229