1.1 --- a/lemon/Makefile.am Mon Aug 31 08:32:25 2009 +0200
1.2 +++ b/lemon/Makefile.am Mon Aug 31 10:03:23 2009 +0200
1.3 @@ -60,6 +60,7 @@
1.4 lemon/bellman_ford.h \
1.5 lemon/bfs.h \
1.6 lemon/bin_heap.h \
1.7 + lemon/binom_heap.h \
1.8 lemon/bucket_heap.h \
1.9 lemon/cbc.h \
1.10 lemon/circulation.h \
1.11 @@ -79,12 +80,14 @@
1.12 lemon/error.h \
1.13 lemon/euler.h \
1.14 lemon/fib_heap.h \
1.15 + lemon/fourary_heap.h \
1.16 lemon/full_graph.h \
1.17 lemon/glpk.h \
1.18 lemon/gomory_hu.h \
1.19 lemon/graph_to_eps.h \
1.20 lemon/grid_graph.h \
1.21 lemon/hypercube_graph.h \
1.22 + lemon/kary_heap.h \
1.23 lemon/kruskal.h \
1.24 lemon/hao_orlin.h \
1.25 lemon/lgf_reader.h \
1.26 @@ -99,6 +102,7 @@
1.27 lemon/min_cost_arborescence.h \
1.28 lemon/nauty_reader.h \
1.29 lemon/network_simplex.h \
1.30 + lemon/pairing_heap.h \
1.31 lemon/path.h \
1.32 lemon/preflow.h \
1.33 lemon/radix_heap.h \
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/binom_heap.h Mon Aug 31 10:03:23 2009 +0200
2.3 @@ -0,0 +1,445 @@
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_BINOM_HEAP_H
2.23 +#define LEMON_BINOM_HEAP_H
2.24 +
2.25 +///\file
2.26 +///\ingroup heaps
2.27 +///\brief Binomial Heap implementation.
2.28 +
2.29 +#include <vector>
2.30 +#include <utility>
2.31 +#include <functional>
2.32 +#include <lemon/math.h>
2.33 +#include <lemon/counter.h>
2.34 +
2.35 +namespace lemon {
2.36 +
2.37 + /// \ingroup heaps
2.38 + ///
2.39 + ///\brief Binomial heap data structure.
2.40 + ///
2.41 + /// This class implements the \e binomial \e heap data structure.
2.42 + /// It fully conforms to the \ref concepts::Heap "heap concept".
2.43 + ///
2.44 + /// The methods \ref increase() and \ref erase() are not efficient
2.45 + /// in a binomial heap. In case of many calls of these operations,
2.46 + /// it is better to use other heap structure, e.g. \ref BinHeap
2.47 + /// "binary heap".
2.48 + ///
2.49 + /// \tparam PR Type of the priorities of the items.
2.50 + /// \tparam IM A read-writable item map with \c int values, used
2.51 + /// internally to handle the cross references.
2.52 + /// \tparam CMP A functor class for comparing the priorities.
2.53 + /// The default is \c std::less<PR>.
2.54 +#ifdef DOXYGEN
2.55 + template <typename PR, typename IM, typename CMP>
2.56 +#else
2.57 + template <typename PR, typename IM, typename CMP = std::less<PR> >
2.58 +#endif
2.59 + class BinomHeap {
2.60 + public:
2.61 + /// Type of the item-int map.
2.62 + typedef IM ItemIntMap;
2.63 + /// Type of the priorities.
2.64 + typedef PR Prio;
2.65 + /// Type of the items stored in the heap.
2.66 + typedef typename ItemIntMap::Key Item;
2.67 + /// Functor type for comparing the priorities.
2.68 + typedef CMP Compare;
2.69 +
2.70 + /// \brief Type to represent the states of the items.
2.71 + ///
2.72 + /// Each item has a state associated to it. It can be "in heap",
2.73 + /// "pre-heap" or "post-heap". The latter two are indifferent from the
2.74 + /// heap's point of view, but may be useful to the user.
2.75 + ///
2.76 + /// The item-int map must be initialized in such way that it assigns
2.77 + /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
2.78 + enum State {
2.79 + IN_HEAP = 0, ///< = 0.
2.80 + PRE_HEAP = -1, ///< = -1.
2.81 + POST_HEAP = -2 ///< = -2.
2.82 + };
2.83 +
2.84 + private:
2.85 + class Store;
2.86 +
2.87 + std::vector<Store> _data;
2.88 + int _min, _head;
2.89 + ItemIntMap &_iim;
2.90 + Compare _comp;
2.91 + int _num_items;
2.92 +
2.93 + public:
2.94 + /// \brief Constructor.
2.95 + ///
2.96 + /// Constructor.
2.97 + /// \param map A map that assigns \c int values to the items.
2.98 + /// It is used internally to handle the cross references.
2.99 + /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
2.100 + explicit BinomHeap(ItemIntMap &map)
2.101 + : _min(0), _head(-1), _iim(map), _num_items(0) {}
2.102 +
2.103 + /// \brief Constructor.
2.104 + ///
2.105 + /// Constructor.
2.106 + /// \param map A map that assigns \c int values to the items.
2.107 + /// It is used internally to handle the cross references.
2.108 + /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
2.109 + /// \param comp The function object used for comparing the priorities.
2.110 + BinomHeap(ItemIntMap &map, const Compare &comp)
2.111 + : _min(0), _head(-1), _iim(map), _comp(comp), _num_items(0) {}
2.112 +
2.113 + /// \brief The number of items stored in the heap.
2.114 + ///
2.115 + /// This function returns the number of items stored in the heap.
2.116 + int size() const { return _num_items; }
2.117 +
2.118 + /// \brief Check if the heap is empty.
2.119 + ///
2.120 + /// This function returns \c true if the heap is empty.
2.121 + bool empty() const { return _num_items==0; }
2.122 +
2.123 + /// \brief Make the heap empty.
2.124 + ///
2.125 + /// This functon makes the heap empty.
2.126 + /// It does not change the cross reference map. If you want to reuse
2.127 + /// a heap that is not surely empty, you should first clear it and
2.128 + /// then you should set the cross reference map to \c PRE_HEAP
2.129 + /// for each item.
2.130 + void clear() {
2.131 + _data.clear(); _min=0; _num_items=0; _head=-1;
2.132 + }
2.133 +
2.134 + /// \brief Set the priority of an item or insert it, if it is
2.135 + /// not stored in the heap.
2.136 + ///
2.137 + /// This method sets the priority of the given item if it is
2.138 + /// already stored in the heap. Otherwise it inserts the given
2.139 + /// item into the heap with the given priority.
2.140 + /// \param item The item.
2.141 + /// \param value The priority.
2.142 + void set (const Item& item, const Prio& value) {
2.143 + int i=_iim[item];
2.144 + if ( i >= 0 && _data[i].in ) {
2.145 + if ( _comp(value, _data[i].prio) ) decrease(item, value);
2.146 + if ( _comp(_data[i].prio, value) ) increase(item, value);
2.147 + } else push(item, value);
2.148 + }
2.149 +
2.150 + /// \brief Insert an item into the heap with the given priority.
2.151 + ///
2.152 + /// This function inserts the given item into the heap with the
2.153 + /// given priority.
2.154 + /// \param item The item to insert.
2.155 + /// \param value The priority of the item.
2.156 + /// \pre \e item must not be stored in the heap.
2.157 + void push (const Item& item, const Prio& value) {
2.158 + int i=_iim[item];
2.159 + if ( i<0 ) {
2.160 + int s=_data.size();
2.161 + _iim.set( item,s );
2.162 + Store st;
2.163 + st.name=item;
2.164 + st.prio=value;
2.165 + _data.push_back(st);
2.166 + i=s;
2.167 + }
2.168 + else {
2.169 + _data[i].parent=_data[i].right_neighbor=_data[i].child=-1;
2.170 + _data[i].degree=0;
2.171 + _data[i].in=true;
2.172 + _data[i].prio=value;
2.173 + }
2.174 +
2.175 + if( 0==_num_items ) {
2.176 + _head=i;
2.177 + _min=i;
2.178 + } else {
2.179 + merge(i);
2.180 + if( _comp(_data[i].prio, _data[_min].prio) ) _min=i;
2.181 + }
2.182 + ++_num_items;
2.183 + }
2.184 +
2.185 + /// \brief Return the item having minimum priority.
2.186 + ///
2.187 + /// This function returns the item having minimum priority.
2.188 + /// \pre The heap must be non-empty.
2.189 + Item top() const { return _data[_min].name; }
2.190 +
2.191 + /// \brief The minimum priority.
2.192 + ///
2.193 + /// This function returns the minimum priority.
2.194 + /// \pre The heap must be non-empty.
2.195 + Prio prio() const { return _data[_min].prio; }
2.196 +
2.197 + /// \brief The priority of the given item.
2.198 + ///
2.199 + /// This function returns the priority of the given item.
2.200 + /// \param item The item.
2.201 + /// \pre \e item must be in the heap.
2.202 + const Prio& operator[](const Item& item) const {
2.203 + return _data[_iim[item]].prio;
2.204 + }
2.205 +
2.206 + /// \brief Remove the item having minimum priority.
2.207 + ///
2.208 + /// This function removes the item having minimum priority.
2.209 + /// \pre The heap must be non-empty.
2.210 + void pop() {
2.211 + _data[_min].in=false;
2.212 +
2.213 + int head_child=-1;
2.214 + if ( _data[_min].child!=-1 ) {
2.215 + int child=_data[_min].child;
2.216 + int neighb;
2.217 + while( child!=-1 ) {
2.218 + neighb=_data[child].right_neighbor;
2.219 + _data[child].parent=-1;
2.220 + _data[child].right_neighbor=head_child;
2.221 + head_child=child;
2.222 + child=neighb;
2.223 + }
2.224 + }
2.225 +
2.226 + if ( _data[_head].right_neighbor==-1 ) {
2.227 + // there was only one root
2.228 + _head=head_child;
2.229 + }
2.230 + else {
2.231 + // there were more roots
2.232 + if( _head!=_min ) { unlace(_min); }
2.233 + else { _head=_data[_head].right_neighbor; }
2.234 + merge(head_child);
2.235 + }
2.236 + _min=findMin();
2.237 + --_num_items;
2.238 + }
2.239 +
2.240 + /// \brief Remove the given item from the heap.
2.241 + ///
2.242 + /// This function removes the given item from the heap if it is
2.243 + /// already stored.
2.244 + /// \param item The item to delete.
2.245 + /// \pre \e item must be in the heap.
2.246 + void erase (const Item& item) {
2.247 + int i=_iim[item];
2.248 + if ( i >= 0 && _data[i].in ) {
2.249 + decrease( item, _data[_min].prio-1 );
2.250 + pop();
2.251 + }
2.252 + }
2.253 +
2.254 + /// \brief Decrease the priority of an item to the given value.
2.255 + ///
2.256 + /// This function decreases the priority of an item to the given value.
2.257 + /// \param item The item.
2.258 + /// \param value The priority.
2.259 + /// \pre \e item must be stored in the heap with priority at least \e value.
2.260 + void decrease (Item item, const Prio& value) {
2.261 + int i=_iim[item];
2.262 + int p=_data[i].parent;
2.263 + _data[i].prio=value;
2.264 +
2.265 + while( p!=-1 && _comp(value, _data[p].prio) ) {
2.266 + _data[i].name=_data[p].name;
2.267 + _data[i].prio=_data[p].prio;
2.268 + _data[p].name=item;
2.269 + _data[p].prio=value;
2.270 + _iim[_data[i].name]=i;
2.271 + i=p;
2.272 + p=_data[p].parent;
2.273 + }
2.274 + _iim[item]=i;
2.275 + if ( _comp(value, _data[_min].prio) ) _min=i;
2.276 + }
2.277 +
2.278 + /// \brief Increase the priority of an item to the given value.
2.279 + ///
2.280 + /// This function increases the priority of an item to the given value.
2.281 + /// \param item The item.
2.282 + /// \param value The priority.
2.283 + /// \pre \e item must be stored in the heap with priority at most \e value.
2.284 + void increase (Item item, const Prio& value) {
2.285 + erase(item);
2.286 + push(item, value);
2.287 + }
2.288 +
2.289 + /// \brief Return the state of an item.
2.290 + ///
2.291 + /// This method returns \c PRE_HEAP if the given item has never
2.292 + /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
2.293 + /// and \c POST_HEAP otherwise.
2.294 + /// In the latter case it is possible that the item will get back
2.295 + /// to the heap again.
2.296 + /// \param item The item.
2.297 + State state(const Item &item) const {
2.298 + int i=_iim[item];
2.299 + if( i>=0 ) {
2.300 + if ( _data[i].in ) i=0;
2.301 + else i=-2;
2.302 + }
2.303 + return State(i);
2.304 + }
2.305 +
2.306 + /// \brief Set the state of an item in the heap.
2.307 + ///
2.308 + /// This function sets the state of the given item in the heap.
2.309 + /// It can be used to manually clear the heap when it is important
2.310 + /// to achive better time complexity.
2.311 + /// \param i The item.
2.312 + /// \param st The state. It should not be \c IN_HEAP.
2.313 + void state(const Item& i, State st) {
2.314 + switch (st) {
2.315 + case POST_HEAP:
2.316 + case PRE_HEAP:
2.317 + if (state(i) == IN_HEAP) {
2.318 + erase(i);
2.319 + }
2.320 + _iim[i] = st;
2.321 + break;
2.322 + case IN_HEAP:
2.323 + break;
2.324 + }
2.325 + }
2.326 +
2.327 + private:
2.328 +
2.329 + // Find the minimum of the roots
2.330 + int findMin() {
2.331 + if( _head!=-1 ) {
2.332 + int min_loc=_head, min_val=_data[_head].prio;
2.333 + for( int x=_data[_head].right_neighbor; x!=-1;
2.334 + x=_data[x].right_neighbor ) {
2.335 + if( _comp( _data[x].prio,min_val ) ) {
2.336 + min_val=_data[x].prio;
2.337 + min_loc=x;
2.338 + }
2.339 + }
2.340 + return min_loc;
2.341 + }
2.342 + else return -1;
2.343 + }
2.344 +
2.345 + // Merge the heap with another heap starting at the given position
2.346 + void merge(int a) {
2.347 + if( _head==-1 || a==-1 ) return;
2.348 + if( _data[a].right_neighbor==-1 &&
2.349 + _data[a].degree<=_data[_head].degree ) {
2.350 + _data[a].right_neighbor=_head;
2.351 + _head=a;
2.352 + } else {
2.353 + interleave(a);
2.354 + }
2.355 + if( _data[_head].right_neighbor==-1 ) return;
2.356 +
2.357 + int x=_head;
2.358 + int x_prev=-1, x_next=_data[x].right_neighbor;
2.359 + while( x_next!=-1 ) {
2.360 + if( _data[x].degree!=_data[x_next].degree ||
2.361 + ( _data[x_next].right_neighbor!=-1 &&
2.362 + _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) {
2.363 + x_prev=x;
2.364 + x=x_next;
2.365 + }
2.366 + else {
2.367 + if( _comp(_data[x_next].prio,_data[x].prio) ) {
2.368 + if( x_prev==-1 ) {
2.369 + _head=x_next;
2.370 + } else {
2.371 + _data[x_prev].right_neighbor=x_next;
2.372 + }
2.373 + fuse(x,x_next);
2.374 + x=x_next;
2.375 + }
2.376 + else {
2.377 + _data[x].right_neighbor=_data[x_next].right_neighbor;
2.378 + fuse(x_next,x);
2.379 + }
2.380 + }
2.381 + x_next=_data[x].right_neighbor;
2.382 + }
2.383 + }
2.384 +
2.385 + // Interleave the elements of the given list into the list of the roots
2.386 + void interleave(int a) {
2.387 + int p=_head, q=a;
2.388 + int curr=_data.size();
2.389 + _data.push_back(Store());
2.390 +
2.391 + while( p!=-1 || q!=-1 ) {
2.392 + if( q==-1 || ( p!=-1 && _data[p].degree<_data[q].degree ) ) {
2.393 + _data[curr].right_neighbor=p;
2.394 + curr=p;
2.395 + p=_data[p].right_neighbor;
2.396 + }
2.397 + else {
2.398 + _data[curr].right_neighbor=q;
2.399 + curr=q;
2.400 + q=_data[q].right_neighbor;
2.401 + }
2.402 + }
2.403 +
2.404 + _head=_data.back().right_neighbor;
2.405 + _data.pop_back();
2.406 + }
2.407 +
2.408 + // Lace node a under node b
2.409 + void fuse(int a, int b) {
2.410 + _data[a].parent=b;
2.411 + _data[a].right_neighbor=_data[b].child;
2.412 + _data[b].child=a;
2.413 +
2.414 + ++_data[b].degree;
2.415 + }
2.416 +
2.417 + // Unlace node a (if it has siblings)
2.418 + void unlace(int a) {
2.419 + int neighb=_data[a].right_neighbor;
2.420 + int other=_head;
2.421 +
2.422 + while( _data[other].right_neighbor!=a )
2.423 + other=_data[other].right_neighbor;
2.424 + _data[other].right_neighbor=neighb;
2.425 + }
2.426 +
2.427 + private:
2.428 +
2.429 + class Store {
2.430 + friend class BinomHeap;
2.431 +
2.432 + Item name;
2.433 + int parent;
2.434 + int right_neighbor;
2.435 + int child;
2.436 + int degree;
2.437 + bool in;
2.438 + Prio prio;
2.439 +
2.440 + Store() : parent(-1), right_neighbor(-1), child(-1), degree(0),
2.441 + in(true) {}
2.442 + };
2.443 + };
2.444 +
2.445 +} //namespace lemon
2.446 +
2.447 +#endif //LEMON_BINOM_HEAP_H
2.448 +
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/lemon/fourary_heap.h Mon Aug 31 10:03:23 2009 +0200
3.3 @@ -0,0 +1,342 @@
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_FOURARY_HEAP_H
3.23 +#define LEMON_FOURARY_HEAP_H
3.24 +
3.25 +///\ingroup heaps
3.26 +///\file
3.27 +///\brief Fourary heap implementation.
3.28 +
3.29 +#include <vector>
3.30 +#include <utility>
3.31 +#include <functional>
3.32 +
3.33 +namespace lemon {
3.34 +
3.35 + /// \ingroup heaps
3.36 + ///
3.37 + ///\brief Fourary heap data structure.
3.38 + ///
3.39 + /// This class implements the \e fourary \e heap data structure.
3.40 + /// It fully conforms to the \ref concepts::Heap "heap concept".
3.41 + ///
3.42 + /// The fourary heap is a specialization of the \ref KaryHeap "K-ary heap"
3.43 + /// for <tt>K=4</tt>. It is similar to the \ref BinHeap "binary heap",
3.44 + /// but its nodes have at most four children, instead of two.
3.45 + ///
3.46 + /// \tparam PR Type of the priorities of the items.
3.47 + /// \tparam IM A read-writable item map with \c int values, used
3.48 + /// internally to handle the cross references.
3.49 + /// \tparam CMP A functor class for comparing the priorities.
3.50 + /// The default is \c std::less<PR>.
3.51 + ///
3.52 + ///\sa BinHeap
3.53 + ///\sa KaryHeap
3.54 +#ifdef DOXYGEN
3.55 + template <typename PR, typename IM, typename CMP>
3.56 +#else
3.57 + template <typename PR, typename IM, typename CMP = std::less<PR> >
3.58 +#endif
3.59 + class FouraryHeap {
3.60 + public:
3.61 + /// Type of the item-int map.
3.62 + typedef IM ItemIntMap;
3.63 + /// Type of the priorities.
3.64 + typedef PR Prio;
3.65 + /// Type of the items stored in the heap.
3.66 + typedef typename ItemIntMap::Key Item;
3.67 + /// Type of the item-priority pairs.
3.68 + typedef std::pair<Item,Prio> Pair;
3.69 + /// Functor type for comparing the priorities.
3.70 + typedef CMP Compare;
3.71 +
3.72 + /// \brief Type to represent the states of the items.
3.73 + ///
3.74 + /// Each item has a state associated to it. It can be "in heap",
3.75 + /// "pre-heap" or "post-heap". The latter two are indifferent from the
3.76 + /// heap's point of view, but may be useful to the user.
3.77 + ///
3.78 + /// The item-int map must be initialized in such way that it assigns
3.79 + /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
3.80 + enum State {
3.81 + IN_HEAP = 0, ///< = 0.
3.82 + PRE_HEAP = -1, ///< = -1.
3.83 + POST_HEAP = -2 ///< = -2.
3.84 + };
3.85 +
3.86 + private:
3.87 + std::vector<Pair> _data;
3.88 + Compare _comp;
3.89 + ItemIntMap &_iim;
3.90 +
3.91 + public:
3.92 + /// \brief Constructor.
3.93 + ///
3.94 + /// Constructor.
3.95 + /// \param map A map that assigns \c int values to the items.
3.96 + /// It is used internally to handle the cross references.
3.97 + /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
3.98 + explicit FouraryHeap(ItemIntMap &map) : _iim(map) {}
3.99 +
3.100 + /// \brief Constructor.
3.101 + ///
3.102 + /// Constructor.
3.103 + /// \param map A map that assigns \c int values to the items.
3.104 + /// It is used internally to handle the cross references.
3.105 + /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
3.106 + /// \param comp The function object used for comparing the priorities.
3.107 + FouraryHeap(ItemIntMap &map, const Compare &comp)
3.108 + : _iim(map), _comp(comp) {}
3.109 +
3.110 + /// \brief The number of items stored in the heap.
3.111 + ///
3.112 + /// This function returns the number of items stored in the heap.
3.113 + int size() const { return _data.size(); }
3.114 +
3.115 + /// \brief Check if the heap is empty.
3.116 + ///
3.117 + /// This function returns \c true if the heap is empty.
3.118 + bool empty() const { return _data.empty(); }
3.119 +
3.120 + /// \brief Make the heap empty.
3.121 + ///
3.122 + /// This functon makes the heap empty.
3.123 + /// It does not change the cross reference map. If you want to reuse
3.124 + /// a heap that is not surely empty, you should first clear it and
3.125 + /// then you should set the cross reference map to \c PRE_HEAP
3.126 + /// for each item.
3.127 + void clear() { _data.clear(); }
3.128 +
3.129 + private:
3.130 + static int parent(int i) { return (i-1)/4; }
3.131 + static int firstChild(int i) { return 4*i+1; }
3.132 +
3.133 + bool less(const Pair &p1, const Pair &p2) const {
3.134 + return _comp(p1.second, p2.second);
3.135 + }
3.136 +
3.137 + void bubbleUp(int hole, Pair p) {
3.138 + int par = parent(hole);
3.139 + while( hole>0 && less(p,_data[par]) ) {
3.140 + move(_data[par],hole);
3.141 + hole = par;
3.142 + par = parent(hole);
3.143 + }
3.144 + move(p, hole);
3.145 + }
3.146 +
3.147 + void bubbleDown(int hole, Pair p, int length) {
3.148 + if( length>1 ) {
3.149 + int child = firstChild(hole);
3.150 + while( child+3<length ) {
3.151 + int min=child;
3.152 + if( less(_data[++child], _data[min]) ) min=child;
3.153 + if( less(_data[++child], _data[min]) ) min=child;
3.154 + if( less(_data[++child], _data[min]) ) min=child;
3.155 + if( !less(_data[min], p) )
3.156 + goto ok;
3.157 + move(_data[min], hole);
3.158 + hole = min;
3.159 + child = firstChild(hole);
3.160 + }
3.161 + if ( child<length ) {
3.162 + int min = child;
3.163 + if( ++child<length && less(_data[child], _data[min]) ) min=child;
3.164 + if( ++child<length && less(_data[child], _data[min]) ) min=child;
3.165 + if( less(_data[min], p) ) {
3.166 + move(_data[min], hole);
3.167 + hole = min;
3.168 + }
3.169 + }
3.170 + }
3.171 + ok:
3.172 + move(p, hole);
3.173 + }
3.174 +
3.175 + void move(const Pair &p, int i) {
3.176 + _data[i] = p;
3.177 + _iim.set(p.first, i);
3.178 + }
3.179 +
3.180 + public:
3.181 + /// \brief Insert a pair of item and priority into the heap.
3.182 + ///
3.183 + /// This function inserts \c p.first to the heap with priority
3.184 + /// \c p.second.
3.185 + /// \param p The pair to insert.
3.186 + /// \pre \c p.first must not be stored in the heap.
3.187 + void push(const Pair &p) {
3.188 + int n = _data.size();
3.189 + _data.resize(n+1);
3.190 + bubbleUp(n, p);
3.191 + }
3.192 +
3.193 + /// \brief Insert an item into the heap with the given priority.
3.194 + ///
3.195 + /// This function inserts the given item into the heap with the
3.196 + /// given priority.
3.197 + /// \param i The item to insert.
3.198 + /// \param p The priority of the item.
3.199 + /// \pre \e i must not be stored in the heap.
3.200 + void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
3.201 +
3.202 + /// \brief Return the item having minimum priority.
3.203 + ///
3.204 + /// This function returns the item having minimum priority.
3.205 + /// \pre The heap must be non-empty.
3.206 + Item top() const { return _data[0].first; }
3.207 +
3.208 + /// \brief The minimum priority.
3.209 + ///
3.210 + /// This function returns the minimum priority.
3.211 + /// \pre The heap must be non-empty.
3.212 + Prio prio() const { return _data[0].second; }
3.213 +
3.214 + /// \brief Remove the item having minimum priority.
3.215 + ///
3.216 + /// This function removes the item having minimum priority.
3.217 + /// \pre The heap must be non-empty.
3.218 + void pop() {
3.219 + int n = _data.size()-1;
3.220 + _iim.set(_data[0].first, POST_HEAP);
3.221 + if (n>0) bubbleDown(0, _data[n], n);
3.222 + _data.pop_back();
3.223 + }
3.224 +
3.225 + /// \brief Remove the given item from the heap.
3.226 + ///
3.227 + /// This function removes the given item from the heap if it is
3.228 + /// already stored.
3.229 + /// \param i The item to delete.
3.230 + /// \pre \e i must be in the heap.
3.231 + void erase(const Item &i) {
3.232 + int h = _iim[i];
3.233 + int n = _data.size()-1;
3.234 + _iim.set(_data[h].first, POST_HEAP);
3.235 + if( h<n ) {
3.236 + if( less(_data[parent(h)], _data[n]) )
3.237 + bubbleDown(h, _data[n], n);
3.238 + else
3.239 + bubbleUp(h, _data[n]);
3.240 + }
3.241 + _data.pop_back();
3.242 + }
3.243 +
3.244 + /// \brief The priority of the given item.
3.245 + ///
3.246 + /// This function returns the priority of the given item.
3.247 + /// \param i The item.
3.248 + /// \pre \e i must be in the heap.
3.249 + Prio operator[](const Item &i) const {
3.250 + int idx = _iim[i];
3.251 + return _data[idx].second;
3.252 + }
3.253 +
3.254 + /// \brief Set the priority of an item or insert it, if it is
3.255 + /// not stored in the heap.
3.256 + ///
3.257 + /// This method sets the priority of the given item if it is
3.258 + /// already stored in the heap. Otherwise it inserts the given
3.259 + /// item into the heap with the given priority.
3.260 + /// \param i The item.
3.261 + /// \param p The priority.
3.262 + void set(const Item &i, const Prio &p) {
3.263 + int idx = _iim[i];
3.264 + if( idx < 0 )
3.265 + push(i,p);
3.266 + else if( _comp(p, _data[idx].second) )
3.267 + bubbleUp(idx, Pair(i,p));
3.268 + else
3.269 + bubbleDown(idx, Pair(i,p), _data.size());
3.270 + }
3.271 +
3.272 + /// \brief Decrease the priority of an item to the given value.
3.273 + ///
3.274 + /// This function decreases the priority of an item to the given value.
3.275 + /// \param i The item.
3.276 + /// \param p The priority.
3.277 + /// \pre \e i must be stored in the heap with priority at least \e p.
3.278 + void decrease(const Item &i, const Prio &p) {
3.279 + int idx = _iim[i];
3.280 + bubbleUp(idx, Pair(i,p));
3.281 + }
3.282 +
3.283 + /// \brief Increase the priority of an item to the given value.
3.284 + ///
3.285 + /// This function increases the priority of an item to the given value.
3.286 + /// \param i The item.
3.287 + /// \param p The priority.
3.288 + /// \pre \e i must be stored in the heap with priority at most \e p.
3.289 + void increase(const Item &i, const Prio &p) {
3.290 + int idx = _iim[i];
3.291 + bubbleDown(idx, Pair(i,p), _data.size());
3.292 + }
3.293 +
3.294 + /// \brief Return the state of an item.
3.295 + ///
3.296 + /// This method returns \c PRE_HEAP if the given item has never
3.297 + /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
3.298 + /// and \c POST_HEAP otherwise.
3.299 + /// In the latter case it is possible that the item will get back
3.300 + /// to the heap again.
3.301 + /// \param i The item.
3.302 + State state(const Item &i) const {
3.303 + int s = _iim[i];
3.304 + if (s>=0) s=0;
3.305 + return State(s);
3.306 + }
3.307 +
3.308 + /// \brief Set the state of an item in the heap.
3.309 + ///
3.310 + /// This function sets the state of the given item in the heap.
3.311 + /// It can be used to manually clear the heap when it is important
3.312 + /// to achive better time complexity.
3.313 + /// \param i The item.
3.314 + /// \param st The state. It should not be \c IN_HEAP.
3.315 + void state(const Item& i, State st) {
3.316 + switch (st) {
3.317 + case POST_HEAP:
3.318 + case PRE_HEAP:
3.319 + if (state(i) == IN_HEAP) erase(i);
3.320 + _iim[i] = st;
3.321 + break;
3.322 + case IN_HEAP:
3.323 + break;
3.324 + }
3.325 + }
3.326 +
3.327 + /// \brief Replace an item in the heap.
3.328 + ///
3.329 + /// This function replaces item \c i with item \c j.
3.330 + /// Item \c i must be in the heap, while \c j must be out of the heap.
3.331 + /// After calling this method, item \c i will be out of the
3.332 + /// heap and \c j will be in the heap with the same prioriority
3.333 + /// as item \c i had before.
3.334 + void replace(const Item& i, const Item& j) {
3.335 + int idx = _iim[i];
3.336 + _iim.set(i, _iim[j]);
3.337 + _iim.set(j, idx);
3.338 + _data[idx].first = j;
3.339 + }
3.340 +
3.341 + }; // class FouraryHeap
3.342 +
3.343 +} // namespace lemon
3.344 +
3.345 +#endif // LEMON_FOURARY_HEAP_H
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/lemon/kary_heap.h Mon Aug 31 10:03:23 2009 +0200
4.3 @@ -0,0 +1,352 @@
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_KARY_HEAP_H
4.23 +#define LEMON_KARY_HEAP_H
4.24 +
4.25 +///\ingroup heaps
4.26 +///\file
4.27 +///\brief Fourary heap implementation.
4.28 +
4.29 +#include <vector>
4.30 +#include <utility>
4.31 +#include <functional>
4.32 +
4.33 +namespace lemon {
4.34 +
4.35 + /// \ingroup heaps
4.36 + ///
4.37 + ///\brief K-ary heap data structure.
4.38 + ///
4.39 + /// This class implements the \e K-ary \e heap data structure.
4.40 + /// It fully conforms to the \ref concepts::Heap "heap concept".
4.41 + ///
4.42 + /// The \ref KaryHeap "K-ary heap" is a generalization of the
4.43 + /// \ref BinHeap "binary heap" structure, its nodes have at most
4.44 + /// \c K children, instead of two.
4.45 + /// \ref BinHeap and \ref FouraryHeap are specialized implementations
4.46 + /// of this structure for <tt>K=2</tt> and <tt>K=4</tt>, respectively.
4.47 + ///
4.48 + /// \tparam PR Type of the priorities of the items.
4.49 + /// \tparam IM A read-writable item map with \c int values, used
4.50 + /// internally to handle the cross references.
4.51 + /// \tparam K The degree of the heap, each node have at most \e K
4.52 + /// children. The default is 16. Powers of two are suggested to use
4.53 + /// so that the multiplications and divisions needed to traverse the
4.54 + /// nodes of the heap could be performed faster.
4.55 + /// \tparam CMP A functor class for comparing the priorities.
4.56 + /// The default is \c std::less<PR>.
4.57 + ///
4.58 + ///\sa BinHeap
4.59 + ///\sa FouraryHeap
4.60 +#ifdef DOXYGEN
4.61 + template <typename PR, typename IM, int K, typename CMP>
4.62 +#else
4.63 + template <typename PR, typename IM, int K = 16,
4.64 + typename CMP = std::less<PR> >
4.65 +#endif
4.66 + class KaryHeap {
4.67 + public:
4.68 + /// Type of the item-int map.
4.69 + typedef IM ItemIntMap;
4.70 + /// Type of the priorities.
4.71 + typedef PR Prio;
4.72 + /// Type of the items stored in the heap.
4.73 + typedef typename ItemIntMap::Key Item;
4.74 + /// Type of the item-priority pairs.
4.75 + typedef std::pair<Item,Prio> Pair;
4.76 + /// Functor type for comparing the priorities.
4.77 + typedef CMP Compare;
4.78 +
4.79 + /// \brief Type to represent the states of the items.
4.80 + ///
4.81 + /// Each item has a state associated to it. It can be "in heap",
4.82 + /// "pre-heap" or "post-heap". The latter two are indifferent from the
4.83 + /// heap's point of view, but may be useful to the user.
4.84 + ///
4.85 + /// The item-int map must be initialized in such way that it assigns
4.86 + /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
4.87 + enum State {
4.88 + IN_HEAP = 0, ///< = 0.
4.89 + PRE_HEAP = -1, ///< = -1.
4.90 + POST_HEAP = -2 ///< = -2.
4.91 + };
4.92 +
4.93 + private:
4.94 + std::vector<Pair> _data;
4.95 + Compare _comp;
4.96 + ItemIntMap &_iim;
4.97 +
4.98 + public:
4.99 + /// \brief Constructor.
4.100 + ///
4.101 + /// Constructor.
4.102 + /// \param map A map that assigns \c int values to the items.
4.103 + /// It is used internally to handle the cross references.
4.104 + /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
4.105 + explicit KaryHeap(ItemIntMap &map) : _iim(map) {}
4.106 +
4.107 + /// \brief Constructor.
4.108 + ///
4.109 + /// Constructor.
4.110 + /// \param map A map that assigns \c int values to the items.
4.111 + /// It is used internally to handle the cross references.
4.112 + /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
4.113 + /// \param comp The function object used for comparing the priorities.
4.114 + KaryHeap(ItemIntMap &map, const Compare &comp)
4.115 + : _iim(map), _comp(comp) {}
4.116 +
4.117 + /// \brief The number of items stored in the heap.
4.118 + ///
4.119 + /// This function returns the number of items stored in the heap.
4.120 + int size() const { return _data.size(); }
4.121 +
4.122 + /// \brief Check if the heap is empty.
4.123 + ///
4.124 + /// This function returns \c true if the heap is empty.
4.125 + bool empty() const { return _data.empty(); }
4.126 +
4.127 + /// \brief Make the heap empty.
4.128 + ///
4.129 + /// This functon makes the heap empty.
4.130 + /// It does not change the cross reference map. If you want to reuse
4.131 + /// a heap that is not surely empty, you should first clear it and
4.132 + /// then you should set the cross reference map to \c PRE_HEAP
4.133 + /// for each item.
4.134 + void clear() { _data.clear(); }
4.135 +
4.136 + private:
4.137 + int parent(int i) { return (i-1)/K; }
4.138 + int firstChild(int i) { return K*i+1; }
4.139 +
4.140 + bool less(const Pair &p1, const Pair &p2) const {
4.141 + return _comp(p1.second, p2.second);
4.142 + }
4.143 +
4.144 + void bubbleUp(int hole, Pair p) {
4.145 + int par = parent(hole);
4.146 + while( hole>0 && less(p,_data[par]) ) {
4.147 + move(_data[par],hole);
4.148 + hole = par;
4.149 + par = parent(hole);
4.150 + }
4.151 + move(p, hole);
4.152 + }
4.153 +
4.154 + void bubbleDown(int hole, Pair p, int length) {
4.155 + if( length>1 ) {
4.156 + int child = firstChild(hole);
4.157 + while( child+K<=length ) {
4.158 + int min=child;
4.159 + for (int i=1; i<K; ++i) {
4.160 + if( less(_data[child+i], _data[min]) )
4.161 + min=child+i;
4.162 + }
4.163 + if( !less(_data[min], p) )
4.164 + goto ok;
4.165 + move(_data[min], hole);
4.166 + hole = min;
4.167 + child = firstChild(hole);
4.168 + }
4.169 + if ( child<length ) {
4.170 + int min = child;
4.171 + while (++child < length) {
4.172 + if( less(_data[child], _data[min]) )
4.173 + min=child;
4.174 + }
4.175 + if( less(_data[min], p) ) {
4.176 + move(_data[min], hole);
4.177 + hole = min;
4.178 + }
4.179 + }
4.180 + }
4.181 + ok:
4.182 + move(p, hole);
4.183 + }
4.184 +
4.185 + void move(const Pair &p, int i) {
4.186 + _data[i] = p;
4.187 + _iim.set(p.first, i);
4.188 + }
4.189 +
4.190 + public:
4.191 + /// \brief Insert a pair of item and priority into the heap.
4.192 + ///
4.193 + /// This function inserts \c p.first to the heap with priority
4.194 + /// \c p.second.
4.195 + /// \param p The pair to insert.
4.196 + /// \pre \c p.first must not be stored in the heap.
4.197 + void push(const Pair &p) {
4.198 + int n = _data.size();
4.199 + _data.resize(n+1);
4.200 + bubbleUp(n, p);
4.201 + }
4.202 +
4.203 + /// \brief Insert an item into the heap with the given priority.
4.204 + ///
4.205 + /// This function inserts the given item into the heap with the
4.206 + /// given priority.
4.207 + /// \param i The item to insert.
4.208 + /// \param p The priority of the item.
4.209 + /// \pre \e i must not be stored in the heap.
4.210 + void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
4.211 +
4.212 + /// \brief Return the item having minimum priority.
4.213 + ///
4.214 + /// This function returns the item having minimum priority.
4.215 + /// \pre The heap must be non-empty.
4.216 + Item top() const { return _data[0].first; }
4.217 +
4.218 + /// \brief The minimum priority.
4.219 + ///
4.220 + /// This function returns the minimum priority.
4.221 + /// \pre The heap must be non-empty.
4.222 + Prio prio() const { return _data[0].second; }
4.223 +
4.224 + /// \brief Remove the item having minimum priority.
4.225 + ///
4.226 + /// This function removes the item having minimum priority.
4.227 + /// \pre The heap must be non-empty.
4.228 + void pop() {
4.229 + int n = _data.size()-1;
4.230 + _iim.set(_data[0].first, POST_HEAP);
4.231 + if (n>0) bubbleDown(0, _data[n], n);
4.232 + _data.pop_back();
4.233 + }
4.234 +
4.235 + /// \brief Remove the given item from the heap.
4.236 + ///
4.237 + /// This function removes the given item from the heap if it is
4.238 + /// already stored.
4.239 + /// \param i The item to delete.
4.240 + /// \pre \e i must be in the heap.
4.241 + void erase(const Item &i) {
4.242 + int h = _iim[i];
4.243 + int n = _data.size()-1;
4.244 + _iim.set(_data[h].first, POST_HEAP);
4.245 + if( h<n ) {
4.246 + if( less(_data[parent(h)], _data[n]) )
4.247 + bubbleDown(h, _data[n], n);
4.248 + else
4.249 + bubbleUp(h, _data[n]);
4.250 + }
4.251 + _data.pop_back();
4.252 + }
4.253 +
4.254 + /// \brief The priority of the given item.
4.255 + ///
4.256 + /// This function returns the priority of the given item.
4.257 + /// \param i The item.
4.258 + /// \pre \e i must be in the heap.
4.259 + Prio operator[](const Item &i) const {
4.260 + int idx = _iim[i];
4.261 + return _data[idx].second;
4.262 + }
4.263 +
4.264 + /// \brief Set the priority of an item or insert it, if it is
4.265 + /// not stored in the heap.
4.266 + ///
4.267 + /// This method sets the priority of the given item if it is
4.268 + /// already stored in the heap. Otherwise it inserts the given
4.269 + /// item into the heap with the given priority.
4.270 + /// \param i The item.
4.271 + /// \param p The priority.
4.272 + void set(const Item &i, const Prio &p) {
4.273 + int idx = _iim[i];
4.274 + if( idx<0 )
4.275 + push(i,p);
4.276 + else if( _comp(p, _data[idx].second) )
4.277 + bubbleUp(idx, Pair(i,p));
4.278 + else
4.279 + bubbleDown(idx, Pair(i,p), _data.size());
4.280 + }
4.281 +
4.282 + /// \brief Decrease the priority of an item to the given value.
4.283 + ///
4.284 + /// This function decreases the priority of an item to the given value.
4.285 + /// \param i The item.
4.286 + /// \param p The priority.
4.287 + /// \pre \e i must be stored in the heap with priority at least \e p.
4.288 + void decrease(const Item &i, const Prio &p) {
4.289 + int idx = _iim[i];
4.290 + bubbleUp(idx, Pair(i,p));
4.291 + }
4.292 +
4.293 + /// \brief Increase the priority of an item to the given value.
4.294 + ///
4.295 + /// This function increases the priority of an item to the given value.
4.296 + /// \param i The item.
4.297 + /// \param p The priority.
4.298 + /// \pre \e i must be stored in the heap with priority at most \e p.
4.299 + void increase(const Item &i, const Prio &p) {
4.300 + int idx = _iim[i];
4.301 + bubbleDown(idx, Pair(i,p), _data.size());
4.302 + }
4.303 +
4.304 + /// \brief Return the state of an item.
4.305 + ///
4.306 + /// This method returns \c PRE_HEAP if the given item has never
4.307 + /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
4.308 + /// and \c POST_HEAP otherwise.
4.309 + /// In the latter case it is possible that the item will get back
4.310 + /// to the heap again.
4.311 + /// \param i The item.
4.312 + State state(const Item &i) const {
4.313 + int s = _iim[i];
4.314 + if (s>=0) s=0;
4.315 + return State(s);
4.316 + }
4.317 +
4.318 + /// \brief Set the state of an item in the heap.
4.319 + ///
4.320 + /// This function sets the state of the given item in the heap.
4.321 + /// It can be used to manually clear the heap when it is important
4.322 + /// to achive better time complexity.
4.323 + /// \param i The item.
4.324 + /// \param st The state. It should not be \c IN_HEAP.
4.325 + void state(const Item& i, State st) {
4.326 + switch (st) {
4.327 + case POST_HEAP:
4.328 + case PRE_HEAP:
4.329 + if (state(i) == IN_HEAP) erase(i);
4.330 + _iim[i] = st;
4.331 + break;
4.332 + case IN_HEAP:
4.333 + break;
4.334 + }
4.335 + }
4.336 +
4.337 + /// \brief Replace an item in the heap.
4.338 + ///
4.339 + /// This function replaces item \c i with item \c j.
4.340 + /// Item \c i must be in the heap, while \c j must be out of the heap.
4.341 + /// After calling this method, item \c i will be out of the
4.342 + /// heap and \c j will be in the heap with the same prioriority
4.343 + /// as item \c i had before.
4.344 + void replace(const Item& i, const Item& j) {
4.345 + int idx=_iim[i];
4.346 + _iim.set(i, _iim[j]);
4.347 + _iim.set(j, idx);
4.348 + _data[idx].first=j;
4.349 + }
4.350 +
4.351 + }; // class KaryHeap
4.352 +
4.353 +} // namespace lemon
4.354 +
4.355 +#endif // LEMON_KARY_HEAP_H
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/lemon/pairing_heap.h Mon Aug 31 10:03:23 2009 +0200
5.3 @@ -0,0 +1,474 @@
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_PAIRING_HEAP_H
5.23 +#define LEMON_PAIRING_HEAP_H
5.24 +
5.25 +///\file
5.26 +///\ingroup heaps
5.27 +///\brief Pairing heap implementation.
5.28 +
5.29 +#include <vector>
5.30 +#include <utility>
5.31 +#include <functional>
5.32 +#include <lemon/math.h>
5.33 +
5.34 +namespace lemon {
5.35 +
5.36 + /// \ingroup heaps
5.37 + ///
5.38 + ///\brief Pairing Heap.
5.39 + ///
5.40 + /// This class implements the \e pairing \e heap data structure.
5.41 + /// It fully conforms to the \ref concepts::Heap "heap concept".
5.42 + ///
5.43 + /// The methods \ref increase() and \ref erase() are not efficient
5.44 + /// in a pairing heap. In case of many calls of these operations,
5.45 + /// it is better to use other heap structure, e.g. \ref BinHeap
5.46 + /// "binary heap".
5.47 + ///
5.48 + /// \tparam PR Type of the priorities of the items.
5.49 + /// \tparam IM A read-writable item map with \c int values, used
5.50 + /// internally to handle the cross references.
5.51 + /// \tparam CMP A functor class for comparing the priorities.
5.52 + /// The default is \c std::less<PR>.
5.53 +#ifdef DOXYGEN
5.54 + template <typename PR, typename IM, typename CMP>
5.55 +#else
5.56 + template <typename PR, typename IM, typename CMP = std::less<PR> >
5.57 +#endif
5.58 + class PairingHeap {
5.59 + public:
5.60 + /// Type of the item-int map.
5.61 + typedef IM ItemIntMap;
5.62 + /// Type of the priorities.
5.63 + typedef PR Prio;
5.64 + /// Type of the items stored in the heap.
5.65 + typedef typename ItemIntMap::Key Item;
5.66 + /// Functor type for comparing the priorities.
5.67 + typedef CMP Compare;
5.68 +
5.69 + /// \brief Type to represent the states of the items.
5.70 + ///
5.71 + /// Each item has a state associated to it. It can be "in heap",
5.72 + /// "pre-heap" or "post-heap". The latter two are indifferent from the
5.73 + /// heap's point of view, but may be useful to the user.
5.74 + ///
5.75 + /// The item-int map must be initialized in such way that it assigns
5.76 + /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
5.77 + enum State {
5.78 + IN_HEAP = 0, ///< = 0.
5.79 + PRE_HEAP = -1, ///< = -1.
5.80 + POST_HEAP = -2 ///< = -2.
5.81 + };
5.82 +
5.83 + private:
5.84 + class store;
5.85 +
5.86 + std::vector<store> _data;
5.87 + int _min;
5.88 + ItemIntMap &_iim;
5.89 + Compare _comp;
5.90 + int _num_items;
5.91 +
5.92 + public:
5.93 + /// \brief Constructor.
5.94 + ///
5.95 + /// Constructor.
5.96 + /// \param map A map that assigns \c int values to the items.
5.97 + /// It is used internally to handle the cross references.
5.98 + /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
5.99 + explicit PairingHeap(ItemIntMap &map)
5.100 + : _min(0), _iim(map), _num_items(0) {}
5.101 +
5.102 + /// \brief Constructor.
5.103 + ///
5.104 + /// Constructor.
5.105 + /// \param map A map that assigns \c int values to the items.
5.106 + /// It is used internally to handle the cross references.
5.107 + /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
5.108 + /// \param comp The function object used for comparing the priorities.
5.109 + PairingHeap(ItemIntMap &map, const Compare &comp)
5.110 + : _min(0), _iim(map), _comp(comp), _num_items(0) {}
5.111 +
5.112 + /// \brief The number of items stored in the heap.
5.113 + ///
5.114 + /// This function returns the number of items stored in the heap.
5.115 + int size() const { return _num_items; }
5.116 +
5.117 + /// \brief Check if the heap is empty.
5.118 + ///
5.119 + /// This function returns \c true if the heap is empty.
5.120 + bool empty() const { return _num_items==0; }
5.121 +
5.122 + /// \brief Make the heap empty.
5.123 + ///
5.124 + /// This functon makes the heap empty.
5.125 + /// It does not change the cross reference map. If you want to reuse
5.126 + /// a heap that is not surely empty, you should first clear it and
5.127 + /// then you should set the cross reference map to \c PRE_HEAP
5.128 + /// for each item.
5.129 + void clear() {
5.130 + _data.clear();
5.131 + _min = 0;
5.132 + _num_items = 0;
5.133 + }
5.134 +
5.135 + /// \brief Set the priority of an item or insert it, if it is
5.136 + /// not stored in the heap.
5.137 + ///
5.138 + /// This method sets the priority of the given item if it is
5.139 + /// already stored in the heap. Otherwise it inserts the given
5.140 + /// item into the heap with the given priority.
5.141 + /// \param item The item.
5.142 + /// \param value The priority.
5.143 + void set (const Item& item, const Prio& value) {
5.144 + int i=_iim[item];
5.145 + if ( i>=0 && _data[i].in ) {
5.146 + if ( _comp(value, _data[i].prio) ) decrease(item, value);
5.147 + if ( _comp(_data[i].prio, value) ) increase(item, value);
5.148 + } else push(item, value);
5.149 + }
5.150 +
5.151 + /// \brief Insert an item into the heap with the given priority.
5.152 + ///
5.153 + /// This function inserts the given item into the heap with the
5.154 + /// given priority.
5.155 + /// \param item The item to insert.
5.156 + /// \param value The priority of the item.
5.157 + /// \pre \e item must not be stored in the heap.
5.158 + void push (const Item& item, const Prio& value) {
5.159 + int i=_iim[item];
5.160 + if( i<0 ) {
5.161 + int s=_data.size();
5.162 + _iim.set(item, s);
5.163 + store st;
5.164 + st.name=item;
5.165 + _data.push_back(st);
5.166 + i=s;
5.167 + } else {
5.168 + _data[i].parent=_data[i].child=-1;
5.169 + _data[i].left_child=false;
5.170 + _data[i].degree=0;
5.171 + _data[i].in=true;
5.172 + }
5.173 +
5.174 + _data[i].prio=value;
5.175 +
5.176 + if ( _num_items!=0 ) {
5.177 + if ( _comp( value, _data[_min].prio) ) {
5.178 + fuse(i,_min);
5.179 + _min=i;
5.180 + }
5.181 + else fuse(_min,i);
5.182 + }
5.183 + else _min=i;
5.184 +
5.185 + ++_num_items;
5.186 + }
5.187 +
5.188 + /// \brief Return the item having minimum priority.
5.189 + ///
5.190 + /// This function returns the item having minimum priority.
5.191 + /// \pre The heap must be non-empty.
5.192 + Item top() const { return _data[_min].name; }
5.193 +
5.194 + /// \brief The minimum priority.
5.195 + ///
5.196 + /// This function returns the minimum priority.
5.197 + /// \pre The heap must be non-empty.
5.198 + const Prio& prio() const { return _data[_min].prio; }
5.199 +
5.200 + /// \brief The priority of the given item.
5.201 + ///
5.202 + /// This function returns the priority of the given item.
5.203 + /// \param item The item.
5.204 + /// \pre \e item must be in the heap.
5.205 + const Prio& operator[](const Item& item) const {
5.206 + return _data[_iim[item]].prio;
5.207 + }
5.208 +
5.209 + /// \brief Remove the item having minimum priority.
5.210 + ///
5.211 + /// This function removes the item having minimum priority.
5.212 + /// \pre The heap must be non-empty.
5.213 + void pop() {
5.214 + std::vector<int> trees;
5.215 + int i=0, child_right = 0;
5.216 + _data[_min].in=false;
5.217 +
5.218 + if( -1!=_data[_min].child ) {
5.219 + i=_data[_min].child;
5.220 + trees.push_back(i);
5.221 + _data[i].parent = -1;
5.222 + _data[_min].child = -1;
5.223 +
5.224 + int ch=-1;
5.225 + while( _data[i].child!=-1 ) {
5.226 + ch=_data[i].child;
5.227 + if( _data[ch].left_child && i==_data[ch].parent ) {
5.228 + break;
5.229 + } else {
5.230 + if( _data[ch].left_child ) {
5.231 + child_right=_data[ch].parent;
5.232 + _data[ch].parent = i;
5.233 + --_data[i].degree;
5.234 + }
5.235 + else {
5.236 + child_right=ch;
5.237 + _data[i].child=-1;
5.238 + _data[i].degree=0;
5.239 + }
5.240 + _data[child_right].parent = -1;
5.241 + trees.push_back(child_right);
5.242 + i = child_right;
5.243 + }
5.244 + }
5.245 +
5.246 + int num_child = trees.size();
5.247 + int other;
5.248 + for( i=0; i<num_child-1; i+=2 ) {
5.249 + if ( !_comp(_data[trees[i]].prio, _data[trees[i+1]].prio) ) {
5.250 + other=trees[i];
5.251 + trees[i]=trees[i+1];
5.252 + trees[i+1]=other;
5.253 + }
5.254 + fuse( trees[i], trees[i+1] );
5.255 + }
5.256 +
5.257 + i = (0==(num_child % 2)) ? num_child-2 : num_child-1;
5.258 + while(i>=2) {
5.259 + if ( _comp(_data[trees[i]].prio, _data[trees[i-2]].prio) ) {
5.260 + other=trees[i];
5.261 + trees[i]=trees[i-2];
5.262 + trees[i-2]=other;
5.263 + }
5.264 + fuse( trees[i-2], trees[i] );
5.265 + i-=2;
5.266 + }
5.267 + _min = trees[0];
5.268 + }
5.269 + else {
5.270 + _min = _data[_min].child;
5.271 + }
5.272 +
5.273 + if (_min >= 0) _data[_min].left_child = false;
5.274 + --_num_items;
5.275 + }
5.276 +
5.277 + /// \brief Remove the given item from the heap.
5.278 + ///
5.279 + /// This function removes the given item from the heap if it is
5.280 + /// already stored.
5.281 + /// \param item The item to delete.
5.282 + /// \pre \e item must be in the heap.
5.283 + void erase (const Item& item) {
5.284 + int i=_iim[item];
5.285 + if ( i>=0 && _data[i].in ) {
5.286 + decrease( item, _data[_min].prio-1 );
5.287 + pop();
5.288 + }
5.289 + }
5.290 +
5.291 + /// \brief Decrease the priority of an item to the given value.
5.292 + ///
5.293 + /// This function decreases the priority of an item to the given value.
5.294 + /// \param item The item.
5.295 + /// \param value The priority.
5.296 + /// \pre \e item must be stored in the heap with priority at least \e value.
5.297 + void decrease (Item item, const Prio& value) {
5.298 + int i=_iim[item];
5.299 + _data[i].prio=value;
5.300 + int p=_data[i].parent;
5.301 +
5.302 + if( _data[i].left_child && i!=_data[p].child ) {
5.303 + p=_data[p].parent;
5.304 + }
5.305 +
5.306 + if ( p!=-1 && _comp(value,_data[p].prio) ) {
5.307 + cut(i,p);
5.308 + if ( _comp(_data[_min].prio,value) ) {
5.309 + fuse(_min,i);
5.310 + } else {
5.311 + fuse(i,_min);
5.312 + _min=i;
5.313 + }
5.314 + }
5.315 + }
5.316 +
5.317 + /// \brief Increase the priority of an item to the given value.
5.318 + ///
5.319 + /// This function increases the priority of an item to the given value.
5.320 + /// \param item The item.
5.321 + /// \param value The priority.
5.322 + /// \pre \e item must be stored in the heap with priority at most \e value.
5.323 + void increase (Item item, const Prio& value) {
5.324 + erase(item);
5.325 + push(item,value);
5.326 + }
5.327 +
5.328 + /// \brief Return the state of an item.
5.329 + ///
5.330 + /// This method returns \c PRE_HEAP if the given item has never
5.331 + /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
5.332 + /// and \c POST_HEAP otherwise.
5.333 + /// In the latter case it is possible that the item will get back
5.334 + /// to the heap again.
5.335 + /// \param item The item.
5.336 + State state(const Item &item) const {
5.337 + int i=_iim[item];
5.338 + if( i>=0 ) {
5.339 + if( _data[i].in ) i=0;
5.340 + else i=-2;
5.341 + }
5.342 + return State(i);
5.343 + }
5.344 +
5.345 + /// \brief Set the state of an item in the heap.
5.346 + ///
5.347 + /// This function sets the state of the given item in the heap.
5.348 + /// It can be used to manually clear the heap when it is important
5.349 + /// to achive better time complexity.
5.350 + /// \param i The item.
5.351 + /// \param st The state. It should not be \c IN_HEAP.
5.352 + void state(const Item& i, State st) {
5.353 + switch (st) {
5.354 + case POST_HEAP:
5.355 + case PRE_HEAP:
5.356 + if (state(i) == IN_HEAP) erase(i);
5.357 + _iim[i]=st;
5.358 + break;
5.359 + case IN_HEAP:
5.360 + break;
5.361 + }
5.362 + }
5.363 +
5.364 + private:
5.365 +
5.366 + void cut(int a, int b) {
5.367 + int child_a;
5.368 + switch (_data[a].degree) {
5.369 + case 2:
5.370 + child_a = _data[_data[a].child].parent;
5.371 + if( _data[a].left_child ) {
5.372 + _data[child_a].left_child=true;
5.373 + _data[b].child=child_a;
5.374 + _data[child_a].parent=_data[a].parent;
5.375 + }
5.376 + else {
5.377 + _data[child_a].left_child=false;
5.378 + _data[child_a].parent=b;
5.379 + if( a!=_data[b].child )
5.380 + _data[_data[b].child].parent=child_a;
5.381 + else
5.382 + _data[b].child=child_a;
5.383 + }
5.384 + --_data[a].degree;
5.385 + _data[_data[a].child].parent=a;
5.386 + break;
5.387 +
5.388 + case 1:
5.389 + child_a = _data[a].child;
5.390 + if( !_data[child_a].left_child ) {
5.391 + --_data[a].degree;
5.392 + if( _data[a].left_child ) {
5.393 + _data[child_a].left_child=true;
5.394 + _data[child_a].parent=_data[a].parent;
5.395 + _data[b].child=child_a;
5.396 + }
5.397 + else {
5.398 + _data[child_a].left_child=false;
5.399 + _data[child_a].parent=b;
5.400 + if( a!=_data[b].child )
5.401 + _data[_data[b].child].parent=child_a;
5.402 + else
5.403 + _data[b].child=child_a;
5.404 + }
5.405 + _data[a].child=-1;
5.406 + }
5.407 + else {
5.408 + --_data[b].degree;
5.409 + if( _data[a].left_child ) {
5.410 + _data[b].child =
5.411 + (1==_data[b].degree) ? _data[a].parent : -1;
5.412 + } else {
5.413 + if (1==_data[b].degree)
5.414 + _data[_data[b].child].parent=b;
5.415 + else
5.416 + _data[b].child=-1;
5.417 + }
5.418 + }
5.419 + break;
5.420 +
5.421 + case 0:
5.422 + --_data[b].degree;
5.423 + if( _data[a].left_child ) {
5.424 + _data[b].child =
5.425 + (0!=_data[b].degree) ? _data[a].parent : -1;
5.426 + } else {
5.427 + if( 0!=_data[b].degree )
5.428 + _data[_data[b].child].parent=b;
5.429 + else
5.430 + _data[b].child=-1;
5.431 + }
5.432 + break;
5.433 + }
5.434 + _data[a].parent=-1;
5.435 + _data[a].left_child=false;
5.436 + }
5.437 +
5.438 + void fuse(int a, int b) {
5.439 + int child_a = _data[a].child;
5.440 + int child_b = _data[b].child;
5.441 + _data[a].child=b;
5.442 + _data[b].parent=a;
5.443 + _data[b].left_child=true;
5.444 +
5.445 + if( -1!=child_a ) {
5.446 + _data[b].child=child_a;
5.447 + _data[child_a].parent=b;
5.448 + _data[child_a].left_child=false;
5.449 + ++_data[b].degree;
5.450 +
5.451 + if( -1!=child_b ) {
5.452 + _data[b].child=child_b;
5.453 + _data[child_b].parent=child_a;
5.454 + }
5.455 + }
5.456 + else { ++_data[a].degree; }
5.457 + }
5.458 +
5.459 + class store {
5.460 + friend class PairingHeap;
5.461 +
5.462 + Item name;
5.463 + int parent;
5.464 + int child;
5.465 + bool left_child;
5.466 + int degree;
5.467 + bool in;
5.468 + Prio prio;
5.469 +
5.470 + store() : parent(-1), child(-1), left_child(false), degree(0), in(true) {}
5.471 + };
5.472 + };
5.473 +
5.474 +} //namespace lemon
5.475 +
5.476 +#endif //LEMON_PAIRING_HEAP_H
5.477 +
6.1 --- a/test/heap_test.cc Mon Aug 31 08:32:25 2009 +0200
6.2 +++ b/test/heap_test.cc Mon Aug 31 10:03:23 2009 +0200
6.3 @@ -25,14 +25,17 @@
6.4 #include <lemon/concepts/heap.h>
6.5
6.6 #include <lemon/smart_graph.h>
6.7 -
6.8 #include <lemon/lgf_reader.h>
6.9 #include <lemon/dijkstra.h>
6.10 #include <lemon/maps.h>
6.11
6.12 #include <lemon/bin_heap.h>
6.13 +#include <lemon/fourary_heap.h>
6.14 +#include <lemon/kary_heap.h>
6.15 #include <lemon/fib_heap.h>
6.16 +#include <lemon/pairing_heap.h>
6.17 #include <lemon/radix_heap.h>
6.18 +#include <lemon/binom_heap.h>
6.19 #include <lemon/bucket_heap.h>
6.20
6.21 #include "test_tools.h"
6.22 @@ -89,18 +92,16 @@
6.23 template <typename Heap>
6.24 void heapSortTest() {
6.25 RangeMap<int> map(test_len, -1);
6.26 -
6.27 Heap heap(map);
6.28
6.29 std::vector<int> v(test_len);
6.30 -
6.31 for (int i = 0; i < test_len; ++i) {
6.32 v[i] = test_seq[i];
6.33 heap.push(i, v[i]);
6.34 }
6.35 std::sort(v.begin(), v.end());
6.36 for (int i = 0; i < test_len; ++i) {
6.37 - check(v[i] == heap.prio() ,"Wrong order in heap sort.");
6.38 + check(v[i] == heap.prio(), "Wrong order in heap sort.");
6.39 heap.pop();
6.40 }
6.41 }
6.42 @@ -112,7 +113,6 @@
6.43 Heap heap(map);
6.44
6.45 std::vector<int> v(test_len);
6.46 -
6.47 for (int i = 0; i < test_len; ++i) {
6.48 v[i] = test_seq[i];
6.49 heap.push(i, v[i]);
6.50 @@ -123,13 +123,11 @@
6.51 }
6.52 std::sort(v.begin(), v.end());
6.53 for (int i = 0; i < test_len; ++i) {
6.54 - check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
6.55 + check(v[i] == heap.prio(), "Wrong order in heap increase test.");
6.56 heap.pop();
6.57 }
6.58 }
6.59
6.60 -
6.61 -
6.62 template <typename Heap>
6.63 void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length,
6.64 Node source) {
6.65 @@ -144,7 +142,7 @@
6.66 Node t = digraph.target(a);
6.67 if (dijkstra.reached(s)) {
6.68 check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
6.69 - "Error in a shortest path tree!");
6.70 + "Error in shortest path tree.");
6.71 }
6.72 }
6.73
6.74 @@ -153,7 +151,7 @@
6.75 Arc a = dijkstra.predArc(n);
6.76 Node s = digraph.source(a);
6.77 check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
6.78 - "Error in a shortest path tree!");
6.79 + "Error in shortest path tree.");
6.80 }
6.81 }
6.82
6.83 @@ -175,6 +173,7 @@
6.84 node("source", source).
6.85 run();
6.86
6.87 + // BinHeap
6.88 {
6.89 typedef BinHeap<Prio, ItemIntMap> IntHeap;
6.90 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
6.91 @@ -186,6 +185,31 @@
6.92 dijkstraHeapTest<NodeHeap>(digraph, length, source);
6.93 }
6.94
6.95 + // FouraryHeap
6.96 + {
6.97 + typedef FouraryHeap<Prio, ItemIntMap> IntHeap;
6.98 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
6.99 + heapSortTest<IntHeap>();
6.100 + heapIncreaseTest<IntHeap>();
6.101 +
6.102 + typedef FouraryHeap<Prio, IntNodeMap > NodeHeap;
6.103 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
6.104 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
6.105 + }
6.106 +
6.107 + // KaryHeap
6.108 + {
6.109 + typedef KaryHeap<Prio, ItemIntMap> IntHeap;
6.110 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
6.111 + heapSortTest<IntHeap>();
6.112 + heapIncreaseTest<IntHeap>();
6.113 +
6.114 + typedef KaryHeap<Prio, IntNodeMap > NodeHeap;
6.115 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
6.116 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
6.117 + }
6.118 +
6.119 + // FibHeap
6.120 {
6.121 typedef FibHeap<Prio, ItemIntMap> IntHeap;
6.122 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
6.123 @@ -197,6 +221,19 @@
6.124 dijkstraHeapTest<NodeHeap>(digraph, length, source);
6.125 }
6.126
6.127 + // PairingHeap
6.128 + {
6.129 + typedef PairingHeap<Prio, ItemIntMap> IntHeap;
6.130 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
6.131 + heapSortTest<IntHeap>();
6.132 + heapIncreaseTest<IntHeap>();
6.133 +
6.134 + typedef PairingHeap<Prio, IntNodeMap > NodeHeap;
6.135 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
6.136 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
6.137 + }
6.138 +
6.139 + // RadixHeap
6.140 {
6.141 typedef RadixHeap<ItemIntMap> IntHeap;
6.142 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
6.143 @@ -208,6 +245,19 @@
6.144 dijkstraHeapTest<NodeHeap>(digraph, length, source);
6.145 }
6.146
6.147 + // BinomHeap
6.148 + {
6.149 + typedef BinomHeap<Prio, ItemIntMap> IntHeap;
6.150 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
6.151 + heapSortTest<IntHeap>();
6.152 + heapIncreaseTest<IntHeap>();
6.153 +
6.154 + typedef BinomHeap<Prio, IntNodeMap > NodeHeap;
6.155 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
6.156 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
6.157 + }
6.158 +
6.159 + // BucketHeap, SimpleBucketHeap
6.160 {
6.161 typedef BucketHeap<ItemIntMap> IntHeap;
6.162 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
6.163 @@ -217,8 +267,10 @@
6.164 typedef BucketHeap<IntNodeMap > NodeHeap;
6.165 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
6.166 dijkstraHeapTest<NodeHeap>(digraph, length, source);
6.167 +
6.168 + typedef SimpleBucketHeap<ItemIntMap> SimpleIntHeap;
6.169 + heapSortTest<SimpleIntHeap>();
6.170 }
6.171
6.172 -
6.173 return 0;
6.174 }