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