COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/fib_heap.h @ 711:28cfac049a6a

Last change on this file since 711:28cfac049a6a was 711:28cfac049a6a, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Unify member names in heaps (#299)

The following renamings are made.

Public members:

Private members:

  • bubble_up() -> bubbleUp()
  • bubble_down() -> bubbleDown()
  • second_child() -> secondChild()
  • makeroot() -> makeRoot()
  • relocate_last() -> relocateLast()
  • data -> _data
  • boxes -> _boxes
File size: 13.5 KB
RevLine 
[681]1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2009
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_FIB_HEAP_H
20#define LEMON_FIB_HEAP_H
21
22///\file
[710]23///\ingroup heaps
[709]24///\brief Fibonacci heap implementation.
[681]25
26#include <vector>
[709]27#include <utility>
[681]28#include <functional>
29#include <lemon/math.h>
30
31namespace lemon {
32
[710]33  /// \ingroup heaps
[681]34  ///
[709]35  /// \brief Fibonacci heap data structure.
[681]36  ///
[709]37  /// This class implements the \e Fibonacci \e heap data structure.
38  /// It fully conforms to the \ref concepts::Heap "heap concept".
[681]39  ///
[709]40  /// The methods \ref increase() and \ref erase() are not efficient in a
41  /// Fibonacci heap. In case of many calls of these operations, it is
42  /// better to use other heap structure, e.g. \ref BinHeap "binary heap".
[681]43  ///
[709]44  /// \tparam PR Type of the priorities of the items.
45  /// \tparam IM A read-writable item map with \c int values, used
46  /// internally to handle the cross references.
47  /// \tparam CMP A functor class for comparing the priorities.
48  /// The default is \c std::less<PR>.
[681]49#ifdef DOXYGEN
[709]50  template <typename PR, typename IM, typename CMP>
[681]51#else
[709]52  template <typename PR, typename IM, typename CMP = std::less<PR> >
[681]53#endif
54  class FibHeap {
55  public:
[709]56
57    /// Type of the item-int map.
[683]58    typedef IM ItemIntMap;
[709]59    /// Type of the priorities.
60    typedef PR Prio;
61    /// Type of the items stored in the heap.
[681]62    typedef typename ItemIntMap::Key Item;
[709]63    /// Type of the item-priority pairs.
[681]64    typedef std::pair<Item,Prio> Pair;
[709]65    /// Functor type for comparing the priorities.
[683]66    typedef CMP Compare;
[681]67
68  private:
[683]69    class Store;
[681]70
[683]71    std::vector<Store> _data;
72    int _minimum;
73    ItemIntMap &_iim;
74    Compare _comp;
75    int _num;
[681]76
77  public:
[683]78
[709]79    /// \brief Type to represent the states of the items.
[683]80    ///
[709]81    /// Each item has a state associated to it. It can be "in heap",
82    /// "pre-heap" or "post-heap". The latter two are indifferent from the
[683]83    /// heap's point of view, but may be useful to the user.
84    ///
85    /// The item-int map must be initialized in such way that it assigns
86    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
[681]87    enum State {
[683]88      IN_HEAP = 0,    ///< = 0.
89      PRE_HEAP = -1,  ///< = -1.
90      POST_HEAP = -2  ///< = -2.
[681]91    };
92
[709]93    /// \brief Constructor.
[681]94    ///
[709]95    /// Constructor.
96    /// \param map A map that assigns \c int values to the items.
97    /// It is used internally to handle the cross references.
98    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
[683]99    explicit FibHeap(ItemIntMap &map)
100      : _minimum(0), _iim(map), _num() {}
[681]101
[709]102    /// \brief Constructor.
[681]103    ///
[709]104    /// Constructor.
105    /// \param map A map that assigns \c int values to the items.
106    /// It is used internally to handle the cross references.
107    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
108    /// \param comp The function object used for comparing the priorities.
[683]109    FibHeap(ItemIntMap &map, const Compare &comp)
110      : _minimum(0), _iim(map), _comp(comp), _num() {}
[681]111
112    /// \brief The number of items stored in the heap.
113    ///
[709]114    /// This function returns the number of items stored in the heap.
[683]115    int size() const { return _num; }
[681]116
[709]117    /// \brief Check if the heap is empty.
[681]118    ///
[709]119    /// This function returns \c true if the heap is empty.
[683]120    bool empty() const { return _num==0; }
[681]121
[709]122    /// \brief Make the heap empty.
[681]123    ///
[709]124    /// This functon makes the heap empty.
125    /// It does not change the cross reference map. If you want to reuse
126    /// a heap that is not surely empty, you should first clear it and
127    /// then you should set the cross reference map to \c PRE_HEAP
128    /// for each item.
[681]129    void clear() {
[683]130      _data.clear(); _minimum = 0; _num = 0;
[681]131    }
132
[709]133    /// \brief Insert an item into the heap with the given priority.
[681]134    ///
[709]135    /// This function inserts the given item into the heap with the
136    /// given priority.
137    /// \param item The item to insert.
138    /// \param prio The priority of the item.
139    /// \pre \e item must not be stored in the heap.
140    void push (const Item& item, const Prio& prio) {
[683]141      int i=_iim[item];
[681]142      if ( i < 0 ) {
[683]143        int s=_data.size();
144        _iim.set( item, s );
145        Store st;
[681]146        st.name=item;
[683]147        _data.push_back(st);
[681]148        i=s;
149      } else {
[683]150        _data[i].parent=_data[i].child=-1;
151        _data[i].degree=0;
152        _data[i].in=true;
153        _data[i].marked=false;
[681]154      }
155
[683]156      if ( _num ) {
157        _data[_data[_minimum].right_neighbor].left_neighbor=i;
158        _data[i].right_neighbor=_data[_minimum].right_neighbor;
159        _data[_minimum].right_neighbor=i;
160        _data[i].left_neighbor=_minimum;
[709]161        if ( _comp( prio, _data[_minimum].prio) ) _minimum=i;
[681]162      } else {
[683]163        _data[i].right_neighbor=_data[i].left_neighbor=i;
164        _minimum=i;
[681]165      }
[709]166      _data[i].prio=prio;
[683]167      ++_num;
[681]168    }
169
[709]170    /// \brief Return the item having minimum priority.
[681]171    ///
[709]172    /// This function returns the item having minimum priority.
173    /// \pre The heap must be non-empty.
[683]174    Item top() const { return _data[_minimum].name; }
[681]175
[709]176    /// \brief The minimum priority.
[681]177    ///
[709]178    /// This function returns the minimum priority.
179    /// \pre The heap must be non-empty.
180    Prio prio() const { return _data[_minimum].prio; }
[681]181
[709]182    /// \brief Remove the item having minimum priority.
[681]183    ///
[709]184    /// This function removes the item having minimum priority.
[681]185    /// \pre The heap must be non-empty.
186    void pop() {
187      /*The first case is that there are only one root.*/
[683]188      if ( _data[_minimum].left_neighbor==_minimum ) {
189        _data[_minimum].in=false;
190        if ( _data[_minimum].degree!=0 ) {
[711]191          makeRoot(_data[_minimum].child);
[683]192          _minimum=_data[_minimum].child;
[681]193          balance();
194        }
195      } else {
[683]196        int right=_data[_minimum].right_neighbor;
197        unlace(_minimum);
198        _data[_minimum].in=false;
199        if ( _data[_minimum].degree > 0 ) {
200          int left=_data[_minimum].left_neighbor;
201          int child=_data[_minimum].child;
202          int last_child=_data[child].left_neighbor;
[681]203
[711]204          makeRoot(child);
[681]205
[683]206          _data[left].right_neighbor=child;
207          _data[child].left_neighbor=left;
208          _data[right].left_neighbor=last_child;
209          _data[last_child].right_neighbor=right;
[681]210        }
[683]211        _minimum=right;
[681]212        balance();
213      } // the case where there are more roots
[683]214      --_num;
[681]215    }
216
[709]217    /// \brief Remove the given item from the heap.
[681]218    ///
[709]219    /// This function removes the given item from the heap if it is
220    /// already stored.
221    /// \param item The item to delete.
222    /// \pre \e item must be in the heap.
[681]223    void erase (const Item& item) {
[683]224      int i=_iim[item];
[681]225
[683]226      if ( i >= 0 && _data[i].in ) {
227        if ( _data[i].parent!=-1 ) {
228          int p=_data[i].parent;
[681]229          cut(i,p);
230          cascade(p);
231        }
[683]232        _minimum=i;     //As if its prio would be -infinity
[681]233        pop();
234      }
235    }
236
[709]237    /// \brief The priority of the given item.
[681]238    ///
[709]239    /// This function returns the priority of the given item.
240    /// \param item The item.
241    /// \pre \e item must be in the heap.
242    Prio operator[](const Item& item) const {
243      return _data[_iim[item]].prio;
244    }
245
246    /// \brief Set the priority of an item or insert it, if it is
247    /// not stored in the heap.
248    ///
249    /// This method sets the priority of the given item if it is
250    /// already stored in the heap. Otherwise it inserts the given
251    /// item into the heap with the given priority.
252    /// \param item The item.
253    /// \param prio The priority.
254    void set (const Item& item, const Prio& prio) {
[683]255      int i=_iim[item];
[709]256      if ( i >= 0 && _data[i].in ) {
257        if ( _comp(prio, _data[i].prio) ) decrease(item, prio);
258        if ( _comp(_data[i].prio, prio) ) increase(item, prio);
259      } else push(item, prio);
260    }
261
262    /// \brief Decrease the priority of an item to the given value.
263    ///
264    /// This function decreases the priority of an item to the given value.
265    /// \param item The item.
266    /// \param prio The priority.
267    /// \pre \e item must be stored in the heap with priority at least \e prio.
268    void decrease (const Item& item, const Prio& prio) {
269      int i=_iim[item];
270      _data[i].prio=prio;
[683]271      int p=_data[i].parent;
[681]272
[709]273      if ( p!=-1 && _comp(prio, _data[p].prio) ) {
[681]274        cut(i,p);
275        cascade(p);
276      }
[709]277      if ( _comp(prio, _data[_minimum].prio) ) _minimum=i;
[681]278    }
279
[709]280    /// \brief Increase the priority of an item to the given value.
[681]281    ///
[709]282    /// This function increases the priority of an item to the given value.
283    /// \param item The item.
284    /// \param prio The priority.
285    /// \pre \e item must be stored in the heap with priority at most \e prio.
286    void increase (const Item& item, const Prio& prio) {
[681]287      erase(item);
[709]288      push(item, prio);
[681]289    }
290
[709]291    /// \brief Return the state of an item.
[681]292    ///
[709]293    /// This method returns \c PRE_HEAP if the given item has never
294    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
295    /// and \c POST_HEAP otherwise.
296    /// In the latter case it is possible that the item will get back
297    /// to the heap again.
298    /// \param item The item.
[681]299    State state(const Item &item) const {
[683]300      int i=_iim[item];
[681]301      if( i>=0 ) {
[683]302        if ( _data[i].in ) i=0;
[681]303        else i=-2;
304      }
305      return State(i);
306    }
307
[709]308    /// \brief Set the state of an item in the heap.
[681]309    ///
[709]310    /// This function sets the state of the given item in the heap.
311    /// It can be used to manually clear the heap when it is important
312    /// to achive better time complexity.
[681]313    /// \param i The item.
314    /// \param st The state. It should not be \c IN_HEAP.
315    void state(const Item& i, State st) {
316      switch (st) {
317      case POST_HEAP:
318      case PRE_HEAP:
319        if (state(i) == IN_HEAP) {
320          erase(i);
321        }
[683]322        _iim[i] = st;
[681]323        break;
324      case IN_HEAP:
325        break;
326      }
327    }
328
329  private:
330
331    void balance() {
332
[683]333      int maxdeg=int( std::floor( 2.08*log(double(_data.size()))))+1;
[681]334
335      std::vector<int> A(maxdeg,-1);
336
337      /*
338       *Recall that now minimum does not point to the minimum prio element.
339       *We set minimum to this during balance().
340       */
[683]341      int anchor=_data[_minimum].left_neighbor;
342      int next=_minimum;
[681]343      bool end=false;
344
345      do {
346        int active=next;
347        if ( anchor==active ) end=true;
[683]348        int d=_data[active].degree;
349        next=_data[active].right_neighbor;
[681]350
351        while (A[d]!=-1) {
[683]352          if( _comp(_data[active].prio, _data[A[d]].prio) ) {
[681]353            fuse(active,A[d]);
354          } else {
355            fuse(A[d],active);
356            active=A[d];
357          }
358          A[d]=-1;
359          ++d;
360        }
361        A[d]=active;
362      } while ( !end );
363
364
[683]365      while ( _data[_minimum].parent >=0 )
366        _minimum=_data[_minimum].parent;
367      int s=_minimum;
368      int m=_minimum;
[681]369      do {
[683]370        if ( _comp(_data[s].prio, _data[_minimum].prio) ) _minimum=s;
371        s=_data[s].right_neighbor;
[681]372      } while ( s != m );
373    }
374
[711]375    void makeRoot(int c) {
[681]376      int s=c;
377      do {
[683]378        _data[s].parent=-1;
379        s=_data[s].right_neighbor;
[681]380      } while ( s != c );
381    }
382
383    void cut(int a, int b) {
384      /*
385       *Replacing a from the children of b.
386       */
[683]387      --_data[b].degree;
[681]388
[683]389      if ( _data[b].degree !=0 ) {
390        int child=_data[b].child;
[681]391        if ( child==a )
[683]392          _data[b].child=_data[child].right_neighbor;
[681]393        unlace(a);
394      }
395
396
397      /*Lacing a to the roots.*/
[683]398      int right=_data[_minimum].right_neighbor;
399      _data[_minimum].right_neighbor=a;
400      _data[a].left_neighbor=_minimum;
401      _data[a].right_neighbor=right;
402      _data[right].left_neighbor=a;
[681]403
[683]404      _data[a].parent=-1;
405      _data[a].marked=false;
[681]406    }
407
408    void cascade(int a) {
[683]409      if ( _data[a].parent!=-1 ) {
410        int p=_data[a].parent;
[681]411
[683]412        if ( _data[a].marked==false ) _data[a].marked=true;
[681]413        else {
414          cut(a,p);
415          cascade(p);
416        }
417      }
418    }
419
420    void fuse(int a, int b) {
421      unlace(b);
422
423      /*Lacing b under a.*/
[683]424      _data[b].parent=a;
[681]425
[683]426      if (_data[a].degree==0) {
427        _data[b].left_neighbor=b;
428        _data[b].right_neighbor=b;
429        _data[a].child=b;
[681]430      } else {
[683]431        int child=_data[a].child;
432        int last_child=_data[child].left_neighbor;
433        _data[child].left_neighbor=b;
434        _data[b].right_neighbor=child;
435        _data[last_child].right_neighbor=b;
436        _data[b].left_neighbor=last_child;
[681]437      }
438
[683]439      ++_data[a].degree;
[681]440
[683]441      _data[b].marked=false;
[681]442    }
443
444    /*
445     *It is invoked only if a has siblings.
446     */
447    void unlace(int a) {
[683]448      int leftn=_data[a].left_neighbor;
449      int rightn=_data[a].right_neighbor;
450      _data[leftn].right_neighbor=rightn;
451      _data[rightn].left_neighbor=leftn;
[681]452    }
453
454
[683]455    class Store {
[681]456      friend class FibHeap;
457
458      Item name;
459      int parent;
460      int left_neighbor;
461      int right_neighbor;
462      int child;
463      int degree;
464      bool marked;
465      bool in;
466      Prio prio;
467
[683]468      Store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
[681]469    };
470  };
471
472} //namespace lemon
473
474#endif //LEMON_FIB_HEAP_H
475
Note: See TracBrowser for help on using the repository browser.