1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/elevator.h Mon Nov 17 15:41:15 2008 +0000
1.3 @@ -0,0 +1,1003 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2008
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef LEMON_ELEVATOR_H
1.23 +#define LEMON_ELEVATOR_H
1.24 +
1.25 +///\ingroup auxdat
1.26 +///\file
1.27 +///\brief Elevator class
1.28 +///
1.29 +///Elevator class implements an efficient data structure
1.30 +///for labeling items in push-relabel type algorithms.
1.31 +///
1.32 +
1.33 +#include <test/test_tools.h>
1.34 +namespace lemon {
1.35 +
1.36 + ///Class for handling "labels" in push-relabel type algorithms.
1.37 +
1.38 + ///A class for handling "labels" in push-relabel type algorithms.
1.39 + ///
1.40 + ///\ingroup auxdat
1.41 + ///Using this class you can assign "labels" (nonnegative integer numbers)
1.42 + ///to the edges or nodes of a graph, manipulate and query them through
1.43 + ///operations typically arising in "push-relabel" type algorithms.
1.44 + ///
1.45 + ///Each item is either \em active or not, and you can also choose a
1.46 + ///highest level active item.
1.47 + ///
1.48 + ///\sa LinkedElevator
1.49 + ///
1.50 + ///\param Graph the underlying graph type
1.51 + ///\param Item Type of the items the data is assigned to (Graph::Node,
1.52 + ///Graph::Edge, Graph::UEdge)
1.53 + template<class Graph, class Item>
1.54 + class Elevator
1.55 + {
1.56 + public:
1.57 +
1.58 + typedef Item Key;
1.59 + typedef int Value;
1.60 +
1.61 + private:
1.62 +
1.63 + typedef typename std::vector<Item>::iterator Vit;
1.64 + typedef typename ItemSetTraits<Graph,Item>::template Map<Vit>::Type VitMap;
1.65 + typedef typename ItemSetTraits<Graph,Item>::template Map<int>::Type IntMap;
1.66 +
1.67 + const Graph &_g;
1.68 + int _max_level;
1.69 + int _item_num;
1.70 + VitMap _where;
1.71 + IntMap _level;
1.72 + std::vector<Item> _items;
1.73 + std::vector<Vit> _first;
1.74 + std::vector<Vit> _last_active;
1.75 +
1.76 + int _highest_active;
1.77 +
1.78 + void copy(Item i, Vit p)
1.79 + {
1.80 + _where[*p=i]=p;
1.81 + }
1.82 + void copy(Vit s, Vit p)
1.83 + {
1.84 + if(s!=p)
1.85 + {
1.86 + Item i=*s;
1.87 + *p=i;
1.88 + _where[i]=p;
1.89 + }
1.90 + }
1.91 + void swap(Vit i, Vit j)
1.92 + {
1.93 + Item ti=*i;
1.94 + Vit ct = _where[ti];
1.95 + _where[ti]=_where[*i=*j];
1.96 + _where[*j]=ct;
1.97 + *j=ti;
1.98 + }
1.99 +
1.100 + public:
1.101 +
1.102 + ///Constructor with given maximum level.
1.103 +
1.104 + ///Constructor with given maximum level.
1.105 + ///
1.106 + ///\param g The underlying graph
1.107 + ///\param max_level Set the range of the possible labels to
1.108 + ///[0...\c max_level]
1.109 + Elevator(const Graph &g,int max_level) :
1.110 + _g(g),
1.111 + _max_level(max_level),
1.112 + _item_num(_max_level),
1.113 + _where(g),
1.114 + _level(g,0),
1.115 + _items(_max_level),
1.116 + _first(_max_level+2),
1.117 + _last_active(_max_level+2),
1.118 + _highest_active(-1) {}
1.119 + ///Constructor.
1.120 +
1.121 + ///Constructor.
1.122 + ///
1.123 + ///\param g The underlying graph
1.124 + ///The range of the possible labels is [0...\c max_level],
1.125 + ///where \c max_level is equal to the number of labeled items in the graph.
1.126 + Elevator(const Graph &g) :
1.127 + _g(g),
1.128 + _max_level(countItems<Graph, Item>(g)),
1.129 + _item_num(_max_level),
1.130 + _where(g),
1.131 + _level(g,0),
1.132 + _items(_max_level),
1.133 + _first(_max_level+2),
1.134 + _last_active(_max_level+2),
1.135 + _highest_active(-1)
1.136 + {
1.137 + }
1.138 +
1.139 + ///Activate item \c i.
1.140 +
1.141 + ///Activate item \c i.
1.142 + ///\pre Item \c i shouldn't be active before.
1.143 + void activate(Item i)
1.144 + {
1.145 + const int l=_level[i];
1.146 + swap(_where[i],++_last_active[l]);
1.147 + if(l>_highest_active) _highest_active=l;
1.148 + }
1.149 +
1.150 + ///Deactivate item \c i.
1.151 +
1.152 + ///Deactivate item \c i.
1.153 + ///\pre Item \c i must be active before.
1.154 + void deactivate(Item i)
1.155 + {
1.156 + swap(_where[i],_last_active[_level[i]]--);
1.157 + while(_highest_active>=0 &&
1.158 + _last_active[_highest_active]<_first[_highest_active])
1.159 + _highest_active--;
1.160 + }
1.161 +
1.162 + ///Query whether item \c i is active
1.163 + bool active(Item i) const { return _where[i]<=_last_active[_level[i]]; }
1.164 +
1.165 + ///Return the level of item \c i.
1.166 + int operator[](Item i) const { return _level[i]; }
1.167 +
1.168 + ///Return the number of items on level \c l.
1.169 + int onLevel(int l) const
1.170 + {
1.171 + return _first[l+1]-_first[l];
1.172 + }
1.173 + ///Return true if the level is empty.
1.174 + bool emptyLevel(int l) const
1.175 + {
1.176 + return _first[l+1]-_first[l]==0;
1.177 + }
1.178 + ///Return the number of items above level \c l.
1.179 + int aboveLevel(int l) const
1.180 + {
1.181 + return _first[_max_level+1]-_first[l+1];
1.182 + }
1.183 + ///Return the number of active items on level \c l.
1.184 + int activesOnLevel(int l) const
1.185 + {
1.186 + return _last_active[l]-_first[l]+1;
1.187 + }
1.188 + ///Return true if there is not active item on level \c l.
1.189 + bool activeFree(int l) const
1.190 + {
1.191 + return _last_active[l]<_first[l];
1.192 + }
1.193 + ///Return the maximum allowed level.
1.194 + int maxLevel() const
1.195 + {
1.196 + return _max_level;
1.197 + }
1.198 +
1.199 + ///\name Highest Active Item
1.200 + ///Functions for working with the highest level
1.201 + ///active item.
1.202 +
1.203 + ///@{
1.204 +
1.205 + ///Return a highest level active item.
1.206 +
1.207 + ///Return a highest level active item.
1.208 + ///
1.209 + ///\return the highest level active item or INVALID if there is no active
1.210 + ///item.
1.211 + Item highestActive() const
1.212 + {
1.213 + return _highest_active>=0?*_last_active[_highest_active]:INVALID;
1.214 + }
1.215 +
1.216 + ///Return a highest active level.
1.217 +
1.218 + ///Return a highest active level.
1.219 + ///
1.220 + ///\return the level of the highest active item or -1 if there is no active
1.221 + ///item.
1.222 + int highestActiveLevel() const
1.223 + {
1.224 + return _highest_active;
1.225 + }
1.226 +
1.227 + ///Lift the highest active item by one.
1.228 +
1.229 + ///Lift the item returned by highestActive() by one.
1.230 + ///
1.231 + void liftHighestActive()
1.232 + {
1.233 + ++_level[*_last_active[_highest_active]];
1.234 + swap(_last_active[_highest_active]--,_last_active[_highest_active+1]);
1.235 + --_first[++_highest_active];
1.236 + }
1.237 +
1.238 + ///Lift the highest active item.
1.239 +
1.240 + ///Lift the item returned by highestActive() to level \c new_level.
1.241 + ///
1.242 + ///\warning \c new_level must be strictly higher
1.243 + ///than the current level.
1.244 + ///
1.245 + void liftHighestActive(int new_level)
1.246 + {
1.247 + const Item li = *_last_active[_highest_active];
1.248 +
1.249 + copy(--_first[_highest_active+1],_last_active[_highest_active]--);
1.250 + for(int l=_highest_active+1;l<new_level;l++)
1.251 + {
1.252 + copy(--_first[l+1],_first[l]);
1.253 + --_last_active[l];
1.254 + }
1.255 + copy(li,_first[new_level]);
1.256 + _level[li]=new_level;
1.257 + _highest_active=new_level;
1.258 + }
1.259 +
1.260 + ///Lift the highest active item.
1.261 +
1.262 + ///Lift the item returned by highestActive() to the top level and
1.263 + ///deactivates it.
1.264 + ///
1.265 + ///\warning \c new_level must be strictly higher
1.266 + ///than the current level.
1.267 + ///
1.268 + void liftHighestActiveToTop()
1.269 + {
1.270 + const Item li = *_last_active[_highest_active];
1.271 +
1.272 + copy(--_first[_highest_active+1],_last_active[_highest_active]--);
1.273 + for(int l=_highest_active+1;l<_max_level;l++)
1.274 + {
1.275 + copy(--_first[l+1],_first[l]);
1.276 + --_last_active[l];
1.277 + }
1.278 + copy(li,_first[_max_level]);
1.279 + --_last_active[_max_level];
1.280 + _level[li]=_max_level;
1.281 +
1.282 + while(_highest_active>=0 &&
1.283 + _last_active[_highest_active]<_first[_highest_active])
1.284 + _highest_active--;
1.285 + }
1.286 +
1.287 + ///@}
1.288 +
1.289 + ///\name Active Item on Certain Level
1.290 + ///Functions for working with the active items.
1.291 +
1.292 + ///@{
1.293 +
1.294 + ///Returns an active item on level \c l.
1.295 +
1.296 + ///Returns an active item on level \c l.
1.297 + ///
1.298 + ///Returns an active item on level \c l or \ref INVALID if there is no such
1.299 + ///an item. (\c l must be from the range [0...\c max_level].
1.300 + Item activeOn(int l) const
1.301 + {
1.302 + return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
1.303 + }
1.304 +
1.305 + ///Lifts the active item returned by \c activeOn() member function.
1.306 +
1.307 + ///Lifts the active item returned by \c activeOn() member function
1.308 + ///by one.
1.309 + Item liftActiveOn(int level)
1.310 + {
1.311 + ++_level[*_last_active[level]];
1.312 + swap(_last_active[level]--, --_first[level+1]);
1.313 + if (level+1>_highest_active) ++_highest_active;
1.314 + }
1.315 +
1.316 + ///Lifts the active item returned by \c activeOn() member function.
1.317 +
1.318 + ///Lifts the active item returned by \c activeOn() member function
1.319 + ///to the given level.
1.320 + void liftActiveOn(int level, int new_level)
1.321 + {
1.322 + const Item ai = *_last_active[level];
1.323 +
1.324 + copy(--_first[level+1], _last_active[level]--);
1.325 + for(int l=level+1;l<new_level;l++)
1.326 + {
1.327 + copy(_last_active[l],_first[l]);
1.328 + copy(--_first[l+1], _last_active[l]--);
1.329 + }
1.330 + copy(ai,_first[new_level]);
1.331 + _level[ai]=new_level;
1.332 + if (new_level>_highest_active) _highest_active=new_level;
1.333 + }
1.334 +
1.335 + ///Lifts the active item returned by \c activeOn() member function.
1.336 +
1.337 + ///Lifts the active item returned by \c activeOn() member function
1.338 + ///to the top level.
1.339 + void liftActiveToTop(int level)
1.340 + {
1.341 + const Item ai = *_last_active[level];
1.342 +
1.343 + copy(--_first[level+1],_last_active[level]--);
1.344 + for(int l=level+1;l<_max_level;l++)
1.345 + {
1.346 + copy(_last_active[l],_first[l]);
1.347 + copy(--_first[l+1], _last_active[l]--);
1.348 + }
1.349 + copy(ai,_first[_max_level]);
1.350 + --_last_active[_max_level];
1.351 + _level[ai]=_max_level;
1.352 +
1.353 + if (_highest_active==level) {
1.354 + while(_highest_active>=0 &&
1.355 + _last_active[_highest_active]<_first[_highest_active])
1.356 + _highest_active--;
1.357 + }
1.358 + }
1.359 +
1.360 + ///@}
1.361 +
1.362 + ///Lift an active item to a higher level.
1.363 +
1.364 + ///Lift an active item to a higher level.
1.365 + ///\param i The item to be lifted. It must be active.
1.366 + ///\param new_level The new level of \c i. It must be strictly higher
1.367 + ///than the current level.
1.368 + ///
1.369 + void lift(Item i, int new_level)
1.370 + {
1.371 + const int lo = _level[i];
1.372 + const Vit w = _where[i];
1.373 +
1.374 + copy(_last_active[lo],w);
1.375 + copy(--_first[lo+1],_last_active[lo]--);
1.376 + for(int l=lo+1;l<new_level;l++)
1.377 + {
1.378 + copy(_last_active[l],_first[l]);
1.379 + copy(--_first[l+1],_last_active[l]--);
1.380 + }
1.381 + copy(i,_first[new_level]);
1.382 + _level[i]=new_level;
1.383 + if(new_level>_highest_active) _highest_active=new_level;
1.384 + }
1.385 +
1.386 + ///Mark the node as it did not reach the max level
1.387 +
1.388 + ///Mark the node as it did not reach the max level. It sets the
1.389 + ///level to the under the max level value. The node will be never
1.390 + ///more activated because the push operation from the maximum
1.391 + ///level is forbidden in the push-relabel algorithms. The node
1.392 + ///should be lifted previously to the top level.
1.393 + void markToBottom(Item i) {
1.394 + _level[i] = _max_level - 1;
1.395 + }
1.396 +
1.397 + ///Lift all nodes on and above a level to the top (and deactivate them).
1.398 +
1.399 + ///This function lifts all nodes on and above level \c l to \c
1.400 + ///maxLevel(), and also deactivates them.
1.401 + void liftToTop(int l)
1.402 + {
1.403 + const Vit f=_first[l];
1.404 + const Vit tl=_first[_max_level];
1.405 + for(Vit i=f;i!=tl;++i)
1.406 + _level[*i]=_max_level;
1.407 + for(int i=l;i<=_max_level;i++)
1.408 + {
1.409 + _first[i]=f;
1.410 + _last_active[i]=f-1;
1.411 + }
1.412 + for(_highest_active=l-1;
1.413 + _highest_active>=0 &&
1.414 + _last_active[_highest_active]<_first[_highest_active];
1.415 + _highest_active--) ;
1.416 + }
1.417 +
1.418 + private:
1.419 + int _init_lev;
1.420 + Vit _init_num;
1.421 +
1.422 + public:
1.423 +
1.424 + ///\name Initialization
1.425 + ///Using this function you can initialize the levels of the item.
1.426 + ///\n
1.427 + ///This initializatios is started with calling \c initStart().
1.428 + ///Then the
1.429 + ///items should be listed levels by levels statring with the lowest one
1.430 + ///(with level 0). This is done by using \c initAddItem()
1.431 + ///and \c initNewLevel(). Finally \c initFinish() must be called.
1.432 + ///The items not listed will be put on the highest level.
1.433 + ///@{
1.434 +
1.435 + ///Start the initialization process.
1.436 +
1.437 + void initStart()
1.438 + {
1.439 + _init_lev=0;
1.440 + _init_num=_items.begin();
1.441 + _first[0]=_items.begin();
1.442 + _last_active[0]=_items.begin()-1;
1.443 + Vit n=_items.begin();
1.444 + for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)
1.445 + {
1.446 + *n=i;
1.447 + _where[i]=n;
1.448 + _level[i]=_max_level;
1.449 + ++n;
1.450 + }
1.451 + }
1.452 +
1.453 + ///Add an item to the current level.
1.454 +
1.455 + void initAddItem(Item i)
1.456 + {
1.457 + swap(_where[i],_init_num);
1.458 + _level[i]=_init_lev;
1.459 + ++_init_num;
1.460 + }
1.461 +
1.462 + ///Start a new level.
1.463 +
1.464 + ///Start a new level.
1.465 + ///It shouldn't be used before the items on level 0 are listed.
1.466 + void initNewLevel()
1.467 + {
1.468 + _init_lev++;
1.469 + _first[_init_lev]=_init_num;
1.470 + _last_active[_init_lev]=_init_num-1;
1.471 + }
1.472 +
1.473 + ///Finalize the initialization process.
1.474 +
1.475 + void initFinish()
1.476 + {
1.477 + for(_init_lev++;_init_lev<=_max_level;_init_lev++)
1.478 + {
1.479 + _first[_init_lev]=_init_num;
1.480 + _last_active[_init_lev]=_init_num-1;
1.481 + }
1.482 + _first[_max_level+1]=_items.begin()+_item_num;
1.483 + _last_active[_max_level+1]=_items.begin()+_item_num-1;
1.484 + _highest_active = -1;
1.485 + }
1.486 +
1.487 + ///@}
1.488 +
1.489 + };
1.490 +
1.491 + ///Class for handling "labels" in push-relabel type algorithms.
1.492 +
1.493 + ///A class for handling "labels" in push-relabel type algorithms.
1.494 + ///
1.495 + ///\ingroup auxdat
1.496 + ///Using this class you can assign "labels" (nonnegative integer numbers)
1.497 + ///to the edges or nodes of a graph, manipulate and query them through
1.498 + ///operations typically arising in "push-relabel" type algorithms.
1.499 + ///
1.500 + ///Each item is either \em active or not, and you can also choose a
1.501 + ///highest level active item.
1.502 + ///
1.503 + ///\sa Elevator
1.504 + ///
1.505 + ///\param Graph the underlying graph type
1.506 + ///\param Item Type of the items the data is assigned to (Graph::Node,
1.507 + ///Graph::Edge, Graph::UEdge)
1.508 + template <class Graph, class Item>
1.509 + class LinkedElevator {
1.510 + public:
1.511 +
1.512 + typedef Item Key;
1.513 + typedef int Value;
1.514 +
1.515 + private:
1.516 +
1.517 + typedef typename ItemSetTraits<Graph,Item>::
1.518 + template Map<Item>::Type ItemMap;
1.519 + typedef typename ItemSetTraits<Graph,Item>::
1.520 + template Map<int>::Type IntMap;
1.521 + typedef typename ItemSetTraits<Graph,Item>::
1.522 + template Map<bool>::Type BoolMap;
1.523 +
1.524 + const Graph &_graph;
1.525 + int _max_level;
1.526 + int _item_num;
1.527 + std::vector<Item> _first, _last;
1.528 + ItemMap _prev, _next;
1.529 + int _highest_active;
1.530 + IntMap _level;
1.531 + BoolMap _active;
1.532 +
1.533 + public:
1.534 + ///Constructor with given maximum level.
1.535 +
1.536 + ///Constructor with given maximum level.
1.537 + ///
1.538 + ///\param g The underlying graph
1.539 + ///\param max_level Set the range of the possible labels to
1.540 + ///[0...\c max_level]
1.541 + LinkedElevator(const Graph& graph, int max_level)
1.542 + : _graph(graph), _max_level(max_level), _item_num(_max_level),
1.543 + _first(_max_level + 1), _last(_max_level + 1),
1.544 + _prev(graph), _next(graph),
1.545 + _highest_active(-1), _level(graph), _active(graph) {}
1.546 +
1.547 + ///Constructor.
1.548 +
1.549 + ///Constructor.
1.550 + ///
1.551 + ///\param g The underlying graph
1.552 + ///The range of the possible labels is [0...\c max_level],
1.553 + ///where \c max_level is equal to the number of labeled items in the graph.
1.554 + LinkedElevator(const Graph& graph)
1.555 + : _graph(graph), _max_level(countItems<Graph, Item>(graph)),
1.556 + _item_num(_max_level),
1.557 + _first(_max_level + 1), _last(_max_level + 1),
1.558 + _prev(graph, INVALID), _next(graph, INVALID),
1.559 + _highest_active(-1), _level(graph), _active(graph) {}
1.560 +
1.561 +
1.562 + ///Activate item \c i.
1.563 +
1.564 + ///Activate item \c i.
1.565 + ///\pre Item \c i shouldn't be active before.
1.566 + void activate(Item i) {
1.567 + _active.set(i, true);
1.568 +
1.569 + int level = _level[i];
1.570 + if (level > _highest_active) {
1.571 + _highest_active = level;
1.572 + }
1.573 +
1.574 + if (_prev[i] == INVALID || _active[_prev[i]]) return;
1.575 + //unlace
1.576 + _next.set(_prev[i], _next[i]);
1.577 + if (_next[i] != INVALID) {
1.578 + _prev.set(_next[i], _prev[i]);
1.579 + } else {
1.580 + _last[level] = _prev[i];
1.581 + }
1.582 + //lace
1.583 + _next.set(i, _first[level]);
1.584 + _prev.set(_first[level], i);
1.585 + _prev.set(i, INVALID);
1.586 + _first[level] = i;
1.587 +
1.588 + }
1.589 +
1.590 + ///Deactivate item \c i.
1.591 +
1.592 + ///Deactivate item \c i.
1.593 + ///\pre Item \c i must be active before.
1.594 + void deactivate(Item i) {
1.595 + _active.set(i, false);
1.596 + int level = _level[i];
1.597 +
1.598 + if (_next[i] == INVALID || !_active[_next[i]])
1.599 + goto find_highest_level;
1.600 +
1.601 + //unlace
1.602 + _prev.set(_next[i], _prev[i]);
1.603 + if (_prev[i] != INVALID) {
1.604 + _next.set(_prev[i], _next[i]);
1.605 + } else {
1.606 + _first[_level[i]] = _next[i];
1.607 + }
1.608 + //lace
1.609 + _prev.set(i, _last[level]);
1.610 + _next.set(_last[level], i);
1.611 + _next.set(i, INVALID);
1.612 + _last[level] = i;
1.613 +
1.614 + find_highest_level:
1.615 + if (level == _highest_active) {
1.616 + while (_highest_active >= 0 && activeFree(_highest_active))
1.617 + --_highest_active;
1.618 + }
1.619 + }
1.620 +
1.621 + ///Query whether item \c i is active
1.622 + bool active(Item i) const { return _active[i]; }
1.623 +
1.624 + ///Return the level of item \c i.
1.625 + int operator[](Item i) const { return _level[i]; }
1.626 +
1.627 + ///Return the number of items on level \c l.
1.628 + int onLevel(int l) const {
1.629 + int num = 0;
1.630 + Item n = _first[l];
1.631 + while (n != INVALID) {
1.632 + ++num;
1.633 + n = _next[n];
1.634 + }
1.635 + return num;
1.636 + }
1.637 +
1.638 + ///Return true if the level is empty.
1.639 + bool emptyLevel(int l) const {
1.640 + return _first[l] == INVALID;
1.641 + }
1.642 +
1.643 + ///Return the number of items above level \c l.
1.644 + int aboveLevel(int l) const {
1.645 + int num = 0;
1.646 + for (int level = l + 1; level < _max_level; ++level)
1.647 + num += onLevel(level);
1.648 + return num;
1.649 + }
1.650 +
1.651 + ///Return the number of active items on level \c l.
1.652 + int activesOnLevel(int l) const {
1.653 + int num = 0;
1.654 + Item n = _first[l];
1.655 + while (n != INVALID && _active[n]) {
1.656 + ++num;
1.657 + n = _next[n];
1.658 + }
1.659 + return num;
1.660 + }
1.661 +
1.662 + ///Return true if there is not active item on level \c l.
1.663 + bool activeFree(int l) const {
1.664 + return _first[l] == INVALID || !_active[_first[l]];
1.665 + }
1.666 +
1.667 + ///Return the maximum allowed level.
1.668 + int maxLevel() const {
1.669 + return _max_level;
1.670 + }
1.671 +
1.672 + ///\name Highest Active Item
1.673 + ///Functions for working with the highest level
1.674 + ///active item.
1.675 +
1.676 + ///@{
1.677 +
1.678 + ///Return a highest level active item.
1.679 +
1.680 + ///Return a highest level active item.
1.681 + ///
1.682 + ///\return the highest level active item or INVALID if there is no
1.683 + ///active item.
1.684 + Item highestActive() const {
1.685 + return _highest_active >= 0 ? _first[_highest_active] : INVALID;
1.686 + }
1.687 +
1.688 + ///Return a highest active level.
1.689 +
1.690 + ///Return a highest active level.
1.691 + ///
1.692 + ///\return the level of the highest active item or -1 if there is
1.693 + ///no active item.
1.694 + int highestActiveLevel() const {
1.695 + return _highest_active;
1.696 + }
1.697 +
1.698 + ///Lift the highest active item by one.
1.699 +
1.700 + ///Lift the item returned by highestActive() by one.
1.701 + ///
1.702 + void liftHighestActive() {
1.703 + Item i = _first[_highest_active];
1.704 + if (_next[i] != INVALID) {
1.705 + _prev.set(_next[i], INVALID);
1.706 + _first[_highest_active] = _next[i];
1.707 + } else {
1.708 + _first[_highest_active] = INVALID;
1.709 + _last[_highest_active] = INVALID;
1.710 + }
1.711 + _level.set(i, ++_highest_active);
1.712 + if (_first[_highest_active] == INVALID) {
1.713 + _first[_highest_active] = i;
1.714 + _last[_highest_active] = i;
1.715 + _prev.set(i, INVALID);
1.716 + _next.set(i, INVALID);
1.717 + } else {
1.718 + _prev.set(_first[_highest_active], i);
1.719 + _next.set(i, _first[_highest_active]);
1.720 + _first[_highest_active] = i;
1.721 + }
1.722 + }
1.723 +
1.724 + ///Lift the highest active item.
1.725 +
1.726 + ///Lift the item returned by highestActive() to level \c new_level.
1.727 + ///
1.728 + ///\warning \c new_level must be strictly higher
1.729 + ///than the current level.
1.730 + ///
1.731 + void liftHighestActive(int new_level) {
1.732 + Item i = _first[_highest_active];
1.733 + if (_next[i] != INVALID) {
1.734 + _prev.set(_next[i], INVALID);
1.735 + _first[_highest_active] = _next[i];
1.736 + } else {
1.737 + _first[_highest_active] = INVALID;
1.738 + _last[_highest_active] = INVALID;
1.739 + }
1.740 + _level.set(i, _highest_active = new_level);
1.741 + if (_first[_highest_active] == INVALID) {
1.742 + _first[_highest_active] = _last[_highest_active] = i;
1.743 + _prev.set(i, INVALID);
1.744 + _next.set(i, INVALID);
1.745 + } else {
1.746 + _prev.set(_first[_highest_active], i);
1.747 + _next.set(i, _first[_highest_active]);
1.748 + _first[_highest_active] = i;
1.749 + }
1.750 + }
1.751 +
1.752 + ///Lift the highest active to top.
1.753 +
1.754 + ///Lift the item returned by highestActive() to the top level and
1.755 + ///deactivates the node.
1.756 + ///
1.757 + void liftHighestActiveToTop() {
1.758 + Item i = _first[_highest_active];
1.759 + _level.set(i, _max_level);
1.760 + if (_next[i] != INVALID) {
1.761 + _prev.set(_next[i], INVALID);
1.762 + _first[_highest_active] = _next[i];
1.763 + } else {
1.764 + _first[_highest_active] = INVALID;
1.765 + _last[_highest_active] = INVALID;
1.766 + }
1.767 + while (_highest_active >= 0 && activeFree(_highest_active))
1.768 + --_highest_active;
1.769 + }
1.770 +
1.771 + ///@}
1.772 +
1.773 + ///\name Active Item on Certain Level
1.774 + ///Functions for working with the active items.
1.775 +
1.776 + ///@{
1.777 +
1.778 + ///Returns an active item on level \c l.
1.779 +
1.780 + ///Returns an active item on level \c l.
1.781 + ///
1.782 + ///Returns an active item on level \c l or \ref INVALID if there is no such
1.783 + ///an item. (\c l must be from the range [0...\c max_level].
1.784 + Item activeOn(int l) const
1.785 + {
1.786 + return _active[_first[l]] ? _first[l] : INVALID;
1.787 + }
1.788 +
1.789 + ///Lifts the active item returned by \c activeOn() member function.
1.790 +
1.791 + ///Lifts the active item returned by \c activeOn() member function
1.792 + ///by one.
1.793 + Item liftActiveOn(int l)
1.794 + {
1.795 + Item i = _first[l];
1.796 + if (_next[i] != INVALID) {
1.797 + _prev.set(_next[i], INVALID);
1.798 + _first[l] = _next[i];
1.799 + } else {
1.800 + _first[l] = INVALID;
1.801 + _last[l] = INVALID;
1.802 + }
1.803 + _level.set(i, ++l);
1.804 + if (_first[l] == INVALID) {
1.805 + _first[l] = _last[l] = i;
1.806 + _prev.set(i, INVALID);
1.807 + _next.set(i, INVALID);
1.808 + } else {
1.809 + _prev.set(_first[l], i);
1.810 + _next.set(i, _first[l]);
1.811 + _first[l] = i;
1.812 + }
1.813 + if (_highest_active < l) {
1.814 + _highest_active = l;
1.815 + }
1.816 + }
1.817 +
1.818 + /// \brief Lifts the active item returned by \c activeOn() member function.
1.819 + ///
1.820 + /// Lifts the active item returned by \c activeOn() member function
1.821 + /// to the given level.
1.822 + void liftActiveOn(int l, int new_level)
1.823 + {
1.824 + Item i = _first[l];
1.825 + if (_next[i] != INVALID) {
1.826 + _prev.set(_next[i], INVALID);
1.827 + _first[l] = _next[i];
1.828 + } else {
1.829 + _first[l] = INVALID;
1.830 + _last[l] = INVALID;
1.831 + }
1.832 + _level.set(i, l = new_level);
1.833 + if (_first[l] == INVALID) {
1.834 + _first[l] = _last[l] = i;
1.835 + _prev.set(i, INVALID);
1.836 + _next.set(i, INVALID);
1.837 + } else {
1.838 + _prev.set(_first[l], i);
1.839 + _next.set(i, _first[l]);
1.840 + _first[l] = i;
1.841 + }
1.842 + if (_highest_active < l) {
1.843 + _highest_active = l;
1.844 + }
1.845 + }
1.846 +
1.847 + ///Lifts the active item returned by \c activeOn() member function.
1.848 +
1.849 + ///Lifts the active item returned by \c activeOn() member function
1.850 + ///to the top level.
1.851 + void liftActiveToTop(int l)
1.852 + {
1.853 + Item i = _first[l];
1.854 + if (_next[i] != INVALID) {
1.855 + _prev.set(_next[i], INVALID);
1.856 + _first[l] = _next[i];
1.857 + } else {
1.858 + _first[l] = INVALID;
1.859 + _last[l] = INVALID;
1.860 + }
1.861 + _level.set(i, _max_level);
1.862 + if (l == _highest_active) {
1.863 + while (_highest_active >= 0 && activeFree(_highest_active))
1.864 + --_highest_active;
1.865 + }
1.866 + }
1.867 +
1.868 + ///@}
1.869 +
1.870 + /// \brief Lift an active item to a higher level.
1.871 + ///
1.872 + /// Lift an active item to a higher level.
1.873 + /// \param i The item to be lifted. It must be active.
1.874 + /// \param new_level The new level of \c i. It must be strictly higher
1.875 + /// than the current level.
1.876 + ///
1.877 + void lift(Item i, int new_level) {
1.878 + if (_next[i] != INVALID) {
1.879 + _prev.set(_next[i], _prev[i]);
1.880 + } else {
1.881 + _last[new_level] = _prev[i];
1.882 + }
1.883 + if (_prev[i] != INVALID) {
1.884 + _next.set(_prev[i], _next[i]);
1.885 + } else {
1.886 + _first[new_level] = _next[i];
1.887 + }
1.888 + _level.set(i, new_level);
1.889 + if (_first[new_level] == INVALID) {
1.890 + _first[new_level] = _last[new_level] = i;
1.891 + _prev.set(i, INVALID);
1.892 + _next.set(i, INVALID);
1.893 + } else {
1.894 + _prev.set(_first[new_level], i);
1.895 + _next.set(i, _first[new_level]);
1.896 + _first[new_level] = i;
1.897 + }
1.898 + if (_highest_active < new_level) {
1.899 + _highest_active = new_level;
1.900 + }
1.901 + }
1.902 +
1.903 + ///Mark the node as it did not reach the max level
1.904 +
1.905 + ///Mark the node as it did not reach the max level. It sets the
1.906 + ///level to the under the max level value. The node will be never
1.907 + ///more activated because the push operation from the maximum
1.908 + ///level is forbidden in the push-relabel algorithms. The node
1.909 + ///should be lifted previously to the top level.
1.910 + void markToBottom(Item i) {
1.911 + _level.set(i, _max_level - 1);
1.912 + }
1.913 +
1.914 + ///Lift all nodes on and above a level to the top (and deactivate them).
1.915 +
1.916 + ///This function lifts all nodes on and above level \c l to \c
1.917 + ///maxLevel(), and also deactivates them.
1.918 + void liftToTop(int l) {
1.919 + for (int i = l + 1; _first[i] != INVALID; ++i) {
1.920 + Item n = _first[i];
1.921 + while (n != INVALID) {
1.922 + _level.set(n, _max_level);
1.923 + n = _next[n];
1.924 + }
1.925 + _first[i] = INVALID;
1.926 + _last[i] = INVALID;
1.927 + }
1.928 + if (_highest_active > l - 1) {
1.929 + _highest_active = l - 1;
1.930 + while (_highest_active >= 0 && activeFree(_highest_active))
1.931 + --_highest_active;
1.932 + }
1.933 + }
1.934 +
1.935 + private:
1.936 +
1.937 + int _init_level;
1.938 +
1.939 + public:
1.940 +
1.941 + ///\name Initialization
1.942 + ///Using this function you can initialize the levels of the item.
1.943 + ///\n
1.944 + ///This initializatios is started with calling \c initStart().
1.945 + ///Then the
1.946 + ///items should be listed levels by levels statring with the lowest one
1.947 + ///(with level 0). This is done by using \c initAddItem()
1.948 + ///and \c initNewLevel(). Finally \c initFinish() must be called.
1.949 + ///The items not listed will be put on the highest level.
1.950 + ///@{
1.951 +
1.952 + ///Start the initialization process.
1.953 +
1.954 + void initStart() {
1.955 +
1.956 + for (int i = 0; i <= _max_level; ++i) {
1.957 + _first[i] = _last[i] = INVALID;
1.958 + }
1.959 + _init_level = 0;
1.960 + for(typename ItemSetTraits<Graph,Item>::ItemIt i(_graph);
1.961 + i != INVALID; ++i) {
1.962 + _level.set(i, _max_level);
1.963 + _active.set(i, false);
1.964 + }
1.965 + }
1.966 +
1.967 + ///Add an item to the current level.
1.968 +
1.969 + void initAddItem(Item i) {
1.970 + _level.set(i, _init_level);
1.971 + if (_last[_init_level] == INVALID) {
1.972 + _first[_init_level] = i;
1.973 + _last[_init_level] = i;
1.974 + _prev.set(i, INVALID);
1.975 + _next.set(i, INVALID);
1.976 + } else {
1.977 + _prev.set(i, _last[_init_level]);
1.978 + _next.set(i, INVALID);
1.979 + _next.set(_last[_init_level], i);
1.980 + _last[_init_level] = i;
1.981 + }
1.982 + }
1.983 +
1.984 + ///Start a new level.
1.985 +
1.986 + ///Start a new level.
1.987 + ///It shouldn't be used before the items on level 0 are listed.
1.988 + void initNewLevel() {
1.989 + ++_init_level;
1.990 + }
1.991 +
1.992 + ///Finalize the initialization process.
1.993 +
1.994 + void initFinish() {
1.995 + _highest_active = -1;
1.996 + }
1.997 +
1.998 + ///@}
1.999 +
1.1000 + };
1.1001 +
1.1002 +
1.1003 +} //END OF NAMESPACE LEMON
1.1004 +
1.1005 +#endif
1.1006 +