COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/fib_heap.h @ 2229:4dbb6dd2dd4b

Last change on this file since 2229:4dbb6dd2dd4b was 2050:d9a221218ea4, checked in by Balazs Dezso, 14 years ago

Changing the mining of the clear in heaps
It does not touch the heap cross ref. It is
sometimes more clean useable and more efficient

File size: 15.2 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
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
23///\ingroup auxdat
24///\brief Fibonacci Heap implementation.
25
26#include <vector>
27#include <functional>
28#include <cmath>
29
30namespace lemon {
31 
32  /// \ingroup auxdat
33
34  /// Fibonacci Heap.
35
36  ///This class implements the \e Fibonacci \e heap data structure. A \e heap
37  ///is a data structure for storing items with specified values called \e
38  ///priorities in such a way that finding the item with minimum priority is
39  ///efficient. \c Compare specifies the ordering of the priorities. In a heap
40  ///one can change the priority of an item, add or erase an item, etc.
41  ///
42  ///The methods \ref increase and \ref erase are not efficient in a Fibonacci
43  ///heap. In case of many calls to these operations, it is better to use a
44  ///\e binary \e heap.
45  ///
46  ///\param Item Type of the items to be stored. 
47  ///\param Prio Type of the priority of the items.
48  ///\param ItemIntMap A read and writable Item int map, used internally
49  ///to handle the cross references.
50  ///\param Compare A class for the ordering of the priorities. The
51  ///default is \c std::less<Prio>.
52  ///
53  ///\sa BinHeap
54  ///\sa Dijkstra
55  ///\author Jacint Szabo
56 
57#ifdef DOXYGEN
58  template <typename Item,
59            typename Prio,
60            typename ItemIntMap,
61            typename Compare>
62#else
63  template <typename Item,
64            typename Prio,
65            typename ItemIntMap,
66            typename Compare = std::less<Prio> >
67#endif
68  class FibHeap {
69  public:     
70    typedef Prio PrioType;
71   
72  private:
73    class store;
74   
75    std::vector<store> container;
76    int minimum;
77    ItemIntMap &iimap;
78    Compare comp;
79    int num_items;
80   
81  public:
82    ///Status of the nodes
83    enum state_enum {
84      ///The node is in the heap
85      IN_HEAP = 0,
86      ///The node has never been in the heap
87      PRE_HEAP = -1,
88      ///The node was in the heap but it got out of it
89      POST_HEAP = -2
90    };
91   
92    /// \brief The constructor
93    ///
94    /// \c _iimap should be given to the constructor, since it is
95    ///   used internally to handle the cross references.
96    explicit FibHeap(ItemIntMap &_iimap)
97      : minimum(0), iimap(_iimap), num_items() {}
98 
99    /// \brief The constructor
100    ///
101    /// \c _iimap should be given to the constructor, since it is used
102    /// internally to handle the cross references. \c _comp is an
103    /// object for ordering of the priorities.
104    FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0),
105                  iimap(_iimap), comp(_comp), num_items() {}
106   
107    /// \brief The number of items stored in the heap.
108    ///
109    /// Returns the number of items stored in the heap.
110    int size() const { return num_items; }
111
112    /// \brief Checks if the heap stores no items.
113    ///
114    ///   Returns \c true if and only if the heap stores no items.
115    bool empty() const { return num_items==0; }
116
117    /// \brief Make empty this heap.
118    ///
119    /// Make empty this heap. It does not change the cross reference
120    /// map.  If you want to reuse a heap what is not surely empty you
121    /// should first clear the heap and after that you should set the
122    /// cross reference map for each item to \c PRE_HEAP.
123    void clear() {
124      container.clear(); minimum = 0; num_items = 0;
125    }
126
127    /// \brief \c item gets to the heap with priority \c value independently
128    /// if \c item was already there.
129    ///
130    /// This method calls \ref push(\c item, \c value) if \c item is not
131    /// stored in the heap and it calls \ref decrease(\c item, \c value) or
132    /// \ref increase(\c item, \c value) otherwise.
133    void set (Item const item, PrioType const value);
134   
135    /// \brief Adds \c item to the heap with priority \c value.
136    ///   
137    /// Adds \c item to the heap with priority \c value.
138    /// \pre \c item must not be stored in the heap.
139    void push (Item const item, PrioType const value);
140   
141    /// \brief Returns the item with minimum priority relative to \c Compare.
142    ///
143    /// This method returns the item with minimum priority relative to \c
144    /// Compare. 
145    /// \pre The heap must be nonempty. 
146    Item top() const { return container[minimum].name; }
147
148    /// \brief Returns the minimum priority relative to \c Compare.
149    ///
150    /// It returns the minimum priority relative to \c Compare.
151    /// \pre The heap must be nonempty.
152    PrioType prio() const { return container[minimum].prio; }
153   
154    /// \brief Returns the priority of \c item.
155    ///
156    /// This function returns the priority of \c item.
157    /// \pre \c item must be in the heap.
158    PrioType& operator[](const Item& item) {
159      return container[iimap[item]].prio;
160    }
161   
162    /// \brief Returns the priority of \c item.
163    ///
164    /// It returns the priority of \c item.
165    /// \pre \c item must be in the heap.
166    const PrioType& operator[](const Item& item) const {
167      return container[iimap[item]].prio;
168    }
169
170
171    /// \brief Deletes the item with minimum priority relative to \c Compare.
172    ///
173    /// This method deletes the item with minimum priority relative to \c
174    /// Compare from the heap. 
175    /// \pre The heap must be non-empty. 
176    void pop();
177
178    /// \brief Deletes \c item from the heap.
179    ///
180    /// This method deletes \c item from the heap, if \c item was already
181    /// stored in the heap. It is quite inefficient in Fibonacci heaps.
182    void erase (const Item& item);
183
184    /// \brief Decreases the priority of \c item to \c value.
185    ///
186    /// This method decreases the priority of \c item to \c value.
187    /// \pre \c item must be stored in the heap with priority at least \c
188    ///   value relative to \c Compare.
189    void decrease (Item item, PrioType const value);
190
191    /// \brief Increases the priority of \c item to \c value.
192    ///
193    /// This method sets the priority of \c item to \c value. Though
194    /// there is no precondition on the priority of \c item, this
195    /// method should be used only if it is indeed necessary to increase
196    /// (relative to \c Compare) the priority of \c item, because this
197    /// method is inefficient.
198    void increase (Item item, PrioType const value) {
199      erase(item);
200      push(item, value);
201    }
202
203
204    /// \brief Returns if \c item is in, has already been in, or has never
205    /// been in the heap.
206    ///
207    /// This method returns PRE_HEAP if \c item has never been in the
208    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
209    /// otherwise. In the latter case it is possible that \c item will
210    /// get back to the heap again.
211    state_enum state(const Item &item) const {
212      int i=iimap[item];
213      if( i>=0 ) {
214        if ( container[i].in ) i=0;
215        else i=-2;
216      }
217      return state_enum(i);
218    }   
219
220    /// \brief Sets the state of the \c item in the heap.
221    ///
222    /// Sets the state of the \c item in the heap. It can be used to
223    /// manually clear the heap when it is important to achive the
224    /// better time complexity.
225    /// \param i The item.
226    /// \param st The state. It should not be \c IN_HEAP.
227    void state(const Item& i, state_enum st) {
228      switch (st) {
229      case POST_HEAP:
230      case PRE_HEAP:
231        if (state(i) == IN_HEAP) {
232          erase(i);
233        }
234        iimap[i] = st;
235        break;
236      case IN_HEAP:
237        break;
238      }
239    }
240   
241  private:
242   
243    void balance();
244    void makeroot(int c);
245    void cut(int a, int b);
246    void cascade(int a);
247    void fuse(int a, int b);
248    void unlace(int a);
249
250
251    class store {
252      friend class FibHeap;
253     
254      Item name;
255      int parent;
256      int left_neighbor;
257      int right_neighbor;
258      int child;
259      int degree; 
260      bool marked;
261      bool in;
262      PrioType prio;
263     
264      store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
265    };
266  };   
267 
268
269
270    // **********************************************************************
271    //  IMPLEMENTATIONS
272    // **********************************************************************
273   
274  template <typename Item, typename Prio, typename ItemIntMap,
275    typename Compare>
276  void FibHeap<Item, Prio, ItemIntMap, Compare>::set
277  (Item const item, PrioType const value)
278  {
279    int i=iimap[item];
280    if ( i >= 0 && container[i].in ) {
281      if ( comp(value, container[i].prio) ) decrease(item, value);
282      if ( comp(container[i].prio, value) ) increase(item, value);
283    } else push(item, value);
284  }
285   
286  template <typename Item, typename Prio, typename ItemIntMap,
287    typename Compare>
288  void FibHeap<Item, Prio, ItemIntMap, Compare>::push
289  (Item const item, PrioType const value) {
290      int i=iimap[item];     
291      if ( i < 0 ) {
292        int s=container.size();
293        iimap.set( item, s );   
294        store st;
295        st.name=item;
296        container.push_back(st);
297        i=s;
298      } else {
299        container[i].parent=container[i].child=-1;
300        container[i].degree=0;
301        container[i].in=true;
302        container[i].marked=false;
303      }
304
305      if ( num_items ) {
306        container[container[minimum].right_neighbor].left_neighbor=i;
307        container[i].right_neighbor=container[minimum].right_neighbor;
308        container[minimum].right_neighbor=i;
309        container[i].left_neighbor=minimum;
310        if ( comp( value, container[minimum].prio) ) minimum=i;
311      } else {
312        container[i].right_neighbor=container[i].left_neighbor=i;
313        minimum=i;     
314      }
315      container[i].prio=value;
316      ++num_items;
317    }
318   
319  template <typename Item, typename Prio, typename ItemIntMap,
320    typename Compare>
321  void FibHeap<Item, Prio, ItemIntMap, Compare>::pop() {
322      /*The first case is that there are only one root.*/
323      if ( container[minimum].left_neighbor==minimum ) {
324        container[minimum].in=false;
325        if ( container[minimum].degree!=0 ) {
326          makeroot(container[minimum].child);
327          minimum=container[minimum].child;
328          balance();
329        }
330      } else {
331        int right=container[minimum].right_neighbor;
332        unlace(minimum);
333        container[minimum].in=false;
334        if ( container[minimum].degree > 0 ) {
335          int left=container[minimum].left_neighbor;
336          int child=container[minimum].child;
337          int last_child=container[child].left_neighbor;
338       
339          makeroot(child);
340         
341          container[left].right_neighbor=child;
342          container[child].left_neighbor=left;
343          container[right].left_neighbor=last_child;
344          container[last_child].right_neighbor=right;
345        }
346        minimum=right;
347        balance();
348      } // the case where there are more roots
349      --num_items;   
350    }
351
352
353  template <typename Item, typename Prio, typename ItemIntMap,
354    typename Compare>
355  void FibHeap<Item, Prio, ItemIntMap, Compare>::erase
356  (const Item& item) {
357      int i=iimap[item];
358     
359      if ( i >= 0 && container[i].in ) {       
360        if ( container[i].parent!=-1 ) {
361          int p=container[i].parent;
362          cut(i,p);         
363          cascade(p);
364        }
365        minimum=i;     //As if its prio would be -infinity
366        pop();
367      }
368  }
369   
370  template <typename Item, typename Prio, typename ItemIntMap,
371    typename Compare>
372  void FibHeap<Item, Prio, ItemIntMap, Compare>::decrease
373  (Item item, PrioType const value) {
374      int i=iimap[item];
375      container[i].prio=value;
376      int p=container[i].parent;
377     
378      if ( p!=-1 && comp(value, container[p].prio) ) {
379        cut(i,p);           
380        cascade(p);
381      }     
382      if ( comp(value, container[minimum].prio) ) minimum=i;
383  }
384 
385
386  template <typename Item, typename Prio, typename ItemIntMap,
387    typename Compare>
388  void FibHeap<Item, Prio, ItemIntMap, Compare>::balance() {     
389
390    int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1;
391 
392    std::vector<int> A(maxdeg,-1);
393   
394    /*
395     *Recall that now minimum does not point to the minimum prio element.
396     *We set minimum to this during balance().
397     */
398    int anchor=container[minimum].left_neighbor;
399    int next=minimum;
400    bool end=false;
401       
402       do {
403        int active=next;
404        if ( anchor==active ) end=true;
405        int d=container[active].degree;
406        next=container[active].right_neighbor;
407
408        while (A[d]!=-1) {       
409          if( comp(container[active].prio, container[A[d]].prio) ) {
410            fuse(active,A[d]);
411          } else {
412            fuse(A[d],active);
413            active=A[d];
414          }
415          A[d]=-1;
416          ++d;
417        }       
418        A[d]=active;
419       } while ( !end );
420
421
422       while ( container[minimum].parent >=0 ) minimum=container[minimum].parent;
423       int s=minimum;
424       int m=minimum;
425       do { 
426         if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
427         s=container[s].right_neighbor;
428       } while ( s != m );
429    }
430
431  template <typename Item, typename Prio, typename ItemIntMap,
432    typename Compare>
433  void FibHeap<Item, Prio, ItemIntMap, Compare>::makeroot
434  (int c) {
435      int s=c;
436      do { 
437        container[s].parent=-1;
438        s=container[s].right_neighbor;
439      } while ( s != c );
440    }
441 
442 
443  template <typename Item, typename Prio, typename ItemIntMap,
444    typename Compare>
445  void FibHeap<Item, Prio, ItemIntMap, Compare>::cut
446  (int a, int b) {   
447    /*
448     *Replacing a from the children of b.
449     */
450    --container[b].degree;
451   
452    if ( container[b].degree !=0 ) {
453      int child=container[b].child;
454      if ( child==a )
455        container[b].child=container[child].right_neighbor;
456      unlace(a);
457    }
458   
459   
460    /*Lacing a to the roots.*/
461    int right=container[minimum].right_neighbor;
462    container[minimum].right_neighbor=a;
463    container[a].left_neighbor=minimum;
464    container[a].right_neighbor=right;
465    container[right].left_neighbor=a;
466   
467    container[a].parent=-1;
468    container[a].marked=false;
469  }
470 
471
472  template <typename Item, typename Prio, typename ItemIntMap,
473    typename Compare>
474  void FibHeap<Item, Prio, ItemIntMap, Compare>::cascade
475  (int a)
476    {
477      if ( container[a].parent!=-1 ) {
478        int p=container[a].parent;
479       
480        if ( container[a].marked==false ) container[a].marked=true;
481        else {
482          cut(a,p);
483          cascade(p);
484        }
485      }
486    }
487
488
489  template <typename Item, typename Prio, typename ItemIntMap,
490    typename Compare>
491  void FibHeap<Item, Prio, ItemIntMap, Compare>::fuse
492  (int a, int b) {
493      unlace(b);
494     
495      /*Lacing b under a.*/
496      container[b].parent=a;
497
498      if (container[a].degree==0) {
499        container[b].left_neighbor=b;
500        container[b].right_neighbor=b;
501        container[a].child=b;   
502      } else {
503        int child=container[a].child;
504        int last_child=container[child].left_neighbor;
505        container[child].left_neighbor=b;
506        container[b].right_neighbor=child;
507        container[last_child].right_neighbor=b;
508        container[b].left_neighbor=last_child;
509      }
510
511      ++container[a].degree;
512     
513      container[b].marked=false;
514    }
515
516 
517  /*
518   *It is invoked only if a has siblings.
519   */
520  template <typename Item, typename Prio, typename ItemIntMap,
521    typename Compare>
522  void FibHeap<Item, Prio, ItemIntMap, Compare>::unlace
523  (int a) {     
524      int leftn=container[a].left_neighbor;
525      int rightn=container[a].right_neighbor;
526      container[leftn].right_neighbor=rightn;
527      container[rightn].left_neighbor=leftn;
528  }
529 
530
531} //namespace lemon
532
533#endif //LEMON_FIB_HEAP_H
534
Note: See TracBrowser for help on using the repository browser.