COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/fib_heap.h @ 1902:e9af75c90c28

Last change on this file since 1902:e9af75c90c28 was 1902:e9af75c90c28, checked in by Balazs Dezso, 18 years ago

state setting function for heaps

If we know that which elements were in the heap then
we can clear it in better time complexity.

File size: 15.0 KB
Line 
1/* -*- C++ -*-
2 * lemon/fib_heap.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17#ifndef LEMON_FIB_HEAP_H
18#define LEMON_FIB_HEAP_H
19
20///\file
21///\ingroup auxdat
22///\brief Fibonacci Heap implementation.
23
24#include <vector>
25#include <functional>
26#include <cmath>
27
28namespace lemon {
29 
30  /// \ingroup auxdat
31
32  /// Fibonacci Heap.
33
34  ///This class implements the \e Fibonacci \e heap data structure. A \e heap
35  ///is a data structure for storing items with specified values called \e
36  ///priorities in such a way that finding the item with minimum priority is
37  ///efficient. \c Compare specifies the ordering of the priorities. In a heap
38  ///one can change the priority of an item, add or erase an item, etc.
39  ///
40  ///The methods \ref increase and \ref erase are not efficient in a Fibonacci
41  ///heap. In case of many calls to these operations, it is better to use a
42  ///\e binary \e heap.
43  ///
44  ///\param Item Type of the items to be stored. 
45  ///\param Prio Type of the priority of the items.
46  ///\param ItemIntMap A read and writable Item int map, used internally
47  ///to handle the cross references.
48  ///\param Compare A class for the ordering of the priorities. The
49  ///default is \c std::less<Prio>.
50  ///
51  ///\sa BinHeap
52  ///\sa Dijkstra
53  ///\author Jacint Szabo
54 
55#ifdef DOXYGEN
56  template <typename Item,
57            typename Prio,
58            typename ItemIntMap,
59            typename Compare>
60#else
61  template <typename Item,
62            typename Prio,
63            typename ItemIntMap,
64            typename Compare = std::less<Prio> >
65#endif
66  class FibHeap {
67  public:     
68    typedef Prio PrioType;
69   
70  private:
71    class store;
72   
73    std::vector<store> container;
74    int minimum;
75    ItemIntMap &iimap;
76    Compare comp;
77    int num_items;
78   
79  public:
80    ///Status of the nodes
81    enum state_enum {
82      ///The node is in the heap
83      IN_HEAP = 0,
84      ///The node has never been in the heap
85      PRE_HEAP = -1,
86      ///The node was in the heap but it got out of it
87      POST_HEAP = -2
88    };
89   
90    /// \brief The constructor
91    ///
92    /// \c _iimap should be given to the constructor, since it is
93    ///   used internally to handle the cross references.
94    explicit FibHeap(ItemIntMap &_iimap)
95      : minimum(0), iimap(_iimap), num_items() {}
96 
97    /// \brief The constructor
98    ///
99    /// \c _iimap should be given to the constructor, since it is used
100    /// internally to handle the cross references. \c _comp is an
101    /// object for ordering of the priorities.
102    FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0),
103                  iimap(_iimap), comp(_comp), num_items() {}
104   
105    /// \brief The number of items stored in the heap.
106    ///
107    /// Returns the number of items stored in the heap.
108    int size() const { return num_items; }
109
110    /// \brief Checks if the heap stores no items.
111    ///
112    ///   Returns \c true if and only if the heap stores no items.
113    bool empty() const { return num_items==0; }
114
115    /// \brief Make empty this heap.
116    ///
117    /// Make empty this heap.
118    void clear() {
119      if (num_items != 0) {
120        for (int i = 0; i < (int)container.size(); ++i) {
121          iimap[container[i].name] = -2;
122        }
123      }
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        index[i] = st;
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 Item, typename Prio, typename ItemIntMap,
273    typename Compare>
274  void FibHeap<Item, 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 Item, typename Prio, typename ItemIntMap,
285    typename Compare>
286  void FibHeap<Item, Prio, ItemIntMap, Compare>::push
287  (Item const item, PrioType const value) {
288      int i=iimap[item];     
289      if ( i < 0 ) {
290        int s=container.size();
291        iimap.set( item, s );   
292        store st;
293        st.name=item;
294        container.push_back(st);
295        i=s;
296      } else {
297        container[i].parent=container[i].child=-1;
298        container[i].degree=0;
299        container[i].in=true;
300        container[i].marked=false;
301      }
302
303      if ( num_items ) {
304        container[container[minimum].right_neighbor].left_neighbor=i;
305        container[i].right_neighbor=container[minimum].right_neighbor;
306        container[minimum].right_neighbor=i;
307        container[i].left_neighbor=minimum;
308        if ( comp( value, container[minimum].prio) ) minimum=i;
309      } else {
310        container[i].right_neighbor=container[i].left_neighbor=i;
311        minimum=i;     
312      }
313      container[i].prio=value;
314      ++num_items;
315    }
316   
317  template <typename Item, typename Prio, typename ItemIntMap,
318    typename Compare>
319  void FibHeap<Item, Prio, ItemIntMap, Compare>::pop() {
320      /*The first case is that there are only one root.*/
321      if ( container[minimum].left_neighbor==minimum ) {
322        container[minimum].in=false;
323        if ( container[minimum].degree!=0 ) {
324          makeroot(container[minimum].child);
325          minimum=container[minimum].child;
326          balance();
327        }
328      } else {
329        int right=container[minimum].right_neighbor;
330        unlace(minimum);
331        container[minimum].in=false;
332        if ( container[minimum].degree > 0 ) {
333          int left=container[minimum].left_neighbor;
334          int child=container[minimum].child;
335          int last_child=container[child].left_neighbor;
336       
337          makeroot(child);
338         
339          container[left].right_neighbor=child;
340          container[child].left_neighbor=left;
341          container[right].left_neighbor=last_child;
342          container[last_child].right_neighbor=right;
343        }
344        minimum=right;
345        balance();
346      } // the case where there are more roots
347      --num_items;   
348    }
349
350
351  template <typename Item, typename Prio, typename ItemIntMap,
352    typename Compare>
353  void FibHeap<Item, Prio, ItemIntMap, Compare>::erase
354  (const Item& item) {
355      int i=iimap[item];
356     
357      if ( i >= 0 && container[i].in ) {       
358        if ( container[i].parent!=-1 ) {
359          int p=container[i].parent;
360          cut(i,p);         
361          cascade(p);
362        }
363        minimum=i;     //As if its prio would be -infinity
364        pop();
365      }
366  }
367   
368  template <typename Item, typename Prio, typename ItemIntMap,
369    typename Compare>
370  void FibHeap<Item, Prio, ItemIntMap, Compare>::decrease
371  (Item item, PrioType const value) {
372      int i=iimap[item];
373      container[i].prio=value;
374      int p=container[i].parent;
375     
376      if ( p!=-1 && comp(value, container[p].prio) ) {
377        cut(i,p);           
378        cascade(p);
379      }     
380      if ( comp(value, container[minimum].prio) ) minimum=i;
381  }
382 
383
384  template <typename Item, typename Prio, typename ItemIntMap,
385    typename Compare>
386  void FibHeap<Item, Prio, ItemIntMap, Compare>::balance() {     
387
388    int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1;
389 
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;
399       
400       do {
401        int active=next;
402        if ( anchor==active ) end=true;
403        int d=container[active].degree;
404        next=container[active].right_neighbor;
405
406        while (A[d]!=-1) {       
407          if( comp(container[active].prio, container[A[d]].prio) ) {
408            fuse(active,A[d]);
409          } else {
410            fuse(A[d],active);
411            active=A[d];
412          }
413          A[d]=-1;
414          ++d;
415        }       
416        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 Item, typename Prio, typename ItemIntMap,
430    typename Compare>
431  void FibHeap<Item, Prio, ItemIntMap, Compare>::makeroot
432  (int c) {
433      int s=c;
434      do { 
435        container[s].parent=-1;
436        s=container[s].right_neighbor;
437      } while ( s != c );
438    }
439 
440 
441  template <typename Item, typename Prio, typename ItemIntMap,
442    typename Compare>
443  void FibHeap<Item, 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 Item, typename Prio, typename ItemIntMap,
471    typename Compare>
472  void FibHeap<Item, Prio, ItemIntMap, Compare>::cascade
473  (int a)
474    {
475      if ( container[a].parent!=-1 ) {
476        int p=container[a].parent;
477       
478        if ( container[a].marked==false ) container[a].marked=true;
479        else {
480          cut(a,p);
481          cascade(p);
482        }
483      }
484    }
485
486
487  template <typename Item, typename Prio, typename ItemIntMap,
488    typename Compare>
489  void FibHeap<Item, Prio, ItemIntMap, Compare>::fuse
490  (int a, int b) {
491      unlace(b);
492     
493      /*Lacing b under a.*/
494      container[b].parent=a;
495
496      if (container[a].degree==0) {
497        container[b].left_neighbor=b;
498        container[b].right_neighbor=b;
499        container[a].child=b;   
500      } else {
501        int child=container[a].child;
502        int last_child=container[child].left_neighbor;
503        container[child].left_neighbor=b;
504        container[b].right_neighbor=child;
505        container[last_child].right_neighbor=b;
506        container[b].left_neighbor=last_child;
507      }
508
509      ++container[a].degree;
510     
511      container[b].marked=false;
512    }
513
514 
515  /*
516   *It is invoked only if a has siblings.
517   */
518  template <typename Item, typename Prio, typename ItemIntMap,
519    typename Compare>
520  void FibHeap<Item, Prio, ItemIntMap, Compare>::unlace
521  (int a) {     
522      int leftn=container[a].left_neighbor;
523      int rightn=container[a].right_neighbor;
524      container[leftn].right_neighbor=rightn;
525      container[rightn].left_neighbor=leftn;
526  }
527 
528
529} //namespace lemon
530
531#endif //LEMON_FIB_HEAP_H
532
Note: See TracBrowser for help on using the repository browser.