///\sa LinkedElevator

   ///

     ///Return true if the level is empty.

     bool emptyLevel(int l) const

     {

       return _first[l+1]-_first[l]==0;

     }

     }

     ///Return true if there is not active item on level \c l.

     bool activeFree(int l) const

     {

       return _last_active[l]<_first[l];

       _highest_active = -1;

   ///Class for handling "labels" in push-relabel type algorithms.

   ///A class for handling "labels" in push-relabel type algorithms.

   ///

   ///\ingroup auxdat

   ///Using this class you can assign "labels" (nonnegative integer numbers)

   ///to the edges or nodes of a graph, manipulate and query them through

   ///operations typically arising in "push-relabel" type algorithms.

   ///

   ///Each item is either \em active or not, and you can also choose a

   ///highest level active item.

   ///

   ///\sa Elevator

   ///

   ///\param Graph the underlying graph type

   ///\param Item Type of the items the data is assigned to (Graph::Node,

   ///Graph::Edge, Graph::UEdge)

   template <class Graph, class Item>

   class LinkedElevator {

   private:

     typedef Item Key;

     typedef int Value;

     typedef typename ItemSetTraits<Graph,Item>::

     template Map<Item>::Type ItemMap;

     typedef typename ItemSetTraits<Graph,Item>::

     template Map<int>::Type IntMap;

     typedef typename ItemSetTraits<Graph,Item>::

     template Map<bool>::Type BoolMap;

     const Graph &_graph;

     int _max_level;

     int _item_num;

     std::vector<Item> _first, _last;

     ItemMap _prev, _next;    

     int _highest_active;

     IntMap _level;

     BoolMap _active;

   public:

     ///Constructor with given maximum level.

     ///Constructor with given maximum level.

     ///

     ///\param g The underlying graph

     ///\param max_level Set the range of the possible labels to

     ///[0...\c max_level]

     LinkedElevator(const Graph& graph, int max_level) 

       : _graph(graph), _max_level(max_level), _item_num(_max_level), 

 	_first(_max_level + 1), _last(_max_level + 1),

 	_prev(graph), _next(graph),      

 	_highest_active(-1), _level(graph), _active(graph) {}

     ///Constructor.

     ///Constructor.

     ///

     ///\param g The underlying graph

     ///The range of the possible labels is [0...\c max_level],

     ///where \c max_level is equal to the number of labeled items in the graph.

     LinkedElevator(const Graph& graph) 

       : _graph(graph), _max_level(countItems<Graph, Item>(graph)), 

 	_item_num(_max_level), 

 	_first(_max_level + 1), _last(_max_level + 1),

 	_prev(graph, INVALID), _next(graph, INVALID),      

 	_highest_active(-1), _level(graph), _active(graph) {}

     ///Activate item \c i.

     ///Activate item \c i.

     ///\pre Item \c i shouldn't be active before.

     void activate(Item i) {

       _active.set(i, true);

       int level = _level[i];

       if (level > _highest_active) {

 	_highest_active = level;

       }

       if (_prev[i] == INVALID || _active[_prev[i]]) return;	    

       //unlace

       _next.set(_prev[i], _next[i]);

       if (_next[i] != INVALID) {

 	_prev.set(_next[i], _prev[i]);

       } else {

 	_last[level] = _prev[i];

       }

       //lace

       _next.set(i, _first[level]);

       _prev.set(_first[level], i);

       _prev.set(i, INVALID);

       _first[level] = i;

     }

     ///Deactivate item \c i.

     ///Deactivate item \c i.

     ///\pre Item \c i must be active before.

     void deactivate(Item i) {

       _active.set(i, false);

       int level = _level[i];

       if (_next[i] == INVALID || !_active[_next[i]])

 	goto find_highest_level;

       //unlace

       _prev.set(_next[i], _prev[i]);

       if (_prev[i] != INVALID) {

 	_next.set(_prev[i], _next[i]);

       } else {

 	_first[_level[i]] = _next[i];

       }

       //lace

       _prev.set(i, _last[level]);

       _next.set(_last[level], i);

       _next.set(i, INVALID);

       _last[level] = i;

     find_highest_level:

       if (level == _highest_active) {

 	while (_highest_active >= 0 && activeFree(_highest_active)) 

 	  --_highest_active;

       }

     }

     ///Query whether item \c i is active

     bool active(Item i) const { return _active[i]; }

     ///Return the level of item \c i.

     int operator[](Item i) const { return _level[i]; }

     ///Return the number of items on level \c l.

     int onLevel(int l) const {

       int num = 0;

       Item n = _first[l];

       while (n != INVALID) {

 	++num;

 	n = _next[n];

       }

       return num;

     }

     ///Return true if the level is empty.

     bool emptyLevel(int l) const {

       return _first[l] == INVALID;

     }

     ///Return the number of items above level \c l.

     int aboveLevel(int l) const {

       int num = 0;

       for (int level = l + 1; level < _max_level; ++level)

 	num += onLevel(level);

       return num;

     }

     ///Return the number of active items on level \c l.

     int activesOnLevel(int l) const {

       int num = 0;

       Item n = _first[l];

       while (n != INVALID && _active[n]) {

 	++num;

 	n = _next[n];

       }

       return num;

     }

     ///Return true if there is not active item on level \c l.

     bool activeFree(int l) const {

       return _first[l] == INVALID || !_active[_first[l]];

     }

     ///Return the maximum allowed level.

     int maxLevel() const {

       return _max_level;

     }    

     ///\name Highest Active Item

     ///Functions for working with the highest level

     ///active item.

     ///@{

     ///Return a highest level active item.

     ///Return a highest level active item.

     ///

     ///\return the highest level active item or INVALID if there is no

     ///active item.

     Item highestActive() const {

       return _highest_active >= 0 ? _first[_highest_active] : INVALID;

     }

     ///Return a highest active level.

     ///Return a highest active level.

     ///

     ///\return the level of the highest active item or -1 if there is

     ///no active item.

     int highestActiveLevel() const {

       return _highest_active;

     }

     ///Lift the highest active item by one.

     ///Lift the item returned by highestActive() by one.

     ///

     void liftHighestActive() {

       Item i = _first[_highest_active];

       if (_next[i] != INVALID) {

 	_prev.set(_next[i], INVALID);

 	_first[_highest_active] = _next[i]; 

       } else {

 	_first[_highest_active] = INVALID;

 	_last[_highest_active] = INVALID;

       }

       _level.set(i, ++_highest_active);

       if (_first[_highest_active] == INVALID) {

 	_first[_highest_active] = i;

 	_last[_highest_active] = i;

 	_prev.set(i, INVALID);

 	_next.set(i, INVALID);

       } else {

 	_prev.set(_first[_highest_active], i);

 	_next.set(i, _first[_highest_active]);

 	_first[_highest_active] = i;

       }

     }

     ///Lift the highest active item.

     ///Lift the item returned by highestActive() to level \c new_level.

     ///

     ///\warning \c new_level must be strictly higher

     ///than the current level.

     ///

     void liftHighestActive(int new_level) {

       Item i = _first[_highest_active];

       if (_next[i] != INVALID) {

 	_prev.set(_next[i], INVALID);

 	_first[_highest_active] = _next[i]; 

       } else {

 	_first[_highest_active] = INVALID;

 	_last[_highest_active] = INVALID;

       }

       _level.set(i, _highest_active = new_level);

       if (_first[_highest_active] == INVALID) {

 	_first[_highest_active] = _last[_highest_active] = i;

 	_prev.set(i, INVALID);

 	_next.set(i, INVALID);

       } else {

 	_prev.set(_first[_highest_active], i);

 	_next.set(i, _first[_highest_active]);

 	_first[_highest_active] = i;

       }

     }

     ///Lift the highest active to top.

     ///Lift the item returned by highestActive() to the top level and

     ///deactivates the node.

     ///

     void liftHighestActiveToTop() {

       Item i = _first[_highest_active];

       _level.set(i, _max_level);

       if (_next[i] != INVALID) {

 	_prev.set(_next[i], INVALID);

 	_first[_highest_active] = _next[i]; 

       } else {

 	_first[_highest_active] = INVALID;

 	_last[_highest_active] = INVALID;

       }

       while (_highest_active >= 0 && activeFree(_highest_active)) 

 	--_highest_active;

     }

     ///@}

     ///\name Active Item on Certain Level 

     ///Functions for working with the active items.

     ///@{

     ///Returns an active item on level \c l.

     ///Returns an active item on level \c l.

     ///

     ///Returns an active item on level \c l or \ref INVALID if there is no such

     ///an item. (\c l must be from the range [0...\c max_level].

     Item activeOn(int l) const

     { 

       return _active[_first[l]] ? _first[l] : INVALID;

     }

     ///Lifts the active item returned by \c activeOn() member function.

     ///Lifts the active item returned by \c activeOn() member function

     ///by one.

     Item liftActiveOn(int l)

     { 

       Item i = _first[l];

       if (_next[i] != INVALID) {

 	_prev.set(_next[i], INVALID);

 	_first[l] = _next[i]; 

       } else {

 	_first[l] = INVALID;

 	_last[l] = INVALID;

       }

       _level.set(i, ++l);

       if (_first[l] == INVALID) {

 	_first[l] = _last[l] = i;

 	_prev.set(i, INVALID);

 	_next.set(i, INVALID);

       } else {

 	_prev.set(_first[l], i);

 	_next.set(i, _first[l]);

 	_first[l] = i;

       }

       if (_highest_active < l) {

 	_highest_active = l;

       }

     }

     /// \brief Lifts the active item returned by \c activeOn() member function.

     ///    

     /// Lifts the active item returned by \c activeOn() member function

     /// to the given level.

     void liftActiveOn(int l, int new_level)

     { 

       Item i = _first[l];

       if (_next[i] != INVALID) {

 	_prev.set(_next[i], INVALID);

 	_first[l] = _next[i]; 

       } else {

 	_first[l] = INVALID;

 	_last[l] = INVALID;

       }

       _level.set(i, l = new_level);

       if (_first[l] == INVALID) {

 	_first[l] = _last[l] = i;

 	_prev.set(i, INVALID);

 	_next.set(i, INVALID);

       } else {

 	_prev.set(_first[l], i);

 	_next.set(i, _first[l]);

 	_first[l] = i;

       }

       if (_highest_active < l) {

 	_highest_active = l;

       }

     }

     ///Lifts the active item returned by \c activeOn() member function.

     ///Lifts the active item returned by \c activeOn() member function

     ///to the top level.

     void liftActiveToTop(int l)

     { 

       Item i = _first[l];

       if (_next[i] != INVALID) {

 	_prev.set(_next[i], INVALID);

 	_first[l] = _next[i]; 

       } else {

 	_first[l] = INVALID;

 	_last[l] = INVALID;

       }

       _level.set(i, _max_level);

       if (l == _highest_active) {

 	while (_highest_active >= 0 && activeFree(_highest_active)) 

 	  --_highest_active;

       }

     }

     ///@}

     /// \brief Lift an active item to a higher level.

     ///

     /// Lift an active item to a higher level.

     /// \param i The item to be lifted. It must be active.

     /// \param new_level The new level of \c i. It must be strictly higher

     /// than the current level.

     ///

     void lift(Item i, int new_level) {

       if (_next[i] != INVALID) {

 	_prev.set(_next[i], _prev[i]);

       } else {

 	_last[new_level] = _prev[i];

       }

       if (_prev[i] != INVALID) {

 	_next.set(_prev[i], _next[i]);

       } else {

 	_first[new_level] = _next[i];

       }

       _level.set(i, new_level);

       if (_first[new_level] == INVALID) {

 	_first[new_level] = _last[new_level] = i;

 	_prev.set(i, INVALID);

 	_next.set(i, INVALID);

       } else {

 	_prev.set(_first[new_level], i);

 	_next.set(i, _first[new_level]);

 	_first[new_level] = i;

       }

       if (_highest_active < new_level) {

 	_highest_active = new_level;

       }

     }

     ///Lift all nodes on and above a level to the top (and deactivate them).

     ///This function lifts all nodes on and above level \c l to \c

     ///maxLevel(), and also deactivates them. 

     void liftToTop(int l)  {

       for (int i = l + 1; _first[i] != INVALID; ++i) {

 	Item n = _first[i];

 	while (n != INVALID) {

 	  _level.set(n, _max_level);

 	  n = _next[n];

 	}

 	_first[i] = INVALID;

 	_last[i] = INVALID;

       }

       if (_highest_active > l - 1) {

 	_highest_active = l - 1;

 	while (_highest_active >= 0 && activeFree(_highest_active)) 

 	  --_highest_active;

       }

     }

   private:

     int _init_level;

   public:

     ///\name Initialization

     ///Using this function you can initialize the levels of the item.

     ///\n

     ///This initializatios is started with calling \c initStart().

     ///Then the

     ///items should be listed levels by levels statring with the lowest one

     ///(with level 0). This is done by using \c initAddItem()

     ///and \c initNewLevel(). Finally \c initFinish() must be called.

     ///The items not listed will be put on the highest level.

     ///@{

     ///Start the initialization process.

     void initStart() {

       for (int i = 0; i <= _max_level; ++i) {

 	_first[i] = _last[i] = INVALID;

       }

       _init_level = 0;

       for(typename ItemSetTraits<Graph,Item>::ItemIt i(_graph); 

 	  i != INVALID; ++i) {

 	_level.set(i, _max_level);

       }

     }

     ///Add an item to the current level.

     void initAddItem(Item i) {

       _level.set(i, _init_level);

       if (_last[_init_level] == INVALID) {

 	_first[_init_level] = i;

 	_last[_init_level] = i;

 	_prev.set(i, INVALID);

 	_next.set(i, INVALID);

       } else {

 	_prev.set(i, _last[_init_level]);

 	_next.set(i, INVALID);

 	_next.set(_last[_init_level], i);

 	_last[_init_level] = i;

       }

     }

     ///Start a new level.

     ///Start a new level.

     ///It shouldn't be used before the items on level 0 are listed.

     void initNewLevel() {

       ++_init_level;

     }

     ///Finalize the initialization process.

     void initFinish() {

       _highest_active = -1;

     }

     ///@}

   };