COIN-OR::LEMON - Graph Library

Changeset 2547:f393a8162688 in lemon-0.x for lemon/fib_heap.h


Ignore:
Timestamp:
12/27/07 14:40:16 (12 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3424
Message:

Renaming state_enum to State
Removing "Type" suffix from typedefs
Moving implementation into the class definition

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/fib_heap.h

    r2529 r2547  
    4242  ///The methods \ref increase and \ref erase are not efficient in a Fibonacci
    4343  ///heap. In case of many calls to these operations, it is better to use a
    44   ///\e binary \e heap.
     44  ///\ref BinHeap "binary heap".
    4545  ///
    46   ///\param Prio Type of the priority of the items.
    47   ///\param ItemIntMap A read and writable Item int map, used internally
     46  ///\param _Prio Type of the priority of the items.
     47  ///\param _ItemIntMap A read and writable Item int map, used internally
    4848  ///to handle the cross references.
    49   ///\param Compare A class for the ordering of the priorities. The
    50   ///default is \c std::less<Prio>.
     49  ///\param _Compare A class for the ordering of the priorities. The
     50  ///default is \c std::less<_Prio>.
    5151  ///
    5252  ///\sa BinHeap
     
    5555 
    5656#ifdef DOXYGEN
    57   template <typename Prio,
    58             typename ItemIntMap,
    59             typename Compare>
     57  template <typename _Prio,
     58            typename _ItemIntMap,
     59            typename _Compare>
    6060#else
    61   template <typename Prio,
    62             typename ItemIntMap,
    63             typename Compare = std::less<Prio> >
     61  template <typename _Prio,
     62            typename _ItemIntMap,
     63            typename _Compare = std::less<_Prio> >
    6464#endif
    6565  class FibHeap {
    6666  public:
     67    typedef _ItemIntMap ItemIntMap;
     68    typedef _Prio Prio;
    6769    typedef typename ItemIntMap::Key Item;
    68     typedef Prio PrioType;
     70    typedef std::pair<Item,Prio> Pair;
     71    typedef _Compare Compare;
    6972   
    7073  private:
     
    7982  public:
    8083    ///Status of the nodes
    81     enum state_enum {
     84    enum State {
    8285      ///The node is in the heap
    8386      IN_HEAP = 0,
     
    100103    /// internally to handle the cross references. \c _comp is an
    101104    /// object for ordering of the priorities.
    102     FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0),
    103                   iimap(_iimap), comp(_comp), num_items() {}
     105    FibHeap(ItemIntMap &_iimap, const Compare &_comp)
     106      : minimum(0), iimap(_iimap), comp(_comp), num_items() {}
    104107   
    105108    /// \brief The number of items stored in the heap.
     
    129132    /// stored in the heap and it calls \ref decrease(\c item, \c value) or
    130133    /// \ref increase(\c item, \c value) otherwise.
    131     void set (Item const item, PrioType const value);
     134    void set (const Item& item, const Prio& value) {
     135      int i=iimap[item];
     136      if ( i >= 0 && container[i].in ) {
     137        if ( comp(value, container[i].prio) ) decrease(item, value);
     138        if ( comp(container[i].prio, value) ) increase(item, value);
     139      } else push(item, value);
     140    }
    132141   
    133142    /// \brief Adds \c item to the heap with priority \c value.
     
    135144    /// Adds \c item to the heap with priority \c value.
    136145    /// \pre \c item must not be stored in the heap.
    137     void push (Item const item, PrioType const value);
    138    
    139     /// \brief Returns the item with minimum priority relative to \c Compare.
    140     ///
    141     /// This method returns the item with minimum priority relative to \c
    142     /// Compare. 
    143     /// \pre The heap must be nonempty. 
    144     Item top() const { return container[minimum].name; }
    145 
    146     /// \brief Returns the minimum priority relative to \c Compare.
    147     ///
    148     /// It returns the minimum priority relative to \c Compare.
    149     /// \pre The heap must be nonempty.
    150     PrioType prio() const { return container[minimum].prio; }
    151    
    152     /// \brief Returns the priority of \c item.
    153     ///
    154     /// This function returns the priority of \c item.
    155     /// \pre \c item must be in the heap.
    156     PrioType& operator[](const Item& item) {
    157       return container[iimap[item]].prio;
    158     }
    159    
    160     /// \brief Returns the priority of \c item.
    161     ///
    162     /// It returns the priority of \c item.
    163     /// \pre \c item must be in the heap.
    164     const PrioType& operator[](const Item& item) const {
    165       return container[iimap[item]].prio;
    166     }
    167 
    168 
    169     /// \brief Deletes the item with minimum priority relative to \c Compare.
    170     ///
    171     /// This method deletes the item with minimum priority relative to \c
    172     /// Compare from the heap. 
    173     /// \pre The heap must be non-empty. 
    174     void pop();
    175 
    176     /// \brief Deletes \c item from the heap.
    177     ///
    178     /// This method deletes \c item from the heap, if \c item was already
    179     /// stored in the heap. It is quite inefficient in Fibonacci heaps.
    180     void erase (const Item& item);
    181 
    182     /// \brief Decreases the priority of \c item to \c value.
    183     ///
    184     /// This method decreases the priority of \c item to \c value.
    185     /// \pre \c item must be stored in the heap with priority at least \c
    186     ///   value relative to \c Compare.
    187     void decrease (Item item, PrioType const value);
    188 
    189     /// \brief Increases the priority of \c item to \c value.
    190     ///
    191     /// This method sets the priority of \c item to \c value. Though
    192     /// there is no precondition on the priority of \c item, this
    193     /// method should be used only if it is indeed necessary to increase
    194     /// (relative to \c Compare) the priority of \c item, because this
    195     /// method is inefficient.
    196     void increase (Item item, PrioType const value) {
    197       erase(item);
    198       push(item, value);
    199     }
    200 
    201 
    202     /// \brief Returns if \c item is in, has already been in, or has never
    203     /// been in the heap.
    204     ///
    205     /// This method returns PRE_HEAP if \c item has never been in the
    206     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
    207     /// otherwise. In the latter case it is possible that \c item will
    208     /// get back to the heap again.
    209     state_enum state(const Item &item) const {
    210       int i=iimap[item];
    211       if( i>=0 ) {
    212         if ( container[i].in ) i=0;
    213         else i=-2;
    214       }
    215       return state_enum(i);
    216     }   
    217 
    218     /// \brief Sets the state of the \c item in the heap.
    219     ///
    220     /// Sets the state of the \c item in the heap. It can be used to
    221     /// manually clear the heap when it is important to achive the
    222     /// better time complexity.
    223     /// \param i The item.
    224     /// \param st The state. It should not be \c IN_HEAP.
    225     void state(const Item& i, state_enum st) {
    226       switch (st) {
    227       case POST_HEAP:
    228       case PRE_HEAP:
    229         if (state(i) == IN_HEAP) {
    230           erase(i);
    231         }
    232         iimap[i] = st;
    233         break;
    234       case IN_HEAP:
    235         break;
    236       }
    237     }
    238    
    239   private:
    240    
    241     void balance();
    242     void makeroot(int c);
    243     void cut(int a, int b);
    244     void cascade(int a);
    245     void fuse(int a, int b);
    246     void unlace(int a);
    247 
    248 
    249     class store {
    250       friend class FibHeap;
    251      
    252       Item name;
    253       int parent;
    254       int left_neighbor;
    255       int right_neighbor;
    256       int child;
    257       int degree; 
    258       bool marked;
    259       bool in;
    260       PrioType prio;
    261      
    262       store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
    263     };
    264   };   
    265  
    266 
    267 
    268     // **********************************************************************
    269     //  IMPLEMENTATIONS
    270     // **********************************************************************
    271    
    272   template <typename Prio, typename ItemIntMap,
    273     typename Compare>
    274   void FibHeap<Prio, ItemIntMap, Compare>::set
    275   (Item const item, PrioType const value)
    276   {
    277     int i=iimap[item];
    278     if ( i >= 0 && container[i].in ) {
    279       if ( comp(value, container[i].prio) ) decrease(item, value);
    280       if ( comp(container[i].prio, value) ) increase(item, value);
    281     } else push(item, value);
    282   }
    283    
    284   template <typename Prio, typename ItemIntMap,
    285     typename Compare>
    286   void FibHeap<Prio, ItemIntMap, Compare>::push
    287   (Item const item, PrioType const value) {
     146    void push (const Item& item, const Prio& value) {
    288147      int i=iimap[item];     
    289148      if ( i < 0 ) {
     
    315174    }
    316175   
    317   template <typename Prio, typename ItemIntMap,
    318     typename Compare>
    319   void FibHeap<Prio, ItemIntMap, Compare>::pop() {
     176    /// \brief Returns the item with minimum priority relative to \c Compare.
     177    ///
     178    /// This method returns the item with minimum priority relative to \c
     179    /// Compare. 
     180    /// \pre The heap must be nonempty. 
     181    Item top() const { return container[minimum].name; }
     182
     183    /// \brief Returns the minimum priority relative to \c Compare.
     184    ///
     185    /// It returns the minimum priority relative to \c Compare.
     186    /// \pre The heap must be nonempty.
     187    const Prio& prio() const { return container[minimum].prio; }
     188       
     189    /// \brief Returns the priority of \c item.
     190    ///
     191    /// It returns the priority of \c item.
     192    /// \pre \c item must be in the heap.
     193    const Prio& operator[](const Item& item) const {
     194      return container[iimap[item]].prio;
     195    }
     196
     197    /// \brief Deletes the item with minimum priority relative to \c Compare.
     198    ///
     199    /// This method deletes the item with minimum priority relative to \c
     200    /// Compare from the heap. 
     201    /// \pre The heap must be non-empty. 
     202    void pop() {
    320203      /*The first case is that there are only one root.*/
    321204      if ( container[minimum].left_neighbor==minimum ) {
     
    334217          int child=container[minimum].child;
    335218          int last_child=container[child].left_neighbor;
    336        
     219         
    337220          makeroot(child);
    338221         
     
    348231    }
    349232
    350 
    351   template <typename Prio, typename ItemIntMap,
    352     typename Compare>
    353   void FibHeap<Prio, ItemIntMap, Compare>::erase
    354   (const Item& item) {
     233    /// \brief Deletes \c item from the heap.
     234    ///
     235    /// This method deletes \c item from the heap, if \c item was already
     236    /// stored in the heap. It is quite inefficient in Fibonacci heaps.
     237    void erase (const Item& item) {
    355238      int i=iimap[item];
    356239     
     
    364247        pop();
    365248      }
    366   }
    367    
    368   template <typename Prio, typename ItemIntMap,
    369     typename Compare>
    370   void FibHeap<Prio, ItemIntMap, Compare>::decrease
    371   (Item item, PrioType const value) {
     249    }
     250
     251    /// \brief Decreases the priority of \c item to \c value.
     252    ///
     253    /// This method decreases the priority of \c item to \c value.
     254    /// \pre \c item must be stored in the heap with priority at least \c
     255    ///   value relative to \c Compare.
     256    void decrease (Item item, const Prio& value) {
    372257      int i=iimap[item];
    373258      container[i].prio=value;
     
    379264      }     
    380265      if ( comp(value, container[minimum].prio) ) minimum=i;
    381   }
    382  
    383 
    384   template <typename Prio, typename ItemIntMap,
    385     typename Compare>
    386   void FibHeap<Prio, ItemIntMap, Compare>::balance() {     
    387 
    388     int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1;
     266    }
     267
     268    /// \brief Increases the priority of \c item to \c value.
     269    ///
     270    /// This method sets the priority of \c item to \c value. Though
     271    /// there is no precondition on the priority of \c item, this
     272    /// method should be used only if it is indeed necessary to increase
     273    /// (relative to \c Compare) the priority of \c item, because this
     274    /// method is inefficient.
     275    void increase (Item item, const Prio& value) {
     276      erase(item);
     277      push(item, value);
     278    }
     279
     280
     281    /// \brief Returns if \c item is in, has already been in, or has never
     282    /// been in the heap.
     283    ///
     284    /// This method returns PRE_HEAP if \c item has never been in the
     285    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
     286    /// otherwise. In the latter case it is possible that \c item will
     287    /// get back to the heap again.
     288    State state(const Item &item) const {
     289      int i=iimap[item];
     290      if( i>=0 ) {
     291        if ( container[i].in ) i=0;
     292        else i=-2;
     293      }
     294      return State(i);
     295    }   
     296
     297    /// \brief Sets the state of the \c item in the heap.
     298    ///
     299    /// Sets the state of the \c item in the heap. It can be used to
     300    /// manually clear the heap when it is important to achive the
     301    /// better time complexity.
     302    /// \param i The item.
     303    /// \param st The state. It should not be \c IN_HEAP.
     304    void state(const Item& i, State st) {
     305      switch (st) {
     306      case POST_HEAP:
     307      case PRE_HEAP:
     308        if (state(i) == IN_HEAP) {
     309          erase(i);
     310        }
     311        iimap[i] = st;
     312        break;
     313      case IN_HEAP:
     314        break;
     315      }
     316    }
     317   
     318  private:
     319   
     320    void balance() {
     321
     322      int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1;
    389323 
    390     std::vector<int> A(maxdeg,-1);
    391    
    392     /*
    393      *Recall that now minimum does not point to the minimum prio element.
    394      *We set minimum to this during balance().
    395      */
    396     int anchor=container[minimum].left_neighbor;
    397     int next=minimum;
    398     bool end=false;
     324      std::vector<int> A(maxdeg,-1);
     325   
     326      /*
     327       *Recall that now minimum does not point to the minimum prio element.
     328       *We set minimum to this during balance().
     329       */
     330      int anchor=container[minimum].left_neighbor;
     331      int next=minimum;
     332      bool end=false;
    399333       
    400        do {
     334      do {
    401335        int active=next;
    402336        if ( anchor==active ) end=true;
     
    415349        }       
    416350        A[d]=active;
    417        } while ( !end );
    418 
    419 
    420        while ( container[minimum].parent >=0 ) minimum=container[minimum].parent;
    421        int s=minimum;
    422        int m=minimum;
    423        do { 
    424          if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
    425          s=container[s].right_neighbor;
    426        } while ( s != m );
    427     }
    428 
    429   template <typename Prio, typename ItemIntMap,
    430     typename Compare>
    431   void FibHeap<Prio, ItemIntMap, Compare>::makeroot
    432   (int c) {
     351      } while ( !end );
     352
     353
     354      while ( container[minimum].parent >=0 )
     355        minimum=container[minimum].parent;
     356      int s=minimum;
     357      int m=minimum;
     358      do { 
     359        if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
     360        s=container[s].right_neighbor;
     361      } while ( s != m );
     362    }
     363
     364    void makeroot(int c) {
    433365      int s=c;
    434366      do { 
     
    437369      } while ( s != c );
    438370    }
    439  
    440  
    441   template <typename Prio, typename ItemIntMap,
    442     typename Compare>
    443   void FibHeap<Prio, ItemIntMap, Compare>::cut
    444   (int a, int b) {   
    445     /*
    446      *Replacing a from the children of b.
    447      */
    448     --container[b].degree;
    449    
    450     if ( container[b].degree !=0 ) {
    451       int child=container[b].child;
    452       if ( child==a )
    453         container[b].child=container[child].right_neighbor;
    454       unlace(a);
    455     }
    456    
    457    
    458     /*Lacing a to the roots.*/
    459     int right=container[minimum].right_neighbor;
    460     container[minimum].right_neighbor=a;
    461     container[a].left_neighbor=minimum;
    462     container[a].right_neighbor=right;
    463     container[right].left_neighbor=a;
    464    
    465     container[a].parent=-1;
    466     container[a].marked=false;
    467   }
    468  
    469 
    470   template <typename Prio, typename ItemIntMap,
    471     typename Compare>
    472   void FibHeap<Prio, ItemIntMap, Compare>::cascade
    473   (int a)
    474     {
     371
     372    void cut(int a, int b) {
     373      /*
     374       *Replacing a from the children of b.
     375       */
     376      --container[b].degree;
     377   
     378      if ( container[b].degree !=0 ) {
     379        int child=container[b].child;
     380        if ( child==a )
     381          container[b].child=container[child].right_neighbor;
     382        unlace(a);
     383      }
     384   
     385   
     386      /*Lacing a to the roots.*/
     387      int right=container[minimum].right_neighbor;
     388      container[minimum].right_neighbor=a;
     389      container[a].left_neighbor=minimum;
     390      container[a].right_neighbor=right;
     391      container[right].left_neighbor=a;
     392   
     393      container[a].parent=-1;
     394      container[a].marked=false;
     395    }
     396
     397    void cascade(int a) {
    475398      if ( container[a].parent!=-1 ) {
    476399        int p=container[a].parent;
     
    484407    }
    485408
    486 
    487   template <typename Prio, typename ItemIntMap,
    488     typename Compare>
    489   void FibHeap<Prio, ItemIntMap, Compare>::fuse
    490   (int a, int b) {
     409    void fuse(int a, int b) {
    491410      unlace(b);
    492411     
     
    512431    }
    513432
    514  
    515   /*
    516    *It is invoked only if a has siblings.
    517    */
    518   template <typename Prio, typename ItemIntMap,
    519     typename Compare>
    520   void FibHeap<Prio, ItemIntMap, Compare>::unlace
    521   (int a) {     
     433    /*
     434     *It is invoked only if a has siblings.
     435     */
     436    void unlace(int a) {
    522437      int leftn=container[a].left_neighbor;
    523438      int rightn=container[a].right_neighbor;
    524439      container[leftn].right_neighbor=rightn;
    525440      container[rightn].left_neighbor=leftn;
    526   }
    527  
     441    }
     442
     443
     444    class store {
     445      friend class FibHeap;
     446     
     447      Item name;
     448      int parent;
     449      int left_neighbor;
     450      int right_neighbor;
     451      int child;
     452      int degree; 
     453      bool marked;
     454      bool in;
     455      Prio prio;
     456     
     457      store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
     458    };
     459  };   
    528460
    529461} //namespace lemon
Note: See TracChangeset for help on using the changeset viewer.