1.1 --- a/lemon/Makefile.am Fri May 29 17:46:48 2009 +0100
1.2 +++ b/lemon/Makefile.am Thu Jun 11 22:11:29 2009 +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 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/bucket_heap.h Thu Jun 11 22:11:29 2009 +0200
2.3 @@ -0,0 +1,831 @@
2.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
2.5 + *
2.6 + * This file is a part of LEMON, a generic C++ optimization library.
2.7 + *
2.8 + * Copyright (C) 2003-2009
2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.11 + *
2.12 + * Permission to use, modify and distribute this software is granted
2.13 + * provided that this copyright notice appears in all copies. For
2.14 + * precise terms see the accompanying LICENSE file.
2.15 + *
2.16 + * This software is provided "AS IS" with no warranty of any kind,
2.17 + * express or implied, and with no claim as to its suitability for any
2.18 + * purpose.
2.19 + *
2.20 + */
2.21 +
2.22 +#ifndef LEMON_BUCKET_HEAP_H
2.23 +#define LEMON_BUCKET_HEAP_H
2.24 +
2.25 +///\ingroup auxdat
2.26 +///\file
2.27 +///\brief Bucket Heap implementation.
2.28 +
2.29 +#include <vector>
2.30 +#include <utility>
2.31 +#include <functional>
2.32 +
2.33 +namespace lemon {
2.34 +
2.35 + /// \ingroup auxdat
2.36 + ///
2.37 + /// \brief A Bucket Heap implementation.
2.38 + ///
2.39 + /// This class implements the \e bucket \e heap data structure. A \e heap
2.40 + /// is a data structure for storing items with specified values called \e
2.41 + /// priorities in such a way that finding the item with minimum priority is
2.42 + /// efficient. The bucket heap is very simple implementation, it can store
2.43 + /// only integer priorities and it stores for each priority in the
2.44 + /// \f$ [0..C) \f$ range a list of items. So it should be used only when
2.45 + /// the priorities are small. It is not intended to use as dijkstra heap.
2.46 + ///
2.47 + /// \param _ItemIntMap A read and writable Item int map, used internally
2.48 + /// to handle the cross references.
2.49 + /// \param minimize If the given parameter is true then the heap gives back
2.50 + /// the lowest priority.
2.51 + template <typename _ItemIntMap, bool minimize = true >
2.52 + class BucketHeap {
2.53 +
2.54 + public:
2.55 + /// \e
2.56 + typedef typename _ItemIntMap::Key Item;
2.57 + /// \e
2.58 + typedef int Prio;
2.59 + /// \e
2.60 + typedef std::pair<Item, Prio> Pair;
2.61 + /// \e
2.62 + typedef _ItemIntMap ItemIntMap;
2.63 +
2.64 + /// \brief Type to represent the items states.
2.65 + ///
2.66 + /// Each Item element have a state associated to it. It may be "in heap",
2.67 + /// "pre heap" or "post heap". The latter two are indifferent from the
2.68 + /// heap's point of view, but may be useful to the user.
2.69 + ///
2.70 + /// The ItemIntMap \e should be initialized in such way that it maps
2.71 + /// PRE_HEAP (-1) to any element to be put in the heap...
2.72 + enum State {
2.73 + IN_HEAP = 0,
2.74 + PRE_HEAP = -1,
2.75 + POST_HEAP = -2
2.76 + };
2.77 +
2.78 + public:
2.79 + /// \brief The constructor.
2.80 + ///
2.81 + /// The constructor.
2.82 + /// \param _index should be given to the constructor, since it is used
2.83 + /// internally to handle the cross references. The value of the map
2.84 + /// should be PRE_HEAP (-1) for each element.
2.85 + explicit BucketHeap(ItemIntMap &_index) : index(_index), minimal(0) {}
2.86 +
2.87 + /// The number of items stored in the heap.
2.88 + ///
2.89 + /// \brief Returns the number of items stored in the heap.
2.90 + int size() const { return data.size(); }
2.91 +
2.92 + /// \brief Checks if the heap stores no items.
2.93 + ///
2.94 + /// Returns \c true if and only if the heap stores no items.
2.95 + bool empty() const { return data.empty(); }
2.96 +
2.97 + /// \brief Make empty this heap.
2.98 + ///
2.99 + /// Make empty this heap. It does not change the cross reference
2.100 + /// map. If you want to reuse a heap what is not surely empty you
2.101 + /// should first clear the heap and after that you should set the
2.102 + /// cross reference map for each item to \c PRE_HEAP.
2.103 + void clear() {
2.104 + data.clear(); first.clear(); minimal = 0;
2.105 + }
2.106 +
2.107 + private:
2.108 +
2.109 + void relocate_last(int idx) {
2.110 + if (idx + 1 < int(data.size())) {
2.111 + data[idx] = data.back();
2.112 + if (data[idx].prev != -1) {
2.113 + data[data[idx].prev].next = idx;
2.114 + } else {
2.115 + first[data[idx].value] = idx;
2.116 + }
2.117 + if (data[idx].next != -1) {
2.118 + data[data[idx].next].prev = idx;
2.119 + }
2.120 + index[data[idx].item] = idx;
2.121 + }
2.122 + data.pop_back();
2.123 + }
2.124 +
2.125 + void unlace(int idx) {
2.126 + if (data[idx].prev != -1) {
2.127 + data[data[idx].prev].next = data[idx].next;
2.128 + } else {
2.129 + first[data[idx].value] = data[idx].next;
2.130 + }
2.131 + if (data[idx].next != -1) {
2.132 + data[data[idx].next].prev = data[idx].prev;
2.133 + }
2.134 + }
2.135 +
2.136 + void lace(int idx) {
2.137 + if (int(first.size()) <= data[idx].value) {
2.138 + first.resize(data[idx].value + 1, -1);
2.139 + }
2.140 + data[idx].next = first[data[idx].value];
2.141 + if (data[idx].next != -1) {
2.142 + data[data[idx].next].prev = idx;
2.143 + }
2.144 + first[data[idx].value] = idx;
2.145 + data[idx].prev = -1;
2.146 + }
2.147 +
2.148 + public:
2.149 + /// \brief Insert a pair of item and priority into the heap.
2.150 + ///
2.151 + /// Adds \c p.first to the heap with priority \c p.second.
2.152 + /// \param p The pair to insert.
2.153 + void push(const Pair& p) {
2.154 + push(p.first, p.second);
2.155 + }
2.156 +
2.157 + /// \brief Insert an item into the heap with the given priority.
2.158 + ///
2.159 + /// Adds \c i to the heap with priority \c p.
2.160 + /// \param i The item to insert.
2.161 + /// \param p The priority of the item.
2.162 + void push(const Item &i, const Prio &p) {
2.163 + int idx = data.size();
2.164 + index[i] = idx;
2.165 + data.push_back(BucketItem(i, p));
2.166 + lace(idx);
2.167 + if (p < minimal) {
2.168 + minimal = p;
2.169 + }
2.170 + }
2.171 +
2.172 + /// \brief Returns the item with minimum priority.
2.173 + ///
2.174 + /// This method returns the item with minimum priority.
2.175 + /// \pre The heap must be nonempty.
2.176 + Item top() const {
2.177 + while (first[minimal] == -1) {
2.178 + ++minimal;
2.179 + }
2.180 + return data[first[minimal]].item;
2.181 + }
2.182 +
2.183 + /// \brief Returns the minimum priority.
2.184 + ///
2.185 + /// It returns the minimum priority.
2.186 + /// \pre The heap must be nonempty.
2.187 + Prio prio() const {
2.188 + while (first[minimal] == -1) {
2.189 + ++minimal;
2.190 + }
2.191 + return minimal;
2.192 + }
2.193 +
2.194 + /// \brief Deletes the item with minimum priority.
2.195 + ///
2.196 + /// This method deletes the item with minimum priority from the heap.
2.197 + /// \pre The heap must be non-empty.
2.198 + void pop() {
2.199 + while (first[minimal] == -1) {
2.200 + ++minimal;
2.201 + }
2.202 + int idx = first[minimal];
2.203 + index[data[idx].item] = -2;
2.204 + unlace(idx);
2.205 + relocate_last(idx);
2.206 + }
2.207 +
2.208 + /// \brief Deletes \c i from the heap.
2.209 + ///
2.210 + /// This method deletes item \c i from the heap, if \c i was
2.211 + /// already stored in the heap.
2.212 + /// \param i The item to erase.
2.213 + void erase(const Item &i) {
2.214 + int idx = index[i];
2.215 + index[data[idx].item] = -2;
2.216 + unlace(idx);
2.217 + relocate_last(idx);
2.218 + }
2.219 +
2.220 +
2.221 + /// \brief Returns the priority of \c i.
2.222 + ///
2.223 + /// This function returns the priority of item \c i.
2.224 + /// \pre \c i must be in the heap.
2.225 + /// \param i The item.
2.226 + Prio operator[](const Item &i) const {
2.227 + int idx = index[i];
2.228 + return data[idx].value;
2.229 + }
2.230 +
2.231 + /// \brief \c i gets to the heap with priority \c p independently
2.232 + /// if \c i was already there.
2.233 + ///
2.234 + /// This method calls \ref push(\c i, \c p) if \c i is not stored
2.235 + /// in the heap and sets the priority of \c i to \c p otherwise.
2.236 + /// \param i The item.
2.237 + /// \param p The priority.
2.238 + void set(const Item &i, const Prio &p) {
2.239 + int idx = index[i];
2.240 + if (idx < 0) {
2.241 + push(i,p);
2.242 + } else if (p > data[idx].value) {
2.243 + increase(i, p);
2.244 + } else {
2.245 + decrease(i, p);
2.246 + }
2.247 + }
2.248 +
2.249 + /// \brief Decreases the priority of \c i to \c p.
2.250 + ///
2.251 + /// This method decreases the priority of item \c i to \c p.
2.252 + /// \pre \c i must be stored in the heap with priority at least \c
2.253 + /// p relative to \c Compare.
2.254 + /// \param i The item.
2.255 + /// \param p The priority.
2.256 + void decrease(const Item &i, const Prio &p) {
2.257 + int idx = index[i];
2.258 + unlace(idx);
2.259 + data[idx].value = p;
2.260 + if (p < minimal) {
2.261 + minimal = p;
2.262 + }
2.263 + lace(idx);
2.264 + }
2.265 +
2.266 + /// \brief Increases the priority of \c i to \c p.
2.267 + ///
2.268 + /// This method sets the priority of item \c i to \c p.
2.269 + /// \pre \c i must be stored in the heap with priority at most \c
2.270 + /// p relative to \c Compare.
2.271 + /// \param i The item.
2.272 + /// \param p The priority.
2.273 + void increase(const Item &i, const Prio &p) {
2.274 + int idx = index[i];
2.275 + unlace(idx);
2.276 + data[idx].value = p;
2.277 + lace(idx);
2.278 + }
2.279 +
2.280 + /// \brief Returns if \c item is in, has already been in, or has
2.281 + /// never been in the heap.
2.282 + ///
2.283 + /// This method returns PRE_HEAP if \c item has never been in the
2.284 + /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
2.285 + /// otherwise. In the latter case it is possible that \c item will
2.286 + /// get back to the heap again.
2.287 + /// \param i The item.
2.288 + State state(const Item &i) const {
2.289 + int idx = index[i];
2.290 + if (idx >= 0) idx = 0;
2.291 + return State(idx);
2.292 + }
2.293 +
2.294 + /// \brief Sets the state of the \c item in the heap.
2.295 + ///
2.296 + /// Sets the state of the \c item in the heap. It can be used to
2.297 + /// manually clear the heap when it is important to achive the
2.298 + /// better time complexity.
2.299 + /// \param i The item.
2.300 + /// \param st The state. It should not be \c IN_HEAP.
2.301 + void state(const Item& i, State st) {
2.302 + switch (st) {
2.303 + case POST_HEAP:
2.304 + case PRE_HEAP:
2.305 + if (state(i) == IN_HEAP) {
2.306 + erase(i);
2.307 + }
2.308 + index[i] = st;
2.309 + break;
2.310 + case IN_HEAP:
2.311 + break;
2.312 + }
2.313 + }
2.314 +
2.315 + private:
2.316 +
2.317 + struct BucketItem {
2.318 + BucketItem(const Item& _item, int _value)
2.319 + : item(_item), value(_value) {}
2.320 +
2.321 + Item item;
2.322 + int value;
2.323 +
2.324 + int prev, next;
2.325 + };
2.326 +
2.327 + ItemIntMap& index;
2.328 + std::vector<int> first;
2.329 + std::vector<BucketItem> data;
2.330 + mutable int minimal;
2.331 +
2.332 + }; // class BucketHeap
2.333 +
2.334 +
2.335 + template <typename _ItemIntMap>
2.336 + class BucketHeap<_ItemIntMap, false> {
2.337 +
2.338 + public:
2.339 + typedef typename _ItemIntMap::Key Item;
2.340 + typedef int Prio;
2.341 + typedef std::pair<Item, Prio> Pair;
2.342 + typedef _ItemIntMap ItemIntMap;
2.343 +
2.344 + enum State {
2.345 + IN_HEAP = 0,
2.346 + PRE_HEAP = -1,
2.347 + POST_HEAP = -2
2.348 + };
2.349 +
2.350 + public:
2.351 +
2.352 + explicit BucketHeap(ItemIntMap &_index) : index(_index), maximal(-1) {}
2.353 +
2.354 + int size() const { return data.size(); }
2.355 + bool empty() const { return data.empty(); }
2.356 +
2.357 + void clear() {
2.358 + data.clear(); first.clear(); maximal = -1;
2.359 + }
2.360 +
2.361 + private:
2.362 +
2.363 + void relocate_last(int idx) {
2.364 + if (idx + 1 != int(data.size())) {
2.365 + data[idx] = data.back();
2.366 + if (data[idx].prev != -1) {
2.367 + data[data[idx].prev].next = idx;
2.368 + } else {
2.369 + first[data[idx].value] = idx;
2.370 + }
2.371 + if (data[idx].next != -1) {
2.372 + data[data[idx].next].prev = idx;
2.373 + }
2.374 + index[data[idx].item] = idx;
2.375 + }
2.376 + data.pop_back();
2.377 + }
2.378 +
2.379 + void unlace(int idx) {
2.380 + if (data[idx].prev != -1) {
2.381 + data[data[idx].prev].next = data[idx].next;
2.382 + } else {
2.383 + first[data[idx].value] = data[idx].next;
2.384 + }
2.385 + if (data[idx].next != -1) {
2.386 + data[data[idx].next].prev = data[idx].prev;
2.387 + }
2.388 + }
2.389 +
2.390 + void lace(int idx) {
2.391 + if (int(first.size()) <= data[idx].value) {
2.392 + first.resize(data[idx].value + 1, -1);
2.393 + }
2.394 + data[idx].next = first[data[idx].value];
2.395 + if (data[idx].next != -1) {
2.396 + data[data[idx].next].prev = idx;
2.397 + }
2.398 + first[data[idx].value] = idx;
2.399 + data[idx].prev = -1;
2.400 + }
2.401 +
2.402 + public:
2.403 +
2.404 + void push(const Pair& p) {
2.405 + push(p.first, p.second);
2.406 + }
2.407 +
2.408 + void push(const Item &i, const Prio &p) {
2.409 + int idx = data.size();
2.410 + index[i] = idx;
2.411 + data.push_back(BucketItem(i, p));
2.412 + lace(idx);
2.413 + if (data[idx].value > maximal) {
2.414 + maximal = data[idx].value;
2.415 + }
2.416 + }
2.417 +
2.418 + Item top() const {
2.419 + while (first[maximal] == -1) {
2.420 + --maximal;
2.421 + }
2.422 + return data[first[maximal]].item;
2.423 + }
2.424 +
2.425 + Prio prio() const {
2.426 + while (first[maximal] == -1) {
2.427 + --maximal;
2.428 + }
2.429 + return maximal;
2.430 + }
2.431 +
2.432 + void pop() {
2.433 + while (first[maximal] == -1) {
2.434 + --maximal;
2.435 + }
2.436 + int idx = first[maximal];
2.437 + index[data[idx].item] = -2;
2.438 + unlace(idx);
2.439 + relocate_last(idx);
2.440 + }
2.441 +
2.442 + void erase(const Item &i) {
2.443 + int idx = index[i];
2.444 + index[data[idx].item] = -2;
2.445 + unlace(idx);
2.446 + relocate_last(idx);
2.447 + }
2.448 +
2.449 + Prio operator[](const Item &i) const {
2.450 + int idx = index[i];
2.451 + return data[idx].value;
2.452 + }
2.453 +
2.454 + void set(const Item &i, const Prio &p) {
2.455 + int idx = index[i];
2.456 + if (idx < 0) {
2.457 + push(i,p);
2.458 + } else if (p > data[idx].value) {
2.459 + decrease(i, p);
2.460 + } else {
2.461 + increase(i, p);
2.462 + }
2.463 + }
2.464 +
2.465 + void decrease(const Item &i, const Prio &p) {
2.466 + int idx = index[i];
2.467 + unlace(idx);
2.468 + data[idx].value = p;
2.469 + if (p > maximal) {
2.470 + maximal = p;
2.471 + }
2.472 + lace(idx);
2.473 + }
2.474 +
2.475 + void increase(const Item &i, const Prio &p) {
2.476 + int idx = index[i];
2.477 + unlace(idx);
2.478 + data[idx].value = p;
2.479 + lace(idx);
2.480 + }
2.481 +
2.482 + State state(const Item &i) const {
2.483 + int idx = index[i];
2.484 + if (idx >= 0) idx = 0;
2.485 + return State(idx);
2.486 + }
2.487 +
2.488 + void state(const Item& i, State st) {
2.489 + switch (st) {
2.490 + case POST_HEAP:
2.491 + case PRE_HEAP:
2.492 + if (state(i) == IN_HEAP) {
2.493 + erase(i);
2.494 + }
2.495 + index[i] = st;
2.496 + break;
2.497 + case IN_HEAP:
2.498 + break;
2.499 + }
2.500 + }
2.501 +
2.502 + private:
2.503 +
2.504 + struct BucketItem {
2.505 + BucketItem(const Item& _item, int _value)
2.506 + : item(_item), value(_value) {}
2.507 +
2.508 + Item item;
2.509 + int value;
2.510 +
2.511 + int prev, next;
2.512 + };
2.513 +
2.514 + ItemIntMap& index;
2.515 + std::vector<int> first;
2.516 + std::vector<BucketItem> data;
2.517 + mutable int maximal;
2.518 +
2.519 + }; // class BucketHeap
2.520 +
2.521 + /// \ingroup auxdat
2.522 + ///
2.523 + /// \brief A Simplified Bucket Heap implementation.
2.524 + ///
2.525 + /// This class implements a simplified \e bucket \e heap data
2.526 + /// structure. It does not provide some functionality but it faster
2.527 + /// and simplier data structure than the BucketHeap. The main
2.528 + /// difference is that the BucketHeap stores for every key a double
2.529 + /// linked list while this class stores just simple lists. In the
2.530 + /// other way it does not supports erasing each elements just the
2.531 + /// minimal and it does not supports key increasing, decreasing.
2.532 + ///
2.533 + /// \param _ItemIntMap A read and writable Item int map, used internally
2.534 + /// to handle the cross references.
2.535 + /// \param minimize If the given parameter is true then the heap gives back
2.536 + /// the lowest priority.
2.537 + ///
2.538 + /// \sa BucketHeap
2.539 + template <typename _ItemIntMap, bool minimize = true >
2.540 + class SimpleBucketHeap {
2.541 +
2.542 + public:
2.543 + typedef typename _ItemIntMap::Key Item;
2.544 + typedef int Prio;
2.545 + typedef std::pair<Item, Prio> Pair;
2.546 + typedef _ItemIntMap ItemIntMap;
2.547 +
2.548 + /// \brief Type to represent the items states.
2.549 + ///
2.550 + /// Each Item element have a state associated to it. It may be "in heap",
2.551 + /// "pre heap" or "post heap". The latter two are indifferent from the
2.552 + /// heap's point of view, but may be useful to the user.
2.553 + ///
2.554 + /// The ItemIntMap \e should be initialized in such way that it maps
2.555 + /// PRE_HEAP (-1) to any element to be put in the heap...
2.556 + enum State {
2.557 + IN_HEAP = 0,
2.558 + PRE_HEAP = -1,
2.559 + POST_HEAP = -2
2.560 + };
2.561 +
2.562 + public:
2.563 +
2.564 + /// \brief The constructor.
2.565 + ///
2.566 + /// The constructor.
2.567 + /// \param _index should be given to the constructor, since it is used
2.568 + /// internally to handle the cross references. The value of the map
2.569 + /// should be PRE_HEAP (-1) for each element.
2.570 + explicit SimpleBucketHeap(ItemIntMap &_index)
2.571 + : index(_index), free(-1), num(0), minimal(0) {}
2.572 +
2.573 + /// \brief Returns the number of items stored in the heap.
2.574 + ///
2.575 + /// The number of items stored in the heap.
2.576 + int size() const { return num; }
2.577 +
2.578 + /// \brief Checks if the heap stores no items.
2.579 + ///
2.580 + /// Returns \c true if and only if the heap stores no items.
2.581 + bool empty() const { return num == 0; }
2.582 +
2.583 + /// \brief Make empty this heap.
2.584 + ///
2.585 + /// Make empty this heap. It does not change the cross reference
2.586 + /// map. If you want to reuse a heap what is not surely empty you
2.587 + /// should first clear the heap and after that you should set the
2.588 + /// cross reference map for each item to \c PRE_HEAP.
2.589 + void clear() {
2.590 + data.clear(); first.clear(); free = -1; num = 0; minimal = 0;
2.591 + }
2.592 +
2.593 + /// \brief Insert a pair of item and priority into the heap.
2.594 + ///
2.595 + /// Adds \c p.first to the heap with priority \c p.second.
2.596 + /// \param p The pair to insert.
2.597 + void push(const Pair& p) {
2.598 + push(p.first, p.second);
2.599 + }
2.600 +
2.601 + /// \brief Insert an item into the heap with the given priority.
2.602 + ///
2.603 + /// Adds \c i to the heap with priority \c p.
2.604 + /// \param i The item to insert.
2.605 + /// \param p The priority of the item.
2.606 + void push(const Item &i, const Prio &p) {
2.607 + int idx;
2.608 + if (free == -1) {
2.609 + idx = data.size();
2.610 + data.push_back(BucketItem(i));
2.611 + } else {
2.612 + idx = free;
2.613 + free = data[idx].next;
2.614 + data[idx].item = i;
2.615 + }
2.616 + index[i] = idx;
2.617 + if (p >= int(first.size())) first.resize(p + 1, -1);
2.618 + data[idx].next = first[p];
2.619 + first[p] = idx;
2.620 + if (p < minimal) {
2.621 + minimal = p;
2.622 + }
2.623 + ++num;
2.624 + }
2.625 +
2.626 + /// \brief Returns the item with minimum priority.
2.627 + ///
2.628 + /// This method returns the item with minimum priority.
2.629 + /// \pre The heap must be nonempty.
2.630 + Item top() const {
2.631 + while (first[minimal] == -1) {
2.632 + ++minimal;
2.633 + }
2.634 + return data[first[minimal]].item;
2.635 + }
2.636 +
2.637 + /// \brief Returns the minimum priority.
2.638 + ///
2.639 + /// It returns the minimum priority.
2.640 + /// \pre The heap must be nonempty.
2.641 + Prio prio() const {
2.642 + while (first[minimal] == -1) {
2.643 + ++minimal;
2.644 + }
2.645 + return minimal;
2.646 + }
2.647 +
2.648 + /// \brief Deletes the item with minimum priority.
2.649 + ///
2.650 + /// This method deletes the item with minimum priority from the heap.
2.651 + /// \pre The heap must be non-empty.
2.652 + void pop() {
2.653 + while (first[minimal] == -1) {
2.654 + ++minimal;
2.655 + }
2.656 + int idx = first[minimal];
2.657 + index[data[idx].item] = -2;
2.658 + first[minimal] = data[idx].next;
2.659 + data[idx].next = free;
2.660 + free = idx;
2.661 + --num;
2.662 + }
2.663 +
2.664 + /// \brief Returns the priority of \c i.
2.665 + ///
2.666 + /// This function returns the priority of item \c i.
2.667 + /// \warning This operator is not a constant time function
2.668 + /// because it scans the whole data structure to find the proper
2.669 + /// value.
2.670 + /// \pre \c i must be in the heap.
2.671 + /// \param i The item.
2.672 + Prio operator[](const Item &i) const {
2.673 + for (int k = 0; k < first.size(); ++k) {
2.674 + int idx = first[k];
2.675 + while (idx != -1) {
2.676 + if (data[idx].item == i) {
2.677 + return k;
2.678 + }
2.679 + idx = data[idx].next;
2.680 + }
2.681 + }
2.682 + return -1;
2.683 + }
2.684 +
2.685 + /// \brief Returns if \c item is in, has already been in, or has
2.686 + /// never been in the heap.
2.687 + ///
2.688 + /// This method returns PRE_HEAP if \c item has never been in the
2.689 + /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
2.690 + /// otherwise. In the latter case it is possible that \c item will
2.691 + /// get back to the heap again.
2.692 + /// \param i The item.
2.693 + State state(const Item &i) const {
2.694 + int idx = index[i];
2.695 + if (idx >= 0) idx = 0;
2.696 + return State(idx);
2.697 + }
2.698 +
2.699 + private:
2.700 +
2.701 + struct BucketItem {
2.702 + BucketItem(const Item& _item)
2.703 + : item(_item) {}
2.704 +
2.705 + Item item;
2.706 + int next;
2.707 + };
2.708 +
2.709 + ItemIntMap& index;
2.710 + std::vector<int> first;
2.711 + std::vector<BucketItem> data;
2.712 + int free, num;
2.713 + mutable int minimal;
2.714 +
2.715 + }; // class SimpleBucketHeap
2.716 +
2.717 + template <typename _ItemIntMap>
2.718 + class SimpleBucketHeap<_ItemIntMap, false> {
2.719 +
2.720 + public:
2.721 + typedef typename _ItemIntMap::Key Item;
2.722 + typedef int Prio;
2.723 + typedef std::pair<Item, Prio> Pair;
2.724 + typedef _ItemIntMap ItemIntMap;
2.725 +
2.726 + enum State {
2.727 + IN_HEAP = 0,
2.728 + PRE_HEAP = -1,
2.729 + POST_HEAP = -2
2.730 + };
2.731 +
2.732 + public:
2.733 +
2.734 + explicit SimpleBucketHeap(ItemIntMap &_index)
2.735 + : index(_index), free(-1), num(0), maximal(0) {}
2.736 +
2.737 + int size() const { return num; }
2.738 +
2.739 + bool empty() const { return num == 0; }
2.740 +
2.741 + void clear() {
2.742 + data.clear(); first.clear(); free = -1; num = 0; maximal = 0;
2.743 + }
2.744 +
2.745 + void push(const Pair& p) {
2.746 + push(p.first, p.second);
2.747 + }
2.748 +
2.749 + void push(const Item &i, const Prio &p) {
2.750 + int idx;
2.751 + if (free == -1) {
2.752 + idx = data.size();
2.753 + data.push_back(BucketItem(i));
2.754 + } else {
2.755 + idx = free;
2.756 + free = data[idx].next;
2.757 + data[idx].item = i;
2.758 + }
2.759 + index[i] = idx;
2.760 + if (p >= int(first.size())) first.resize(p + 1, -1);
2.761 + data[idx].next = first[p];
2.762 + first[p] = idx;
2.763 + if (p > maximal) {
2.764 + maximal = p;
2.765 + }
2.766 + ++num;
2.767 + }
2.768 +
2.769 + Item top() const {
2.770 + while (first[maximal] == -1) {
2.771 + --maximal;
2.772 + }
2.773 + return data[first[maximal]].item;
2.774 + }
2.775 +
2.776 + Prio prio() const {
2.777 + while (first[maximal] == -1) {
2.778 + --maximal;
2.779 + }
2.780 + return maximal;
2.781 + }
2.782 +
2.783 + void pop() {
2.784 + while (first[maximal] == -1) {
2.785 + --maximal;
2.786 + }
2.787 + int idx = first[maximal];
2.788 + index[data[idx].item] = -2;
2.789 + first[maximal] = data[idx].next;
2.790 + data[idx].next = free;
2.791 + free = idx;
2.792 + --num;
2.793 + }
2.794 +
2.795 + Prio operator[](const Item &i) const {
2.796 + for (int k = 0; k < first.size(); ++k) {
2.797 + int idx = first[k];
2.798 + while (idx != -1) {
2.799 + if (data[idx].item == i) {
2.800 + return k;
2.801 + }
2.802 + idx = data[idx].next;
2.803 + }
2.804 + }
2.805 + return -1;
2.806 + }
2.807 +
2.808 + State state(const Item &i) const {
2.809 + int idx = index[i];
2.810 + if (idx >= 0) idx = 0;
2.811 + return State(idx);
2.812 + }
2.813 +
2.814 + private:
2.815 +
2.816 + struct BucketItem {
2.817 + BucketItem(const Item& _item) : item(_item) {}
2.818 +
2.819 + Item item;
2.820 +
2.821 + int next;
2.822 + };
2.823 +
2.824 + ItemIntMap& index;
2.825 + std::vector<int> first;
2.826 + std::vector<BucketItem> data;
2.827 + int free, num;
2.828 + mutable int maximal;
2.829 +
2.830 + };
2.831 +
2.832 +}
2.833 +
2.834 +#endif
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/lemon/fib_heap.h Thu Jun 11 22:11:29 2009 +0200
3.3 @@ -0,0 +1,467 @@
3.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
3.5 + *
3.6 + * This file is a part of LEMON, a generic C++ optimization library.
3.7 + *
3.8 + * Copyright (C) 2003-2009
3.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
3.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
3.11 + *
3.12 + * Permission to use, modify and distribute this software is granted
3.13 + * provided that this copyright notice appears in all copies. For
3.14 + * precise terms see the accompanying LICENSE file.
3.15 + *
3.16 + * This software is provided "AS IS" with no warranty of any kind,
3.17 + * express or implied, and with no claim as to its suitability for any
3.18 + * purpose.
3.19 + *
3.20 + */
3.21 +
3.22 +#ifndef LEMON_FIB_HEAP_H
3.23 +#define LEMON_FIB_HEAP_H
3.24 +
3.25 +///\file
3.26 +///\ingroup auxdat
3.27 +///\brief Fibonacci Heap implementation.
3.28 +
3.29 +#include <vector>
3.30 +#include <functional>
3.31 +#include <lemon/math.h>
3.32 +
3.33 +namespace lemon {
3.34 +
3.35 + /// \ingroup auxdat
3.36 + ///
3.37 + ///\brief Fibonacci Heap.
3.38 + ///
3.39 + ///This class implements the \e Fibonacci \e heap data structure. A \e heap
3.40 + ///is a data structure for storing items with specified values called \e
3.41 + ///priorities in such a way that finding the item with minimum priority is
3.42 + ///efficient. \c Compare specifies the ordering of the priorities. In a heap
3.43 + ///one can change the priority of an item, add or erase an item, etc.
3.44 + ///
3.45 + ///The methods \ref increase and \ref erase are not efficient in a Fibonacci
3.46 + ///heap. In case of many calls to these operations, it is better to use a
3.47 + ///\ref BinHeap "binary heap".
3.48 + ///
3.49 + ///\param _Prio Type of the priority of the items.
3.50 + ///\param _ItemIntMap A read and writable Item int map, used internally
3.51 + ///to handle the cross references.
3.52 + ///\param _Compare A class for the ordering of the priorities. The
3.53 + ///default is \c std::less<_Prio>.
3.54 + ///
3.55 + ///\sa BinHeap
3.56 + ///\sa Dijkstra
3.57 +#ifdef DOXYGEN
3.58 + template <typename _Prio,
3.59 + typename _ItemIntMap,
3.60 + typename _Compare>
3.61 +#else
3.62 + template <typename _Prio,
3.63 + typename _ItemIntMap,
3.64 + typename _Compare = std::less<_Prio> >
3.65 +#endif
3.66 + class FibHeap {
3.67 + public:
3.68 + ///\e
3.69 + typedef _ItemIntMap ItemIntMap;
3.70 + ///\e
3.71 + typedef _Prio Prio;
3.72 + ///\e
3.73 + typedef typename ItemIntMap::Key Item;
3.74 + ///\e
3.75 + typedef std::pair<Item,Prio> Pair;
3.76 + ///\e
3.77 + typedef _Compare Compare;
3.78 +
3.79 + private:
3.80 + class store;
3.81 +
3.82 + std::vector<store> container;
3.83 + int minimum;
3.84 + ItemIntMap &iimap;
3.85 + Compare comp;
3.86 + int num_items;
3.87 +
3.88 + public:
3.89 + ///Status of the nodes
3.90 + enum State {
3.91 + ///The node is in the heap
3.92 + IN_HEAP = 0,
3.93 + ///The node has never been in the heap
3.94 + PRE_HEAP = -1,
3.95 + ///The node was in the heap but it got out of it
3.96 + POST_HEAP = -2
3.97 + };
3.98 +
3.99 + /// \brief The constructor
3.100 + ///
3.101 + /// \c _iimap should be given to the constructor, since it is
3.102 + /// used internally to handle the cross references.
3.103 + explicit FibHeap(ItemIntMap &_iimap)
3.104 + : minimum(0), iimap(_iimap), num_items() {}
3.105 +
3.106 + /// \brief The constructor
3.107 + ///
3.108 + /// \c _iimap should be given to the constructor, since it is used
3.109 + /// internally to handle the cross references. \c _comp is an
3.110 + /// object for ordering of the priorities.
3.111 + FibHeap(ItemIntMap &_iimap, const Compare &_comp)
3.112 + : minimum(0), iimap(_iimap), comp(_comp), num_items() {}
3.113 +
3.114 + /// \brief The number of items stored in the heap.
3.115 + ///
3.116 + /// Returns the number of items stored in the heap.
3.117 + int size() const { return num_items; }
3.118 +
3.119 + /// \brief Checks if the heap stores no items.
3.120 + ///
3.121 + /// Returns \c true if and only if the heap stores no items.
3.122 + bool empty() const { return num_items==0; }
3.123 +
3.124 + /// \brief Make empty this heap.
3.125 + ///
3.126 + /// Make empty this heap. It does not change the cross reference
3.127 + /// map. If you want to reuse a heap what is not surely empty you
3.128 + /// should first clear the heap and after that you should set the
3.129 + /// cross reference map for each item to \c PRE_HEAP.
3.130 + void clear() {
3.131 + container.clear(); minimum = 0; num_items = 0;
3.132 + }
3.133 +
3.134 + /// \brief \c item gets to the heap with priority \c value independently
3.135 + /// if \c item was already there.
3.136 + ///
3.137 + /// This method calls \ref push(\c item, \c value) if \c item is not
3.138 + /// stored in the heap and it calls \ref decrease(\c item, \c value) or
3.139 + /// \ref increase(\c item, \c value) otherwise.
3.140 + void set (const Item& item, const Prio& value) {
3.141 + int i=iimap[item];
3.142 + if ( i >= 0 && container[i].in ) {
3.143 + if ( comp(value, container[i].prio) ) decrease(item, value);
3.144 + if ( comp(container[i].prio, value) ) increase(item, value);
3.145 + } else push(item, value);
3.146 + }
3.147 +
3.148 + /// \brief Adds \c item to the heap with priority \c value.
3.149 + ///
3.150 + /// Adds \c item to the heap with priority \c value.
3.151 + /// \pre \c item must not be stored in the heap.
3.152 + void push (const Item& item, const Prio& value) {
3.153 + int i=iimap[item];
3.154 + if ( i < 0 ) {
3.155 + int s=container.size();
3.156 + iimap.set( item, s );
3.157 + store st;
3.158 + st.name=item;
3.159 + container.push_back(st);
3.160 + i=s;
3.161 + } else {
3.162 + container[i].parent=container[i].child=-1;
3.163 + container[i].degree=0;
3.164 + container[i].in=true;
3.165 + container[i].marked=false;
3.166 + }
3.167 +
3.168 + if ( num_items ) {
3.169 + container[container[minimum].right_neighbor].left_neighbor=i;
3.170 + container[i].right_neighbor=container[minimum].right_neighbor;
3.171 + container[minimum].right_neighbor=i;
3.172 + container[i].left_neighbor=minimum;
3.173 + if ( comp( value, container[minimum].prio) ) minimum=i;
3.174 + } else {
3.175 + container[i].right_neighbor=container[i].left_neighbor=i;
3.176 + minimum=i;
3.177 + }
3.178 + container[i].prio=value;
3.179 + ++num_items;
3.180 + }
3.181 +
3.182 + /// \brief Returns the item with minimum priority relative to \c Compare.
3.183 + ///
3.184 + /// This method returns the item with minimum priority relative to \c
3.185 + /// Compare.
3.186 + /// \pre The heap must be nonempty.
3.187 + Item top() const { return container[minimum].name; }
3.188 +
3.189 + /// \brief Returns the minimum priority relative to \c Compare.
3.190 + ///
3.191 + /// It returns the minimum priority relative to \c Compare.
3.192 + /// \pre The heap must be nonempty.
3.193 + const Prio& prio() const { return container[minimum].prio; }
3.194 +
3.195 + /// \brief Returns the priority of \c item.
3.196 + ///
3.197 + /// It returns the priority of \c item.
3.198 + /// \pre \c item must be in the heap.
3.199 + const Prio& operator[](const Item& item) const {
3.200 + return container[iimap[item]].prio;
3.201 + }
3.202 +
3.203 + /// \brief Deletes the item with minimum priority relative to \c Compare.
3.204 + ///
3.205 + /// This method deletes the item with minimum priority relative to \c
3.206 + /// Compare from the heap.
3.207 + /// \pre The heap must be non-empty.
3.208 + void pop() {
3.209 + /*The first case is that there are only one root.*/
3.210 + if ( container[minimum].left_neighbor==minimum ) {
3.211 + container[minimum].in=false;
3.212 + if ( container[minimum].degree!=0 ) {
3.213 + makeroot(container[minimum].child);
3.214 + minimum=container[minimum].child;
3.215 + balance();
3.216 + }
3.217 + } else {
3.218 + int right=container[minimum].right_neighbor;
3.219 + unlace(minimum);
3.220 + container[minimum].in=false;
3.221 + if ( container[minimum].degree > 0 ) {
3.222 + int left=container[minimum].left_neighbor;
3.223 + int child=container[minimum].child;
3.224 + int last_child=container[child].left_neighbor;
3.225 +
3.226 + makeroot(child);
3.227 +
3.228 + container[left].right_neighbor=child;
3.229 + container[child].left_neighbor=left;
3.230 + container[right].left_neighbor=last_child;
3.231 + container[last_child].right_neighbor=right;
3.232 + }
3.233 + minimum=right;
3.234 + balance();
3.235 + } // the case where there are more roots
3.236 + --num_items;
3.237 + }
3.238 +
3.239 + /// \brief Deletes \c item from the heap.
3.240 + ///
3.241 + /// This method deletes \c item from the heap, if \c item was already
3.242 + /// stored in the heap. It is quite inefficient in Fibonacci heaps.
3.243 + void erase (const Item& item) {
3.244 + int i=iimap[item];
3.245 +
3.246 + if ( i >= 0 && container[i].in ) {
3.247 + if ( container[i].parent!=-1 ) {
3.248 + int p=container[i].parent;
3.249 + cut(i,p);
3.250 + cascade(p);
3.251 + }
3.252 + minimum=i; //As if its prio would be -infinity
3.253 + pop();
3.254 + }
3.255 + }
3.256 +
3.257 + /// \brief Decreases the priority of \c item to \c value.
3.258 + ///
3.259 + /// This method decreases the priority of \c item to \c value.
3.260 + /// \pre \c item must be stored in the heap with priority at least \c
3.261 + /// value relative to \c Compare.
3.262 + void decrease (Item item, const Prio& value) {
3.263 + int i=iimap[item];
3.264 + container[i].prio=value;
3.265 + int p=container[i].parent;
3.266 +
3.267 + if ( p!=-1 && comp(value, container[p].prio) ) {
3.268 + cut(i,p);
3.269 + cascade(p);
3.270 + }
3.271 + if ( comp(value, container[minimum].prio) ) minimum=i;
3.272 + }
3.273 +
3.274 + /// \brief Increases the priority of \c item to \c value.
3.275 + ///
3.276 + /// This method sets the priority of \c item to \c value. Though
3.277 + /// there is no precondition on the priority of \c item, this
3.278 + /// method should be used only if it is indeed necessary to increase
3.279 + /// (relative to \c Compare) the priority of \c item, because this
3.280 + /// method is inefficient.
3.281 + void increase (Item item, const Prio& value) {
3.282 + erase(item);
3.283 + push(item, value);
3.284 + }
3.285 +
3.286 +
3.287 + /// \brief Returns if \c item is in, has already been in, or has never
3.288 + /// been in the heap.
3.289 + ///
3.290 + /// This method returns PRE_HEAP if \c item has never been in the
3.291 + /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
3.292 + /// otherwise. In the latter case it is possible that \c item will
3.293 + /// get back to the heap again.
3.294 + State state(const Item &item) const {
3.295 + int i=iimap[item];
3.296 + if( i>=0 ) {
3.297 + if ( container[i].in ) i=0;
3.298 + else i=-2;
3.299 + }
3.300 + return State(i);
3.301 + }
3.302 +
3.303 + /// \brief Sets the state of the \c item in the heap.
3.304 + ///
3.305 + /// Sets the state of the \c item in the heap. It can be used to
3.306 + /// manually clear the heap when it is important to achive the
3.307 + /// better time complexity.
3.308 + /// \param i The item.
3.309 + /// \param st The state. It should not be \c IN_HEAP.
3.310 + void state(const Item& i, State st) {
3.311 + switch (st) {
3.312 + case POST_HEAP:
3.313 + case PRE_HEAP:
3.314 + if (state(i) == IN_HEAP) {
3.315 + erase(i);
3.316 + }
3.317 + iimap[i] = st;
3.318 + break;
3.319 + case IN_HEAP:
3.320 + break;
3.321 + }
3.322 + }
3.323 +
3.324 + private:
3.325 +
3.326 + void balance() {
3.327 +
3.328 + int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1;
3.329 +
3.330 + std::vector<int> A(maxdeg,-1);
3.331 +
3.332 + /*
3.333 + *Recall that now minimum does not point to the minimum prio element.
3.334 + *We set minimum to this during balance().
3.335 + */
3.336 + int anchor=container[minimum].left_neighbor;
3.337 + int next=minimum;
3.338 + bool end=false;
3.339 +
3.340 + do {
3.341 + int active=next;
3.342 + if ( anchor==active ) end=true;
3.343 + int d=container[active].degree;
3.344 + next=container[active].right_neighbor;
3.345 +
3.346 + while (A[d]!=-1) {
3.347 + if( comp(container[active].prio, container[A[d]].prio) ) {
3.348 + fuse(active,A[d]);
3.349 + } else {
3.350 + fuse(A[d],active);
3.351 + active=A[d];
3.352 + }
3.353 + A[d]=-1;
3.354 + ++d;
3.355 + }
3.356 + A[d]=active;
3.357 + } while ( !end );
3.358 +
3.359 +
3.360 + while ( container[minimum].parent >=0 )
3.361 + minimum=container[minimum].parent;
3.362 + int s=minimum;
3.363 + int m=minimum;
3.364 + do {
3.365 + if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
3.366 + s=container[s].right_neighbor;
3.367 + } while ( s != m );
3.368 + }
3.369 +
3.370 + void makeroot(int c) {
3.371 + int s=c;
3.372 + do {
3.373 + container[s].parent=-1;
3.374 + s=container[s].right_neighbor;
3.375 + } while ( s != c );
3.376 + }
3.377 +
3.378 + void cut(int a, int b) {
3.379 + /*
3.380 + *Replacing a from the children of b.
3.381 + */
3.382 + --container[b].degree;
3.383 +
3.384 + if ( container[b].degree !=0 ) {
3.385 + int child=container[b].child;
3.386 + if ( child==a )
3.387 + container[b].child=container[child].right_neighbor;
3.388 + unlace(a);
3.389 + }
3.390 +
3.391 +
3.392 + /*Lacing a to the roots.*/
3.393 + int right=container[minimum].right_neighbor;
3.394 + container[minimum].right_neighbor=a;
3.395 + container[a].left_neighbor=minimum;
3.396 + container[a].right_neighbor=right;
3.397 + container[right].left_neighbor=a;
3.398 +
3.399 + container[a].parent=-1;
3.400 + container[a].marked=false;
3.401 + }
3.402 +
3.403 + void cascade(int a) {
3.404 + if ( container[a].parent!=-1 ) {
3.405 + int p=container[a].parent;
3.406 +
3.407 + if ( container[a].marked==false ) container[a].marked=true;
3.408 + else {
3.409 + cut(a,p);
3.410 + cascade(p);
3.411 + }
3.412 + }
3.413 + }
3.414 +
3.415 + void fuse(int a, int b) {
3.416 + unlace(b);
3.417 +
3.418 + /*Lacing b under a.*/
3.419 + container[b].parent=a;
3.420 +
3.421 + if (container[a].degree==0) {
3.422 + container[b].left_neighbor=b;
3.423 + container[b].right_neighbor=b;
3.424 + container[a].child=b;
3.425 + } else {
3.426 + int child=container[a].child;
3.427 + int last_child=container[child].left_neighbor;
3.428 + container[child].left_neighbor=b;
3.429 + container[b].right_neighbor=child;
3.430 + container[last_child].right_neighbor=b;
3.431 + container[b].left_neighbor=last_child;
3.432 + }
3.433 +
3.434 + ++container[a].degree;
3.435 +
3.436 + container[b].marked=false;
3.437 + }
3.438 +
3.439 + /*
3.440 + *It is invoked only if a has siblings.
3.441 + */
3.442 + void unlace(int a) {
3.443 + int leftn=container[a].left_neighbor;
3.444 + int rightn=container[a].right_neighbor;
3.445 + container[leftn].right_neighbor=rightn;
3.446 + container[rightn].left_neighbor=leftn;
3.447 + }
3.448 +
3.449 +
3.450 + class store {
3.451 + friend class FibHeap;
3.452 +
3.453 + Item name;
3.454 + int parent;
3.455 + int left_neighbor;
3.456 + int right_neighbor;
3.457 + int child;
3.458 + int degree;
3.459 + bool marked;
3.460 + bool in;
3.461 + Prio prio;
3.462 +
3.463 + store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
3.464 + };
3.465 + };
3.466 +
3.467 +} //namespace lemon
3.468 +
3.469 +#endif //LEMON_FIB_HEAP_H
3.470 +
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/lemon/radix_heap.h Thu Jun 11 22:11:29 2009 +0200
4.3 @@ -0,0 +1,433 @@
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_RADIX_HEAP_H
4.23 +#define LEMON_RADIX_HEAP_H
4.24 +
4.25 +///\ingroup auxdat
4.26 +///\file
4.27 +///\brief Radix Heap implementation.
4.28 +
4.29 +#include <vector>
4.30 +#include <lemon/error.h>
4.31 +
4.32 +namespace lemon {
4.33 +
4.34 +
4.35 + /// \ingroup auxdata
4.36 + ///
4.37 + /// \brief A Radix Heap implementation.
4.38 + ///
4.39 + /// This class implements the \e radix \e heap data structure. A \e heap
4.40 + /// is a data structure for storing items with specified values called \e
4.41 + /// priorities in such a way that finding the item with minimum priority is
4.42 + /// efficient. This heap type can store only items with \e int priority.
4.43 + /// In a heap one can change the priority of an item, add or erase an
4.44 + /// item, but the priority cannot be decreased under the last removed
4.45 + /// item's priority.
4.46 + ///
4.47 + /// \param _ItemIntMap A read and writable Item int map, used internally
4.48 + /// to handle the cross references.
4.49 + ///
4.50 + /// \see BinHeap
4.51 + /// \see Dijkstra
4.52 + template <typename _ItemIntMap>
4.53 + class RadixHeap {
4.54 +
4.55 + public:
4.56 + typedef typename _ItemIntMap::Key Item;
4.57 + typedef int Prio;
4.58 + typedef _ItemIntMap ItemIntMap;
4.59 +
4.60 + /// \brief Exception thrown by RadixHeap.
4.61 + ///
4.62 + /// This Exception is thrown when a smaller priority
4.63 + /// is inserted into the \e RadixHeap then the last time erased.
4.64 + /// \see RadixHeap
4.65 +
4.66 + class UnderFlowPriorityError : public Exception {
4.67 + public:
4.68 + virtual const char* what() const throw() {
4.69 + return "lemon::RadixHeap::UnderFlowPriorityError";
4.70 + }
4.71 + };
4.72 +
4.73 + /// \brief Type to represent the items states.
4.74 + ///
4.75 + /// Each Item element have a state associated to it. It may be "in heap",
4.76 + /// "pre heap" or "post heap". The latter two are indifferent from the
4.77 + /// heap's point of view, but may be useful to the user.
4.78 + ///
4.79 + /// The ItemIntMap \e should be initialized in such way that it maps
4.80 + /// PRE_HEAP (-1) to any element to be put in the heap...
4.81 + enum State {
4.82 + IN_HEAP = 0,
4.83 + PRE_HEAP = -1,
4.84 + POST_HEAP = -2
4.85 + };
4.86 +
4.87 + private:
4.88 +
4.89 + struct RadixItem {
4.90 + int prev, next, box;
4.91 + Item item;
4.92 + int prio;
4.93 + RadixItem(Item _item, int _prio) : item(_item), prio(_prio) {}
4.94 + };
4.95 +
4.96 + struct RadixBox {
4.97 + int first;
4.98 + int min, size;
4.99 + RadixBox(int _min, int _size) : first(-1), min(_min), size(_size) {}
4.100 + };
4.101 +
4.102 + std::vector<RadixItem> data;
4.103 + std::vector<RadixBox> boxes;
4.104 +
4.105 + ItemIntMap &iim;
4.106 +
4.107 +
4.108 + public:
4.109 + /// \brief The constructor.
4.110 + ///
4.111 + /// The constructor.
4.112 + ///
4.113 + /// \param _iim It 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 + ///
4.117 + /// \param minimal The initial minimal value of the heap.
4.118 + /// \param capacity It determines the initial capacity of the heap.
4.119 + RadixHeap(ItemIntMap &_iim, int minimal = 0, int capacity = 0)
4.120 + : iim(_iim) {
4.121 + boxes.push_back(RadixBox(minimal, 1));
4.122 + boxes.push_back(RadixBox(minimal + 1, 1));
4.123 + while (lower(boxes.size() - 1, capacity + minimal - 1)) {
4.124 + extend();
4.125 + }
4.126 + }
4.127 +
4.128 + /// The number of items stored in the heap.
4.129 + ///
4.130 + /// \brief Returns the number of items stored in the heap.
4.131 + int size() const { return data.size(); }
4.132 + /// \brief Checks if the heap stores no items.
4.133 + ///
4.134 + /// Returns \c true if and only if the heap stores no items.
4.135 + bool empty() const { return data.empty(); }
4.136 +
4.137 + /// \brief Make empty this heap.
4.138 + ///
4.139 + /// Make empty this heap. It does not change the cross reference
4.140 + /// map. If you want to reuse a heap what is not surely empty you
4.141 + /// should first clear the heap and after that you should set the
4.142 + /// cross reference map for each item to \c PRE_HEAP.
4.143 + void clear(int minimal = 0, int capacity = 0) {
4.144 + data.clear(); boxes.clear();
4.145 + boxes.push_back(RadixBox(minimal, 1));
4.146 + boxes.push_back(RadixBox(minimal + 1, 1));
4.147 + while (lower(boxes.size() - 1, capacity + minimal - 1)) {
4.148 + extend();
4.149 + }
4.150 + }
4.151 +
4.152 + private:
4.153 +
4.154 + bool upper(int box, Prio pr) {
4.155 + return pr < boxes[box].min;
4.156 + }
4.157 +
4.158 + bool lower(int box, Prio pr) {
4.159 + return pr >= boxes[box].min + boxes[box].size;
4.160 + }
4.161 +
4.162 + /// \brief Remove item from the box list.
4.163 + void remove(int index) {
4.164 + if (data[index].prev >= 0) {
4.165 + data[data[index].prev].next = data[index].next;
4.166 + } else {
4.167 + boxes[data[index].box].first = data[index].next;
4.168 + }
4.169 + if (data[index].next >= 0) {
4.170 + data[data[index].next].prev = data[index].prev;
4.171 + }
4.172 + }
4.173 +
4.174 + /// \brief Insert item into the box list.
4.175 + void insert(int box, int index) {
4.176 + if (boxes[box].first == -1) {
4.177 + boxes[box].first = index;
4.178 + data[index].next = data[index].prev = -1;
4.179 + } else {
4.180 + data[index].next = boxes[box].first;
4.181 + data[boxes[box].first].prev = index;
4.182 + data[index].prev = -1;
4.183 + boxes[box].first = index;
4.184 + }
4.185 + data[index].box = box;
4.186 + }
4.187 +
4.188 + /// \brief Add a new box to the box list.
4.189 + void extend() {
4.190 + int min = boxes.back().min + boxes.back().size;
4.191 + int bs = 2 * boxes.back().size;
4.192 + boxes.push_back(RadixBox(min, bs));
4.193 + }
4.194 +
4.195 + /// \brief Move an item up into the proper box.
4.196 + void bubble_up(int index) {
4.197 + if (!lower(data[index].box, data[index].prio)) return;
4.198 + remove(index);
4.199 + int box = findUp(data[index].box, data[index].prio);
4.200 + insert(box, index);
4.201 + }
4.202 +
4.203 + /// \brief Find up the proper box for the item with the given prio.
4.204 + int findUp(int start, int pr) {
4.205 + while (lower(start, pr)) {
4.206 + if (++start == int(boxes.size())) {
4.207 + extend();
4.208 + }
4.209 + }
4.210 + return start;
4.211 + }
4.212 +
4.213 + /// \brief Move an item down into the proper box.
4.214 + void bubble_down(int index) {
4.215 + if (!upper(data[index].box, data[index].prio)) return;
4.216 + remove(index);
4.217 + int box = findDown(data[index].box, data[index].prio);
4.218 + insert(box, index);
4.219 + }
4.220 +
4.221 + /// \brief Find up the proper box for the item with the given prio.
4.222 + int findDown(int start, int pr) {
4.223 + while (upper(start, pr)) {
4.224 + if (--start < 0) throw UnderFlowPriorityError();
4.225 + }
4.226 + return start;
4.227 + }
4.228 +
4.229 + /// \brief Find the first not empty box.
4.230 + int findFirst() {
4.231 + int first = 0;
4.232 + while (boxes[first].first == -1) ++first;
4.233 + return first;
4.234 + }
4.235 +
4.236 + /// \brief Gives back the minimal prio of the box.
4.237 + int minValue(int box) {
4.238 + int min = data[boxes[box].first].prio;
4.239 + for (int k = boxes[box].first; k != -1; k = data[k].next) {
4.240 + if (data[k].prio < min) min = data[k].prio;
4.241 + }
4.242 + return min;
4.243 + }
4.244 +
4.245 + /// \brief Rearrange the items of the heap and makes the
4.246 + /// first box not empty.
4.247 + void moveDown() {
4.248 + int box = findFirst();
4.249 + if (box == 0) return;
4.250 + int min = minValue(box);
4.251 + for (int i = 0; i <= box; ++i) {
4.252 + boxes[i].min = min;
4.253 + min += boxes[i].size;
4.254 + }
4.255 + int curr = boxes[box].first, next;
4.256 + while (curr != -1) {
4.257 + next = data[curr].next;
4.258 + bubble_down(curr);
4.259 + curr = next;
4.260 + }
4.261 + }
4.262 +
4.263 + void relocate_last(int index) {
4.264 + if (index != int(data.size()) - 1) {
4.265 + data[index] = data.back();
4.266 + if (data[index].prev != -1) {
4.267 + data[data[index].prev].next = index;
4.268 + } else {
4.269 + boxes[data[index].box].first = index;
4.270 + }
4.271 + if (data[index].next != -1) {
4.272 + data[data[index].next].prev = index;
4.273 + }
4.274 + iim[data[index].item] = index;
4.275 + }
4.276 + data.pop_back();
4.277 + }
4.278 +
4.279 + public:
4.280 +
4.281 + /// \brief Insert an item into the heap with the given priority.
4.282 + ///
4.283 + /// Adds \c i to the heap with priority \c p.
4.284 + /// \param i The item to insert.
4.285 + /// \param p The priority of the item.
4.286 + void push(const Item &i, const Prio &p) {
4.287 + int n = data.size();
4.288 + iim.set(i, n);
4.289 + data.push_back(RadixItem(i, p));
4.290 + while (lower(boxes.size() - 1, p)) {
4.291 + extend();
4.292 + }
4.293 + int box = findDown(boxes.size() - 1, p);
4.294 + insert(box, n);
4.295 + }
4.296 +
4.297 + /// \brief Returns the item with minimum priority.
4.298 + ///
4.299 + /// This method returns the item with minimum priority.
4.300 + /// \pre The heap must be nonempty.
4.301 + Item top() const {
4.302 + const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
4.303 + return data[boxes[0].first].item;
4.304 + }
4.305 +
4.306 + /// \brief Returns the minimum priority.
4.307 + ///
4.308 + /// It returns the minimum priority.
4.309 + /// \pre The heap must be nonempty.
4.310 + Prio prio() const {
4.311 + const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
4.312 + return data[boxes[0].first].prio;
4.313 + }
4.314 +
4.315 + /// \brief Deletes the item with minimum priority.
4.316 + ///
4.317 + /// This method deletes the item with minimum priority.
4.318 + /// \pre The heap must be non-empty.
4.319 + void pop() {
4.320 + moveDown();
4.321 + int index = boxes[0].first;
4.322 + iim[data[index].item] = POST_HEAP;
4.323 + remove(index);
4.324 + relocate_last(index);
4.325 + }
4.326 +
4.327 + /// \brief Deletes \c i from the heap.
4.328 + ///
4.329 + /// This method deletes item \c i from the heap, if \c i was
4.330 + /// already stored in the heap.
4.331 + /// \param i The item to erase.
4.332 + void erase(const Item &i) {
4.333 + int index = iim[i];
4.334 + iim[i] = POST_HEAP;
4.335 + remove(index);
4.336 + relocate_last(index);
4.337 + }
4.338 +
4.339 + /// \brief Returns the priority of \c i.
4.340 + ///
4.341 + /// This function returns the priority of item \c i.
4.342 + /// \pre \c i must be in the heap.
4.343 + /// \param i The item.
4.344 + Prio operator[](const Item &i) const {
4.345 + int idx = iim[i];
4.346 + return data[idx].prio;
4.347 + }
4.348 +
4.349 + /// \brief \c i gets to the heap with priority \c p independently
4.350 + /// if \c i was already there.
4.351 + ///
4.352 + /// This method calls \ref push(\c i, \c p) if \c i is not stored
4.353 + /// in the heap and sets the priority of \c i to \c p otherwise.
4.354 + /// It may throw an \e UnderFlowPriorityException.
4.355 + /// \param i The item.
4.356 + /// \param p The priority.
4.357 + void set(const Item &i, const Prio &p) {
4.358 + int idx = iim[i];
4.359 + if( idx < 0 ) {
4.360 + push(i, p);
4.361 + }
4.362 + else if( p >= data[idx].prio ) {
4.363 + data[idx].prio = p;
4.364 + bubble_up(idx);
4.365 + } else {
4.366 + data[idx].prio = p;
4.367 + bubble_down(idx);
4.368 + }
4.369 + }
4.370 +
4.371 +
4.372 + /// \brief Decreases the priority of \c i to \c p.
4.373 + ///
4.374 + /// This method decreases the priority of item \c i to \c p.
4.375 + /// \pre \c i must be stored in the heap with priority at least \c p, and
4.376 + /// \c should be greater or equal to the last removed item's priority.
4.377 + /// \param i The item.
4.378 + /// \param p The priority.
4.379 + void decrease(const Item &i, const Prio &p) {
4.380 + int idx = iim[i];
4.381 + data[idx].prio = p;
4.382 + bubble_down(idx);
4.383 + }
4.384 +
4.385 + /// \brief Increases the priority of \c i to \c p.
4.386 + ///
4.387 + /// This method sets the priority of item \c i to \c p.
4.388 + /// \pre \c i must be stored in the heap with priority at most \c p
4.389 + /// \param i The item.
4.390 + /// \param p The priority.
4.391 + void increase(const Item &i, const Prio &p) {
4.392 + int idx = iim[i];
4.393 + data[idx].prio = p;
4.394 + bubble_up(idx);
4.395 + }
4.396 +
4.397 + /// \brief Returns if \c item is in, has already been in, or has
4.398 + /// never been in the heap.
4.399 + ///
4.400 + /// This method returns PRE_HEAP if \c item has never been in the
4.401 + /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
4.402 + /// otherwise. In the latter case it is possible that \c item will
4.403 + /// get back to the heap again.
4.404 + /// \param i The item.
4.405 + State state(const Item &i) const {
4.406 + int s = iim[i];
4.407 + if( s >= 0 ) s = 0;
4.408 + return State(s);
4.409 + }
4.410 +
4.411 + /// \brief Sets the state of the \c item in the heap.
4.412 + ///
4.413 + /// Sets the state of the \c item in the heap. It can be used to
4.414 + /// manually clear the heap when it is important to achive the
4.415 + /// better time complexity.
4.416 + /// \param i The item.
4.417 + /// \param st The state. It should not be \c IN_HEAP.
4.418 + void state(const Item& i, State st) {
4.419 + switch (st) {
4.420 + case POST_HEAP:
4.421 + case PRE_HEAP:
4.422 + if (state(i) == IN_HEAP) {
4.423 + erase(i);
4.424 + }
4.425 + iim[i] = st;
4.426 + break;
4.427 + case IN_HEAP:
4.428 + break;
4.429 + }
4.430 + }
4.431 +
4.432 + }; // class RadixHeap
4.433 +
4.434 +} // namespace lemon
4.435 +
4.436 +#endif // LEMON_RADIX_HEAP_H
5.1 --- a/test/heap_test.cc Fri May 29 17:46:48 2009 +0100
5.2 +++ b/test/heap_test.cc Thu Jun 11 22:11:29 2009 +0200
5.3 @@ -31,6 +31,9 @@
5.4 #include <lemon/maps.h>
5.5
5.6 #include <lemon/bin_heap.h>
5.7 +#include <lemon/fib_heap.h>
5.8 +#include <lemon/radix_heap.h>
5.9 +#include <lemon/bucket_heap.h>
5.10
5.11 #include "test_tools.h"
5.12
5.13 @@ -183,5 +186,39 @@
5.14 dijkstraHeapTest<NodeHeap>(digraph, length, source);
5.15 }
5.16
5.17 + {
5.18 + typedef FibHeap<Prio, ItemIntMap> IntHeap;
5.19 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
5.20 + heapSortTest<IntHeap>();
5.21 + heapIncreaseTest<IntHeap>();
5.22 +
5.23 + typedef FibHeap<Prio, IntNodeMap > NodeHeap;
5.24 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
5.25 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
5.26 + }
5.27 +
5.28 + {
5.29 + typedef RadixHeap<ItemIntMap> IntHeap;
5.30 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
5.31 + heapSortTest<IntHeap>();
5.32 + heapIncreaseTest<IntHeap>();
5.33 +
5.34 + typedef RadixHeap<IntNodeMap > NodeHeap;
5.35 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
5.36 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
5.37 + }
5.38 +
5.39 + {
5.40 + typedef BucketHeap<ItemIntMap> IntHeap;
5.41 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
5.42 + heapSortTest<IntHeap>();
5.43 + heapIncreaseTest<IntHeap>();
5.44 +
5.45 + typedef BucketHeap<IntNodeMap > NodeHeap;
5.46 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
5.47 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
5.48 + }
5.49 +
5.50 +
5.51 return 0;
5.52 }