lemon/binom_heap.h
author Peter Kovacs <kpeter@inf.elte.hu>
Thu, 12 Nov 2009 23:30:45 +0100
changeset 809 22bb98ca0101
parent 703 bb3392fe91f2
permissions -rw-r--r--
Entirely rework CostScaling (#180)

- Use the new interface similarly to NetworkSimplex.
- Rework the implementation using an efficient internal structure
for handling the residual network. This improvement made the
code much faster.
- Handle GEQ supply type (LEQ is not supported).
- Handle infinite upper bounds.
- Handle negative costs (for arcs of finite upper bound).
- Traits class + named parameter for the LargeCost type used in
internal computations.
- Extend the documentation.
     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_BINOM_HEAP_H
    20 #define LEMON_BINOM_HEAP_H
    21 
    22 ///\file
    23 ///\ingroup heaps
    24 ///\brief Binomial Heap implementation.
    25 
    26 #include <vector>
    27 #include <utility>
    28 #include <functional>
    29 #include <lemon/math.h>
    30 #include <lemon/counter.h>
    31 
    32 namespace lemon {
    33 
    34   /// \ingroup heaps
    35   ///
    36   ///\brief Binomial heap data structure.
    37   ///
    38   /// This class implements the \e binomial \e heap data structure.
    39   /// It fully conforms to the \ref concepts::Heap "heap concept".
    40   ///
    41   /// The methods \ref increase() and \ref erase() are not efficient
    42   /// in a binomial heap. In case of many calls of these operations,
    43   /// it is better to use other heap structure, e.g. \ref BinHeap
    44   /// "binary heap".
    45   ///
    46   /// \tparam PR Type of the priorities of the items.
    47   /// \tparam IM A read-writable item map with \c int values, used
    48   /// internally to handle the cross references.
    49   /// \tparam CMP A functor class for comparing the priorities.
    50   /// The default is \c std::less<PR>.
    51 #ifdef DOXYGEN
    52   template <typename PR, typename IM, typename CMP>
    53 #else
    54   template <typename PR, typename IM, typename CMP = std::less<PR> >
    55 #endif
    56   class BinomHeap {
    57   public:
    58     /// Type of the item-int map.
    59     typedef IM ItemIntMap;
    60     /// Type of the priorities.
    61     typedef PR Prio;
    62     /// Type of the items stored in the heap.
    63     typedef typename ItemIntMap::Key Item;
    64     /// Functor type for comparing the priorities.
    65     typedef CMP Compare;
    66 
    67     /// \brief Type to represent the states of the items.
    68     ///
    69     /// Each item has a state associated to it. It can be "in heap",
    70     /// "pre-heap" or "post-heap". The latter two are indifferent from the
    71     /// heap's point of view, but may be useful to the user.
    72     ///
    73     /// The item-int map must be initialized in such way that it assigns
    74     /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
    75     enum State {
    76       IN_HEAP = 0,    ///< = 0.
    77       PRE_HEAP = -1,  ///< = -1.
    78       POST_HEAP = -2  ///< = -2.
    79     };
    80 
    81   private:
    82     class Store;
    83 
    84     std::vector<Store> _data;
    85     int _min, _head;
    86     ItemIntMap &_iim;
    87     Compare _comp;
    88     int _num_items;
    89 
    90   public:
    91     /// \brief Constructor.
    92     ///
    93     /// Constructor.
    94     /// \param map A map that assigns \c int values to the items.
    95     /// It is used internally to handle the cross references.
    96     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
    97     explicit BinomHeap(ItemIntMap &map)
    98       : _min(0), _head(-1), _iim(map), _num_items(0) {}
    99 
   100     /// \brief Constructor.
   101     ///
   102     /// Constructor.
   103     /// \param map A map that assigns \c int values to the items.
   104     /// It is used internally to handle the cross references.
   105     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
   106     /// \param comp The function object used for comparing the priorities.
   107     BinomHeap(ItemIntMap &map, const Compare &comp)
   108       : _min(0), _head(-1), _iim(map), _comp(comp), _num_items(0) {}
   109 
   110     /// \brief The number of items stored in the heap.
   111     ///
   112     /// This function returns the number of items stored in the heap.
   113     int size() const { return _num_items; }
   114 
   115     /// \brief Check if the heap is empty.
   116     ///
   117     /// This function returns \c true if the heap is empty.
   118     bool empty() const { return _num_items==0; }
   119 
   120     /// \brief Make the heap empty.
   121     ///
   122     /// This functon makes the heap empty.
   123     /// It does not change the cross reference map. If you want to reuse
   124     /// a heap that is not surely empty, you should first clear it and
   125     /// then you should set the cross reference map to \c PRE_HEAP
   126     /// for each item.
   127     void clear() {
   128       _data.clear(); _min=0; _num_items=0; _head=-1;
   129     }
   130 
   131     /// \brief Set the priority of an item or insert it, if it is
   132     /// not stored in the heap.
   133     ///
   134     /// This method sets the priority of the given item if it is
   135     /// already stored in the heap. Otherwise it inserts the given
   136     /// item into the heap with the given priority.
   137     /// \param item The item.
   138     /// \param value The priority.
   139     void set (const Item& item, const Prio& value) {
   140       int i=_iim[item];
   141       if ( i >= 0 && _data[i].in ) {
   142         if ( _comp(value, _data[i].prio) ) decrease(item, value);
   143         if ( _comp(_data[i].prio, value) ) increase(item, value);
   144       } else push(item, value);
   145     }
   146 
   147     /// \brief Insert an item into the heap with the given priority.
   148     ///
   149     /// This function inserts the given item into the heap with the
   150     /// given priority.
   151     /// \param item The item to insert.
   152     /// \param value The priority of the item.
   153     /// \pre \e item must not be stored in the heap.
   154     void push (const Item& item, const Prio& value) {
   155       int i=_iim[item];
   156       if ( i<0 ) {
   157         int s=_data.size();
   158         _iim.set( item,s );
   159         Store st;
   160         st.name=item;
   161         st.prio=value;
   162         _data.push_back(st);
   163         i=s;
   164       }
   165       else {
   166         _data[i].parent=_data[i].right_neighbor=_data[i].child=-1;
   167         _data[i].degree=0;
   168         _data[i].in=true;
   169         _data[i].prio=value;
   170       }
   171 
   172       if( 0==_num_items ) {
   173         _head=i;
   174         _min=i;
   175       } else {
   176         merge(i);
   177         if( _comp(_data[i].prio, _data[_min].prio) ) _min=i;
   178       }
   179       ++_num_items;
   180     }
   181 
   182     /// \brief Return the item having minimum priority.
   183     ///
   184     /// This function returns the item having minimum priority.
   185     /// \pre The heap must be non-empty.
   186     Item top() const { return _data[_min].name; }
   187 
   188     /// \brief The minimum priority.
   189     ///
   190     /// This function returns the minimum priority.
   191     /// \pre The heap must be non-empty.
   192     Prio prio() const { return _data[_min].prio; }
   193 
   194     /// \brief The priority of the given item.
   195     ///
   196     /// This function returns the priority of the given item.
   197     /// \param item The item.
   198     /// \pre \e item must be in the heap.
   199     const Prio& operator[](const Item& item) const {
   200       return _data[_iim[item]].prio;
   201     }
   202 
   203     /// \brief Remove the item having minimum priority.
   204     ///
   205     /// This function removes the item having minimum priority.
   206     /// \pre The heap must be non-empty.
   207     void pop() {
   208       _data[_min].in=false;
   209 
   210       int head_child=-1;
   211       if ( _data[_min].child!=-1 ) {
   212         int child=_data[_min].child;
   213         int neighb;
   214         while( child!=-1 ) {
   215           neighb=_data[child].right_neighbor;
   216           _data[child].parent=-1;
   217           _data[child].right_neighbor=head_child;
   218           head_child=child;
   219           child=neighb;
   220         }
   221       }
   222 
   223       if ( _data[_head].right_neighbor==-1 ) {
   224         // there was only one root
   225         _head=head_child;
   226       }
   227       else {
   228         // there were more roots
   229         if( _head!=_min )  { unlace(_min); }
   230         else { _head=_data[_head].right_neighbor; }
   231         merge(head_child);
   232       }
   233       _min=findMin();
   234       --_num_items;
   235     }
   236 
   237     /// \brief Remove the given item from the heap.
   238     ///
   239     /// This function removes the given item from the heap if it is
   240     /// already stored.
   241     /// \param item The item to delete.
   242     /// \pre \e item must be in the heap.
   243     void erase (const Item& item) {
   244       int i=_iim[item];
   245       if ( i >= 0 && _data[i].in ) {
   246         decrease( item, _data[_min].prio-1 );
   247         pop();
   248       }
   249     }
   250 
   251     /// \brief Decrease the priority of an item to the given value.
   252     ///
   253     /// This function decreases the priority of an item to the given value.
   254     /// \param item The item.
   255     /// \param value The priority.
   256     /// \pre \e item must be stored in the heap with priority at least \e value.
   257     void decrease (Item item, const Prio& value) {
   258       int i=_iim[item];
   259       int p=_data[i].parent;
   260       _data[i].prio=value;
   261       
   262       while( p!=-1 && _comp(value, _data[p].prio) ) {
   263         _data[i].name=_data[p].name;
   264         _data[i].prio=_data[p].prio;
   265         _data[p].name=item;
   266         _data[p].prio=value;
   267         _iim[_data[i].name]=i;
   268         i=p;
   269         p=_data[p].parent;
   270       }
   271       _iim[item]=i;
   272       if ( _comp(value, _data[_min].prio) ) _min=i;
   273     }
   274 
   275     /// \brief Increase the priority of an item to the given value.
   276     ///
   277     /// This function increases the priority of an item to the given value.
   278     /// \param item The item.
   279     /// \param value The priority.
   280     /// \pre \e item must be stored in the heap with priority at most \e value.
   281     void increase (Item item, const Prio& value) {
   282       erase(item);
   283       push(item, value);
   284     }
   285 
   286     /// \brief Return the state of an item.
   287     ///
   288     /// This method returns \c PRE_HEAP if the given item has never
   289     /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
   290     /// and \c POST_HEAP otherwise.
   291     /// In the latter case it is possible that the item will get back
   292     /// to the heap again.
   293     /// \param item The item.
   294     State state(const Item &item) const {
   295       int i=_iim[item];
   296       if( i>=0 ) {
   297         if ( _data[i].in ) i=0;
   298         else i=-2;
   299       }
   300       return State(i);
   301     }
   302 
   303     /// \brief Set the state of an item in the heap.
   304     ///
   305     /// This function sets the state of the given item in the heap.
   306     /// It can be used to manually clear the heap when it is important
   307     /// to achive better time complexity.
   308     /// \param i The item.
   309     /// \param st The state. It should not be \c IN_HEAP.
   310     void state(const Item& i, State st) {
   311       switch (st) {
   312       case POST_HEAP:
   313       case PRE_HEAP:
   314         if (state(i) == IN_HEAP) {
   315           erase(i);
   316         }
   317         _iim[i] = st;
   318         break;
   319       case IN_HEAP:
   320         break;
   321       }
   322     }
   323 
   324   private:
   325     
   326     // Find the minimum of the roots
   327     int findMin() {
   328       if( _head!=-1 ) {
   329         int min_loc=_head, min_val=_data[_head].prio;
   330         for( int x=_data[_head].right_neighbor; x!=-1;
   331              x=_data[x].right_neighbor ) {
   332           if( _comp( _data[x].prio,min_val ) ) {
   333             min_val=_data[x].prio;
   334             min_loc=x;
   335           }
   336         }
   337         return min_loc;
   338       }
   339       else return -1;
   340     }
   341 
   342     // Merge the heap with another heap starting at the given position
   343     void merge(int a) {
   344       if( _head==-1 || a==-1 ) return;
   345       if( _data[a].right_neighbor==-1 &&
   346           _data[a].degree<=_data[_head].degree ) {
   347         _data[a].right_neighbor=_head;
   348         _head=a;
   349       } else {
   350         interleave(a);
   351       }
   352       if( _data[_head].right_neighbor==-1 ) return;
   353       
   354       int x=_head;
   355       int x_prev=-1, x_next=_data[x].right_neighbor;
   356       while( x_next!=-1 ) {
   357         if( _data[x].degree!=_data[x_next].degree ||
   358             ( _data[x_next].right_neighbor!=-1 &&
   359               _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) {
   360           x_prev=x;
   361           x=x_next;
   362         }
   363         else {
   364           if( _comp(_data[x_next].prio,_data[x].prio) ) {
   365             if( x_prev==-1 ) {
   366               _head=x_next;
   367             } else {
   368               _data[x_prev].right_neighbor=x_next;
   369             }
   370             fuse(x,x_next);
   371             x=x_next;
   372           }
   373           else {
   374             _data[x].right_neighbor=_data[x_next].right_neighbor;
   375             fuse(x_next,x);
   376           }
   377         }
   378         x_next=_data[x].right_neighbor;
   379       }
   380     }
   381 
   382     // Interleave the elements of the given list into the list of the roots
   383     void interleave(int a) {
   384       int p=_head, q=a;
   385       int curr=_data.size();
   386       _data.push_back(Store());
   387       
   388       while( p!=-1 || q!=-1 ) {
   389         if( q==-1 || ( p!=-1 && _data[p].degree<_data[q].degree ) ) {
   390           _data[curr].right_neighbor=p;
   391           curr=p;
   392           p=_data[p].right_neighbor;
   393         }
   394         else {
   395           _data[curr].right_neighbor=q;
   396           curr=q;
   397           q=_data[q].right_neighbor;
   398         }
   399       }
   400       
   401       _head=_data.back().right_neighbor;
   402       _data.pop_back();
   403     }
   404 
   405     // Lace node a under node b
   406     void fuse(int a, int b) {
   407       _data[a].parent=b;
   408       _data[a].right_neighbor=_data[b].child;
   409       _data[b].child=a;
   410 
   411       ++_data[b].degree;
   412     }
   413 
   414     // Unlace node a (if it has siblings)
   415     void unlace(int a) {
   416       int neighb=_data[a].right_neighbor;
   417       int other=_head;
   418 
   419       while( _data[other].right_neighbor!=a )
   420         other=_data[other].right_neighbor;
   421       _data[other].right_neighbor=neighb;
   422     }
   423 
   424   private:
   425 
   426     class Store {
   427       friend class BinomHeap;
   428 
   429       Item name;
   430       int parent;
   431       int right_neighbor;
   432       int child;
   433       int degree;
   434       bool in;
   435       Prio prio;
   436 
   437       Store() : parent(-1), right_neighbor(-1), child(-1), degree(0),
   438         in(true) {}
   439     };
   440   };
   441 
   442 } //namespace lemon
   443 
   444 #endif //LEMON_BINOM_HEAP_H
   445