chomp/struct/fibheap.h

Go to the documentation of this file.
00001 /// @addtogroup struct
00002 /// @{
00003 
00004 /////////////////////////////////////////////////////////////////////////////
00005 ///
00006 /// @file fibheap.h
00007 ///
00008 /// This file contains the definition of a Fibonacci heap
00009 /// optimized for good memory usage.
00010 ///
00011 /// @author Pawel Pilarczyk
00012 ///
00013 /////////////////////////////////////////////////////////////////////////////
00014 
00015 // Copyright (C) 1997-2007 by Pawel Pilarczyk.
00016 //
00017 // This file is part of the Homology Library.  This library is free software;
00018 // you can redistribute it and/or modify it under the terms of the GNU
00019 // General Public License as published by the Free Software Foundation;
00020 // either version 2 of the License, or (at your option) any later version.
00021 //
00022 // This library is distributed in the hope that it will be useful,
00023 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00024 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00025 // GNU General Public License for more details.
00026 //
00027 // You should have received a copy of the GNU General Public License along
00028 // with this software; see the file "license.txt".  If not, write to the
00029 // Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
00030 // MA 02111-1307, USA.
00031 
00032 // Started on August 13, 2007. Last revision: August 23, 2007.
00033 
00034 
00035 #ifndef _FIBHEAP_H_
00036 #define _FIBHEAP_H_
00037 
00038 
00039 #include "chomp/struct/multitab.h"
00040 //#include "chomp/struct/pool.h"
00041 
00042 
00043 namespace chomp {
00044 namespace homology {
00045 
00046 
00047 // --------------------------------------------------
00048 // ----------------- FIBONACCI HEAP -----------------
00049 // --------------------------------------------------
00050 
00051 /// This template contains the definition of a Fibonacci heap
00052 /// that can be used as an efficient priority queue,
00053 /// for example, in the Dijxtra graph algorithm.
00054 /// Note that if the "Delete" function is used then the elements
00055 /// must support the arithmetic subtraction of 1 to create a value
00056 /// that is strictly smaller than the given one (like the integers).
00057 /// This is a very specialized implementation which does not support
00058 /// the "Union" operation.
00059 /// Moreover, the "Delete" or "ExtractMinimum" don't actually free the
00060 /// memory used by the deleted elements in this implementation.
00061 /// See the description of the functions in this class for more information.
00062 template <class element>
00063 class FibonacciHeap
00064 {
00065 public:
00066         /// The type of a pointer to a node in the Fibonacci heap.
00067         typedef int NodePtr;
00068 
00069         /// The value used for a NULL pointer.
00070         static const int NullPtr = -1;
00071 
00072 private:
00073         /// The structure that holds a graph node for the graph
00074         /// representation of a Fibonacci heap.
00075         struct Node
00076         {
00077                 /// The value of the element that is used to compare
00078                 /// the elements.
00079                 element key;
00080 
00081                 /// A mark bit which indicates whether the node has lost
00082                 /// a child since the last time it was made a child of
00083                 /// another node.
00084                 bool mark;
00085 
00086                 /// The degree of the node, i.e., the number of its children.
00087                 /// Nodes that have been removed from the heap have the
00088                 /// degree set to -1.
00089                 int degree;
00090 
00091                 /// The number of this node 
00092                 int number;
00093 
00094                 /// A pointer to the parent node.
00095                 NodePtr parent;
00096 
00097                 /// A pointer to one of the children nodes.
00098                 NodePtr child;
00099 
00100                 /// A pointer to the left sibling node.
00101                 NodePtr left;
00102 
00103                 /// A pointer to the right sibling node.
00104                 NodePtr right;
00105         };
00106 
00107 public:
00108         /// The constructor of an empty Fibonacci heap.
00109         /// The maximal number of elements may be given if it is known.
00110         FibonacciHeap (int maxSize = 0);
00111 
00112         /// The destructor of a Fibonacci heap.
00113         ~FibonacciHeap ();
00114 
00115         /// Inserts an element into the heap.
00116         /// Returns the number of the node which is to be used
00117         /// for decreasing the key or removing this element from the heap.
00118         /// The numbers are returned in the ascending order, starting at 0.
00119         int Insert (const element &value);
00120 
00121         /// Returns the number of the node that contains the minimum.
00122         /// This is the number given to the node at its insertion.
00123         int Minimum () const;
00124 
00125         /// Returns the value of the node with the given number.
00126         const element &Value (int number) const;
00127 
00128         // Adds another heap to this one. Destroys the other one.
00129         // WARNING: Because of the node memory allocation strategy used
00130         // in this implementation of Fibonacci heaps, the complexity
00131         // of computing the union is O(n) instead of O(1).
00132         // Even worse, this operation is not yet implemented... Sorry!
00133 //      void Union (FibonacciHeap<element> &h);
00134 
00135         /// Extracts the minimum from the heap. The element is removed
00136         /// from the heap and its value is returned.
00137         element ExtractMinimum ();
00138 
00139         /// Decreases the key of the element identified by the given number
00140         /// to the new value.
00141         void DecreaseKey (int number, const element &value);
00142 
00143         /// Removes the element identified by the given number from the heap.
00144         void Delete (int number);
00145 
00146 private:
00147         /// The copy constructor is not allowed.
00148         FibonacciHeap (const FibonacciHeap<element> &);
00149 
00150         /// The assignment operator is not allowed.
00151         FibonacciHeap<element> &operator = (const FibonacciHeap<element> &);
00152 
00153         /// A pointer to the minimal element in the list of roots.
00154         NodePtr minRoot;
00155 
00156         /// The total number of nodes inserted to the heap and allocated
00157         /// in the multitable "nodes".
00158         int nodeCount;
00159 
00160         /// The array of nodes which hold the elements inserted to the heap
00161         /// in this order. The indices of these elements are returned
00162         /// while inserting them to the heap and can be used to access
00163         /// these nodes directly, e.g., in order to decrease their keys
00164         /// or delete them from the heap.
00165         multitable<Node> nodes;
00166 
00167         /// The minimal value that ever appeared in the heap. This value
00168         /// minus 1 is used as a substitute for the minus infinity while
00169         /// deleting elements from the heap with the use of the "Delete"
00170         /// function.
00171         element minValue;
00172 
00173         // The pool of nodes used for the Fibonacci heap.
00174 //      static pool<typename FibonacciHeap<element>::Node> *p;
00175 
00176         // The number of Fibonacci heaps in use.
00177 //      static int heapsInUse;
00178 
00179         /// Consolidates the Fibonacci heap by joining roots of equal degree.
00180         void Consolidate ();
00181 
00182         /// An auto-expandable array used by the "Consolidate" procedure.
00183         multitable<NodePtr> auxArray;
00184 
00185         /// The size of the prepared data in the array.
00186         int arrayPrepared;
00187 
00188         /// Cuts the tree.
00189         void Cut (const typename FibonacciHeap<element>::NodePtr &x,
00190                 const typename FibonacciHeap<element>::NodePtr &y);
00191 
00192         /// Does a cascading cut of the tree.
00193         void CascadingCut (typename FibonacciHeap<element>::NodePtr y);
00194 
00195         /// Shows a graph starting at the given node using DFS.
00196         void showGraph (std::ostream &out, int depth,
00197                 const typename FibonacciHeap<element>::NodePtr &x) const;
00198 
00199 public:
00200         /// Operator << shows the heap to the output stream.
00201         /// Essentially, this might be useful for debugging purposes only.
00202         friend inline std::ostream &operator << (std::ostream &out,
00203                 const FibonacciHeap<element> &h)
00204         {
00205                 out << "Fibonacci heap (min root = " << h. minRoot << "):\n";
00206                 NodePtr rootPtr = h. minRoot;
00207                 if (rootPtr == NullPtr)
00208                         return out;
00209                 do
00210                 {
00211                         h. showGraph (out, 0, rootPtr);
00212                         rootPtr = h. nodes [rootPtr]. right;
00213                 } while (rootPtr != h. minRoot);
00214                 return out;
00215         } /* operator << */
00216 
00217 }; /* class FibonacciHeap */
00218 
00219 //template <class element>
00220 //pool<typename FibonacciHeap<element>::Node> *FibonacciHeap<element>::p = 0;
00221 
00222 //template <class element>
00223 //int FibonacciHeap<element>::heapsInUse = 0;
00224 
00225 // --------------------------------------------------
00226 
00227 template <class element>
00228 void FibonacciHeap<element>::showGraph (std::ostream &out, int depth,
00229         const typename FibonacciHeap<element>::NodePtr &x) const
00230 {
00231         // show this node
00232         for (int i = 0; i < depth; ++ i)
00233                 out << "|   ";
00234         out << "+-- [" << nodes [x]. number << ": " << nodes [x]. key << "]";
00235         if (nodes [x]. left != NullPtr)
00236                 out << " left=" << nodes [x]. left;
00237         if (nodes [x]. right != NullPtr)
00238                 out << " right=" << nodes [x]. right;
00239         if (nodes [x]. parent != NullPtr)
00240                 out << " parent=" << nodes [x]. parent;
00241         if (nodes [x]. child != NullPtr)
00242                 out << " child=" << nodes [x]. child;
00243         out << " deg=" << nodes [x]. degree << "\n";
00244 
00245         // show all the children trees
00246         NodePtr child = nodes [x]. child;
00247         if (child == NullPtr)
00248                 return;
00249         do
00250         {
00251                 showGraph (out, depth + 1, child);
00252                 child = nodes [child]. right;
00253         } while (child != nodes [x]. child);
00254         return;
00255 } /* FibonacciHeap::showGraph */
00256 
00257 template <class element>
00258 inline FibonacciHeap<element>::FibonacciHeap (int maxSize):
00259         minRoot (NullPtr), nodeCount (0), nodes (maxSize), arrayPrepared (0)
00260 {
00261         // allocate a new pool for elements if this is the first heap
00262 //      if (!heapsInUse)
00263 //              p = new pool<typename FibonacciHeap<element>::Node>;
00264 
00265         // increase the number of heaps in use
00266 //      ++ heapsInUse;
00267 
00268         return;
00269 } /* FibonacciHeap::FibonacciHeap */
00270 
00271 template <class element>
00272 inline FibonacciHeap<element>::~FibonacciHeap ()
00273 {
00274         // decrease the number of heaps in use
00275 //      -- heapsInUse;
00276 
00277         // delete the pool for elements if this was the last heap
00278 //      if (!heapsInUse)
00279 //              delete p;
00280 
00281         return;
00282 } /* FibonacciHeap::~FibonacciHeap */
00283 
00284 template <class element>
00285 inline FibonacciHeap<element>::FibonacciHeap (const FibonacciHeap<element> &)
00286 {
00287         throw "Copy constructor for a Fibonacci heap not implemented.";
00288         return;
00289 } /* FibonacciHeap::FibonacciHeap */
00290 
00291 template <class element>
00292 inline FibonacciHeap<element> &FibonacciHeap<element>::operator =
00293         (const FibonacciHeap<element> &)
00294 {
00295         throw "Assignment operator for a Fibonacci heap not implemented.";
00296         return *this;
00297 } /* FibonacciHeap::operator = */
00298 
00299 template <class element>
00300 inline int FibonacciHeap<element>::Insert (const element &value)
00301 {
00302         // allocate memory for the new node
00303         NodePtr nodePtr = nodeCount;
00304 
00305         // update the minimal value
00306         if (!nodeCount)
00307                 minValue = value;
00308         else if (value < minValue)
00309                 minValue = value;
00310 
00311         // fill in the fields of the new node
00312         Node &node = nodes [nodePtr];
00313         node. key = value;
00314         node. mark = false;
00315         node. degree = 0;
00316         node. number = nodeCount;
00317         node. parent = NullPtr;
00318         node. child = NullPtr;
00319 
00320         // insert the node to the unordered bidirectional list of roots
00321         if (minRoot == NullPtr)
00322         {
00323                 node. left = nodePtr;
00324                 node. right = nodePtr;
00325         }
00326         else
00327         {
00328                 node. left = nodes [minRoot]. left;
00329                 node. right = minRoot;
00330                 nodes [node. left]. right = nodePtr;
00331                 nodes [node. right]. left = nodePtr;
00332         }
00333 
00334         // make a correction to the pointer to the minimal root if necessary
00335         if ((minRoot == NullPtr) || (value < nodes [minRoot]. key))
00336                 minRoot = nodePtr;
00337 
00338         // return the number of the new node and increase the number of nodes
00339         return nodeCount ++;
00340 } /* FibonacciHeap::Insert */
00341 
00342 template <class element>
00343 inline int FibonacciHeap<element>::Minimum () const
00344 {
00345         return minRoot;
00346 } /* FibonacciHeap::Minimum */
00347 
00348 template <class element>
00349 inline const element &FibonacciHeap<element>::Value (int number) const
00350 {
00351         return nodes [number]. key;
00352 } /* FibonacciHeap::Value */
00353 
00354 /*
00355 template <class element>
00356 inline void FibonacciHeap<element>::Union (FibonacciHeap<element> &h)
00357 {
00358         // if the other heap is empty, then do nothing
00359         if (h. minRoot == NullPtr)
00360                 return;
00361 
00362         // if this heap is empty, then just copy the data
00363         if (minRoot == NullPtr)
00364         {
00365                 minRoot = h. minRoot;
00366                 nodeCount = h. nodeCount;
00367                 minValue = h. minValue;
00368                 return;
00369         }
00370 
00371         // copy the nodes from the other heap to this one and update links
00372         // TODO
00373 
00374         // join the root lists
00375         // TODO
00376 
00377         // update the node count
00378         nodeCount += h. nodeCount;
00379 
00380         // update the minimal key value
00381         if (h. minValue < minValue)
00382                 minValue = h. minValue;
00383 
00384         // make the other heap empty
00385         h. minRoot = NullPtr;
00386         h. nodeCount = 0;
00387         throw "The union of Fibonacci heaps not implemented, yet.";
00388         return;
00389 }*/ /* FibonacciHeap::Union */
00390 
00391 template <class element>
00392 inline void FibonacciHeap<element>::Consolidate ()
00393 {
00394         // do nothing if the heap is empty
00395         if (minRoot == NullPtr)
00396                 return;
00397 
00398         // for each node in the root list of the heap...
00399         NodePtr node = minRoot;
00400         int maxDegree = 0;
00401         do
00402         {
00403                 // take the node for the loop and get its degree
00404                 NodePtr x = node;
00405                 int d = nodes [x]. degree;
00406 
00407                 // prepare the next node from the root list for the next time
00408                 node = nodes [node]. right;
00409 
00410                 // expand the auxiliary array if necessary
00411                 while (arrayPrepared <= d)
00412                         auxArray [arrayPrepared ++] = NullPtr;
00413 
00414                 // update the strict upper limit on the degree used
00415                 if (maxDegree <= d)
00416                         maxDegree = d + 1;
00417 
00418                 // join this tree with another one of the same degree if any
00419                 while (auxArray [d] != NullPtr)
00420                 {
00421                         // take the node of the same degree as x
00422                         NodePtr y = auxArray [d];
00423 
00424                         // swap the node pointers if necessary
00425                         if (nodes [y]. key < nodes [x]. key)
00426                         {
00427                                 NodePtr tmp = x;
00428                                 x = y;
00429                                 y = tmp;
00430                         }
00431 
00432                         // clear the mark of the node y
00433                         nodes [y]. mark = false;
00434 
00435                         // make the node y a child of the node x
00436                         nodes [y]. parent = x;
00437                         NodePtr child = nodes [x]. child;
00438                         if (child == NullPtr)
00439                         {
00440                                 nodes [x]. child = y;
00441                                 nodes [y]. left = y;
00442                                 nodes [y]. right = y;
00443                         }
00444                         else
00445                         {
00446                                 nodes [y]. left = child;
00447                                 nodes [y]. right = nodes [child]. right;
00448                                 nodes [child]. right = y;
00449                                 nodes [nodes [y]. right]. left = y;
00450                         }
00451                         ++ nodes [x]. degree;
00452 
00453                         // clear the entry which stored the node of degree d
00454                         auxArray [d] = NullPtr;
00455 
00456                         // increase the degree to the degree of x
00457                         ++ d;
00458 
00459                         // expand the auxiliary array if necessary
00460                         if (arrayPrepared <= d)
00461                                 auxArray [arrayPrepared ++] = NullPtr;
00462 
00463                         // update the strict upper limit on the degree used
00464                         if (maxDegree <= d)
00465                                 maxDegree = d + 1;
00466                 }
00467 
00468                 // put this node in the array
00469                 auxArray [d] = x;
00470 
00471         } while (node != minRoot);
00472 
00473         // reconstruct the root list from the auxiliary array
00474         minRoot = NullPtr;
00475         for (int d = 0; d < maxDegree; ++ d)
00476         {
00477                 // skip entries of the array which don't point to nodes
00478                 if (auxArray [d] == NullPtr)
00479                         continue;
00480 
00481                 // take the node pointer of the array
00482                 NodePtr nodePtr = auxArray [d];
00483                 auxArray [d] = NullPtr;
00484                 Node &node = nodes [nodePtr];
00485 
00486                 // link this node to the root list
00487                 if (minRoot == NullPtr)
00488                 {
00489                         node. left = nodePtr;
00490                         node. right = nodePtr;
00491                 }
00492                 else
00493                 {
00494                         node. left = minRoot;
00495                         node. right = nodes [minRoot]. right;
00496                         nodes [node. left]. right = nodePtr;
00497                         nodes [node. right]. left = nodePtr;
00498                 }
00499 
00500                 // update the pointer to the minimal root node if necessary
00501                 if ((minRoot == NullPtr) ||
00502                         (node. key < nodes [minRoot]. key))
00503                 {
00504                         minRoot = nodePtr;
00505                 }
00506         }
00507         return;
00508 } /* FibonacciHeap::Consolidate */
00509 
00510 template <class element>
00511 inline element FibonacciHeap<element>::ExtractMinimum ()
00512 {
00513         // determine the node with the minimum to extract
00514         NodePtr nodePtr = minRoot;
00515         Node &node = nodes [minRoot];
00516 
00517         // make the children of the node become root nodes
00518         // and attach them to the root list
00519         NodePtr child = node. child;
00520         if (child != NullPtr)
00521         {
00522                 // clear the child pointer in the parent
00523                 node. child = NullPtr;
00524 
00525                 // clear the parent pointers in the children
00526                 while (nodes [child]. parent != NullPtr)
00527                 {
00528                         nodes [child]. parent = NullPtr;
00529                         child = nodes [child]. right;
00530                 }
00531 
00532                 // attach the children to the root list
00533                 NodePtr leftChild = child;
00534                 NodePtr rightChild = nodes [child]. right;
00535                 NodePtr leftRoot = nodePtr;
00536                 NodePtr rightRoot = node. right;
00537                 nodes [leftRoot]. right = rightChild;
00538                 nodes [rightRoot]. left = leftChild;
00539                 nodes [leftChild]. right = rightRoot;
00540                 nodes [rightChild]. left = leftRoot;
00541         }
00542 
00543         // make the min root pointer point at any other node
00544         // and remove the node from the root list
00545         if (node. right != nodePtr)
00546         {
00547                 minRoot = node. right;
00548                 nodes [minRoot]. left = node. left;
00549                 nodes [node. left]. right = minRoot;
00550         }
00551         else
00552                 minRoot = NullPtr;
00553 
00554         // reset the fields in the node to avoid any confusion in the future
00555         node. left = NullPtr;
00556         node. right = NullPtr;
00557         node. parent = NullPtr;
00558         node. child = NullPtr;
00559         node. degree = -1;
00560 
00561         // consolidate the heap
00562         Consolidate ();
00563 
00564         return node. key;
00565 } /* FibonacciHeap::ExtractMinimum */
00566 
00567 template <class element>
00568 inline void FibonacciHeap<element>::Cut
00569         (const typename FibonacciHeap<element>::NodePtr &x,
00570         const typename FibonacciHeap<element>::NodePtr &y)
00571 {
00572         // remove x from the children of y:
00573         // case 1: if x is the only child of y
00574         nodes [x]. parent = NullPtr;
00575         if (nodes [x]. right == x)
00576         {
00577                 nodes [y]. child = NullPtr;
00578         }
00579         //case 2: if there are also other children of y
00580         else
00581         {
00582                 NodePtr leftChild = nodes [x]. left;
00583                 NodePtr rightChild = nodes [x]. right;
00584                 nodes [y]. child = rightChild;
00585                 nodes [leftChild]. right = rightChild;
00586                 nodes [rightChild]. left = leftChild;
00587         }
00588 
00589         // update the degree of y
00590         -- nodes [y]. degree;
00591 
00592         // add x to the root list of the heap
00593         NodePtr leftRoot = minRoot;
00594         NodePtr rightRoot = nodes [minRoot]. right;
00595         nodes [x]. left = leftRoot;
00596         nodes [x]. right = rightRoot;
00597         nodes [leftRoot]. right = x;
00598         nodes [rightRoot]. left = x;
00599 
00600         // clear the marking of the node x if any
00601         nodes [x]. mark = false;
00602 
00603         return;
00604 } /* FibonacciHeap::Cut */
00605 
00606 template <class element>
00607 inline void FibonacciHeap<element>::CascadingCut
00608         (typename FibonacciHeap<element>::NodePtr y)
00609 {
00610         // do the cascading cut while the node has a parent
00611         while (!(nodes [y]. parent == NullPtr))
00612         {
00613                 // if this is the first time the node lost its child,
00614                 // then just mark the node and exit the cascading cut
00615                 if (!nodes [y]. mark)
00616                 {
00617                         nodes [y]. mark = true;
00618                         return;
00619                 }
00620 
00621                 // cut the node and continue the cascading cut
00622                 // with its parent
00623                 NodePtr z = nodes [y]. parent;
00624                 Cut (y, z);
00625                 y = z;
00626         }
00627         return;
00628 } /* FibonacciHeap::CascadingCut */
00629 
00630 template <class element>
00631 inline void FibonacciHeap<element>::DecreaseKey (int number,
00632         const element &value)
00633 {
00634         // translate the number to a node pointer
00635         NodePtr x (number);
00636 
00637         // ignore this action if the node is no longer in the heap
00638         if (nodes [x]. degree == -1)
00639                 return;
00640 
00641         // update the minimal value in the heap
00642         if (value < minValue)
00643                 minValue = value;
00644 
00645         // update the value of the node
00646         nodes [x]. key = value;
00647 
00648         // cut the tree so that the node x is in the root list
00649         NodePtr y = nodes [x]. parent;
00650         if ((y != NullPtr) && (value < nodes [y]. key))
00651         {
00652                 Cut (x, y);
00653                 CascadingCut (y);
00654         }
00655 
00656         // update the pointer to the minimal node in the root list
00657         if (value < nodes [minRoot]. key)
00658                 minRoot = x;
00659 
00660         return;
00661 } /* FibonacciHeap::DecreaseKey */
00662 
00663 template <class element>
00664 inline void FibonacciHeap<element>::Delete (int number)
00665 {
00666         element value = minValue;
00667         DecreaseKey (number, value - 1);
00668         ExtractMinimum ();
00669         minValue = value;
00670         return;
00671 } /* FibonacciHeap::Delete */
00672 
00673 
00674 } // namespace homology
00675 } // namespace chomp
00676 
00677 #endif // _FIBHEAP_H_
00678 
00679 /// @}
00680 

Generated on Wed Nov 21 11:08:41 2007 for The Uniform Expansion Software by  doxygen 1.5.3