1.1 --- a/lemon/Makefile.am Thu Jun 11 23:13:24 2009 +0200
1.2 +++ b/lemon/Makefile.am Thu Jul 09 02:38:01 2009 +0200
1.3 @@ -59,6 +59,7 @@
1.4 lemon/assert.h \
1.5 lemon/bfs.h \
1.6 lemon/bin_heap.h \
1.7 + lemon/binom_heap.h \
1.8 lemon/bucket_heap.h \
1.9 lemon/cbc.h \
1.10 lemon/circulation.h \
1.11 @@ -78,12 +79,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 Thu Jul 09 02:38:01 2009 +0200
2.3 @@ -0,0 +1,506 @@
2.4 +/* -*- C++ -*-
2.5 + *
2.6 + * This file is a part of LEMON, a generic C++ optimization library
2.7 + *
2.8 + * Copyright (C) 2003-2008
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 auxdat
2.27 +///\brief Binomial Heap implementation.
2.28 +
2.29 +#include <vector>
2.30 +#include <functional>
2.31 +#include <lemon/math.h>
2.32 +#include <lemon/counter.h>
2.33 +
2.34 +namespace lemon {
2.35 +
2.36 + /// \ingroup auxdat
2.37 + ///
2.38 + ///\brief Binomial Heap.
2.39 + ///
2.40 + ///This class implements the \e Binomial \e heap data structure. A \e heap
2.41 + ///is a data structure for storing items with specified values called \e
2.42 + ///priorities in such a way that finding the item with minimum priority is
2.43 + ///efficient. \c Compare specifies the ordering of the priorities. In a heap
2.44 + ///one can change the priority of an item, add or erase an item, etc.
2.45 + ///
2.46 + ///The methods \ref increase and \ref erase are not efficient in a Binomial
2.47 + ///heap. In case of many calls to these operations, it is better to use a
2.48 + ///\ref BinHeap "binary heap".
2.49 + ///
2.50 + ///\param _Prio Type of the priority of the items.
2.51 + ///\param _ItemIntMap A read and writable Item int map, used internally
2.52 + ///to handle the cross references.
2.53 + ///\param _Compare A class for the ordering of the priorities. The
2.54 + ///default is \c std::less<_Prio>.
2.55 + ///
2.56 + ///\sa BinHeap
2.57 + ///\sa Dijkstra
2.58 + ///\author Dorian Batha
2.59 +
2.60 +#ifdef DOXYGEN
2.61 + template <typename _Prio,
2.62 + typename _ItemIntMap,
2.63 + typename _Compare>
2.64 +#else
2.65 + template <typename _Prio,
2.66 + typename _ItemIntMap,
2.67 + typename _Compare = std::less<_Prio> >
2.68 +#endif
2.69 + class BinomHeap {
2.70 + public:
2.71 + typedef _ItemIntMap ItemIntMap;
2.72 + typedef _Prio Prio;
2.73 + typedef typename ItemIntMap::Key Item;
2.74 + typedef std::pair<Item,Prio> Pair;
2.75 + typedef _Compare Compare;
2.76 +
2.77 + private:
2.78 + class store;
2.79 +
2.80 + std::vector<store> container;
2.81 + int minimum, head;
2.82 + ItemIntMap &iimap;
2.83 + Compare comp;
2.84 + int num_items;
2.85 +
2.86 + public:
2.87 + ///Status of the nodes
2.88 + enum State {
2.89 + ///The node is in the heap
2.90 + IN_HEAP = 0,
2.91 + ///The node has never been in the heap
2.92 + PRE_HEAP = -1,
2.93 + ///The node was in the heap but it got out of it
2.94 + POST_HEAP = -2
2.95 + };
2.96 +
2.97 + /// \brief The constructor
2.98 + ///
2.99 + /// \c _iimap should be given to the constructor, since it is
2.100 + /// used internally to handle the cross references.
2.101 + explicit BinomHeap(ItemIntMap &_iimap)
2.102 + : minimum(0), head(-1), iimap(_iimap), num_items() {}
2.103 +
2.104 + /// \brief The constructor
2.105 + ///
2.106 + /// \c _iimap should be given to the constructor, since it is used
2.107 + /// internally to handle the cross references. \c _comp is an
2.108 + /// object for ordering of the priorities.
2.109 + BinomHeap(ItemIntMap &_iimap, const Compare &_comp)
2.110 + : minimum(0), head(-1), iimap(_iimap), comp(_comp), num_items() {}
2.111 +
2.112 + /// \brief The number of items stored in the heap.
2.113 + ///
2.114 + /// Returns the number of items stored in the heap.
2.115 + int size() const { return num_items; }
2.116 +
2.117 + /// \brief Checks if the heap stores no items.
2.118 + ///
2.119 + /// Returns \c true if and only if the heap stores no items.
2.120 + bool empty() const { return num_items==0; }
2.121 +
2.122 + /// \brief Make empty this heap.
2.123 + ///
2.124 + /// Make empty this heap. It does not change the cross reference
2.125 + /// map. If you want to reuse a heap what is not surely empty you
2.126 + /// should first clear the heap and after that you should set the
2.127 + /// cross reference map for each item to \c PRE_HEAP.
2.128 + void clear() {
2.129 + container.clear(); minimum=0; num_items=0; head=-1;
2.130 + }
2.131 +
2.132 + /// \brief \c item gets to the heap with priority \c value independently
2.133 + /// if \c item was already there.
2.134 + ///
2.135 + /// This method calls \ref push(\c item, \c value) if \c item is not
2.136 + /// stored in the heap and it calls \ref decrease(\c item, \c value) or
2.137 + /// \ref increase(\c item, \c value) otherwise.
2.138 + void set (const Item& item, const Prio& value) {
2.139 + int i=iimap[item];
2.140 + if ( i >= 0 && container[i].in ) {
2.141 + if ( comp(value, container[i].prio) ) decrease(item, value);
2.142 + if ( comp(container[i].prio, value) ) increase(item, value);
2.143 + } else push(item, value);
2.144 + }
2.145 +
2.146 + /// \brief Adds \c item to the heap with priority \c value.
2.147 + ///
2.148 + /// Adds \c item to the heap with priority \c value.
2.149 + /// \pre \c item must not be stored in the heap.
2.150 + void push (const Item& item, const Prio& value) {
2.151 + int i=iimap[item];
2.152 + if ( i<0 ) {
2.153 + int s=container.size();
2.154 + iimap.set( item,s );
2.155 + store st;
2.156 + st.name=item;
2.157 + container.push_back(st);
2.158 + i=s;
2.159 + }
2.160 + else {
2.161 + container[i].parent=container[i].right_neighbor=container[i].child=-1;
2.162 + container[i].degree=0;
2.163 + container[i].in=true;
2.164 + }
2.165 + container[i].prio=value;
2.166 +
2.167 + if( 0==num_items ) { head=i; minimum=i; }
2.168 + else { merge(i); }
2.169 +
2.170 + minimum = find_min();
2.171 +
2.172 + ++num_items;
2.173 + }
2.174 +
2.175 + /// \brief Returns the item with minimum priority relative to \c Compare.
2.176 + ///
2.177 + /// This method returns the item with minimum priority relative to \c
2.178 + /// Compare.
2.179 + /// \pre The heap must be nonempty.
2.180 + Item top() const { return container[minimum].name; }
2.181 +
2.182 + /// \brief Returns the minimum priority relative to \c Compare.
2.183 + ///
2.184 + /// It returns the minimum priority relative to \c Compare.
2.185 + /// \pre The heap must be nonempty.
2.186 + const Prio& prio() const { return container[minimum].prio; }
2.187 +
2.188 + /// \brief Returns the priority of \c item.
2.189 + ///
2.190 + /// It returns the priority of \c item.
2.191 + /// \pre \c item must be in the heap.
2.192 + const Prio& operator[](const Item& item) const {
2.193 + return container[iimap[item]].prio;
2.194 + }
2.195 +
2.196 + /// \brief Deletes the item with minimum priority relative to \c Compare.
2.197 + ///
2.198 + /// This method deletes the item with minimum priority relative to \c
2.199 + /// Compare from the heap.
2.200 + /// \pre The heap must be non-empty.
2.201 + void pop() {
2.202 + container[minimum].in=false;
2.203 +
2.204 + int head_child=-1;
2.205 + if ( container[minimum].child!=-1 ) {
2.206 + int child=container[minimum].child;
2.207 + int neighb;
2.208 + int prev=-1;
2.209 + while( child!=-1 ) {
2.210 + neighb=container[child].right_neighbor;
2.211 + container[child].parent=-1;
2.212 + container[child].right_neighbor=prev;
2.213 + head_child=child;
2.214 + prev=child;
2.215 + child=neighb;
2.216 + }
2.217 + }
2.218 +
2.219 + // The first case is that there are only one root.
2.220 + if ( -1==container[head].right_neighbor ) {
2.221 + head=head_child;
2.222 + }
2.223 + // The case where there are more roots.
2.224 + else {
2.225 + if( head!=minimum ) { unlace(minimum); }
2.226 + else { head=container[head].right_neighbor; }
2.227 +
2.228 + merge(head_child);
2.229 + }
2.230 + minimum=find_min();
2.231 + --num_items;
2.232 + }
2.233 +
2.234 + /// \brief Deletes \c item from the heap.
2.235 + ///
2.236 + /// This method deletes \c item from the heap, if \c item was already
2.237 + /// stored in the heap. It is quite inefficient in Binomial heaps.
2.238 + void erase (const Item& item) {
2.239 + int i=iimap[item];
2.240 + if ( i >= 0 && container[i].in ) {
2.241 + decrease( item, container[minimum].prio-1 );
2.242 + pop();
2.243 + }
2.244 + }
2.245 +
2.246 + /// \brief Decreases the priority of \c item to \c value.
2.247 + ///
2.248 + /// This method decreases the priority of \c item to \c value.
2.249 + /// \pre \c item must be stored in the heap with priority at least \c
2.250 + /// value relative to \c Compare.
2.251 + void decrease (Item item, const Prio& value) {
2.252 + int i=iimap[item];
2.253 +
2.254 + if( comp( value,container[i].prio ) ) {
2.255 + container[i].prio=value;
2.256 +
2.257 + int p_loc=container[i].parent, loc=i;
2.258 + int parent, child, neighb;
2.259 +
2.260 + while( -1!=p_loc && comp(container[loc].prio,container[p_loc].prio) ) {
2.261 +
2.262 + // parent set for other loc_child
2.263 + child=container[loc].child;
2.264 + while( -1!=child ) {
2.265 + container[child].parent=p_loc;
2.266 + child=container[child].right_neighbor;
2.267 + }
2.268 +
2.269 + // parent set for other p_loc_child
2.270 + child=container[p_loc].child;
2.271 + while( -1!=child ) {
2.272 + container[child].parent=loc;
2.273 + child=container[child].right_neighbor;
2.274 + }
2.275 +
2.276 + child=container[p_loc].child;
2.277 + container[p_loc].child=container[loc].child;
2.278 + if( child==loc )
2.279 + child=p_loc;
2.280 + container[loc].child=child;
2.281 +
2.282 + // left_neighb set for p_loc
2.283 + if( container[loc].child!=p_loc ) {
2.284 + while( container[child].right_neighbor!=loc )
2.285 + child=container[child].right_neighbor;
2.286 + container[child].right_neighbor=p_loc;
2.287 + }
2.288 +
2.289 + // left_neighb set for loc
2.290 + parent=container[p_loc].parent;
2.291 + if( -1!=parent ) child=container[parent].child;
2.292 + else child=head;
2.293 +
2.294 + if( child!=p_loc ) {
2.295 + while( container[child].right_neighbor!=p_loc )
2.296 + child=container[child].right_neighbor;
2.297 + container[child].right_neighbor=loc;
2.298 + }
2.299 +
2.300 + neighb=container[p_loc].right_neighbor;
2.301 + container[p_loc].right_neighbor=container[loc].right_neighbor;
2.302 + container[loc].right_neighbor=neighb;
2.303 +
2.304 + container[p_loc].parent=loc;
2.305 + container[loc].parent=parent;
2.306 +
2.307 + if( -1!=parent && container[parent].child==p_loc )
2.308 + container[parent].child=loc;
2.309 +
2.310 + /*if new parent will be the first root*/
2.311 + if( head==p_loc )
2.312 + head=loc;
2.313 +
2.314 + p_loc=container[loc].parent;
2.315 + }
2.316 + }
2.317 + if( comp(value,container[minimum].prio) ) {
2.318 + minimum=i;
2.319 + }
2.320 + }
2.321 +
2.322 + /// \brief Increases the priority of \c item to \c value.
2.323 + ///
2.324 + /// This method sets the priority of \c item to \c value. Though
2.325 + /// there is no precondition on the priority of \c item, this
2.326 + /// method should be used only if it is indeed necessary to increase
2.327 + /// (relative to \c Compare) the priority of \c item, because this
2.328 + /// method is inefficient.
2.329 + void increase (Item item, const Prio& value) {
2.330 + erase(item);
2.331 + push(item, value);
2.332 + }
2.333 +
2.334 +
2.335 + /// \brief Returns if \c item is in, has already been in, or has never
2.336 + /// been in the heap.
2.337 + ///
2.338 + /// This method returns PRE_HEAP if \c item has never been in the
2.339 + /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
2.340 + /// otherwise. In the latter case it is possible that \c item will
2.341 + /// get back to the heap again.
2.342 + State state(const Item &item) const {
2.343 + int i=iimap[item];
2.344 + if( i>=0 ) {
2.345 + if ( container[i].in ) i=0;
2.346 + else i=-2;
2.347 + }
2.348 + return State(i);
2.349 + }
2.350 +
2.351 + /// \brief Sets the state of the \c item in the heap.
2.352 + ///
2.353 + /// Sets the state of the \c item in the heap. It can be used to
2.354 + /// manually clear the heap when it is important to achive the
2.355 + /// better time complexity.
2.356 + /// \param i The item.
2.357 + /// \param st The state. It should not be \c IN_HEAP.
2.358 + void state(const Item& i, State st) {
2.359 + switch (st) {
2.360 + case POST_HEAP:
2.361 + case PRE_HEAP:
2.362 + if (state(i) == IN_HEAP) {
2.363 + erase(i);
2.364 + }
2.365 + iimap[i] = st;
2.366 + break;
2.367 + case IN_HEAP:
2.368 + break;
2.369 + }
2.370 + }
2.371 +
2.372 + private:
2.373 + int find_min() {
2.374 + int min_loc=-1, min_val;
2.375 + int x=head;
2.376 + if( x!=-1 ) {
2.377 + min_val=container[x].prio;
2.378 + min_loc=x;
2.379 + x=container[x].right_neighbor;
2.380 +
2.381 + while( x!=-1 ) {
2.382 + if( comp( container[x].prio,min_val ) ) {
2.383 + min_val=container[x].prio;
2.384 + min_loc=x;
2.385 + }
2.386 + x=container[x].right_neighbor;
2.387 + }
2.388 + }
2.389 + return min_loc;
2.390 + }
2.391 +
2.392 + void merge(int a) {
2.393 + interleave(a);
2.394 +
2.395 + int x=head;
2.396 + if( -1!=x ) {
2.397 + int x_prev=-1, x_next=container[x].right_neighbor;
2.398 + while( -1!=x_next ) {
2.399 + if( container[x].degree!=container[x_next].degree || ( -1!=container[x_next].right_neighbor && container[container[x_next].right_neighbor].degree==container[x].degree ) ) {
2.400 + x_prev=x;
2.401 + x=x_next;
2.402 + }
2.403 + else {
2.404 + if( comp(container[x].prio,container[x_next].prio) ) {
2.405 + container[x].right_neighbor=container[x_next].right_neighbor;
2.406 + fuse(x_next,x);
2.407 + }
2.408 + else {
2.409 + if( -1==x_prev ) { head=x_next; }
2.410 + else {
2.411 + container[x_prev].right_neighbor=x_next;
2.412 + }
2.413 + fuse(x,x_next);
2.414 + x=x_next;
2.415 + }
2.416 + }
2.417 + x_next=container[x].right_neighbor;
2.418 + }
2.419 + }
2.420 + }
2.421 +
2.422 + void interleave(int a) {
2.423 + int other=-1, head_other=-1;
2.424 +
2.425 + while( -1!=a || -1!=head ) {
2.426 + if( -1==a ) {
2.427 + if( -1==head_other ) {
2.428 + head_other=head;
2.429 + }
2.430 + else {
2.431 + container[other].right_neighbor=head;
2.432 + }
2.433 + head=-1;
2.434 + }
2.435 + else if( -1==head ) {
2.436 + if( -1==head_other ) {
2.437 + head_other=a;
2.438 + }
2.439 + else {
2.440 + container[other].right_neighbor=a;
2.441 + }
2.442 + a=-1;
2.443 + }
2.444 + else {
2.445 + if( container[a].degree<container[head].degree ) {
2.446 + if( -1==head_other ) {
2.447 + head_other=a;
2.448 + }
2.449 + else {
2.450 + container[other].right_neighbor=a;
2.451 + }
2.452 + other=a;
2.453 + a=container[a].right_neighbor;
2.454 + }
2.455 + else {
2.456 + if( -1==head_other ) {
2.457 + head_other=head;
2.458 + }
2.459 + else {
2.460 + container[other].right_neighbor=head;
2.461 + }
2.462 + other=head;
2.463 + head=container[head].right_neighbor;
2.464 + }
2.465 + }
2.466 + }
2.467 + head=head_other;
2.468 + }
2.469 +
2.470 + // Lacing a under b
2.471 + void fuse(int a, int b) {
2.472 + container[a].parent=b;
2.473 + container[a].right_neighbor=container[b].child;
2.474 + container[b].child=a;
2.475 +
2.476 + ++container[b].degree;
2.477 + }
2.478 +
2.479 + // It is invoked only if a has siblings.
2.480 + void unlace(int a) {
2.481 + int neighb=container[a].right_neighbor;
2.482 + int other=head;
2.483 +
2.484 + while( container[other].right_neighbor!=a )
2.485 + other=container[other].right_neighbor;
2.486 + container[other].right_neighbor=neighb;
2.487 + }
2.488 +
2.489 + private:
2.490 +
2.491 + class store {
2.492 + friend class BinomHeap;
2.493 +
2.494 + Item name;
2.495 + int parent;
2.496 + int right_neighbor;
2.497 + int child;
2.498 + int degree;
2.499 + bool in;
2.500 + Prio prio;
2.501 +
2.502 + store() : parent(-1), right_neighbor(-1), child(-1), degree(0), in(true) {}
2.503 + };
2.504 + };
2.505 +
2.506 +} //namespace lemon
2.507 +
2.508 +#endif //LEMON_BINOM_HEAP_H
2.509 +
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/lemon/fourary_heap.h Thu Jul 09 02:38:01 2009 +0200
3.3 @@ -0,0 +1,350 @@
3.4 +/* -*- C++ -*-
3.5 + *
3.6 + * This file is a part of LEMON, a generic C++ optimization library
3.7 + *
3.8 + * Copyright (C) 2003-2008
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 auxdat
3.26 +///\file
3.27 +///\brief 4ary Heap implementation.
3.28 +
3.29 +#include <iostream>
3.30 +#include <vector>
3.31 +#include <utility>
3.32 +#include <functional>
3.33 +
3.34 +namespace lemon {
3.35 +
3.36 + ///\ingroup auxdat
3.37 + ///
3.38 + ///\brief A 4ary Heap implementation.
3.39 + ///
3.40 + ///This class implements the \e 4ary \e heap data structure. A \e heap
3.41 + ///is a data structure for storing items with specified values called \e
3.42 + ///priorities in such a way that finding the item with minimum priority is
3.43 + ///efficient. \c Compare specifies the ordering of the priorities. In a heap
3.44 + ///one can change the priority of an item, add or erase an item, etc.
3.45 + ///
3.46 + ///\param _Prio Type of the priority of the items.
3.47 + ///\param _ItemIntMap A read and writable Item int map, used internally
3.48 + ///to handle the cross references.
3.49 + ///\param _Compare A class for the ordering of the priorities. The
3.50 + ///default is \c std::less<_Prio>.
3.51 + ///
3.52 + ///\sa FibHeap
3.53 + ///\sa Dijkstra
3.54 + ///\author Dorian Batha
3.55 +
3.56 + template <typename _Prio, typename _ItemIntMap,
3.57 + typename _Compare = std::less<_Prio> >
3.58 +
3.59 + class FouraryHeap {
3.60 +
3.61 + public:
3.62 + ///\e
3.63 + typedef _ItemIntMap ItemIntMap;
3.64 + ///\e
3.65 + typedef _Prio Prio;
3.66 + ///\e
3.67 + typedef typename ItemIntMap::Key Item;
3.68 + ///\e
3.69 + typedef std::pair<Item,Prio> Pair;
3.70 + ///\e
3.71 + typedef _Compare Compare;
3.72 +
3.73 + /// \brief Type to represent the items states.
3.74 + ///
3.75 + /// Each Item element have a state associated to it. It may be "in heap",
3.76 + /// "pre heap" or "post heap". The latter two are indifferent from the
3.77 + /// heap's point of view, but may be useful to the user.
3.78 + ///
3.79 + /// The ItemIntMap \e should be initialized in such way that it maps
3.80 + /// PRE_HEAP (-1) to any element to be put in the heap...
3.81 + enum State {
3.82 + IN_HEAP = 0,
3.83 + PRE_HEAP = -1,
3.84 + POST_HEAP = -2
3.85 + };
3.86 +
3.87 + private:
3.88 + std::vector<Pair> data;
3.89 + Compare comp;
3.90 + ItemIntMap &iim;
3.91 +
3.92 + public:
3.93 + /// \brief The constructor.
3.94 + ///
3.95 + /// The constructor.
3.96 + /// \param _iim should be given to the constructor, since it is used
3.97 + /// internally to handle the cross references. The value of the map
3.98 + /// should be PRE_HEAP (-1) for each element.
3.99 + explicit FouraryHeap(ItemIntMap &_iim) : iim(_iim) {}
3.100 +
3.101 + /// \brief The constructor.
3.102 + ///
3.103 + /// The constructor.
3.104 + /// \param _iim should be given to the constructor, since it is used
3.105 + /// internally to handle the cross references. The value of the map
3.106 + /// should be PRE_HEAP (-1) for each element.
3.107 + ///
3.108 + /// \param _comp The comparator function object.
3.109 + FouraryHeap(ItemIntMap &_iim, const Compare &_comp)
3.110 + : iim(_iim), comp(_comp) {}
3.111 +
3.112 + /// The number of items stored in the heap.
3.113 + ///
3.114 + /// \brief Returns the number of items stored in the heap.
3.115 + int size() const { return data.size(); }
3.116 +
3.117 + /// \brief Checks if the heap stores no items.
3.118 + ///
3.119 + /// Returns \c true if and only if the heap stores no items.
3.120 + bool empty() const { return data.empty(); }
3.121 +
3.122 + /// \brief Make empty this heap.
3.123 + ///
3.124 + /// Make empty this heap. It does not change the cross reference map.
3.125 + /// If you want to reuse what is not surely empty you should first clear
3.126 + /// the heap and after that you should set the cross reference map for
3.127 + /// each item to \c PRE_HEAP.
3.128 + void clear() { data.clear(); }
3.129 +
3.130 + private:
3.131 + static int parent(int i) { return (i-1)/4; }
3.132 + static int firstChild(int i) { return 4*i+1; }
3.133 +
3.134 + bool less(const Pair &p1, const Pair &p2) const {
3.135 + return comp(p1.second, p2.second);
3.136 + }
3.137 +
3.138 + int find_min(const int child, const int length) {
3.139 + int min=child;
3.140 + if( child+3<length ) {
3.141 + if( less(data[child+3], data[min]) )
3.142 + min=child+3;
3.143 + if( less(data[child+2], data[min]) )
3.144 + min=child+2;
3.145 + if( less(data[child+1], data[min]) )
3.146 + min=child+1;
3.147 + }
3.148 + else if( child+2<length ) {
3.149 + if( less(data[child+2], data[min]) )
3.150 + min=child+2;
3.151 + if( less(data[child+1], data[min]) )
3.152 + min=child+1;
3.153 + }
3.154 + else if( child+1<length ) {
3.155 + if( less(data[child+1], data[min]) )
3.156 + min=child+1;
3.157 + }
3.158 + return min;
3.159 + }
3.160 +
3.161 + void bubble_up(int hole, Pair p) {
3.162 + int par = parent(hole);
3.163 + while( hole>0 && less(p,data[par]) ) {
3.164 + move(data[par],hole);
3.165 + hole = par;
3.166 + par = parent(hole);
3.167 + }
3.168 + move(p, hole);
3.169 + }
3.170 +
3.171 + void bubble_down(int hole, Pair p, int length) {
3.172 + int child = firstChild(hole);
3.173 + while( child<length && length>1 ) {
3.174 + child = find_min(child,length);
3.175 + if( !less(data[child], p) )
3.176 + goto ok;
3.177 + move(data[child], hole);
3.178 + hole = child;
3.179 + child = firstChild(hole);
3.180 + }
3.181 + ok:
3.182 + move(p, hole);
3.183 + }
3.184 +
3.185 + void move(const Pair &p, int i) {
3.186 + data[i] = p;
3.187 + iim.set(p.first, i);
3.188 + }
3.189 +
3.190 + public:
3.191 +
3.192 + /// \brief Insert a pair of item and priority into the heap.
3.193 + ///
3.194 + /// Adds \c p.first to the heap with priority \c p.second.
3.195 + /// \param p The pair to insert.
3.196 + void push(const Pair &p) {
3.197 + int n = data.size();
3.198 + data.resize(n+1);
3.199 + bubble_up(n, p);
3.200 + }
3.201 +
3.202 + /// \brief Insert an item into the heap with the given heap.
3.203 + ///
3.204 + /// Adds \c i to the heap with priority \c p.
3.205 + /// \param i The item to insert.
3.206 + /// \param p The priority of the item.
3.207 + void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
3.208 +
3.209 + /// \brief Returns the item with minimum priority relative to \c Compare.
3.210 + ///
3.211 + /// This method returns the item with minimum priority relative to \c
3.212 + /// Compare.
3.213 + /// \pre The heap must be nonempty.
3.214 + Item top() const { return data[0].first; }
3.215 +
3.216 + /// \brief Returns the minimum priority relative to \c Compare.
3.217 + ///
3.218 + /// It returns the minimum priority relative to \c Compare.
3.219 + /// \pre The heap must be nonempty.
3.220 + Prio prio() const { return data[0].second; }
3.221 +
3.222 + /// \brief Deletes the item with minimum priority relative to \c Compare.
3.223 + ///
3.224 + /// This method deletes the item with minimum priority relative to \c
3.225 + /// Compare from the heap.
3.226 + /// \pre The heap must be non-empty.
3.227 + void pop() {
3.228 + int n = data.size()-1;
3.229 + iim.set(data[0].first, POST_HEAP);
3.230 + if (n>0) bubble_down(0, data[n], n);
3.231 + data.pop_back();
3.232 + }
3.233 +
3.234 + /// \brief Deletes \c i from the heap.
3.235 + ///
3.236 + /// This method deletes item \c i from the heap.
3.237 + /// \param i The item to erase.
3.238 + /// \pre The item should be in the heap.
3.239 + void erase(const Item &i) {
3.240 + int h = iim[i];
3.241 + int n = data.size()-1;
3.242 + iim.set(data[h].first, POST_HEAP);
3.243 + if( h<n ) {
3.244 + if( less(data[parent(h)], data[n]) )
3.245 + bubble_down(h, data[n], n);
3.246 + else
3.247 + bubble_up(h, data[n]);
3.248 + }
3.249 + data.pop_back();
3.250 + }
3.251 +
3.252 + /// \brief Returns the priority of \c i.
3.253 + ///
3.254 + /// This function returns the priority of item \c i.
3.255 + /// \pre \c i must be in the heap.
3.256 + /// \param i The item.
3.257 + Prio operator[](const Item &i) const {
3.258 + int idx = iim[i];
3.259 + return data[idx].second;
3.260 + }
3.261 +
3.262 + /// \brief \c i gets to the heap with priority \c p independently
3.263 + /// if \c i was already there.
3.264 + ///
3.265 + /// This method calls \ref push(\c i, \c p) if \c i is not stored
3.266 + /// in the heap and sets the priority of \c i to \c p otherwise.
3.267 + /// \param i The item.
3.268 + /// \param p The priority.
3.269 + void set(const Item &i, const Prio &p) {
3.270 + int idx = iim[i];
3.271 + if( idx < 0 )
3.272 + push(i,p);
3.273 + else if( comp(p, data[idx].second) )
3.274 + bubble_up(idx, Pair(i,p));
3.275 + else
3.276 + bubble_down(idx, Pair(i,p), data.size());
3.277 + }
3.278 +
3.279 + /// \brief Decreases the priority of \c i to \c p.
3.280 + ///
3.281 + /// This method decreases the priority of item \c i to \c p.
3.282 + /// \pre \c i must be stored in the heap with priority at least \c
3.283 + /// p relative to \c Compare.
3.284 + /// \param i The item.
3.285 + /// \param p The priority.
3.286 + void decrease(const Item &i, const Prio &p) {
3.287 + int idx = iim[i];
3.288 + bubble_up(idx, Pair(i,p));
3.289 + }
3.290 +
3.291 + /// \brief Increases the priority of \c i to \c p.
3.292 + ///
3.293 + /// This method sets the priority of item \c i to \c p.
3.294 + /// \pre \c i must be stored in the heap with priority at most \c
3.295 + /// p relative to \c Compare.
3.296 + /// \param i The item.
3.297 + /// \param p The priority.
3.298 + void increase(const Item &i, const Prio &p) {
3.299 + int idx = iim[i];
3.300 + bubble_down(idx, Pair(i,p), data.size());
3.301 + }
3.302 +
3.303 + /// \brief Returns if \c item is in, has already been in, or has
3.304 + /// never been in the heap.
3.305 + ///
3.306 + /// This method returns PRE_HEAP if \c item has never been in the
3.307 + /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
3.308 + /// otherwise. In the latter case it is possible that \c item will
3.309 + /// get back to the heap again.
3.310 + /// \param i The item.
3.311 + State state(const Item &i) const {
3.312 + int s = iim[i];
3.313 + if (s>=0) s=0;
3.314 + return State(s);
3.315 + }
3.316 +
3.317 + /// \brief Sets the state of the \c item in the heap.
3.318 + ///
3.319 + /// Sets the state of the \c item in the heap. It can be used to
3.320 + /// manually clear the heap when it is important to achive the
3.321 + /// better time complexity.
3.322 + /// \param i The item.
3.323 + /// \param st The state. It should not be \c IN_HEAP.
3.324 + void state(const Item& i, State st) {
3.325 + switch (st) {
3.326 + case POST_HEAP:
3.327 + case PRE_HEAP:
3.328 + if (state(i) == IN_HEAP) erase(i);
3.329 + iim[i] = st;
3.330 + break;
3.331 + case IN_HEAP:
3.332 + break;
3.333 + }
3.334 + }
3.335 +
3.336 + /// \brief Replaces an item in the heap.
3.337 + ///
3.338 + /// The \c i item is replaced with \c j item. The \c i item should
3.339 + /// be in the heap, while the \c j should be out of the heap. The
3.340 + /// \c i item will out of the heap and \c j will be in the heap
3.341 + /// with the same prioriority as prevoiusly the \c i item.
3.342 + void replace(const Item& i, const Item& j) {
3.343 + int idx = iim[i];
3.344 + iim.set(i, iim[j]);
3.345 + iim.set(j, idx);
3.346 + data[idx].first = j;
3.347 + }
3.348 +
3.349 + }; // class FouraryHeap
3.350 +
3.351 +} // namespace lemon
3.352 +
3.353 +#endif // LEMON_FOURARY_HEAP_H
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/lemon/kary_heap.h Thu Jul 09 02:38:01 2009 +0200
4.3 @@ -0,0 +1,342 @@
4.4 +/* -*- C++ -*-
4.5 + *
4.6 + * This file is a part of LEMON, a generic C++ optimization library
4.7 + *
4.8 + * Copyright (C) 2003-2008
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 auxdat
4.26 +///\file
4.27 +///\brief Kary Heap implementation.
4.28 +
4.29 +#include <iostream>
4.30 +#include <vector>
4.31 +#include <utility>
4.32 +#include <functional>
4.33 +
4.34 +namespace lemon {
4.35 +
4.36 + ///\ingroup auxdat
4.37 + ///
4.38 + ///\brief A Kary Heap implementation.
4.39 + ///
4.40 + ///This class implements the \e Kary \e heap data structure. A \e heap
4.41 + ///is a data structure for storing items with specified values called \e
4.42 + ///priorities in such a way that finding the item with minimum priority is
4.43 + ///efficient. \c Compare specifies the ordering of the priorities. In a heap
4.44 + ///one can change the priority of an item, add or erase an item, etc.
4.45 + ///
4.46 + ///\param _Prio Type of the priority of the items.
4.47 + ///\param _ItemIntMap A read and writable Item int map, used internally
4.48 + ///to handle the cross references.
4.49 + ///\param _Compare A class for the ordering of the priorities. The
4.50 + ///default is \c std::less<_Prio>.
4.51 + ///
4.52 + ///\sa FibHeap
4.53 + ///\sa Dijkstra
4.54 + ///\author Dorian Batha
4.55 +
4.56 + template <typename _Prio, typename _ItemIntMap,
4.57 + typename _Compare = std::less<_Prio> >
4.58 +
4.59 + class KaryHeap {
4.60 +
4.61 + public:
4.62 + ///\e
4.63 + typedef _ItemIntMap ItemIntMap;
4.64 + ///\e
4.65 + typedef _Prio Prio;
4.66 + ///\e
4.67 + typedef typename ItemIntMap::Key Item;
4.68 + ///\e
4.69 + typedef std::pair<Item,Prio> Pair;
4.70 + ///\e
4.71 + typedef _Compare Compare;
4.72 + ///\e
4.73 +
4.74 + /// \brief Type to represent the items states.
4.75 + ///
4.76 + /// Each Item element have a state associated to it. It may be "in heap",
4.77 + /// "pre heap" or "post heap". The latter two are indifferent from the
4.78 + /// heap's point of view, but may be useful to the user.
4.79 + ///
4.80 + /// The ItemIntMap \e should be initialized in such way that it maps
4.81 + /// PRE_HEAP (-1) to any element to be put in the heap...
4.82 + enum State {
4.83 + IN_HEAP = 0,
4.84 + PRE_HEAP = -1,
4.85 + POST_HEAP = -2
4.86 + };
4.87 +
4.88 + private:
4.89 + std::vector<Pair> data;
4.90 + Compare comp;
4.91 + ItemIntMap &iim;
4.92 + int K;
4.93 +
4.94 + public:
4.95 + /// \brief The constructor.
4.96 + ///
4.97 + /// The constructor.
4.98 + /// \param _iim should be given to the constructor, since it is used
4.99 + /// internally to handle the cross references. The value of the map
4.100 + /// should be PRE_HEAP (-1) for each element.
4.101 + explicit KaryHeap(ItemIntMap &_iim, const int &_K=32) : iim(_iim), K(_K) {}
4.102 +
4.103 + /// \brief The constructor.
4.104 + ///
4.105 + /// The constructor.
4.106 + /// \param _iim should be given to the constructor, since it is used
4.107 + /// internally to handle the cross references. The value of the map
4.108 + /// should be PRE_HEAP (-1) for each element.
4.109 + ///
4.110 + /// \param _comp The comparator function object.
4.111 + KaryHeap(ItemIntMap &_iim, const Compare &_comp, const int &_K=32)
4.112 + : iim(_iim), comp(_comp), K(_K) {}
4.113 +
4.114 +
4.115 + /// The number of items stored in the heap.
4.116 + ///
4.117 + /// \brief Returns the number of items stored in the heap.
4.118 + int size() const { return data.size(); }
4.119 +
4.120 + /// \brief Checks if the heap stores no items.
4.121 + ///
4.122 + /// Returns \c true if and only if the heap stores no items.
4.123 + bool empty() const { return data.empty(); }
4.124 +
4.125 + /// \brief Make empty this heap.
4.126 + ///
4.127 + /// Make empty this heap. It does not change the cross reference map.
4.128 + /// If you want to reuse what is not surely empty you should first clear
4.129 + /// the heap and after that you should set the cross reference map for
4.130 + /// each item to \c PRE_HEAP.
4.131 + void clear() { data.clear(); }
4.132 +
4.133 + private:
4.134 + int parent(int i) { return (i-1)/K; }
4.135 + int first_child(int i) { return K*i+1; }
4.136 +
4.137 + bool less(const Pair &p1, const Pair &p2) const {
4.138 + return comp(p1.second, p2.second);
4.139 + }
4.140 +
4.141 + int find_min(const int child, const int length) {
4.142 + int min=child, i=1;
4.143 + while( i<K && child+i<length ) {
4.144 + if( less(data[child+i], data[min]) )
4.145 + min=child+i;
4.146 + ++i;
4.147 + }
4.148 + return min;
4.149 + }
4.150 +
4.151 + void bubble_up(int hole, Pair p) {
4.152 + int par = parent(hole);
4.153 + while( hole>0 && less(p,data[par]) ) {
4.154 + move(data[par],hole);
4.155 + hole = par;
4.156 + par = parent(hole);
4.157 + }
4.158 + move(p, hole);
4.159 + }
4.160 +
4.161 + void bubble_down(int hole, Pair p, int length) {
4.162 + if( length>1 ) {
4.163 + int child = first_child(hole);
4.164 + while( child<length ) {
4.165 + child = find_min(child, length);
4.166 + if( !less(data[child], p) )
4.167 + goto ok;
4.168 + move(data[child], hole);
4.169 + hole = child;
4.170 + child = first_child(hole);
4.171 + }
4.172 + }
4.173 + ok:
4.174 + move(p, hole);
4.175 + }
4.176 +
4.177 + void move(const Pair &p, int i) {
4.178 + data[i] = p;
4.179 + iim.set(p.first, i);
4.180 + }
4.181 +
4.182 + public:
4.183 + /// \brief Insert a pair of item and priority into the heap.
4.184 + ///
4.185 + /// Adds \c p.first to the heap with priority \c p.second.
4.186 + /// \param p The pair to insert.
4.187 + void push(const Pair &p) {
4.188 + int n = data.size();
4.189 + data.resize(n+1);
4.190 + bubble_up(n, p);
4.191 + }
4.192 +
4.193 + /// \brief Insert an item into the heap with the given heap.
4.194 + ///
4.195 + /// Adds \c i to the heap with priority \c p.
4.196 + /// \param i The item to insert.
4.197 + /// \param p The priority of the item.
4.198 + void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
4.199 +
4.200 + /// \brief Returns the item with minimum priority relative to \c Compare.
4.201 + ///
4.202 + /// This method returns the item with minimum priority relative to \c
4.203 + /// Compare.
4.204 + /// \pre The heap must be nonempty.
4.205 + Item top() const { return data[0].first; }
4.206 +
4.207 + /// \brief Returns the minimum priority relative to \c Compare.
4.208 + ///
4.209 + /// It returns the minimum priority relative to \c Compare.
4.210 + /// \pre The heap must be nonempty.
4.211 + Prio prio() const { return data[0].second; }
4.212 +
4.213 + /// \brief Deletes the item with minimum priority relative to \c Compare.
4.214 + ///
4.215 + /// This method deletes the item with minimum priority relative to \c
4.216 + /// Compare from the heap.
4.217 + /// \pre The heap must be non-empty.
4.218 + void pop() {
4.219 + int n = data.size()-1;
4.220 + iim.set(data[0].first, POST_HEAP);
4.221 + if (n>0) bubble_down(0, data[n], n);
4.222 + data.pop_back();
4.223 + }
4.224 +
4.225 + /// \brief Deletes \c i from the heap.
4.226 + ///
4.227 + /// This method deletes item \c i from the heap.
4.228 + /// \param i The item to erase.
4.229 + /// \pre The item should be in the heap.
4.230 + void erase(const Item &i) {
4.231 + int h = iim[i];
4.232 + int n = data.size()-1;
4.233 + iim.set(data[h].first, POST_HEAP);
4.234 + if( h<n ) {
4.235 + if( less(data[parent(h)], data[n]) )
4.236 + bubble_down(h, data[n], n);
4.237 + else
4.238 + bubble_up(h, data[n]);
4.239 + }
4.240 + data.pop_back();
4.241 + }
4.242 +
4.243 +
4.244 + /// \brief Returns the priority of \c i.
4.245 + ///
4.246 + /// This function returns the priority of item \c i.
4.247 + /// \pre \c i must be in the heap.
4.248 + /// \param i The item.
4.249 + Prio operator[](const Item &i) const {
4.250 + int idx = iim[i];
4.251 + return data[idx].second;
4.252 + }
4.253 +
4.254 + /// \brief \c i gets to the heap with priority \c p independently
4.255 + /// if \c i was already there.
4.256 + ///
4.257 + /// This method calls \ref push(\c i, \c p) if \c i is not stored
4.258 + /// in the heap and sets the priority of \c i to \c p otherwise.
4.259 + /// \param i The item.
4.260 + /// \param p The priority.
4.261 + void set(const Item &i, const Prio &p) {
4.262 + int idx = iim[i];
4.263 + if( idx<0 )
4.264 + push(i,p);
4.265 + else if( comp(p, data[idx].second) )
4.266 + bubble_up(idx, Pair(i,p));
4.267 + else
4.268 + bubble_down(idx, Pair(i,p), data.size());
4.269 + }
4.270 +
4.271 + /// \brief Decreases the priority of \c i to \c p.
4.272 + ///
4.273 + /// This method decreases the priority of item \c i to \c p.
4.274 + /// \pre \c i must be stored in the heap with priority at least \c
4.275 + /// p relative to \c Compare.
4.276 + /// \param i The item.
4.277 + /// \param p The priority.
4.278 + void decrease(const Item &i, const Prio &p) {
4.279 + int idx = iim[i];
4.280 + bubble_up(idx, Pair(i,p));
4.281 + }
4.282 +
4.283 + /// \brief Increases the priority of \c i to \c p.
4.284 + ///
4.285 + /// This method sets the priority of item \c i to \c p.
4.286 + /// \pre \c i must be stored in the heap with priority at most \c
4.287 + /// p relative to \c Compare.
4.288 + /// \param i The item.
4.289 + /// \param p The priority.
4.290 + void increase(const Item &i, const Prio &p) {
4.291 + int idx = iim[i];
4.292 + bubble_down(idx, Pair(i,p), data.size());
4.293 + }
4.294 +
4.295 + /// \brief Returns if \c item is in, has already been in, or has
4.296 + /// never been in the heap.
4.297 + ///
4.298 + /// This method returns PRE_HEAP if \c item has never been in the
4.299 + /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
4.300 + /// otherwise. In the latter case it is possible that \c item will
4.301 + /// get back to the heap again.
4.302 + /// \param i The item.
4.303 + State state(const Item &i) const {
4.304 + int s = iim[i];
4.305 + if (s>=0) s=0;
4.306 + return State(s);
4.307 + }
4.308 +
4.309 + /// \brief Sets the state of the \c item in the heap.
4.310 + ///
4.311 + /// Sets the state of the \c item in the heap. It can be used to
4.312 + /// manually clear the heap when it is important to achive the
4.313 + /// better time complexity.
4.314 + /// \param i The item.
4.315 + /// \param st The state. It should not be \c IN_HEAP.
4.316 + void state(const Item& i, State st) {
4.317 + switch (st) {
4.318 + case POST_HEAP:
4.319 + case PRE_HEAP:
4.320 + if (state(i) == IN_HEAP) erase(i);
4.321 + iim[i] = st;
4.322 + break;
4.323 + case IN_HEAP:
4.324 + break;
4.325 + }
4.326 + }
4.327 +
4.328 + /// \brief Replaces an item in the heap.
4.329 + ///
4.330 + /// The \c i item is replaced with \c j item. The \c i item should
4.331 + /// be in the heap, while the \c j should be out of the heap. The
4.332 + /// \c i item will out of the heap and \c j will be in the heap
4.333 + /// with the same prioriority as prevoiusly the \c i item.
4.334 + void replace(const Item& i, const Item& j) {
4.335 + int idx=iim[i];
4.336 + iim.set(i, iim[j]);
4.337 + iim.set(j, idx);
4.338 + data[idx].first=j;
4.339 + }
4.340 +
4.341 + }; // class KaryHeap
4.342 +
4.343 +} // namespace lemon
4.344 +
4.345 +#endif // LEMON_KARY_HEAP_H
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/lemon/pairing_heap.h Thu Jul 09 02:38:01 2009 +0200
5.3 @@ -0,0 +1,469 @@
5.4 +/* -*- C++ -*-
5.5 + *
5.6 + * This file is a part of LEMON, a generic C++ optimization library
5.7 + *
5.8 + * Copyright (C) 2003-2008
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 auxdat
5.27 +///\brief Pairing Heap implementation.
5.28 +
5.29 +#include <vector>
5.30 +#include <functional>
5.31 +#include <lemon/math.h>
5.32 +
5.33 +namespace lemon {
5.34 +
5.35 + /// \ingroup auxdat
5.36 + ///
5.37 + ///\brief Pairing Heap.
5.38 + ///
5.39 + ///This class implements the \e Pairing \e heap data structure. A \e heap
5.40 + ///is a data structure for storing items with specified values called \e
5.41 + ///priorities in such a way that finding the item with minimum priority is
5.42 + ///efficient. \c Compare specifies the ordering of the priorities. In a heap
5.43 + ///one can change the priority of an item, add or erase an item, etc.
5.44 + ///
5.45 + ///The methods \ref increase and \ref erase are not efficient in a Pairing
5.46 + ///heap. In case of many calls to these operations, it is better to use a
5.47 + ///\ref BinHeap "binary heap".
5.48 + ///
5.49 + ///\param _Prio Type of the priority of the items.
5.50 + ///\param _ItemIntMap A read and writable Item int map, used internally
5.51 + ///to handle the cross references.
5.52 + ///\param _Compare A class for the ordering of the priorities. The
5.53 + ///default is \c std::less<_Prio>.
5.54 + ///
5.55 + ///\sa BinHeap
5.56 + ///\sa Dijkstra
5.57 + ///\author Dorian Batha
5.58 +
5.59 +#ifdef DOXYGEN
5.60 + template <typename _Prio,
5.61 + typename _ItemIntMap,
5.62 + typename _Compare>
5.63 +#else
5.64 + template <typename _Prio,
5.65 + typename _ItemIntMap,
5.66 + typename _Compare = std::less<_Prio> >
5.67 +#endif
5.68 + class PairingHeap {
5.69 + public:
5.70 + typedef _ItemIntMap ItemIntMap;
5.71 + typedef _Prio Prio;
5.72 + typedef typename ItemIntMap::Key Item;
5.73 + typedef std::pair<Item,Prio> Pair;
5.74 + typedef _Compare Compare;
5.75 +
5.76 + private:
5.77 + class store;
5.78 +
5.79 + std::vector<store> container;
5.80 + int minimum;
5.81 + ItemIntMap &iimap;
5.82 + Compare comp;
5.83 + int num_items;
5.84 +
5.85 + public:
5.86 + ///Status of the nodes
5.87 + enum State {
5.88 + ///The node is in the heap
5.89 + IN_HEAP = 0,
5.90 + ///The node has never been in the heap
5.91 + PRE_HEAP = -1,
5.92 + ///The node was in the heap but it got out of it
5.93 + POST_HEAP = -2
5.94 + };
5.95 +
5.96 + /// \brief The constructor
5.97 + ///
5.98 + /// \c _iimap should be given to the constructor, since it is
5.99 + /// used internally to handle the cross references.
5.100 + explicit PairingHeap(ItemIntMap &_iimap)
5.101 + : minimum(0), iimap(_iimap), num_items(0) {}
5.102 +
5.103 + /// \brief The constructor
5.104 + ///
5.105 + /// \c _iimap should be given to the constructor, since it is used
5.106 + /// internally to handle the cross references. \c _comp is an
5.107 + /// object for ordering of the priorities.
5.108 + PairingHeap(ItemIntMap &_iimap, const Compare &_comp)
5.109 + : minimum(0), iimap(_iimap), comp(_comp), num_items(0) {}
5.110 +
5.111 + /// \brief The number of items stored in the heap.
5.112 + ///
5.113 + /// Returns the number of items stored in the heap.
5.114 + int size() const { return num_items; }
5.115 +
5.116 + /// \brief Checks if the heap stores no items.
5.117 + ///
5.118 + /// Returns \c true if and only if the heap stores no items.
5.119 + bool empty() const { return num_items==0; }
5.120 +
5.121 + /// \brief Make empty this heap.
5.122 + ///
5.123 + /// Make empty this heap. It does not change the cross reference
5.124 + /// map. If you want to reuse a heap what is not surely empty you
5.125 + /// should first clear the heap and after that you should set the
5.126 + /// cross reference map for each item to \c PRE_HEAP.
5.127 + void clear() {
5.128 + container.clear();
5.129 + minimum = 0;
5.130 + num_items = 0;
5.131 + }
5.132 +
5.133 + /// \brief \c item gets to the heap with priority \c value independently
5.134 + /// if \c item was already there.
5.135 + ///
5.136 + /// This method calls \ref push(\c item, \c value) if \c item is not
5.137 + /// stored in the heap and it calls \ref decrease(\c item, \c value) or
5.138 + /// \ref increase(\c item, \c value) otherwise.
5.139 + void set (const Item& item, const Prio& value) {
5.140 + int i=iimap[item];
5.141 + if ( i>=0 && container[i].in ) {
5.142 + if ( comp(value, container[i].prio) ) decrease(item, value);
5.143 + if ( comp(container[i].prio, value) ) increase(item, value);
5.144 + } else push(item, value);
5.145 + }
5.146 +
5.147 + /// \brief Adds \c item to the heap with priority \c value.
5.148 + ///
5.149 + /// Adds \c item to the heap with priority \c value.
5.150 + /// \pre \c item must not be stored in the heap.
5.151 + void push (const Item& item, const Prio& value) {
5.152 + int i=iimap[item];
5.153 + if( i<0 ) {
5.154 + int s=container.size();
5.155 + iimap.set(item, s);
5.156 + store st;
5.157 + st.name=item;
5.158 + container.push_back(st);
5.159 + i=s;
5.160 + } else {
5.161 + container[i].parent=container[i].child=-1;
5.162 + container[i].left_child=false;
5.163 + container[i].degree=0;
5.164 + container[i].in=true;
5.165 + }
5.166 +
5.167 + container[i].prio=value;
5.168 +
5.169 + if ( num_items!=0 ) {
5.170 + if ( comp( value, container[minimum].prio) ) {
5.171 + fuse(i,minimum);
5.172 + minimum=i;
5.173 + }
5.174 + else fuse(minimum,i);
5.175 + }
5.176 + else minimum=i;
5.177 +
5.178 + ++num_items;
5.179 + }
5.180 +
5.181 + /// \brief Returns the item with minimum priority relative to \c Compare.
5.182 + ///
5.183 + /// This method returns the item with minimum priority relative to \c
5.184 + /// Compare.
5.185 + /// \pre The heap must be nonempty.
5.186 + Item top() const { return container[minimum].name; }
5.187 +
5.188 + /// \brief Returns the minimum priority relative to \c Compare.
5.189 + ///
5.190 + /// It returns the minimum priority relative to \c Compare.
5.191 + /// \pre The heap must be nonempty.
5.192 + const Prio& prio() const { return container[minimum].prio; }
5.193 +
5.194 + /// \brief Returns the priority of \c item.
5.195 + ///
5.196 + /// It returns the priority of \c item.
5.197 + /// \pre \c item must be in the heap.
5.198 + const Prio& operator[](const Item& item) const {
5.199 + return container[iimap[item]].prio;
5.200 + }
5.201 +
5.202 + /// \brief Deletes the item with minimum priority relative to \c Compare.
5.203 + ///
5.204 + /// This method deletes the item with minimum priority relative to \c
5.205 + /// Compare from the heap.
5.206 + /// \pre The heap must be non-empty.
5.207 + void pop() {
5.208 + int TreeArray[num_items];
5.209 + int i=0, num_child=0, child_right = 0;
5.210 + container[minimum].in=false;
5.211 +
5.212 + if( -1!=container[minimum].child ) {
5.213 + i=container[minimum].child;
5.214 + TreeArray[num_child] = i;
5.215 + container[i].parent = -1;
5.216 + container[minimum].child = -1;
5.217 +
5.218 + ++num_child;
5.219 + int ch=-1;
5.220 + while( container[i].child!=-1 ) {
5.221 + ch=container[i].child;
5.222 + if( container[ch].left_child && i==container[ch].parent ) {
5.223 + i=ch;
5.224 + //break;
5.225 + } else {
5.226 + if( container[ch].left_child ) {
5.227 + child_right=container[ch].parent;
5.228 + container[ch].parent = i;
5.229 + --container[i].degree;
5.230 + }
5.231 + else {
5.232 + child_right=ch;
5.233 + container[i].child=-1;
5.234 + container[i].degree=0;
5.235 + }
5.236 + container[child_right].parent = -1;
5.237 + TreeArray[num_child] = child_right;
5.238 + i = child_right;
5.239 + ++num_child;
5.240 + }
5.241 + }
5.242 +
5.243 + int other;
5.244 + for( i=0; i<num_child-1; i+=2 ) {
5.245 + if ( !comp(container[TreeArray[i]].prio,
5.246 + container[TreeArray[i+1]].prio) ) {
5.247 + other=TreeArray[i];
5.248 + TreeArray[i]=TreeArray[i+1];
5.249 + TreeArray[i+1]=other;
5.250 + }
5.251 + fuse( TreeArray[i], TreeArray[i+1] );
5.252 + }
5.253 +
5.254 + i = (0==(num_child % 2)) ? num_child-2 : num_child-1;
5.255 + while(i>=2) {
5.256 + if ( comp(container[TreeArray[i]].prio,
5.257 + container[TreeArray[i-2]].prio) ) {
5.258 + other=TreeArray[i];
5.259 + TreeArray[i]=TreeArray[i-2];
5.260 + TreeArray[i-2]=other;
5.261 + }
5.262 + fuse( TreeArray[i-2], TreeArray[i] );
5.263 + i-=2;
5.264 + }
5.265 + minimum = TreeArray[0];
5.266 + }
5.267 +
5.268 + if ( 0==num_child ) {
5.269 + minimum = container[minimum].child;
5.270 + }
5.271 +
5.272 + --num_items;
5.273 + }
5.274 +
5.275 + /// \brief Deletes \c item from the heap.
5.276 + ///
5.277 + /// This method deletes \c item from the heap, if \c item was already
5.278 + /// stored in the heap. It is quite inefficient in Pairing heaps.
5.279 + void erase (const Item& item) {
5.280 + int i=iimap[item];
5.281 + if ( i>=0 && container[i].in ) {
5.282 + decrease( item, container[minimum].prio-1 );
5.283 + pop();
5.284 + }
5.285 + }
5.286 +
5.287 + /// \brief Decreases the priority of \c item to \c value.
5.288 + ///
5.289 + /// This method decreases the priority of \c item to \c value.
5.290 + /// \pre \c item must be stored in the heap with priority at least \c
5.291 + /// value relative to \c Compare.
5.292 + void decrease (Item item, const Prio& value) {
5.293 + int i=iimap[item];
5.294 + container[i].prio=value;
5.295 + int p=container[i].parent;
5.296 +
5.297 + if( container[i].left_child && i!=container[p].child ) {
5.298 + p=container[p].parent;
5.299 + }
5.300 +
5.301 + if ( p!=-1 && comp(value,container[p].prio) ) {
5.302 + cut(i,p);
5.303 + if ( comp(container[minimum].prio,value) ) {
5.304 + fuse(minimum,i);
5.305 + } else {
5.306 + fuse(i,minimum);
5.307 + minimum=i;
5.308 + }
5.309 + }
5.310 + }
5.311 +
5.312 + /// \brief Increases the priority of \c item to \c value.
5.313 + ///
5.314 + /// This method sets the priority of \c item to \c value. Though
5.315 + /// there is no precondition on the priority of \c item, this
5.316 + /// method should be used only if it is indeed necessary to increase
5.317 + /// (relative to \c Compare) the priority of \c item, because this
5.318 + /// method is inefficient.
5.319 + void increase (Item item, const Prio& value) {
5.320 + erase(item);
5.321 + push(item,value);
5.322 + }
5.323 +
5.324 + /// \brief Returns if \c item is in, has already been in, or has never
5.325 + /// been in the heap.
5.326 + ///
5.327 + /// This method returns PRE_HEAP if \c item has never been in the
5.328 + /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
5.329 + /// otherwise. In the latter case it is possible that \c item will
5.330 + /// get back to the heap again.
5.331 + State state(const Item &item) const {
5.332 + int i=iimap[item];
5.333 + if( i>=0 ) {
5.334 + if( container[i].in ) i=0;
5.335 + else i=-2;
5.336 + }
5.337 + return State(i);
5.338 + }
5.339 +
5.340 + /// \brief Sets the state of the \c item in the heap.
5.341 + ///
5.342 + /// Sets the state of the \c item in the heap. It can be used to
5.343 + /// manually clear the heap when it is important to achive the
5.344 + /// better time complexity.
5.345 + /// \param i The item.
5.346 + /// \param st The state. It should not be \c IN_HEAP.
5.347 + void state(const Item& i, State st) {
5.348 + switch (st) {
5.349 + case POST_HEAP:
5.350 + case PRE_HEAP:
5.351 + if (state(i) == IN_HEAP) erase(i);
5.352 + iimap[i]=st;
5.353 + break;
5.354 + case IN_HEAP:
5.355 + break;
5.356 + }
5.357 + }
5.358 +
5.359 + private:
5.360 +
5.361 + void cut(int a, int b) {
5.362 + int child_a;
5.363 + switch (container[a].degree) {
5.364 + case 2:
5.365 + child_a = container[container[a].child].parent;
5.366 + if( container[a].left_child ) {
5.367 + container[child_a].left_child=true;
5.368 + container[b].child=child_a;
5.369 + container[child_a].parent=container[a].parent;
5.370 + }
5.371 + else {
5.372 + container[child_a].left_child=false;
5.373 + container[child_a].parent=b;
5.374 + if( a!=container[b].child )
5.375 + container[container[b].child].parent=child_a;
5.376 + else
5.377 + container[b].child=child_a;
5.378 + }
5.379 + --container[a].degree;
5.380 + container[container[a].child].parent=a;
5.381 + break;
5.382 +
5.383 + case 1:
5.384 + child_a = container[a].child;
5.385 + if( !container[child_a].left_child ) {
5.386 + --container[a].degree;
5.387 + if( container[a].left_child ) {
5.388 + container[child_a].left_child=true;
5.389 + container[child_a].parent=container[a].parent;
5.390 + container[b].child=child_a;
5.391 + }
5.392 + else {
5.393 + container[child_a].left_child=false;
5.394 + container[child_a].parent=b;
5.395 + if( a!=container[b].child )
5.396 + container[container[b].child].parent=child_a;
5.397 + else
5.398 + container[b].child=child_a;
5.399 + }
5.400 + container[a].child=-1;
5.401 + }
5.402 + else {
5.403 + --container[b].degree;
5.404 + if( container[a].left_child ) {
5.405 + container[b].child =
5.406 + (1==container[b].degree) ? container[a].parent : -1;
5.407 + } else {
5.408 + if (1==container[b].degree)
5.409 + container[container[b].child].parent=b;
5.410 + else
5.411 + container[b].child=-1;
5.412 + }
5.413 + }
5.414 + break;
5.415 +
5.416 + case 0:
5.417 + --container[b].degree;
5.418 + if( container[a].left_child ) {
5.419 + container[b].child =
5.420 + (0!=container[b].degree) ? container[a].parent : -1;
5.421 + } else {
5.422 + if( 0!=container[b].degree )
5.423 + container[container[b].child].parent=b;
5.424 + else
5.425 + container[b].child=-1;
5.426 + }
5.427 + break;
5.428 + }
5.429 + container[a].parent=-1;
5.430 + container[a].left_child=false;
5.431 + }
5.432 +
5.433 + void fuse(int a, int b) {
5.434 + int child_a = container[a].child;
5.435 + int child_b = container[b].child;
5.436 + container[a].child=b;
5.437 + container[b].parent=a;
5.438 + container[b].left_child=true;
5.439 +
5.440 + if( -1!=child_a ) {
5.441 + container[b].child=child_a;
5.442 + container[child_a].parent=b;
5.443 + container[child_a].left_child=false;
5.444 + ++container[b].degree;
5.445 +
5.446 + if( -1!=child_b ) {
5.447 + container[b].child=child_b;
5.448 + container[child_b].parent=child_a;
5.449 + }
5.450 + }
5.451 + else { ++container[a].degree; }
5.452 + }
5.453 +
5.454 + class store {
5.455 + friend class PairingHeap;
5.456 +
5.457 + Item name;
5.458 + int parent;
5.459 + int child;
5.460 + bool left_child;
5.461 + int degree;
5.462 + bool in;
5.463 + Prio prio;
5.464 +
5.465 + store() : parent(-1), child(-1), left_child(false), degree(0), in(true) {}
5.466 + };
5.467 + };
5.468 +
5.469 +} //namespace lemon
5.470 +
5.471 +#endif //LEMON_PAIRING_HEAP_H
5.472 +
6.1 --- a/test/heap_test.cc Thu Jun 11 23:13:24 2009 +0200
6.2 +++ b/test/heap_test.cc Thu Jul 09 02:38:01 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 }