alpar@2346: /* -*- C++ -*- alpar@2346: * alpar@2346: * This file is a part of LEMON, a generic C++ optimization library alpar@2346: * alpar@2391: * Copyright (C) 2003-2007 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 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: /// 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 alpar@2346: class Elevator alpar@2346: { alpar@2346: public: alpar@2346: typedef typename std::vector::iterator Vit; alpar@2346: typedef DefaultMap VitMap; alpar@2346: typedef DefaultMap 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 _items; alpar@2346: std::vector _first; alpar@2346: std::vector _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@2348: void checkDs() const alpar@2346: { alpar@2346: for(typename ItemSetTraits::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@2348: for(int l=0;l<=_max_level;++l) alpar@2348: { alpar@2348: check(_first[l]<=_last_active[l]+1,"GEBASZ: CORRUPT DS"); alpar@2348: check(_last_active[l]<_first[l+1],"GEBASZ: CORRUPT DS"); alpar@2348: check(_first[l]<=_first[l+1],"GEBASZ: CORRUPT DS"); alpar@2348: } 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(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@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: ///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@2348: int onLevel(int l) const alpar@2346: { alpar@2346: return _first[l+1]-_first[l]; alpar@2346: } 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: } 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: /// 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_highest_active) _highest_active=new_level; alpar@2348: } alpar@2348: alpar@2348: // void liftToTop(int l) alpar@2348: // { alpar@2348: // const Vit f=_first[l]; 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(Vit i=f;i!=_items.end();++i) alpar@2348: // _level[*i]=_max_level; 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@2348: ///Lift all nodes on and above a level to the top (and deactivate them). alpar@2348: alpar@2348: ///This function lifts all nodes on and above level \c l to \c maxLevel(), alpar@2348: ///and alpar@2348: ///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::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; 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: