lemon/elevator.h
author deba
Sat, 17 Nov 2007 20:58:11 +0000
changeset 2514 57143c09dc20
parent 2391 14a343be7a5a
child 2518 4c0a23bd70b5
permissions -rw-r--r--
Redesign the maximum flow algorithms

Redesigned interface
Preflow changed to use elevator
Edmonds-Karp does not use the ResGraphAdaptor
Goldberg-Tarjan algorithm (Preflow with Dynamic Trees)
Dinitz-Sleator-Tarjan (Blocking flow with Dynamic Tree)
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2007
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_ELEVATOR_H
    20 #define LEMON_ELEVATOR_H
    21 
    22 ///\ingroup auxdat
    23 ///\file
    24 ///\brief Elevator class
    25 ///
    26 ///Elevator class implements an efficient data structure
    27 ///for labeling items in push-relabel type algorithms.
    28 ///
    29 
    30 #include <test/test_tools.h>
    31 namespace lemon {
    32 
    33   ///Class for handling "labels" in push-relabel type algorithms.
    34   
    35   ///A class for handling "labels" in push-relabel type algorithms.
    36   ///
    37   ///\ingroup auxdat
    38   ///Using this class you can assign "labels" (nonnegative integer numbers)
    39   ///to the edges or nodes of a graph, manipulate and query them through
    40   ///operations typically arising in "push-relabel" type algorithms.
    41   ///
    42   ///Each item is either \em active or not, and you can also choose a
    43   ///highest level active item.
    44   ///
    45   ///\sa LinkedElevator
    46   ///
    47   ///\param Graph the underlying graph type
    48   ///\param Item Type of the items the data is assigned to (Graph::Node,
    49   ///Graph::Edge, Graph::UEdge)
    50   template<class Graph, class Item>
    51   class Elevator 
    52   {
    53   private:
    54 
    55     typedef Item Key;
    56     typedef int Value;
    57 
    58     typedef typename std::vector<Item>::iterator Vit;
    59     typedef typename ItemSetTraits<Graph,Item>::template Map<Vit>::Type VitMap;
    60     typedef typename ItemSetTraits<Graph,Item>::template Map<int>::Type IntMap;
    61 
    62     const Graph &_g;
    63     int _max_level;
    64     int _item_num;
    65     VitMap _where;
    66     IntMap _level;
    67     std::vector<Item> _items;
    68     std::vector<Vit> _first;
    69     std::vector<Vit> _last_active;
    70 
    71     int _highest_active;
    72 
    73     void copy(Item i, Vit p)
    74     {
    75       _where[*p=i]=p;
    76     }
    77     void copy(Vit s, Vit p)
    78     {
    79       if(s!=p) 
    80 	{
    81 	  Item i=*s;
    82 	  *p=i;
    83 	  _where[i]=p;
    84 	}
    85     }
    86     void swap(Vit i, Vit j)
    87     {
    88       Item ti=*i;
    89       Vit ct = _where[ti];
    90       _where[ti]=_where[*i=*j];
    91       _where[*j]=ct;
    92       *j=ti;
    93     }
    94     
    95   public:
    96         
    97     ///Constructor with given maximum level.
    98 
    99     ///Constructor with given maximum level.
   100     ///
   101     ///\param g The underlying graph
   102     ///\param max_level Set the range of the possible labels to
   103     ///[0...\c max_level]
   104     Elevator(const Graph &g,int max_level) :
   105       _g(g),
   106       _max_level(max_level),
   107       _item_num(_max_level),
   108       _where(g),
   109       _level(g,0),
   110       _items(_max_level),
   111       _first(_max_level+2),
   112       _last_active(_max_level+2),
   113       _highest_active(-1) {}
   114     ///Constructor.
   115 
   116     ///Constructor.
   117     ///
   118     ///\param g The underlying graph
   119     ///The range of the possible labels is [0...\c max_level],
   120     ///where \c max_level is equal to the number of labeled items in the graph.
   121     Elevator(const Graph &g) :
   122       _g(g),
   123       _max_level(countItems<Graph, Item>(g)),
   124       _item_num(_max_level),
   125       _where(g),
   126       _level(g,0),
   127       _items(_max_level),
   128       _first(_max_level+2),
   129       _last_active(_max_level+2),
   130       _highest_active(-1)
   131     {
   132     }
   133     
   134     ///Activate item \c i.
   135 
   136     ///Activate item \c i.
   137     ///\pre Item \c i shouldn't be active before.
   138     void activate(Item i)
   139     {
   140       const int l=_level[i];
   141       swap(_where[i],++_last_active[l]);
   142       if(l>_highest_active) _highest_active=l;
   143     }
   144   
   145     ///Deactivate item \c i.
   146 
   147     ///Deactivate item \c i.
   148     ///\pre Item \c i must be active before.
   149     void deactivate(Item i)  
   150     {
   151       swap(_where[i],_last_active[_level[i]]--);
   152       while(_highest_active>=0 &&
   153 	    _last_active[_highest_active]<_first[_highest_active])
   154 	_highest_active--;
   155     }
   156 
   157     ///Query whether item \c i is active
   158     bool active(Item i) const { return _where[i]<=_last_active[_level[i]]; }
   159     
   160     ///Return the level of item \c i.
   161     int operator[](Item i) const { return _level[i]; }
   162 
   163     ///Return the number of items on level \c l.
   164     int onLevel(int l) const
   165     {
   166       return _first[l+1]-_first[l];
   167     }
   168     ///Return true if the level is empty.
   169     bool emptyLevel(int l) const
   170     {
   171       return _first[l+1]-_first[l]==0;
   172     }
   173     ///Return the number of items above level \c l.
   174     int aboveLevel(int l) const
   175     {
   176       return _first[_max_level+1]-_first[l+1];
   177     }
   178     ///Return the number of active items on level \c l.
   179     int activesOnLevel(int l) const
   180     {
   181       return _last_active[l]-_first[l]+1;
   182     }
   183     ///Return true if there is not active item on level \c l.
   184     bool activeFree(int l) const
   185     {
   186       return _last_active[l]<_first[l];
   187     }
   188     ///Return the maximum allowed level.
   189     int maxLevel() const 
   190     {
   191       return _max_level;
   192     }    
   193 
   194     ///\name Highest Active Item
   195     ///Functions for working with the highest level
   196     ///active item.
   197 
   198     ///@{
   199 
   200     ///Return a highest level active item.
   201   
   202     ///Return a highest level active item.
   203     ///
   204     ///\return the highest level active item or INVALID if there is no active
   205     ///item.
   206     Item highestActive() const 
   207     {
   208       return _highest_active>=0?*_last_active[_highest_active]:INVALID;
   209     }
   210 
   211     ///Return a highest active level.
   212 
   213     ///Return a highest active level.
   214     ///
   215     ///\return the level of the highest active item or -1 if there is no active
   216     ///item.
   217     int highestActiveLevel() const 
   218     {
   219       return _highest_active;
   220     }
   221 
   222     ///Lift the highest active item by one.
   223 
   224     ///Lift the item returned by highestActive() by one.
   225     ///
   226     void liftHighestActive() 
   227     {
   228       ++_level[*_last_active[_highest_active]];
   229       swap(_last_active[_highest_active]--,_last_active[_highest_active+1]);
   230       --_first[++_highest_active];
   231     }
   232 
   233     ///Lift the highest active item.
   234 
   235     ///Lift the item returned by highestActive() to level \c new_level.
   236     ///
   237     ///\warning \c new_level must be strictly higher
   238     ///than the current level.
   239     ///
   240     void liftHighestActive(int new_level) 
   241     {
   242       const Item li = *_last_active[_highest_active];
   243       
   244       copy(--_first[_highest_active+1],_last_active[_highest_active]--);
   245       for(int l=_highest_active+1;l<new_level;l++)
   246 	{
   247 	  copy(--_first[l+1],_first[l]);
   248 	  --_last_active[l];
   249 	}
   250       copy(li,_first[new_level]);
   251       _level[li]=new_level;
   252       _highest_active=new_level;
   253     }
   254 
   255     ///Lift the highest active item.
   256 
   257     ///Lift the item returned by highestActive() to the top level and
   258     ///deactivates it.
   259     ///
   260     ///\warning \c new_level must be strictly higher
   261     ///than the current level.
   262     ///
   263     void liftHighestActiveToTop() 
   264     {
   265       const Item li = *_last_active[_highest_active];
   266       
   267       copy(--_first[_highest_active+1],_last_active[_highest_active]--);
   268       for(int l=_highest_active+1;l<_max_level;l++)
   269 	{
   270 	  copy(--_first[l+1],_first[l]);
   271 	  --_last_active[l];
   272 	}
   273       copy(li,_first[_max_level]);
   274       --_last_active[_max_level];
   275       _level[li]=_max_level;
   276 
   277       while(_highest_active>=0 &&
   278 	    _last_active[_highest_active]<_first[_highest_active])
   279 	_highest_active--;
   280     }
   281     
   282     ///@}
   283     
   284     ///\name Active Item on Certain Level 
   285     ///Functions for working with the active items.
   286 
   287     ///@{
   288 
   289     ///Returns an active item on level \c l.
   290     
   291     ///Returns an active item on level \c l.
   292     ///
   293     ///Returns an active item on level \c l or \ref INVALID if there is no such
   294     ///an item. (\c l must be from the range [0...\c max_level].
   295     Item activeOn(int l) const
   296     { 
   297       return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
   298     }
   299 
   300     ///Lifts the active item returned by \c activeOn() member function.
   301     
   302     ///Lifts the active item returned by \c activeOn() member function
   303     ///by one.
   304     Item liftActiveOn(int level)
   305     { 
   306       ++_level[*_last_active[level]];
   307       swap(_last_active[level]--, --_first[level+1]);
   308       if (level+1>_highest_active) ++_highest_active;
   309     }
   310 
   311     ///Lifts the active item returned by \c activeOn() member function.
   312     
   313     ///Lifts the active item returned by \c activeOn() member function
   314     ///to the given level.
   315     void liftActiveOn(int level, int new_level)
   316     { 
   317       const Item ai = *_last_active[level];
   318       
   319       copy(--_first[level+1], _last_active[level]--);
   320       for(int l=level+1;l<new_level;l++)
   321 	{
   322 	  copy(_last_active[l],_first[l]);
   323 	  copy(--_first[l+1], _last_active[l]--);
   324 	}
   325       copy(ai,_first[new_level]);
   326       _level[ai]=new_level;
   327       if (new_level>_highest_active) _highest_active=new_level;
   328     }
   329 
   330     ///Lifts the active item returned by \c activeOn() member function.
   331     
   332     ///Lifts the active item returned by \c activeOn() member function
   333     ///to the top level.
   334     void liftActiveToTop(int level)
   335     {
   336       const Item ai = *_last_active[level];
   337       
   338       copy(--_first[level+1],_last_active[level]--);
   339       for(int l=level+1;l<_max_level;l++)
   340 	{
   341 	  copy(_last_active[l],_first[l]);
   342 	  copy(--_first[l+1], _last_active[l]--);
   343 	}
   344       copy(ai,_first[_max_level]);
   345       --_last_active[_max_level];
   346       _level[ai]=_max_level;
   347 
   348       if (_highest_active==level) {
   349 	while(_highest_active>=0 && 
   350 	      _last_active[_highest_active]<_first[_highest_active]) 
   351 	  _highest_active--;
   352       }
   353     }
   354 
   355     ///@}
   356     
   357     ///Lift an active item to a higher level.
   358 
   359     ///Lift an active item to a higher level.
   360     ///\param i The item to be lifted. It must be active.
   361     ///\param new_level The new level of \c i. It must be strictly higher
   362     ///than the current level.
   363     ///
   364     void lift(Item i, int new_level) 
   365     {
   366       const int lo = _level[i];
   367       const Vit w = _where[i];
   368 
   369       copy(_last_active[lo],w);
   370       copy(--_first[lo+1],_last_active[lo]--);
   371       for(int l=lo+1;l<new_level;l++)
   372 	{
   373 	  copy(_last_active[l],_first[l]);
   374 	  copy(--_first[l+1],_last_active[l]--);
   375 	}
   376       copy(i,_first[new_level]);
   377       _level[i]=new_level;
   378       if(new_level>_highest_active) _highest_active=new_level;
   379     }
   380     
   381     ///Lift all nodes on and above a level to the top (and deactivate them).
   382 
   383     ///This function lifts all nodes on and above level \c l to \c
   384     ///maxLevel(), and also deactivates them.
   385     void liftToTop(int l) 
   386     {
   387       const Vit f=_first[l];
   388       const Vit tl=_first[_max_level];
   389       for(Vit i=f;i!=tl;++i)
   390 	_level[*i]=_max_level;
   391       for(int i=l;i<=_max_level;i++)
   392 	{
   393 	  _first[i]=f;
   394 	  _last_active[i]=f-1;
   395 	}
   396       for(_highest_active=l-1;
   397 	  _highest_active>=0 &&
   398 	    _last_active[_highest_active]<_first[_highest_active];
   399 	  _highest_active--) ;
   400     }
   401     
   402   private:
   403     int _init_lev;
   404     Vit _init_num;
   405 
   406   public:
   407 
   408     ///\name Initialization
   409     ///Using this function you can initialize the levels of the item.
   410     ///\n
   411     ///This initializatios is started with calling \c initStart().
   412     ///Then the
   413     ///items should be listed levels by levels statring with the lowest one
   414     ///(with level 0). This is done by using \c initAddItem()
   415     ///and \c initNewLevel(). Finally \c initFinish() must be called.
   416     ///The items not listed will be put on the highest level.
   417     ///@{
   418 
   419     ///Start the initialization process.
   420 
   421     void initStart() 
   422     {
   423       _init_lev=0;
   424       _init_num=_items.begin();
   425       _first[0]=_items.begin();
   426       _last_active[0]=_items.begin()-1;
   427       Vit n=_items.begin();
   428       for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)
   429 	{
   430 	  *n=i;
   431 	  _where[i]=n;
   432 	  _level[i]=_max_level;
   433 	  ++n;
   434 	}
   435     }
   436 
   437     ///Add an item to the current level.
   438 
   439     void initAddItem(Item i)
   440     { 
   441      swap(_where[i],_init_num);
   442       _level[i]=_init_lev;
   443       ++_init_num;
   444     }
   445 
   446     ///Start a new level.
   447 
   448     ///Start a new level.
   449     ///It shouldn't be used before the items on level 0 are listed.
   450     void initNewLevel() 
   451     {
   452       _init_lev++;
   453       _first[_init_lev]=_init_num;
   454       _last_active[_init_lev]=_init_num-1;
   455     }
   456 
   457     ///Finalize the initialization process.
   458 
   459     void initFinish()
   460     {
   461       for(_init_lev++;_init_lev<=_max_level;_init_lev++)
   462 	{
   463 	  _first[_init_lev]=_init_num;
   464 	  _last_active[_init_lev]=_init_num-1;
   465 	}
   466       _first[_max_level+1]=_items.begin()+_item_num;
   467       _last_active[_max_level+1]=_items.begin()+_item_num-1;
   468       _highest_active = -1;
   469     }
   470 
   471     ///@}
   472 
   473   };
   474 
   475   ///Class for handling "labels" in push-relabel type algorithms.
   476   
   477   ///A class for handling "labels" in push-relabel type algorithms.
   478   ///
   479   ///\ingroup auxdat
   480   ///Using this class you can assign "labels" (nonnegative integer numbers)
   481   ///to the edges or nodes of a graph, manipulate and query them through
   482   ///operations typically arising in "push-relabel" type algorithms.
   483   ///
   484   ///Each item is either \em active or not, and you can also choose a
   485   ///highest level active item.
   486   ///
   487   ///\sa Elevator
   488   ///
   489   ///\param Graph the underlying graph type
   490   ///\param Item Type of the items the data is assigned to (Graph::Node,
   491   ///Graph::Edge, Graph::UEdge)
   492   template <class Graph, class Item>
   493   class LinkedElevator {
   494   private:
   495 
   496     typedef Item Key;
   497     typedef int Value;
   498 
   499     typedef typename ItemSetTraits<Graph,Item>::
   500     template Map<Item>::Type ItemMap;
   501     typedef typename ItemSetTraits<Graph,Item>::
   502     template Map<int>::Type IntMap;
   503     typedef typename ItemSetTraits<Graph,Item>::
   504     template Map<bool>::Type BoolMap;
   505 
   506     const Graph &_graph;
   507     int _max_level;
   508     int _item_num;
   509     std::vector<Item> _first, _last;
   510     ItemMap _prev, _next;    
   511     int _highest_active;
   512     IntMap _level;
   513     BoolMap _active;
   514     
   515   public:
   516     ///Constructor with given maximum level.
   517 
   518     ///Constructor with given maximum level.
   519     ///
   520     ///\param g The underlying graph
   521     ///\param max_level Set the range of the possible labels to
   522     ///[0...\c max_level]
   523     LinkedElevator(const Graph& graph, int max_level) 
   524       : _graph(graph), _max_level(max_level), _item_num(_max_level), 
   525 	_first(_max_level + 1), _last(_max_level + 1),
   526 	_prev(graph), _next(graph),      
   527 	_highest_active(-1), _level(graph), _active(graph) {}
   528 
   529     ///Constructor.
   530 
   531     ///Constructor.
   532     ///
   533     ///\param g The underlying graph
   534     ///The range of the possible labels is [0...\c max_level],
   535     ///where \c max_level is equal to the number of labeled items in the graph.
   536     LinkedElevator(const Graph& graph) 
   537       : _graph(graph), _max_level(countItems<Graph, Item>(graph)), 
   538 	_item_num(_max_level), 
   539 	_first(_max_level + 1), _last(_max_level + 1),
   540 	_prev(graph, INVALID), _next(graph, INVALID),      
   541 	_highest_active(-1), _level(graph), _active(graph) {}
   542   
   543 
   544     ///Activate item \c i.
   545 
   546     ///Activate item \c i.
   547     ///\pre Item \c i shouldn't be active before.
   548     void activate(Item i) {
   549       _active.set(i, true);
   550 
   551       int level = _level[i];
   552       if (level > _highest_active) {
   553 	_highest_active = level;
   554       }
   555 
   556       if (_prev[i] == INVALID || _active[_prev[i]]) return;	    
   557       //unlace
   558       _next.set(_prev[i], _next[i]);
   559       if (_next[i] != INVALID) {
   560 	_prev.set(_next[i], _prev[i]);
   561       } else {
   562 	_last[level] = _prev[i];
   563       }
   564       //lace
   565       _next.set(i, _first[level]);
   566       _prev.set(_first[level], i);
   567       _prev.set(i, INVALID);
   568       _first[level] = i;
   569 
   570     }
   571   
   572     ///Deactivate item \c i.
   573 
   574     ///Deactivate item \c i.
   575     ///\pre Item \c i must be active before.
   576     void deactivate(Item i) {
   577       _active.set(i, false);
   578       int level = _level[i];
   579 
   580       if (_next[i] == INVALID || !_active[_next[i]])
   581 	goto find_highest_level;
   582 
   583       //unlace
   584       _prev.set(_next[i], _prev[i]);
   585       if (_prev[i] != INVALID) {
   586 	_next.set(_prev[i], _next[i]);
   587       } else {
   588 	_first[_level[i]] = _next[i];
   589       }
   590       //lace
   591       _prev.set(i, _last[level]);
   592       _next.set(_last[level], i);
   593       _next.set(i, INVALID);
   594       _last[level] = i;
   595       
   596     find_highest_level:
   597       if (level == _highest_active) {
   598 	while (_highest_active >= 0 && activeFree(_highest_active)) 
   599 	  --_highest_active;
   600       }
   601     }
   602 
   603     ///Query whether item \c i is active
   604     bool active(Item i) const { return _active[i]; }
   605     
   606     ///Return the level of item \c i.
   607     int operator[](Item i) const { return _level[i]; }
   608     
   609     ///Return the number of items on level \c l.
   610     int onLevel(int l) const {
   611       int num = 0;
   612       Item n = _first[l];
   613       while (n != INVALID) {
   614 	++num;
   615 	n = _next[n];
   616       }
   617       return num;
   618     }
   619 
   620     ///Return true if the level is empty.
   621     bool emptyLevel(int l) const {
   622       return _first[l] == INVALID;
   623     }
   624 
   625     ///Return the number of items above level \c l.
   626     int aboveLevel(int l) const {
   627       int num = 0;
   628       for (int level = l + 1; level < _max_level; ++level)
   629 	num += onLevel(level);
   630       return num;
   631     }
   632 
   633     ///Return the number of active items on level \c l.
   634     int activesOnLevel(int l) const {
   635       int num = 0;
   636       Item n = _first[l];
   637       while (n != INVALID && _active[n]) {
   638 	++num;
   639 	n = _next[n];
   640       }
   641       return num;
   642     }
   643 
   644     ///Return true if there is not active item on level \c l.
   645     bool activeFree(int l) const {
   646       return _first[l] == INVALID || !_active[_first[l]];
   647     }
   648 
   649     ///Return the maximum allowed level.
   650     int maxLevel() const {
   651       return _max_level;
   652     }    
   653 
   654     ///\name Highest Active Item
   655     ///Functions for working with the highest level
   656     ///active item.
   657 
   658     ///@{
   659 
   660     ///Return a highest level active item.
   661   
   662     ///Return a highest level active item.
   663     ///
   664     ///\return the highest level active item or INVALID if there is no
   665     ///active item.
   666     Item highestActive() const {
   667       return _highest_active >= 0 ? _first[_highest_active] : INVALID;
   668     }
   669 
   670     ///Return a highest active level.
   671 
   672     ///Return a highest active level.
   673     ///
   674     ///\return the level of the highest active item or -1 if there is
   675     ///no active item.
   676     int highestActiveLevel() const {
   677       return _highest_active;
   678     }
   679 
   680     ///Lift the highest active item by one.
   681 
   682     ///Lift the item returned by highestActive() by one.
   683     ///
   684     void liftHighestActive() {
   685       Item i = _first[_highest_active];
   686       if (_next[i] != INVALID) {
   687 	_prev.set(_next[i], INVALID);
   688 	_first[_highest_active] = _next[i]; 
   689       } else {
   690 	_first[_highest_active] = INVALID;
   691 	_last[_highest_active] = INVALID;
   692       }
   693       _level.set(i, ++_highest_active);
   694       if (_first[_highest_active] == INVALID) {
   695 	_first[_highest_active] = i;
   696 	_last[_highest_active] = i;
   697 	_prev.set(i, INVALID);
   698 	_next.set(i, INVALID);
   699       } else {
   700 	_prev.set(_first[_highest_active], i);
   701 	_next.set(i, _first[_highest_active]);
   702 	_first[_highest_active] = i;
   703       }
   704     }
   705 
   706     ///Lift the highest active item.
   707 
   708     ///Lift the item returned by highestActive() to level \c new_level.
   709     ///
   710     ///\warning \c new_level must be strictly higher
   711     ///than the current level.
   712     ///
   713     void liftHighestActive(int new_level) {
   714       Item i = _first[_highest_active];
   715       if (_next[i] != INVALID) {
   716 	_prev.set(_next[i], INVALID);
   717 	_first[_highest_active] = _next[i]; 
   718       } else {
   719 	_first[_highest_active] = INVALID;
   720 	_last[_highest_active] = INVALID;
   721       }
   722       _level.set(i, _highest_active = new_level);
   723       if (_first[_highest_active] == INVALID) {
   724 	_first[_highest_active] = _last[_highest_active] = i;
   725 	_prev.set(i, INVALID);
   726 	_next.set(i, INVALID);
   727       } else {
   728 	_prev.set(_first[_highest_active], i);
   729 	_next.set(i, _first[_highest_active]);
   730 	_first[_highest_active] = i;
   731       }
   732     }
   733 
   734     ///Lift the highest active to top.
   735 
   736     ///Lift the item returned by highestActive() to the top level and
   737     ///deactivates the node.
   738     ///
   739     void liftHighestActiveToTop() {
   740       Item i = _first[_highest_active];
   741       _level.set(i, _max_level);
   742       if (_next[i] != INVALID) {
   743 	_prev.set(_next[i], INVALID);
   744 	_first[_highest_active] = _next[i]; 
   745       } else {
   746 	_first[_highest_active] = INVALID;
   747 	_last[_highest_active] = INVALID;
   748       }
   749       while (_highest_active >= 0 && activeFree(_highest_active)) 
   750 	--_highest_active;
   751     }
   752     
   753     ///@}
   754 
   755     ///\name Active Item on Certain Level 
   756     ///Functions for working with the active items.
   757 
   758     ///@{
   759 
   760     ///Returns an active item on level \c l.
   761     
   762     ///Returns an active item on level \c l.
   763     ///
   764     ///Returns an active item on level \c l or \ref INVALID if there is no such
   765     ///an item. (\c l must be from the range [0...\c max_level].
   766     Item activeOn(int l) const
   767     { 
   768       return _active[_first[l]] ? _first[l] : INVALID;
   769     }
   770 
   771     ///Lifts the active item returned by \c activeOn() member function.
   772     
   773     ///Lifts the active item returned by \c activeOn() member function
   774     ///by one.
   775     Item liftActiveOn(int l)
   776     { 
   777       Item i = _first[l];
   778       if (_next[i] != INVALID) {
   779 	_prev.set(_next[i], INVALID);
   780 	_first[l] = _next[i]; 
   781       } else {
   782 	_first[l] = INVALID;
   783 	_last[l] = INVALID;
   784       }
   785       _level.set(i, ++l);
   786       if (_first[l] == INVALID) {
   787 	_first[l] = _last[l] = i;
   788 	_prev.set(i, INVALID);
   789 	_next.set(i, INVALID);
   790       } else {
   791 	_prev.set(_first[l], i);
   792 	_next.set(i, _first[l]);
   793 	_first[l] = i;
   794       }
   795       if (_highest_active < l) {
   796 	_highest_active = l;
   797       }
   798     }
   799 
   800     /// \brief Lifts the active item returned by \c activeOn() member function.
   801     ///    
   802     /// Lifts the active item returned by \c activeOn() member function
   803     /// to the given level.
   804     void liftActiveOn(int l, int new_level)
   805     { 
   806       Item i = _first[l];
   807       if (_next[i] != INVALID) {
   808 	_prev.set(_next[i], INVALID);
   809 	_first[l] = _next[i]; 
   810       } else {
   811 	_first[l] = INVALID;
   812 	_last[l] = INVALID;
   813       }
   814       _level.set(i, l = new_level);
   815       if (_first[l] == INVALID) {
   816 	_first[l] = _last[l] = i;
   817 	_prev.set(i, INVALID);
   818 	_next.set(i, INVALID);
   819       } else {
   820 	_prev.set(_first[l], i);
   821 	_next.set(i, _first[l]);
   822 	_first[l] = i;
   823       }
   824       if (_highest_active < l) {
   825 	_highest_active = l;
   826       }
   827     }
   828 
   829     ///Lifts the active item returned by \c activeOn() member function.
   830     
   831     ///Lifts the active item returned by \c activeOn() member function
   832     ///to the top level.
   833     void liftActiveToTop(int l)
   834     { 
   835       Item i = _first[l];
   836       if (_next[i] != INVALID) {
   837 	_prev.set(_next[i], INVALID);
   838 	_first[l] = _next[i]; 
   839       } else {
   840 	_first[l] = INVALID;
   841 	_last[l] = INVALID;
   842       }
   843       _level.set(i, _max_level);
   844       if (l == _highest_active) {
   845 	while (_highest_active >= 0 && activeFree(_highest_active)) 
   846 	  --_highest_active;
   847       }
   848     }
   849 
   850     ///@}
   851     
   852     /// \brief Lift an active item to a higher level.
   853     ///
   854     /// Lift an active item to a higher level.
   855     /// \param i The item to be lifted. It must be active.
   856     /// \param new_level The new level of \c i. It must be strictly higher
   857     /// than the current level.
   858     ///
   859     void lift(Item i, int new_level) {
   860       if (_next[i] != INVALID) {
   861 	_prev.set(_next[i], _prev[i]);
   862       } else {
   863 	_last[new_level] = _prev[i];
   864       }
   865       if (_prev[i] != INVALID) {
   866 	_next.set(_prev[i], _next[i]);
   867       } else {
   868 	_first[new_level] = _next[i];
   869       }
   870       _level.set(i, new_level);
   871       if (_first[new_level] == INVALID) {
   872 	_first[new_level] = _last[new_level] = i;
   873 	_prev.set(i, INVALID);
   874 	_next.set(i, INVALID);
   875       } else {
   876 	_prev.set(_first[new_level], i);
   877 	_next.set(i, _first[new_level]);
   878 	_first[new_level] = i;
   879       }
   880       if (_highest_active < new_level) {
   881 	_highest_active = new_level;
   882       }
   883     }
   884     
   885     ///Lift all nodes on and above a level to the top (and deactivate them).
   886 
   887     ///This function lifts all nodes on and above level \c l to \c
   888     ///maxLevel(), and also deactivates them. 
   889     void liftToTop(int l)  {
   890       for (int i = l + 1; _first[i] != INVALID; ++i) {
   891 	Item n = _first[i];
   892 	while (n != INVALID) {
   893 	  _level.set(n, _max_level);
   894 	  n = _next[n];
   895 	}
   896 	_first[i] = INVALID;
   897 	_last[i] = INVALID;
   898       }
   899       if (_highest_active > l - 1) {
   900 	_highest_active = l - 1;
   901 	while (_highest_active >= 0 && activeFree(_highest_active)) 
   902 	  --_highest_active;
   903       }
   904     }
   905     
   906   private:
   907 
   908     int _init_level;
   909 
   910   public:
   911 
   912     ///\name Initialization
   913     ///Using this function you can initialize the levels of the item.
   914     ///\n
   915     ///This initializatios is started with calling \c initStart().
   916     ///Then the
   917     ///items should be listed levels by levels statring with the lowest one
   918     ///(with level 0). This is done by using \c initAddItem()
   919     ///and \c initNewLevel(). Finally \c initFinish() must be called.
   920     ///The items not listed will be put on the highest level.
   921     ///@{
   922 
   923     ///Start the initialization process.
   924 
   925     void initStart() {
   926       
   927       for (int i = 0; i <= _max_level; ++i) {
   928 	_first[i] = _last[i] = INVALID;
   929       }
   930       _init_level = 0;
   931       for(typename ItemSetTraits<Graph,Item>::ItemIt i(_graph); 
   932 	  i != INVALID; ++i) {
   933 	_level.set(i, _max_level);
   934       }
   935     }
   936 
   937     ///Add an item to the current level.
   938 
   939     void initAddItem(Item i) {
   940       _level.set(i, _init_level);
   941       if (_last[_init_level] == INVALID) {
   942 	_first[_init_level] = i;
   943 	_last[_init_level] = i;
   944 	_prev.set(i, INVALID);
   945 	_next.set(i, INVALID);
   946       } else {
   947 	_prev.set(i, _last[_init_level]);
   948 	_next.set(i, INVALID);
   949 	_next.set(_last[_init_level], i);
   950 	_last[_init_level] = i;
   951       }
   952     }
   953 
   954     ///Start a new level.
   955 
   956     ///Start a new level.
   957     ///It shouldn't be used before the items on level 0 are listed.
   958     void initNewLevel() {
   959       ++_init_level;
   960     }
   961 
   962     ///Finalize the initialization process.
   963 
   964     void initFinish() {
   965       _highest_active = -1;
   966     }
   967 
   968     ///@}
   969 
   970   };
   971 
   972 
   973 } //END OF NAMESPACE LEMON
   974 
   975 #endif
   976