alpar@2346: /* -*- C++ -*-
alpar@2346:  *
alpar@2346:  * This file is a part of LEMON, a generic C++ optimization library
alpar@2346:  *
alpar@2346:  * Copyright (C) 2003-2006
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@2346:   ///Class for hangling "labels" in push-relabel type algorithms.
alpar@2346:   
alpar@2346:   ///A class for hangling "labels" in push-relabel type algorithms.
alpar@2346:   ///
alpar@2346:   ///\ingroup auxdat
alpar@2346:   ///Using this class you can assign "labels" (nonnegativ 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:   ///
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:   {
alpar@2346:   public:
alpar@2346:     typedef typename std::vector<Item>::iterator Vit;
alpar@2346:     typedef DefaultMap<Graph,Item,Vit> VitMap;
alpar@2346:     typedef DefaultMap<Graph,Item,int> 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:     void checkDs() 
alpar@2346:     {
alpar@2346:       for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)
alpar@2346: 	{
alpar@2346: 	  Vit w=_where[i];
alpar@2346: 	  int l=_level[i];
alpar@2346: 	  check(*w==i,"GEBASZ: CORRUPT DS");
alpar@2346: 	  check(_first[l]<=w,"GEBASZ: CORRUPT DS");
alpar@2346: 	  check(_first[l+1]>w,"GEBASZ: CORRUPT DS");
alpar@2346: 	}
alpar@2346:       check(_highest_active<0 ||
alpar@2346: 	    _first[_highest_active]<=_last_active[_highest_active],
alpar@2346: 	    "GEBASZ: CORRUPT DS");
alpar@2346:     }
alpar@2346: 
alpar@2346:   public:
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:     }
alpar@2346:   
alpar@2346:     ///Activate item \c i.
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@2346:     void deactivate(Item i)  
alpar@2346:     {
alpar@2346:       swap(_where[i],_last_active[_level[i]]--);
alpar@2346:       _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:     ///Returns an active item on level \c l.
alpar@2346: 
alpar@2346:     ///Returns an active item on level \c l.
alpar@2346:     ///
alpar@2346:     ///Returns an active item on level \c l or \ref INVALID if there is no such
alpar@2346:     ///an item. (\c l must be from the range [0...\c max_level].
alpar@2346:     Item operator[](int l) const
alpar@2346:     { 
alpar@2346:       return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
alpar@2346:     }
alpar@2346: 
alpar@2346:     ///Return the number of items on level \c l.
alpar@2346:     int &onLevel(int l)
alpar@2346:     {
alpar@2346:       return _first[l+1]-_first[l];
alpar@2346:     }
alpar@2346:     ///Return the number of active items on level \c l.
alpar@2346:     int &activesOnLevel(int l)
alpar@2346:     {
alpar@2346:       return _last_active[l]-_first[l]+1;
alpar@2346:     }
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.
alpar@2346:     Item 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@2346:     ///
alpar@2346:     void liftHighestActiveTo(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@2346: 	  _highest_active=new_level;
alpar@2346:     }
alpar@2346:     
alpar@2346:     ///@}
alpar@2346:     
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@2346:     ///The items not listes will be put on the highest level.
alpar@2346:     ///@{
alpar@2346: 
alpar@2346:     ///Starts 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@2346:     ///Finalizes 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;
alpar@2346:     }
alpar@2346: 
alpar@2346:     ///@}
alpar@2346: 
alpar@2346:   };
alpar@2346: 
alpar@2346: } //END OF NAMESPACE LEMON
alpar@2346: 
alpar@2346: #endif
alpar@2346: