1.1 --- a/lemon/Makefile.am Sat Sep 26 07:21:54 2009 +0200
1.2 +++ b/lemon/Makefile.am Tue Sep 29 13:32:01 2009 +0200
1.3 @@ -60,7 +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/binomial_heap.h \
1.9 lemon/bucket_heap.h \
1.10 lemon/cbc.h \
1.11 lemon/circulation.h \
1.12 @@ -72,6 +72,7 @@
1.13 lemon/core.h \
1.14 lemon/cplex.h \
1.15 lemon/dfs.h \
1.16 + lemon/dheap.h \
1.17 lemon/dijkstra.h \
1.18 lemon/dim2.h \
1.19 lemon/dimacs.h \
1.20 @@ -80,14 +81,12 @@
1.21 lemon/error.h \
1.22 lemon/euler.h \
1.23 lemon/fib_heap.h \
1.24 - lemon/fourary_heap.h \
1.25 lemon/full_graph.h \
1.26 lemon/glpk.h \
1.27 lemon/gomory_hu.h \
1.28 lemon/graph_to_eps.h \
1.29 lemon/grid_graph.h \
1.30 lemon/hypercube_graph.h \
1.31 - lemon/kary_heap.h \
1.32 lemon/kruskal.h \
1.33 lemon/hao_orlin.h \
1.34 lemon/lgf_reader.h \
1.35 @@ -105,6 +104,7 @@
1.36 lemon/pairing_heap.h \
1.37 lemon/path.h \
1.38 lemon/preflow.h \
1.39 + lemon/quad_heap.h \
1.40 lemon/radix_heap.h \
1.41 lemon/radix_sort.h \
1.42 lemon/random.h \
2.1 --- a/lemon/binom_heap.h Sat Sep 26 07:21:54 2009 +0200
2.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
2.3 @@ -1,445 +0,0 @@
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/binomial_heap.h Tue Sep 29 13:32:01 2009 +0200
3.3 @@ -0,0 +1,445 @@
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_BINOMIAL_HEAP_H
3.23 +#define LEMON_BINOMIAL_HEAP_H
3.24 +
3.25 +///\file
3.26 +///\ingroup heaps
3.27 +///\brief Binomial Heap implementation.
3.28 +
3.29 +#include <vector>
3.30 +#include <utility>
3.31 +#include <functional>
3.32 +#include <lemon/math.h>
3.33 +#include <lemon/counter.h>
3.34 +
3.35 +namespace lemon {
3.36 +
3.37 + /// \ingroup heaps
3.38 + ///
3.39 + ///\brief Binomial heap data structure.
3.40 + ///
3.41 + /// This class implements the \e binomial \e heap data structure.
3.42 + /// It fully conforms to the \ref concepts::Heap "heap concept".
3.43 + ///
3.44 + /// The methods \ref increase() and \ref erase() are not efficient
3.45 + /// in a binomial heap. In case of many calls of these operations,
3.46 + /// it is better to use other heap structure, e.g. \ref BinHeap
3.47 + /// "binary heap".
3.48 + ///
3.49 + /// \tparam PR Type of the priorities of the items.
3.50 + /// \tparam IM A read-writable item map with \c int values, used
3.51 + /// internally to handle the cross references.
3.52 + /// \tparam CMP A functor class for comparing the priorities.
3.53 + /// The default is \c std::less<PR>.
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 BinomialHeap {
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 + /// Functor type for comparing the priorities.
3.68 + typedef CMP Compare;
3.69 +
3.70 + /// \brief Type to represent the states of the items.
3.71 + ///
3.72 + /// Each item has a state associated to it. It can be "in heap",
3.73 + /// "pre-heap" or "post-heap". The latter two are indifferent from the
3.74 + /// heap's point of view, but may be useful to the user.
3.75 + ///
3.76 + /// The item-int map must be initialized in such way that it assigns
3.77 + /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
3.78 + enum State {
3.79 + IN_HEAP = 0, ///< = 0.
3.80 + PRE_HEAP = -1, ///< = -1.
3.81 + POST_HEAP = -2 ///< = -2.
3.82 + };
3.83 +
3.84 + private:
3.85 + class Store;
3.86 +
3.87 + std::vector<Store> _data;
3.88 + int _min, _head;
3.89 + ItemIntMap &_iim;
3.90 + Compare _comp;
3.91 + int _num_items;
3.92 +
3.93 + public:
3.94 + /// \brief Constructor.
3.95 + ///
3.96 + /// Constructor.
3.97 + /// \param map A map that assigns \c int values to the items.
3.98 + /// It is used internally to handle the cross references.
3.99 + /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
3.100 + explicit BinomialHeap(ItemIntMap &map)
3.101 + : _min(0), _head(-1), _iim(map), _num_items(0) {}
3.102 +
3.103 + /// \brief Constructor.
3.104 + ///
3.105 + /// Constructor.
3.106 + /// \param map A map that assigns \c int values to the items.
3.107 + /// It is used internally to handle the cross references.
3.108 + /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
3.109 + /// \param comp The function object used for comparing the priorities.
3.110 + BinomialHeap(ItemIntMap &map, const Compare &comp)
3.111 + : _min(0), _head(-1), _iim(map), _comp(comp), _num_items(0) {}
3.112 +
3.113 + /// \brief The number of items stored in the heap.
3.114 + ///
3.115 + /// This function returns the number of items stored in the heap.
3.116 + int size() const { return _num_items; }
3.117 +
3.118 + /// \brief Check if the heap is empty.
3.119 + ///
3.120 + /// This function returns \c true if the heap is empty.
3.121 + bool empty() const { return _num_items==0; }
3.122 +
3.123 + /// \brief Make the heap empty.
3.124 + ///
3.125 + /// This functon makes the heap empty.
3.126 + /// It does not change the cross reference map. If you want to reuse
3.127 + /// a heap that is not surely empty, you should first clear it and
3.128 + /// then you should set the cross reference map to \c PRE_HEAP
3.129 + /// for each item.
3.130 + void clear() {
3.131 + _data.clear(); _min=0; _num_items=0; _head=-1;
3.132 + }
3.133 +
3.134 + /// \brief Set the priority of an item or insert it, if it is
3.135 + /// not stored in the heap.
3.136 + ///
3.137 + /// This method sets the priority of the given item if it is
3.138 + /// already stored in the heap. Otherwise it inserts the given
3.139 + /// item into the heap with the given priority.
3.140 + /// \param item The item.
3.141 + /// \param value The priority.
3.142 + void set (const Item& item, const Prio& value) {
3.143 + int i=_iim[item];
3.144 + if ( i >= 0 && _data[i].in ) {
3.145 + if ( _comp(value, _data[i].prio) ) decrease(item, value);
3.146 + if ( _comp(_data[i].prio, value) ) increase(item, value);
3.147 + } else push(item, value);
3.148 + }
3.149 +
3.150 + /// \brief Insert an item into the heap with the given priority.
3.151 + ///
3.152 + /// This function inserts the given item into the heap with the
3.153 + /// given priority.
3.154 + /// \param item The item to insert.
3.155 + /// \param value The priority of the item.
3.156 + /// \pre \e item must not be stored in the heap.
3.157 + void push (const Item& item, const Prio& value) {
3.158 + int i=_iim[item];
3.159 + if ( i<0 ) {
3.160 + int s=_data.size();
3.161 + _iim.set( item,s );
3.162 + Store st;
3.163 + st.name=item;
3.164 + st.prio=value;
3.165 + _data.push_back(st);
3.166 + i=s;
3.167 + }
3.168 + else {
3.169 + _data[i].parent=_data[i].right_neighbor=_data[i].child=-1;
3.170 + _data[i].degree=0;
3.171 + _data[i].in=true;
3.172 + _data[i].prio=value;
3.173 + }
3.174 +
3.175 + if( 0==_num_items ) {
3.176 + _head=i;
3.177 + _min=i;
3.178 + } else {
3.179 + merge(i);
3.180 + if( _comp(_data[i].prio, _data[_min].prio) ) _min=i;
3.181 + }
3.182 + ++_num_items;
3.183 + }
3.184 +
3.185 + /// \brief Return the item having minimum priority.
3.186 + ///
3.187 + /// This function returns the item having minimum priority.
3.188 + /// \pre The heap must be non-empty.
3.189 + Item top() const { return _data[_min].name; }
3.190 +
3.191 + /// \brief The minimum priority.
3.192 + ///
3.193 + /// This function returns the minimum priority.
3.194 + /// \pre The heap must be non-empty.
3.195 + Prio prio() const { return _data[_min].prio; }
3.196 +
3.197 + /// \brief The priority of the given item.
3.198 + ///
3.199 + /// This function returns the priority of the given item.
3.200 + /// \param item The item.
3.201 + /// \pre \e item must be in the heap.
3.202 + const Prio& operator[](const Item& item) const {
3.203 + return _data[_iim[item]].prio;
3.204 + }
3.205 +
3.206 + /// \brief Remove the item having minimum priority.
3.207 + ///
3.208 + /// This function removes the item having minimum priority.
3.209 + /// \pre The heap must be non-empty.
3.210 + void pop() {
3.211 + _data[_min].in=false;
3.212 +
3.213 + int head_child=-1;
3.214 + if ( _data[_min].child!=-1 ) {
3.215 + int child=_data[_min].child;
3.216 + int neighb;
3.217 + while( child!=-1 ) {
3.218 + neighb=_data[child].right_neighbor;
3.219 + _data[child].parent=-1;
3.220 + _data[child].right_neighbor=head_child;
3.221 + head_child=child;
3.222 + child=neighb;
3.223 + }
3.224 + }
3.225 +
3.226 + if ( _data[_head].right_neighbor==-1 ) {
3.227 + // there was only one root
3.228 + _head=head_child;
3.229 + }
3.230 + else {
3.231 + // there were more roots
3.232 + if( _head!=_min ) { unlace(_min); }
3.233 + else { _head=_data[_head].right_neighbor; }
3.234 + merge(head_child);
3.235 + }
3.236 + _min=findMin();
3.237 + --_num_items;
3.238 + }
3.239 +
3.240 + /// \brief Remove the given item from the heap.
3.241 + ///
3.242 + /// This function removes the given item from the heap if it is
3.243 + /// already stored.
3.244 + /// \param item The item to delete.
3.245 + /// \pre \e item must be in the heap.
3.246 + void erase (const Item& item) {
3.247 + int i=_iim[item];
3.248 + if ( i >= 0 && _data[i].in ) {
3.249 + decrease( item, _data[_min].prio-1 );
3.250 + pop();
3.251 + }
3.252 + }
3.253 +
3.254 + /// \brief Decrease the priority of an item to the given value.
3.255 + ///
3.256 + /// This function decreases the priority of an item to the given value.
3.257 + /// \param item The item.
3.258 + /// \param value The priority.
3.259 + /// \pre \e item must be stored in the heap with priority at least \e value.
3.260 + void decrease (Item item, const Prio& value) {
3.261 + int i=_iim[item];
3.262 + int p=_data[i].parent;
3.263 + _data[i].prio=value;
3.264 +
3.265 + while( p!=-1 && _comp(value, _data[p].prio) ) {
3.266 + _data[i].name=_data[p].name;
3.267 + _data[i].prio=_data[p].prio;
3.268 + _data[p].name=item;
3.269 + _data[p].prio=value;
3.270 + _iim[_data[i].name]=i;
3.271 + i=p;
3.272 + p=_data[p].parent;
3.273 + }
3.274 + _iim[item]=i;
3.275 + if ( _comp(value, _data[_min].prio) ) _min=i;
3.276 + }
3.277 +
3.278 + /// \brief Increase the priority of an item to the given value.
3.279 + ///
3.280 + /// This function increases the priority of an item to the given value.
3.281 + /// \param item The item.
3.282 + /// \param value The priority.
3.283 + /// \pre \e item must be stored in the heap with priority at most \e value.
3.284 + void increase (Item item, const Prio& value) {
3.285 + erase(item);
3.286 + push(item, value);
3.287 + }
3.288 +
3.289 + /// \brief Return the state of an item.
3.290 + ///
3.291 + /// This method returns \c PRE_HEAP if the given item has never
3.292 + /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
3.293 + /// and \c POST_HEAP otherwise.
3.294 + /// In the latter case it is possible that the item will get back
3.295 + /// to the heap again.
3.296 + /// \param item The item.
3.297 + State state(const Item &item) const {
3.298 + int i=_iim[item];
3.299 + if( i>=0 ) {
3.300 + if ( _data[i].in ) i=0;
3.301 + else i=-2;
3.302 + }
3.303 + return State(i);
3.304 + }
3.305 +
3.306 + /// \brief Set the state of an item in the heap.
3.307 + ///
3.308 + /// This function sets the state of the given item in the heap.
3.309 + /// It can be used to manually clear the heap when it is important
3.310 + /// to achive better time complexity.
3.311 + /// \param i The item.
3.312 + /// \param st The state. It should not be \c IN_HEAP.
3.313 + void state(const Item& i, State st) {
3.314 + switch (st) {
3.315 + case POST_HEAP:
3.316 + case PRE_HEAP:
3.317 + if (state(i) == IN_HEAP) {
3.318 + erase(i);
3.319 + }
3.320 + _iim[i] = st;
3.321 + break;
3.322 + case IN_HEAP:
3.323 + break;
3.324 + }
3.325 + }
3.326 +
3.327 + private:
3.328 +
3.329 + // Find the minimum of the roots
3.330 + int findMin() {
3.331 + if( _head!=-1 ) {
3.332 + int min_loc=_head, min_val=_data[_head].prio;
3.333 + for( int x=_data[_head].right_neighbor; x!=-1;
3.334 + x=_data[x].right_neighbor ) {
3.335 + if( _comp( _data[x].prio,min_val ) ) {
3.336 + min_val=_data[x].prio;
3.337 + min_loc=x;
3.338 + }
3.339 + }
3.340 + return min_loc;
3.341 + }
3.342 + else return -1;
3.343 + }
3.344 +
3.345 + // Merge the heap with another heap starting at the given position
3.346 + void merge(int a) {
3.347 + if( _head==-1 || a==-1 ) return;
3.348 + if( _data[a].right_neighbor==-1 &&
3.349 + _data[a].degree<=_data[_head].degree ) {
3.350 + _data[a].right_neighbor=_head;
3.351 + _head=a;
3.352 + } else {
3.353 + interleave(a);
3.354 + }
3.355 + if( _data[_head].right_neighbor==-1 ) return;
3.356 +
3.357 + int x=_head;
3.358 + int x_prev=-1, x_next=_data[x].right_neighbor;
3.359 + while( x_next!=-1 ) {
3.360 + if( _data[x].degree!=_data[x_next].degree ||
3.361 + ( _data[x_next].right_neighbor!=-1 &&
3.362 + _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) {
3.363 + x_prev=x;
3.364 + x=x_next;
3.365 + }
3.366 + else {
3.367 + if( _comp(_data[x_next].prio,_data[x].prio) ) {
3.368 + if( x_prev==-1 ) {
3.369 + _head=x_next;
3.370 + } else {
3.371 + _data[x_prev].right_neighbor=x_next;
3.372 + }
3.373 + fuse(x,x_next);
3.374 + x=x_next;
3.375 + }
3.376 + else {
3.377 + _data[x].right_neighbor=_data[x_next].right_neighbor;
3.378 + fuse(x_next,x);
3.379 + }
3.380 + }
3.381 + x_next=_data[x].right_neighbor;
3.382 + }
3.383 + }
3.384 +
3.385 + // Interleave the elements of the given list into the list of the roots
3.386 + void interleave(int a) {
3.387 + int p=_head, q=a;
3.388 + int curr=_data.size();
3.389 + _data.push_back(Store());
3.390 +
3.391 + while( p!=-1 || q!=-1 ) {
3.392 + if( q==-1 || ( p!=-1 && _data[p].degree<_data[q].degree ) ) {
3.393 + _data[curr].right_neighbor=p;
3.394 + curr=p;
3.395 + p=_data[p].right_neighbor;
3.396 + }
3.397 + else {
3.398 + _data[curr].right_neighbor=q;
3.399 + curr=q;
3.400 + q=_data[q].right_neighbor;
3.401 + }
3.402 + }
3.403 +
3.404 + _head=_data.back().right_neighbor;
3.405 + _data.pop_back();
3.406 + }
3.407 +
3.408 + // Lace node a under node b
3.409 + void fuse(int a, int b) {
3.410 + _data[a].parent=b;
3.411 + _data[a].right_neighbor=_data[b].child;
3.412 + _data[b].child=a;
3.413 +
3.414 + ++_data[b].degree;
3.415 + }
3.416 +
3.417 + // Unlace node a (if it has siblings)
3.418 + void unlace(int a) {
3.419 + int neighb=_data[a].right_neighbor;
3.420 + int other=_head;
3.421 +
3.422 + while( _data[other].right_neighbor!=a )
3.423 + other=_data[other].right_neighbor;
3.424 + _data[other].right_neighbor=neighb;
3.425 + }
3.426 +
3.427 + private:
3.428 +
3.429 + class Store {
3.430 + friend class BinomialHeap;
3.431 +
3.432 + Item name;
3.433 + int parent;
3.434 + int right_neighbor;
3.435 + int child;
3.436 + int degree;
3.437 + bool in;
3.438 + Prio prio;
3.439 +
3.440 + Store() : parent(-1), right_neighbor(-1), child(-1), degree(0),
3.441 + in(true) {}
3.442 + };
3.443 + };
3.444 +
3.445 +} //namespace lemon
3.446 +
3.447 +#endif //LEMON_BINOMIAL_HEAP_H
3.448 +
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/lemon/dheap.h Tue Sep 29 13:32:01 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_DHEAP_H
4.23 +#define LEMON_DHEAP_H
4.24 +
4.25 +///\ingroup heaps
4.26 +///\file
4.27 +///\brief D-ary 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 D-ary heap data structure.
4.38 + ///
4.39 + /// This class implements the \e D-ary \e heap data structure.
4.40 + /// It fully conforms to the \ref concepts::Heap "heap concept".
4.41 + ///
4.42 + /// The \ref DHeap "D-ary heap" is a generalization of the
4.43 + /// \ref BinHeap "binary heap" structure, its nodes have at most
4.44 + /// \c D children, instead of two.
4.45 + /// \ref BinHeap and \ref QuadHeap are specialized implementations
4.46 + /// of this structure for <tt>D=2</tt> and <tt>D=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 D The degree of the heap, each node have at most \e D
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 D, typename CMP>
4.62 +#else
4.63 + template <typename PR, typename IM, int D = 16,
4.64 + typename CMP = std::less<PR> >
4.65 +#endif
4.66 + class DHeap {
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 DHeap(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 + DHeap(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)/D; }
4.138 + int firstChild(int i) { return D*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+D<=length ) {
4.158 + int min=child;
4.159 + for (int i=1; i<D; ++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 DHeap
4.352 +
4.353 +} // namespace lemon
4.354 +
4.355 +#endif // LEMON_DHEAP_H
5.1 --- a/lemon/fourary_heap.h Sat Sep 26 07:21:54 2009 +0200
5.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
5.3 @@ -1,342 +0,0 @@
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_FOURARY_HEAP_H
5.23 -#define LEMON_FOURARY_HEAP_H
5.24 -
5.25 -///\ingroup heaps
5.26 -///\file
5.27 -///\brief Fourary heap implementation.
5.28 -
5.29 -#include <vector>
5.30 -#include <utility>
5.31 -#include <functional>
5.32 -
5.33 -namespace lemon {
5.34 -
5.35 - /// \ingroup heaps
5.36 - ///
5.37 - ///\brief Fourary heap data structure.
5.38 - ///
5.39 - /// This class implements the \e fourary \e heap data structure.
5.40 - /// It fully conforms to the \ref concepts::Heap "heap concept".
5.41 - ///
5.42 - /// The fourary heap is a specialization of the \ref KaryHeap "K-ary heap"
5.43 - /// for <tt>K=4</tt>. It is similar to the \ref BinHeap "binary heap",
5.44 - /// but its nodes have at most four children, instead of two.
5.45 - ///
5.46 - /// \tparam PR Type of the priorities of the items.
5.47 - /// \tparam IM A read-writable item map with \c int values, used
5.48 - /// internally to handle the cross references.
5.49 - /// \tparam CMP A functor class for comparing the priorities.
5.50 - /// The default is \c std::less<PR>.
5.51 - ///
5.52 - ///\sa BinHeap
5.53 - ///\sa KaryHeap
5.54 -#ifdef DOXYGEN
5.55 - template <typename PR, typename IM, typename CMP>
5.56 -#else
5.57 - template <typename PR, typename IM, typename CMP = std::less<PR> >
5.58 -#endif
5.59 - class FouraryHeap {
5.60 - public:
5.61 - /// Type of the item-int map.
5.62 - typedef IM ItemIntMap;
5.63 - /// Type of the priorities.
5.64 - typedef PR Prio;
5.65 - /// Type of the items stored in the heap.
5.66 - typedef typename ItemIntMap::Key Item;
5.67 - /// Type of the item-priority pairs.
5.68 - typedef std::pair<Item,Prio> Pair;
5.69 - /// Functor type for comparing the priorities.
5.70 - typedef CMP Compare;
5.71 -
5.72 - /// \brief Type to represent the states of the items.
5.73 - ///
5.74 - /// Each item has a state associated to it. It can be "in heap",
5.75 - /// "pre-heap" or "post-heap". The latter two are indifferent from the
5.76 - /// heap's point of view, but may be useful to the user.
5.77 - ///
5.78 - /// The item-int map must be initialized in such way that it assigns
5.79 - /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
5.80 - enum State {
5.81 - IN_HEAP = 0, ///< = 0.
5.82 - PRE_HEAP = -1, ///< = -1.
5.83 - POST_HEAP = -2 ///< = -2.
5.84 - };
5.85 -
5.86 - private:
5.87 - std::vector<Pair> _data;
5.88 - Compare _comp;
5.89 - ItemIntMap &_iim;
5.90 -
5.91 - public:
5.92 - /// \brief Constructor.
5.93 - ///
5.94 - /// Constructor.
5.95 - /// \param map A map that assigns \c int values to the items.
5.96 - /// It is used internally to handle the cross references.
5.97 - /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
5.98 - explicit FouraryHeap(ItemIntMap &map) : _iim(map) {}
5.99 -
5.100 - /// \brief Constructor.
5.101 - ///
5.102 - /// Constructor.
5.103 - /// \param map A map that assigns \c int values to the items.
5.104 - /// It is used internally to handle the cross references.
5.105 - /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
5.106 - /// \param comp The function object used for comparing the priorities.
5.107 - FouraryHeap(ItemIntMap &map, const Compare &comp)
5.108 - : _iim(map), _comp(comp) {}
5.109 -
5.110 - /// \brief The number of items stored in the heap.
5.111 - ///
5.112 - /// This function returns the number of items stored in the heap.
5.113 - int size() const { return _data.size(); }
5.114 -
5.115 - /// \brief Check if the heap is empty.
5.116 - ///
5.117 - /// This function returns \c true if the heap is empty.
5.118 - bool empty() const { return _data.empty(); }
5.119 -
5.120 - /// \brief Make the heap empty.
5.121 - ///
5.122 - /// This functon makes the heap empty.
5.123 - /// It does not change the cross reference map. If you want to reuse
5.124 - /// a heap that is not surely empty, you should first clear it and
5.125 - /// then you should set the cross reference map to \c PRE_HEAP
5.126 - /// for each item.
5.127 - void clear() { _data.clear(); }
5.128 -
5.129 - private:
5.130 - static int parent(int i) { return (i-1)/4; }
5.131 - static int firstChild(int i) { return 4*i+1; }
5.132 -
5.133 - bool less(const Pair &p1, const Pair &p2) const {
5.134 - return _comp(p1.second, p2.second);
5.135 - }
5.136 -
5.137 - void bubbleUp(int hole, Pair p) {
5.138 - int par = parent(hole);
5.139 - while( hole>0 && less(p,_data[par]) ) {
5.140 - move(_data[par],hole);
5.141 - hole = par;
5.142 - par = parent(hole);
5.143 - }
5.144 - move(p, hole);
5.145 - }
5.146 -
5.147 - void bubbleDown(int hole, Pair p, int length) {
5.148 - if( length>1 ) {
5.149 - int child = firstChild(hole);
5.150 - while( child+3<length ) {
5.151 - int min=child;
5.152 - if( less(_data[++child], _data[min]) ) min=child;
5.153 - if( less(_data[++child], _data[min]) ) min=child;
5.154 - if( less(_data[++child], _data[min]) ) min=child;
5.155 - if( !less(_data[min], p) )
5.156 - goto ok;
5.157 - move(_data[min], hole);
5.158 - hole = min;
5.159 - child = firstChild(hole);
5.160 - }
5.161 - if ( child<length ) {
5.162 - int min = child;
5.163 - if( ++child<length && less(_data[child], _data[min]) ) min=child;
5.164 - if( ++child<length && less(_data[child], _data[min]) ) min=child;
5.165 - if( less(_data[min], p) ) {
5.166 - move(_data[min], hole);
5.167 - hole = min;
5.168 - }
5.169 - }
5.170 - }
5.171 - ok:
5.172 - move(p, hole);
5.173 - }
5.174 -
5.175 - void move(const Pair &p, int i) {
5.176 - _data[i] = p;
5.177 - _iim.set(p.first, i);
5.178 - }
5.179 -
5.180 - public:
5.181 - /// \brief Insert a pair of item and priority into the heap.
5.182 - ///
5.183 - /// This function inserts \c p.first to the heap with priority
5.184 - /// \c p.second.
5.185 - /// \param p The pair to insert.
5.186 - /// \pre \c p.first must not be stored in the heap.
5.187 - void push(const Pair &p) {
5.188 - int n = _data.size();
5.189 - _data.resize(n+1);
5.190 - bubbleUp(n, p);
5.191 - }
5.192 -
5.193 - /// \brief Insert an item into the heap with the given priority.
5.194 - ///
5.195 - /// This function inserts the given item into the heap with the
5.196 - /// given priority.
5.197 - /// \param i The item to insert.
5.198 - /// \param p The priority of the item.
5.199 - /// \pre \e i must not be stored in the heap.
5.200 - void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
5.201 -
5.202 - /// \brief Return the item having minimum priority.
5.203 - ///
5.204 - /// This function returns the item having minimum priority.
5.205 - /// \pre The heap must be non-empty.
5.206 - Item top() const { return _data[0].first; }
5.207 -
5.208 - /// \brief The minimum priority.
5.209 - ///
5.210 - /// This function returns the minimum priority.
5.211 - /// \pre The heap must be non-empty.
5.212 - Prio prio() const { return _data[0].second; }
5.213 -
5.214 - /// \brief Remove the item having minimum priority.
5.215 - ///
5.216 - /// This function removes the item having minimum priority.
5.217 - /// \pre The heap must be non-empty.
5.218 - void pop() {
5.219 - int n = _data.size()-1;
5.220 - _iim.set(_data[0].first, POST_HEAP);
5.221 - if (n>0) bubbleDown(0, _data[n], n);
5.222 - _data.pop_back();
5.223 - }
5.224 -
5.225 - /// \brief Remove the given item from the heap.
5.226 - ///
5.227 - /// This function removes the given item from the heap if it is
5.228 - /// already stored.
5.229 - /// \param i The item to delete.
5.230 - /// \pre \e i must be in the heap.
5.231 - void erase(const Item &i) {
5.232 - int h = _iim[i];
5.233 - int n = _data.size()-1;
5.234 - _iim.set(_data[h].first, POST_HEAP);
5.235 - if( h<n ) {
5.236 - if( less(_data[parent(h)], _data[n]) )
5.237 - bubbleDown(h, _data[n], n);
5.238 - else
5.239 - bubbleUp(h, _data[n]);
5.240 - }
5.241 - _data.pop_back();
5.242 - }
5.243 -
5.244 - /// \brief The priority of the given item.
5.245 - ///
5.246 - /// This function returns the priority of the given item.
5.247 - /// \param i The item.
5.248 - /// \pre \e i must be in the heap.
5.249 - Prio operator[](const Item &i) const {
5.250 - int idx = _iim[i];
5.251 - return _data[idx].second;
5.252 - }
5.253 -
5.254 - /// \brief Set the priority of an item or insert it, if it is
5.255 - /// not stored in the heap.
5.256 - ///
5.257 - /// This method sets the priority of the given item if it is
5.258 - /// already stored in the heap. Otherwise it inserts the given
5.259 - /// item into the heap with the given priority.
5.260 - /// \param i The item.
5.261 - /// \param p The priority.
5.262 - void set(const Item &i, const Prio &p) {
5.263 - int idx = _iim[i];
5.264 - if( idx < 0 )
5.265 - push(i,p);
5.266 - else if( _comp(p, _data[idx].second) )
5.267 - bubbleUp(idx, Pair(i,p));
5.268 - else
5.269 - bubbleDown(idx, Pair(i,p), _data.size());
5.270 - }
5.271 -
5.272 - /// \brief Decrease the priority of an item to the given value.
5.273 - ///
5.274 - /// This function decreases the priority of an item to the given value.
5.275 - /// \param i The item.
5.276 - /// \param p The priority.
5.277 - /// \pre \e i must be stored in the heap with priority at least \e p.
5.278 - void decrease(const Item &i, const Prio &p) {
5.279 - int idx = _iim[i];
5.280 - bubbleUp(idx, Pair(i,p));
5.281 - }
5.282 -
5.283 - /// \brief Increase the priority of an item to the given value.
5.284 - ///
5.285 - /// This function increases the priority of an item to the given value.
5.286 - /// \param i The item.
5.287 - /// \param p The priority.
5.288 - /// \pre \e i must be stored in the heap with priority at most \e p.
5.289 - void increase(const Item &i, const Prio &p) {
5.290 - int idx = _iim[i];
5.291 - bubbleDown(idx, Pair(i,p), _data.size());
5.292 - }
5.293 -
5.294 - /// \brief Return the state of an item.
5.295 - ///
5.296 - /// This method returns \c PRE_HEAP if the given item has never
5.297 - /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
5.298 - /// and \c POST_HEAP otherwise.
5.299 - /// In the latter case it is possible that the item will get back
5.300 - /// to the heap again.
5.301 - /// \param i The item.
5.302 - State state(const Item &i) const {
5.303 - int s = _iim[i];
5.304 - if (s>=0) s=0;
5.305 - return State(s);
5.306 - }
5.307 -
5.308 - /// \brief Set the state of an item in the heap.
5.309 - ///
5.310 - /// This function sets the state of the given item in the heap.
5.311 - /// It can be used to manually clear the heap when it is important
5.312 - /// to achive better time complexity.
5.313 - /// \param i The item.
5.314 - /// \param st The state. It should not be \c IN_HEAP.
5.315 - void state(const Item& i, State st) {
5.316 - switch (st) {
5.317 - case POST_HEAP:
5.318 - case PRE_HEAP:
5.319 - if (state(i) == IN_HEAP) erase(i);
5.320 - _iim[i] = st;
5.321 - break;
5.322 - case IN_HEAP:
5.323 - break;
5.324 - }
5.325 - }
5.326 -
5.327 - /// \brief Replace an item in the heap.
5.328 - ///
5.329 - /// This function replaces item \c i with item \c j.
5.330 - /// Item \c i must be in the heap, while \c j must be out of the heap.
5.331 - /// After calling this method, item \c i will be out of the
5.332 - /// heap and \c j will be in the heap with the same prioriority
5.333 - /// as item \c i had before.
5.334 - void replace(const Item& i, const Item& j) {
5.335 - int idx = _iim[i];
5.336 - _iim.set(i, _iim[j]);
5.337 - _iim.set(j, idx);
5.338 - _data[idx].first = j;
5.339 - }
5.340 -
5.341 - }; // class FouraryHeap
5.342 -
5.343 -} // namespace lemon
5.344 -
5.345 -#endif // LEMON_FOURARY_HEAP_H
6.1 --- a/lemon/kary_heap.h Sat Sep 26 07:21:54 2009 +0200
6.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
6.3 @@ -1,352 +0,0 @@
6.4 -/* -*- mode: C++; indent-tabs-mode: nil; -*-
6.5 - *
6.6 - * This file is a part of LEMON, a generic C++ optimization library.
6.7 - *
6.8 - * Copyright (C) 2003-2009
6.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
6.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
6.11 - *
6.12 - * Permission to use, modify and distribute this software is granted
6.13 - * provided that this copyright notice appears in all copies. For
6.14 - * precise terms see the accompanying LICENSE file.
6.15 - *
6.16 - * This software is provided "AS IS" with no warranty of any kind,
6.17 - * express or implied, and with no claim as to its suitability for any
6.18 - * purpose.
6.19 - *
6.20 - */
6.21 -
6.22 -#ifndef LEMON_KARY_HEAP_H
6.23 -#define LEMON_KARY_HEAP_H
6.24 -
6.25 -///\ingroup heaps
6.26 -///\file
6.27 -///\brief Fourary heap implementation.
6.28 -
6.29 -#include <vector>
6.30 -#include <utility>
6.31 -#include <functional>
6.32 -
6.33 -namespace lemon {
6.34 -
6.35 - /// \ingroup heaps
6.36 - ///
6.37 - ///\brief K-ary heap data structure.
6.38 - ///
6.39 - /// This class implements the \e K-ary \e heap data structure.
6.40 - /// It fully conforms to the \ref concepts::Heap "heap concept".
6.41 - ///
6.42 - /// The \ref KaryHeap "K-ary heap" is a generalization of the
6.43 - /// \ref BinHeap "binary heap" structure, its nodes have at most
6.44 - /// \c K children, instead of two.
6.45 - /// \ref BinHeap and \ref FouraryHeap are specialized implementations
6.46 - /// of this structure for <tt>K=2</tt> and <tt>K=4</tt>, respectively.
6.47 - ///
6.48 - /// \tparam PR Type of the priorities of the items.
6.49 - /// \tparam IM A read-writable item map with \c int values, used
6.50 - /// internally to handle the cross references.
6.51 - /// \tparam K The degree of the heap, each node have at most \e K
6.52 - /// children. The default is 16. Powers of two are suggested to use
6.53 - /// so that the multiplications and divisions needed to traverse the
6.54 - /// nodes of the heap could be performed faster.
6.55 - /// \tparam CMP A functor class for comparing the priorities.
6.56 - /// The default is \c std::less<PR>.
6.57 - ///
6.58 - ///\sa BinHeap
6.59 - ///\sa FouraryHeap
6.60 -#ifdef DOXYGEN
6.61 - template <typename PR, typename IM, int K, typename CMP>
6.62 -#else
6.63 - template <typename PR, typename IM, int K = 16,
6.64 - typename CMP = std::less<PR> >
6.65 -#endif
6.66 - class KaryHeap {
6.67 - public:
6.68 - /// Type of the item-int map.
6.69 - typedef IM ItemIntMap;
6.70 - /// Type of the priorities.
6.71 - typedef PR Prio;
6.72 - /// Type of the items stored in the heap.
6.73 - typedef typename ItemIntMap::Key Item;
6.74 - /// Type of the item-priority pairs.
6.75 - typedef std::pair<Item,Prio> Pair;
6.76 - /// Functor type for comparing the priorities.
6.77 - typedef CMP Compare;
6.78 -
6.79 - /// \brief Type to represent the states of the items.
6.80 - ///
6.81 - /// Each item has a state associated to it. It can be "in heap",
6.82 - /// "pre-heap" or "post-heap". The latter two are indifferent from the
6.83 - /// heap's point of view, but may be useful to the user.
6.84 - ///
6.85 - /// The item-int map must be initialized in such way that it assigns
6.86 - /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
6.87 - enum State {
6.88 - IN_HEAP = 0, ///< = 0.
6.89 - PRE_HEAP = -1, ///< = -1.
6.90 - POST_HEAP = -2 ///< = -2.
6.91 - };
6.92 -
6.93 - private:
6.94 - std::vector<Pair> _data;
6.95 - Compare _comp;
6.96 - ItemIntMap &_iim;
6.97 -
6.98 - public:
6.99 - /// \brief Constructor.
6.100 - ///
6.101 - /// Constructor.
6.102 - /// \param map A map that assigns \c int values to the items.
6.103 - /// It is used internally to handle the cross references.
6.104 - /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
6.105 - explicit KaryHeap(ItemIntMap &map) : _iim(map) {}
6.106 -
6.107 - /// \brief Constructor.
6.108 - ///
6.109 - /// Constructor.
6.110 - /// \param map A map that assigns \c int values to the items.
6.111 - /// It is used internally to handle the cross references.
6.112 - /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
6.113 - /// \param comp The function object used for comparing the priorities.
6.114 - KaryHeap(ItemIntMap &map, const Compare &comp)
6.115 - : _iim(map), _comp(comp) {}
6.116 -
6.117 - /// \brief The number of items stored in the heap.
6.118 - ///
6.119 - /// This function returns the number of items stored in the heap.
6.120 - int size() const { return _data.size(); }
6.121 -
6.122 - /// \brief Check if the heap is empty.
6.123 - ///
6.124 - /// This function returns \c true if the heap is empty.
6.125 - bool empty() const { return _data.empty(); }
6.126 -
6.127 - /// \brief Make the heap empty.
6.128 - ///
6.129 - /// This functon makes the heap empty.
6.130 - /// It does not change the cross reference map. If you want to reuse
6.131 - /// a heap that is not surely empty, you should first clear it and
6.132 - /// then you should set the cross reference map to \c PRE_HEAP
6.133 - /// for each item.
6.134 - void clear() { _data.clear(); }
6.135 -
6.136 - private:
6.137 - int parent(int i) { return (i-1)/K; }
6.138 - int firstChild(int i) { return K*i+1; }
6.139 -
6.140 - bool less(const Pair &p1, const Pair &p2) const {
6.141 - return _comp(p1.second, p2.second);
6.142 - }
6.143 -
6.144 - void bubbleUp(int hole, Pair p) {
6.145 - int par = parent(hole);
6.146 - while( hole>0 && less(p,_data[par]) ) {
6.147 - move(_data[par],hole);
6.148 - hole = par;
6.149 - par = parent(hole);
6.150 - }
6.151 - move(p, hole);
6.152 - }
6.153 -
6.154 - void bubbleDown(int hole, Pair p, int length) {
6.155 - if( length>1 ) {
6.156 - int child = firstChild(hole);
6.157 - while( child+K<=length ) {
6.158 - int min=child;
6.159 - for (int i=1; i<K; ++i) {
6.160 - if( less(_data[child+i], _data[min]) )
6.161 - min=child+i;
6.162 - }
6.163 - if( !less(_data[min], p) )
6.164 - goto ok;
6.165 - move(_data[min], hole);
6.166 - hole = min;
6.167 - child = firstChild(hole);
6.168 - }
6.169 - if ( child<length ) {
6.170 - int min = child;
6.171 - while (++child < length) {
6.172 - if( less(_data[child], _data[min]) )
6.173 - min=child;
6.174 - }
6.175 - if( less(_data[min], p) ) {
6.176 - move(_data[min], hole);
6.177 - hole = min;
6.178 - }
6.179 - }
6.180 - }
6.181 - ok:
6.182 - move(p, hole);
6.183 - }
6.184 -
6.185 - void move(const Pair &p, int i) {
6.186 - _data[i] = p;
6.187 - _iim.set(p.first, i);
6.188 - }
6.189 -
6.190 - public:
6.191 - /// \brief Insert a pair of item and priority into the heap.
6.192 - ///
6.193 - /// This function inserts \c p.first to the heap with priority
6.194 - /// \c p.second.
6.195 - /// \param p The pair to insert.
6.196 - /// \pre \c p.first must not be stored in the heap.
6.197 - void push(const Pair &p) {
6.198 - int n = _data.size();
6.199 - _data.resize(n+1);
6.200 - bubbleUp(n, p);
6.201 - }
6.202 -
6.203 - /// \brief Insert an item into the heap with the given priority.
6.204 - ///
6.205 - /// This function inserts the given item into the heap with the
6.206 - /// given priority.
6.207 - /// \param i The item to insert.
6.208 - /// \param p The priority of the item.
6.209 - /// \pre \e i must not be stored in the heap.
6.210 - void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
6.211 -
6.212 - /// \brief Return the item having minimum priority.
6.213 - ///
6.214 - /// This function returns the item having minimum priority.
6.215 - /// \pre The heap must be non-empty.
6.216 - Item top() const { return _data[0].first; }
6.217 -
6.218 - /// \brief The minimum priority.
6.219 - ///
6.220 - /// This function returns the minimum priority.
6.221 - /// \pre The heap must be non-empty.
6.222 - Prio prio() const { return _data[0].second; }
6.223 -
6.224 - /// \brief Remove the item having minimum priority.
6.225 - ///
6.226 - /// This function removes the item having minimum priority.
6.227 - /// \pre The heap must be non-empty.
6.228 - void pop() {
6.229 - int n = _data.size()-1;
6.230 - _iim.set(_data[0].first, POST_HEAP);
6.231 - if (n>0) bubbleDown(0, _data[n], n);
6.232 - _data.pop_back();
6.233 - }
6.234 -
6.235 - /// \brief Remove the given item from the heap.
6.236 - ///
6.237 - /// This function removes the given item from the heap if it is
6.238 - /// already stored.
6.239 - /// \param i The item to delete.
6.240 - /// \pre \e i must be in the heap.
6.241 - void erase(const Item &i) {
6.242 - int h = _iim[i];
6.243 - int n = _data.size()-1;
6.244 - _iim.set(_data[h].first, POST_HEAP);
6.245 - if( h<n ) {
6.246 - if( less(_data[parent(h)], _data[n]) )
6.247 - bubbleDown(h, _data[n], n);
6.248 - else
6.249 - bubbleUp(h, _data[n]);
6.250 - }
6.251 - _data.pop_back();
6.252 - }
6.253 -
6.254 - /// \brief The priority of the given item.
6.255 - ///
6.256 - /// This function returns the priority of the given item.
6.257 - /// \param i The item.
6.258 - /// \pre \e i must be in the heap.
6.259 - Prio operator[](const Item &i) const {
6.260 - int idx = _iim[i];
6.261 - return _data[idx].second;
6.262 - }
6.263 -
6.264 - /// \brief Set the priority of an item or insert it, if it is
6.265 - /// not stored in the heap.
6.266 - ///
6.267 - /// This method sets the priority of the given item if it is
6.268 - /// already stored in the heap. Otherwise it inserts the given
6.269 - /// item into the heap with the given priority.
6.270 - /// \param i The item.
6.271 - /// \param p The priority.
6.272 - void set(const Item &i, const Prio &p) {
6.273 - int idx = _iim[i];
6.274 - if( idx<0 )
6.275 - push(i,p);
6.276 - else if( _comp(p, _data[idx].second) )
6.277 - bubbleUp(idx, Pair(i,p));
6.278 - else
6.279 - bubbleDown(idx, Pair(i,p), _data.size());
6.280 - }
6.281 -
6.282 - /// \brief Decrease the priority of an item to the given value.
6.283 - ///
6.284 - /// This function decreases the priority of an item to the given value.
6.285 - /// \param i The item.
6.286 - /// \param p The priority.
6.287 - /// \pre \e i must be stored in the heap with priority at least \e p.
6.288 - void decrease(const Item &i, const Prio &p) {
6.289 - int idx = _iim[i];
6.290 - bubbleUp(idx, Pair(i,p));
6.291 - }
6.292 -
6.293 - /// \brief Increase the priority of an item to the given value.
6.294 - ///
6.295 - /// This function increases the priority of an item to the given value.
6.296 - /// \param i The item.
6.297 - /// \param p The priority.
6.298 - /// \pre \e i must be stored in the heap with priority at most \e p.
6.299 - void increase(const Item &i, const Prio &p) {
6.300 - int idx = _iim[i];
6.301 - bubbleDown(idx, Pair(i,p), _data.size());
6.302 - }
6.303 -
6.304 - /// \brief Return the state of an item.
6.305 - ///
6.306 - /// This method returns \c PRE_HEAP if the given item has never
6.307 - /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
6.308 - /// and \c POST_HEAP otherwise.
6.309 - /// In the latter case it is possible that the item will get back
6.310 - /// to the heap again.
6.311 - /// \param i The item.
6.312 - State state(const Item &i) const {
6.313 - int s = _iim[i];
6.314 - if (s>=0) s=0;
6.315 - return State(s);
6.316 - }
6.317 -
6.318 - /// \brief Set the state of an item in the heap.
6.319 - ///
6.320 - /// This function sets the state of the given item in the heap.
6.321 - /// It can be used to manually clear the heap when it is important
6.322 - /// to achive better time complexity.
6.323 - /// \param i The item.
6.324 - /// \param st The state. It should not be \c IN_HEAP.
6.325 - void state(const Item& i, State st) {
6.326 - switch (st) {
6.327 - case POST_HEAP:
6.328 - case PRE_HEAP:
6.329 - if (state(i) == IN_HEAP) erase(i);
6.330 - _iim[i] = st;
6.331 - break;
6.332 - case IN_HEAP:
6.333 - break;
6.334 - }
6.335 - }
6.336 -
6.337 - /// \brief Replace an item in the heap.
6.338 - ///
6.339 - /// This function replaces item \c i with item \c j.
6.340 - /// Item \c i must be in the heap, while \c j must be out of the heap.
6.341 - /// After calling this method, item \c i will be out of the
6.342 - /// heap and \c j will be in the heap with the same prioriority
6.343 - /// as item \c i had before.
6.344 - void replace(const Item& i, const Item& j) {
6.345 - int idx=_iim[i];
6.346 - _iim.set(i, _iim[j]);
6.347 - _iim.set(j, idx);
6.348 - _data[idx].first=j;
6.349 - }
6.350 -
6.351 - }; // class KaryHeap
6.352 -
6.353 -} // namespace lemon
6.354 -
6.355 -#endif // LEMON_KARY_HEAP_H
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
7.2 +++ b/lemon/quad_heap.h Tue Sep 29 13:32:01 2009 +0200
7.3 @@ -0,0 +1,343 @@
7.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
7.5 + *
7.6 + * This file is a part of LEMON, a generic C++ optimization library.
7.7 + *
7.8 + * Copyright (C) 2003-2009
7.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
7.11 + *
7.12 + * Permission to use, modify and distribute this software is granted
7.13 + * provided that this copyright notice appears in all copies. For
7.14 + * precise terms see the accompanying LICENSE file.
7.15 + *
7.16 + * This software is provided "AS IS" with no warranty of any kind,
7.17 + * express or implied, and with no claim as to its suitability for any
7.18 + * purpose.
7.19 + *
7.20 + */
7.21 +
7.22 +#ifndef LEMON_QUAD_HEAP_H
7.23 +#define LEMON_QUAD_HEAP_H
7.24 +
7.25 +///\ingroup heaps
7.26 +///\file
7.27 +///\brief Fourary (quaternary) heap implementation.
7.28 +
7.29 +#include <vector>
7.30 +#include <utility>
7.31 +#include <functional>
7.32 +
7.33 +namespace lemon {
7.34 +
7.35 + /// \ingroup heaps
7.36 + ///
7.37 + ///\brief Fourary (quaternary) heap data structure.
7.38 + ///
7.39 + /// This class implements the \e Fourary (\e quaternary) \e heap
7.40 + /// data structure.
7.41 + /// It fully conforms to the \ref concepts::Heap "heap concept".
7.42 + ///
7.43 + /// The fourary heap is a specialization of the \ref DHeap "D-ary heap"
7.44 + /// for <tt>D=4</tt>. It is similar to the \ref BinHeap "binary heap",
7.45 + /// but its nodes have at most four children, instead of two.
7.46 + ///
7.47 + /// \tparam PR Type of the priorities of the items.
7.48 + /// \tparam IM A read-writable item map with \c int values, used
7.49 + /// internally to handle the cross references.
7.50 + /// \tparam CMP A functor class for comparing the priorities.
7.51 + /// The default is \c std::less<PR>.
7.52 + ///
7.53 + ///\sa BinHeap
7.54 + ///\sa DHeap
7.55 +#ifdef DOXYGEN
7.56 + template <typename PR, typename IM, typename CMP>
7.57 +#else
7.58 + template <typename PR, typename IM, typename CMP = std::less<PR> >
7.59 +#endif
7.60 + class QuadHeap {
7.61 + public:
7.62 + /// Type of the item-int map.
7.63 + typedef IM ItemIntMap;
7.64 + /// Type of the priorities.
7.65 + typedef PR Prio;
7.66 + /// Type of the items stored in the heap.
7.67 + typedef typename ItemIntMap::Key Item;
7.68 + /// Type of the item-priority pairs.
7.69 + typedef std::pair<Item,Prio> Pair;
7.70 + /// Functor type for comparing the priorities.
7.71 + typedef CMP Compare;
7.72 +
7.73 + /// \brief Type to represent the states of the items.
7.74 + ///
7.75 + /// Each item has a state associated to it. It can be "in heap",
7.76 + /// "pre-heap" or "post-heap". The latter two are indifferent from the
7.77 + /// heap's point of view, but may be useful to the user.
7.78 + ///
7.79 + /// The item-int map must be initialized in such way that it assigns
7.80 + /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
7.81 + enum State {
7.82 + IN_HEAP = 0, ///< = 0.
7.83 + PRE_HEAP = -1, ///< = -1.
7.84 + POST_HEAP = -2 ///< = -2.
7.85 + };
7.86 +
7.87 + private:
7.88 + std::vector<Pair> _data;
7.89 + Compare _comp;
7.90 + ItemIntMap &_iim;
7.91 +
7.92 + public:
7.93 + /// \brief Constructor.
7.94 + ///
7.95 + /// Constructor.
7.96 + /// \param map A map that assigns \c int values to the items.
7.97 + /// It is used internally to handle the cross references.
7.98 + /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
7.99 + explicit QuadHeap(ItemIntMap &map) : _iim(map) {}
7.100 +
7.101 + /// \brief Constructor.
7.102 + ///
7.103 + /// Constructor.
7.104 + /// \param map A map that assigns \c int values to the items.
7.105 + /// It is used internally to handle the cross references.
7.106 + /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
7.107 + /// \param comp The function object used for comparing the priorities.
7.108 + QuadHeap(ItemIntMap &map, const Compare &comp)
7.109 + : _iim(map), _comp(comp) {}
7.110 +
7.111 + /// \brief The number of items stored in the heap.
7.112 + ///
7.113 + /// This function returns the number of items stored in the heap.
7.114 + int size() const { return _data.size(); }
7.115 +
7.116 + /// \brief Check if the heap is empty.
7.117 + ///
7.118 + /// This function returns \c true if the heap is empty.
7.119 + bool empty() const { return _data.empty(); }
7.120 +
7.121 + /// \brief Make the heap empty.
7.122 + ///
7.123 + /// This functon makes the heap empty.
7.124 + /// It does not change the cross reference map. If you want to reuse
7.125 + /// a heap that is not surely empty, you should first clear it and
7.126 + /// then you should set the cross reference map to \c PRE_HEAP
7.127 + /// for each item.
7.128 + void clear() { _data.clear(); }
7.129 +
7.130 + private:
7.131 + static int parent(int i) { return (i-1)/4; }
7.132 + static int firstChild(int i) { return 4*i+1; }
7.133 +
7.134 + bool less(const Pair &p1, const Pair &p2) const {
7.135 + return _comp(p1.second, p2.second);
7.136 + }
7.137 +
7.138 + void bubbleUp(int hole, Pair p) {
7.139 + int par = parent(hole);
7.140 + while( hole>0 && less(p,_data[par]) ) {
7.141 + move(_data[par],hole);
7.142 + hole = par;
7.143 + par = parent(hole);
7.144 + }
7.145 + move(p, hole);
7.146 + }
7.147 +
7.148 + void bubbleDown(int hole, Pair p, int length) {
7.149 + if( length>1 ) {
7.150 + int child = firstChild(hole);
7.151 + while( child+3<length ) {
7.152 + int min=child;
7.153 + if( less(_data[++child], _data[min]) ) min=child;
7.154 + if( less(_data[++child], _data[min]) ) min=child;
7.155 + if( less(_data[++child], _data[min]) ) min=child;
7.156 + if( !less(_data[min], p) )
7.157 + goto ok;
7.158 + move(_data[min], hole);
7.159 + hole = min;
7.160 + child = firstChild(hole);
7.161 + }
7.162 + if ( child<length ) {
7.163 + int min = child;
7.164 + if( ++child<length && less(_data[child], _data[min]) ) min=child;
7.165 + if( ++child<length && less(_data[child], _data[min]) ) min=child;
7.166 + if( less(_data[min], p) ) {
7.167 + move(_data[min], hole);
7.168 + hole = min;
7.169 + }
7.170 + }
7.171 + }
7.172 + ok:
7.173 + move(p, hole);
7.174 + }
7.175 +
7.176 + void move(const Pair &p, int i) {
7.177 + _data[i] = p;
7.178 + _iim.set(p.first, i);
7.179 + }
7.180 +
7.181 + public:
7.182 + /// \brief Insert a pair of item and priority into the heap.
7.183 + ///
7.184 + /// This function inserts \c p.first to the heap with priority
7.185 + /// \c p.second.
7.186 + /// \param p The pair to insert.
7.187 + /// \pre \c p.first must not be stored in the heap.
7.188 + void push(const Pair &p) {
7.189 + int n = _data.size();
7.190 + _data.resize(n+1);
7.191 + bubbleUp(n, p);
7.192 + }
7.193 +
7.194 + /// \brief Insert an item into the heap with the given priority.
7.195 + ///
7.196 + /// This function inserts the given item into the heap with the
7.197 + /// given priority.
7.198 + /// \param i The item to insert.
7.199 + /// \param p The priority of the item.
7.200 + /// \pre \e i must not be stored in the heap.
7.201 + void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
7.202 +
7.203 + /// \brief Return the item having minimum priority.
7.204 + ///
7.205 + /// This function returns the item having minimum priority.
7.206 + /// \pre The heap must be non-empty.
7.207 + Item top() const { return _data[0].first; }
7.208 +
7.209 + /// \brief The minimum priority.
7.210 + ///
7.211 + /// This function returns the minimum priority.
7.212 + /// \pre The heap must be non-empty.
7.213 + Prio prio() const { return _data[0].second; }
7.214 +
7.215 + /// \brief Remove the item having minimum priority.
7.216 + ///
7.217 + /// This function removes the item having minimum priority.
7.218 + /// \pre The heap must be non-empty.
7.219 + void pop() {
7.220 + int n = _data.size()-1;
7.221 + _iim.set(_data[0].first, POST_HEAP);
7.222 + if (n>0) bubbleDown(0, _data[n], n);
7.223 + _data.pop_back();
7.224 + }
7.225 +
7.226 + /// \brief Remove the given item from the heap.
7.227 + ///
7.228 + /// This function removes the given item from the heap if it is
7.229 + /// already stored.
7.230 + /// \param i The item to delete.
7.231 + /// \pre \e i must be in the heap.
7.232 + void erase(const Item &i) {
7.233 + int h = _iim[i];
7.234 + int n = _data.size()-1;
7.235 + _iim.set(_data[h].first, POST_HEAP);
7.236 + if( h<n ) {
7.237 + if( less(_data[parent(h)], _data[n]) )
7.238 + bubbleDown(h, _data[n], n);
7.239 + else
7.240 + bubbleUp(h, _data[n]);
7.241 + }
7.242 + _data.pop_back();
7.243 + }
7.244 +
7.245 + /// \brief The priority of the given item.
7.246 + ///
7.247 + /// This function returns the priority of the given item.
7.248 + /// \param i The item.
7.249 + /// \pre \e i must be in the heap.
7.250 + Prio operator[](const Item &i) const {
7.251 + int idx = _iim[i];
7.252 + return _data[idx].second;
7.253 + }
7.254 +
7.255 + /// \brief Set the priority of an item or insert it, if it is
7.256 + /// not stored in the heap.
7.257 + ///
7.258 + /// This method sets the priority of the given item if it is
7.259 + /// already stored in the heap. Otherwise it inserts the given
7.260 + /// item into the heap with the given priority.
7.261 + /// \param i The item.
7.262 + /// \param p The priority.
7.263 + void set(const Item &i, const Prio &p) {
7.264 + int idx = _iim[i];
7.265 + if( idx < 0 )
7.266 + push(i,p);
7.267 + else if( _comp(p, _data[idx].second) )
7.268 + bubbleUp(idx, Pair(i,p));
7.269 + else
7.270 + bubbleDown(idx, Pair(i,p), _data.size());
7.271 + }
7.272 +
7.273 + /// \brief Decrease the priority of an item to the given value.
7.274 + ///
7.275 + /// This function decreases the priority of an item to the given value.
7.276 + /// \param i The item.
7.277 + /// \param p The priority.
7.278 + /// \pre \e i must be stored in the heap with priority at least \e p.
7.279 + void decrease(const Item &i, const Prio &p) {
7.280 + int idx = _iim[i];
7.281 + bubbleUp(idx, Pair(i,p));
7.282 + }
7.283 +
7.284 + /// \brief Increase the priority of an item to the given value.
7.285 + ///
7.286 + /// This function increases the priority of an item to the given value.
7.287 + /// \param i The item.
7.288 + /// \param p The priority.
7.289 + /// \pre \e i must be stored in the heap with priority at most \e p.
7.290 + void increase(const Item &i, const Prio &p) {
7.291 + int idx = _iim[i];
7.292 + bubbleDown(idx, Pair(i,p), _data.size());
7.293 + }
7.294 +
7.295 + /// \brief Return the state of an item.
7.296 + ///
7.297 + /// This method returns \c PRE_HEAP if the given item has never
7.298 + /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
7.299 + /// and \c POST_HEAP otherwise.
7.300 + /// In the latter case it is possible that the item will get back
7.301 + /// to the heap again.
7.302 + /// \param i The item.
7.303 + State state(const Item &i) const {
7.304 + int s = _iim[i];
7.305 + if (s>=0) s=0;
7.306 + return State(s);
7.307 + }
7.308 +
7.309 + /// \brief Set the state of an item in the heap.
7.310 + ///
7.311 + /// This function sets the state of the given item in the heap.
7.312 + /// It can be used to manually clear the heap when it is important
7.313 + /// to achive better time complexity.
7.314 + /// \param i The item.
7.315 + /// \param st The state. It should not be \c IN_HEAP.
7.316 + void state(const Item& i, State st) {
7.317 + switch (st) {
7.318 + case POST_HEAP:
7.319 + case PRE_HEAP:
7.320 + if (state(i) == IN_HEAP) erase(i);
7.321 + _iim[i] = st;
7.322 + break;
7.323 + case IN_HEAP:
7.324 + break;
7.325 + }
7.326 + }
7.327 +
7.328 + /// \brief Replace an item in the heap.
7.329 + ///
7.330 + /// This function replaces item \c i with item \c j.
7.331 + /// Item \c i must be in the heap, while \c j must be out of the heap.
7.332 + /// After calling this method, item \c i will be out of the
7.333 + /// heap and \c j will be in the heap with the same prioriority
7.334 + /// as item \c i had before.
7.335 + void replace(const Item& i, const Item& j) {
7.336 + int idx = _iim[i];
7.337 + _iim.set(i, _iim[j]);
7.338 + _iim.set(j, idx);
7.339 + _data[idx].first = j;
7.340 + }
7.341 +
7.342 + }; // class QuadHeap
7.343 +
7.344 +} // namespace lemon
7.345 +
7.346 +#endif // LEMON_FOURARY_HEAP_H
8.1 --- a/test/heap_test.cc Sat Sep 26 07:21:54 2009 +0200
8.2 +++ b/test/heap_test.cc Tue Sep 29 13:32:01 2009 +0200
8.3 @@ -30,12 +30,12 @@
8.4 #include <lemon/maps.h>
8.5
8.6 #include <lemon/bin_heap.h>
8.7 -#include <lemon/fourary_heap.h>
8.8 -#include <lemon/kary_heap.h>
8.9 +#include <lemon/quad_heap.h>
8.10 +#include <lemon/dheap.h>
8.11 #include <lemon/fib_heap.h>
8.12 #include <lemon/pairing_heap.h>
8.13 #include <lemon/radix_heap.h>
8.14 -#include <lemon/binom_heap.h>
8.15 +#include <lemon/binomial_heap.h>
8.16 #include <lemon/bucket_heap.h>
8.17
8.18 #include "test_tools.h"
8.19 @@ -185,26 +185,26 @@
8.20 dijkstraHeapTest<NodeHeap>(digraph, length, source);
8.21 }
8.22
8.23 - // FouraryHeap
8.24 + // QuadHeap
8.25 {
8.26 - typedef FouraryHeap<Prio, ItemIntMap> IntHeap;
8.27 + typedef QuadHeap<Prio, ItemIntMap> IntHeap;
8.28 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
8.29 heapSortTest<IntHeap>();
8.30 heapIncreaseTest<IntHeap>();
8.31
8.32 - typedef FouraryHeap<Prio, IntNodeMap > NodeHeap;
8.33 + typedef QuadHeap<Prio, IntNodeMap > NodeHeap;
8.34 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
8.35 dijkstraHeapTest<NodeHeap>(digraph, length, source);
8.36 }
8.37
8.38 - // KaryHeap
8.39 + // DHeap
8.40 {
8.41 - typedef KaryHeap<Prio, ItemIntMap> IntHeap;
8.42 + typedef DHeap<Prio, ItemIntMap> IntHeap;
8.43 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
8.44 heapSortTest<IntHeap>();
8.45 heapIncreaseTest<IntHeap>();
8.46
8.47 - typedef KaryHeap<Prio, IntNodeMap > NodeHeap;
8.48 + typedef DHeap<Prio, IntNodeMap > NodeHeap;
8.49 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
8.50 dijkstraHeapTest<NodeHeap>(digraph, length, source);
8.51 }
8.52 @@ -245,14 +245,14 @@
8.53 dijkstraHeapTest<NodeHeap>(digraph, length, source);
8.54 }
8.55
8.56 - // BinomHeap
8.57 + // BinomialHeap
8.58 {
8.59 - typedef BinomHeap<Prio, ItemIntMap> IntHeap;
8.60 + typedef BinomialHeap<Prio, ItemIntMap> IntHeap;
8.61 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
8.62 heapSortTest<IntHeap>();
8.63 heapIncreaseTest<IntHeap>();
8.64
8.65 - typedef BinomHeap<Prio, IntNodeMap > NodeHeap;
8.66 + typedef BinomialHeap<Prio, IntNodeMap > NodeHeap;
8.67 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
8.68 dijkstraHeapTest<NodeHeap>(digraph, length, source);
8.69 }