COIN-OR::LEMON - Graph Library

Changeset 387:4406c93c862b in lemon-0.x for src


Ignore:
Timestamp:
04/23/04 21:41:01 (16 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@517
Message:

Documentation added.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/include/fib_heap.h

    r373 r387  
    1616
    1717  /**
    18      This class implements the \e Fibonacci \e heap data structure. A \e
    19      heap is a data structure for storing items with specified priorities,
    20      such that finding the item with minimum priority is efficient. In a
    21      heap one can change the priority of an item, and to add or erase an
    22      item.
    23 
    24      The methods \ref increase and \ref erase are not efficient, in
    25      case of many calls to these operations, it is better to use
    26      a binary heap.
     18     This class implements the \e Fibonacci \e heap data structure. A \e heap
     19     is a data structure for storing items with specified values called \e
     20     priorities, such that finding the item with minimum priority with respect
     21     to \e Compare is efficient. In a heap one can change the priority of an
     22     item, add or erase an item, etc.
     23
     24     The methods \ref increase and \ref erase are not efficient in a Fibonacci
     25     heap. In case of many calls to these operations, it is better to use a
     26     \e binary \e heap.
    2727     
    28      /param Item The type of the items to be stored. 
    29      /param Prio The type of the priority of the items.
    30      /param ItemIntMap A read and writable Item int map, for the usage of
     28     \param Item The type of the items to be stored. 
     29     \param Prio The type of the priority of the items.
     30     \param ItemIntMap A read and writable Item int map, for the usage of
    3131     the heap.
    32      /param Compare A class for the comparison of the priorities. The
     32     \param Compare A class for the comparison of the priorities. The
    3333     default is \c std::less<Prio>.
    3434
     
    4747#endif
    4848  class FibHeap {
    49   public:
     49  public:    
    5050    typedef Prio PrioType;
    5151   
     
    6868    };
    6969   
    70   public :
    71    
    7270    FibHeap(ItemIntMap &_iimap) : minimum(0), iimap(_iimap), num_items() {}
    7371    FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0),
     
    7775
    7876    /**
    79     Returns the number of items stored in the heap.
     77       Returns the number of items stored in the heap.
    8078    */
    8179    int size() const { return num_items; }
     
    8482   
    8583    /**
    86        Returns true iff the heap stores no items.
     84       Returns \c true iff the heap stores no items.
    8785    */
    8886    bool empty() const { return num_items==0; }
    8987
    90     ///Item \c item gets to the heap with priority \c value independently if \c item was already there.
    91 
    92     /**
    93        This method calls \ref push(item, value) if \c item is not
    94        stored in the heap, and it calls \ref decrease(it, \c value) or
    95        \ref increase(it, \c value) otherwise.
    96     */
    97     void set (Item const item, PrioType const value); //vigyazat: az implementacioban it van
     88    ///\c item gets to the heap with priority \c value independently if \c item was already there.
     89
     90    /**
     91       This method calls \ref push(\c item, \c value) if \c item is not
     92       stored in the heap and it calls \ref decrease(\c item, \c value) or
     93       \ref increase(\c item, \c value) otherwise.
     94    */
     95    void set (Item const item, PrioType const value);
    9896   
    9997    ///Adds \c item to the heap with priority \c value.
     
    103101       \pre \c item must not be stored in the heap.
    104102    */
    105     void push (Item const it, PrioType const value); /*vigyazat: az implementacioban it van*/
     103    void push (Item const item, PrioType const value);
    106104   
    107105   
     
    130128       \pre \c item must be in the heap.
    131129    */
    132     PrioType& operator[](const Item& it) { return container[iimap[it]].prio; }
     130    PrioType& operator[](const Item& item) {
     131      return container[iimap[item]].prio;
     132    }
    133133   
    134134    ///Returns the priority of \c item.
     
    138138       \pre \c item must be in the heap.
    139139    */
    140     const PrioType& operator[](const Item& it) const {
    141       return container[iimap[it]].prio;
     140    const PrioType& operator[](const Item& item) const {
     141      return container[iimap[item]].prio;
    142142    }
    143143
     
    158158       stored in the heap. It is quite inefficient in Fibonacci heaps.
    159159    */
    160     void erase (const Item& item); /*vigyazat: az implementacioban it van*/
     160    void erase (const Item& item);
    161161
    162162    ///Decreases the priority of \c item to \c value.
     
    167167       value w.r.t.  Compare.
    168168    */
    169     void decrease (Item item, PrioType const value); /*vigyazat: az implementacioban it van*/
     169    void decrease (Item item, PrioType const value);
    170170
    171171
     
    175175       This method sets the priority of \c item to \c value. Though
    176176       there is no precondition on the priority of \c item, this
    177        method should be used only if one wants to \e increase
     177       method should be used only if there is a need to really \e increase
    178178       (w.r.t.  Compare) the priority of \c item, because this
    179179       method is inefficient.
    180180    */
    181     void increase (Item it, PrioType const value) {
    182       erase(it);
    183       push(it, value);
    184     }
    185 
    186 
    187     ///Tells if \c item is in, was in, or has not been in the heap.
     181    void increase (Item item, PrioType const value) {
     182      erase(item);
     183      push(item, value);
     184    }
     185
     186
     187    ///Tells if \c item is in, was already in, or has never been in the heap.
    188188
    189189    /**
     
    193193       get back to the heap again.
    194194    */
    195     state_enum state(const Item &it);  /*vigyazat: az implementacioban it van*/
    196 
     195    state_enum state(const Item &item) const {
     196      int i=iimap[item];
     197      if( i>=0 ) {
     198        if ( container[i].in ) i=0;
     199        else i=-2;
     200      }
     201      return state_enum(i);
     202    }   
     203   
     204  private:
     205   
     206    void balance();
     207    void makeroot(int c);
     208    void cut(int a, int b);
     209    void cascade(int a);
     210    void fuse(int a, int b);
     211    void unlace(int a);
     212
     213
     214    class store {
     215      friend class FibHeap;
     216     
     217      Item name;
     218      int parent;
     219      int left_neighbor;
     220      int right_neighbor;
     221      int child;
     222      int degree; 
     223      bool marked;
     224      bool in;
     225      PrioType prio;
     226     
     227      store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
     228    };
     229  };   
     230 
    197231
    198232
     
    201235    // **********************************************************************
    202236   
    203 
    204     void set (Item const it, PrioType const value) {
    205       int i=iimap[it];
    206       if ( i >= 0 && container[i].in ) {
    207         if ( comp(value, container[i].prio) ) decrease(it, value);
    208         if ( comp(container[i].prio, value) ) increase(it, value);
    209       } else push(it, value);
    210     }
    211    
    212 
    213     void push (Item const it, PrioType const value) {
    214       int i=iimap[it];     
     237  template <typename Item, typename Prio, typename ItemIntMap,
     238    typename Compare>
     239  void FibHeap<Item, Prio, ItemIntMap, Compare>::set
     240  (Item const item, PrioType const value)
     241  {
     242    int i=iimap[item];
     243    if ( i >= 0 && container[i].in ) {
     244      if ( comp(value, container[i].prio) ) decrease(item, value);
     245      if ( comp(container[i].prio, value) ) increase(item, value);
     246    } else push(item, value);
     247  }
     248   
     249  template <typename Item, typename Prio, typename ItemIntMap,
     250    typename Compare>
     251  void FibHeap<Item, Prio, ItemIntMap, Compare>::push
     252  (Item const item, PrioType const value) {
     253      int i=iimap[item];     
    215254      if ( i < 0 ) {
    216255        int s=container.size();
    217         iimap.set( it, s );     
     256        iimap.set( item, s );   
    218257        store st;
    219         st.name=it;
     258        st.name=item;
    220259        container.push_back(st);
    221260        i=s;
     
    241280    }
    242281   
    243 
    244     void pop() {
     282  template <typename Item, typename Prio, typename ItemIntMap,
     283    typename Compare>
     284  void FibHeap<Item, Prio, ItemIntMap, Compare>::pop() {
    245285      /*The first case is that there are only one root.*/
    246286      if ( container[minimum].left_neighbor==minimum ) {
     
    273313    }
    274314
    275    
    276     void erase (const Item& it) {
    277       int i=iimap[it];
     315
     316  template <typename Item, typename Prio, typename ItemIntMap,
     317    typename Compare>
     318  void FibHeap<Item, Prio, ItemIntMap, Compare>::erase
     319  (const Item& item) {
     320      int i=iimap[item];
    278321     
    279322      if ( i >= 0 && container[i].in ) {       
     
    286329        pop();
    287330      }
    288     }
    289    
    290 
    291     void decrease (Item it, PrioType const value) {
    292       int i=iimap[it];
     331  }
     332   
     333  template <typename Item, typename Prio, typename ItemIntMap,
     334    typename Compare>
     335  void FibHeap<Item, Prio, ItemIntMap, Compare>::decrease
     336  (Item item, PrioType const value) {
     337      int i=iimap[item];
    293338      container[i].prio=value;
    294339      int p=container[i].parent;
     
    299344      }     
    300345      if ( comp(value, container[minimum].prio) ) minimum=i;
    301     }
    302    
    303 
    304     state_enum state(const Item &it) const {
    305       int i=iimap[it];
    306       if( i>=0 ) {
    307         if ( container[i].in ) i=0;
    308         else i=-2;
    309       }
    310       return state_enum(i);
    311     }
    312 
    313 
    314   private:
    315    
    316     void balance() {     
     346  }
     347 
     348
     349  template <typename Item, typename Prio, typename ItemIntMap,
     350    typename Compare>
     351  void FibHeap<Item, Prio, ItemIntMap, Compare>::balance() {     
    317352
    318353    int maxdeg=int( floor( 2.08*log(double(container.size()))))+1;
     
    357392    }
    358393
    359 
    360     void makeroot (int c) {
     394  template <typename Item, typename Prio, typename ItemIntMap,
     395    typename Compare>
     396  void FibHeap<Item, Prio, ItemIntMap, Compare>::makeroot
     397  (int c) {
    361398      int s=c;
    362399      do { 
     
    365402      } while ( s != c );
    366403    }
    367    
    368 
    369     void cut (int a, int b) {   
    370       /*
    371        *Replacing a from the children of b.
    372        */
    373       --container[b].degree;
    374      
    375       if ( container[b].degree !=0 ) {
    376         int child=container[b].child;
    377         if ( child==a )
    378           container[b].child=container[child].right_neighbor;
    379         unlace(a);
    380       }
    381      
    382      
    383       /*Lacing a to the roots.*/
    384       int right=container[minimum].right_neighbor;
    385       container[minimum].right_neighbor=a;
    386       container[a].left_neighbor=minimum;
    387       container[a].right_neighbor=right;
    388       container[right].left_neighbor=a;
    389 
    390       container[a].parent=-1;
    391       container[a].marked=false;
    392     }
    393 
    394 
    395     void cascade (int a)
     404 
     405 
     406  template <typename Item, typename Prio, typename ItemIntMap,
     407    typename Compare>
     408  void FibHeap<Item, Prio, ItemIntMap, Compare>::cut
     409  (int a, int b) {   
     410    /*
     411     *Replacing a from the children of b.
     412     */
     413    --container[b].degree;
     414   
     415    if ( container[b].degree !=0 ) {
     416      int child=container[b].child;
     417      if ( child==a )
     418        container[b].child=container[child].right_neighbor;
     419      unlace(a);
     420    }
     421   
     422   
     423    /*Lacing a to the roots.*/
     424    int right=container[minimum].right_neighbor;
     425    container[minimum].right_neighbor=a;
     426    container[a].left_neighbor=minimum;
     427    container[a].right_neighbor=right;
     428    container[right].left_neighbor=a;
     429   
     430    container[a].parent=-1;
     431    container[a].marked=false;
     432  }
     433 
     434
     435  template <typename Item, typename Prio, typename ItemIntMap,
     436    typename Compare>
     437  void FibHeap<Item, Prio, ItemIntMap, Compare>::cascade
     438  (int a)
    396439    {
    397440      if ( container[a].parent!=-1 ) {
     
    407450
    408451
    409     void fuse (int a, int b) {
     452  template <typename Item, typename Prio, typename ItemIntMap,
     453    typename Compare>
     454  void FibHeap<Item, Prio, ItemIntMap, Compare>::fuse
     455  (int a, int b) {
    410456      unlace(b);
    411457     
     
    431477    }
    432478
    433 
    434     /*
    435      *It is invoked only if a has siblings.
    436      */
    437     void unlace (int a) {     
     479 
     480  /*
     481   *It is invoked only if a has siblings.
     482   */
     483  template <typename Item, typename Prio, typename ItemIntMap,
     484    typename Compare>
     485  void FibHeap<Item, Prio, ItemIntMap, Compare>::unlace
     486  (int a) {     
    438487      int leftn=container[a].left_neighbor;
    439488      int rightn=container[a].right_neighbor;
    440489      container[leftn].right_neighbor=rightn;
    441490      container[rightn].left_neighbor=leftn;
    442     }
    443 
    444 
    445     class store {
    446       friend class FibHeap;
    447      
    448       Item name;
    449       int parent;
    450       int left_neighbor;
    451       int right_neighbor;
    452       int child;
    453       int degree; 
    454       bool marked;
    455       bool in;
    456       PrioType prio;
    457 
    458       store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
    459     };
    460    
    461   };
     491  }
    462492 
    463493} //namespace hugo
Note: See TracChangeset for help on using the changeset viewer.