COIN-OR::LEMON - Graph Library

Changeset 2089:fce8db723736 in lemon-0.x


Ignore:
Timestamp:
05/17/06 11:07:24 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2756
Message:

SimpleBucketHeap? added

It does not supports erasing, decreasing, increasing.
It contains single linked lists

It can be used to store levels for push-relabel algorithms

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/bucket_heap.h

    r2050 r2089  
    3131
    3232  /// \ingroup auxdat
    33 
     33  ///
    3434  /// \brief A Bucket Heap implementation.
    3535  ///
     
    242242
    243243    /// \brief Decreases the priority of \c i to \c p.
    244 
     244    ///
    245245    /// This method decreases the priority of item \c i to \c p.
    246246    /// \pre \c i must be stored in the heap with priority at least \c
     
    513513  }; // class BucketHeap
    514514
     515  /// \ingroup auxdat
     516  ///
     517  /// \brief A Simplified Bucket Heap implementation.
     518  ///
     519  /// This class implements a simplified \e bucket \e heap data
     520  /// structure.  It does not provide some functionality but it faster
     521  /// and simplier data structure than the BucketHeap. The main
     522  /// difference is that the BucketHeap stores for every key a double
     523  /// linked list while this class stores just simple lists. In the
     524  /// other way it does not supports erasing each elements just the
     525  /// minimal and it does not supports key increasing, decreasing.
     526  ///
     527  /// \param _Item Type of the items to be stored. 
     528  /// \param _ItemIntMap A read and writable Item int map, used internally
     529  /// to handle the cross references.
     530  /// \param minimize If the given parameter is true then the heap gives back
     531  /// the lowest priority.
     532  ///
     533  /// \sa BucketHeap
     534  template <typename _Item, typename _ItemIntMap, bool minimize = true >
     535  class SimpleBucketHeap {
     536
     537  public:
     538    typedef _Item Item;
     539    typedef int Prio;
     540    typedef std::pair<Item, Prio> Pair;
     541    typedef _ItemIntMap ItemIntMap;
     542
     543    /// \brief Type to represent the items states.
     544    ///
     545    /// Each Item element have a state associated to it. It may be "in heap",
     546    /// "pre heap" or "post heap". The latter two are indifferent from the
     547    /// heap's point of view, but may be useful to the user.
     548    ///
     549    /// The ItemIntMap \e should be initialized in such way that it maps
     550    /// PRE_HEAP (-1) to any element to be put in the heap...
     551    enum state_enum {
     552      IN_HEAP = 0,
     553      PRE_HEAP = -1,
     554      POST_HEAP = -2
     555    };
     556
     557  public:
     558
     559    /// \brief The constructor.
     560    ///
     561    /// The constructor.
     562    /// \param _index should be given to the constructor, since it is used
     563    /// internally to handle the cross references. The value of the map
     564    /// should be PRE_HEAP (-1) for each element.
     565    explicit SimpleBucketHeap(ItemIntMap &_index)
     566      : index(_index), free(-1), num(0), minimal(0) {}
     567   
     568    /// \brief Returns the number of items stored in the heap.
     569    ///
     570    /// The number of items stored in the heap.
     571    int size() const { return num; }
     572   
     573    /// \brief Checks if the heap stores no items.
     574    ///
     575    /// Returns \c true if and only if the heap stores no items.
     576    bool empty() const { return num == 0; }
     577
     578    /// \brief Make empty this heap.
     579    ///
     580    /// Make empty this heap. It does not change the cross reference
     581    /// map.  If you want to reuse a heap what is not surely empty you
     582    /// should first clear the heap and after that you should set the
     583    /// cross reference map for each item to \c PRE_HEAP.
     584    void clear() {
     585      data.clear(); first.clear(); free = -1; num = 0; minimal = 0;
     586    }
     587
     588    /// \brief Insert a pair of item and priority into the heap.
     589    ///
     590    /// Adds \c p.first to the heap with priority \c p.second.
     591    /// \param p The pair to insert.
     592    void push(const Pair& p) {
     593      push(p.first, p.second);
     594    }
     595
     596    /// \brief Insert an item into the heap with the given priority.
     597    ///   
     598    /// Adds \c i to the heap with priority \c p.
     599    /// \param i The item to insert.
     600    /// \param p The priority of the item.
     601    void push(const Item &i, const Prio &p) {
     602      int idx;
     603      if (free == -1) {
     604        idx = data.size();
     605        data.push_back(BucketItem(i, p));
     606      } else {
     607        idx = free;
     608        free = data[idx].next;
     609        data[idx].item = i; data[idx].value = p;
     610      }
     611      index[i] = idx;
     612      if (p >= (int)first.size()) first.resize(p + 1, -1);
     613      data[idx].next = first[p];
     614      first[p] = idx;
     615      if (p < minimal) {
     616        minimal = p;
     617      }
     618      ++num;
     619    }
     620
     621    /// \brief Returns the item with minimum priority.
     622    ///
     623    /// This method returns the item with minimum priority.
     624    /// \pre The heap must be nonempty. 
     625    Item top() const {
     626      while (first[minimal] == -1) {
     627        ++minimal;
     628      }
     629      return data[first[minimal]].item;
     630    }
     631
     632    /// \brief Returns the minimum priority.
     633    ///
     634    /// It returns the minimum priority.
     635    /// \pre The heap must be nonempty.
     636    Prio prio() const {
     637      while (first[minimal] == -1) {
     638        ++minimal;
     639      }
     640      return minimal;
     641    }
     642
     643    /// \brief Deletes the item with minimum priority.
     644    ///
     645    /// This method deletes the item with minimum priority from the heap. 
     646    /// \pre The heap must be non-empty. 
     647    void pop() {
     648      while (first[minimal] == -1) {
     649        ++minimal;
     650      }
     651      int idx = first[minimal];
     652      index[data[idx].item] = -2;
     653      first[minimal] = data[idx].next;
     654      data[idx].next = free;
     655      free = idx;
     656      --num;
     657    }
     658   
     659    /// \brief Returns the priority of \c i.
     660    ///
     661    /// This function returns the priority of item \c i. 
     662    /// \pre \c i must be in the heap.
     663    /// \param i The item.
     664    Prio operator[](const Item &i) const {
     665      int idx = index[i];
     666      return data[idx].value;
     667    }
     668
     669    /// \brief Returns if \c item is in, has already been in, or has
     670    /// never been in the heap.
     671    ///
     672    /// This method returns PRE_HEAP if \c item has never been in the
     673    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
     674    /// otherwise. In the latter case it is possible that \c item will
     675    /// get back to the heap again.
     676    /// \param i The item.
     677    state_enum state(const Item &i) const {
     678      int idx = index[i];
     679      if (idx >= 0) idx = 0;
     680      return state_enum(idx);
     681    }
     682
     683  private:
     684
     685    struct BucketItem {
     686      BucketItem(const Item& _item, int _value)
     687        : item(_item), value(_value) {}
     688
     689      Item item;
     690      int value;
     691
     692      int next;
     693    };
     694
     695    ItemIntMap& index;
     696    std::vector<int> first;
     697    std::vector<BucketItem> data;
     698    int free, num;
     699    mutable int minimal;
     700
     701  }; // class SimpleBucketHeap
     702
     703  template <typename _Item, typename _ItemIntMap>
     704  class SimpleBucketHeap<_Item, _ItemIntMap, false> {
     705
     706  public:
     707    typedef _Item Item;
     708    typedef int Prio;
     709    typedef std::pair<Item, Prio> Pair;
     710    typedef _ItemIntMap ItemIntMap;
     711
     712    enum state_enum {
     713      IN_HEAP = 0,
     714      PRE_HEAP = -1,
     715      POST_HEAP = -2
     716    };
     717
     718  public:
     719
     720    explicit SimpleBucketHeap(ItemIntMap &_index)
     721      : index(_index), free(-1), num(0), maximal(0) {}
     722   
     723    int size() const { return num; }
     724   
     725    bool empty() const { return num == 0; }
     726
     727    void clear() {
     728      data.clear(); first.clear(); free = -1; num = 0; maximal = 0;
     729    }
     730
     731    void push(const Pair& p) {
     732      push(p.first, p.second);
     733    }
     734
     735    void push(const Item &i, const Prio &p) {
     736      int idx;
     737      if (free == -1) {
     738        idx = data.size();
     739        data.push_back(BucketItem(i, p));
     740      } else {
     741        idx = free;
     742        free = data[idx].next;
     743        data[idx].item = i; data[idx].value = p;
     744      }
     745      index[i] = idx;
     746      if (p >= (int)first.size()) first.resize(p + 1, -1);
     747      data[idx].next = first[p];
     748      first[p] = idx;
     749      if (p > maximal) {
     750        maximal = p;
     751      }
     752      ++num;
     753    }
     754
     755    Item top() const {
     756      while (first[maximal] == -1) {
     757        --maximal;
     758      }
     759      return data[first[maximal]].item;
     760    }
     761
     762    Prio prio() const {
     763      while (first[maximal] == -1) {
     764        --maximal;
     765      }
     766      return maximal;
     767    }
     768
     769    void pop() {
     770      while (first[maximal] == -1) {
     771        --maximal;
     772      }
     773      int idx = first[maximal];
     774      index[data[idx].item] = -2;
     775      first[maximal] = data[idx].next;
     776      data[idx].next = free;
     777      free = idx;
     778      --num;
     779    }
     780   
     781    Prio operator[](const Item &i) const {
     782      int idx = index[i];
     783      return data[idx].value;
     784    }
     785
     786    state_enum state(const Item &i) const {
     787      int idx = index[i];
     788      if (idx >= 0) idx = 0;
     789      return state_enum(idx);
     790    }
     791
     792  private:
     793
     794    struct BucketItem {
     795      BucketItem(const Item& _item, int _value)
     796        : item(_item), value(_value) {}
     797
     798      Item item;
     799      int value;
     800
     801      int next;
     802    };
     803
     804    ItemIntMap& index;
     805    std::vector<int> first;
     806    std::vector<BucketItem> data;
     807    int free, num;
     808    mutable int maximal;
     809
     810  };
     811
    515812}
    516813 
Note: See TracChangeset for help on using the changeset viewer.