1.1 --- a/cmake/FindCOIN.cmake Tue Apr 12 07:46:34 2011 +0200
1.2 +++ b/cmake/FindCOIN.cmake Wed Jul 13 14:40:05 2011 +0200
1.3 @@ -5,42 +5,52 @@
1.4 )
1.5 FIND_LIBRARY(COIN_CBC_LIBRARY
1.6 NAMES Cbc libCbc
1.7 + HINTS ${COIN_ROOT_DIR}/lib/coin
1.8 HINTS ${COIN_ROOT_DIR}/lib
1.9 )
1.10 FIND_LIBRARY(COIN_CBC_SOLVER_LIBRARY
1.11 NAMES CbcSolver libCbcSolver
1.12 + HINTS ${COIN_ROOT_DIR}/lib/coin
1.13 HINTS ${COIN_ROOT_DIR}/lib
1.14 )
1.15 FIND_LIBRARY(COIN_CGL_LIBRARY
1.16 NAMES Cgl libCgl
1.17 + HINTS ${COIN_ROOT_DIR}/lib/coin
1.18 HINTS ${COIN_ROOT_DIR}/lib
1.19 )
1.20 FIND_LIBRARY(COIN_CLP_LIBRARY
1.21 NAMES Clp libClp
1.22 + HINTS ${COIN_ROOT_DIR}/lib/coin
1.23 HINTS ${COIN_ROOT_DIR}/lib
1.24 )
1.25 FIND_LIBRARY(COIN_COIN_UTILS_LIBRARY
1.26 NAMES CoinUtils libCoinUtils
1.27 + HINTS ${COIN_ROOT_DIR}/lib/coin
1.28 HINTS ${COIN_ROOT_DIR}/lib
1.29 )
1.30 FIND_LIBRARY(COIN_OSI_LIBRARY
1.31 NAMES Osi libOsi
1.32 + HINTS ${COIN_ROOT_DIR}/lib/coin
1.33 HINTS ${COIN_ROOT_DIR}/lib
1.34 )
1.35 FIND_LIBRARY(COIN_OSI_CBC_LIBRARY
1.36 NAMES OsiCbc libOsiCbc
1.37 + HINTS ${COIN_ROOT_DIR}/lib/coin
1.38 HINTS ${COIN_ROOT_DIR}/lib
1.39 )
1.40 FIND_LIBRARY(COIN_OSI_CLP_LIBRARY
1.41 NAMES OsiClp libOsiClp
1.42 + HINTS ${COIN_ROOT_DIR}/lib/coin
1.43 HINTS ${COIN_ROOT_DIR}/lib
1.44 )
1.45 FIND_LIBRARY(COIN_OSI_VOL_LIBRARY
1.46 NAMES OsiVol libOsiVol
1.47 + HINTS ${COIN_ROOT_DIR}/lib/coin
1.48 HINTS ${COIN_ROOT_DIR}/lib
1.49 )
1.50 FIND_LIBRARY(COIN_VOL_LIBRARY
1.51 NAMES Vol libVol
1.52 + HINTS ${COIN_ROOT_DIR}/lib/coin
1.53 HINTS ${COIN_ROOT_DIR}/lib
1.54 )
1.55
1.56 @@ -55,13 +65,13 @@
1.57 COIN_OSI_LIBRARY
1.58 COIN_OSI_CBC_LIBRARY
1.59 COIN_OSI_CLP_LIBRARY
1.60 - COIN_OSI_VOL_LIBRARY
1.61 - COIN_VOL_LIBRARY
1.62 + # COIN_OSI_VOL_LIBRARY
1.63 + # COIN_VOL_LIBRARY
1.64 )
1.65
1.66 IF(COIN_FOUND)
1.67 SET(COIN_INCLUDE_DIRS ${COIN_INCLUDE_DIR})
1.68 - SET(COIN_LIBRARIES "${COIN_CBC_LIBRARY};${COIN_CBC_SOLVER_LIBRARY};${COIN_CGL_LIBRARY};${COIN_CLP_LIBRARY};${COIN_COIN_UTILS_LIBRARY};${COIN_OSI_LIBRARY};${COIN_OSI_CBC_LIBRARY};${COIN_OSI_CLP_LIBRARY};${COIN_OSI_VOL_LIBRARY};${COIN_VOL_LIBRARY}")
1.69 + SET(COIN_LIBRARIES "${COIN_CBC_LIBRARY};${COIN_CBC_SOLVER_LIBRARY};${COIN_CGL_LIBRARY};${COIN_CLP_LIBRARY};${COIN_COIN_UTILS_LIBRARY};${COIN_OSI_LIBRARY};${COIN_OSI_CBC_LIBRARY};${COIN_OSI_CLP_LIBRARY}")
1.70 SET(COIN_CLP_LIBRARIES "${COIN_CLP_LIBRARY};${COIN_COIN_UTILS_LIBRARY}")
1.71 SET(COIN_CBC_LIBRARIES ${COIN_LIBRARIES})
1.72 ENDIF(COIN_FOUND)
2.1 --- a/lemon/Makefile.am Tue Apr 12 07:46:34 2011 +0200
2.2 +++ b/lemon/Makefile.am Wed Jul 13 14:40:05 2011 +0200
2.3 @@ -59,6 +59,7 @@
2.4 lemon/assert.h \
2.5 lemon/bfs.h \
2.6 lemon/bin_heap.h \
2.7 + lemon/bucket_heap.h \
2.8 lemon/cbc.h \
2.9 lemon/circulation.h \
2.10 lemon/clp.h \
2.11 @@ -76,6 +77,7 @@
2.12 lemon/elevator.h \
2.13 lemon/error.h \
2.14 lemon/euler.h \
2.15 + lemon/fib_heap.h \
2.16 lemon/full_graph.h \
2.17 lemon/glpk.h \
2.18 lemon/gomory_hu.h \
2.19 @@ -98,6 +100,7 @@
2.20 lemon/network_simplex.h \
2.21 lemon/path.h \
2.22 lemon/preflow.h \
2.23 + lemon/radix_heap.h \
2.24 lemon/radix_sort.h \
2.25 lemon/random.h \
2.26 lemon/smart_graph.h \
3.1 --- a/lemon/bin_heap.h Tue Apr 12 07:46:34 2011 +0200
3.2 +++ b/lemon/bin_heap.h Wed Jul 13 14:40:05 2011 +0200
3.3 @@ -33,23 +33,23 @@
3.4 ///
3.5 ///\brief A Binary Heap implementation.
3.6 ///
3.7 - ///This class implements the \e binary \e heap data structure.
3.8 - ///
3.9 + ///This class implements the \e binary \e heap data structure.
3.10 + ///
3.11 ///A \e heap is a data structure for storing items with specified values
3.12 ///called \e priorities in such a way that finding the item with minimum
3.13 - ///priority is efficient. \c Comp specifies the ordering of the priorities.
3.14 + ///priority is efficient. \c CMP specifies the ordering of the priorities.
3.15 ///In a heap one can change the priority of an item, add or erase an
3.16 ///item, etc.
3.17 ///
3.18 ///\tparam PR Type of the priority of the items.
3.19 ///\tparam IM A read and writable item map with int values, used internally
3.20 ///to handle the cross references.
3.21 - ///\tparam Comp A functor class for the ordering of the priorities.
3.22 + ///\tparam CMP A functor class for the ordering of the priorities.
3.23 ///The default is \c std::less<PR>.
3.24 ///
3.25 ///\sa FibHeap
3.26 ///\sa Dijkstra
3.27 - template <typename PR, typename IM, typename Comp = std::less<PR> >
3.28 + template <typename PR, typename IM, typename CMP = std::less<PR> >
3.29 class BinHeap {
3.30
3.31 public:
3.32 @@ -62,7 +62,7 @@
3.33 ///\e
3.34 typedef std::pair<Item,Prio> Pair;
3.35 ///\e
3.36 - typedef Comp Compare;
3.37 + typedef CMP Compare;
3.38
3.39 /// \brief Type to represent the items states.
3.40 ///
4.1 --- a/lemon/bits/map_extender.h Tue Apr 12 07:46:34 2011 +0200
4.2 +++ b/lemon/bits/map_extender.h Wed Jul 13 14:40:05 2011 +0200
4.3 @@ -49,6 +49,8 @@
4.4 typedef typename Parent::Reference Reference;
4.5 typedef typename Parent::ConstReference ConstReference;
4.6
4.7 + typedef typename Parent::ReferenceMapTag ReferenceMapTag;
4.8 +
4.9 class MapIt;
4.10 class ConstMapIt;
4.11
4.12 @@ -191,6 +193,8 @@
4.13 typedef typename Parent::Reference Reference;
4.14 typedef typename Parent::ConstReference ConstReference;
4.15
4.16 + typedef typename Parent::ReferenceMapTag ReferenceMapTag;
4.17 +
4.18 class MapIt;
4.19 class ConstMapIt;
4.20
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/lemon/bucket_heap.h Wed Jul 13 14:40:05 2011 +0200
5.3 @@ -0,0 +1,567 @@
5.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
5.5 + *
5.6 + * This file is a part of LEMON, a generic C++ optimization library.
5.7 + *
5.8 + * Copyright (C) 2003-2009
5.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
5.11 + *
5.12 + * Permission to use, modify and distribute this software is granted
5.13 + * provided that this copyright notice appears in all copies. For
5.14 + * precise terms see the accompanying LICENSE file.
5.15 + *
5.16 + * This software is provided "AS IS" with no warranty of any kind,
5.17 + * express or implied, and with no claim as to its suitability for any
5.18 + * purpose.
5.19 + *
5.20 + */
5.21 +
5.22 +#ifndef LEMON_BUCKET_HEAP_H
5.23 +#define LEMON_BUCKET_HEAP_H
5.24 +
5.25 +///\ingroup auxdat
5.26 +///\file
5.27 +///\brief Bucket Heap implementation.
5.28 +
5.29 +#include <vector>
5.30 +#include <utility>
5.31 +#include <functional>
5.32 +
5.33 +namespace lemon {
5.34 +
5.35 + namespace _bucket_heap_bits {
5.36 +
5.37 + template <bool MIN>
5.38 + struct DirectionTraits {
5.39 + static bool less(int left, int right) {
5.40 + return left < right;
5.41 + }
5.42 + static void increase(int& value) {
5.43 + ++value;
5.44 + }
5.45 + };
5.46 +
5.47 + template <>
5.48 + struct DirectionTraits<false> {
5.49 + static bool less(int left, int right) {
5.50 + return left > right;
5.51 + }
5.52 + static void increase(int& value) {
5.53 + --value;
5.54 + }
5.55 + };
5.56 +
5.57 + }
5.58 +
5.59 + /// \ingroup auxdat
5.60 + ///
5.61 + /// \brief A Bucket Heap implementation.
5.62 + ///
5.63 + /// This class implements the \e bucket \e heap data structure. A \e heap
5.64 + /// is a data structure for storing items with specified values called \e
5.65 + /// priorities in such a way that finding the item with minimum priority is
5.66 + /// efficient. The bucket heap is very simple implementation, it can store
5.67 + /// only integer priorities and it stores for each priority in the
5.68 + /// \f$ [0..C) \f$ range a list of items. So it should be used only when
5.69 + /// the priorities are small. It is not intended to use as dijkstra heap.
5.70 + ///
5.71 + /// \param IM A read and write Item int map, used internally
5.72 + /// to handle the cross references.
5.73 + /// \param MIN If the given parameter is false then instead of the
5.74 + /// minimum value the maximum can be retrivied with the top() and
5.75 + /// prio() member functions.
5.76 + template <typename IM, bool MIN = true>
5.77 + class BucketHeap {
5.78 +
5.79 + public:
5.80 + /// \e
5.81 + typedef typename IM::Key Item;
5.82 + /// \e
5.83 + typedef int Prio;
5.84 + /// \e
5.85 + typedef std::pair<Item, Prio> Pair;
5.86 + /// \e
5.87 + typedef IM ItemIntMap;
5.88 +
5.89 + private:
5.90 +
5.91 + typedef _bucket_heap_bits::DirectionTraits<MIN> Direction;
5.92 +
5.93 + public:
5.94 +
5.95 + /// \brief Type to represent the items states.
5.96 + ///
5.97 + /// Each Item element have a state associated to it. It may be "in heap",
5.98 + /// "pre heap" or "post heap". The latter two are indifferent from the
5.99 + /// heap's point of view, but may be useful to the user.
5.100 + ///
5.101 + /// The item-int map must be initialized in such way that it assigns
5.102 + /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
5.103 + enum State {
5.104 + IN_HEAP = 0, ///< = 0.
5.105 + PRE_HEAP = -1, ///< = -1.
5.106 + POST_HEAP = -2 ///< = -2.
5.107 + };
5.108 +
5.109 + public:
5.110 + /// \brief The constructor.
5.111 + ///
5.112 + /// The constructor.
5.113 + /// \param map should be given to the constructor, since it is used
5.114 + /// internally to handle the cross references. The value of the map
5.115 + /// should be PRE_HEAP (-1) for each element.
5.116 + explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {}
5.117 +
5.118 + /// The number of items stored in the heap.
5.119 + ///
5.120 + /// \brief Returns the number of items stored in the heap.
5.121 + int size() const { return _data.size(); }
5.122 +
5.123 + /// \brief Checks if the heap stores no items.
5.124 + ///
5.125 + /// Returns \c true if and only if the heap stores no items.
5.126 + bool empty() const { return _data.empty(); }
5.127 +
5.128 + /// \brief Make empty this heap.
5.129 + ///
5.130 + /// Make empty this heap. It does not change the cross reference
5.131 + /// map. If you want to reuse a heap what is not surely empty you
5.132 + /// should first clear the heap and after that you should set the
5.133 + /// cross reference map for each item to \c PRE_HEAP.
5.134 + void clear() {
5.135 + _data.clear(); _first.clear(); _minimum = 0;
5.136 + }
5.137 +
5.138 + private:
5.139 +
5.140 + void relocate_last(int idx) {
5.141 + if (idx + 1 < int(_data.size())) {
5.142 + _data[idx] = _data.back();
5.143 + if (_data[idx].prev != -1) {
5.144 + _data[_data[idx].prev].next = idx;
5.145 + } else {
5.146 + _first[_data[idx].value] = idx;
5.147 + }
5.148 + if (_data[idx].next != -1) {
5.149 + _data[_data[idx].next].prev = idx;
5.150 + }
5.151 + _iim[_data[idx].item] = idx;
5.152 + }
5.153 + _data.pop_back();
5.154 + }
5.155 +
5.156 + void unlace(int idx) {
5.157 + if (_data[idx].prev != -1) {
5.158 + _data[_data[idx].prev].next = _data[idx].next;
5.159 + } else {
5.160 + _first[_data[idx].value] = _data[idx].next;
5.161 + }
5.162 + if (_data[idx].next != -1) {
5.163 + _data[_data[idx].next].prev = _data[idx].prev;
5.164 + }
5.165 + }
5.166 +
5.167 + void lace(int idx) {
5.168 + if (int(_first.size()) <= _data[idx].value) {
5.169 + _first.resize(_data[idx].value + 1, -1);
5.170 + }
5.171 + _data[idx].next = _first[_data[idx].value];
5.172 + if (_data[idx].next != -1) {
5.173 + _data[_data[idx].next].prev = idx;
5.174 + }
5.175 + _first[_data[idx].value] = idx;
5.176 + _data[idx].prev = -1;
5.177 + }
5.178 +
5.179 + public:
5.180 + /// \brief Insert a pair of item and priority into the heap.
5.181 + ///
5.182 + /// Adds \c p.first to the heap with priority \c p.second.
5.183 + /// \param p The pair to insert.
5.184 + void push(const Pair& p) {
5.185 + push(p.first, p.second);
5.186 + }
5.187 +
5.188 + /// \brief Insert an item into the heap with the given priority.
5.189 + ///
5.190 + /// Adds \c i to the heap with priority \c p.
5.191 + /// \param i The item to insert.
5.192 + /// \param p The priority of the item.
5.193 + void push(const Item &i, const Prio &p) {
5.194 + int idx = _data.size();
5.195 + _iim[i] = idx;
5.196 + _data.push_back(BucketItem(i, p));
5.197 + lace(idx);
5.198 + if (Direction::less(p, _minimum)) {
5.199 + _minimum = p;
5.200 + }
5.201 + }
5.202 +
5.203 + /// \brief Returns the item with minimum priority.
5.204 + ///
5.205 + /// This method returns the item with minimum priority.
5.206 + /// \pre The heap must be nonempty.
5.207 + Item top() const {
5.208 + while (_first[_minimum] == -1) {
5.209 + Direction::increase(_minimum);
5.210 + }
5.211 + return _data[_first[_minimum]].item;
5.212 + }
5.213 +
5.214 + /// \brief Returns the minimum priority.
5.215 + ///
5.216 + /// It returns the minimum priority.
5.217 + /// \pre The heap must be nonempty.
5.218 + Prio prio() const {
5.219 + while (_first[_minimum] == -1) {
5.220 + Direction::increase(_minimum);
5.221 + }
5.222 + return _minimum;
5.223 + }
5.224 +
5.225 + /// \brief Deletes the item with minimum priority.
5.226 + ///
5.227 + /// This method deletes the item with minimum priority from the heap.
5.228 + /// \pre The heap must be non-empty.
5.229 + void pop() {
5.230 + while (_first[_minimum] == -1) {
5.231 + Direction::increase(_minimum);
5.232 + }
5.233 + int idx = _first[_minimum];
5.234 + _iim[_data[idx].item] = -2;
5.235 + unlace(idx);
5.236 + relocate_last(idx);
5.237 + }
5.238 +
5.239 + /// \brief Deletes \c i from the heap.
5.240 + ///
5.241 + /// This method deletes item \c i from the heap, if \c i was
5.242 + /// already stored in the heap.
5.243 + /// \param i The item to erase.
5.244 + void erase(const Item &i) {
5.245 + int idx = _iim[i];
5.246 + _iim[_data[idx].item] = -2;
5.247 + unlace(idx);
5.248 + relocate_last(idx);
5.249 + }
5.250 +
5.251 +
5.252 + /// \brief Returns the priority of \c i.
5.253 + ///
5.254 + /// This function returns the priority of item \c i.
5.255 + /// \pre \c i must be in the heap.
5.256 + /// \param i The item.
5.257 + Prio operator[](const Item &i) const {
5.258 + int idx = _iim[i];
5.259 + return _data[idx].value;
5.260 + }
5.261 +
5.262 + /// \brief \c i gets to the heap with priority \c p independently
5.263 + /// if \c i was already there.
5.264 + ///
5.265 + /// This method calls \ref push(\c i, \c p) if \c i is not stored
5.266 + /// in the heap and sets the priority of \c i to \c p otherwise.
5.267 + /// \param i The item.
5.268 + /// \param p The priority.
5.269 + void set(const Item &i, const Prio &p) {
5.270 + int idx = _iim[i];
5.271 + if (idx < 0) {
5.272 + push(i, p);
5.273 + } else if (Direction::less(p, _data[idx].value)) {
5.274 + decrease(i, p);
5.275 + } else {
5.276 + increase(i, p);
5.277 + }
5.278 + }
5.279 +
5.280 + /// \brief Decreases the priority of \c i to \c p.
5.281 + ///
5.282 + /// This method decreases the priority of item \c i to \c p.
5.283 + /// \pre \c i must be stored in the heap with priority at least \c
5.284 + /// p relative to \c Compare.
5.285 + /// \param i The item.
5.286 + /// \param p The priority.
5.287 + void decrease(const Item &i, const Prio &p) {
5.288 + int idx = _iim[i];
5.289 + unlace(idx);
5.290 + _data[idx].value = p;
5.291 + if (Direction::less(p, _minimum)) {
5.292 + _minimum = p;
5.293 + }
5.294 + lace(idx);
5.295 + }
5.296 +
5.297 + /// \brief Increases the priority of \c i to \c p.
5.298 + ///
5.299 + /// This method sets the priority of item \c i to \c p.
5.300 + /// \pre \c i must be stored in the heap with priority at most \c
5.301 + /// p relative to \c Compare.
5.302 + /// \param i The item.
5.303 + /// \param p The priority.
5.304 + void increase(const Item &i, const Prio &p) {
5.305 + int idx = _iim[i];
5.306 + unlace(idx);
5.307 + _data[idx].value = p;
5.308 + lace(idx);
5.309 + }
5.310 +
5.311 + /// \brief Returns if \c item is in, has already been in, or has
5.312 + /// never been in the heap.
5.313 + ///
5.314 + /// This method returns PRE_HEAP if \c item has never been in the
5.315 + /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
5.316 + /// otherwise. In the latter case it is possible that \c item will
5.317 + /// get back to the heap again.
5.318 + /// \param i The item.
5.319 + State state(const Item &i) const {
5.320 + int idx = _iim[i];
5.321 + if (idx >= 0) idx = 0;
5.322 + return State(idx);
5.323 + }
5.324 +
5.325 + /// \brief Sets the state of the \c item in the heap.
5.326 + ///
5.327 + /// Sets the state of the \c item in the heap. It can be used to
5.328 + /// manually clear the heap when it is important to achive the
5.329 + /// better time complexity.
5.330 + /// \param i The item.
5.331 + /// \param st The state. It should not be \c IN_HEAP.
5.332 + void state(const Item& i, State st) {
5.333 + switch (st) {
5.334 + case POST_HEAP:
5.335 + case PRE_HEAP:
5.336 + if (state(i) == IN_HEAP) {
5.337 + erase(i);
5.338 + }
5.339 + _iim[i] = st;
5.340 + break;
5.341 + case IN_HEAP:
5.342 + break;
5.343 + }
5.344 + }
5.345 +
5.346 + private:
5.347 +
5.348 + struct BucketItem {
5.349 + BucketItem(const Item& _item, int _value)
5.350 + : item(_item), value(_value) {}
5.351 +
5.352 + Item item;
5.353 + int value;
5.354 +
5.355 + int prev, next;
5.356 + };
5.357 +
5.358 + ItemIntMap& _iim;
5.359 + std::vector<int> _first;
5.360 + std::vector<BucketItem> _data;
5.361 + mutable int _minimum;
5.362 +
5.363 + }; // class BucketHeap
5.364 +
5.365 + /// \ingroup auxdat
5.366 + ///
5.367 + /// \brief A Simplified Bucket Heap implementation.
5.368 + ///
5.369 + /// This class implements a simplified \e bucket \e heap data
5.370 + /// structure. It does not provide some functionality but it faster
5.371 + /// and simplier data structure than the BucketHeap. The main
5.372 + /// difference is that the BucketHeap stores for every key a double
5.373 + /// linked list while this class stores just simple lists. In the
5.374 + /// other way it does not support erasing each elements just the
5.375 + /// minimal and it does not supports key increasing, decreasing.
5.376 + ///
5.377 + /// \param IM A read and write Item int map, used internally
5.378 + /// to handle the cross references.
5.379 + /// \param MIN If the given parameter is false then instead of the
5.380 + /// minimum value the maximum can be retrivied with the top() and
5.381 + /// prio() member functions.
5.382 + ///
5.383 + /// \sa BucketHeap
5.384 + template <typename IM, bool MIN = true >
5.385 + class SimpleBucketHeap {
5.386 +
5.387 + public:
5.388 + typedef typename IM::Key Item;
5.389 + typedef int Prio;
5.390 + typedef std::pair<Item, Prio> Pair;
5.391 + typedef IM ItemIntMap;
5.392 +
5.393 + private:
5.394 +
5.395 + typedef _bucket_heap_bits::DirectionTraits<MIN> Direction;
5.396 +
5.397 + public:
5.398 +
5.399 + /// \brief Type to represent the items states.
5.400 + ///
5.401 + /// Each Item element have a state associated to it. It may be "in heap",
5.402 + /// "pre heap" or "post heap". The latter two are indifferent from the
5.403 + /// heap's point of view, but may be useful to the user.
5.404 + ///
5.405 + /// The item-int map must be initialized in such way that it assigns
5.406 + /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
5.407 + enum State {
5.408 + IN_HEAP = 0, ///< = 0.
5.409 + PRE_HEAP = -1, ///< = -1.
5.410 + POST_HEAP = -2 ///< = -2.
5.411 + };
5.412 +
5.413 + public:
5.414 +
5.415 + /// \brief The constructor.
5.416 + ///
5.417 + /// The constructor.
5.418 + /// \param map should be given to the constructor, since it is used
5.419 + /// internally to handle the cross references. The value of the map
5.420 + /// should be PRE_HEAP (-1) for each element.
5.421 + explicit SimpleBucketHeap(ItemIntMap &map)
5.422 + : _iim(map), _free(-1), _num(0), _minimum(0) {}
5.423 +
5.424 + /// \brief Returns the number of items stored in the heap.
5.425 + ///
5.426 + /// The number of items stored in the heap.
5.427 + int size() const { return _num; }
5.428 +
5.429 + /// \brief Checks if the heap stores no items.
5.430 + ///
5.431 + /// Returns \c true if and only if the heap stores no items.
5.432 + bool empty() const { return _num == 0; }
5.433 +
5.434 + /// \brief Make empty this heap.
5.435 + ///
5.436 + /// Make empty this heap. It does not change the cross reference
5.437 + /// map. If you want to reuse a heap what is not surely empty you
5.438 + /// should first clear the heap and after that you should set the
5.439 + /// cross reference map for each item to \c PRE_HEAP.
5.440 + void clear() {
5.441 + _data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0;
5.442 + }
5.443 +
5.444 + /// \brief Insert a pair of item and priority into the heap.
5.445 + ///
5.446 + /// Adds \c p.first to the heap with priority \c p.second.
5.447 + /// \param p The pair to insert.
5.448 + void push(const Pair& p) {
5.449 + push(p.first, p.second);
5.450 + }
5.451 +
5.452 + /// \brief Insert an item into the heap with the given priority.
5.453 + ///
5.454 + /// Adds \c i to the heap with priority \c p.
5.455 + /// \param i The item to insert.
5.456 + /// \param p The priority of the item.
5.457 + void push(const Item &i, const Prio &p) {
5.458 + int idx;
5.459 + if (_free == -1) {
5.460 + idx = _data.size();
5.461 + _data.push_back(BucketItem(i));
5.462 + } else {
5.463 + idx = _free;
5.464 + _free = _data[idx].next;
5.465 + _data[idx].item = i;
5.466 + }
5.467 + _iim[i] = idx;
5.468 + if (p >= int(_first.size())) _first.resize(p + 1, -1);
5.469 + _data[idx].next = _first[p];
5.470 + _first[p] = idx;
5.471 + if (Direction::less(p, _minimum)) {
5.472 + _minimum = p;
5.473 + }
5.474 + ++_num;
5.475 + }
5.476 +
5.477 + /// \brief Returns the item with minimum priority.
5.478 + ///
5.479 + /// This method returns the item with minimum priority.
5.480 + /// \pre The heap must be nonempty.
5.481 + Item top() const {
5.482 + while (_first[_minimum] == -1) {
5.483 + Direction::increase(_minimum);
5.484 + }
5.485 + return _data[_first[_minimum]].item;
5.486 + }
5.487 +
5.488 + /// \brief Returns the minimum priority.
5.489 + ///
5.490 + /// It returns the minimum priority.
5.491 + /// \pre The heap must be nonempty.
5.492 + Prio prio() const {
5.493 + while (_first[_minimum] == -1) {
5.494 + Direction::increase(_minimum);
5.495 + }
5.496 + return _minimum;
5.497 + }
5.498 +
5.499 + /// \brief Deletes the item with minimum priority.
5.500 + ///
5.501 + /// This method deletes the item with minimum priority from the heap.
5.502 + /// \pre The heap must be non-empty.
5.503 + void pop() {
5.504 + while (_first[_minimum] == -1) {
5.505 + Direction::increase(_minimum);
5.506 + }
5.507 + int idx = _first[_minimum];
5.508 + _iim[_data[idx].item] = -2;
5.509 + _first[_minimum] = _data[idx].next;
5.510 + _data[idx].next = _free;
5.511 + _free = idx;
5.512 + --_num;
5.513 + }
5.514 +
5.515 + /// \brief Returns the priority of \c i.
5.516 + ///
5.517 + /// This function returns the priority of item \c i.
5.518 + /// \warning This operator is not a constant time function
5.519 + /// because it scans the whole data structure to find the proper
5.520 + /// value.
5.521 + /// \pre \c i must be in the heap.
5.522 + /// \param i The item.
5.523 + Prio operator[](const Item &i) const {
5.524 + for (int k = 0; k < _first.size(); ++k) {
5.525 + int idx = _first[k];
5.526 + while (idx != -1) {
5.527 + if (_data[idx].item == i) {
5.528 + return k;
5.529 + }
5.530 + idx = _data[idx].next;
5.531 + }
5.532 + }
5.533 + return -1;
5.534 + }
5.535 +
5.536 + /// \brief Returns if \c item is in, has already been in, or has
5.537 + /// never been in the heap.
5.538 + ///
5.539 + /// This method returns PRE_HEAP if \c item has never been in the
5.540 + /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
5.541 + /// otherwise. In the latter case it is possible that \c item will
5.542 + /// get back to the heap again.
5.543 + /// \param i The item.
5.544 + State state(const Item &i) const {
5.545 + int idx = _iim[i];
5.546 + if (idx >= 0) idx = 0;
5.547 + return State(idx);
5.548 + }
5.549 +
5.550 + private:
5.551 +
5.552 + struct BucketItem {
5.553 + BucketItem(const Item& _item)
5.554 + : item(_item) {}
5.555 +
5.556 + Item item;
5.557 + int next;
5.558 + };
5.559 +
5.560 + ItemIntMap& _iim;
5.561 + std::vector<int> _first;
5.562 + std::vector<BucketItem> _data;
5.563 + int _free, _num;
5.564 + mutable int _minimum;
5.565 +
5.566 + }; // class SimpleBucketHeap
5.567 +
5.568 +}
5.569 +
5.570 +#endif
6.1 --- a/lemon/concepts/maps.h Tue Apr 12 07:46:34 2011 +0200
6.2 +++ b/lemon/concepts/maps.h Wed Jul 13 14:40:05 2011 +0200
6.3 @@ -182,7 +182,8 @@
6.4
6.5 template<typename _ReferenceMap>
6.6 struct Constraints {
6.7 - void constraints() {
6.8 + typename enable_if<typename _ReferenceMap::ReferenceMapTag, void>::type
6.9 + constraints() {
6.10 checkConcept<ReadWriteMap<K, T>, _ReferenceMap >();
6.11 ref = m[key];
6.12 m[key] = val;
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
7.2 +++ b/lemon/fib_heap.h Wed Jul 13 14:40:05 2011 +0200
7.3 @@ -0,0 +1,468 @@
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_FIB_HEAP_H
7.23 +#define LEMON_FIB_HEAP_H
7.24 +
7.25 +///\file
7.26 +///\ingroup auxdat
7.27 +///\brief Fibonacci Heap implementation.
7.28 +
7.29 +#include <vector>
7.30 +#include <functional>
7.31 +#include <lemon/math.h>
7.32 +
7.33 +namespace lemon {
7.34 +
7.35 + /// \ingroup auxdat
7.36 + ///
7.37 + ///\brief Fibonacci Heap.
7.38 + ///
7.39 + ///This class implements the \e Fibonacci \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. \c CMP specifies the ordering of the priorities. In a heap
7.43 + ///one can change the priority of an item, add or erase an item, etc.
7.44 + ///
7.45 + ///The methods \ref increase and \ref erase are not efficient in a Fibonacci
7.46 + ///heap. In case of many calls to these operations, it is better to use a
7.47 + ///\ref BinHeap "binary heap".
7.48 + ///
7.49 + ///\param PRIO Type of the priority of the items.
7.50 + ///\param IM A read and writable Item int map, used internally
7.51 + ///to handle the cross references.
7.52 + ///\param CMP A class for the ordering of the priorities. The
7.53 + ///default is \c std::less<PRIO>.
7.54 + ///
7.55 + ///\sa BinHeap
7.56 + ///\sa Dijkstra
7.57 +#ifdef DOXYGEN
7.58 + template <typename PRIO, typename IM, typename CMP>
7.59 +#else
7.60 + template <typename PRIO, typename IM, typename CMP = std::less<PRIO> >
7.61 +#endif
7.62 + class FibHeap {
7.63 + public:
7.64 + ///\e
7.65 + typedef IM ItemIntMap;
7.66 + ///\e
7.67 + typedef PRIO Prio;
7.68 + ///\e
7.69 + typedef typename ItemIntMap::Key Item;
7.70 + ///\e
7.71 + typedef std::pair<Item,Prio> Pair;
7.72 + ///\e
7.73 + typedef CMP Compare;
7.74 +
7.75 + private:
7.76 + class Store;
7.77 +
7.78 + std::vector<Store> _data;
7.79 + int _minimum;
7.80 + ItemIntMap &_iim;
7.81 + Compare _comp;
7.82 + int _num;
7.83 +
7.84 + public:
7.85 +
7.86 + /// \brief Type to represent the items states.
7.87 + ///
7.88 + /// Each Item element have a state associated to it. It may be "in heap",
7.89 + /// "pre heap" or "post heap". The latter two are indifferent from the
7.90 + /// heap's point of view, but may be useful to the user.
7.91 + ///
7.92 + /// The item-int map must be initialized in such way that it assigns
7.93 + /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
7.94 + enum State {
7.95 + IN_HEAP = 0, ///< = 0.
7.96 + PRE_HEAP = -1, ///< = -1.
7.97 + POST_HEAP = -2 ///< = -2.
7.98 + };
7.99 +
7.100 + /// \brief The constructor
7.101 + ///
7.102 + /// \c map should be given to the constructor, since it is
7.103 + /// used internally to handle the cross references.
7.104 + explicit FibHeap(ItemIntMap &map)
7.105 + : _minimum(0), _iim(map), _num() {}
7.106 +
7.107 + /// \brief The constructor
7.108 + ///
7.109 + /// \c map should be given to the constructor, since it is used
7.110 + /// internally to handle the cross references. \c comp is an
7.111 + /// object for ordering of the priorities.
7.112 + FibHeap(ItemIntMap &map, const Compare &comp)
7.113 + : _minimum(0), _iim(map), _comp(comp), _num() {}
7.114 +
7.115 + /// \brief The number of items stored in the heap.
7.116 + ///
7.117 + /// Returns the number of items stored in the heap.
7.118 + int size() const { return _num; }
7.119 +
7.120 + /// \brief Checks if the heap stores no items.
7.121 + ///
7.122 + /// Returns \c true if and only if the heap stores no items.
7.123 + bool empty() const { return _num==0; }
7.124 +
7.125 + /// \brief Make empty this heap.
7.126 + ///
7.127 + /// Make empty this heap. It does not change the cross reference
7.128 + /// map. If you want to reuse a heap what is not surely empty you
7.129 + /// should first clear the heap and after that you should set the
7.130 + /// cross reference map for each item to \c PRE_HEAP.
7.131 + void clear() {
7.132 + _data.clear(); _minimum = 0; _num = 0;
7.133 + }
7.134 +
7.135 + /// \brief \c item gets to the heap with priority \c value independently
7.136 + /// if \c item was already there.
7.137 + ///
7.138 + /// This method calls \ref push(\c item, \c value) if \c item is not
7.139 + /// stored in the heap and it calls \ref decrease(\c item, \c value) or
7.140 + /// \ref increase(\c item, \c value) otherwise.
7.141 + void set (const Item& item, const Prio& value) {
7.142 + int i=_iim[item];
7.143 + if ( i >= 0 && _data[i].in ) {
7.144 + if ( _comp(value, _data[i].prio) ) decrease(item, value);
7.145 + if ( _comp(_data[i].prio, value) ) increase(item, value);
7.146 + } else push(item, value);
7.147 + }
7.148 +
7.149 + /// \brief Adds \c item to the heap with priority \c value.
7.150 + ///
7.151 + /// Adds \c item to the heap with priority \c value.
7.152 + /// \pre \c item must not be stored in the heap.
7.153 + void push (const Item& item, const Prio& value) {
7.154 + int i=_iim[item];
7.155 + if ( i < 0 ) {
7.156 + int s=_data.size();
7.157 + _iim.set( item, s );
7.158 + Store st;
7.159 + st.name=item;
7.160 + _data.push_back(st);
7.161 + i=s;
7.162 + } else {
7.163 + _data[i].parent=_data[i].child=-1;
7.164 + _data[i].degree=0;
7.165 + _data[i].in=true;
7.166 + _data[i].marked=false;
7.167 + }
7.168 +
7.169 + if ( _num ) {
7.170 + _data[_data[_minimum].right_neighbor].left_neighbor=i;
7.171 + _data[i].right_neighbor=_data[_minimum].right_neighbor;
7.172 + _data[_minimum].right_neighbor=i;
7.173 + _data[i].left_neighbor=_minimum;
7.174 + if ( _comp( value, _data[_minimum].prio) ) _minimum=i;
7.175 + } else {
7.176 + _data[i].right_neighbor=_data[i].left_neighbor=i;
7.177 + _minimum=i;
7.178 + }
7.179 + _data[i].prio=value;
7.180 + ++_num;
7.181 + }
7.182 +
7.183 + /// \brief Returns the item with minimum priority relative to \c Compare.
7.184 + ///
7.185 + /// This method returns the item with minimum priority relative to \c
7.186 + /// Compare.
7.187 + /// \pre The heap must be nonempty.
7.188 + Item top() const { return _data[_minimum].name; }
7.189 +
7.190 + /// \brief Returns the minimum priority relative to \c Compare.
7.191 + ///
7.192 + /// It returns the minimum priority relative to \c Compare.
7.193 + /// \pre The heap must be nonempty.
7.194 + const Prio& prio() const { return _data[_minimum].prio; }
7.195 +
7.196 + /// \brief Returns the priority of \c item.
7.197 + ///
7.198 + /// It returns the priority of \c item.
7.199 + /// \pre \c item must be in the heap.
7.200 + const Prio& operator[](const Item& item) const {
7.201 + return _data[_iim[item]].prio;
7.202 + }
7.203 +
7.204 + /// \brief Deletes the item with minimum priority relative to \c Compare.
7.205 + ///
7.206 + /// This method deletes the item with minimum priority relative to \c
7.207 + /// Compare from the heap.
7.208 + /// \pre The heap must be non-empty.
7.209 + void pop() {
7.210 + /*The first case is that there are only one root.*/
7.211 + if ( _data[_minimum].left_neighbor==_minimum ) {
7.212 + _data[_minimum].in=false;
7.213 + if ( _data[_minimum].degree!=0 ) {
7.214 + makeroot(_data[_minimum].child);
7.215 + _minimum=_data[_minimum].child;
7.216 + balance();
7.217 + }
7.218 + } else {
7.219 + int right=_data[_minimum].right_neighbor;
7.220 + unlace(_minimum);
7.221 + _data[_minimum].in=false;
7.222 + if ( _data[_minimum].degree > 0 ) {
7.223 + int left=_data[_minimum].left_neighbor;
7.224 + int child=_data[_minimum].child;
7.225 + int last_child=_data[child].left_neighbor;
7.226 +
7.227 + makeroot(child);
7.228 +
7.229 + _data[left].right_neighbor=child;
7.230 + _data[child].left_neighbor=left;
7.231 + _data[right].left_neighbor=last_child;
7.232 + _data[last_child].right_neighbor=right;
7.233 + }
7.234 + _minimum=right;
7.235 + balance();
7.236 + } // the case where there are more roots
7.237 + --_num;
7.238 + }
7.239 +
7.240 + /// \brief Deletes \c item from the heap.
7.241 + ///
7.242 + /// This method deletes \c item from the heap, if \c item was already
7.243 + /// stored in the heap. It is quite inefficient in Fibonacci heaps.
7.244 + void erase (const Item& item) {
7.245 + int i=_iim[item];
7.246 +
7.247 + if ( i >= 0 && _data[i].in ) {
7.248 + if ( _data[i].parent!=-1 ) {
7.249 + int p=_data[i].parent;
7.250 + cut(i,p);
7.251 + cascade(p);
7.252 + }
7.253 + _minimum=i; //As if its prio would be -infinity
7.254 + pop();
7.255 + }
7.256 + }
7.257 +
7.258 + /// \brief Decreases the priority of \c item to \c value.
7.259 + ///
7.260 + /// This method decreases the priority of \c item to \c value.
7.261 + /// \pre \c item must be stored in the heap with priority at least \c
7.262 + /// value relative to \c Compare.
7.263 + void decrease (Item item, const Prio& value) {
7.264 + int i=_iim[item];
7.265 + _data[i].prio=value;
7.266 + int p=_data[i].parent;
7.267 +
7.268 + if ( p!=-1 && _comp(value, _data[p].prio) ) {
7.269 + cut(i,p);
7.270 + cascade(p);
7.271 + }
7.272 + if ( _comp(value, _data[_minimum].prio) ) _minimum=i;
7.273 + }
7.274 +
7.275 + /// \brief Increases the priority of \c item to \c value.
7.276 + ///
7.277 + /// This method sets the priority of \c item to \c value. Though
7.278 + /// there is no precondition on the priority of \c item, this
7.279 + /// method should be used only if it is indeed necessary to increase
7.280 + /// (relative to \c Compare) the priority of \c item, because this
7.281 + /// method is inefficient.
7.282 + void increase (Item item, const Prio& value) {
7.283 + erase(item);
7.284 + push(item, value);
7.285 + }
7.286 +
7.287 +
7.288 + /// \brief Returns if \c item is in, has already been in, or has never
7.289 + /// been in the heap.
7.290 + ///
7.291 + /// This method returns PRE_HEAP if \c item has never been in the
7.292 + /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
7.293 + /// otherwise. In the latter case it is possible that \c item will
7.294 + /// get back to the heap again.
7.295 + State state(const Item &item) const {
7.296 + int i=_iim[item];
7.297 + if( i>=0 ) {
7.298 + if ( _data[i].in ) i=0;
7.299 + else i=-2;
7.300 + }
7.301 + return State(i);
7.302 + }
7.303 +
7.304 + /// \brief Sets the state of the \c item in the heap.
7.305 + ///
7.306 + /// Sets the state of the \c item in the heap. It can be used to
7.307 + /// manually clear the heap when it is important to achive the
7.308 + /// better time _complexity.
7.309 + /// \param i The item.
7.310 + /// \param st The state. It should not be \c IN_HEAP.
7.311 + void state(const Item& i, State st) {
7.312 + switch (st) {
7.313 + case POST_HEAP:
7.314 + case PRE_HEAP:
7.315 + if (state(i) == IN_HEAP) {
7.316 + erase(i);
7.317 + }
7.318 + _iim[i] = st;
7.319 + break;
7.320 + case IN_HEAP:
7.321 + break;
7.322 + }
7.323 + }
7.324 +
7.325 + private:
7.326 +
7.327 + void balance() {
7.328 +
7.329 + int maxdeg=int( std::floor( 2.08*log(double(_data.size()))))+1;
7.330 +
7.331 + std::vector<int> A(maxdeg,-1);
7.332 +
7.333 + /*
7.334 + *Recall that now minimum does not point to the minimum prio element.
7.335 + *We set minimum to this during balance().
7.336 + */
7.337 + int anchor=_data[_minimum].left_neighbor;
7.338 + int next=_minimum;
7.339 + bool end=false;
7.340 +
7.341 + do {
7.342 + int active=next;
7.343 + if ( anchor==active ) end=true;
7.344 + int d=_data[active].degree;
7.345 + next=_data[active].right_neighbor;
7.346 +
7.347 + while (A[d]!=-1) {
7.348 + if( _comp(_data[active].prio, _data[A[d]].prio) ) {
7.349 + fuse(active,A[d]);
7.350 + } else {
7.351 + fuse(A[d],active);
7.352 + active=A[d];
7.353 + }
7.354 + A[d]=-1;
7.355 + ++d;
7.356 + }
7.357 + A[d]=active;
7.358 + } while ( !end );
7.359 +
7.360 +
7.361 + while ( _data[_minimum].parent >=0 )
7.362 + _minimum=_data[_minimum].parent;
7.363 + int s=_minimum;
7.364 + int m=_minimum;
7.365 + do {
7.366 + if ( _comp(_data[s].prio, _data[_minimum].prio) ) _minimum=s;
7.367 + s=_data[s].right_neighbor;
7.368 + } while ( s != m );
7.369 + }
7.370 +
7.371 + void makeroot(int c) {
7.372 + int s=c;
7.373 + do {
7.374 + _data[s].parent=-1;
7.375 + s=_data[s].right_neighbor;
7.376 + } while ( s != c );
7.377 + }
7.378 +
7.379 + void cut(int a, int b) {
7.380 + /*
7.381 + *Replacing a from the children of b.
7.382 + */
7.383 + --_data[b].degree;
7.384 +
7.385 + if ( _data[b].degree !=0 ) {
7.386 + int child=_data[b].child;
7.387 + if ( child==a )
7.388 + _data[b].child=_data[child].right_neighbor;
7.389 + unlace(a);
7.390 + }
7.391 +
7.392 +
7.393 + /*Lacing a to the roots.*/
7.394 + int right=_data[_minimum].right_neighbor;
7.395 + _data[_minimum].right_neighbor=a;
7.396 + _data[a].left_neighbor=_minimum;
7.397 + _data[a].right_neighbor=right;
7.398 + _data[right].left_neighbor=a;
7.399 +
7.400 + _data[a].parent=-1;
7.401 + _data[a].marked=false;
7.402 + }
7.403 +
7.404 + void cascade(int a) {
7.405 + if ( _data[a].parent!=-1 ) {
7.406 + int p=_data[a].parent;
7.407 +
7.408 + if ( _data[a].marked==false ) _data[a].marked=true;
7.409 + else {
7.410 + cut(a,p);
7.411 + cascade(p);
7.412 + }
7.413 + }
7.414 + }
7.415 +
7.416 + void fuse(int a, int b) {
7.417 + unlace(b);
7.418 +
7.419 + /*Lacing b under a.*/
7.420 + _data[b].parent=a;
7.421 +
7.422 + if (_data[a].degree==0) {
7.423 + _data[b].left_neighbor=b;
7.424 + _data[b].right_neighbor=b;
7.425 + _data[a].child=b;
7.426 + } else {
7.427 + int child=_data[a].child;
7.428 + int last_child=_data[child].left_neighbor;
7.429 + _data[child].left_neighbor=b;
7.430 + _data[b].right_neighbor=child;
7.431 + _data[last_child].right_neighbor=b;
7.432 + _data[b].left_neighbor=last_child;
7.433 + }
7.434 +
7.435 + ++_data[a].degree;
7.436 +
7.437 + _data[b].marked=false;
7.438 + }
7.439 +
7.440 + /*
7.441 + *It is invoked only if a has siblings.
7.442 + */
7.443 + void unlace(int a) {
7.444 + int leftn=_data[a].left_neighbor;
7.445 + int rightn=_data[a].right_neighbor;
7.446 + _data[leftn].right_neighbor=rightn;
7.447 + _data[rightn].left_neighbor=leftn;
7.448 + }
7.449 +
7.450 +
7.451 + class Store {
7.452 + friend class FibHeap;
7.453 +
7.454 + Item name;
7.455 + int parent;
7.456 + int left_neighbor;
7.457 + int right_neighbor;
7.458 + int child;
7.459 + int degree;
7.460 + bool marked;
7.461 + bool in;
7.462 + Prio prio;
7.463 +
7.464 + Store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
7.465 + };
7.466 + };
7.467 +
7.468 +} //namespace lemon
7.469 +
7.470 +#endif //LEMON_FIB_HEAP_H
7.471 +
8.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
8.2 +++ b/lemon/radix_heap.h Wed Jul 13 14:40:05 2011 +0200
8.3 @@ -0,0 +1,433 @@
8.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
8.5 + *
8.6 + * This file is a part of LEMON, a generic C++ optimization library.
8.7 + *
8.8 + * Copyright (C) 2003-2009
8.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
8.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
8.11 + *
8.12 + * Permission to use, modify and distribute this software is granted
8.13 + * provided that this copyright notice appears in all copies. For
8.14 + * precise terms see the accompanying LICENSE file.
8.15 + *
8.16 + * This software is provided "AS IS" with no warranty of any kind,
8.17 + * express or implied, and with no claim as to its suitability for any
8.18 + * purpose.
8.19 + *
8.20 + */
8.21 +
8.22 +#ifndef LEMON_RADIX_HEAP_H
8.23 +#define LEMON_RADIX_HEAP_H
8.24 +
8.25 +///\ingroup auxdat
8.26 +///\file
8.27 +///\brief Radix Heap implementation.
8.28 +
8.29 +#include <vector>
8.30 +#include <lemon/error.h>
8.31 +
8.32 +namespace lemon {
8.33 +
8.34 +
8.35 + /// \ingroup auxdata
8.36 + ///
8.37 + /// \brief A Radix Heap implementation.
8.38 + ///
8.39 + /// This class implements the \e radix \e heap data structure. A \e heap
8.40 + /// is a data structure for storing items with specified values called \e
8.41 + /// priorities in such a way that finding the item with minimum priority is
8.42 + /// efficient. This heap type can store only items with \e int priority.
8.43 + /// In a heap one can change the priority of an item, add or erase an
8.44 + /// item, but the priority cannot be decreased under the last removed
8.45 + /// item's priority.
8.46 + ///
8.47 + /// \param IM A read and writable Item int map, used internally
8.48 + /// to handle the cross references.
8.49 + ///
8.50 + /// \see BinHeap
8.51 + /// \see Dijkstra
8.52 + template <typename IM>
8.53 + class RadixHeap {
8.54 +
8.55 + public:
8.56 + typedef typename IM::Key Item;
8.57 + typedef int Prio;
8.58 + typedef IM ItemIntMap;
8.59 +
8.60 + /// \brief Exception thrown by RadixHeap.
8.61 + ///
8.62 + /// This Exception is thrown when a smaller priority
8.63 + /// is inserted into the \e RadixHeap then the last time erased.
8.64 + /// \see RadixHeap
8.65 +
8.66 + class UnderFlowPriorityError : public Exception {
8.67 + public:
8.68 + virtual const char* what() const throw() {
8.69 + return "lemon::RadixHeap::UnderFlowPriorityError";
8.70 + }
8.71 + };
8.72 +
8.73 + /// \brief Type to represent the items states.
8.74 + ///
8.75 + /// Each Item element have a state associated to it. It may be "in heap",
8.76 + /// "pre heap" or "post heap". The latter two are indifferent from the
8.77 + /// heap's point of view, but may be useful to the user.
8.78 + ///
8.79 + /// The ItemIntMap \e should be initialized in such way that it maps
8.80 + /// PRE_HEAP (-1) to any element to be put in the heap...
8.81 + enum State {
8.82 + IN_HEAP = 0,
8.83 + PRE_HEAP = -1,
8.84 + POST_HEAP = -2
8.85 + };
8.86 +
8.87 + private:
8.88 +
8.89 + struct RadixItem {
8.90 + int prev, next, box;
8.91 + Item item;
8.92 + int prio;
8.93 + RadixItem(Item _item, int _prio) : item(_item), prio(_prio) {}
8.94 + };
8.95 +
8.96 + struct RadixBox {
8.97 + int first;
8.98 + int min, size;
8.99 + RadixBox(int _min, int _size) : first(-1), min(_min), size(_size) {}
8.100 + };
8.101 +
8.102 + std::vector<RadixItem> data;
8.103 + std::vector<RadixBox> boxes;
8.104 +
8.105 + ItemIntMap &_iim;
8.106 +
8.107 +
8.108 + public:
8.109 + /// \brief The constructor.
8.110 + ///
8.111 + /// The constructor.
8.112 + ///
8.113 + /// \param map It should be given to the constructor, since it is used
8.114 + /// internally to handle the cross references. The value of the map
8.115 + /// should be PRE_HEAP (-1) for each element.
8.116 + ///
8.117 + /// \param minimal The initial minimal value of the heap.
8.118 + /// \param capacity It determines the initial capacity of the heap.
8.119 + RadixHeap(ItemIntMap &map, int minimal = 0, int capacity = 0)
8.120 + : _iim(map) {
8.121 + boxes.push_back(RadixBox(minimal, 1));
8.122 + boxes.push_back(RadixBox(minimal + 1, 1));
8.123 + while (lower(boxes.size() - 1, capacity + minimal - 1)) {
8.124 + extend();
8.125 + }
8.126 + }
8.127 +
8.128 + /// The number of items stored in the heap.
8.129 + ///
8.130 + /// \brief Returns the number of items stored in the heap.
8.131 + int size() const { return data.size(); }
8.132 + /// \brief Checks if the heap stores no items.
8.133 + ///
8.134 + /// Returns \c true if and only if the heap stores no items.
8.135 + bool empty() const { return data.empty(); }
8.136 +
8.137 + /// \brief Make empty this heap.
8.138 + ///
8.139 + /// Make empty this heap. It does not change the cross reference
8.140 + /// map. If you want to reuse a heap what is not surely empty you
8.141 + /// should first clear the heap and after that you should set the
8.142 + /// cross reference map for each item to \c PRE_HEAP.
8.143 + void clear(int minimal = 0, int capacity = 0) {
8.144 + data.clear(); boxes.clear();
8.145 + boxes.push_back(RadixBox(minimal, 1));
8.146 + boxes.push_back(RadixBox(minimal + 1, 1));
8.147 + while (lower(boxes.size() - 1, capacity + minimal - 1)) {
8.148 + extend();
8.149 + }
8.150 + }
8.151 +
8.152 + private:
8.153 +
8.154 + bool upper(int box, Prio pr) {
8.155 + return pr < boxes[box].min;
8.156 + }
8.157 +
8.158 + bool lower(int box, Prio pr) {
8.159 + return pr >= boxes[box].min + boxes[box].size;
8.160 + }
8.161 +
8.162 + /// \brief Remove item from the box list.
8.163 + void remove(int index) {
8.164 + if (data[index].prev >= 0) {
8.165 + data[data[index].prev].next = data[index].next;
8.166 + } else {
8.167 + boxes[data[index].box].first = data[index].next;
8.168 + }
8.169 + if (data[index].next >= 0) {
8.170 + data[data[index].next].prev = data[index].prev;
8.171 + }
8.172 + }
8.173 +
8.174 + /// \brief Insert item into the box list.
8.175 + void insert(int box, int index) {
8.176 + if (boxes[box].first == -1) {
8.177 + boxes[box].first = index;
8.178 + data[index].next = data[index].prev = -1;
8.179 + } else {
8.180 + data[index].next = boxes[box].first;
8.181 + data[boxes[box].first].prev = index;
8.182 + data[index].prev = -1;
8.183 + boxes[box].first = index;
8.184 + }
8.185 + data[index].box = box;
8.186 + }
8.187 +
8.188 + /// \brief Add a new box to the box list.
8.189 + void extend() {
8.190 + int min = boxes.back().min + boxes.back().size;
8.191 + int bs = 2 * boxes.back().size;
8.192 + boxes.push_back(RadixBox(min, bs));
8.193 + }
8.194 +
8.195 + /// \brief Move an item up into the proper box.
8.196 + void bubble_up(int index) {
8.197 + if (!lower(data[index].box, data[index].prio)) return;
8.198 + remove(index);
8.199 + int box = findUp(data[index].box, data[index].prio);
8.200 + insert(box, index);
8.201 + }
8.202 +
8.203 + /// \brief Find up the proper box for the item with the given prio.
8.204 + int findUp(int start, int pr) {
8.205 + while (lower(start, pr)) {
8.206 + if (++start == int(boxes.size())) {
8.207 + extend();
8.208 + }
8.209 + }
8.210 + return start;
8.211 + }
8.212 +
8.213 + /// \brief Move an item down into the proper box.
8.214 + void bubble_down(int index) {
8.215 + if (!upper(data[index].box, data[index].prio)) return;
8.216 + remove(index);
8.217 + int box = findDown(data[index].box, data[index].prio);
8.218 + insert(box, index);
8.219 + }
8.220 +
8.221 + /// \brief Find up the proper box for the item with the given prio.
8.222 + int findDown(int start, int pr) {
8.223 + while (upper(start, pr)) {
8.224 + if (--start < 0) throw UnderFlowPriorityError();
8.225 + }
8.226 + return start;
8.227 + }
8.228 +
8.229 + /// \brief Find the first not empty box.
8.230 + int findFirst() {
8.231 + int first = 0;
8.232 + while (boxes[first].first == -1) ++first;
8.233 + return first;
8.234 + }
8.235 +
8.236 + /// \brief Gives back the minimal prio of the box.
8.237 + int minValue(int box) {
8.238 + int min = data[boxes[box].first].prio;
8.239 + for (int k = boxes[box].first; k != -1; k = data[k].next) {
8.240 + if (data[k].prio < min) min = data[k].prio;
8.241 + }
8.242 + return min;
8.243 + }
8.244 +
8.245 + /// \brief Rearrange the items of the heap and makes the
8.246 + /// first box not empty.
8.247 + void moveDown() {
8.248 + int box = findFirst();
8.249 + if (box == 0) return;
8.250 + int min = minValue(box);
8.251 + for (int i = 0; i <= box; ++i) {
8.252 + boxes[i].min = min;
8.253 + min += boxes[i].size;
8.254 + }
8.255 + int curr = boxes[box].first, next;
8.256 + while (curr != -1) {
8.257 + next = data[curr].next;
8.258 + bubble_down(curr);
8.259 + curr = next;
8.260 + }
8.261 + }
8.262 +
8.263 + void relocate_last(int index) {
8.264 + if (index != int(data.size()) - 1) {
8.265 + data[index] = data.back();
8.266 + if (data[index].prev != -1) {
8.267 + data[data[index].prev].next = index;
8.268 + } else {
8.269 + boxes[data[index].box].first = index;
8.270 + }
8.271 + if (data[index].next != -1) {
8.272 + data[data[index].next].prev = index;
8.273 + }
8.274 + _iim[data[index].item] = index;
8.275 + }
8.276 + data.pop_back();
8.277 + }
8.278 +
8.279 + public:
8.280 +
8.281 + /// \brief Insert an item into the heap with the given priority.
8.282 + ///
8.283 + /// Adds \c i to the heap with priority \c p.
8.284 + /// \param i The item to insert.
8.285 + /// \param p The priority of the item.
8.286 + void push(const Item &i, const Prio &p) {
8.287 + int n = data.size();
8.288 + _iim.set(i, n);
8.289 + data.push_back(RadixItem(i, p));
8.290 + while (lower(boxes.size() - 1, p)) {
8.291 + extend();
8.292 + }
8.293 + int box = findDown(boxes.size() - 1, p);
8.294 + insert(box, n);
8.295 + }
8.296 +
8.297 + /// \brief Returns the item with minimum priority.
8.298 + ///
8.299 + /// This method returns the item with minimum priority.
8.300 + /// \pre The heap must be nonempty.
8.301 + Item top() const {
8.302 + const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
8.303 + return data[boxes[0].first].item;
8.304 + }
8.305 +
8.306 + /// \brief Returns the minimum priority.
8.307 + ///
8.308 + /// It returns the minimum priority.
8.309 + /// \pre The heap must be nonempty.
8.310 + Prio prio() const {
8.311 + const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
8.312 + return data[boxes[0].first].prio;
8.313 + }
8.314 +
8.315 + /// \brief Deletes the item with minimum priority.
8.316 + ///
8.317 + /// This method deletes the item with minimum priority.
8.318 + /// \pre The heap must be non-empty.
8.319 + void pop() {
8.320 + moveDown();
8.321 + int index = boxes[0].first;
8.322 + _iim[data[index].item] = POST_HEAP;
8.323 + remove(index);
8.324 + relocate_last(index);
8.325 + }
8.326 +
8.327 + /// \brief Deletes \c i from the heap.
8.328 + ///
8.329 + /// This method deletes item \c i from the heap, if \c i was
8.330 + /// already stored in the heap.
8.331 + /// \param i The item to erase.
8.332 + void erase(const Item &i) {
8.333 + int index = _iim[i];
8.334 + _iim[i] = POST_HEAP;
8.335 + remove(index);
8.336 + relocate_last(index);
8.337 + }
8.338 +
8.339 + /// \brief Returns the priority of \c i.
8.340 + ///
8.341 + /// This function returns the priority of item \c i.
8.342 + /// \pre \c i must be in the heap.
8.343 + /// \param i The item.
8.344 + Prio operator[](const Item &i) const {
8.345 + int idx = _iim[i];
8.346 + return data[idx].prio;
8.347 + }
8.348 +
8.349 + /// \brief \c i gets to the heap with priority \c p independently
8.350 + /// if \c i was already there.
8.351 + ///
8.352 + /// This method calls \ref push(\c i, \c p) if \c i is not stored
8.353 + /// in the heap and sets the priority of \c i to \c p otherwise.
8.354 + /// It may throw an \e UnderFlowPriorityException.
8.355 + /// \param i The item.
8.356 + /// \param p The priority.
8.357 + void set(const Item &i, const Prio &p) {
8.358 + int idx = _iim[i];
8.359 + if( idx < 0 ) {
8.360 + push(i, p);
8.361 + }
8.362 + else if( p >= data[idx].prio ) {
8.363 + data[idx].prio = p;
8.364 + bubble_up(idx);
8.365 + } else {
8.366 + data[idx].prio = p;
8.367 + bubble_down(idx);
8.368 + }
8.369 + }
8.370 +
8.371 +
8.372 + /// \brief Decreases the priority of \c i to \c p.
8.373 + ///
8.374 + /// This method decreases the priority of item \c i to \c p.
8.375 + /// \pre \c i must be stored in the heap with priority at least \c p, and
8.376 + /// \c should be greater or equal to the last removed item's priority.
8.377 + /// \param i The item.
8.378 + /// \param p The priority.
8.379 + void decrease(const Item &i, const Prio &p) {
8.380 + int idx = _iim[i];
8.381 + data[idx].prio = p;
8.382 + bubble_down(idx);
8.383 + }
8.384 +
8.385 + /// \brief Increases the priority of \c i to \c p.
8.386 + ///
8.387 + /// This method sets the priority of item \c i to \c p.
8.388 + /// \pre \c i must be stored in the heap with priority at most \c p
8.389 + /// \param i The item.
8.390 + /// \param p The priority.
8.391 + void increase(const Item &i, const Prio &p) {
8.392 + int idx = _iim[i];
8.393 + data[idx].prio = p;
8.394 + bubble_up(idx);
8.395 + }
8.396 +
8.397 + /// \brief Returns if \c item is in, has already been in, or has
8.398 + /// never been in the heap.
8.399 + ///
8.400 + /// This method returns PRE_HEAP if \c item has never been in the
8.401 + /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
8.402 + /// otherwise. In the latter case it is possible that \c item will
8.403 + /// get back to the heap again.
8.404 + /// \param i The item.
8.405 + State state(const Item &i) const {
8.406 + int s = _iim[i];
8.407 + if( s >= 0 ) s = 0;
8.408 + return State(s);
8.409 + }
8.410 +
8.411 + /// \brief Sets the state of the \c item in the heap.
8.412 + ///
8.413 + /// Sets the state of the \c item in the heap. It can be used to
8.414 + /// manually clear the heap when it is important to achive the
8.415 + /// better time complexity.
8.416 + /// \param i The item.
8.417 + /// \param st The state. It should not be \c IN_HEAP.
8.418 + void state(const Item& i, State st) {
8.419 + switch (st) {
8.420 + case POST_HEAP:
8.421 + case PRE_HEAP:
8.422 + if (state(i) == IN_HEAP) {
8.423 + erase(i);
8.424 + }
8.425 + _iim[i] = st;
8.426 + break;
8.427 + case IN_HEAP:
8.428 + break;
8.429 + }
8.430 + }
8.431 +
8.432 + }; // class RadixHeap
8.433 +
8.434 +} // namespace lemon
8.435 +
8.436 +#endif // LEMON_RADIX_HEAP_H
9.1 --- a/test/CMakeLists.txt Tue Apr 12 07:46:34 2011 +0200
9.2 +++ b/test/CMakeLists.txt Wed Jul 13 14:40:05 2011 +0200
9.3 @@ -65,6 +65,7 @@
9.4
9.5 TARGET_LINK_LIBRARIES(lp_test ${LP_TEST_LIBS})
9.6 ADD_TEST(lp_test lp_test)
9.7 + ADD_DEPENDENCIES(check lp_test)
9.8
9.9 IF(WIN32 AND LEMON_HAVE_GLPK)
9.10 GET_TARGET_PROPERTY(TARGET_LOC lp_test LOCATION)
9.11 @@ -106,6 +107,7 @@
9.12
9.13 TARGET_LINK_LIBRARIES(mip_test ${MIP_TEST_LIBS})
9.14 ADD_TEST(mip_test mip_test)
9.15 + ADD_DEPENDENCIES(check mip_test)
9.16
9.17 IF(WIN32 AND LEMON_HAVE_GLPK)
9.18 GET_TARGET_PROPERTY(TARGET_LOC mip_test LOCATION)
10.1 --- a/test/heap_test.cc Tue Apr 12 07:46:34 2011 +0200
10.2 +++ b/test/heap_test.cc Wed Jul 13 14:40:05 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 }