1.1 --- a/lemon/bits/traits.h Wed Nov 14 17:42:48 2007 +0000
1.2 +++ b/lemon/bits/traits.h Wed Nov 14 17:44:42 2007 +0000
1.3 @@ -1,3 +1,4 @@
1.4 +
1.5 /* -*- C++ -*-
1.6 *
1.7 * This file is a part of LEMON, a generic C++ optimization library
1.8 @@ -57,6 +58,7 @@
1.9 class Map : public Graph::template NodeMap<_Value> {
1.10 public:
1.11 typedef typename Graph::template NodeMap<_Value> Parent;
1.12 + typedef typename Graph::template NodeMap<_Value> Type;
1.13 typedef typename Parent::Value Value;
1.14
1.15 Map(const Graph& _graph) : Parent(_graph) {}
1.16 @@ -94,6 +96,7 @@
1.17 class Map : public Graph::template EdgeMap<_Value> {
1.18 public:
1.19 typedef typename Graph::template EdgeMap<_Value> Parent;
1.20 + typedef typename Graph::template EdgeMap<_Value> Type;
1.21 typedef typename Parent::Value Value;
1.22
1.23 Map(const Graph& _graph) : Parent(_graph) {}
1.24 @@ -130,6 +133,7 @@
1.25 class Map : public Graph::template UEdgeMap<_Value> {
1.26 public:
1.27 typedef typename Graph::template UEdgeMap<_Value> Parent;
1.28 + typedef typename Graph::template UEdgeMap<_Value> Type;
1.29 typedef typename Parent::Value Value;
1.30
1.31 Map(const Graph& _graph) : Parent(_graph) {}
1.32 @@ -166,6 +170,7 @@
1.33 class Map : public Graph::template ANodeMap<_Value> {
1.34 public:
1.35 typedef typename Graph::template ANodeMap<_Value> Parent;
1.36 + typedef typename Graph::template ANodeMap<_Value> Type;
1.37 typedef typename Parent::Value Value;
1.38
1.39 Map(const Graph& _graph) : Parent(_graph) {}
1.40 @@ -202,6 +207,7 @@
1.41 class Map : public Graph::template BNodeMap<_Value> {
1.42 public:
1.43 typedef typename Graph::template BNodeMap<_Value> Parent;
1.44 + typedef typename Graph::template BNodeMap<_Value> Type;
1.45 typedef typename Parent::Value Value;
1.46
1.47 Map(const Graph& _graph) : Parent(_graph) {}
2.1 --- a/lemon/circulation.h Wed Nov 14 17:42:48 2007 +0000
2.2 +++ b/lemon/circulation.h Wed Nov 14 17:44:42 2007 +0000
2.3 @@ -253,14 +253,14 @@
2.4 _excess[act]=exc;
2.5 if(!_tol.positive(exc)) _levels.deactivate(act);
2.6 else if(mlevel==_node_num) {
2.7 - _levels.liftHighestActiveTo(_node_num);
2.8 + _levels.liftHighestActiveToTop();
2.9 #ifdef LEMON_CIRCULATION_DEBUG
2.10 std::cerr << " Lift to level " << _node_num << std::endl;
2.11 #endif
2.12 return _levels.onLevel(_node_num-1)==0?_node_num-1:actlevel;
2.13 }
2.14 else {
2.15 - _levels.liftHighestActiveTo(mlevel+1);
2.16 + _levels.liftHighestActive(mlevel+1);
2.17 #ifdef LEMON_CIRCULATION_DEBUG
2.18 std::cerr << " Lift to level " << mlevel+1 << std::endl;
2.19 #endif
3.1 --- a/lemon/elevator.h Wed Nov 14 17:42:48 2007 +0000
3.2 +++ b/lemon/elevator.h Wed Nov 14 17:44:42 2007 +0000
3.3 @@ -42,16 +42,22 @@
3.4 ///Each item is either \em active or not, and you can also choose a
3.5 ///highest level active item.
3.6 ///
3.7 + ///\sa LinkedElevator
3.8 + ///
3.9 ///\param Graph the underlying graph type
3.10 ///\param Item Type of the items the data is assigned to (Graph::Node,
3.11 ///Graph::Edge, Graph::UEdge)
3.12 template<class Graph, class Item>
3.13 class Elevator
3.14 {
3.15 - public:
3.16 + private:
3.17 +
3.18 + typedef Item Key;
3.19 + typedef int Value;
3.20 +
3.21 typedef typename std::vector<Item>::iterator Vit;
3.22 - typedef DefaultMap<Graph,Item,Vit> VitMap;
3.23 - typedef DefaultMap<Graph,Item,int> IntMap;
3.24 + typedef typename ItemSetTraits<Graph,Item>::template Map<Vit>::Type VitMap;
3.25 + typedef typename ItemSetTraits<Graph,Item>::template Map<int>::Type IntMap;
3.26
3.27 const Graph &_g;
3.28 int _max_level;
3.29 @@ -86,28 +92,8 @@
3.30 *j=ti;
3.31 }
3.32
3.33 - void checkDs() const
3.34 - {
3.35 - for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)
3.36 - {
3.37 - Vit w=_where[i];
3.38 - int l=_level[i];
3.39 - check(*w==i,"GEBASZ: CORRUPT DS");
3.40 - check(_first[l]<=w,"GEBASZ: CORRUPT DS");
3.41 - check(_first[l+1]>w,"GEBASZ: CORRUPT DS");
3.42 - }
3.43 - for(int l=0;l<=_max_level;++l)
3.44 - {
3.45 - check(_first[l]<=_last_active[l]+1,"GEBASZ: CORRUPT DS");
3.46 - check(_last_active[l]<_first[l+1],"GEBASZ: CORRUPT DS");
3.47 - check(_first[l]<=_first[l+1],"GEBASZ: CORRUPT DS");
3.48 - }
3.49 - check(_highest_active<0 ||
3.50 - _first[_highest_active]<=_last_active[_highest_active],
3.51 - "GEBASZ: CORRUPT DS");
3.52 - }
3.53 -
3.54 public:
3.55 +
3.56 ///Constructor with given maximum level.
3.57
3.58 ///Constructor with given maximum level.
3.59 @@ -144,7 +130,7 @@
3.60 _highest_active(-1)
3.61 {
3.62 }
3.63 -
3.64 +
3.65 ///Activate item \c i.
3.66
3.67 ///Activate item \c i.
3.68 @@ -174,22 +160,16 @@
3.69 ///Return the level of item \c i.
3.70 int operator[](Item i) const { return _level[i]; }
3.71
3.72 - ///Returns an active item on level \c l.
3.73 -
3.74 - ///Returns an active item on level \c l.
3.75 - ///
3.76 - ///Returns an active item on level \c l or \ref INVALID if there is no such
3.77 - ///an item. (\c l must be from the range [0...\c max_level].
3.78 - Item operator[](int l) const
3.79 - {
3.80 - return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
3.81 - }
3.82 -
3.83 ///Return the number of items on level \c l.
3.84 int onLevel(int l) const
3.85 {
3.86 return _first[l+1]-_first[l];
3.87 }
3.88 + ///Return true if the level is empty.
3.89 + bool emptyLevel(int l) const
3.90 + {
3.91 + return _first[l+1]-_first[l]==0;
3.92 + }
3.93 ///Return the number of items above level \c l.
3.94 int aboveLevel(int l) const
3.95 {
3.96 @@ -200,6 +180,11 @@
3.97 {
3.98 return _last_active[l]-_first[l]+1;
3.99 }
3.100 + ///Return true if there is not active item on level \c l.
3.101 + bool activeFree(int l) const
3.102 + {
3.103 + return _last_active[l]<_first[l];
3.104 + }
3.105 ///Return the maximum allowed level.
3.106 int maxLevel() const
3.107 {
3.108 @@ -252,7 +237,7 @@
3.109 ///\warning \c new_level must be strictly higher
3.110 ///than the current level.
3.111 ///
3.112 - void liftHighestActiveTo(int new_level)
3.113 + void liftHighestActive(int new_level)
3.114 {
3.115 const Item li = *_last_active[_highest_active];
3.116
3.117 @@ -266,9 +251,109 @@
3.118 _level[li]=new_level;
3.119 _highest_active=new_level;
3.120 }
3.121 +
3.122 + ///Lift the highest active item.
3.123 +
3.124 + ///Lift the item returned by highestActive() to the top level and
3.125 + ///deactivates it.
3.126 + ///
3.127 + ///\warning \c new_level must be strictly higher
3.128 + ///than the current level.
3.129 + ///
3.130 + void liftHighestActiveToTop()
3.131 + {
3.132 + const Item li = *_last_active[_highest_active];
3.133 +
3.134 + copy(--_first[_highest_active+1],_last_active[_highest_active]--);
3.135 + for(int l=_highest_active+1;l<_max_level;l++)
3.136 + {
3.137 + copy(--_first[l+1],_first[l]);
3.138 + --_last_active[l];
3.139 + }
3.140 + copy(li,_first[_max_level]);
3.141 + --_last_active[_max_level];
3.142 + _level[li]=_max_level;
3.143 +
3.144 + while(_highest_active>=0 &&
3.145 + _last_active[_highest_active]<_first[_highest_active])
3.146 + _highest_active--;
3.147 + }
3.148
3.149 ///@}
3.150
3.151 + ///\name Active Item on Certain Level
3.152 + ///Functions for working with the active items.
3.153 +
3.154 + ///@{
3.155 +
3.156 + ///Returns an active item on level \c l.
3.157 +
3.158 + ///Returns an active item on level \c l.
3.159 + ///
3.160 + ///Returns an active item on level \c l or \ref INVALID if there is no such
3.161 + ///an item. (\c l must be from the range [0...\c max_level].
3.162 + Item activeOn(int l) const
3.163 + {
3.164 + return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
3.165 + }
3.166 +
3.167 + ///Lifts the active item returned by \c activeOn() member function.
3.168 +
3.169 + ///Lifts the active item returned by \c activeOn() member function
3.170 + ///by one.
3.171 + Item liftActiveOn(int level)
3.172 + {
3.173 + ++_level[*_last_active[level]];
3.174 + swap(_last_active[level]--, --_first[level+1]);
3.175 + if (level+1>_highest_active) ++_highest_active;
3.176 + }
3.177 +
3.178 + ///Lifts the active item returned by \c activeOn() member function.
3.179 +
3.180 + ///Lifts the active item returned by \c activeOn() member function
3.181 + ///to the given level.
3.182 + void liftActiveOn(int level, int new_level)
3.183 + {
3.184 + const Item ai = *_last_active[level];
3.185 +
3.186 + copy(--_first[level+1], _last_active[level]--);
3.187 + for(int l=level+1;l<new_level;l++)
3.188 + {
3.189 + copy(_last_active[l],_first[l]);
3.190 + copy(--_first[l+1], _last_active[l]--);
3.191 + }
3.192 + copy(ai,_first[new_level]);
3.193 + _level[ai]=new_level;
3.194 + if (new_level>_highest_active) _highest_active=new_level;
3.195 + }
3.196 +
3.197 + ///Lifts the active item returned by \c activeOn() member function.
3.198 +
3.199 + ///Lifts the active item returned by \c activeOn() member function
3.200 + ///to the top level.
3.201 + void liftActiveToTop(int level)
3.202 + {
3.203 + const Item ai = *_last_active[level];
3.204 +
3.205 + copy(--_first[level+1],_last_active[level]--);
3.206 + for(int l=level+1;l<_max_level;l++)
3.207 + {
3.208 + copy(_last_active[l],_first[l]);
3.209 + copy(--_first[l+1], _last_active[l]--);
3.210 + }
3.211 + copy(ai,_first[_max_level]);
3.212 + --_last_active[_max_level];
3.213 + _level[ai]=_max_level;
3.214 +
3.215 + if (_highest_active==level) {
3.216 + while(_highest_active>=0 &&
3.217 + _last_active[_highest_active]<_first[_highest_active])
3.218 + _highest_active--;
3.219 + }
3.220 + }
3.221 +
3.222 + ///@}
3.223 +
3.224 ///Lift an active item to a higher level.
3.225
3.226 ///Lift an active item to a higher level.
3.227 @@ -276,7 +361,7 @@
3.228 ///\param new_level The new level of \c i. It must be strictly higher
3.229 ///than the current level.
3.230 ///
3.231 - void liftTo(Item i, int new_level)
3.232 + void lift(Item i, int new_level)
3.233 {
3.234 const int lo = _level[i];
3.235 const Vit w = _where[i];
3.236 @@ -292,28 +377,11 @@
3.237 _level[i]=new_level;
3.238 if(new_level>_highest_active) _highest_active=new_level;
3.239 }
3.240 -
3.241 -// void liftToTop(int l)
3.242 -// {
3.243 -// const Vit f=_first[l];
3.244 -// for(int i=l;i<=_max_level;i++)
3.245 -// {
3.246 -// _first[i]=f;
3.247 -// _last_active[i]=f-1;
3.248 -// }
3.249 -// for(Vit i=f;i!=_items.end();++i)
3.250 -// _level[*i]=_max_level;
3.251 -// for(_highest_active=l-1;
3.252 -// _highest_active>=0 &&
3.253 -// _last_active[_highest_active]<_first[_highest_active];
3.254 -// _highest_active--) ;
3.255 -// }
3.256
3.257 ///Lift all nodes on and above a level to the top (and deactivate them).
3.258
3.259 - ///This function lifts all nodes on and above level \c l to \c maxLevel(),
3.260 - ///and
3.261 - ///also deactivates them.
3.262 + ///This function lifts all nodes on and above level \c l to \c
3.263 + ///maxLevel(), and also deactivates them.
3.264 void liftToTop(int l)
3.265 {
3.266 const Vit f=_first[l];
3.267 @@ -397,12 +465,511 @@
3.268 }
3.269 _first[_max_level+1]=_items.begin()+_item_num;
3.270 _last_active[_max_level+1]=_items.begin()+_item_num-1;
3.271 + _highest_active = -1;
3.272 }
3.273
3.274 ///@}
3.275
3.276 };
3.277
3.278 + ///Class for handling "labels" in push-relabel type algorithms.
3.279 +
3.280 + ///A class for handling "labels" in push-relabel type algorithms.
3.281 + ///
3.282 + ///\ingroup auxdat
3.283 + ///Using this class you can assign "labels" (nonnegative integer numbers)
3.284 + ///to the edges or nodes of a graph, manipulate and query them through
3.285 + ///operations typically arising in "push-relabel" type algorithms.
3.286 + ///
3.287 + ///Each item is either \em active or not, and you can also choose a
3.288 + ///highest level active item.
3.289 + ///
3.290 + ///\sa Elevator
3.291 + ///
3.292 + ///\param Graph the underlying graph type
3.293 + ///\param Item Type of the items the data is assigned to (Graph::Node,
3.294 + ///Graph::Edge, Graph::UEdge)
3.295 + template <class Graph, class Item>
3.296 + class LinkedElevator {
3.297 + private:
3.298 +
3.299 + typedef Item Key;
3.300 + typedef int Value;
3.301 +
3.302 + typedef typename ItemSetTraits<Graph,Item>::
3.303 + template Map<Item>::Type ItemMap;
3.304 + typedef typename ItemSetTraits<Graph,Item>::
3.305 + template Map<int>::Type IntMap;
3.306 + typedef typename ItemSetTraits<Graph,Item>::
3.307 + template Map<bool>::Type BoolMap;
3.308 +
3.309 + const Graph &_graph;
3.310 + int _max_level;
3.311 + int _item_num;
3.312 + std::vector<Item> _first, _last;
3.313 + ItemMap _prev, _next;
3.314 + int _highest_active;
3.315 + IntMap _level;
3.316 + BoolMap _active;
3.317 +
3.318 + public:
3.319 + ///Constructor with given maximum level.
3.320 +
3.321 + ///Constructor with given maximum level.
3.322 + ///
3.323 + ///\param g The underlying graph
3.324 + ///\param max_level Set the range of the possible labels to
3.325 + ///[0...\c max_level]
3.326 + LinkedElevator(const Graph& graph, int max_level)
3.327 + : _graph(graph), _max_level(max_level), _item_num(_max_level),
3.328 + _first(_max_level + 1), _last(_max_level + 1),
3.329 + _prev(graph), _next(graph),
3.330 + _highest_active(-1), _level(graph), _active(graph) {}
3.331 +
3.332 + ///Constructor.
3.333 +
3.334 + ///Constructor.
3.335 + ///
3.336 + ///\param g The underlying graph
3.337 + ///The range of the possible labels is [0...\c max_level],
3.338 + ///where \c max_level is equal to the number of labeled items in the graph.
3.339 + LinkedElevator(const Graph& graph)
3.340 + : _graph(graph), _max_level(countItems<Graph, Item>(graph)),
3.341 + _item_num(_max_level),
3.342 + _first(_max_level + 1), _last(_max_level + 1),
3.343 + _prev(graph, INVALID), _next(graph, INVALID),
3.344 + _highest_active(-1), _level(graph), _active(graph) {}
3.345 +
3.346 +
3.347 + ///Activate item \c i.
3.348 +
3.349 + ///Activate item \c i.
3.350 + ///\pre Item \c i shouldn't be active before.
3.351 + void activate(Item i) {
3.352 + _active.set(i, true);
3.353 +
3.354 + int level = _level[i];
3.355 + if (level > _highest_active) {
3.356 + _highest_active = level;
3.357 + }
3.358 +
3.359 + if (_prev[i] == INVALID || _active[_prev[i]]) return;
3.360 + //unlace
3.361 + _next.set(_prev[i], _next[i]);
3.362 + if (_next[i] != INVALID) {
3.363 + _prev.set(_next[i], _prev[i]);
3.364 + } else {
3.365 + _last[level] = _prev[i];
3.366 + }
3.367 + //lace
3.368 + _next.set(i, _first[level]);
3.369 + _prev.set(_first[level], i);
3.370 + _prev.set(i, INVALID);
3.371 + _first[level] = i;
3.372 +
3.373 + }
3.374 +
3.375 + ///Deactivate item \c i.
3.376 +
3.377 + ///Deactivate item \c i.
3.378 + ///\pre Item \c i must be active before.
3.379 + void deactivate(Item i) {
3.380 + _active.set(i, false);
3.381 + int level = _level[i];
3.382 +
3.383 + if (_next[i] == INVALID || !_active[_next[i]])
3.384 + goto find_highest_level;
3.385 +
3.386 + //unlace
3.387 + _prev.set(_next[i], _prev[i]);
3.388 + if (_prev[i] != INVALID) {
3.389 + _next.set(_prev[i], _next[i]);
3.390 + } else {
3.391 + _first[_level[i]] = _next[i];
3.392 + }
3.393 + //lace
3.394 + _prev.set(i, _last[level]);
3.395 + _next.set(_last[level], i);
3.396 + _next.set(i, INVALID);
3.397 + _last[level] = i;
3.398 +
3.399 + find_highest_level:
3.400 + if (level == _highest_active) {
3.401 + while (_highest_active >= 0 && activeFree(_highest_active))
3.402 + --_highest_active;
3.403 + }
3.404 + }
3.405 +
3.406 + ///Query whether item \c i is active
3.407 + bool active(Item i) const { return _active[i]; }
3.408 +
3.409 + ///Return the level of item \c i.
3.410 + int operator[](Item i) const { return _level[i]; }
3.411 +
3.412 + ///Return the number of items on level \c l.
3.413 + int onLevel(int l) const {
3.414 + int num = 0;
3.415 + Item n = _first[l];
3.416 + while (n != INVALID) {
3.417 + ++num;
3.418 + n = _next[n];
3.419 + }
3.420 + return num;
3.421 + }
3.422 +
3.423 + ///Return true if the level is empty.
3.424 + bool emptyLevel(int l) const {
3.425 + return _first[l] == INVALID;
3.426 + }
3.427 +
3.428 + ///Return the number of items above level \c l.
3.429 + int aboveLevel(int l) const {
3.430 + int num = 0;
3.431 + for (int level = l + 1; level < _max_level; ++level)
3.432 + num += onLevel(level);
3.433 + return num;
3.434 + }
3.435 +
3.436 + ///Return the number of active items on level \c l.
3.437 + int activesOnLevel(int l) const {
3.438 + int num = 0;
3.439 + Item n = _first[l];
3.440 + while (n != INVALID && _active[n]) {
3.441 + ++num;
3.442 + n = _next[n];
3.443 + }
3.444 + return num;
3.445 + }
3.446 +
3.447 + ///Return true if there is not active item on level \c l.
3.448 + bool activeFree(int l) const {
3.449 + return _first[l] == INVALID || !_active[_first[l]];
3.450 + }
3.451 +
3.452 + ///Return the maximum allowed level.
3.453 + int maxLevel() const {
3.454 + return _max_level;
3.455 + }
3.456 +
3.457 + ///\name Highest Active Item
3.458 + ///Functions for working with the highest level
3.459 + ///active item.
3.460 +
3.461 + ///@{
3.462 +
3.463 + ///Return a highest level active item.
3.464 +
3.465 + ///Return a highest level active item.
3.466 + ///
3.467 + ///\return the highest level active item or INVALID if there is no
3.468 + ///active item.
3.469 + Item highestActive() const {
3.470 + return _highest_active >= 0 ? _first[_highest_active] : INVALID;
3.471 + }
3.472 +
3.473 + ///Return a highest active level.
3.474 +
3.475 + ///Return a highest active level.
3.476 + ///
3.477 + ///\return the level of the highest active item or -1 if there is
3.478 + ///no active item.
3.479 + int highestActiveLevel() const {
3.480 + return _highest_active;
3.481 + }
3.482 +
3.483 + ///Lift the highest active item by one.
3.484 +
3.485 + ///Lift the item returned by highestActive() by one.
3.486 + ///
3.487 + void liftHighestActive() {
3.488 + Item i = _first[_highest_active];
3.489 + if (_next[i] != INVALID) {
3.490 + _prev.set(_next[i], INVALID);
3.491 + _first[_highest_active] = _next[i];
3.492 + } else {
3.493 + _first[_highest_active] = INVALID;
3.494 + _last[_highest_active] = INVALID;
3.495 + }
3.496 + _level.set(i, ++_highest_active);
3.497 + if (_first[_highest_active] == INVALID) {
3.498 + _first[_highest_active] = i;
3.499 + _last[_highest_active] = i;
3.500 + _prev.set(i, INVALID);
3.501 + _next.set(i, INVALID);
3.502 + } else {
3.503 + _prev.set(_first[_highest_active], i);
3.504 + _next.set(i, _first[_highest_active]);
3.505 + _first[_highest_active] = i;
3.506 + }
3.507 + }
3.508 +
3.509 + ///Lift the highest active item.
3.510 +
3.511 + ///Lift the item returned by highestActive() to level \c new_level.
3.512 + ///
3.513 + ///\warning \c new_level must be strictly higher
3.514 + ///than the current level.
3.515 + ///
3.516 + void liftHighestActive(int new_level) {
3.517 + Item i = _first[_highest_active];
3.518 + if (_next[i] != INVALID) {
3.519 + _prev.set(_next[i], INVALID);
3.520 + _first[_highest_active] = _next[i];
3.521 + } else {
3.522 + _first[_highest_active] = INVALID;
3.523 + _last[_highest_active] = INVALID;
3.524 + }
3.525 + _level.set(i, _highest_active = new_level);
3.526 + if (_first[_highest_active] == INVALID) {
3.527 + _first[_highest_active] = _last[_highest_active] = i;
3.528 + _prev.set(i, INVALID);
3.529 + _next.set(i, INVALID);
3.530 + } else {
3.531 + _prev.set(_first[_highest_active], i);
3.532 + _next.set(i, _first[_highest_active]);
3.533 + _first[_highest_active] = i;
3.534 + }
3.535 + }
3.536 +
3.537 + ///Lift the highest active to top.
3.538 +
3.539 + ///Lift the item returned by highestActive() to the top level and
3.540 + ///deactivates the node.
3.541 + ///
3.542 + void liftHighestActiveToTop() {
3.543 + Item i = _first[_highest_active];
3.544 + _level.set(i, _max_level);
3.545 + if (_next[i] != INVALID) {
3.546 + _prev.set(_next[i], INVALID);
3.547 + _first[_highest_active] = _next[i];
3.548 + } else {
3.549 + _first[_highest_active] = INVALID;
3.550 + _last[_highest_active] = INVALID;
3.551 + }
3.552 + while (_highest_active >= 0 && activeFree(_highest_active))
3.553 + --_highest_active;
3.554 + }
3.555 +
3.556 + ///@}
3.557 +
3.558 + ///\name Active Item on Certain Level
3.559 + ///Functions for working with the active items.
3.560 +
3.561 + ///@{
3.562 +
3.563 + ///Returns an active item on level \c l.
3.564 +
3.565 + ///Returns an active item on level \c l.
3.566 + ///
3.567 + ///Returns an active item on level \c l or \ref INVALID if there is no such
3.568 + ///an item. (\c l must be from the range [0...\c max_level].
3.569 + Item activeOn(int l) const
3.570 + {
3.571 + return _active[_first[l]] ? _first[l] : INVALID;
3.572 + }
3.573 +
3.574 + ///Lifts the active item returned by \c activeOn() member function.
3.575 +
3.576 + ///Lifts the active item returned by \c activeOn() member function
3.577 + ///by one.
3.578 + Item liftActiveOn(int l)
3.579 + {
3.580 + Item i = _first[l];
3.581 + if (_next[i] != INVALID) {
3.582 + _prev.set(_next[i], INVALID);
3.583 + _first[l] = _next[i];
3.584 + } else {
3.585 + _first[l] = INVALID;
3.586 + _last[l] = INVALID;
3.587 + }
3.588 + _level.set(i, ++l);
3.589 + if (_first[l] == INVALID) {
3.590 + _first[l] = _last[l] = i;
3.591 + _prev.set(i, INVALID);
3.592 + _next.set(i, INVALID);
3.593 + } else {
3.594 + _prev.set(_first[l], i);
3.595 + _next.set(i, _first[l]);
3.596 + _first[l] = i;
3.597 + }
3.598 + if (_highest_active < l) {
3.599 + _highest_active = l;
3.600 + }
3.601 + }
3.602 +
3.603 + /// \brief Lifts the active item returned by \c activeOn() member function.
3.604 + ///
3.605 + /// Lifts the active item returned by \c activeOn() member function
3.606 + /// to the given level.
3.607 + void liftActiveOn(int l, int new_level)
3.608 + {
3.609 + Item i = _first[l];
3.610 + if (_next[i] != INVALID) {
3.611 + _prev.set(_next[i], INVALID);
3.612 + _first[l] = _next[i];
3.613 + } else {
3.614 + _first[l] = INVALID;
3.615 + _last[l] = INVALID;
3.616 + }
3.617 + _level.set(i, l = new_level);
3.618 + if (_first[l] == INVALID) {
3.619 + _first[l] = _last[l] = i;
3.620 + _prev.set(i, INVALID);
3.621 + _next.set(i, INVALID);
3.622 + } else {
3.623 + _prev.set(_first[l], i);
3.624 + _next.set(i, _first[l]);
3.625 + _first[l] = i;
3.626 + }
3.627 + if (_highest_active < l) {
3.628 + _highest_active = l;
3.629 + }
3.630 + }
3.631 +
3.632 + ///Lifts the active item returned by \c activeOn() member function.
3.633 +
3.634 + ///Lifts the active item returned by \c activeOn() member function
3.635 + ///to the top level.
3.636 + void liftActiveToTop(int l)
3.637 + {
3.638 + Item i = _first[l];
3.639 + if (_next[i] != INVALID) {
3.640 + _prev.set(_next[i], INVALID);
3.641 + _first[l] = _next[i];
3.642 + } else {
3.643 + _first[l] = INVALID;
3.644 + _last[l] = INVALID;
3.645 + }
3.646 + _level.set(i, _max_level);
3.647 + if (l == _highest_active) {
3.648 + while (_highest_active >= 0 && activeFree(_highest_active))
3.649 + --_highest_active;
3.650 + }
3.651 + }
3.652 +
3.653 + ///@}
3.654 +
3.655 + /// \brief Lift an active item to a higher level.
3.656 + ///
3.657 + /// Lift an active item to a higher level.
3.658 + /// \param i The item to be lifted. It must be active.
3.659 + /// \param new_level The new level of \c i. It must be strictly higher
3.660 + /// than the current level.
3.661 + ///
3.662 + void lift(Item i, int new_level) {
3.663 + if (_next[i] != INVALID) {
3.664 + _prev.set(_next[i], _prev[i]);
3.665 + } else {
3.666 + _last[new_level] = _prev[i];
3.667 + }
3.668 + if (_prev[i] != INVALID) {
3.669 + _next.set(_prev[i], _next[i]);
3.670 + } else {
3.671 + _first[new_level] = _next[i];
3.672 + }
3.673 + _level.set(i, new_level);
3.674 + if (_first[new_level] == INVALID) {
3.675 + _first[new_level] = _last[new_level] = i;
3.676 + _prev.set(i, INVALID);
3.677 + _next.set(i, INVALID);
3.678 + } else {
3.679 + _prev.set(_first[new_level], i);
3.680 + _next.set(i, _first[new_level]);
3.681 + _first[new_level] = i;
3.682 + }
3.683 + if (_highest_active < new_level) {
3.684 + _highest_active = new_level;
3.685 + }
3.686 + }
3.687 +
3.688 + ///Lift all nodes on and above a level to the top (and deactivate them).
3.689 +
3.690 + ///This function lifts all nodes on and above level \c l to \c
3.691 + ///maxLevel(), and also deactivates them.
3.692 + void liftToTop(int l) {
3.693 + for (int i = l + 1; _first[i] != INVALID; ++i) {
3.694 + Item n = _first[i];
3.695 + while (n != INVALID) {
3.696 + _level.set(n, _max_level);
3.697 + n = _next[n];
3.698 + }
3.699 + _first[i] = INVALID;
3.700 + _last[i] = INVALID;
3.701 + }
3.702 + if (_highest_active > l - 1) {
3.703 + _highest_active = l - 1;
3.704 + while (_highest_active >= 0 && activeFree(_highest_active))
3.705 + --_highest_active;
3.706 + }
3.707 + }
3.708 +
3.709 + private:
3.710 +
3.711 + int _init_level;
3.712 +
3.713 + public:
3.714 +
3.715 + ///\name Initialization
3.716 + ///Using this function you can initialize the levels of the item.
3.717 + ///\n
3.718 + ///This initializatios is started with calling \c initStart().
3.719 + ///Then the
3.720 + ///items should be listed levels by levels statring with the lowest one
3.721 + ///(with level 0). This is done by using \c initAddItem()
3.722 + ///and \c initNewLevel(). Finally \c initFinish() must be called.
3.723 + ///The items not listed will be put on the highest level.
3.724 + ///@{
3.725 +
3.726 + ///Start the initialization process.
3.727 +
3.728 + void initStart() {
3.729 +
3.730 + for (int i = 0; i <= _max_level; ++i) {
3.731 + _first[i] = _last[i] = INVALID;
3.732 + }
3.733 + _init_level = 0;
3.734 + for(typename ItemSetTraits<Graph,Item>::ItemIt i(_graph);
3.735 + i != INVALID; ++i) {
3.736 + _level.set(i, _max_level);
3.737 + }
3.738 + }
3.739 +
3.740 + ///Add an item to the current level.
3.741 +
3.742 + void initAddItem(Item i) {
3.743 + _level.set(i, _init_level);
3.744 + if (_last[_init_level] == INVALID) {
3.745 + _first[_init_level] = i;
3.746 + _last[_init_level] = i;
3.747 + _prev.set(i, INVALID);
3.748 + _next.set(i, INVALID);
3.749 + } else {
3.750 + _prev.set(i, _last[_init_level]);
3.751 + _next.set(i, INVALID);
3.752 + _next.set(_last[_init_level], i);
3.753 + _last[_init_level] = i;
3.754 + }
3.755 + }
3.756 +
3.757 + ///Start a new level.
3.758 +
3.759 + ///Start a new level.
3.760 + ///It shouldn't be used before the items on level 0 are listed.
3.761 + void initNewLevel() {
3.762 + ++_init_level;
3.763 + }
3.764 +
3.765 + ///Finalize the initialization process.
3.766 +
3.767 + void initFinish() {
3.768 + _highest_active = -1;
3.769 + }
3.770 +
3.771 + ///@}
3.772 +
3.773 + };
3.774 +
3.775 +
3.776 } //END OF NAMESPACE LEMON
3.777
3.778 #endif
4.1 --- a/lemon/pr_bipartite_matching.h Wed Nov 14 17:42:48 2007 +0000
4.2 +++ b/lemon/pr_bipartite_matching.h Wed Nov 14 17:44:42 2007 +0000
4.3 @@ -179,7 +179,7 @@
4.4 }
4.5 if(nlevel<_node_num) {
4.6 if(nlevel>=actlevel)
4.7 - _levels.liftHighestActiveTo(nlevel+1);
4.8 + _levels.liftHighestActive(nlevel+1);
4.9 bact=_g.bNode(_matching[_g.aNode(bedge)]);
4.10 if(--_cov[bact]<1) {
4.11 _levels.activate(bact);
4.12 @@ -190,12 +190,10 @@
4.13 _levels.deactivate(act);
4.14 }
4.15 else {
4.16 - if(_node_num>actlevel)
4.17 - _levels.liftHighestActiveTo(_node_num);
4.18 - _levels.deactivate(act);
4.19 + _levels.liftHighestActiveToTop();
4.20 }
4.21
4.22 - if(_levels.onLevel(actlevel)==0)
4.23 + if(_levels.emptyLevel(actlevel))
4.24 _levels.liftToTop(actlevel);
4.25 }
4.26
4.27 @@ -246,7 +244,7 @@
4.28 }
4.29 if(nlevel<_node_num) {
4.30 if(nlevel>=actlevel)
4.31 - _levels.liftHighestActiveTo(nlevel+1);
4.32 + _levels.liftHighestActive(nlevel+1);
4.33 bact=_g.bNode(_matching[_g.aNode(bedge)]);
4.34 if(--_cov[bact]<1) {
4.35 _levels.activate(bact);
4.36 @@ -257,12 +255,10 @@
4.37 _levels.deactivate(act);
4.38 }
4.39 else {
4.40 - if(_node_num>actlevel)
4.41 - _levels.liftHighestActiveTo(_node_num);
4.42 - _levels.deactivate(act);
4.43 + _levels.liftHighestActiveToTop();
4.44 }
4.45
4.46 - if(_levels.onLevel(actlevel)==0)
4.47 + if(_levels.emptyLevel(actlevel))
4.48 _empty_level=actlevel;
4.49 return false;
4.50 }