alpar@2346: /* -*- C++ -*-
alpar@2346:  *
alpar@2346:  * This file is a part of LEMON, a generic C++ optimization library
alpar@2346:  *
alpar@2553:  * Copyright (C) 2003-2008
alpar@2346:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@2346:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@2346:  *
alpar@2346:  * Permission to use, modify and distribute this software is granted
alpar@2346:  * provided that this copyright notice appears in all copies. For
alpar@2346:  * precise terms see the accompanying LICENSE file.
alpar@2346:  *
alpar@2346:  * This software is provided "AS IS" with no warranty of any kind,
alpar@2346:  * express or implied, and with no claim as to its suitability for any
alpar@2346:  * purpose.
alpar@2346:  *
alpar@2346:  */
alpar@2346: 
alpar@2346: #ifndef LEMON_ELEVATOR_H
alpar@2346: #define LEMON_ELEVATOR_H
alpar@2346: 
alpar@2346: ///\ingroup auxdat
alpar@2346: ///\file
alpar@2346: ///\brief Elevator class
alpar@2346: ///
alpar@2346: ///Elevator class implements an efficient data structure
alpar@2346: ///for labeling items in push-relabel type algorithms.
alpar@2346: ///
alpar@2346: 
alpar@2346: #include <test/test_tools.h>
alpar@2346: namespace lemon {
alpar@2346: 
alpar@2347:   ///Class for handling "labels" in push-relabel type algorithms.
alpar@2346:   
alpar@2347:   ///A class for handling "labels" in push-relabel type algorithms.
alpar@2346:   ///
alpar@2346:   ///\ingroup auxdat
alpar@2352:   ///Using this class you can assign "labels" (nonnegative integer numbers)
alpar@2346:   ///to the edges or nodes of a graph, manipulate and query them through
alpar@2346:   ///operations typically arising in "push-relabel" type algorithms.
alpar@2346:   ///
alpar@2346:   ///Each item is either \em active or not, and you can also choose a
alpar@2346:   ///highest level active item.
alpar@2346:   ///
deba@2512:   ///\sa LinkedElevator
deba@2512:   ///
alpar@2346:   ///\param Graph the underlying graph type
alpar@2346:   ///\param Item Type of the items the data is assigned to (Graph::Node,
alpar@2346:   ///Graph::Edge, Graph::UEdge)
alpar@2346:   template<class Graph, class Item>
alpar@2346:   class Elevator 
alpar@2346:   {
deba@2518:   public:
deba@2512: 
deba@2512:     typedef Item Key;
deba@2512:     typedef int Value;
deba@2512: 
deba@2518:   private:
deba@2518: 
alpar@2346:     typedef typename std::vector<Item>::iterator Vit;
deba@2512:     typedef typename ItemSetTraits<Graph,Item>::template Map<Vit>::Type VitMap;
deba@2512:     typedef typename ItemSetTraits<Graph,Item>::template Map<int>::Type IntMap;
alpar@2346: 
alpar@2346:     const Graph &_g;
alpar@2346:     int _max_level;
alpar@2346:     int _item_num;
alpar@2346:     VitMap _where;
alpar@2346:     IntMap _level;
alpar@2346:     std::vector<Item> _items;
alpar@2346:     std::vector<Vit> _first;
alpar@2346:     std::vector<Vit> _last_active;
alpar@2346: 
alpar@2346:     int _highest_active;
alpar@2346: 
alpar@2346:     void copy(Item i, Vit p)
alpar@2346:     {
alpar@2346:       _where[*p=i]=p;
alpar@2346:     }
alpar@2346:     void copy(Vit s, Vit p)
alpar@2346:     {
alpar@2346:       if(s!=p) 
alpar@2346: 	{
alpar@2346: 	  Item i=*s;
alpar@2346: 	  *p=i;
alpar@2346: 	  _where[i]=p;
alpar@2346: 	}
alpar@2346:     }
alpar@2346:     void swap(Vit i, Vit j)
alpar@2346:     {
alpar@2346:       Item ti=*i;
alpar@2346:       Vit ct = _where[ti];
alpar@2346:       _where[ti]=_where[*i=*j];
alpar@2346:       _where[*j]=ct;
alpar@2346:       *j=ti;
alpar@2346:     }
alpar@2346:     
alpar@2346:   public:
deba@2512:         
alpar@2346:     ///Constructor with given maximum level.
alpar@2346: 
alpar@2346:     ///Constructor with given maximum level.
alpar@2346:     ///
alpar@2346:     ///\param g The underlying graph
alpar@2346:     ///\param max_level Set the range of the possible labels to
alpar@2346:     ///[0...\c max_level]
alpar@2346:     Elevator(const Graph &g,int max_level) :
alpar@2346:       _g(g),
alpar@2346:       _max_level(max_level),
alpar@2346:       _item_num(_max_level),
alpar@2346:       _where(g),
alpar@2346:       _level(g,0),
alpar@2346:       _items(_max_level),
alpar@2346:       _first(_max_level+2),
alpar@2346:       _last_active(_max_level+2),
alpar@2346:       _highest_active(-1) {}
alpar@2346:     ///Constructor.
alpar@2346: 
alpar@2346:     ///Constructor.
alpar@2346:     ///
alpar@2346:     ///\param g The underlying graph
alpar@2346:     ///The range of the possible labels is [0...\c max_level],
alpar@2346:     ///where \c max_level is equal to the number of labeled items in the graph.
alpar@2346:     Elevator(const Graph &g) :
alpar@2346:       _g(g),
alpar@2346:       _max_level(countItems<Graph, Item>(g)),
alpar@2346:       _item_num(_max_level),
alpar@2346:       _where(g),
alpar@2346:       _level(g,0),
alpar@2346:       _items(_max_level),
alpar@2346:       _first(_max_level+2),
alpar@2346:       _last_active(_max_level+2),
alpar@2346:       _highest_active(-1)
alpar@2346:     {
alpar@2346:     }
deba@2512:     
alpar@2346:     ///Activate item \c i.
alpar@2373: 
alpar@2373:     ///Activate item \c i.
alpar@2373:     ///\pre Item \c i shouldn't be active before.
alpar@2346:     void activate(Item i)
alpar@2346:     {
alpar@2346:       const int l=_level[i];
alpar@2346:       swap(_where[i],++_last_active[l]);
alpar@2346:       if(l>_highest_active) _highest_active=l;
alpar@2346:     }
alpar@2346:   
alpar@2346:     ///Deactivate item \c i.
alpar@2373: 
alpar@2373:     ///Deactivate item \c i.
alpar@2373:     ///\pre Item \c i must be active before.
alpar@2346:     void deactivate(Item i)  
alpar@2346:     {
alpar@2346:       swap(_where[i],_last_active[_level[i]]--);
alpar@2346:       while(_highest_active>=0 &&
alpar@2346: 	    _last_active[_highest_active]<_first[_highest_active])
alpar@2346: 	_highest_active--;
alpar@2346:     }
alpar@2346: 
alpar@2346:     ///Query whether item \c i is active
alpar@2346:     bool active(Item i) const { return _where[i]<=_last_active[_level[i]]; }
alpar@2346:     
alpar@2346:     ///Return the level of item \c i.
alpar@2346:     int operator[](Item i) const { return _level[i]; }
alpar@2346: 
alpar@2346:     ///Return the number of items on level \c l.
alpar@2348:     int onLevel(int l) const
alpar@2346:     {
alpar@2346:       return _first[l+1]-_first[l];
alpar@2346:     }
deba@2512:     ///Return true if the level is empty.
deba@2512:     bool emptyLevel(int l) const
deba@2512:     {
deba@2512:       return _first[l+1]-_first[l]==0;
deba@2512:     }
alpar@2348:     ///Return the number of items above level \c l.
alpar@2348:     int aboveLevel(int l) const
alpar@2348:     {
alpar@2348:       return _first[_max_level+1]-_first[l+1];
alpar@2348:     }
alpar@2346:     ///Return the number of active items on level \c l.
alpar@2348:     int activesOnLevel(int l) const
alpar@2346:     {
alpar@2346:       return _last_active[l]-_first[l]+1;
alpar@2346:     }
deba@2512:     ///Return true if there is not active item on level \c l.
deba@2512:     bool activeFree(int l) const
deba@2512:     {
deba@2512:       return _last_active[l]<_first[l];
deba@2512:     }
alpar@2346:     ///Return the maximum allowed level.
alpar@2346:     int maxLevel() const 
alpar@2346:     {
alpar@2346:       return _max_level;
alpar@2346:     }    
alpar@2346: 
alpar@2346:     ///\name Highest Active Item
alpar@2346:     ///Functions for working with the highest level
alpar@2346:     ///active item.
alpar@2346: 
alpar@2346:     ///@{
alpar@2346: 
alpar@2346:     ///Return a highest level active item.
alpar@2346:   
alpar@2346:     ///Return a highest level active item.
alpar@2346:     ///
alpar@2346:     ///\return the highest level active item or INVALID if there is no active
alpar@2346:     ///item.
alpar@2346:     Item highestActive() const 
alpar@2346:     {
alpar@2346:       return _highest_active>=0?*_last_active[_highest_active]:INVALID;
alpar@2346:     }
alpar@2346: 
alpar@2346:     ///Return a highest active level.
alpar@2346: 
alpar@2346:     ///Return a highest active level.
alpar@2346:     ///
alpar@2346:     ///\return the level of the highest active item or -1 if there is no active
alpar@2346:     ///item.
athos@2349:     int highestActiveLevel() const 
alpar@2346:     {
alpar@2346:       return _highest_active;
alpar@2346:     }
alpar@2346: 
alpar@2346:     ///Lift the highest active item by one.
alpar@2346: 
alpar@2346:     ///Lift the item returned by highestActive() by one.
alpar@2346:     ///
alpar@2346:     void liftHighestActive() 
alpar@2346:     {
alpar@2346:       ++_level[*_last_active[_highest_active]];
alpar@2346:       swap(_last_active[_highest_active]--,_last_active[_highest_active+1]);
alpar@2346:       --_first[++_highest_active];
alpar@2346:     }
alpar@2346: 
alpar@2346:     ///Lift the highest active item.
alpar@2346: 
alpar@2346:     ///Lift the item returned by highestActive() to level \c new_level.
alpar@2346:     ///
alpar@2348:     ///\warning \c new_level must be strictly higher
alpar@2348:     ///than the current level.
alpar@2346:     ///
deba@2512:     void liftHighestActive(int new_level) 
alpar@2346:     {
alpar@2346:       const Item li = *_last_active[_highest_active];
alpar@2346:       
alpar@2346:       copy(--_first[_highest_active+1],_last_active[_highest_active]--);
alpar@2346:       for(int l=_highest_active+1;l<new_level;l++)
alpar@2346: 	{
alpar@2346: 	  copy(--_first[l+1],_first[l]);
alpar@2346: 	  --_last_active[l];
alpar@2346: 	}
alpar@2346:       copy(li,_first[new_level]);
alpar@2346:       _level[li]=new_level;
alpar@2348:       _highest_active=new_level;
alpar@2346:     }
deba@2512: 
deba@2512:     ///Lift the highest active item.
deba@2512: 
deba@2512:     ///Lift the item returned by highestActive() to the top level and
deba@2512:     ///deactivates it.
deba@2512:     ///
deba@2512:     ///\warning \c new_level must be strictly higher
deba@2512:     ///than the current level.
deba@2512:     ///
deba@2512:     void liftHighestActiveToTop() 
deba@2512:     {
deba@2512:       const Item li = *_last_active[_highest_active];
deba@2512:       
deba@2512:       copy(--_first[_highest_active+1],_last_active[_highest_active]--);
deba@2512:       for(int l=_highest_active+1;l<_max_level;l++)
deba@2512: 	{
deba@2512: 	  copy(--_first[l+1],_first[l]);
deba@2512: 	  --_last_active[l];
deba@2512: 	}
deba@2512:       copy(li,_first[_max_level]);
deba@2512:       --_last_active[_max_level];
deba@2512:       _level[li]=_max_level;
deba@2512: 
deba@2512:       while(_highest_active>=0 &&
deba@2512: 	    _last_active[_highest_active]<_first[_highest_active])
deba@2512: 	_highest_active--;
deba@2512:     }
alpar@2346:     
alpar@2346:     ///@}
alpar@2346:     
deba@2512:     ///\name Active Item on Certain Level 
deba@2512:     ///Functions for working with the active items.
deba@2512: 
deba@2512:     ///@{
deba@2512: 
deba@2512:     ///Returns an active item on level \c l.
deba@2512:     
deba@2512:     ///Returns an active item on level \c l.
deba@2512:     ///
deba@2512:     ///Returns an active item on level \c l or \ref INVALID if there is no such
deba@2512:     ///an item. (\c l must be from the range [0...\c max_level].
deba@2512:     Item activeOn(int l) const
deba@2512:     { 
deba@2512:       return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
deba@2512:     }
deba@2512: 
deba@2512:     ///Lifts the active item returned by \c activeOn() member function.
deba@2512:     
deba@2512:     ///Lifts the active item returned by \c activeOn() member function
deba@2512:     ///by one.
deba@2512:     Item liftActiveOn(int level)
deba@2512:     { 
deba@2512:       ++_level[*_last_active[level]];
deba@2512:       swap(_last_active[level]--, --_first[level+1]);
deba@2512:       if (level+1>_highest_active) ++_highest_active;
deba@2512:     }
deba@2512: 
deba@2512:     ///Lifts the active item returned by \c activeOn() member function.
deba@2512:     
deba@2512:     ///Lifts the active item returned by \c activeOn() member function
deba@2512:     ///to the given level.
deba@2512:     void liftActiveOn(int level, int new_level)
deba@2512:     { 
deba@2512:       const Item ai = *_last_active[level];
deba@2512:       
deba@2512:       copy(--_first[level+1], _last_active[level]--);
deba@2512:       for(int l=level+1;l<new_level;l++)
deba@2512: 	{
deba@2512: 	  copy(_last_active[l],_first[l]);
deba@2512: 	  copy(--_first[l+1], _last_active[l]--);
deba@2512: 	}
deba@2512:       copy(ai,_first[new_level]);
deba@2512:       _level[ai]=new_level;
deba@2512:       if (new_level>_highest_active) _highest_active=new_level;
deba@2512:     }
deba@2512: 
deba@2512:     ///Lifts the active item returned by \c activeOn() member function.
deba@2512:     
deba@2512:     ///Lifts the active item returned by \c activeOn() member function
deba@2512:     ///to the top level.
deba@2512:     void liftActiveToTop(int level)
deba@2512:     {
deba@2512:       const Item ai = *_last_active[level];
deba@2512:       
deba@2512:       copy(--_first[level+1],_last_active[level]--);
deba@2512:       for(int l=level+1;l<_max_level;l++)
deba@2512: 	{
deba@2512: 	  copy(_last_active[l],_first[l]);
deba@2512: 	  copy(--_first[l+1], _last_active[l]--);
deba@2512: 	}
deba@2512:       copy(ai,_first[_max_level]);
deba@2512:       --_last_active[_max_level];
deba@2512:       _level[ai]=_max_level;
deba@2512: 
deba@2512:       if (_highest_active==level) {
deba@2512: 	while(_highest_active>=0 && 
deba@2512: 	      _last_active[_highest_active]<_first[_highest_active]) 
deba@2512: 	  _highest_active--;
deba@2512:       }
deba@2512:     }
deba@2512: 
deba@2512:     ///@}
deba@2512:     
alpar@2348:     ///Lift an active item to a higher level.
alpar@2348: 
alpar@2348:     ///Lift an active item to a higher level.
alpar@2350:     ///\param i The item to be lifted. It must be active.
alpar@2350:     ///\param new_level The new level of \c i. It must be strictly higher
alpar@2348:     ///than the current level.
alpar@2348:     ///
deba@2512:     void lift(Item i, int new_level) 
alpar@2348:     {
alpar@2348:       const int lo = _level[i];
alpar@2348:       const Vit w = _where[i];
alpar@2348: 
alpar@2348:       copy(_last_active[lo],w);
alpar@2348:       copy(--_first[lo+1],_last_active[lo]--);
alpar@2348:       for(int l=lo+1;l<new_level;l++)
alpar@2348: 	{
alpar@2348: 	  copy(_last_active[l],_first[l]);
alpar@2348: 	  copy(--_first[l+1],_last_active[l]--);
alpar@2348: 	}
alpar@2348:       copy(i,_first[new_level]);
alpar@2348:       _level[i]=new_level;
alpar@2348:       if(new_level>_highest_active) _highest_active=new_level;
alpar@2348:     }
deba@2518: 
deba@2518:     ///Mark the node as it did not reach the max level
deba@2518:     
deba@2518:     ///Mark the node as it did not reach the max level. It sets the
deba@2520:     ///level to the under the max level value. The node will be never
deba@2520:     ///more activated because the push operation from the maximum
deba@2520:     ///level is forbidden in the push-relabel algorithms. The node
deba@2520:     ///should be lifted previously to the top level.
deba@2518:     void markToBottom(Item i) {
deba@2520:       _level[i] = _max_level - 1;
deba@2518:     }
alpar@2348:     
alpar@2348:     ///Lift all nodes on and above a level to the top (and deactivate them).
alpar@2348: 
deba@2512:     ///This function lifts all nodes on and above level \c l to \c
deba@2512:     ///maxLevel(), and also deactivates them.
alpar@2348:     void liftToTop(int l) 
alpar@2348:     {
alpar@2348:       const Vit f=_first[l];
alpar@2348:       const Vit tl=_first[_max_level];
alpar@2348:       for(Vit i=f;i!=tl;++i)
alpar@2348: 	_level[*i]=_max_level;
alpar@2348:       for(int i=l;i<=_max_level;i++)
alpar@2348: 	{
alpar@2348: 	  _first[i]=f;
alpar@2348: 	  _last_active[i]=f-1;
alpar@2348: 	}
alpar@2348:       for(_highest_active=l-1;
alpar@2348: 	  _highest_active>=0 &&
alpar@2348: 	    _last_active[_highest_active]<_first[_highest_active];
alpar@2348: 	  _highest_active--) ;
alpar@2348:     }
alpar@2348:     
alpar@2346:   private:
alpar@2346:     int _init_lev;
alpar@2346:     Vit _init_num;
alpar@2346: 
alpar@2346:   public:
alpar@2346: 
alpar@2346:     ///\name Initialization
alpar@2346:     ///Using this function you can initialize the levels of the item.
alpar@2346:     ///\n
alpar@2346:     ///This initializatios is started with calling \c initStart().
alpar@2346:     ///Then the
alpar@2346:     ///items should be listed levels by levels statring with the lowest one
alpar@2346:     ///(with level 0). This is done by using \c initAddItem()
alpar@2346:     ///and \c initNewLevel(). Finally \c initFinish() must be called.
alpar@2348:     ///The items not listed will be put on the highest level.
alpar@2346:     ///@{
alpar@2346: 
alpar@2348:     ///Start the initialization process.
alpar@2346: 
alpar@2346:     void initStart() 
alpar@2346:     {
alpar@2346:       _init_lev=0;
alpar@2346:       _init_num=_items.begin();
alpar@2346:       _first[0]=_items.begin();
alpar@2346:       _last_active[0]=_items.begin()-1;
alpar@2346:       Vit n=_items.begin();
alpar@2346:       for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)
alpar@2346: 	{
alpar@2346: 	  *n=i;
alpar@2346: 	  _where[i]=n;
alpar@2346: 	  _level[i]=_max_level;
alpar@2346: 	  ++n;
alpar@2346: 	}
alpar@2346:     }
alpar@2346: 
alpar@2346:     ///Add an item to the current level.
alpar@2346: 
alpar@2346:     void initAddItem(Item i)
alpar@2346:     { 
alpar@2346:      swap(_where[i],_init_num);
alpar@2346:       _level[i]=_init_lev;
alpar@2346:       ++_init_num;
alpar@2346:     }
alpar@2346: 
alpar@2346:     ///Start a new level.
alpar@2346: 
alpar@2346:     ///Start a new level.
alpar@2346:     ///It shouldn't be used before the items on level 0 are listed.
alpar@2346:     void initNewLevel() 
alpar@2346:     {
alpar@2346:       _init_lev++;
alpar@2346:       _first[_init_lev]=_init_num;
alpar@2346:       _last_active[_init_lev]=_init_num-1;
alpar@2346:     }
alpar@2346: 
alpar@2348:     ///Finalize the initialization process.
alpar@2346: 
alpar@2346:     void initFinish()
alpar@2346:     {
alpar@2346:       for(_init_lev++;_init_lev<=_max_level;_init_lev++)
alpar@2346: 	{
alpar@2346: 	  _first[_init_lev]=_init_num;
alpar@2346: 	  _last_active[_init_lev]=_init_num-1;
alpar@2346: 	}
alpar@2346:       _first[_max_level+1]=_items.begin()+_item_num;
alpar@2346:       _last_active[_max_level+1]=_items.begin()+_item_num-1;
deba@2512:       _highest_active = -1;
alpar@2346:     }
alpar@2346: 
alpar@2346:     ///@}
alpar@2346: 
alpar@2346:   };
alpar@2346: 
deba@2512:   ///Class for handling "labels" in push-relabel type algorithms.
deba@2512:   
deba@2512:   ///A class for handling "labels" in push-relabel type algorithms.
deba@2512:   ///
deba@2512:   ///\ingroup auxdat
deba@2512:   ///Using this class you can assign "labels" (nonnegative integer numbers)
deba@2512:   ///to the edges or nodes of a graph, manipulate and query them through
deba@2512:   ///operations typically arising in "push-relabel" type algorithms.
deba@2512:   ///
deba@2512:   ///Each item is either \em active or not, and you can also choose a
deba@2512:   ///highest level active item.
deba@2512:   ///
deba@2512:   ///\sa Elevator
deba@2512:   ///
deba@2512:   ///\param Graph the underlying graph type
deba@2512:   ///\param Item Type of the items the data is assigned to (Graph::Node,
deba@2512:   ///Graph::Edge, Graph::UEdge)
deba@2512:   template <class Graph, class Item>
deba@2512:   class LinkedElevator {
deba@2518:   public:
deba@2512: 
deba@2512:     typedef Item Key;
deba@2512:     typedef int Value;
deba@2512: 
deba@2518:   private:
deba@2518: 
deba@2512:     typedef typename ItemSetTraits<Graph,Item>::
deba@2512:     template Map<Item>::Type ItemMap;
deba@2512:     typedef typename ItemSetTraits<Graph,Item>::
deba@2512:     template Map<int>::Type IntMap;
deba@2512:     typedef typename ItemSetTraits<Graph,Item>::
deba@2512:     template Map<bool>::Type BoolMap;
deba@2512: 
deba@2512:     const Graph &_graph;
deba@2512:     int _max_level;
deba@2512:     int _item_num;
deba@2512:     std::vector<Item> _first, _last;
deba@2512:     ItemMap _prev, _next;    
deba@2512:     int _highest_active;
deba@2512:     IntMap _level;
deba@2512:     BoolMap _active;
deba@2512:     
deba@2512:   public:
deba@2512:     ///Constructor with given maximum level.
deba@2512: 
deba@2512:     ///Constructor with given maximum level.
deba@2512:     ///
deba@2512:     ///\param g The underlying graph
deba@2512:     ///\param max_level Set the range of the possible labels to
deba@2512:     ///[0...\c max_level]
deba@2512:     LinkedElevator(const Graph& graph, int max_level) 
deba@2512:       : _graph(graph), _max_level(max_level), _item_num(_max_level), 
deba@2512: 	_first(_max_level + 1), _last(_max_level + 1),
deba@2512: 	_prev(graph), _next(graph),      
deba@2512: 	_highest_active(-1), _level(graph), _active(graph) {}
deba@2512: 
deba@2512:     ///Constructor.
deba@2512: 
deba@2512:     ///Constructor.
deba@2512:     ///
deba@2512:     ///\param g The underlying graph
deba@2512:     ///The range of the possible labels is [0...\c max_level],
deba@2512:     ///where \c max_level is equal to the number of labeled items in the graph.
deba@2512:     LinkedElevator(const Graph& graph) 
deba@2512:       : _graph(graph), _max_level(countItems<Graph, Item>(graph)), 
deba@2512: 	_item_num(_max_level), 
deba@2512: 	_first(_max_level + 1), _last(_max_level + 1),
deba@2512: 	_prev(graph, INVALID), _next(graph, INVALID),      
deba@2512: 	_highest_active(-1), _level(graph), _active(graph) {}
deba@2512:   
deba@2512: 
deba@2512:     ///Activate item \c i.
deba@2512: 
deba@2512:     ///Activate item \c i.
deba@2512:     ///\pre Item \c i shouldn't be active before.
deba@2512:     void activate(Item i) {
deba@2512:       _active.set(i, true);
deba@2512: 
deba@2512:       int level = _level[i];
deba@2512:       if (level > _highest_active) {
deba@2512: 	_highest_active = level;
deba@2512:       }
deba@2512: 
deba@2512:       if (_prev[i] == INVALID || _active[_prev[i]]) return;	    
deba@2512:       //unlace
deba@2512:       _next.set(_prev[i], _next[i]);
deba@2512:       if (_next[i] != INVALID) {
deba@2512: 	_prev.set(_next[i], _prev[i]);
deba@2512:       } else {
deba@2512: 	_last[level] = _prev[i];
deba@2512:       }
deba@2512:       //lace
deba@2512:       _next.set(i, _first[level]);
deba@2512:       _prev.set(_first[level], i);
deba@2512:       _prev.set(i, INVALID);
deba@2512:       _first[level] = i;
deba@2512: 
deba@2512:     }
deba@2512:   
deba@2512:     ///Deactivate item \c i.
deba@2512: 
deba@2512:     ///Deactivate item \c i.
deba@2512:     ///\pre Item \c i must be active before.
deba@2512:     void deactivate(Item i) {
deba@2512:       _active.set(i, false);
deba@2512:       int level = _level[i];
deba@2512: 
deba@2512:       if (_next[i] == INVALID || !_active[_next[i]])
deba@2512: 	goto find_highest_level;
deba@2512: 
deba@2512:       //unlace
deba@2512:       _prev.set(_next[i], _prev[i]);
deba@2512:       if (_prev[i] != INVALID) {
deba@2512: 	_next.set(_prev[i], _next[i]);
deba@2512:       } else {
deba@2512: 	_first[_level[i]] = _next[i];
deba@2512:       }
deba@2512:       //lace
deba@2512:       _prev.set(i, _last[level]);
deba@2512:       _next.set(_last[level], i);
deba@2512:       _next.set(i, INVALID);
deba@2512:       _last[level] = i;
deba@2512:       
deba@2512:     find_highest_level:
deba@2512:       if (level == _highest_active) {
deba@2512: 	while (_highest_active >= 0 && activeFree(_highest_active)) 
deba@2512: 	  --_highest_active;
deba@2512:       }
deba@2512:     }
deba@2512: 
deba@2512:     ///Query whether item \c i is active
deba@2512:     bool active(Item i) const { return _active[i]; }
deba@2512:     
deba@2512:     ///Return the level of item \c i.
deba@2512:     int operator[](Item i) const { return _level[i]; }
deba@2512:     
deba@2512:     ///Return the number of items on level \c l.
deba@2512:     int onLevel(int l) const {
deba@2512:       int num = 0;
deba@2512:       Item n = _first[l];
deba@2512:       while (n != INVALID) {
deba@2512: 	++num;
deba@2512: 	n = _next[n];
deba@2512:       }
deba@2512:       return num;
deba@2512:     }
deba@2512: 
deba@2512:     ///Return true if the level is empty.
deba@2512:     bool emptyLevel(int l) const {
deba@2512:       return _first[l] == INVALID;
deba@2512:     }
deba@2512: 
deba@2512:     ///Return the number of items above level \c l.
deba@2512:     int aboveLevel(int l) const {
deba@2512:       int num = 0;
deba@2512:       for (int level = l + 1; level < _max_level; ++level)
deba@2512: 	num += onLevel(level);
deba@2512:       return num;
deba@2512:     }
deba@2512: 
deba@2512:     ///Return the number of active items on level \c l.
deba@2512:     int activesOnLevel(int l) const {
deba@2512:       int num = 0;
deba@2512:       Item n = _first[l];
deba@2512:       while (n != INVALID && _active[n]) {
deba@2512: 	++num;
deba@2512: 	n = _next[n];
deba@2512:       }
deba@2512:       return num;
deba@2512:     }
deba@2512: 
deba@2512:     ///Return true if there is not active item on level \c l.
deba@2512:     bool activeFree(int l) const {
deba@2512:       return _first[l] == INVALID || !_active[_first[l]];
deba@2512:     }
deba@2512: 
deba@2512:     ///Return the maximum allowed level.
deba@2512:     int maxLevel() const {
deba@2512:       return _max_level;
deba@2512:     }    
deba@2512: 
deba@2512:     ///\name Highest Active Item
deba@2512:     ///Functions for working with the highest level
deba@2512:     ///active item.
deba@2512: 
deba@2512:     ///@{
deba@2512: 
deba@2512:     ///Return a highest level active item.
deba@2512:   
deba@2512:     ///Return a highest level active item.
deba@2512:     ///
deba@2512:     ///\return the highest level active item or INVALID if there is no
deba@2512:     ///active item.
deba@2512:     Item highestActive() const {
deba@2512:       return _highest_active >= 0 ? _first[_highest_active] : INVALID;
deba@2512:     }
deba@2512: 
deba@2512:     ///Return a highest active level.
deba@2512: 
deba@2512:     ///Return a highest active level.
deba@2512:     ///
deba@2512:     ///\return the level of the highest active item or -1 if there is
deba@2512:     ///no active item.
deba@2512:     int highestActiveLevel() const {
deba@2512:       return _highest_active;
deba@2512:     }
deba@2512: 
deba@2512:     ///Lift the highest active item by one.
deba@2512: 
deba@2512:     ///Lift the item returned by highestActive() by one.
deba@2512:     ///
deba@2512:     void liftHighestActive() {
deba@2512:       Item i = _first[_highest_active];
deba@2512:       if (_next[i] != INVALID) {
deba@2512: 	_prev.set(_next[i], INVALID);
deba@2512: 	_first[_highest_active] = _next[i]; 
deba@2512:       } else {
deba@2512: 	_first[_highest_active] = INVALID;
deba@2512: 	_last[_highest_active] = INVALID;
deba@2512:       }
deba@2512:       _level.set(i, ++_highest_active);
deba@2512:       if (_first[_highest_active] == INVALID) {
deba@2512: 	_first[_highest_active] = i;
deba@2512: 	_last[_highest_active] = i;
deba@2512: 	_prev.set(i, INVALID);
deba@2512: 	_next.set(i, INVALID);
deba@2512:       } else {
deba@2512: 	_prev.set(_first[_highest_active], i);
deba@2512: 	_next.set(i, _first[_highest_active]);
deba@2512: 	_first[_highest_active] = i;
deba@2512:       }
deba@2512:     }
deba@2512: 
deba@2512:     ///Lift the highest active item.
deba@2512: 
deba@2512:     ///Lift the item returned by highestActive() to level \c new_level.
deba@2512:     ///
deba@2512:     ///\warning \c new_level must be strictly higher
deba@2512:     ///than the current level.
deba@2512:     ///
deba@2512:     void liftHighestActive(int new_level) {
deba@2512:       Item i = _first[_highest_active];
deba@2512:       if (_next[i] != INVALID) {
deba@2512: 	_prev.set(_next[i], INVALID);
deba@2512: 	_first[_highest_active] = _next[i]; 
deba@2512:       } else {
deba@2512: 	_first[_highest_active] = INVALID;
deba@2512: 	_last[_highest_active] = INVALID;
deba@2512:       }
deba@2512:       _level.set(i, _highest_active = new_level);
deba@2512:       if (_first[_highest_active] == INVALID) {
deba@2512: 	_first[_highest_active] = _last[_highest_active] = i;
deba@2512: 	_prev.set(i, INVALID);
deba@2512: 	_next.set(i, INVALID);
deba@2512:       } else {
deba@2512: 	_prev.set(_first[_highest_active], i);
deba@2512: 	_next.set(i, _first[_highest_active]);
deba@2512: 	_first[_highest_active] = i;
deba@2512:       }
deba@2512:     }
deba@2512: 
deba@2512:     ///Lift the highest active to top.
deba@2512: 
deba@2512:     ///Lift the item returned by highestActive() to the top level and
deba@2512:     ///deactivates the node.
deba@2512:     ///
deba@2512:     void liftHighestActiveToTop() {
deba@2512:       Item i = _first[_highest_active];
deba@2512:       _level.set(i, _max_level);
deba@2512:       if (_next[i] != INVALID) {
deba@2512: 	_prev.set(_next[i], INVALID);
deba@2512: 	_first[_highest_active] = _next[i]; 
deba@2512:       } else {
deba@2512: 	_first[_highest_active] = INVALID;
deba@2512: 	_last[_highest_active] = INVALID;
deba@2512:       }
deba@2512:       while (_highest_active >= 0 && activeFree(_highest_active)) 
deba@2512: 	--_highest_active;
deba@2512:     }
deba@2512:     
deba@2512:     ///@}
deba@2512: 
deba@2512:     ///\name Active Item on Certain Level 
deba@2512:     ///Functions for working with the active items.
deba@2512: 
deba@2512:     ///@{
deba@2512: 
deba@2512:     ///Returns an active item on level \c l.
deba@2512:     
deba@2512:     ///Returns an active item on level \c l.
deba@2512:     ///
deba@2512:     ///Returns an active item on level \c l or \ref INVALID if there is no such
deba@2512:     ///an item. (\c l must be from the range [0...\c max_level].
deba@2512:     Item activeOn(int l) const
deba@2512:     { 
deba@2512:       return _active[_first[l]] ? _first[l] : INVALID;
deba@2512:     }
deba@2512: 
deba@2512:     ///Lifts the active item returned by \c activeOn() member function.
deba@2512:     
deba@2512:     ///Lifts the active item returned by \c activeOn() member function
deba@2512:     ///by one.
deba@2512:     Item liftActiveOn(int l)
deba@2512:     { 
deba@2512:       Item i = _first[l];
deba@2512:       if (_next[i] != INVALID) {
deba@2512: 	_prev.set(_next[i], INVALID);
deba@2512: 	_first[l] = _next[i]; 
deba@2512:       } else {
deba@2512: 	_first[l] = INVALID;
deba@2512: 	_last[l] = INVALID;
deba@2512:       }
deba@2512:       _level.set(i, ++l);
deba@2512:       if (_first[l] == INVALID) {
deba@2512: 	_first[l] = _last[l] = i;
deba@2512: 	_prev.set(i, INVALID);
deba@2512: 	_next.set(i, INVALID);
deba@2512:       } else {
deba@2512: 	_prev.set(_first[l], i);
deba@2512: 	_next.set(i, _first[l]);
deba@2512: 	_first[l] = i;
deba@2512:       }
deba@2512:       if (_highest_active < l) {
deba@2512: 	_highest_active = l;
deba@2512:       }
deba@2512:     }
deba@2512: 
deba@2512:     /// \brief Lifts the active item returned by \c activeOn() member function.
deba@2512:     ///    
deba@2512:     /// Lifts the active item returned by \c activeOn() member function
deba@2512:     /// to the given level.
deba@2512:     void liftActiveOn(int l, int new_level)
deba@2512:     { 
deba@2512:       Item i = _first[l];
deba@2512:       if (_next[i] != INVALID) {
deba@2512: 	_prev.set(_next[i], INVALID);
deba@2512: 	_first[l] = _next[i]; 
deba@2512:       } else {
deba@2512: 	_first[l] = INVALID;
deba@2512: 	_last[l] = INVALID;
deba@2512:       }
deba@2512:       _level.set(i, l = new_level);
deba@2512:       if (_first[l] == INVALID) {
deba@2512: 	_first[l] = _last[l] = i;
deba@2512: 	_prev.set(i, INVALID);
deba@2512: 	_next.set(i, INVALID);
deba@2512:       } else {
deba@2512: 	_prev.set(_first[l], i);
deba@2512: 	_next.set(i, _first[l]);
deba@2512: 	_first[l] = i;
deba@2512:       }
deba@2512:       if (_highest_active < l) {
deba@2512: 	_highest_active = l;
deba@2512:       }
deba@2512:     }
deba@2512: 
deba@2512:     ///Lifts the active item returned by \c activeOn() member function.
deba@2512:     
deba@2512:     ///Lifts the active item returned by \c activeOn() member function
deba@2512:     ///to the top level.
deba@2512:     void liftActiveToTop(int l)
deba@2512:     { 
deba@2512:       Item i = _first[l];
deba@2512:       if (_next[i] != INVALID) {
deba@2512: 	_prev.set(_next[i], INVALID);
deba@2512: 	_first[l] = _next[i]; 
deba@2512:       } else {
deba@2512: 	_first[l] = INVALID;
deba@2512: 	_last[l] = INVALID;
deba@2512:       }
deba@2512:       _level.set(i, _max_level);
deba@2512:       if (l == _highest_active) {
deba@2512: 	while (_highest_active >= 0 && activeFree(_highest_active)) 
deba@2512: 	  --_highest_active;
deba@2512:       }
deba@2512:     }
deba@2512: 
deba@2512:     ///@}
deba@2512:     
deba@2512:     /// \brief Lift an active item to a higher level.
deba@2512:     ///
deba@2512:     /// Lift an active item to a higher level.
deba@2512:     /// \param i The item to be lifted. It must be active.
deba@2512:     /// \param new_level The new level of \c i. It must be strictly higher
deba@2512:     /// than the current level.
deba@2512:     ///
deba@2512:     void lift(Item i, int new_level) {
deba@2512:       if (_next[i] != INVALID) {
deba@2512: 	_prev.set(_next[i], _prev[i]);
deba@2512:       } else {
deba@2512: 	_last[new_level] = _prev[i];
deba@2512:       }
deba@2512:       if (_prev[i] != INVALID) {
deba@2512: 	_next.set(_prev[i], _next[i]);
deba@2512:       } else {
deba@2512: 	_first[new_level] = _next[i];
deba@2512:       }
deba@2512:       _level.set(i, new_level);
deba@2512:       if (_first[new_level] == INVALID) {
deba@2512: 	_first[new_level] = _last[new_level] = i;
deba@2512: 	_prev.set(i, INVALID);
deba@2512: 	_next.set(i, INVALID);
deba@2512:       } else {
deba@2512: 	_prev.set(_first[new_level], i);
deba@2512: 	_next.set(i, _first[new_level]);
deba@2512: 	_first[new_level] = i;
deba@2512:       }
deba@2512:       if (_highest_active < new_level) {
deba@2512: 	_highest_active = new_level;
deba@2512:       }
deba@2512:     }
deba@2512:     
deba@2518:     ///Mark the node as it did not reach the max level
deba@2518:     
deba@2518:     ///Mark the node as it did not reach the max level. It sets the
deba@2520:     ///level to the under the max level value. The node will be never
deba@2520:     ///more activated because the push operation from the maximum
deba@2520:     ///level is forbidden in the push-relabel algorithms. The node
deba@2520:     ///should be lifted previously to the top level.
deba@2518:     void markToBottom(Item i) {
deba@2521:       _level.set(i, _max_level - 1);
deba@2518:     }
deba@2518: 
deba@2512:     ///Lift all nodes on and above a level to the top (and deactivate them).
deba@2512: 
deba@2512:     ///This function lifts all nodes on and above level \c l to \c
deba@2512:     ///maxLevel(), and also deactivates them. 
deba@2512:     void liftToTop(int l)  {
deba@2512:       for (int i = l + 1; _first[i] != INVALID; ++i) {
deba@2512: 	Item n = _first[i];
deba@2512: 	while (n != INVALID) {
deba@2512: 	  _level.set(n, _max_level);
deba@2512: 	  n = _next[n];
deba@2512: 	}
deba@2512: 	_first[i] = INVALID;
deba@2512: 	_last[i] = INVALID;
deba@2512:       }
deba@2512:       if (_highest_active > l - 1) {
deba@2512: 	_highest_active = l - 1;
deba@2512: 	while (_highest_active >= 0 && activeFree(_highest_active)) 
deba@2512: 	  --_highest_active;
deba@2512:       }
deba@2512:     }
deba@2512:     
deba@2512:   private:
deba@2512: 
deba@2512:     int _init_level;
deba@2512: 
deba@2512:   public:
deba@2512: 
deba@2512:     ///\name Initialization
deba@2512:     ///Using this function you can initialize the levels of the item.
deba@2512:     ///\n
deba@2512:     ///This initializatios is started with calling \c initStart().
deba@2512:     ///Then the
deba@2512:     ///items should be listed levels by levels statring with the lowest one
deba@2512:     ///(with level 0). This is done by using \c initAddItem()
deba@2512:     ///and \c initNewLevel(). Finally \c initFinish() must be called.
deba@2512:     ///The items not listed will be put on the highest level.
deba@2512:     ///@{
deba@2512: 
deba@2512:     ///Start the initialization process.
deba@2512: 
deba@2512:     void initStart() {
deba@2512:       
deba@2512:       for (int i = 0; i <= _max_level; ++i) {
deba@2512: 	_first[i] = _last[i] = INVALID;
deba@2512:       }
deba@2512:       _init_level = 0;
deba@2512:       for(typename ItemSetTraits<Graph,Item>::ItemIt i(_graph); 
deba@2512: 	  i != INVALID; ++i) {
deba@2512: 	_level.set(i, _max_level);
deba@2524: 	_active.set(i, false);
deba@2512:       }
deba@2512:     }
deba@2512: 
deba@2512:     ///Add an item to the current level.
deba@2512: 
deba@2512:     void initAddItem(Item i) {
deba@2512:       _level.set(i, _init_level);
deba@2512:       if (_last[_init_level] == INVALID) {
deba@2512: 	_first[_init_level] = i;
deba@2512: 	_last[_init_level] = i;
deba@2512: 	_prev.set(i, INVALID);
deba@2512: 	_next.set(i, INVALID);
deba@2512:       } else {
deba@2512: 	_prev.set(i, _last[_init_level]);
deba@2512: 	_next.set(i, INVALID);
deba@2512: 	_next.set(_last[_init_level], i);
deba@2512: 	_last[_init_level] = i;
deba@2512:       }
deba@2512:     }
deba@2512: 
deba@2512:     ///Start a new level.
deba@2512: 
deba@2512:     ///Start a new level.
deba@2512:     ///It shouldn't be used before the items on level 0 are listed.
deba@2512:     void initNewLevel() {
deba@2512:       ++_init_level;
deba@2512:     }
deba@2512: 
deba@2512:     ///Finalize the initialization process.
deba@2512: 
deba@2512:     void initFinish() {
deba@2512:       _highest_active = -1;
deba@2512:     }
deba@2512: 
deba@2512:     ///@}
deba@2512: 
deba@2512:   };
deba@2512: 
deba@2512: 
alpar@2346: } //END OF NAMESPACE LEMON
alpar@2346: 
alpar@2346: #endif
alpar@2346: