1.1 --- a/lemon/Makefile.am Thu Nov 05 16:01:39 2009 +0100
1.2 +++ b/lemon/Makefile.am Thu Dec 10 17:10:25 2009 +0100
1.3 @@ -59,6 +59,7 @@
1.4 lemon/assert.h \
1.5 lemon/bfs.h \
1.6 lemon/bin_heap.h \
1.7 + lemon/bucket_heap.h \
1.8 lemon/cbc.h \
1.9 lemon/circulation.h \
1.10 lemon/clp.h \
1.11 @@ -76,6 +77,7 @@
1.12 lemon/elevator.h \
1.13 lemon/error.h \
1.14 lemon/euler.h \
1.15 + lemon/fib_heap.h \
1.16 lemon/full_graph.h \
1.17 lemon/glpk.h \
1.18 lemon/gomory_hu.h \
1.19 @@ -98,6 +100,7 @@
1.20 lemon/network_simplex.h \
1.21 lemon/path.h \
1.22 lemon/preflow.h \
1.23 + lemon/radix_heap.h \
1.24 lemon/radix_sort.h \
1.25 lemon/random.h \
1.26 lemon/smart_graph.h \
2.1 --- a/lemon/bin_heap.h Thu Nov 05 16:01:39 2009 +0100
2.2 +++ b/lemon/bin_heap.h Thu Dec 10 17:10:25 2009 +0100
2.3 @@ -33,23 +33,23 @@
2.4 ///
2.5 ///\brief A Binary Heap implementation.
2.6 ///
2.7 - ///This class implements the \e binary \e heap data structure.
2.8 - ///
2.9 + ///This class implements the \e binary \e heap data structure.
2.10 + ///
2.11 ///A \e heap is a data structure for storing items with specified values
2.12 ///called \e priorities in such a way that finding the item with minimum
2.13 - ///priority is efficient. \c Comp specifies the ordering of the priorities.
2.14 + ///priority is efficient. \c CMP specifies the ordering of the priorities.
2.15 ///In a heap one can change the priority of an item, add or erase an
2.16 ///item, etc.
2.17 ///
2.18 ///\tparam PR Type of the priority of the items.
2.19 ///\tparam IM A read and writable item map with int values, used internally
2.20 ///to handle the cross references.
2.21 - ///\tparam Comp A functor class for the ordering of the priorities.
2.22 + ///\tparam CMP A functor class for the ordering of the priorities.
2.23 ///The default is \c std::less<PR>.
2.24 ///
2.25 ///\sa FibHeap
2.26 ///\sa Dijkstra
2.27 - template <typename PR, typename IM, typename Comp = std::less<PR> >
2.28 + template <typename PR, typename IM, typename CMP = std::less<PR> >
2.29 class BinHeap {
2.30
2.31 public:
2.32 @@ -62,7 +62,7 @@
2.33 ///\e
2.34 typedef std::pair<Item,Prio> Pair;
2.35 ///\e
2.36 - typedef Comp Compare;
2.37 + typedef CMP Compare;
2.38
2.39 /// \brief Type to represent the items states.
2.40 ///
3.1 --- a/lemon/bits/map_extender.h Thu Nov 05 16:01:39 2009 +0100
3.2 +++ b/lemon/bits/map_extender.h Thu Dec 10 17:10:25 2009 +0100
3.3 @@ -49,6 +49,8 @@
3.4 typedef typename Parent::Reference Reference;
3.5 typedef typename Parent::ConstReference ConstReference;
3.6
3.7 + typedef typename Parent::ReferenceMapTag ReferenceMapTag;
3.8 +
3.9 class MapIt;
3.10 class ConstMapIt;
3.11
3.12 @@ -82,36 +84,36 @@
3.13
3.14 typedef typename Map::Value Value;
3.15
3.16 - MapIt() {}
3.17 + MapIt() : map(NULL) {}
3.18
3.19 - MapIt(Invalid i) : Parent(i) { }
3.20 + MapIt(Invalid i) : Parent(i), map(NULL) {}
3.21
3.22 - explicit MapIt(Map& _map) : map(_map) {
3.23 - map.notifier()->first(*this);
3.24 + explicit MapIt(Map& _map) : map(&_map) {
3.25 + map->notifier()->first(*this);
3.26 }
3.27
3.28 MapIt(const Map& _map, const Item& item)
3.29 - : Parent(item), map(_map) {}
3.30 + : Parent(item), map(&_map) {}
3.31
3.32 MapIt& operator++() {
3.33 - map.notifier()->next(*this);
3.34 + map->notifier()->next(*this);
3.35 return *this;
3.36 }
3.37
3.38 typename MapTraits<Map>::ConstReturnValue operator*() const {
3.39 - return map[*this];
3.40 + return (*map)[*this];
3.41 }
3.42
3.43 typename MapTraits<Map>::ReturnValue operator*() {
3.44 - return map[*this];
3.45 + return (*map)[*this];
3.46 }
3.47
3.48 void set(const Value& value) {
3.49 - map.set(*this, value);
3.50 + map->set(*this, value);
3.51 }
3.52
3.53 protected:
3.54 - Map& map;
3.55 + Map* map;
3.56
3.57 };
3.58
3.59 @@ -122,19 +124,19 @@
3.60
3.61 typedef typename Map::Value Value;
3.62
3.63 - ConstMapIt() {}
3.64 + ConstMapIt() : map(NULL) {}
3.65
3.66 - ConstMapIt(Invalid i) : Parent(i) { }
3.67 + ConstMapIt(Invalid i) : Parent(i), map(NULL) {}
3.68
3.69 - explicit ConstMapIt(Map& _map) : map(_map) {
3.70 - map.notifier()->first(*this);
3.71 + explicit ConstMapIt(Map& _map) : map(&_map) {
3.72 + map->notifier()->first(*this);
3.73 }
3.74
3.75 ConstMapIt(const Map& _map, const Item& item)
3.76 : Parent(item), map(_map) {}
3.77
3.78 ConstMapIt& operator++() {
3.79 - map.notifier()->next(*this);
3.80 + map->notifier()->next(*this);
3.81 return *this;
3.82 }
3.83
3.84 @@ -143,32 +145,32 @@
3.85 }
3.86
3.87 protected:
3.88 - const Map& map;
3.89 + const Map* map;
3.90 };
3.91
3.92 class ItemIt : public Item {
3.93 typedef Item Parent;
3.94
3.95 public:
3.96 + ItemIt() : map(NULL) {}
3.97
3.98 - ItemIt() {}
3.99
3.100 - ItemIt(Invalid i) : Parent(i) { }
3.101 + ItemIt(Invalid i) : Parent(i), map(NULL) {}
3.102
3.103 - explicit ItemIt(Map& _map) : map(_map) {
3.104 - map.notifier()->first(*this);
3.105 + explicit ItemIt(Map& _map) : map(&_map) {
3.106 + map->notifier()->first(*this);
3.107 }
3.108
3.109 ItemIt(const Map& _map, const Item& item)
3.110 - : Parent(item), map(_map) {}
3.111 + : Parent(item), map(&_map) {}
3.112
3.113 ItemIt& operator++() {
3.114 - map.notifier()->next(*this);
3.115 + map->notifier()->next(*this);
3.116 return *this;
3.117 }
3.118
3.119 protected:
3.120 - const Map& map;
3.121 + const Map* map;
3.122
3.123 };
3.124 };
3.125 @@ -191,6 +193,8 @@
3.126 typedef typename Parent::Reference Reference;
3.127 typedef typename Parent::ConstReference ConstReference;
3.128
3.129 + typedef typename Parent::ReferenceMapTag ReferenceMapTag;
3.130 +
3.131 class MapIt;
3.132 class ConstMapIt;
3.133
3.134 @@ -227,36 +231,36 @@
3.135 public:
3.136 typedef typename Map::Value Value;
3.137
3.138 - MapIt() {}
3.139 + MapIt() : map(NULL) {}
3.140
3.141 - MapIt(Invalid i) : Parent(i) { }
3.142 + MapIt(Invalid i) : Parent(i), map(NULL) { }
3.143
3.144 - explicit MapIt(Map& _map) : map(_map) {
3.145 - map.graph.first(*this);
3.146 + explicit MapIt(Map& _map) : map(&_map) {
3.147 + map->graph.first(*this);
3.148 }
3.149
3.150 MapIt(const Map& _map, const Item& item)
3.151 - : Parent(item), map(_map) {}
3.152 + : Parent(item), map(&_map) {}
3.153
3.154 MapIt& operator++() {
3.155 - map.graph.next(*this);
3.156 + map->graph.next(*this);
3.157 return *this;
3.158 }
3.159
3.160 typename MapTraits<Map>::ConstReturnValue operator*() const {
3.161 - return map[*this];
3.162 + return (*map)[*this];
3.163 }
3.164
3.165 typename MapTraits<Map>::ReturnValue operator*() {
3.166 - return map[*this];
3.167 + return (*map)[*this];
3.168 }
3.169
3.170 void set(const Value& value) {
3.171 - map.set(*this, value);
3.172 + map->set(*this, value);
3.173 }
3.174
3.175 protected:
3.176 - Map& map;
3.177 + Map* map;
3.178
3.179 };
3.180
3.181 @@ -267,53 +271,53 @@
3.182
3.183 typedef typename Map::Value Value;
3.184
3.185 - ConstMapIt() {}
3.186 + ConstMapIt() : map(NULL) {}
3.187
3.188 - ConstMapIt(Invalid i) : Parent(i) { }
3.189 + ConstMapIt(Invalid i) : Parent(i), map(NULL) { }
3.190
3.191 - explicit ConstMapIt(Map& _map) : map(_map) {
3.192 - map.graph.first(*this);
3.193 + explicit ConstMapIt(Map& _map) : map(&_map) {
3.194 + map->graph.first(*this);
3.195 }
3.196
3.197 ConstMapIt(const Map& _map, const Item& item)
3.198 - : Parent(item), map(_map) {}
3.199 + : Parent(item), map(&_map) {}
3.200
3.201 ConstMapIt& operator++() {
3.202 - map.graph.next(*this);
3.203 + map->graph.next(*this);
3.204 return *this;
3.205 }
3.206
3.207 typename MapTraits<Map>::ConstReturnValue operator*() const {
3.208 - return map[*this];
3.209 + return (*map)[*this];
3.210 }
3.211
3.212 protected:
3.213 - const Map& map;
3.214 + const Map* map;
3.215 };
3.216
3.217 class ItemIt : public Item {
3.218 typedef Item Parent;
3.219
3.220 public:
3.221 + ItemIt() : map(NULL) {}
3.222
3.223 - ItemIt() {}
3.224
3.225 - ItemIt(Invalid i) : Parent(i) { }
3.226 + ItemIt(Invalid i) : Parent(i), map(NULL) { }
3.227
3.228 - explicit ItemIt(Map& _map) : map(_map) {
3.229 - map.graph.first(*this);
3.230 + explicit ItemIt(Map& _map) : map(&_map) {
3.231 + map->graph.first(*this);
3.232 }
3.233
3.234 ItemIt(const Map& _map, const Item& item)
3.235 - : Parent(item), map(_map) {}
3.236 + : Parent(item), map(&_map) {}
3.237
3.238 ItemIt& operator++() {
3.239 - map.graph.next(*this);
3.240 + map->graph.next(*this);
3.241 return *this;
3.242 }
3.243
3.244 protected:
3.245 - const Map& map;
3.246 + const Map* map;
3.247
3.248 };
3.249
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/lemon/bucket_heap.h Thu Dec 10 17:10:25 2009 +0100
4.3 @@ -0,0 +1,567 @@
4.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
4.5 + *
4.6 + * This file is a part of LEMON, a generic C++ optimization library.
4.7 + *
4.8 + * Copyright (C) 2003-2009
4.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
4.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
4.11 + *
4.12 + * Permission to use, modify and distribute this software is granted
4.13 + * provided that this copyright notice appears in all copies. For
4.14 + * precise terms see the accompanying LICENSE file.
4.15 + *
4.16 + * This software is provided "AS IS" with no warranty of any kind,
4.17 + * express or implied, and with no claim as to its suitability for any
4.18 + * purpose.
4.19 + *
4.20 + */
4.21 +
4.22 +#ifndef LEMON_BUCKET_HEAP_H
4.23 +#define LEMON_BUCKET_HEAP_H
4.24 +
4.25 +///\ingroup auxdat
4.26 +///\file
4.27 +///\brief Bucket Heap implementation.
4.28 +
4.29 +#include <vector>
4.30 +#include <utility>
4.31 +#include <functional>
4.32 +
4.33 +namespace lemon {
4.34 +
4.35 + namespace _bucket_heap_bits {
4.36 +
4.37 + template <bool MIN>
4.38 + struct DirectionTraits {
4.39 + static bool less(int left, int right) {
4.40 + return left < right;
4.41 + }
4.42 + static void increase(int& value) {
4.43 + ++value;
4.44 + }
4.45 + };
4.46 +
4.47 + template <>
4.48 + struct DirectionTraits<false> {
4.49 + static bool less(int left, int right) {
4.50 + return left > right;
4.51 + }
4.52 + static void increase(int& value) {
4.53 + --value;
4.54 + }
4.55 + };
4.56 +
4.57 + }
4.58 +
4.59 + /// \ingroup auxdat
4.60 + ///
4.61 + /// \brief A Bucket Heap implementation.
4.62 + ///
4.63 + /// This class implements the \e bucket \e heap data structure. A \e heap
4.64 + /// is a data structure for storing items with specified values called \e
4.65 + /// priorities in such a way that finding the item with minimum priority is
4.66 + /// efficient. The bucket heap is very simple implementation, it can store
4.67 + /// only integer priorities and it stores for each priority in the
4.68 + /// \f$ [0..C) \f$ range a list of items. So it should be used only when
4.69 + /// the priorities are small. It is not intended to use as dijkstra heap.
4.70 + ///
4.71 + /// \param IM A read and write Item int map, used internally
4.72 + /// to handle the cross references.
4.73 + /// \param MIN If the given parameter is false then instead of the
4.74 + /// minimum value the maximum can be retrivied with the top() and
4.75 + /// prio() member functions.
4.76 + template <typename IM, bool MIN = true>
4.77 + class BucketHeap {
4.78 +
4.79 + public:
4.80 + /// \e
4.81 + typedef typename IM::Key Item;
4.82 + /// \e
4.83 + typedef int Prio;
4.84 + /// \e
4.85 + typedef std::pair<Item, Prio> Pair;
4.86 + /// \e
4.87 + typedef IM ItemIntMap;
4.88 +
4.89 + private:
4.90 +
4.91 + typedef _bucket_heap_bits::DirectionTraits<MIN> Direction;
4.92 +
4.93 + public:
4.94 +
4.95 + /// \brief Type to represent the items states.
4.96 + ///
4.97 + /// Each Item element have a state associated to it. It may be "in heap",
4.98 + /// "pre heap" or "post heap". The latter two are indifferent from the
4.99 + /// heap's point of view, but may be useful to the user.
4.100 + ///
4.101 + /// The item-int map must be initialized in such way that it assigns
4.102 + /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
4.103 + enum State {
4.104 + IN_HEAP = 0, ///< = 0.
4.105 + PRE_HEAP = -1, ///< = -1.
4.106 + POST_HEAP = -2 ///< = -2.
4.107 + };
4.108 +
4.109 + public:
4.110 + /// \brief The constructor.
4.111 + ///
4.112 + /// The constructor.
4.113 + /// \param map should be given to the constructor, since it is used
4.114 + /// internally to handle the cross references. The value of the map
4.115 + /// should be PRE_HEAP (-1) for each element.
4.116 + explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {}
4.117 +
4.118 + /// The number of items stored in the heap.
4.119 + ///
4.120 + /// \brief Returns the number of items stored in the heap.
4.121 + int size() const { return _data.size(); }
4.122 +
4.123 + /// \brief Checks if the heap stores no items.
4.124 + ///
4.125 + /// Returns \c true if and only if the heap stores no items.
4.126 + bool empty() const { return _data.empty(); }
4.127 +
4.128 + /// \brief Make empty this heap.
4.129 + ///
4.130 + /// Make empty this heap. It does not change the cross reference
4.131 + /// map. If you want to reuse a heap what is not surely empty you
4.132 + /// should first clear the heap and after that you should set the
4.133 + /// cross reference map for each item to \c PRE_HEAP.
4.134 + void clear() {
4.135 + _data.clear(); _first.clear(); _minimum = 0;
4.136 + }
4.137 +
4.138 + private:
4.139 +
4.140 + void relocate_last(int idx) {
4.141 + if (idx + 1 < int(_data.size())) {
4.142 + _data[idx] = _data.back();
4.143 + if (_data[idx].prev != -1) {
4.144 + _data[_data[idx].prev].next = idx;
4.145 + } else {
4.146 + _first[_data[idx].value] = idx;
4.147 + }
4.148 + if (_data[idx].next != -1) {
4.149 + _data[_data[idx].next].prev = idx;
4.150 + }
4.151 + _iim[_data[idx].item] = idx;
4.152 + }
4.153 + _data.pop_back();
4.154 + }
4.155 +
4.156 + void unlace(int idx) {
4.157 + if (_data[idx].prev != -1) {
4.158 + _data[_data[idx].prev].next = _data[idx].next;
4.159 + } else {
4.160 + _first[_data[idx].value] = _data[idx].next;
4.161 + }
4.162 + if (_data[idx].next != -1) {
4.163 + _data[_data[idx].next].prev = _data[idx].prev;
4.164 + }
4.165 + }
4.166 +
4.167 + void lace(int idx) {
4.168 + if (int(_first.size()) <= _data[idx].value) {
4.169 + _first.resize(_data[idx].value + 1, -1);
4.170 + }
4.171 + _data[idx].next = _first[_data[idx].value];
4.172 + if (_data[idx].next != -1) {
4.173 + _data[_data[idx].next].prev = idx;
4.174 + }
4.175 + _first[_data[idx].value] = idx;
4.176 + _data[idx].prev = -1;
4.177 + }
4.178 +
4.179 + public:
4.180 + /// \brief Insert a pair of item and priority into the heap.
4.181 + ///
4.182 + /// Adds \c p.first to the heap with priority \c p.second.
4.183 + /// \param p The pair to insert.
4.184 + void push(const Pair& p) {
4.185 + push(p.first, p.second);
4.186 + }
4.187 +
4.188 + /// \brief Insert an item into the heap with the given priority.
4.189 + ///
4.190 + /// Adds \c i to the heap with priority \c p.
4.191 + /// \param i The item to insert.
4.192 + /// \param p The priority of the item.
4.193 + void push(const Item &i, const Prio &p) {
4.194 + int idx = _data.size();
4.195 + _iim[i] = idx;
4.196 + _data.push_back(BucketItem(i, p));
4.197 + lace(idx);
4.198 + if (Direction::less(p, _minimum)) {
4.199 + _minimum = p;
4.200 + }
4.201 + }
4.202 +
4.203 + /// \brief Returns the item with minimum priority.
4.204 + ///
4.205 + /// This method returns the item with minimum priority.
4.206 + /// \pre The heap must be nonempty.
4.207 + Item top() const {
4.208 + while (_first[_minimum] == -1) {
4.209 + Direction::increase(_minimum);
4.210 + }
4.211 + return _data[_first[_minimum]].item;
4.212 + }
4.213 +
4.214 + /// \brief Returns the minimum priority.
4.215 + ///
4.216 + /// It returns the minimum priority.
4.217 + /// \pre The heap must be nonempty.
4.218 + Prio prio() const {
4.219 + while (_first[_minimum] == -1) {
4.220 + Direction::increase(_minimum);
4.221 + }
4.222 + return _minimum;
4.223 + }
4.224 +
4.225 + /// \brief Deletes the item with minimum priority.
4.226 + ///
4.227 + /// This method deletes the item with minimum priority from the heap.
4.228 + /// \pre The heap must be non-empty.
4.229 + void pop() {
4.230 + while (_first[_minimum] == -1) {
4.231 + Direction::increase(_minimum);
4.232 + }
4.233 + int idx = _first[_minimum];
4.234 + _iim[_data[idx].item] = -2;
4.235 + unlace(idx);
4.236 + relocate_last(idx);
4.237 + }
4.238 +
4.239 + /// \brief Deletes \c i from the heap.
4.240 + ///
4.241 + /// This method deletes item \c i from the heap, if \c i was
4.242 + /// already stored in the heap.
4.243 + /// \param i The item to erase.
4.244 + void erase(const Item &i) {
4.245 + int idx = _iim[i];
4.246 + _iim[_data[idx].item] = -2;
4.247 + unlace(idx);
4.248 + relocate_last(idx);
4.249 + }
4.250 +
4.251 +
4.252 + /// \brief Returns the priority of \c i.
4.253 + ///
4.254 + /// This function returns the priority of item \c i.
4.255 + /// \pre \c i must be in the heap.
4.256 + /// \param i The item.
4.257 + Prio operator[](const Item &i) const {
4.258 + int idx = _iim[i];
4.259 + return _data[idx].value;
4.260 + }
4.261 +
4.262 + /// \brief \c i gets to the heap with priority \c p independently
4.263 + /// if \c i was already there.
4.264 + ///
4.265 + /// This method calls \ref push(\c i, \c p) if \c i is not stored
4.266 + /// in the heap and sets the priority of \c i to \c p otherwise.
4.267 + /// \param i The item.
4.268 + /// \param p The priority.
4.269 + void set(const Item &i, const Prio &p) {
4.270 + int idx = _iim[i];
4.271 + if (idx < 0) {
4.272 + push(i, p);
4.273 + } else if (Direction::less(p, _data[idx].value)) {
4.274 + decrease(i, p);
4.275 + } else {
4.276 + increase(i, p);
4.277 + }
4.278 + }
4.279 +
4.280 + /// \brief Decreases the priority of \c i to \c p.
4.281 + ///
4.282 + /// This method decreases the priority of item \c i to \c p.
4.283 + /// \pre \c i must be stored in the heap with priority at least \c
4.284 + /// p relative to \c Compare.
4.285 + /// \param i The item.
4.286 + /// \param p The priority.
4.287 + void decrease(const Item &i, const Prio &p) {
4.288 + int idx = _iim[i];
4.289 + unlace(idx);
4.290 + _data[idx].value = p;
4.291 + if (Direction::less(p, _minimum)) {
4.292 + _minimum = p;
4.293 + }
4.294 + lace(idx);
4.295 + }
4.296 +
4.297 + /// \brief Increases the priority of \c i to \c p.
4.298 + ///
4.299 + /// This method sets the priority of item \c i to \c p.
4.300 + /// \pre \c i must be stored in the heap with priority at most \c
4.301 + /// p relative to \c Compare.
4.302 + /// \param i The item.
4.303 + /// \param p The priority.
4.304 + void increase(const Item &i, const Prio &p) {
4.305 + int idx = _iim[i];
4.306 + unlace(idx);
4.307 + _data[idx].value = p;
4.308 + lace(idx);
4.309 + }
4.310 +
4.311 + /// \brief Returns if \c item is in, has already been in, or has
4.312 + /// never been in the heap.
4.313 + ///
4.314 + /// This method returns PRE_HEAP if \c item has never been in the
4.315 + /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
4.316 + /// otherwise. In the latter case it is possible that \c item will
4.317 + /// get back to the heap again.
4.318 + /// \param i The item.
4.319 + State state(const Item &i) const {
4.320 + int idx = _iim[i];
4.321 + if (idx >= 0) idx = 0;
4.322 + return State(idx);
4.323 + }
4.324 +
4.325 + /// \brief Sets the state of the \c item in the heap.
4.326 + ///
4.327 + /// Sets the state of the \c item in the heap. It can be used to
4.328 + /// manually clear the heap when it is important to achive the
4.329 + /// better time complexity.
4.330 + /// \param i The item.
4.331 + /// \param st The state. It should not be \c IN_HEAP.
4.332 + void state(const Item& i, State st) {
4.333 + switch (st) {
4.334 + case POST_HEAP:
4.335 + case PRE_HEAP:
4.336 + if (state(i) == IN_HEAP) {
4.337 + erase(i);
4.338 + }
4.339 + _iim[i] = st;
4.340 + break;
4.341 + case IN_HEAP:
4.342 + break;
4.343 + }
4.344 + }
4.345 +
4.346 + private:
4.347 +
4.348 + struct BucketItem {
4.349 + BucketItem(const Item& _item, int _value)
4.350 + : item(_item), value(_value) {}
4.351 +
4.352 + Item item;
4.353 + int value;
4.354 +
4.355 + int prev, next;
4.356 + };
4.357 +
4.358 + ItemIntMap& _iim;
4.359 + std::vector<int> _first;
4.360 + std::vector<BucketItem> _data;
4.361 + mutable int _minimum;
4.362 +
4.363 + }; // class BucketHeap
4.364 +
4.365 + /// \ingroup auxdat
4.366 + ///
4.367 + /// \brief A Simplified Bucket Heap implementation.
4.368 + ///
4.369 + /// This class implements a simplified \e bucket \e heap data
4.370 + /// structure. It does not provide some functionality but it faster
4.371 + /// and simplier data structure than the BucketHeap. The main
4.372 + /// difference is that the BucketHeap stores for every key a double
4.373 + /// linked list while this class stores just simple lists. In the
4.374 + /// other way it does not support erasing each elements just the
4.375 + /// minimal and it does not supports key increasing, decreasing.
4.376 + ///
4.377 + /// \param IM A read and write Item int map, used internally
4.378 + /// to handle the cross references.
4.379 + /// \param MIN If the given parameter is false then instead of the
4.380 + /// minimum value the maximum can be retrivied with the top() and
4.381 + /// prio() member functions.
4.382 + ///
4.383 + /// \sa BucketHeap
4.384 + template <typename IM, bool MIN = true >
4.385 + class SimpleBucketHeap {
4.386 +
4.387 + public:
4.388 + typedef typename IM::Key Item;
4.389 + typedef int Prio;
4.390 + typedef std::pair<Item, Prio> Pair;
4.391 + typedef IM ItemIntMap;
4.392 +
4.393 + private:
4.394 +
4.395 + typedef _bucket_heap_bits::DirectionTraits<MIN> Direction;
4.396 +
4.397 + public:
4.398 +
4.399 + /// \brief Type to represent the items states.
4.400 + ///
4.401 + /// Each Item element have a state associated to it. It may be "in heap",
4.402 + /// "pre heap" or "post heap". The latter two are indifferent from the
4.403 + /// heap's point of view, but may be useful to the user.
4.404 + ///
4.405 + /// The item-int map must be initialized in such way that it assigns
4.406 + /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
4.407 + enum State {
4.408 + IN_HEAP = 0, ///< = 0.
4.409 + PRE_HEAP = -1, ///< = -1.
4.410 + POST_HEAP = -2 ///< = -2.
4.411 + };
4.412 +
4.413 + public:
4.414 +
4.415 + /// \brief The constructor.
4.416 + ///
4.417 + /// The constructor.
4.418 + /// \param map should be given to the constructor, since it is used
4.419 + /// internally to handle the cross references. The value of the map
4.420 + /// should be PRE_HEAP (-1) for each element.
4.421 + explicit SimpleBucketHeap(ItemIntMap &map)
4.422 + : _iim(map), _free(-1), _num(0), _minimum(0) {}
4.423 +
4.424 + /// \brief Returns the number of items stored in the heap.
4.425 + ///
4.426 + /// The number of items stored in the heap.
4.427 + int size() const { return _num; }
4.428 +
4.429 + /// \brief Checks if the heap stores no items.
4.430 + ///
4.431 + /// Returns \c true if and only if the heap stores no items.
4.432 + bool empty() const { return _num == 0; }
4.433 +
4.434 + /// \brief Make empty this heap.
4.435 + ///
4.436 + /// Make empty this heap. It does not change the cross reference
4.437 + /// map. If you want to reuse a heap what is not surely empty you
4.438 + /// should first clear the heap and after that you should set the
4.439 + /// cross reference map for each item to \c PRE_HEAP.
4.440 + void clear() {
4.441 + _data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0;
4.442 + }
4.443 +
4.444 + /// \brief Insert a pair of item and priority into the heap.
4.445 + ///
4.446 + /// Adds \c p.first to the heap with priority \c p.second.
4.447 + /// \param p The pair to insert.
4.448 + void push(const Pair& p) {
4.449 + push(p.first, p.second);
4.450 + }
4.451 +
4.452 + /// \brief Insert an item into the heap with the given priority.
4.453 + ///
4.454 + /// Adds \c i to the heap with priority \c p.
4.455 + /// \param i The item to insert.
4.456 + /// \param p The priority of the item.
4.457 + void push(const Item &i, const Prio &p) {
4.458 + int idx;
4.459 + if (_free == -1) {
4.460 + idx = _data.size();
4.461 + _data.push_back(BucketItem(i));
4.462 + } else {
4.463 + idx = _free;
4.464 + _free = _data[idx].next;
4.465 + _data[idx].item = i;
4.466 + }
4.467 + _iim[i] = idx;
4.468 + if (p >= int(_first.size())) _first.resize(p + 1, -1);
4.469 + _data[idx].next = _first[p];
4.470 + _first[p] = idx;
4.471 + if (Direction::less(p, _minimum)) {
4.472 + _minimum = p;
4.473 + }
4.474 + ++_num;
4.475 + }
4.476 +
4.477 + /// \brief Returns the item with minimum priority.
4.478 + ///
4.479 + /// This method returns the item with minimum priority.
4.480 + /// \pre The heap must be nonempty.
4.481 + Item top() const {
4.482 + while (_first[_minimum] == -1) {
4.483 + Direction::increase(_minimum);
4.484 + }
4.485 + return _data[_first[_minimum]].item;
4.486 + }
4.487 +
4.488 + /// \brief Returns the minimum priority.
4.489 + ///
4.490 + /// It returns the minimum priority.
4.491 + /// \pre The heap must be nonempty.
4.492 + Prio prio() const {
4.493 + while (_first[_minimum] == -1) {
4.494 + Direction::increase(_minimum);
4.495 + }
4.496 + return _minimum;
4.497 + }
4.498 +
4.499 + /// \brief Deletes the item with minimum priority.
4.500 + ///
4.501 + /// This method deletes the item with minimum priority from the heap.
4.502 + /// \pre The heap must be non-empty.
4.503 + void pop() {
4.504 + while (_first[_minimum] == -1) {
4.505 + Direction::increase(_minimum);
4.506 + }
4.507 + int idx = _first[_minimum];
4.508 + _iim[_data[idx].item] = -2;
4.509 + _first[_minimum] = _data[idx].next;
4.510 + _data[idx].next = _free;
4.511 + _free = idx;
4.512 + --_num;
4.513 + }
4.514 +
4.515 + /// \brief Returns the priority of \c i.
4.516 + ///
4.517 + /// This function returns the priority of item \c i.
4.518 + /// \warning This operator is not a constant time function
4.519 + /// because it scans the whole data structure to find the proper
4.520 + /// value.
4.521 + /// \pre \c i must be in the heap.
4.522 + /// \param i The item.
4.523 + Prio operator[](const Item &i) const {
4.524 + for (int k = 0; k < _first.size(); ++k) {
4.525 + int idx = _first[k];
4.526 + while (idx != -1) {
4.527 + if (_data[idx].item == i) {
4.528 + return k;
4.529 + }
4.530 + idx = _data[idx].next;
4.531 + }
4.532 + }
4.533 + return -1;
4.534 + }
4.535 +
4.536 + /// \brief Returns if \c item is in, has already been in, or has
4.537 + /// never been in the heap.
4.538 + ///
4.539 + /// This method returns PRE_HEAP if \c item has never been in the
4.540 + /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
4.541 + /// otherwise. In the latter case it is possible that \c item will
4.542 + /// get back to the heap again.
4.543 + /// \param i The item.
4.544 + State state(const Item &i) const {
4.545 + int idx = _iim[i];
4.546 + if (idx >= 0) idx = 0;
4.547 + return State(idx);
4.548 + }
4.549 +
4.550 + private:
4.551 +
4.552 + struct BucketItem {
4.553 + BucketItem(const Item& _item)
4.554 + : item(_item) {}
4.555 +
4.556 + Item item;
4.557 + int next;
4.558 + };
4.559 +
4.560 + ItemIntMap& _iim;
4.561 + std::vector<int> _first;
4.562 + std::vector<BucketItem> _data;
4.563 + int _free, _num;
4.564 + mutable int _minimum;
4.565 +
4.566 + }; // class SimpleBucketHeap
4.567 +
4.568 +}
4.569 +
4.570 +#endif
5.1 --- a/lemon/concepts/maps.h Thu Nov 05 16:01:39 2009 +0100
5.2 +++ b/lemon/concepts/maps.h Thu Dec 10 17:10:25 2009 +0100
5.3 @@ -182,7 +182,8 @@
5.4
5.5 template<typename _ReferenceMap>
5.6 struct Constraints {
5.7 - void constraints() {
5.8 + typename enable_if<typename _ReferenceMap::ReferenceMapTag, void>::type
5.9 + constraints() {
5.10 checkConcept<ReadWriteMap<K, T>, _ReferenceMap >();
5.11 ref = m[key];
5.12 m[key] = val;
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/lemon/fib_heap.h Thu Dec 10 17:10:25 2009 +0100
6.3 @@ -0,0 +1,468 @@
6.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
6.5 + *
6.6 + * This file is a part of LEMON, a generic C++ optimization library.
6.7 + *
6.8 + * Copyright (C) 2003-2009
6.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
6.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
6.11 + *
6.12 + * Permission to use, modify and distribute this software is granted
6.13 + * provided that this copyright notice appears in all copies. For
6.14 + * precise terms see the accompanying LICENSE file.
6.15 + *
6.16 + * This software is provided "AS IS" with no warranty of any kind,
6.17 + * express or implied, and with no claim as to its suitability for any
6.18 + * purpose.
6.19 + *
6.20 + */
6.21 +
6.22 +#ifndef LEMON_FIB_HEAP_H
6.23 +#define LEMON_FIB_HEAP_H
6.24 +
6.25 +///\file
6.26 +///\ingroup auxdat
6.27 +///\brief Fibonacci Heap implementation.
6.28 +
6.29 +#include <vector>
6.30 +#include <functional>
6.31 +#include <lemon/math.h>
6.32 +
6.33 +namespace lemon {
6.34 +
6.35 + /// \ingroup auxdat
6.36 + ///
6.37 + ///\brief Fibonacci Heap.
6.38 + ///
6.39 + ///This class implements the \e Fibonacci \e heap data structure. A \e heap
6.40 + ///is a data structure for storing items with specified values called \e
6.41 + ///priorities in such a way that finding the item with minimum priority is
6.42 + ///efficient. \c CMP specifies the ordering of the priorities. In a heap
6.43 + ///one can change the priority of an item, add or erase an item, etc.
6.44 + ///
6.45 + ///The methods \ref increase and \ref erase are not efficient in a Fibonacci
6.46 + ///heap. In case of many calls to these operations, it is better to use a
6.47 + ///\ref BinHeap "binary heap".
6.48 + ///
6.49 + ///\param PRIO Type of the priority of the items.
6.50 + ///\param IM A read and writable Item int map, used internally
6.51 + ///to handle the cross references.
6.52 + ///\param CMP A class for the ordering of the priorities. The
6.53 + ///default is \c std::less<PRIO>.
6.54 + ///
6.55 + ///\sa BinHeap
6.56 + ///\sa Dijkstra
6.57 +#ifdef DOXYGEN
6.58 + template <typename PRIO, typename IM, typename CMP>
6.59 +#else
6.60 + template <typename PRIO, typename IM, typename CMP = std::less<PRIO> >
6.61 +#endif
6.62 + class FibHeap {
6.63 + public:
6.64 + ///\e
6.65 + typedef IM ItemIntMap;
6.66 + ///\e
6.67 + typedef PRIO Prio;
6.68 + ///\e
6.69 + typedef typename ItemIntMap::Key Item;
6.70 + ///\e
6.71 + typedef std::pair<Item,Prio> Pair;
6.72 + ///\e
6.73 + typedef CMP Compare;
6.74 +
6.75 + private:
6.76 + class Store;
6.77 +
6.78 + std::vector<Store> _data;
6.79 + int _minimum;
6.80 + ItemIntMap &_iim;
6.81 + Compare _comp;
6.82 + int _num;
6.83 +
6.84 + public:
6.85 +
6.86 + /// \brief Type to represent the items states.
6.87 + ///
6.88 + /// Each Item element have a state associated to it. It may be "in heap",
6.89 + /// "pre heap" or "post heap". The latter two are indifferent from the
6.90 + /// heap's point of view, but may be useful to the user.
6.91 + ///
6.92 + /// The item-int map must be initialized in such way that it assigns
6.93 + /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
6.94 + enum State {
6.95 + IN_HEAP = 0, ///< = 0.
6.96 + PRE_HEAP = -1, ///< = -1.
6.97 + POST_HEAP = -2 ///< = -2.
6.98 + };
6.99 +
6.100 + /// \brief The constructor
6.101 + ///
6.102 + /// \c map should be given to the constructor, since it is
6.103 + /// used internally to handle the cross references.
6.104 + explicit FibHeap(ItemIntMap &map)
6.105 + : _minimum(0), _iim(map), _num() {}
6.106 +
6.107 + /// \brief The constructor
6.108 + ///
6.109 + /// \c map should be given to the constructor, since it is used
6.110 + /// internally to handle the cross references. \c comp is an
6.111 + /// object for ordering of the priorities.
6.112 + FibHeap(ItemIntMap &map, const Compare &comp)
6.113 + : _minimum(0), _iim(map), _comp(comp), _num() {}
6.114 +
6.115 + /// \brief The number of items stored in the heap.
6.116 + ///
6.117 + /// Returns the number of items stored in the heap.
6.118 + int size() const { return _num; }
6.119 +
6.120 + /// \brief Checks if the heap stores no items.
6.121 + ///
6.122 + /// Returns \c true if and only if the heap stores no items.
6.123 + bool empty() const { return _num==0; }
6.124 +
6.125 + /// \brief Make empty this heap.
6.126 + ///
6.127 + /// Make empty this heap. It does not change the cross reference
6.128 + /// map. If you want to reuse a heap what is not surely empty you
6.129 + /// should first clear the heap and after that you should set the
6.130 + /// cross reference map for each item to \c PRE_HEAP.
6.131 + void clear() {
6.132 + _data.clear(); _minimum = 0; _num = 0;
6.133 + }
6.134 +
6.135 + /// \brief \c item gets to the heap with priority \c value independently
6.136 + /// if \c item was already there.
6.137 + ///
6.138 + /// This method calls \ref push(\c item, \c value) if \c item is not
6.139 + /// stored in the heap and it calls \ref decrease(\c item, \c value) or
6.140 + /// \ref increase(\c item, \c value) otherwise.
6.141 + void set (const Item& item, const Prio& value) {
6.142 + int i=_iim[item];
6.143 + if ( i >= 0 && _data[i].in ) {
6.144 + if ( _comp(value, _data[i].prio) ) decrease(item, value);
6.145 + if ( _comp(_data[i].prio, value) ) increase(item, value);
6.146 + } else push(item, value);
6.147 + }
6.148 +
6.149 + /// \brief Adds \c item to the heap with priority \c value.
6.150 + ///
6.151 + /// Adds \c item to the heap with priority \c value.
6.152 + /// \pre \c item must not be stored in the heap.
6.153 + void push (const Item& item, const Prio& value) {
6.154 + int i=_iim[item];
6.155 + if ( i < 0 ) {
6.156 + int s=_data.size();
6.157 + _iim.set( item, s );
6.158 + Store st;
6.159 + st.name=item;
6.160 + _data.push_back(st);
6.161 + i=s;
6.162 + } else {
6.163 + _data[i].parent=_data[i].child=-1;
6.164 + _data[i].degree=0;
6.165 + _data[i].in=true;
6.166 + _data[i].marked=false;
6.167 + }
6.168 +
6.169 + if ( _num ) {
6.170 + _data[_data[_minimum].right_neighbor].left_neighbor=i;
6.171 + _data[i].right_neighbor=_data[_minimum].right_neighbor;
6.172 + _data[_minimum].right_neighbor=i;
6.173 + _data[i].left_neighbor=_minimum;
6.174 + if ( _comp( value, _data[_minimum].prio) ) _minimum=i;
6.175 + } else {
6.176 + _data[i].right_neighbor=_data[i].left_neighbor=i;
6.177 + _minimum=i;
6.178 + }
6.179 + _data[i].prio=value;
6.180 + ++_num;
6.181 + }
6.182 +
6.183 + /// \brief Returns the item with minimum priority relative to \c Compare.
6.184 + ///
6.185 + /// This method returns the item with minimum priority relative to \c
6.186 + /// Compare.
6.187 + /// \pre The heap must be nonempty.
6.188 + Item top() const { return _data[_minimum].name; }
6.189 +
6.190 + /// \brief Returns the minimum priority relative to \c Compare.
6.191 + ///
6.192 + /// It returns the minimum priority relative to \c Compare.
6.193 + /// \pre The heap must be nonempty.
6.194 + const Prio& prio() const { return _data[_minimum].prio; }
6.195 +
6.196 + /// \brief Returns the priority of \c item.
6.197 + ///
6.198 + /// It returns the priority of \c item.
6.199 + /// \pre \c item must be in the heap.
6.200 + const Prio& operator[](const Item& item) const {
6.201 + return _data[_iim[item]].prio;
6.202 + }
6.203 +
6.204 + /// \brief Deletes the item with minimum priority relative to \c Compare.
6.205 + ///
6.206 + /// This method deletes the item with minimum priority relative to \c
6.207 + /// Compare from the heap.
6.208 + /// \pre The heap must be non-empty.
6.209 + void pop() {
6.210 + /*The first case is that there are only one root.*/
6.211 + if ( _data[_minimum].left_neighbor==_minimum ) {
6.212 + _data[_minimum].in=false;
6.213 + if ( _data[_minimum].degree!=0 ) {
6.214 + makeroot(_data[_minimum].child);
6.215 + _minimum=_data[_minimum].child;
6.216 + balance();
6.217 + }
6.218 + } else {
6.219 + int right=_data[_minimum].right_neighbor;
6.220 + unlace(_minimum);
6.221 + _data[_minimum].in=false;
6.222 + if ( _data[_minimum].degree > 0 ) {
6.223 + int left=_data[_minimum].left_neighbor;
6.224 + int child=_data[_minimum].child;
6.225 + int last_child=_data[child].left_neighbor;
6.226 +
6.227 + makeroot(child);
6.228 +
6.229 + _data[left].right_neighbor=child;
6.230 + _data[child].left_neighbor=left;
6.231 + _data[right].left_neighbor=last_child;
6.232 + _data[last_child].right_neighbor=right;
6.233 + }
6.234 + _minimum=right;
6.235 + balance();
6.236 + } // the case where there are more roots
6.237 + --_num;
6.238 + }
6.239 +
6.240 + /// \brief Deletes \c item from the heap.
6.241 + ///
6.242 + /// This method deletes \c item from the heap, if \c item was already
6.243 + /// stored in the heap. It is quite inefficient in Fibonacci heaps.
6.244 + void erase (const Item& item) {
6.245 + int i=_iim[item];
6.246 +
6.247 + if ( i >= 0 && _data[i].in ) {
6.248 + if ( _data[i].parent!=-1 ) {
6.249 + int p=_data[i].parent;
6.250 + cut(i,p);
6.251 + cascade(p);
6.252 + }
6.253 + _minimum=i; //As if its prio would be -infinity
6.254 + pop();
6.255 + }
6.256 + }
6.257 +
6.258 + /// \brief Decreases the priority of \c item to \c value.
6.259 + ///
6.260 + /// This method decreases the priority of \c item to \c value.
6.261 + /// \pre \c item must be stored in the heap with priority at least \c
6.262 + /// value relative to \c Compare.
6.263 + void decrease (Item item, const Prio& value) {
6.264 + int i=_iim[item];
6.265 + _data[i].prio=value;
6.266 + int p=_data[i].parent;
6.267 +
6.268 + if ( p!=-1 && _comp(value, _data[p].prio) ) {
6.269 + cut(i,p);
6.270 + cascade(p);
6.271 + }
6.272 + if ( _comp(value, _data[_minimum].prio) ) _minimum=i;
6.273 + }
6.274 +
6.275 + /// \brief Increases the priority of \c item to \c value.
6.276 + ///
6.277 + /// This method sets the priority of \c item to \c value. Though
6.278 + /// there is no precondition on the priority of \c item, this
6.279 + /// method should be used only if it is indeed necessary to increase
6.280 + /// (relative to \c Compare) the priority of \c item, because this
6.281 + /// method is inefficient.
6.282 + void increase (Item item, const Prio& value) {
6.283 + erase(item);
6.284 + push(item, value);
6.285 + }
6.286 +
6.287 +
6.288 + /// \brief Returns if \c item is in, has already been in, or has never
6.289 + /// been in the heap.
6.290 + ///
6.291 + /// This method returns PRE_HEAP if \c item has never been in the
6.292 + /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
6.293 + /// otherwise. In the latter case it is possible that \c item will
6.294 + /// get back to the heap again.
6.295 + State state(const Item &item) const {
6.296 + int i=_iim[item];
6.297 + if( i>=0 ) {
6.298 + if ( _data[i].in ) i=0;
6.299 + else i=-2;
6.300 + }
6.301 + return State(i);
6.302 + }
6.303 +
6.304 + /// \brief Sets the state of the \c item in the heap.
6.305 + ///
6.306 + /// Sets the state of the \c item in the heap. It can be used to
6.307 + /// manually clear the heap when it is important to achive the
6.308 + /// better time _complexity.
6.309 + /// \param i The item.
6.310 + /// \param st The state. It should not be \c IN_HEAP.
6.311 + void state(const Item& i, State st) {
6.312 + switch (st) {
6.313 + case POST_HEAP:
6.314 + case PRE_HEAP:
6.315 + if (state(i) == IN_HEAP) {
6.316 + erase(i);
6.317 + }
6.318 + _iim[i] = st;
6.319 + break;
6.320 + case IN_HEAP:
6.321 + break;
6.322 + }
6.323 + }
6.324 +
6.325 + private:
6.326 +
6.327 + void balance() {
6.328 +
6.329 + int maxdeg=int( std::floor( 2.08*log(double(_data.size()))))+1;
6.330 +
6.331 + std::vector<int> A(maxdeg,-1);
6.332 +
6.333 + /*
6.334 + *Recall that now minimum does not point to the minimum prio element.
6.335 + *We set minimum to this during balance().
6.336 + */
6.337 + int anchor=_data[_minimum].left_neighbor;
6.338 + int next=_minimum;
6.339 + bool end=false;
6.340 +
6.341 + do {
6.342 + int active=next;
6.343 + if ( anchor==active ) end=true;
6.344 + int d=_data[active].degree;
6.345 + next=_data[active].right_neighbor;
6.346 +
6.347 + while (A[d]!=-1) {
6.348 + if( _comp(_data[active].prio, _data[A[d]].prio) ) {
6.349 + fuse(active,A[d]);
6.350 + } else {
6.351 + fuse(A[d],active);
6.352 + active=A[d];
6.353 + }
6.354 + A[d]=-1;
6.355 + ++d;
6.356 + }
6.357 + A[d]=active;
6.358 + } while ( !end );
6.359 +
6.360 +
6.361 + while ( _data[_minimum].parent >=0 )
6.362 + _minimum=_data[_minimum].parent;
6.363 + int s=_minimum;
6.364 + int m=_minimum;
6.365 + do {
6.366 + if ( _comp(_data[s].prio, _data[_minimum].prio) ) _minimum=s;
6.367 + s=_data[s].right_neighbor;
6.368 + } while ( s != m );
6.369 + }
6.370 +
6.371 + void makeroot(int c) {
6.372 + int s=c;
6.373 + do {
6.374 + _data[s].parent=-1;
6.375 + s=_data[s].right_neighbor;
6.376 + } while ( s != c );
6.377 + }
6.378 +
6.379 + void cut(int a, int b) {
6.380 + /*
6.381 + *Replacing a from the children of b.
6.382 + */
6.383 + --_data[b].degree;
6.384 +
6.385 + if ( _data[b].degree !=0 ) {
6.386 + int child=_data[b].child;
6.387 + if ( child==a )
6.388 + _data[b].child=_data[child].right_neighbor;
6.389 + unlace(a);
6.390 + }
6.391 +
6.392 +
6.393 + /*Lacing a to the roots.*/
6.394 + int right=_data[_minimum].right_neighbor;
6.395 + _data[_minimum].right_neighbor=a;
6.396 + _data[a].left_neighbor=_minimum;
6.397 + _data[a].right_neighbor=right;
6.398 + _data[right].left_neighbor=a;
6.399 +
6.400 + _data[a].parent=-1;
6.401 + _data[a].marked=false;
6.402 + }
6.403 +
6.404 + void cascade(int a) {
6.405 + if ( _data[a].parent!=-1 ) {
6.406 + int p=_data[a].parent;
6.407 +
6.408 + if ( _data[a].marked==false ) _data[a].marked=true;
6.409 + else {
6.410 + cut(a,p);
6.411 + cascade(p);
6.412 + }
6.413 + }
6.414 + }
6.415 +
6.416 + void fuse(int a, int b) {
6.417 + unlace(b);
6.418 +
6.419 + /*Lacing b under a.*/
6.420 + _data[b].parent=a;
6.421 +
6.422 + if (_data[a].degree==0) {
6.423 + _data[b].left_neighbor=b;
6.424 + _data[b].right_neighbor=b;
6.425 + _data[a].child=b;
6.426 + } else {
6.427 + int child=_data[a].child;
6.428 + int last_child=_data[child].left_neighbor;
6.429 + _data[child].left_neighbor=b;
6.430 + _data[b].right_neighbor=child;
6.431 + _data[last_child].right_neighbor=b;
6.432 + _data[b].left_neighbor=last_child;
6.433 + }
6.434 +
6.435 + ++_data[a].degree;
6.436 +
6.437 + _data[b].marked=false;
6.438 + }
6.439 +
6.440 + /*
6.441 + *It is invoked only if a has siblings.
6.442 + */
6.443 + void unlace(int a) {
6.444 + int leftn=_data[a].left_neighbor;
6.445 + int rightn=_data[a].right_neighbor;
6.446 + _data[leftn].right_neighbor=rightn;
6.447 + _data[rightn].left_neighbor=leftn;
6.448 + }
6.449 +
6.450 +
6.451 + class Store {
6.452 + friend class FibHeap;
6.453 +
6.454 + Item name;
6.455 + int parent;
6.456 + int left_neighbor;
6.457 + int right_neighbor;
6.458 + int child;
6.459 + int degree;
6.460 + bool marked;
6.461 + bool in;
6.462 + Prio prio;
6.463 +
6.464 + Store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
6.465 + };
6.466 + };
6.467 +
6.468 +} //namespace lemon
6.469 +
6.470 +#endif //LEMON_FIB_HEAP_H
6.471 +
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
7.2 +++ b/lemon/radix_heap.h Thu Dec 10 17:10:25 2009 +0100
7.3 @@ -0,0 +1,433 @@
7.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
7.5 + *
7.6 + * This file is a part of LEMON, a generic C++ optimization library.
7.7 + *
7.8 + * Copyright (C) 2003-2009
7.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
7.11 + *
7.12 + * Permission to use, modify and distribute this software is granted
7.13 + * provided that this copyright notice appears in all copies. For
7.14 + * precise terms see the accompanying LICENSE file.
7.15 + *
7.16 + * This software is provided "AS IS" with no warranty of any kind,
7.17 + * express or implied, and with no claim as to its suitability for any
7.18 + * purpose.
7.19 + *
7.20 + */
7.21 +
7.22 +#ifndef LEMON_RADIX_HEAP_H
7.23 +#define LEMON_RADIX_HEAP_H
7.24 +
7.25 +///\ingroup auxdat
7.26 +///\file
7.27 +///\brief Radix Heap implementation.
7.28 +
7.29 +#include <vector>
7.30 +#include <lemon/error.h>
7.31 +
7.32 +namespace lemon {
7.33 +
7.34 +
7.35 + /// \ingroup auxdata
7.36 + ///
7.37 + /// \brief A Radix Heap implementation.
7.38 + ///
7.39 + /// This class implements the \e radix \e heap data structure. A \e heap
7.40 + /// is a data structure for storing items with specified values called \e
7.41 + /// priorities in such a way that finding the item with minimum priority is
7.42 + /// efficient. This heap type can store only items with \e int priority.
7.43 + /// In a heap one can change the priority of an item, add or erase an
7.44 + /// item, but the priority cannot be decreased under the last removed
7.45 + /// item's priority.
7.46 + ///
7.47 + /// \param IM A read and writable Item int map, used internally
7.48 + /// to handle the cross references.
7.49 + ///
7.50 + /// \see BinHeap
7.51 + /// \see Dijkstra
7.52 + template <typename IM>
7.53 + class RadixHeap {
7.54 +
7.55 + public:
7.56 + typedef typename IM::Key Item;
7.57 + typedef int Prio;
7.58 + typedef IM ItemIntMap;
7.59 +
7.60 + /// \brief Exception thrown by RadixHeap.
7.61 + ///
7.62 + /// This Exception is thrown when a smaller priority
7.63 + /// is inserted into the \e RadixHeap then the last time erased.
7.64 + /// \see RadixHeap
7.65 +
7.66 + class UnderFlowPriorityError : public Exception {
7.67 + public:
7.68 + virtual const char* what() const throw() {
7.69 + return "lemon::RadixHeap::UnderFlowPriorityError";
7.70 + }
7.71 + };
7.72 +
7.73 + /// \brief Type to represent the items states.
7.74 + ///
7.75 + /// Each Item element have a state associated to it. It may be "in heap",
7.76 + /// "pre heap" or "post heap". The latter two are indifferent from the
7.77 + /// heap's point of view, but may be useful to the user.
7.78 + ///
7.79 + /// The ItemIntMap \e should be initialized in such way that it maps
7.80 + /// PRE_HEAP (-1) to any element to be put in the heap...
7.81 + enum State {
7.82 + IN_HEAP = 0,
7.83 + PRE_HEAP = -1,
7.84 + POST_HEAP = -2
7.85 + };
7.86 +
7.87 + private:
7.88 +
7.89 + struct RadixItem {
7.90 + int prev, next, box;
7.91 + Item item;
7.92 + int prio;
7.93 + RadixItem(Item _item, int _prio) : item(_item), prio(_prio) {}
7.94 + };
7.95 +
7.96 + struct RadixBox {
7.97 + int first;
7.98 + int min, size;
7.99 + RadixBox(int _min, int _size) : first(-1), min(_min), size(_size) {}
7.100 + };
7.101 +
7.102 + std::vector<RadixItem> data;
7.103 + std::vector<RadixBox> boxes;
7.104 +
7.105 + ItemIntMap &_iim;
7.106 +
7.107 +
7.108 + public:
7.109 + /// \brief The constructor.
7.110 + ///
7.111 + /// The constructor.
7.112 + ///
7.113 + /// \param map It should be given to the constructor, since it is used
7.114 + /// internally to handle the cross references. The value of the map
7.115 + /// should be PRE_HEAP (-1) for each element.
7.116 + ///
7.117 + /// \param minimal The initial minimal value of the heap.
7.118 + /// \param capacity It determines the initial capacity of the heap.
7.119 + RadixHeap(ItemIntMap &map, int minimal = 0, int capacity = 0)
7.120 + : _iim(map) {
7.121 + boxes.push_back(RadixBox(minimal, 1));
7.122 + boxes.push_back(RadixBox(minimal + 1, 1));
7.123 + while (lower(boxes.size() - 1, capacity + minimal - 1)) {
7.124 + extend();
7.125 + }
7.126 + }
7.127 +
7.128 + /// The number of items stored in the heap.
7.129 + ///
7.130 + /// \brief Returns the number of items stored in the heap.
7.131 + int size() const { return data.size(); }
7.132 + /// \brief Checks if the heap stores no items.
7.133 + ///
7.134 + /// Returns \c true if and only if the heap stores no items.
7.135 + bool empty() const { return data.empty(); }
7.136 +
7.137 + /// \brief Make empty this heap.
7.138 + ///
7.139 + /// Make empty this heap. It does not change the cross reference
7.140 + /// map. If you want to reuse a heap what is not surely empty you
7.141 + /// should first clear the heap and after that you should set the
7.142 + /// cross reference map for each item to \c PRE_HEAP.
7.143 + void clear(int minimal = 0, int capacity = 0) {
7.144 + data.clear(); boxes.clear();
7.145 + boxes.push_back(RadixBox(minimal, 1));
7.146 + boxes.push_back(RadixBox(minimal + 1, 1));
7.147 + while (lower(boxes.size() - 1, capacity + minimal - 1)) {
7.148 + extend();
7.149 + }
7.150 + }
7.151 +
7.152 + private:
7.153 +
7.154 + bool upper(int box, Prio pr) {
7.155 + return pr < boxes[box].min;
7.156 + }
7.157 +
7.158 + bool lower(int box, Prio pr) {
7.159 + return pr >= boxes[box].min + boxes[box].size;
7.160 + }
7.161 +
7.162 + /// \brief Remove item from the box list.
7.163 + void remove(int index) {
7.164 + if (data[index].prev >= 0) {
7.165 + data[data[index].prev].next = data[index].next;
7.166 + } else {
7.167 + boxes[data[index].box].first = data[index].next;
7.168 + }
7.169 + if (data[index].next >= 0) {
7.170 + data[data[index].next].prev = data[index].prev;
7.171 + }
7.172 + }
7.173 +
7.174 + /// \brief Insert item into the box list.
7.175 + void insert(int box, int index) {
7.176 + if (boxes[box].first == -1) {
7.177 + boxes[box].first = index;
7.178 + data[index].next = data[index].prev = -1;
7.179 + } else {
7.180 + data[index].next = boxes[box].first;
7.181 + data[boxes[box].first].prev = index;
7.182 + data[index].prev = -1;
7.183 + boxes[box].first = index;
7.184 + }
7.185 + data[index].box = box;
7.186 + }
7.187 +
7.188 + /// \brief Add a new box to the box list.
7.189 + void extend() {
7.190 + int min = boxes.back().min + boxes.back().size;
7.191 + int bs = 2 * boxes.back().size;
7.192 + boxes.push_back(RadixBox(min, bs));
7.193 + }
7.194 +
7.195 + /// \brief Move an item up into the proper box.
7.196 + void bubble_up(int index) {
7.197 + if (!lower(data[index].box, data[index].prio)) return;
7.198 + remove(index);
7.199 + int box = findUp(data[index].box, data[index].prio);
7.200 + insert(box, index);
7.201 + }
7.202 +
7.203 + /// \brief Find up the proper box for the item with the given prio.
7.204 + int findUp(int start, int pr) {
7.205 + while (lower(start, pr)) {
7.206 + if (++start == int(boxes.size())) {
7.207 + extend();
7.208 + }
7.209 + }
7.210 + return start;
7.211 + }
7.212 +
7.213 + /// \brief Move an item down into the proper box.
7.214 + void bubble_down(int index) {
7.215 + if (!upper(data[index].box, data[index].prio)) return;
7.216 + remove(index);
7.217 + int box = findDown(data[index].box, data[index].prio);
7.218 + insert(box, index);
7.219 + }
7.220 +
7.221 + /// \brief Find up the proper box for the item with the given prio.
7.222 + int findDown(int start, int pr) {
7.223 + while (upper(start, pr)) {
7.224 + if (--start < 0) throw UnderFlowPriorityError();
7.225 + }
7.226 + return start;
7.227 + }
7.228 +
7.229 + /// \brief Find the first not empty box.
7.230 + int findFirst() {
7.231 + int first = 0;
7.232 + while (boxes[first].first == -1) ++first;
7.233 + return first;
7.234 + }
7.235 +
7.236 + /// \brief Gives back the minimal prio of the box.
7.237 + int minValue(int box) {
7.238 + int min = data[boxes[box].first].prio;
7.239 + for (int k = boxes[box].first; k != -1; k = data[k].next) {
7.240 + if (data[k].prio < min) min = data[k].prio;
7.241 + }
7.242 + return min;
7.243 + }
7.244 +
7.245 + /// \brief Rearrange the items of the heap and makes the
7.246 + /// first box not empty.
7.247 + void moveDown() {
7.248 + int box = findFirst();
7.249 + if (box == 0) return;
7.250 + int min = minValue(box);
7.251 + for (int i = 0; i <= box; ++i) {
7.252 + boxes[i].min = min;
7.253 + min += boxes[i].size;
7.254 + }
7.255 + int curr = boxes[box].first, next;
7.256 + while (curr != -1) {
7.257 + next = data[curr].next;
7.258 + bubble_down(curr);
7.259 + curr = next;
7.260 + }
7.261 + }
7.262 +
7.263 + void relocate_last(int index) {
7.264 + if (index != int(data.size()) - 1) {
7.265 + data[index] = data.back();
7.266 + if (data[index].prev != -1) {
7.267 + data[data[index].prev].next = index;
7.268 + } else {
7.269 + boxes[data[index].box].first = index;
7.270 + }
7.271 + if (data[index].next != -1) {
7.272 + data[data[index].next].prev = index;
7.273 + }
7.274 + _iim[data[index].item] = index;
7.275 + }
7.276 + data.pop_back();
7.277 + }
7.278 +
7.279 + public:
7.280 +
7.281 + /// \brief Insert an item into the heap with the given priority.
7.282 + ///
7.283 + /// Adds \c i to the heap with priority \c p.
7.284 + /// \param i The item to insert.
7.285 + /// \param p The priority of the item.
7.286 + void push(const Item &i, const Prio &p) {
7.287 + int n = data.size();
7.288 + _iim.set(i, n);
7.289 + data.push_back(RadixItem(i, p));
7.290 + while (lower(boxes.size() - 1, p)) {
7.291 + extend();
7.292 + }
7.293 + int box = findDown(boxes.size() - 1, p);
7.294 + insert(box, n);
7.295 + }
7.296 +
7.297 + /// \brief Returns the item with minimum priority.
7.298 + ///
7.299 + /// This method returns the item with minimum priority.
7.300 + /// \pre The heap must be nonempty.
7.301 + Item top() const {
7.302 + const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
7.303 + return data[boxes[0].first].item;
7.304 + }
7.305 +
7.306 + /// \brief Returns the minimum priority.
7.307 + ///
7.308 + /// It returns the minimum priority.
7.309 + /// \pre The heap must be nonempty.
7.310 + Prio prio() const {
7.311 + const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
7.312 + return data[boxes[0].first].prio;
7.313 + }
7.314 +
7.315 + /// \brief Deletes the item with minimum priority.
7.316 + ///
7.317 + /// This method deletes the item with minimum priority.
7.318 + /// \pre The heap must be non-empty.
7.319 + void pop() {
7.320 + moveDown();
7.321 + int index = boxes[0].first;
7.322 + _iim[data[index].item] = POST_HEAP;
7.323 + remove(index);
7.324 + relocate_last(index);
7.325 + }
7.326 +
7.327 + /// \brief Deletes \c i from the heap.
7.328 + ///
7.329 + /// This method deletes item \c i from the heap, if \c i was
7.330 + /// already stored in the heap.
7.331 + /// \param i The item to erase.
7.332 + void erase(const Item &i) {
7.333 + int index = _iim[i];
7.334 + _iim[i] = POST_HEAP;
7.335 + remove(index);
7.336 + relocate_last(index);
7.337 + }
7.338 +
7.339 + /// \brief Returns the priority of \c i.
7.340 + ///
7.341 + /// This function returns the priority of item \c i.
7.342 + /// \pre \c i must be in the heap.
7.343 + /// \param i The item.
7.344 + Prio operator[](const Item &i) const {
7.345 + int idx = _iim[i];
7.346 + return data[idx].prio;
7.347 + }
7.348 +
7.349 + /// \brief \c i gets to the heap with priority \c p independently
7.350 + /// if \c i was already there.
7.351 + ///
7.352 + /// This method calls \ref push(\c i, \c p) if \c i is not stored
7.353 + /// in the heap and sets the priority of \c i to \c p otherwise.
7.354 + /// It may throw an \e UnderFlowPriorityException.
7.355 + /// \param i The item.
7.356 + /// \param p The priority.
7.357 + void set(const Item &i, const Prio &p) {
7.358 + int idx = _iim[i];
7.359 + if( idx < 0 ) {
7.360 + push(i, p);
7.361 + }
7.362 + else if( p >= data[idx].prio ) {
7.363 + data[idx].prio = p;
7.364 + bubble_up(idx);
7.365 + } else {
7.366 + data[idx].prio = p;
7.367 + bubble_down(idx);
7.368 + }
7.369 + }
7.370 +
7.371 +
7.372 + /// \brief Decreases the priority of \c i to \c p.
7.373 + ///
7.374 + /// This method decreases the priority of item \c i to \c p.
7.375 + /// \pre \c i must be stored in the heap with priority at least \c p, and
7.376 + /// \c should be greater or equal to the last removed item's priority.
7.377 + /// \param i The item.
7.378 + /// \param p The priority.
7.379 + void decrease(const Item &i, const Prio &p) {
7.380 + int idx = _iim[i];
7.381 + data[idx].prio = p;
7.382 + bubble_down(idx);
7.383 + }
7.384 +
7.385 + /// \brief Increases the priority of \c i to \c p.
7.386 + ///
7.387 + /// This method sets the priority of item \c i to \c p.
7.388 + /// \pre \c i must be stored in the heap with priority at most \c p
7.389 + /// \param i The item.
7.390 + /// \param p The priority.
7.391 + void increase(const Item &i, const Prio &p) {
7.392 + int idx = _iim[i];
7.393 + data[idx].prio = p;
7.394 + bubble_up(idx);
7.395 + }
7.396 +
7.397 + /// \brief Returns if \c item is in, has already been in, or has
7.398 + /// never been in the heap.
7.399 + ///
7.400 + /// This method returns PRE_HEAP if \c item has never been in the
7.401 + /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
7.402 + /// otherwise. In the latter case it is possible that \c item will
7.403 + /// get back to the heap again.
7.404 + /// \param i The item.
7.405 + State state(const Item &i) const {
7.406 + int s = _iim[i];
7.407 + if( s >= 0 ) s = 0;
7.408 + return State(s);
7.409 + }
7.410 +
7.411 + /// \brief Sets the state of the \c item in the heap.
7.412 + ///
7.413 + /// Sets the state of the \c item in the heap. It can be used to
7.414 + /// manually clear the heap when it is important to achive the
7.415 + /// better time complexity.
7.416 + /// \param i The item.
7.417 + /// \param st The state. It should not be \c IN_HEAP.
7.418 + void state(const Item& i, State st) {
7.419 + switch (st) {
7.420 + case POST_HEAP:
7.421 + case PRE_HEAP:
7.422 + if (state(i) == IN_HEAP) {
7.423 + erase(i);
7.424 + }
7.425 + _iim[i] = st;
7.426 + break;
7.427 + case IN_HEAP:
7.428 + break;
7.429 + }
7.430 + }
7.431 +
7.432 + }; // class RadixHeap
7.433 +
7.434 +} // namespace lemon
7.435 +
7.436 +#endif // LEMON_RADIX_HEAP_H
8.1 --- a/test/heap_test.cc Thu Nov 05 16:01:39 2009 +0100
8.2 +++ b/test/heap_test.cc Thu Dec 10 17:10:25 2009 +0100
8.3 @@ -31,6 +31,9 @@
8.4 #include <lemon/maps.h>
8.5
8.6 #include <lemon/bin_heap.h>
8.7 +#include <lemon/fib_heap.h>
8.8 +#include <lemon/radix_heap.h>
8.9 +#include <lemon/bucket_heap.h>
8.10
8.11 #include "test_tools.h"
8.12
8.13 @@ -183,5 +186,39 @@
8.14 dijkstraHeapTest<NodeHeap>(digraph, length, source);
8.15 }
8.16
8.17 + {
8.18 + typedef FibHeap<Prio, ItemIntMap> IntHeap;
8.19 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
8.20 + heapSortTest<IntHeap>();
8.21 + heapIncreaseTest<IntHeap>();
8.22 +
8.23 + typedef FibHeap<Prio, IntNodeMap > NodeHeap;
8.24 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
8.25 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
8.26 + }
8.27 +
8.28 + {
8.29 + typedef RadixHeap<ItemIntMap> IntHeap;
8.30 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
8.31 + heapSortTest<IntHeap>();
8.32 + heapIncreaseTest<IntHeap>();
8.33 +
8.34 + typedef RadixHeap<IntNodeMap > NodeHeap;
8.35 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
8.36 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
8.37 + }
8.38 +
8.39 + {
8.40 + typedef BucketHeap<ItemIntMap> IntHeap;
8.41 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
8.42 + heapSortTest<IntHeap>();
8.43 + heapIncreaseTest<IntHeap>();
8.44 +
8.45 + typedef BucketHeap<IntNodeMap > NodeHeap;
8.46 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
8.47 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
8.48 + }
8.49 +
8.50 +
8.51 return 0;
8.52 }