Changeset 2547:f393a8162688 in lemon-0.x
- Timestamp:
- 12/27/07 14:40:16 (16 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3424
- Location:
- lemon
- Files:
-
- 5 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bin_heap.h
r2546 r2547 40 40 ///one can change the priority of an item, add or erase an item, etc. 41 41 /// 42 ///\param Prio Type of the priority of the items.43 ///\param ItemIntMap A read and writable Item int map, used internally42 ///\param _Prio Type of the priority of the items. 43 ///\param _ItemIntMap A read and writable Item int map, used internally 44 44 ///to handle the cross references. 45 ///\param Compare A class for the ordering of the priorities. The46 ///default is \c std::less< Prio>.45 ///\param _Compare A class for the ordering of the priorities. The 46 ///default is \c std::less<_Prio>. 47 47 /// 48 48 ///\sa FibHeap 49 49 ///\sa Dijkstra 50 template <typename Prio, typenameItemIntMap,51 typename Compare = std::less<Prio> >50 template <typename _Prio, typename _ItemIntMap, 51 typename _Compare = std::less<_Prio> > 52 52 class BinHeap { 53 53 54 54 public: 55 typedef typename ItemIntMap::Key ItemType;56 typedef Prio PrioType;57 typedef std::pair<ItemType,PrioType> PairType;58 typedef ItemIntMap ItemIntMapType;59 typedef Compare PrioCompare;55 typedef _ItemIntMap ItemIntMap; 56 typedef _Prio Prio; 57 typedef typename ItemIntMap::Key Item; 58 typedef std::pair<Item,Prio> Pair; 59 typedef _Compare Compare; 60 60 61 61 /// \brief Type to represent the items states. … … 67 67 /// The ItemIntMap \e should be initialized in such way that it maps 68 68 /// PRE_HEAP (-1) to any element to be put in the heap... 69 enum state_enum{69 enum State { 70 70 IN_HEAP = 0, 71 71 PRE_HEAP = -1, … … 74 74 75 75 private: 76 std::vector<Pair Type> data;76 std::vector<Pair> data; 77 77 Compare comp; 78 78 ItemIntMap &iim; … … 123 123 124 124 static int second_child(int i) { return 2*i+2; } 125 bool less(const Pair Type &p1, const PairType&p2) const {125 bool less(const Pair &p1, const Pair &p2) const { 126 126 return comp(p1.second, p2.second); 127 127 } 128 128 129 int bubble_up(int hole, Pair Typep) {129 int bubble_up(int hole, Pair p) { 130 130 int par = parent(hole); 131 131 while( hole>0 && less(p,data[par]) ) { … … 138 138 } 139 139 140 int bubble_down(int hole, Pair Typep, int length) {140 int bubble_down(int hole, Pair p, int length) { 141 141 int child = second_child(hole); 142 142 while(child < length) { … … 160 160 } 161 161 162 void move(const Pair Type&p, int i) {162 void move(const Pair &p, int i) { 163 163 data[i] = p; 164 164 iim.set(p.first, i); … … 170 170 /// Adds \c p.first to the heap with priority \c p.second. 171 171 /// \param p The pair to insert. 172 void push(const Pair Type&p) {172 void push(const Pair &p) { 173 173 int n = data.size(); 174 174 data.resize(n+1); … … 181 181 /// \param i The item to insert. 182 182 /// \param p The priority of the item. 183 void push(const Item Type &i, const Prio &p) { push(PairType(i,p)); }183 void push(const Item &i, const Prio &p) { push(Pair(i,p)); } 184 184 185 185 /// \brief Returns the item with minimum priority relative to \c Compare. … … 188 188 /// Compare. 189 189 /// \pre The heap must be nonempty. 190 Item Typetop() const {190 Item top() const { 191 191 return data[0].first; 192 192 } … … 219 219 /// \param i The item to erase. 220 220 /// \pre The item should be in the heap. 221 void erase(const Item Type&i) {221 void erase(const Item &i) { 222 222 int h = iim[i]; 223 223 int n = data.size()-1; … … 237 237 /// \pre \c i must be in the heap. 238 238 /// \param i The item. 239 Prio operator[](const Item Type&i) const {239 Prio operator[](const Item &i) const { 240 240 int idx = iim[i]; 241 241 return data[idx].second; … … 249 249 /// \param i The item. 250 250 /// \param p The priority. 251 void set(const Item Type&i, const Prio &p) {251 void set(const Item &i, const Prio &p) { 252 252 int idx = iim[i]; 253 253 if( idx < 0 ) { … … 255 255 } 256 256 else if( comp(p, data[idx].second) ) { 257 bubble_up(idx, Pair Type(i,p));257 bubble_up(idx, Pair(i,p)); 258 258 } 259 259 else { 260 bubble_down(idx, Pair Type(i,p), data.size());260 bubble_down(idx, Pair(i,p), data.size()); 261 261 } 262 262 } … … 269 269 /// \param i The item. 270 270 /// \param p The priority. 271 void decrease(const Item Type&i, const Prio &p) {271 void decrease(const Item &i, const Prio &p) { 272 272 int idx = iim[i]; 273 bubble_up(idx, Pair Type(i,p));273 bubble_up(idx, Pair(i,p)); 274 274 } 275 275 … … 281 281 /// \param i The item. 282 282 /// \param p The priority. 283 void increase(const Item Type&i, const Prio &p) {283 void increase(const Item &i, const Prio &p) { 284 284 int idx = iim[i]; 285 bubble_down(idx, Pair Type(i,p), data.size());285 bubble_down(idx, Pair(i,p), data.size()); 286 286 } 287 287 … … 294 294 /// get back to the heap again. 295 295 /// \param i The item. 296 state_enum state(const ItemType&i) const {296 State state(const Item &i) const { 297 297 int s = iim[i]; 298 298 if( s>=0 ) 299 299 s=0; 300 return state_enum(s);300 return State(s); 301 301 } 302 302 … … 308 308 /// \param i The item. 309 309 /// \param st The state. It should not be \c IN_HEAP. 310 void state(const Item Type& i, state_enumst) {310 void state(const Item& i, State st) { 311 311 switch (st) { 312 312 case POST_HEAP: -
lemon/bucket_heap.h
r2391 r2547 50 50 51 51 public: 52 /// \e 52 53 typedef typename _ItemIntMap::Key Item; 54 /// \e 53 55 typedef int Prio; 56 /// \e 54 57 typedef std::pair<Item, Prio> Pair; 58 /// \e 55 59 typedef _ItemIntMap ItemIntMap; 56 60 … … 63 67 /// The ItemIntMap \e should be initialized in such way that it maps 64 68 /// PRE_HEAP (-1) to any element to be put in the heap... 65 enum state_enum{69 enum State { 66 70 IN_HEAP = 0, 67 71 PRE_HEAP = -1, … … 279 283 /// get back to the heap again. 280 284 /// \param i The item. 281 state_enumstate(const Item &i) const {285 State state(const Item &i) const { 282 286 int idx = index[i]; 283 287 if (idx >= 0) idx = 0; 284 return state_enum(idx);288 return State(idx); 285 289 } 286 290 … … 292 296 /// \param i The item. 293 297 /// \param st The state. It should not be \c IN_HEAP. 294 void state(const Item& i, state_enumst) {298 void state(const Item& i, State st) { 295 299 switch (st) { 296 300 case POST_HEAP: … … 335 339 typedef _ItemIntMap ItemIntMap; 336 340 337 enum state_enum{341 enum State { 338 342 IN_HEAP = 0, 339 343 PRE_HEAP = -1, … … 473 477 } 474 478 475 state_enumstate(const Item &i) const {479 State state(const Item &i) const { 476 480 int idx = index[i]; 477 481 if (idx >= 0) idx = 0; 478 return state_enum(idx);479 } 480 481 void state(const Item& i, state_enumst) {482 return State(idx); 483 } 484 485 void state(const Item& i, State st) { 482 486 switch (st) { 483 487 case POST_HEAP: … … 547 551 /// The ItemIntMap \e should be initialized in such way that it maps 548 552 /// PRE_HEAP (-1) to any element to be put in the heap... 549 enum state_enum{553 enum State { 550 554 IN_HEAP = 0, 551 555 PRE_HEAP = -1, … … 684 688 /// get back to the heap again. 685 689 /// \param i The item. 686 state_enumstate(const Item &i) const {690 State state(const Item &i) const { 687 691 int idx = index[i]; 688 692 if (idx >= 0) idx = 0; 689 return state_enum(idx);693 return State(idx); 690 694 } 691 695 … … 717 721 typedef _ItemIntMap ItemIntMap; 718 722 719 enum state_enum{723 enum State { 720 724 IN_HEAP = 0, 721 725 PRE_HEAP = -1, … … 799 803 } 800 804 801 state_enumstate(const Item &i) const {805 State state(const Item &i) const { 802 806 int idx = index[i]; 803 807 if (idx >= 0) idx = 0; 804 return state_enum(idx);808 return State(idx); 805 809 } 806 810 -
lemon/concepts/heap.h
r2391 r2547 53 53 /// The ItemIntMap _should_ be initialized in such way, that it maps 54 54 /// PRE_HEAP (-1) to any element to be put in the heap... 55 enum state_enum{55 enum State { 56 56 IN_HEAP = 0, 57 57 PRE_HEAP = -1, … … 156 156 /// get back to the heap again. 157 157 /// \param i The item. 158 state_enumstate(const Item &i) const {}158 State state(const Item &i) const {} 159 159 160 160 /// \brief Sets the state of the \c item in the heap. … … 165 165 /// \param i The item. 166 166 /// \param st The state. It should not be \c IN_HEAP. 167 void state(const Item& i, state_enumst) {}167 void state(const Item& i, State st) {} 168 168 169 169 … … 182 182 ignore_unused_variable_warning(prio); 183 183 184 typedef typename _Heap:: state_enum state_enum;185 state_enumstate;184 typedef typename _Heap::State State; 185 State state; 186 186 187 187 ignore_unused_variable_warning(state); -
lemon/fib_heap.h
r2529 r2547 42 42 ///The methods \ref increase and \ref erase are not efficient in a Fibonacci 43 43 ///heap. In case of many calls to these operations, it is better to use a 44 ///\ e binary \e heap.44 ///\ref BinHeap "binary heap". 45 45 /// 46 ///\param Prio Type of the priority of the items.47 ///\param ItemIntMap A read and writable Item int map, used internally46 ///\param _Prio Type of the priority of the items. 47 ///\param _ItemIntMap A read and writable Item int map, used internally 48 48 ///to handle the cross references. 49 ///\param Compare A class for the ordering of the priorities. The50 ///default is \c std::less< Prio>.49 ///\param _Compare A class for the ordering of the priorities. The 50 ///default is \c std::less<_Prio>. 51 51 /// 52 52 ///\sa BinHeap … … 55 55 56 56 #ifdef DOXYGEN 57 template <typename Prio,58 typename ItemIntMap,59 typename Compare>57 template <typename _Prio, 58 typename _ItemIntMap, 59 typename _Compare> 60 60 #else 61 template <typename Prio,62 typename ItemIntMap,63 typename Compare = std::less<Prio> >61 template <typename _Prio, 62 typename _ItemIntMap, 63 typename _Compare = std::less<_Prio> > 64 64 #endif 65 65 class FibHeap { 66 66 public: 67 typedef _ItemIntMap ItemIntMap; 68 typedef _Prio Prio; 67 69 typedef typename ItemIntMap::Key Item; 68 typedef Prio PrioType; 70 typedef std::pair<Item,Prio> Pair; 71 typedef _Compare Compare; 69 72 70 73 private: … … 79 82 public: 80 83 ///Status of the nodes 81 enum state_enum{84 enum State { 82 85 ///The node is in the heap 83 86 IN_HEAP = 0, … … 100 103 /// internally to handle the cross references. \c _comp is an 101 104 /// object for ordering of the priorities. 102 FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0),103 105 FibHeap(ItemIntMap &_iimap, const Compare &_comp) 106 : minimum(0), iimap(_iimap), comp(_comp), num_items() {} 104 107 105 108 /// \brief The number of items stored in the heap. … … 129 132 /// stored in the heap and it calls \ref decrease(\c item, \c value) or 130 133 /// \ref increase(\c item, \c value) otherwise. 131 void set (Item const item, PrioType const value); 134 void set (const Item& item, const Prio& value) { 135 int i=iimap[item]; 136 if ( i >= 0 && container[i].in ) { 137 if ( comp(value, container[i].prio) ) decrease(item, value); 138 if ( comp(container[i].prio, value) ) increase(item, value); 139 } else push(item, value); 140 } 132 141 133 142 /// \brief Adds \c item to the heap with priority \c value. … … 135 144 /// Adds \c item to the heap with priority \c value. 136 145 /// \pre \c item must not be stored in the heap. 137 void push (Item const item, PrioType const value); 138 139 /// \brief Returns the item with minimum priority relative to \c Compare. 140 /// 141 /// This method returns the item with minimum priority relative to \c 142 /// Compare. 143 /// \pre The heap must be nonempty. 144 Item top() const { return container[minimum].name; } 145 146 /// \brief Returns the minimum priority relative to \c Compare. 147 /// 148 /// It returns the minimum priority relative to \c Compare. 149 /// \pre The heap must be nonempty. 150 PrioType prio() const { return container[minimum].prio; } 151 152 /// \brief Returns the priority of \c item. 153 /// 154 /// This function returns the priority of \c item. 155 /// \pre \c item must be in the heap. 156 PrioType& operator[](const Item& item) { 157 return container[iimap[item]].prio; 158 } 159 160 /// \brief Returns the priority of \c item. 161 /// 162 /// It returns the priority of \c item. 163 /// \pre \c item must be in the heap. 164 const PrioType& operator[](const Item& item) const { 165 return container[iimap[item]].prio; 166 } 167 168 169 /// \brief Deletes the item with minimum priority relative to \c Compare. 170 /// 171 /// This method deletes the item with minimum priority relative to \c 172 /// Compare from the heap. 173 /// \pre The heap must be non-empty. 174 void pop(); 175 176 /// \brief Deletes \c item from the heap. 177 /// 178 /// This method deletes \c item from the heap, if \c item was already 179 /// stored in the heap. It is quite inefficient in Fibonacci heaps. 180 void erase (const Item& item); 181 182 /// \brief Decreases the priority of \c item to \c value. 183 /// 184 /// This method decreases the priority of \c item to \c value. 185 /// \pre \c item must be stored in the heap with priority at least \c 186 /// value relative to \c Compare. 187 void decrease (Item item, PrioType const value); 188 189 /// \brief Increases the priority of \c item to \c value. 190 /// 191 /// This method sets the priority of \c item to \c value. Though 192 /// there is no precondition on the priority of \c item, this 193 /// method should be used only if it is indeed necessary to increase 194 /// (relative to \c Compare) the priority of \c item, because this 195 /// method is inefficient. 196 void increase (Item item, PrioType const value) { 197 erase(item); 198 push(item, value); 199 } 200 201 202 /// \brief Returns if \c item is in, has already been in, or has never 203 /// been in the heap. 204 /// 205 /// This method returns PRE_HEAP if \c item has never been in the 206 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP 207 /// otherwise. In the latter case it is possible that \c item will 208 /// get back to the heap again. 209 state_enum state(const Item &item) const { 210 int i=iimap[item]; 211 if( i>=0 ) { 212 if ( container[i].in ) i=0; 213 else i=-2; 214 } 215 return state_enum(i); 216 } 217 218 /// \brief Sets the state of the \c item in the heap. 219 /// 220 /// Sets the state of the \c item in the heap. It can be used to 221 /// manually clear the heap when it is important to achive the 222 /// better time complexity. 223 /// \param i The item. 224 /// \param st The state. It should not be \c IN_HEAP. 225 void state(const Item& i, state_enum st) { 226 switch (st) { 227 case POST_HEAP: 228 case PRE_HEAP: 229 if (state(i) == IN_HEAP) { 230 erase(i); 231 } 232 iimap[i] = st; 233 break; 234 case IN_HEAP: 235 break; 236 } 237 } 238 239 private: 240 241 void balance(); 242 void makeroot(int c); 243 void cut(int a, int b); 244 void cascade(int a); 245 void fuse(int a, int b); 246 void unlace(int a); 247 248 249 class store { 250 friend class FibHeap; 251 252 Item name; 253 int parent; 254 int left_neighbor; 255 int right_neighbor; 256 int child; 257 int degree; 258 bool marked; 259 bool in; 260 PrioType prio; 261 262 store() : parent(-1), child(-1), degree(), marked(false), in(true) {} 263 }; 264 }; 265 266 267 268 // ********************************************************************** 269 // IMPLEMENTATIONS 270 // ********************************************************************** 271 272 template <typename Prio, typename ItemIntMap, 273 typename Compare> 274 void FibHeap<Prio, ItemIntMap, Compare>::set 275 (Item const item, PrioType const value) 276 { 277 int i=iimap[item]; 278 if ( i >= 0 && container[i].in ) { 279 if ( comp(value, container[i].prio) ) decrease(item, value); 280 if ( comp(container[i].prio, value) ) increase(item, value); 281 } else push(item, value); 282 } 283 284 template <typename Prio, typename ItemIntMap, 285 typename Compare> 286 void FibHeap<Prio, ItemIntMap, Compare>::push 287 (Item const item, PrioType const value) { 146 void push (const Item& item, const Prio& value) { 288 147 int i=iimap[item]; 289 148 if ( i < 0 ) { … … 315 174 } 316 175 317 template <typename Prio, typename ItemIntMap, 318 typename Compare> 319 void FibHeap<Prio, ItemIntMap, Compare>::pop() { 176 /// \brief Returns the item with minimum priority relative to \c Compare. 177 /// 178 /// This method returns the item with minimum priority relative to \c 179 /// Compare. 180 /// \pre The heap must be nonempty. 181 Item top() const { return container[minimum].name; } 182 183 /// \brief Returns the minimum priority relative to \c Compare. 184 /// 185 /// It returns the minimum priority relative to \c Compare. 186 /// \pre The heap must be nonempty. 187 const Prio& prio() const { return container[minimum].prio; } 188 189 /// \brief Returns the priority of \c item. 190 /// 191 /// It returns the priority of \c item. 192 /// \pre \c item must be in the heap. 193 const Prio& operator[](const Item& item) const { 194 return container[iimap[item]].prio; 195 } 196 197 /// \brief Deletes the item with minimum priority relative to \c Compare. 198 /// 199 /// This method deletes the item with minimum priority relative to \c 200 /// Compare from the heap. 201 /// \pre The heap must be non-empty. 202 void pop() { 320 203 /*The first case is that there are only one root.*/ 321 204 if ( container[minimum].left_neighbor==minimum ) { … … 334 217 int child=container[minimum].child; 335 218 int last_child=container[child].left_neighbor; 336 219 337 220 makeroot(child); 338 221 … … 348 231 } 349 232 350 351 template <typename Prio, typename ItemIntMap,352 typename Compare>353 void FibHeap<Prio, ItemIntMap, Compare>::erase354 (const Item& item) {233 /// \brief Deletes \c item from the heap. 234 /// 235 /// This method deletes \c item from the heap, if \c item was already 236 /// stored in the heap. It is quite inefficient in Fibonacci heaps. 237 void erase (const Item& item) { 355 238 int i=iimap[item]; 356 239 … … 364 247 pop(); 365 248 } 366 } 367 368 template <typename Prio, typename ItemIntMap, 369 typename Compare> 370 void FibHeap<Prio, ItemIntMap, Compare>::decrease 371 (Item item, PrioType const value) { 249 } 250 251 /// \brief Decreases the priority of \c item to \c value. 252 /// 253 /// This method decreases the priority of \c item to \c value. 254 /// \pre \c item must be stored in the heap with priority at least \c 255 /// value relative to \c Compare. 256 void decrease (Item item, const Prio& value) { 372 257 int i=iimap[item]; 373 258 container[i].prio=value; … … 379 264 } 380 265 if ( comp(value, container[minimum].prio) ) minimum=i; 381 } 382 383 384 template <typename Prio, typename ItemIntMap, 385 typename Compare> 386 void FibHeap<Prio, ItemIntMap, Compare>::balance() { 387 388 int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1; 266 } 267 268 /// \brief Increases the priority of \c item to \c value. 269 /// 270 /// This method sets the priority of \c item to \c value. Though 271 /// there is no precondition on the priority of \c item, this 272 /// method should be used only if it is indeed necessary to increase 273 /// (relative to \c Compare) the priority of \c item, because this 274 /// method is inefficient. 275 void increase (Item item, const Prio& value) { 276 erase(item); 277 push(item, value); 278 } 279 280 281 /// \brief Returns if \c item is in, has already been in, or has never 282 /// been in the heap. 283 /// 284 /// This method returns PRE_HEAP if \c item has never been in the 285 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP 286 /// otherwise. In the latter case it is possible that \c item will 287 /// get back to the heap again. 288 State state(const Item &item) const { 289 int i=iimap[item]; 290 if( i>=0 ) { 291 if ( container[i].in ) i=0; 292 else i=-2; 293 } 294 return State(i); 295 } 296 297 /// \brief Sets the state of the \c item in the heap. 298 /// 299 /// Sets the state of the \c item in the heap. It can be used to 300 /// manually clear the heap when it is important to achive the 301 /// better time complexity. 302 /// \param i The item. 303 /// \param st The state. It should not be \c IN_HEAP. 304 void state(const Item& i, State st) { 305 switch (st) { 306 case POST_HEAP: 307 case PRE_HEAP: 308 if (state(i) == IN_HEAP) { 309 erase(i); 310 } 311 iimap[i] = st; 312 break; 313 case IN_HEAP: 314 break; 315 } 316 } 317 318 private: 319 320 void balance() { 321 322 int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1; 389 323 390 std::vector<int> A(maxdeg,-1);391 392 /*393 *Recall that now minimum does not point to the minimum prio element.394 *We set minimum to this during balance().395 */396 int anchor=container[minimum].left_neighbor;397 int next=minimum;398 bool end=false;324 std::vector<int> A(maxdeg,-1); 325 326 /* 327 *Recall that now minimum does not point to the minimum prio element. 328 *We set minimum to this during balance(). 329 */ 330 int anchor=container[minimum].left_neighbor; 331 int next=minimum; 332 bool end=false; 399 333 400 334 do { 401 335 int active=next; 402 336 if ( anchor==active ) end=true; … … 415 349 } 416 350 A[d]=active; 417 } while ( !end ); 418 419 420 while ( container[minimum].parent >=0 ) minimum=container[minimum].parent; 421 int s=minimum; 422 int m=minimum; 423 do { 424 if ( comp(container[s].prio, container[minimum].prio) ) minimum=s; 425 s=container[s].right_neighbor; 426 } while ( s != m ); 427 } 428 429 template <typename Prio, typename ItemIntMap, 430 typename Compare> 431 void FibHeap<Prio, ItemIntMap, Compare>::makeroot 432 (int c) { 351 } while ( !end ); 352 353 354 while ( container[minimum].parent >=0 ) 355 minimum=container[minimum].parent; 356 int s=minimum; 357 int m=minimum; 358 do { 359 if ( comp(container[s].prio, container[minimum].prio) ) minimum=s; 360 s=container[s].right_neighbor; 361 } while ( s != m ); 362 } 363 364 void makeroot(int c) { 433 365 int s=c; 434 366 do { … … 437 369 } while ( s != c ); 438 370 } 439 440 441 template <typename Prio, typename ItemIntMap, 442 typename Compare> 443 void FibHeap<Prio, ItemIntMap, Compare>::cut 444 (int a, int b) { 445 /* 446 *Replacing a from the children of b. 447 */ 448 --container[b].degree; 449 450 if ( container[b].degree !=0 ) { 451 int child=container[b].child; 452 if ( child==a ) 453 container[b].child=container[child].right_neighbor; 454 unlace(a); 455 } 456 457 458 /*Lacing a to the roots.*/ 459 int right=container[minimum].right_neighbor; 460 container[minimum].right_neighbor=a; 461 container[a].left_neighbor=minimum; 462 container[a].right_neighbor=right; 463 container[right].left_neighbor=a; 464 465 container[a].parent=-1; 466 container[a].marked=false; 467 } 468 469 470 template <typename Prio, typename ItemIntMap, 471 typename Compare> 472 void FibHeap<Prio, ItemIntMap, Compare>::cascade 473 (int a) 474 { 371 372 void cut(int a, int b) { 373 /* 374 *Replacing a from the children of b. 375 */ 376 --container[b].degree; 377 378 if ( container[b].degree !=0 ) { 379 int child=container[b].child; 380 if ( child==a ) 381 container[b].child=container[child].right_neighbor; 382 unlace(a); 383 } 384 385 386 /*Lacing a to the roots.*/ 387 int right=container[minimum].right_neighbor; 388 container[minimum].right_neighbor=a; 389 container[a].left_neighbor=minimum; 390 container[a].right_neighbor=right; 391 container[right].left_neighbor=a; 392 393 container[a].parent=-1; 394 container[a].marked=false; 395 } 396 397 void cascade(int a) { 475 398 if ( container[a].parent!=-1 ) { 476 399 int p=container[a].parent; … … 484 407 } 485 408 486 487 template <typename Prio, typename ItemIntMap, 488 typename Compare> 489 void FibHeap<Prio, ItemIntMap, Compare>::fuse 490 (int a, int b) { 409 void fuse(int a, int b) { 491 410 unlace(b); 492 411 … … 512 431 } 513 432 514 515 /* 516 *It is invoked only if a has siblings. 517 */ 518 template <typename Prio, typename ItemIntMap, 519 typename Compare> 520 void FibHeap<Prio, ItemIntMap, Compare>::unlace 521 (int a) { 433 /* 434 *It is invoked only if a has siblings. 435 */ 436 void unlace(int a) { 522 437 int leftn=container[a].left_neighbor; 523 438 int rightn=container[a].right_neighbor; 524 439 container[leftn].right_neighbor=rightn; 525 440 container[rightn].left_neighbor=leftn; 526 } 527 441 } 442 443 444 class store { 445 friend class FibHeap; 446 447 Item name; 448 int parent; 449 int left_neighbor; 450 int right_neighbor; 451 int child; 452 int degree; 453 bool marked; 454 bool in; 455 Prio prio; 456 457 store() : parent(-1), child(-1), degree(), marked(false), in(true) {} 458 }; 459 }; 528 460 529 461 } //namespace lemon -
lemon/radix_heap.h
r2391 r2547 29 29 namespace lemon { 30 30 31 /// \brief Exception thrown by RadixHeap.32 ///33 /// This Exception is thrown when a smaller priority34 /// is inserted into the \e RadixHeap then the last time erased.35 /// \see RadixHeap36 /// \author Balazs Dezso37 38 class UnderFlowPriorityError : public RuntimeError {39 public:40 virtual const char* what() const throw() {41 return "lemon::UnderFlowPriorityError";42 }43 };44 31 45 32 /// \ingroup auxdata … … 70 57 typedef _ItemIntMap ItemIntMap; 71 58 59 /// \brief Exception thrown by RadixHeap. 60 /// 61 /// This Exception is thrown when a smaller priority 62 /// is inserted into the \e RadixHeap then the last time erased. 63 /// \see RadixHeap 64 /// \author Balazs Dezso 65 66 class UnderFlowPriorityError : public RuntimeError { 67 public: 68 virtual const char* what() const throw() { 69 return "lemon::RadixHeap::UnderFlowPriorityError"; 70 } 71 }; 72 72 73 /// \brief Type to represent the items states. 73 74 /// … … 78 79 /// The ItemIntMap \e should be initialized in such way that it maps 79 80 /// PRE_HEAP (-1) to any element to be put in the heap... 80 enum state_enum{81 enum State { 81 82 IN_HEAP = 0, 82 83 PRE_HEAP = -1, … … 402 403 /// get back to the heap again. 403 404 /// \param i The item. 404 state_enumstate(const Item &i) const {405 State state(const Item &i) const { 405 406 int s = iim[i]; 406 407 if( s >= 0 ) s = 0; 407 return state_enum(s);408 return State(s); 408 409 } 409 410 … … 415 416 /// \param i The item. 416 417 /// \param st The state. It should not be \c IN_HEAP. 417 void state(const Item& i, state_enumst) {418 void state(const Item& i, State st) { 418 419 switch (st) { 419 420 case POST_HEAP:
Note: See TracChangeset
for help on using the changeset viewer.