1.1 --- a/lemon/Makefile.am Tue Nov 04 10:25:47 2008 +0000
1.2 +++ b/lemon/Makefile.am Mon Nov 17 15:41:15 2008 +0000
1.3 @@ -27,6 +27,7 @@
1.4 lemon/dfs.h \
1.5 lemon/dijkstra.h \
1.6 lemon/dim2.h \
1.7 + lemon/elevator.h \
1.8 lemon/error.h \
1.9 lemon/full_graph.h \
1.10 lemon/graph_to_eps.h \
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/elevator.h Mon Nov 17 15:41:15 2008 +0000
2.3 @@ -0,0 +1,1003 @@
2.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
2.5 + *
2.6 + * This file is a part of LEMON, a generic C++ optimization library.
2.7 + *
2.8 + * Copyright (C) 2003-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_ELEVATOR_H
2.23 +#define LEMON_ELEVATOR_H
2.24 +
2.25 +///\ingroup auxdat
2.26 +///\file
2.27 +///\brief Elevator class
2.28 +///
2.29 +///Elevator class implements an efficient data structure
2.30 +///for labeling items in push-relabel type algorithms.
2.31 +///
2.32 +
2.33 +#include <test/test_tools.h>
2.34 +namespace lemon {
2.35 +
2.36 + ///Class for handling "labels" in push-relabel type algorithms.
2.37 +
2.38 + ///A class for handling "labels" in push-relabel type algorithms.
2.39 + ///
2.40 + ///\ingroup auxdat
2.41 + ///Using this class you can assign "labels" (nonnegative integer numbers)
2.42 + ///to the edges or nodes of a graph, manipulate and query them through
2.43 + ///operations typically arising in "push-relabel" type algorithms.
2.44 + ///
2.45 + ///Each item is either \em active or not, and you can also choose a
2.46 + ///highest level active item.
2.47 + ///
2.48 + ///\sa LinkedElevator
2.49 + ///
2.50 + ///\param Graph the underlying graph type
2.51 + ///\param Item Type of the items the data is assigned to (Graph::Node,
2.52 + ///Graph::Edge, Graph::UEdge)
2.53 + template<class Graph, class Item>
2.54 + class Elevator
2.55 + {
2.56 + public:
2.57 +
2.58 + typedef Item Key;
2.59 + typedef int Value;
2.60 +
2.61 + private:
2.62 +
2.63 + typedef typename std::vector<Item>::iterator Vit;
2.64 + typedef typename ItemSetTraits<Graph,Item>::template Map<Vit>::Type VitMap;
2.65 + typedef typename ItemSetTraits<Graph,Item>::template Map<int>::Type IntMap;
2.66 +
2.67 + const Graph &_g;
2.68 + int _max_level;
2.69 + int _item_num;
2.70 + VitMap _where;
2.71 + IntMap _level;
2.72 + std::vector<Item> _items;
2.73 + std::vector<Vit> _first;
2.74 + std::vector<Vit> _last_active;
2.75 +
2.76 + int _highest_active;
2.77 +
2.78 + void copy(Item i, Vit p)
2.79 + {
2.80 + _where[*p=i]=p;
2.81 + }
2.82 + void copy(Vit s, Vit p)
2.83 + {
2.84 + if(s!=p)
2.85 + {
2.86 + Item i=*s;
2.87 + *p=i;
2.88 + _where[i]=p;
2.89 + }
2.90 + }
2.91 + void swap(Vit i, Vit j)
2.92 + {
2.93 + Item ti=*i;
2.94 + Vit ct = _where[ti];
2.95 + _where[ti]=_where[*i=*j];
2.96 + _where[*j]=ct;
2.97 + *j=ti;
2.98 + }
2.99 +
2.100 + public:
2.101 +
2.102 + ///Constructor with given maximum level.
2.103 +
2.104 + ///Constructor with given maximum level.
2.105 + ///
2.106 + ///\param g The underlying graph
2.107 + ///\param max_level Set the range of the possible labels to
2.108 + ///[0...\c max_level]
2.109 + Elevator(const Graph &g,int max_level) :
2.110 + _g(g),
2.111 + _max_level(max_level),
2.112 + _item_num(_max_level),
2.113 + _where(g),
2.114 + _level(g,0),
2.115 + _items(_max_level),
2.116 + _first(_max_level+2),
2.117 + _last_active(_max_level+2),
2.118 + _highest_active(-1) {}
2.119 + ///Constructor.
2.120 +
2.121 + ///Constructor.
2.122 + ///
2.123 + ///\param g The underlying graph
2.124 + ///The range of the possible labels is [0...\c max_level],
2.125 + ///where \c max_level is equal to the number of labeled items in the graph.
2.126 + Elevator(const Graph &g) :
2.127 + _g(g),
2.128 + _max_level(countItems<Graph, Item>(g)),
2.129 + _item_num(_max_level),
2.130 + _where(g),
2.131 + _level(g,0),
2.132 + _items(_max_level),
2.133 + _first(_max_level+2),
2.134 + _last_active(_max_level+2),
2.135 + _highest_active(-1)
2.136 + {
2.137 + }
2.138 +
2.139 + ///Activate item \c i.
2.140 +
2.141 + ///Activate item \c i.
2.142 + ///\pre Item \c i shouldn't be active before.
2.143 + void activate(Item i)
2.144 + {
2.145 + const int l=_level[i];
2.146 + swap(_where[i],++_last_active[l]);
2.147 + if(l>_highest_active) _highest_active=l;
2.148 + }
2.149 +
2.150 + ///Deactivate item \c i.
2.151 +
2.152 + ///Deactivate item \c i.
2.153 + ///\pre Item \c i must be active before.
2.154 + void deactivate(Item i)
2.155 + {
2.156 + swap(_where[i],_last_active[_level[i]]--);
2.157 + while(_highest_active>=0 &&
2.158 + _last_active[_highest_active]<_first[_highest_active])
2.159 + _highest_active--;
2.160 + }
2.161 +
2.162 + ///Query whether item \c i is active
2.163 + bool active(Item i) const { return _where[i]<=_last_active[_level[i]]; }
2.164 +
2.165 + ///Return the level of item \c i.
2.166 + int operator[](Item i) const { return _level[i]; }
2.167 +
2.168 + ///Return the number of items on level \c l.
2.169 + int onLevel(int l) const
2.170 + {
2.171 + return _first[l+1]-_first[l];
2.172 + }
2.173 + ///Return true if the level is empty.
2.174 + bool emptyLevel(int l) const
2.175 + {
2.176 + return _first[l+1]-_first[l]==0;
2.177 + }
2.178 + ///Return the number of items above level \c l.
2.179 + int aboveLevel(int l) const
2.180 + {
2.181 + return _first[_max_level+1]-_first[l+1];
2.182 + }
2.183 + ///Return the number of active items on level \c l.
2.184 + int activesOnLevel(int l) const
2.185 + {
2.186 + return _last_active[l]-_first[l]+1;
2.187 + }
2.188 + ///Return true if there is not active item on level \c l.
2.189 + bool activeFree(int l) const
2.190 + {
2.191 + return _last_active[l]<_first[l];
2.192 + }
2.193 + ///Return the maximum allowed level.
2.194 + int maxLevel() const
2.195 + {
2.196 + return _max_level;
2.197 + }
2.198 +
2.199 + ///\name Highest Active Item
2.200 + ///Functions for working with the highest level
2.201 + ///active item.
2.202 +
2.203 + ///@{
2.204 +
2.205 + ///Return a highest level active item.
2.206 +
2.207 + ///Return a highest level active item.
2.208 + ///
2.209 + ///\return the highest level active item or INVALID if there is no active
2.210 + ///item.
2.211 + Item highestActive() const
2.212 + {
2.213 + return _highest_active>=0?*_last_active[_highest_active]:INVALID;
2.214 + }
2.215 +
2.216 + ///Return a highest active level.
2.217 +
2.218 + ///Return a highest active level.
2.219 + ///
2.220 + ///\return the level of the highest active item or -1 if there is no active
2.221 + ///item.
2.222 + int highestActiveLevel() const
2.223 + {
2.224 + return _highest_active;
2.225 + }
2.226 +
2.227 + ///Lift the highest active item by one.
2.228 +
2.229 + ///Lift the item returned by highestActive() by one.
2.230 + ///
2.231 + void liftHighestActive()
2.232 + {
2.233 + ++_level[*_last_active[_highest_active]];
2.234 + swap(_last_active[_highest_active]--,_last_active[_highest_active+1]);
2.235 + --_first[++_highest_active];
2.236 + }
2.237 +
2.238 + ///Lift the highest active item.
2.239 +
2.240 + ///Lift the item returned by highestActive() to level \c new_level.
2.241 + ///
2.242 + ///\warning \c new_level must be strictly higher
2.243 + ///than the current level.
2.244 + ///
2.245 + void liftHighestActive(int new_level)
2.246 + {
2.247 + const Item li = *_last_active[_highest_active];
2.248 +
2.249 + copy(--_first[_highest_active+1],_last_active[_highest_active]--);
2.250 + for(int l=_highest_active+1;l<new_level;l++)
2.251 + {
2.252 + copy(--_first[l+1],_first[l]);
2.253 + --_last_active[l];
2.254 + }
2.255 + copy(li,_first[new_level]);
2.256 + _level[li]=new_level;
2.257 + _highest_active=new_level;
2.258 + }
2.259 +
2.260 + ///Lift the highest active item.
2.261 +
2.262 + ///Lift the item returned by highestActive() to the top level and
2.263 + ///deactivates it.
2.264 + ///
2.265 + ///\warning \c new_level must be strictly higher
2.266 + ///than the current level.
2.267 + ///
2.268 + void liftHighestActiveToTop()
2.269 + {
2.270 + const Item li = *_last_active[_highest_active];
2.271 +
2.272 + copy(--_first[_highest_active+1],_last_active[_highest_active]--);
2.273 + for(int l=_highest_active+1;l<_max_level;l++)
2.274 + {
2.275 + copy(--_first[l+1],_first[l]);
2.276 + --_last_active[l];
2.277 + }
2.278 + copy(li,_first[_max_level]);
2.279 + --_last_active[_max_level];
2.280 + _level[li]=_max_level;
2.281 +
2.282 + while(_highest_active>=0 &&
2.283 + _last_active[_highest_active]<_first[_highest_active])
2.284 + _highest_active--;
2.285 + }
2.286 +
2.287 + ///@}
2.288 +
2.289 + ///\name Active Item on Certain Level
2.290 + ///Functions for working with the active items.
2.291 +
2.292 + ///@{
2.293 +
2.294 + ///Returns an active item on level \c l.
2.295 +
2.296 + ///Returns an active item on level \c l.
2.297 + ///
2.298 + ///Returns an active item on level \c l or \ref INVALID if there is no such
2.299 + ///an item. (\c l must be from the range [0...\c max_level].
2.300 + Item activeOn(int l) const
2.301 + {
2.302 + return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
2.303 + }
2.304 +
2.305 + ///Lifts the active item returned by \c activeOn() member function.
2.306 +
2.307 + ///Lifts the active item returned by \c activeOn() member function
2.308 + ///by one.
2.309 + Item liftActiveOn(int level)
2.310 + {
2.311 + ++_level[*_last_active[level]];
2.312 + swap(_last_active[level]--, --_first[level+1]);
2.313 + if (level+1>_highest_active) ++_highest_active;
2.314 + }
2.315 +
2.316 + ///Lifts the active item returned by \c activeOn() member function.
2.317 +
2.318 + ///Lifts the active item returned by \c activeOn() member function
2.319 + ///to the given level.
2.320 + void liftActiveOn(int level, int new_level)
2.321 + {
2.322 + const Item ai = *_last_active[level];
2.323 +
2.324 + copy(--_first[level+1], _last_active[level]--);
2.325 + for(int l=level+1;l<new_level;l++)
2.326 + {
2.327 + copy(_last_active[l],_first[l]);
2.328 + copy(--_first[l+1], _last_active[l]--);
2.329 + }
2.330 + copy(ai,_first[new_level]);
2.331 + _level[ai]=new_level;
2.332 + if (new_level>_highest_active) _highest_active=new_level;
2.333 + }
2.334 +
2.335 + ///Lifts the active item returned by \c activeOn() member function.
2.336 +
2.337 + ///Lifts the active item returned by \c activeOn() member function
2.338 + ///to the top level.
2.339 + void liftActiveToTop(int level)
2.340 + {
2.341 + const Item ai = *_last_active[level];
2.342 +
2.343 + copy(--_first[level+1],_last_active[level]--);
2.344 + for(int l=level+1;l<_max_level;l++)
2.345 + {
2.346 + copy(_last_active[l],_first[l]);
2.347 + copy(--_first[l+1], _last_active[l]--);
2.348 + }
2.349 + copy(ai,_first[_max_level]);
2.350 + --_last_active[_max_level];
2.351 + _level[ai]=_max_level;
2.352 +
2.353 + if (_highest_active==level) {
2.354 + while(_highest_active>=0 &&
2.355 + _last_active[_highest_active]<_first[_highest_active])
2.356 + _highest_active--;
2.357 + }
2.358 + }
2.359 +
2.360 + ///@}
2.361 +
2.362 + ///Lift an active item to a higher level.
2.363 +
2.364 + ///Lift an active item to a higher level.
2.365 + ///\param i The item to be lifted. It must be active.
2.366 + ///\param new_level The new level of \c i. It must be strictly higher
2.367 + ///than the current level.
2.368 + ///
2.369 + void lift(Item i, int new_level)
2.370 + {
2.371 + const int lo = _level[i];
2.372 + const Vit w = _where[i];
2.373 +
2.374 + copy(_last_active[lo],w);
2.375 + copy(--_first[lo+1],_last_active[lo]--);
2.376 + for(int l=lo+1;l<new_level;l++)
2.377 + {
2.378 + copy(_last_active[l],_first[l]);
2.379 + copy(--_first[l+1],_last_active[l]--);
2.380 + }
2.381 + copy(i,_first[new_level]);
2.382 + _level[i]=new_level;
2.383 + if(new_level>_highest_active) _highest_active=new_level;
2.384 + }
2.385 +
2.386 + ///Mark the node as it did not reach the max level
2.387 +
2.388 + ///Mark the node as it did not reach the max level. It sets the
2.389 + ///level to the under the max level value. The node will be never
2.390 + ///more activated because the push operation from the maximum
2.391 + ///level is forbidden in the push-relabel algorithms. The node
2.392 + ///should be lifted previously to the top level.
2.393 + void markToBottom(Item i) {
2.394 + _level[i] = _max_level - 1;
2.395 + }
2.396 +
2.397 + ///Lift all nodes on and above a level to the top (and deactivate them).
2.398 +
2.399 + ///This function lifts all nodes on and above level \c l to \c
2.400 + ///maxLevel(), and also deactivates them.
2.401 + void liftToTop(int l)
2.402 + {
2.403 + const Vit f=_first[l];
2.404 + const Vit tl=_first[_max_level];
2.405 + for(Vit i=f;i!=tl;++i)
2.406 + _level[*i]=_max_level;
2.407 + for(int i=l;i<=_max_level;i++)
2.408 + {
2.409 + _first[i]=f;
2.410 + _last_active[i]=f-1;
2.411 + }
2.412 + for(_highest_active=l-1;
2.413 + _highest_active>=0 &&
2.414 + _last_active[_highest_active]<_first[_highest_active];
2.415 + _highest_active--) ;
2.416 + }
2.417 +
2.418 + private:
2.419 + int _init_lev;
2.420 + Vit _init_num;
2.421 +
2.422 + public:
2.423 +
2.424 + ///\name Initialization
2.425 + ///Using this function you can initialize the levels of the item.
2.426 + ///\n
2.427 + ///This initializatios is started with calling \c initStart().
2.428 + ///Then the
2.429 + ///items should be listed levels by levels statring with the lowest one
2.430 + ///(with level 0). This is done by using \c initAddItem()
2.431 + ///and \c initNewLevel(). Finally \c initFinish() must be called.
2.432 + ///The items not listed will be put on the highest level.
2.433 + ///@{
2.434 +
2.435 + ///Start the initialization process.
2.436 +
2.437 + void initStart()
2.438 + {
2.439 + _init_lev=0;
2.440 + _init_num=_items.begin();
2.441 + _first[0]=_items.begin();
2.442 + _last_active[0]=_items.begin()-1;
2.443 + Vit n=_items.begin();
2.444 + for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)
2.445 + {
2.446 + *n=i;
2.447 + _where[i]=n;
2.448 + _level[i]=_max_level;
2.449 + ++n;
2.450 + }
2.451 + }
2.452 +
2.453 + ///Add an item to the current level.
2.454 +
2.455 + void initAddItem(Item i)
2.456 + {
2.457 + swap(_where[i],_init_num);
2.458 + _level[i]=_init_lev;
2.459 + ++_init_num;
2.460 + }
2.461 +
2.462 + ///Start a new level.
2.463 +
2.464 + ///Start a new level.
2.465 + ///It shouldn't be used before the items on level 0 are listed.
2.466 + void initNewLevel()
2.467 + {
2.468 + _init_lev++;
2.469 + _first[_init_lev]=_init_num;
2.470 + _last_active[_init_lev]=_init_num-1;
2.471 + }
2.472 +
2.473 + ///Finalize the initialization process.
2.474 +
2.475 + void initFinish()
2.476 + {
2.477 + for(_init_lev++;_init_lev<=_max_level;_init_lev++)
2.478 + {
2.479 + _first[_init_lev]=_init_num;
2.480 + _last_active[_init_lev]=_init_num-1;
2.481 + }
2.482 + _first[_max_level+1]=_items.begin()+_item_num;
2.483 + _last_active[_max_level+1]=_items.begin()+_item_num-1;
2.484 + _highest_active = -1;
2.485 + }
2.486 +
2.487 + ///@}
2.488 +
2.489 + };
2.490 +
2.491 + ///Class for handling "labels" in push-relabel type algorithms.
2.492 +
2.493 + ///A class for handling "labels" in push-relabel type algorithms.
2.494 + ///
2.495 + ///\ingroup auxdat
2.496 + ///Using this class you can assign "labels" (nonnegative integer numbers)
2.497 + ///to the edges or nodes of a graph, manipulate and query them through
2.498 + ///operations typically arising in "push-relabel" type algorithms.
2.499 + ///
2.500 + ///Each item is either \em active or not, and you can also choose a
2.501 + ///highest level active item.
2.502 + ///
2.503 + ///\sa Elevator
2.504 + ///
2.505 + ///\param Graph the underlying graph type
2.506 + ///\param Item Type of the items the data is assigned to (Graph::Node,
2.507 + ///Graph::Edge, Graph::UEdge)
2.508 + template <class Graph, class Item>
2.509 + class LinkedElevator {
2.510 + public:
2.511 +
2.512 + typedef Item Key;
2.513 + typedef int Value;
2.514 +
2.515 + private:
2.516 +
2.517 + typedef typename ItemSetTraits<Graph,Item>::
2.518 + template Map<Item>::Type ItemMap;
2.519 + typedef typename ItemSetTraits<Graph,Item>::
2.520 + template Map<int>::Type IntMap;
2.521 + typedef typename ItemSetTraits<Graph,Item>::
2.522 + template Map<bool>::Type BoolMap;
2.523 +
2.524 + const Graph &_graph;
2.525 + int _max_level;
2.526 + int _item_num;
2.527 + std::vector<Item> _first, _last;
2.528 + ItemMap _prev, _next;
2.529 + int _highest_active;
2.530 + IntMap _level;
2.531 + BoolMap _active;
2.532 +
2.533 + public:
2.534 + ///Constructor with given maximum level.
2.535 +
2.536 + ///Constructor with given maximum level.
2.537 + ///
2.538 + ///\param g The underlying graph
2.539 + ///\param max_level Set the range of the possible labels to
2.540 + ///[0...\c max_level]
2.541 + LinkedElevator(const Graph& graph, int max_level)
2.542 + : _graph(graph), _max_level(max_level), _item_num(_max_level),
2.543 + _first(_max_level + 1), _last(_max_level + 1),
2.544 + _prev(graph), _next(graph),
2.545 + _highest_active(-1), _level(graph), _active(graph) {}
2.546 +
2.547 + ///Constructor.
2.548 +
2.549 + ///Constructor.
2.550 + ///
2.551 + ///\param g The underlying graph
2.552 + ///The range of the possible labels is [0...\c max_level],
2.553 + ///where \c max_level is equal to the number of labeled items in the graph.
2.554 + LinkedElevator(const Graph& graph)
2.555 + : _graph(graph), _max_level(countItems<Graph, Item>(graph)),
2.556 + _item_num(_max_level),
2.557 + _first(_max_level + 1), _last(_max_level + 1),
2.558 + _prev(graph, INVALID), _next(graph, INVALID),
2.559 + _highest_active(-1), _level(graph), _active(graph) {}
2.560 +
2.561 +
2.562 + ///Activate item \c i.
2.563 +
2.564 + ///Activate item \c i.
2.565 + ///\pre Item \c i shouldn't be active before.
2.566 + void activate(Item i) {
2.567 + _active.set(i, true);
2.568 +
2.569 + int level = _level[i];
2.570 + if (level > _highest_active) {
2.571 + _highest_active = level;
2.572 + }
2.573 +
2.574 + if (_prev[i] == INVALID || _active[_prev[i]]) return;
2.575 + //unlace
2.576 + _next.set(_prev[i], _next[i]);
2.577 + if (_next[i] != INVALID) {
2.578 + _prev.set(_next[i], _prev[i]);
2.579 + } else {
2.580 + _last[level] = _prev[i];
2.581 + }
2.582 + //lace
2.583 + _next.set(i, _first[level]);
2.584 + _prev.set(_first[level], i);
2.585 + _prev.set(i, INVALID);
2.586 + _first[level] = i;
2.587 +
2.588 + }
2.589 +
2.590 + ///Deactivate item \c i.
2.591 +
2.592 + ///Deactivate item \c i.
2.593 + ///\pre Item \c i must be active before.
2.594 + void deactivate(Item i) {
2.595 + _active.set(i, false);
2.596 + int level = _level[i];
2.597 +
2.598 + if (_next[i] == INVALID || !_active[_next[i]])
2.599 + goto find_highest_level;
2.600 +
2.601 + //unlace
2.602 + _prev.set(_next[i], _prev[i]);
2.603 + if (_prev[i] != INVALID) {
2.604 + _next.set(_prev[i], _next[i]);
2.605 + } else {
2.606 + _first[_level[i]] = _next[i];
2.607 + }
2.608 + //lace
2.609 + _prev.set(i, _last[level]);
2.610 + _next.set(_last[level], i);
2.611 + _next.set(i, INVALID);
2.612 + _last[level] = i;
2.613 +
2.614 + find_highest_level:
2.615 + if (level == _highest_active) {
2.616 + while (_highest_active >= 0 && activeFree(_highest_active))
2.617 + --_highest_active;
2.618 + }
2.619 + }
2.620 +
2.621 + ///Query whether item \c i is active
2.622 + bool active(Item i) const { return _active[i]; }
2.623 +
2.624 + ///Return the level of item \c i.
2.625 + int operator[](Item i) const { return _level[i]; }
2.626 +
2.627 + ///Return the number of items on level \c l.
2.628 + int onLevel(int l) const {
2.629 + int num = 0;
2.630 + Item n = _first[l];
2.631 + while (n != INVALID) {
2.632 + ++num;
2.633 + n = _next[n];
2.634 + }
2.635 + return num;
2.636 + }
2.637 +
2.638 + ///Return true if the level is empty.
2.639 + bool emptyLevel(int l) const {
2.640 + return _first[l] == INVALID;
2.641 + }
2.642 +
2.643 + ///Return the number of items above level \c l.
2.644 + int aboveLevel(int l) const {
2.645 + int num = 0;
2.646 + for (int level = l + 1; level < _max_level; ++level)
2.647 + num += onLevel(level);
2.648 + return num;
2.649 + }
2.650 +
2.651 + ///Return the number of active items on level \c l.
2.652 + int activesOnLevel(int l) const {
2.653 + int num = 0;
2.654 + Item n = _first[l];
2.655 + while (n != INVALID && _active[n]) {
2.656 + ++num;
2.657 + n = _next[n];
2.658 + }
2.659 + return num;
2.660 + }
2.661 +
2.662 + ///Return true if there is not active item on level \c l.
2.663 + bool activeFree(int l) const {
2.664 + return _first[l] == INVALID || !_active[_first[l]];
2.665 + }
2.666 +
2.667 + ///Return the maximum allowed level.
2.668 + int maxLevel() const {
2.669 + return _max_level;
2.670 + }
2.671 +
2.672 + ///\name Highest Active Item
2.673 + ///Functions for working with the highest level
2.674 + ///active item.
2.675 +
2.676 + ///@{
2.677 +
2.678 + ///Return a highest level active item.
2.679 +
2.680 + ///Return a highest level active item.
2.681 + ///
2.682 + ///\return the highest level active item or INVALID if there is no
2.683 + ///active item.
2.684 + Item highestActive() const {
2.685 + return _highest_active >= 0 ? _first[_highest_active] : INVALID;
2.686 + }
2.687 +
2.688 + ///Return a highest active level.
2.689 +
2.690 + ///Return a highest active level.
2.691 + ///
2.692 + ///\return the level of the highest active item or -1 if there is
2.693 + ///no active item.
2.694 + int highestActiveLevel() const {
2.695 + return _highest_active;
2.696 + }
2.697 +
2.698 + ///Lift the highest active item by one.
2.699 +
2.700 + ///Lift the item returned by highestActive() by one.
2.701 + ///
2.702 + void liftHighestActive() {
2.703 + Item i = _first[_highest_active];
2.704 + if (_next[i] != INVALID) {
2.705 + _prev.set(_next[i], INVALID);
2.706 + _first[_highest_active] = _next[i];
2.707 + } else {
2.708 + _first[_highest_active] = INVALID;
2.709 + _last[_highest_active] = INVALID;
2.710 + }
2.711 + _level.set(i, ++_highest_active);
2.712 + if (_first[_highest_active] == INVALID) {
2.713 + _first[_highest_active] = i;
2.714 + _last[_highest_active] = i;
2.715 + _prev.set(i, INVALID);
2.716 + _next.set(i, INVALID);
2.717 + } else {
2.718 + _prev.set(_first[_highest_active], i);
2.719 + _next.set(i, _first[_highest_active]);
2.720 + _first[_highest_active] = i;
2.721 + }
2.722 + }
2.723 +
2.724 + ///Lift the highest active item.
2.725 +
2.726 + ///Lift the item returned by highestActive() to level \c new_level.
2.727 + ///
2.728 + ///\warning \c new_level must be strictly higher
2.729 + ///than the current level.
2.730 + ///
2.731 + void liftHighestActive(int new_level) {
2.732 + Item i = _first[_highest_active];
2.733 + if (_next[i] != INVALID) {
2.734 + _prev.set(_next[i], INVALID);
2.735 + _first[_highest_active] = _next[i];
2.736 + } else {
2.737 + _first[_highest_active] = INVALID;
2.738 + _last[_highest_active] = INVALID;
2.739 + }
2.740 + _level.set(i, _highest_active = new_level);
2.741 + if (_first[_highest_active] == INVALID) {
2.742 + _first[_highest_active] = _last[_highest_active] = i;
2.743 + _prev.set(i, INVALID);
2.744 + _next.set(i, INVALID);
2.745 + } else {
2.746 + _prev.set(_first[_highest_active], i);
2.747 + _next.set(i, _first[_highest_active]);
2.748 + _first[_highest_active] = i;
2.749 + }
2.750 + }
2.751 +
2.752 + ///Lift the highest active to top.
2.753 +
2.754 + ///Lift the item returned by highestActive() to the top level and
2.755 + ///deactivates the node.
2.756 + ///
2.757 + void liftHighestActiveToTop() {
2.758 + Item i = _first[_highest_active];
2.759 + _level.set(i, _max_level);
2.760 + if (_next[i] != INVALID) {
2.761 + _prev.set(_next[i], INVALID);
2.762 + _first[_highest_active] = _next[i];
2.763 + } else {
2.764 + _first[_highest_active] = INVALID;
2.765 + _last[_highest_active] = INVALID;
2.766 + }
2.767 + while (_highest_active >= 0 && activeFree(_highest_active))
2.768 + --_highest_active;
2.769 + }
2.770 +
2.771 + ///@}
2.772 +
2.773 + ///\name Active Item on Certain Level
2.774 + ///Functions for working with the active items.
2.775 +
2.776 + ///@{
2.777 +
2.778 + ///Returns an active item on level \c l.
2.779 +
2.780 + ///Returns an active item on level \c l.
2.781 + ///
2.782 + ///Returns an active item on level \c l or \ref INVALID if there is no such
2.783 + ///an item. (\c l must be from the range [0...\c max_level].
2.784 + Item activeOn(int l) const
2.785 + {
2.786 + return _active[_first[l]] ? _first[l] : INVALID;
2.787 + }
2.788 +
2.789 + ///Lifts the active item returned by \c activeOn() member function.
2.790 +
2.791 + ///Lifts the active item returned by \c activeOn() member function
2.792 + ///by one.
2.793 + Item liftActiveOn(int l)
2.794 + {
2.795 + Item i = _first[l];
2.796 + if (_next[i] != INVALID) {
2.797 + _prev.set(_next[i], INVALID);
2.798 + _first[l] = _next[i];
2.799 + } else {
2.800 + _first[l] = INVALID;
2.801 + _last[l] = INVALID;
2.802 + }
2.803 + _level.set(i, ++l);
2.804 + if (_first[l] == INVALID) {
2.805 + _first[l] = _last[l] = i;
2.806 + _prev.set(i, INVALID);
2.807 + _next.set(i, INVALID);
2.808 + } else {
2.809 + _prev.set(_first[l], i);
2.810 + _next.set(i, _first[l]);
2.811 + _first[l] = i;
2.812 + }
2.813 + if (_highest_active < l) {
2.814 + _highest_active = l;
2.815 + }
2.816 + }
2.817 +
2.818 + /// \brief Lifts the active item returned by \c activeOn() member function.
2.819 + ///
2.820 + /// Lifts the active item returned by \c activeOn() member function
2.821 + /// to the given level.
2.822 + void liftActiveOn(int l, int new_level)
2.823 + {
2.824 + Item i = _first[l];
2.825 + if (_next[i] != INVALID) {
2.826 + _prev.set(_next[i], INVALID);
2.827 + _first[l] = _next[i];
2.828 + } else {
2.829 + _first[l] = INVALID;
2.830 + _last[l] = INVALID;
2.831 + }
2.832 + _level.set(i, l = new_level);
2.833 + if (_first[l] == INVALID) {
2.834 + _first[l] = _last[l] = i;
2.835 + _prev.set(i, INVALID);
2.836 + _next.set(i, INVALID);
2.837 + } else {
2.838 + _prev.set(_first[l], i);
2.839 + _next.set(i, _first[l]);
2.840 + _first[l] = i;
2.841 + }
2.842 + if (_highest_active < l) {
2.843 + _highest_active = l;
2.844 + }
2.845 + }
2.846 +
2.847 + ///Lifts the active item returned by \c activeOn() member function.
2.848 +
2.849 + ///Lifts the active item returned by \c activeOn() member function
2.850 + ///to the top level.
2.851 + void liftActiveToTop(int l)
2.852 + {
2.853 + Item i = _first[l];
2.854 + if (_next[i] != INVALID) {
2.855 + _prev.set(_next[i], INVALID);
2.856 + _first[l] = _next[i];
2.857 + } else {
2.858 + _first[l] = INVALID;
2.859 + _last[l] = INVALID;
2.860 + }
2.861 + _level.set(i, _max_level);
2.862 + if (l == _highest_active) {
2.863 + while (_highest_active >= 0 && activeFree(_highest_active))
2.864 + --_highest_active;
2.865 + }
2.866 + }
2.867 +
2.868 + ///@}
2.869 +
2.870 + /// \brief Lift an active item to a higher level.
2.871 + ///
2.872 + /// Lift an active item to a higher level.
2.873 + /// \param i The item to be lifted. It must be active.
2.874 + /// \param new_level The new level of \c i. It must be strictly higher
2.875 + /// than the current level.
2.876 + ///
2.877 + void lift(Item i, int new_level) {
2.878 + if (_next[i] != INVALID) {
2.879 + _prev.set(_next[i], _prev[i]);
2.880 + } else {
2.881 + _last[new_level] = _prev[i];
2.882 + }
2.883 + if (_prev[i] != INVALID) {
2.884 + _next.set(_prev[i], _next[i]);
2.885 + } else {
2.886 + _first[new_level] = _next[i];
2.887 + }
2.888 + _level.set(i, new_level);
2.889 + if (_first[new_level] == INVALID) {
2.890 + _first[new_level] = _last[new_level] = i;
2.891 + _prev.set(i, INVALID);
2.892 + _next.set(i, INVALID);
2.893 + } else {
2.894 + _prev.set(_first[new_level], i);
2.895 + _next.set(i, _first[new_level]);
2.896 + _first[new_level] = i;
2.897 + }
2.898 + if (_highest_active < new_level) {
2.899 + _highest_active = new_level;
2.900 + }
2.901 + }
2.902 +
2.903 + ///Mark the node as it did not reach the max level
2.904 +
2.905 + ///Mark the node as it did not reach the max level. It sets the
2.906 + ///level to the under the max level value. The node will be never
2.907 + ///more activated because the push operation from the maximum
2.908 + ///level is forbidden in the push-relabel algorithms. The node
2.909 + ///should be lifted previously to the top level.
2.910 + void markToBottom(Item i) {
2.911 + _level.set(i, _max_level - 1);
2.912 + }
2.913 +
2.914 + ///Lift all nodes on and above a level to the top (and deactivate them).
2.915 +
2.916 + ///This function lifts all nodes on and above level \c l to \c
2.917 + ///maxLevel(), and also deactivates them.
2.918 + void liftToTop(int l) {
2.919 + for (int i = l + 1; _first[i] != INVALID; ++i) {
2.920 + Item n = _first[i];
2.921 + while (n != INVALID) {
2.922 + _level.set(n, _max_level);
2.923 + n = _next[n];
2.924 + }
2.925 + _first[i] = INVALID;
2.926 + _last[i] = INVALID;
2.927 + }
2.928 + if (_highest_active > l - 1) {
2.929 + _highest_active = l - 1;
2.930 + while (_highest_active >= 0 && activeFree(_highest_active))
2.931 + --_highest_active;
2.932 + }
2.933 + }
2.934 +
2.935 + private:
2.936 +
2.937 + int _init_level;
2.938 +
2.939 + public:
2.940 +
2.941 + ///\name Initialization
2.942 + ///Using this function you can initialize the levels of the item.
2.943 + ///\n
2.944 + ///This initializatios is started with calling \c initStart().
2.945 + ///Then the
2.946 + ///items should be listed levels by levels statring with the lowest one
2.947 + ///(with level 0). This is done by using \c initAddItem()
2.948 + ///and \c initNewLevel(). Finally \c initFinish() must be called.
2.949 + ///The items not listed will be put on the highest level.
2.950 + ///@{
2.951 +
2.952 + ///Start the initialization process.
2.953 +
2.954 + void initStart() {
2.955 +
2.956 + for (int i = 0; i <= _max_level; ++i) {
2.957 + _first[i] = _last[i] = INVALID;
2.958 + }
2.959 + _init_level = 0;
2.960 + for(typename ItemSetTraits<Graph,Item>::ItemIt i(_graph);
2.961 + i != INVALID; ++i) {
2.962 + _level.set(i, _max_level);
2.963 + _active.set(i, false);
2.964 + }
2.965 + }
2.966 +
2.967 + ///Add an item to the current level.
2.968 +
2.969 + void initAddItem(Item i) {
2.970 + _level.set(i, _init_level);
2.971 + if (_last[_init_level] == INVALID) {
2.972 + _first[_init_level] = i;
2.973 + _last[_init_level] = i;
2.974 + _prev.set(i, INVALID);
2.975 + _next.set(i, INVALID);
2.976 + } else {
2.977 + _prev.set(i, _last[_init_level]);
2.978 + _next.set(i, INVALID);
2.979 + _next.set(_last[_init_level], i);
2.980 + _last[_init_level] = i;
2.981 + }
2.982 + }
2.983 +
2.984 + ///Start a new level.
2.985 +
2.986 + ///Start a new level.
2.987 + ///It shouldn't be used before the items on level 0 are listed.
2.988 + void initNewLevel() {
2.989 + ++_init_level;
2.990 + }
2.991 +
2.992 + ///Finalize the initialization process.
2.993 +
2.994 + void initFinish() {
2.995 + _highest_active = -1;
2.996 + }
2.997 +
2.998 + ///@}
2.999 +
2.1000 + };
2.1001 +
2.1002 +
2.1003 +} //END OF NAMESPACE LEMON
2.1004 +
2.1005 +#endif
2.1006 +