1.1 --- a/lemon/Makefile.am Mon Mar 14 08:56:54 2011 +0100
1.2 +++ b/lemon/Makefile.am Fri Apr 15 09:26:09 2011 +0200
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 @@ -99,6 +101,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 Mon Mar 14 08:56:54 2011 +0100
2.2 +++ b/lemon/bin_heap.h Fri Apr 15 09:26:09 2011 +0200
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 Mon Mar 14 08:56:54 2011 +0100
3.2 +++ b/lemon/bits/map_extender.h Fri Apr 15 09:26:09 2011 +0200
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 Fri Apr 15 09:26:09 2011 +0200
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 Mon Mar 14 08:56:54 2011 +0100
5.2 +++ b/lemon/concepts/maps.h Fri Apr 15 09:26:09 2011 +0200
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 Fri Apr 15 09:26:09 2011 +0200
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 --- a/lemon/glpk.h Mon Mar 14 08:56:54 2011 +0100
7.2 +++ b/lemon/glpk.h Fri Apr 15 09:26:09 2011 +0200
7.3 @@ -25,16 +25,28 @@
7.4
7.5 #include <lemon/lp_base.h>
7.6
7.7 -// forward declaration
7.8 -#if !defined _GLP_PROB && !defined GLP_PROB
7.9 -#define _GLP_PROB
7.10 -#define GLP_PROB
7.11 -typedef struct { double _opaque_prob; } glp_prob;
7.12 -/* LP/MIP problem object */
7.13 -#endif
7.14 -
7.15 namespace lemon {
7.16
7.17 + namespace _solver_bits {
7.18 + class VoidPtr {
7.19 + private:
7.20 + void *_ptr;
7.21 + public:
7.22 + VoidPtr() : _ptr(0) {}
7.23 +
7.24 + template <typename T>
7.25 + VoidPtr(T* ptr) : _ptr(reinterpret_cast<void*>(ptr)) {}
7.26 +
7.27 + template <typename T>
7.28 + VoidPtr& operator=(T* ptr) {
7.29 + _ptr = reinterpret_cast<void*>(ptr);
7.30 + return *this;
7.31 + }
7.32 +
7.33 + template <typename T>
7.34 + operator T*() const { return reinterpret_cast<T*>(_ptr); }
7.35 + };
7.36 + }
7.37
7.38 /// \brief Base interface for the GLPK LP and MIP solver
7.39 ///
7.40 @@ -43,8 +55,7 @@
7.41 class GlpkBase : virtual public LpBase {
7.42 protected:
7.43
7.44 - typedef glp_prob LPX;
7.45 - glp_prob* lp;
7.46 + _solver_bits::VoidPtr lp;
7.47
7.48 GlpkBase();
7.49 GlpkBase(const GlpkBase&);
7.50 @@ -122,9 +133,9 @@
7.51 public:
7.52
7.53 ///Pointer to the underlying GLPK data structure.
7.54 - LPX *lpx() {return lp;}
7.55 + _solver_bits::VoidPtr lpx() {return lp;}
7.56 ///Const pointer to the underlying GLPK data structure.
7.57 - const LPX *lpx() const {return lp;}
7.58 + _solver_bits::VoidPtr lpx() const {return lp;}
7.59
7.60 ///Returns the constraint identifier understood by GLPK.
7.61 int lpxRow(Row r) const { return rows(id(r)); }
8.1 --- a/lemon/path.h Mon Mar 14 08:56:54 2011 +0100
8.2 +++ b/lemon/path.h Fri Apr 15 09:26:09 2011 +0200
8.3 @@ -70,7 +70,7 @@
8.4 /// It simply makes a copy of the given path.
8.5 template <typename CPath>
8.6 Path(const CPath& cpath) {
8.7 - copyPath(*this, cpath);
8.8 + pathCopy(cpath, *this);
8.9 }
8.10
8.11 /// \brief Template copy assignment
8.12 @@ -78,7 +78,7 @@
8.13 /// This operator makes a copy of a path of any other type.
8.14 template <typename CPath>
8.15 Path& operator=(const CPath& cpath) {
8.16 - copyPath(*this, cpath);
8.17 + pathCopy(cpath, *this);
8.18 return *this;
8.19 }
8.20
8.21 @@ -258,7 +258,7 @@
8.22 /// makes a copy of the given path.
8.23 template <typename CPath>
8.24 SimplePath(const CPath& cpath) {
8.25 - copyPath(*this, cpath);
8.26 + pathCopy(cpath, *this);
8.27 }
8.28
8.29 /// \brief Template copy assignment
8.30 @@ -267,7 +267,7 @@
8.31 /// makes a copy of the given path.
8.32 template <typename CPath>
8.33 SimplePath& operator=(const CPath& cpath) {
8.34 - copyPath(*this, cpath);
8.35 + pathCopy(cpath, *this);
8.36 return *this;
8.37 }
8.38
8.39 @@ -437,7 +437,7 @@
8.40 /// makes a copy of the given path.
8.41 template <typename CPath>
8.42 ListPath(const CPath& cpath) : first(0), last(0) {
8.43 - copyPath(*this, cpath);
8.44 + pathCopy(cpath, *this);
8.45 }
8.46
8.47 /// \brief Destructor of the path
8.48 @@ -453,7 +453,7 @@
8.49 /// makes a copy of the given path.
8.50 template <typename CPath>
8.51 ListPath& operator=(const CPath& cpath) {
8.52 - copyPath(*this, cpath);
8.53 + pathCopy(cpath, *this);
8.54 return *this;
8.55 }
8.56
8.57 @@ -763,7 +763,7 @@
8.58 /// This path can be initialized from any other path type.
8.59 template <typename CPath>
8.60 StaticPath(const CPath& cpath) : arcs(0) {
8.61 - copyPath(*this, cpath);
8.62 + pathCopy(cpath, *this);
8.63 }
8.64
8.65 /// \brief Destructor of the path
8.66 @@ -779,7 +779,7 @@
8.67 /// makes a copy of the given path.
8.68 template <typename CPath>
8.69 StaticPath& operator=(const CPath& cpath) {
8.70 - copyPath(*this, cpath);
8.71 + pathCopy(cpath, *this);
8.72 return *this;
8.73 }
8.74
8.75 @@ -928,57 +928,57 @@
8.76 static const bool value = true;
8.77 };
8.78
8.79 - template <typename Target, typename Source,
8.80 - bool buildEnable = BuildTagIndicator<Target>::value>
8.81 + template <typename From, typename To,
8.82 + bool buildEnable = BuildTagIndicator<To>::value>
8.83 struct PathCopySelectorForward {
8.84 - static void copy(Target& target, const Source& source) {
8.85 - target.clear();
8.86 - for (typename Source::ArcIt it(source); it != INVALID; ++it) {
8.87 - target.addBack(it);
8.88 + static void copy(const From& from, To& to) {
8.89 + to.clear();
8.90 + for (typename From::ArcIt it(from); it != INVALID; ++it) {
8.91 + to.addBack(it);
8.92 }
8.93 }
8.94 };
8.95
8.96 - template <typename Target, typename Source>
8.97 - struct PathCopySelectorForward<Target, Source, true> {
8.98 - static void copy(Target& target, const Source& source) {
8.99 - target.clear();
8.100 - target.build(source);
8.101 + template <typename From, typename To>
8.102 + struct PathCopySelectorForward<From, To, true> {
8.103 + static void copy(const From& from, To& to) {
8.104 + to.clear();
8.105 + to.build(from);
8.106 }
8.107 };
8.108
8.109 - template <typename Target, typename Source,
8.110 - bool buildEnable = BuildTagIndicator<Target>::value>
8.111 + template <typename From, typename To,
8.112 + bool buildEnable = BuildTagIndicator<To>::value>
8.113 struct PathCopySelectorBackward {
8.114 - static void copy(Target& target, const Source& source) {
8.115 - target.clear();
8.116 - for (typename Source::RevArcIt it(source); it != INVALID; ++it) {
8.117 - target.addFront(it);
8.118 + static void copy(const From& from, To& to) {
8.119 + to.clear();
8.120 + for (typename From::RevArcIt it(from); it != INVALID; ++it) {
8.121 + to.addFront(it);
8.122 }
8.123 }
8.124 };
8.125
8.126 - template <typename Target, typename Source>
8.127 - struct PathCopySelectorBackward<Target, Source, true> {
8.128 - static void copy(Target& target, const Source& source) {
8.129 - target.clear();
8.130 - target.buildRev(source);
8.131 + template <typename From, typename To>
8.132 + struct PathCopySelectorBackward<From, To, true> {
8.133 + static void copy(const From& from, To& to) {
8.134 + to.clear();
8.135 + to.buildRev(from);
8.136 }
8.137 };
8.138
8.139
8.140 - template <typename Target, typename Source,
8.141 - bool revEnable = RevPathTagIndicator<Source>::value>
8.142 + template <typename From, typename To,
8.143 + bool revEnable = RevPathTagIndicator<From>::value>
8.144 struct PathCopySelector {
8.145 - static void copy(Target& target, const Source& source) {
8.146 - PathCopySelectorForward<Target, Source>::copy(target, source);
8.147 + static void copy(const From& from, To& to) {
8.148 + PathCopySelectorForward<From, To>::copy(from, to);
8.149 }
8.150 };
8.151
8.152 - template <typename Target, typename Source>
8.153 - struct PathCopySelector<Target, Source, true> {
8.154 - static void copy(Target& target, const Source& source) {
8.155 - PathCopySelectorBackward<Target, Source>::copy(target, source);
8.156 + template <typename From, typename To>
8.157 + struct PathCopySelector<From, To, true> {
8.158 + static void copy(const From& from, To& to) {
8.159 + PathCopySelectorBackward<From, To>::copy(from, to);
8.160 }
8.161 };
8.162
8.163 @@ -987,11 +987,19 @@
8.164
8.165 /// \brief Make a copy of a path.
8.166 ///
8.167 - /// This function makes a copy of a path.
8.168 - template <typename Target, typename Source>
8.169 - void copyPath(Target& target, const Source& source) {
8.170 - checkConcept<concepts::PathDumper<typename Source::Digraph>, Source>();
8.171 - _path_bits::PathCopySelector<Target, Source>::copy(target, source);
8.172 + /// This function makes a copy of a path.
8.173 + template <typename From, typename To>
8.174 + void pathCopy(const From& from, To& to) {
8.175 + checkConcept<concepts::PathDumper<typename From::Digraph>, From>();
8.176 + _path_bits::PathCopySelector<From, To>::copy(from, to);
8.177 + }
8.178 +
8.179 + /// \brief Deprecated version of \ref pathCopy().
8.180 + ///
8.181 + /// Deprecated version of \ref pathCopy() (only for reverse compatibility).
8.182 + template <typename To, typename From>
8.183 + void copyPath(To& to, const From& from) {
8.184 + pathCopy(from, to);
8.185 }
8.186
8.187 /// \brief Check the consistency of a path.
8.188 @@ -1015,18 +1023,20 @@
8.189
8.190 /// \brief The source of a path
8.191 ///
8.192 - /// This function returns the source of the given path.
8.193 + /// This function returns the source node of the given path.
8.194 + /// If the path is empty, then it returns \c INVALID.
8.195 template <typename Digraph, typename Path>
8.196 typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
8.197 - return digraph.source(path.front());
8.198 + return path.empty() ? INVALID : digraph.source(path.front());
8.199 }
8.200
8.201 /// \brief The target of a path
8.202 ///
8.203 - /// This function returns the target of the given path.
8.204 + /// This function returns the target node of the given path.
8.205 + /// If the path is empty, then it returns \c INVALID.
8.206 template <typename Digraph, typename Path>
8.207 typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {
8.208 - return digraph.target(path.back());
8.209 + return path.empty() ? INVALID : digraph.target(path.back());
8.210 }
8.211
8.212 /// \brief Class which helps to iterate through the nodes of a path
9.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
9.2 +++ b/lemon/radix_heap.h Fri Apr 15 09:26:09 2011 +0200
9.3 @@ -0,0 +1,433 @@
9.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
9.5 + *
9.6 + * This file is a part of LEMON, a generic C++ optimization library.
9.7 + *
9.8 + * Copyright (C) 2003-2009
9.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
9.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
9.11 + *
9.12 + * Permission to use, modify and distribute this software is granted
9.13 + * provided that this copyright notice appears in all copies. For
9.14 + * precise terms see the accompanying LICENSE file.
9.15 + *
9.16 + * This software is provided "AS IS" with no warranty of any kind,
9.17 + * express or implied, and with no claim as to its suitability for any
9.18 + * purpose.
9.19 + *
9.20 + */
9.21 +
9.22 +#ifndef LEMON_RADIX_HEAP_H
9.23 +#define LEMON_RADIX_HEAP_H
9.24 +
9.25 +///\ingroup auxdat
9.26 +///\file
9.27 +///\brief Radix Heap implementation.
9.28 +
9.29 +#include <vector>
9.30 +#include <lemon/error.h>
9.31 +
9.32 +namespace lemon {
9.33 +
9.34 +
9.35 + /// \ingroup auxdata
9.36 + ///
9.37 + /// \brief A Radix Heap implementation.
9.38 + ///
9.39 + /// This class implements the \e radix \e heap data structure. A \e heap
9.40 + /// is a data structure for storing items with specified values called \e
9.41 + /// priorities in such a way that finding the item with minimum priority is
9.42 + /// efficient. This heap type can store only items with \e int priority.
9.43 + /// In a heap one can change the priority of an item, add or erase an
9.44 + /// item, but the priority cannot be decreased under the last removed
9.45 + /// item's priority.
9.46 + ///
9.47 + /// \param IM A read and writable Item int map, used internally
9.48 + /// to handle the cross references.
9.49 + ///
9.50 + /// \see BinHeap
9.51 + /// \see Dijkstra
9.52 + template <typename IM>
9.53 + class RadixHeap {
9.54 +
9.55 + public:
9.56 + typedef typename IM::Key Item;
9.57 + typedef int Prio;
9.58 + typedef IM ItemIntMap;
9.59 +
9.60 + /// \brief Exception thrown by RadixHeap.
9.61 + ///
9.62 + /// This Exception is thrown when a smaller priority
9.63 + /// is inserted into the \e RadixHeap then the last time erased.
9.64 + /// \see RadixHeap
9.65 +
9.66 + class UnderFlowPriorityError : public Exception {
9.67 + public:
9.68 + virtual const char* what() const throw() {
9.69 + return "lemon::RadixHeap::UnderFlowPriorityError";
9.70 + }
9.71 + };
9.72 +
9.73 + /// \brief Type to represent the items states.
9.74 + ///
9.75 + /// Each Item element have a state associated to it. It may be "in heap",
9.76 + /// "pre heap" or "post heap". The latter two are indifferent from the
9.77 + /// heap's point of view, but may be useful to the user.
9.78 + ///
9.79 + /// The ItemIntMap \e should be initialized in such way that it maps
9.80 + /// PRE_HEAP (-1) to any element to be put in the heap...
9.81 + enum State {
9.82 + IN_HEAP = 0,
9.83 + PRE_HEAP = -1,
9.84 + POST_HEAP = -2
9.85 + };
9.86 +
9.87 + private:
9.88 +
9.89 + struct RadixItem {
9.90 + int prev, next, box;
9.91 + Item item;
9.92 + int prio;
9.93 + RadixItem(Item _item, int _prio) : item(_item), prio(_prio) {}
9.94 + };
9.95 +
9.96 + struct RadixBox {
9.97 + int first;
9.98 + int min, size;
9.99 + RadixBox(int _min, int _size) : first(-1), min(_min), size(_size) {}
9.100 + };
9.101 +
9.102 + std::vector<RadixItem> data;
9.103 + std::vector<RadixBox> boxes;
9.104 +
9.105 + ItemIntMap &_iim;
9.106 +
9.107 +
9.108 + public:
9.109 + /// \brief The constructor.
9.110 + ///
9.111 + /// The constructor.
9.112 + ///
9.113 + /// \param map It should be given to the constructor, since it is used
9.114 + /// internally to handle the cross references. The value of the map
9.115 + /// should be PRE_HEAP (-1) for each element.
9.116 + ///
9.117 + /// \param minimal The initial minimal value of the heap.
9.118 + /// \param capacity It determines the initial capacity of the heap.
9.119 + RadixHeap(ItemIntMap &map, int minimal = 0, int capacity = 0)
9.120 + : _iim(map) {
9.121 + boxes.push_back(RadixBox(minimal, 1));
9.122 + boxes.push_back(RadixBox(minimal + 1, 1));
9.123 + while (lower(boxes.size() - 1, capacity + minimal - 1)) {
9.124 + extend();
9.125 + }
9.126 + }
9.127 +
9.128 + /// The number of items stored in the heap.
9.129 + ///
9.130 + /// \brief Returns the number of items stored in the heap.
9.131 + int size() const { return data.size(); }
9.132 + /// \brief Checks if the heap stores no items.
9.133 + ///
9.134 + /// Returns \c true if and only if the heap stores no items.
9.135 + bool empty() const { return data.empty(); }
9.136 +
9.137 + /// \brief Make empty this heap.
9.138 + ///
9.139 + /// Make empty this heap. It does not change the cross reference
9.140 + /// map. If you want to reuse a heap what is not surely empty you
9.141 + /// should first clear the heap and after that you should set the
9.142 + /// cross reference map for each item to \c PRE_HEAP.
9.143 + void clear(int minimal = 0, int capacity = 0) {
9.144 + data.clear(); boxes.clear();
9.145 + boxes.push_back(RadixBox(minimal, 1));
9.146 + boxes.push_back(RadixBox(minimal + 1, 1));
9.147 + while (lower(boxes.size() - 1, capacity + minimal - 1)) {
9.148 + extend();
9.149 + }
9.150 + }
9.151 +
9.152 + private:
9.153 +
9.154 + bool upper(int box, Prio pr) {
9.155 + return pr < boxes[box].min;
9.156 + }
9.157 +
9.158 + bool lower(int box, Prio pr) {
9.159 + return pr >= boxes[box].min + boxes[box].size;
9.160 + }
9.161 +
9.162 + /// \brief Remove item from the box list.
9.163 + void remove(int index) {
9.164 + if (data[index].prev >= 0) {
9.165 + data[data[index].prev].next = data[index].next;
9.166 + } else {
9.167 + boxes[data[index].box].first = data[index].next;
9.168 + }
9.169 + if (data[index].next >= 0) {
9.170 + data[data[index].next].prev = data[index].prev;
9.171 + }
9.172 + }
9.173 +
9.174 + /// \brief Insert item into the box list.
9.175 + void insert(int box, int index) {
9.176 + if (boxes[box].first == -1) {
9.177 + boxes[box].first = index;
9.178 + data[index].next = data[index].prev = -1;
9.179 + } else {
9.180 + data[index].next = boxes[box].first;
9.181 + data[boxes[box].first].prev = index;
9.182 + data[index].prev = -1;
9.183 + boxes[box].first = index;
9.184 + }
9.185 + data[index].box = box;
9.186 + }
9.187 +
9.188 + /// \brief Add a new box to the box list.
9.189 + void extend() {
9.190 + int min = boxes.back().min + boxes.back().size;
9.191 + int bs = 2 * boxes.back().size;
9.192 + boxes.push_back(RadixBox(min, bs));
9.193 + }
9.194 +
9.195 + /// \brief Move an item up into the proper box.
9.196 + void bubble_up(int index) {
9.197 + if (!lower(data[index].box, data[index].prio)) return;
9.198 + remove(index);
9.199 + int box = findUp(data[index].box, data[index].prio);
9.200 + insert(box, index);
9.201 + }
9.202 +
9.203 + /// \brief Find up the proper box for the item with the given prio.
9.204 + int findUp(int start, int pr) {
9.205 + while (lower(start, pr)) {
9.206 + if (++start == int(boxes.size())) {
9.207 + extend();
9.208 + }
9.209 + }
9.210 + return start;
9.211 + }
9.212 +
9.213 + /// \brief Move an item down into the proper box.
9.214 + void bubble_down(int index) {
9.215 + if (!upper(data[index].box, data[index].prio)) return;
9.216 + remove(index);
9.217 + int box = findDown(data[index].box, data[index].prio);
9.218 + insert(box, index);
9.219 + }
9.220 +
9.221 + /// \brief Find up the proper box for the item with the given prio.
9.222 + int findDown(int start, int pr) {
9.223 + while (upper(start, pr)) {
9.224 + if (--start < 0) throw UnderFlowPriorityError();
9.225 + }
9.226 + return start;
9.227 + }
9.228 +
9.229 + /// \brief Find the first not empty box.
9.230 + int findFirst() {
9.231 + int first = 0;
9.232 + while (boxes[first].first == -1) ++first;
9.233 + return first;
9.234 + }
9.235 +
9.236 + /// \brief Gives back the minimal prio of the box.
9.237 + int minValue(int box) {
9.238 + int min = data[boxes[box].first].prio;
9.239 + for (int k = boxes[box].first; k != -1; k = data[k].next) {
9.240 + if (data[k].prio < min) min = data[k].prio;
9.241 + }
9.242 + return min;
9.243 + }
9.244 +
9.245 + /// \brief Rearrange the items of the heap and makes the
9.246 + /// first box not empty.
9.247 + void moveDown() {
9.248 + int box = findFirst();
9.249 + if (box == 0) return;
9.250 + int min = minValue(box);
9.251 + for (int i = 0; i <= box; ++i) {
9.252 + boxes[i].min = min;
9.253 + min += boxes[i].size;
9.254 + }
9.255 + int curr = boxes[box].first, next;
9.256 + while (curr != -1) {
9.257 + next = data[curr].next;
9.258 + bubble_down(curr);
9.259 + curr = next;
9.260 + }
9.261 + }
9.262 +
9.263 + void relocate_last(int index) {
9.264 + if (index != int(data.size()) - 1) {
9.265 + data[index] = data.back();
9.266 + if (data[index].prev != -1) {
9.267 + data[data[index].prev].next = index;
9.268 + } else {
9.269 + boxes[data[index].box].first = index;
9.270 + }
9.271 + if (data[index].next != -1) {
9.272 + data[data[index].next].prev = index;
9.273 + }
9.274 + _iim[data[index].item] = index;
9.275 + }
9.276 + data.pop_back();
9.277 + }
9.278 +
9.279 + public:
9.280 +
9.281 + /// \brief Insert an item into the heap with the given priority.
9.282 + ///
9.283 + /// Adds \c i to the heap with priority \c p.
9.284 + /// \param i The item to insert.
9.285 + /// \param p The priority of the item.
9.286 + void push(const Item &i, const Prio &p) {
9.287 + int n = data.size();
9.288 + _iim.set(i, n);
9.289 + data.push_back(RadixItem(i, p));
9.290 + while (lower(boxes.size() - 1, p)) {
9.291 + extend();
9.292 + }
9.293 + int box = findDown(boxes.size() - 1, p);
9.294 + insert(box, n);
9.295 + }
9.296 +
9.297 + /// \brief Returns the item with minimum priority.
9.298 + ///
9.299 + /// This method returns the item with minimum priority.
9.300 + /// \pre The heap must be nonempty.
9.301 + Item top() const {
9.302 + const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
9.303 + return data[boxes[0].first].item;
9.304 + }
9.305 +
9.306 + /// \brief Returns the minimum priority.
9.307 + ///
9.308 + /// It returns the minimum priority.
9.309 + /// \pre The heap must be nonempty.
9.310 + Prio prio() const {
9.311 + const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
9.312 + return data[boxes[0].first].prio;
9.313 + }
9.314 +
9.315 + /// \brief Deletes the item with minimum priority.
9.316 + ///
9.317 + /// This method deletes the item with minimum priority.
9.318 + /// \pre The heap must be non-empty.
9.319 + void pop() {
9.320 + moveDown();
9.321 + int index = boxes[0].first;
9.322 + _iim[data[index].item] = POST_HEAP;
9.323 + remove(index);
9.324 + relocate_last(index);
9.325 + }
9.326 +
9.327 + /// \brief Deletes \c i from the heap.
9.328 + ///
9.329 + /// This method deletes item \c i from the heap, if \c i was
9.330 + /// already stored in the heap.
9.331 + /// \param i The item to erase.
9.332 + void erase(const Item &i) {
9.333 + int index = _iim[i];
9.334 + _iim[i] = POST_HEAP;
9.335 + remove(index);
9.336 + relocate_last(index);
9.337 + }
9.338 +
9.339 + /// \brief Returns the priority of \c i.
9.340 + ///
9.341 + /// This function returns the priority of item \c i.
9.342 + /// \pre \c i must be in the heap.
9.343 + /// \param i The item.
9.344 + Prio operator[](const Item &i) const {
9.345 + int idx = _iim[i];
9.346 + return data[idx].prio;
9.347 + }
9.348 +
9.349 + /// \brief \c i gets to the heap with priority \c p independently
9.350 + /// if \c i was already there.
9.351 + ///
9.352 + /// This method calls \ref push(\c i, \c p) if \c i is not stored
9.353 + /// in the heap and sets the priority of \c i to \c p otherwise.
9.354 + /// It may throw an \e UnderFlowPriorityException.
9.355 + /// \param i The item.
9.356 + /// \param p The priority.
9.357 + void set(const Item &i, const Prio &p) {
9.358 + int idx = _iim[i];
9.359 + if( idx < 0 ) {
9.360 + push(i, p);
9.361 + }
9.362 + else if( p >= data[idx].prio ) {
9.363 + data[idx].prio = p;
9.364 + bubble_up(idx);
9.365 + } else {
9.366 + data[idx].prio = p;
9.367 + bubble_down(idx);
9.368 + }
9.369 + }
9.370 +
9.371 +
9.372 + /// \brief Decreases the priority of \c i to \c p.
9.373 + ///
9.374 + /// This method decreases the priority of item \c i to \c p.
9.375 + /// \pre \c i must be stored in the heap with priority at least \c p, and
9.376 + /// \c should be greater or equal to the last removed item's priority.
9.377 + /// \param i The item.
9.378 + /// \param p The priority.
9.379 + void decrease(const Item &i, const Prio &p) {
9.380 + int idx = _iim[i];
9.381 + data[idx].prio = p;
9.382 + bubble_down(idx);
9.383 + }
9.384 +
9.385 + /// \brief Increases the priority of \c i to \c p.
9.386 + ///
9.387 + /// This method sets the priority of item \c i to \c p.
9.388 + /// \pre \c i must be stored in the heap with priority at most \c p
9.389 + /// \param i The item.
9.390 + /// \param p The priority.
9.391 + void increase(const Item &i, const Prio &p) {
9.392 + int idx = _iim[i];
9.393 + data[idx].prio = p;
9.394 + bubble_up(idx);
9.395 + }
9.396 +
9.397 + /// \brief Returns if \c item is in, has already been in, or has
9.398 + /// never been in the heap.
9.399 + ///
9.400 + /// This method returns PRE_HEAP if \c item has never been in the
9.401 + /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
9.402 + /// otherwise. In the latter case it is possible that \c item will
9.403 + /// get back to the heap again.
9.404 + /// \param i The item.
9.405 + State state(const Item &i) const {
9.406 + int s = _iim[i];
9.407 + if( s >= 0 ) s = 0;
9.408 + return State(s);
9.409 + }
9.410 +
9.411 + /// \brief Sets the state of the \c item in the heap.
9.412 + ///
9.413 + /// Sets the state of the \c item in the heap. It can be used to
9.414 + /// manually clear the heap when it is important to achive the
9.415 + /// better time complexity.
9.416 + /// \param i The item.
9.417 + /// \param st The state. It should not be \c IN_HEAP.
9.418 + void state(const Item& i, State st) {
9.419 + switch (st) {
9.420 + case POST_HEAP:
9.421 + case PRE_HEAP:
9.422 + if (state(i) == IN_HEAP) {
9.423 + erase(i);
9.424 + }
9.425 + _iim[i] = st;
9.426 + break;
9.427 + case IN_HEAP:
9.428 + break;
9.429 + }
9.430 + }
9.431 +
9.432 + }; // class RadixHeap
9.433 +
9.434 +} // namespace lemon
9.435 +
9.436 +#endif // LEMON_RADIX_HEAP_H
10.1 --- a/test/heap_test.cc Mon Mar 14 08:56:54 2011 +0100
10.2 +++ b/test/heap_test.cc Fri Apr 15 09:26:09 2011 +0200
10.3 @@ -31,6 +31,9 @@
10.4 #include <lemon/maps.h>
10.5
10.6 #include <lemon/bin_heap.h>
10.7 +#include <lemon/fib_heap.h>
10.8 +#include <lemon/radix_heap.h>
10.9 +#include <lemon/bucket_heap.h>
10.10
10.11 #include "test_tools.h"
10.12
10.13 @@ -183,5 +186,39 @@
10.14 dijkstraHeapTest<NodeHeap>(digraph, length, source);
10.15 }
10.16
10.17 + {
10.18 + typedef FibHeap<Prio, ItemIntMap> IntHeap;
10.19 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
10.20 + heapSortTest<IntHeap>();
10.21 + heapIncreaseTest<IntHeap>();
10.22 +
10.23 + typedef FibHeap<Prio, IntNodeMap > NodeHeap;
10.24 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
10.25 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
10.26 + }
10.27 +
10.28 + {
10.29 + typedef RadixHeap<ItemIntMap> IntHeap;
10.30 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
10.31 + heapSortTest<IntHeap>();
10.32 + heapIncreaseTest<IntHeap>();
10.33 +
10.34 + typedef RadixHeap<IntNodeMap > NodeHeap;
10.35 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
10.36 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
10.37 + }
10.38 +
10.39 + {
10.40 + typedef BucketHeap<ItemIntMap> IntHeap;
10.41 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
10.42 + heapSortTest<IntHeap>();
10.43 + heapIncreaseTest<IntHeap>();
10.44 +
10.45 + typedef BucketHeap<IntNodeMap > NodeHeap;
10.46 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
10.47 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
10.48 + }
10.49 +
10.50 +
10.51 return 0;
10.52 }