3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #ifndef LEMON_ELEVATOR_H
20 #define LEMON_ELEVATOR_H
24 ///\brief Elevator class
26 ///Elevator class implements an efficient data structure
27 ///for labeling items in push-relabel type algorithms.
30 #include <test/test_tools.h>
33 ///Class for handling "labels" in push-relabel type algorithms.
35 ///A class for handling "labels" in push-relabel type algorithms.
38 ///Using this class you can assign "labels" (nonnegativ 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.
42 ///Each item is either \em active or not, and you can also choose a
43 ///highest level active item.
45 ///\param Graph the underlying graph type
46 ///\param Item Type of the items the data is assigned to (Graph::Node,
47 ///Graph::Edge, Graph::UEdge)
48 template<class Graph, class Item>
52 typedef typename std::vector<Item>::iterator Vit;
53 typedef DefaultMap<Graph,Item,Vit> VitMap;
54 typedef DefaultMap<Graph,Item,int> IntMap;
61 std::vector<Item> _items;
62 std::vector<Vit> _first;
63 std::vector<Vit> _last_active;
67 void copy(Item i, Vit p)
71 void copy(Vit s, Vit p)
80 void swap(Vit i, Vit j)
84 _where[ti]=_where[*i=*j];
91 for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)
95 check(*w==i,"GEBASZ: CORRUPT DS");
96 check(_first[l]<=w,"GEBASZ: CORRUPT DS");
97 check(_first[l+1]>w,"GEBASZ: CORRUPT DS");
99 check(_highest_active<0 ||
100 _first[_highest_active]<=_last_active[_highest_active],
101 "GEBASZ: CORRUPT DS");
105 ///Constructor with given maximum level.
107 ///Constructor with given maximum level.
109 ///\param g The underlying graph
110 ///\param max_level Set the range of the possible labels to
111 ///[0...\c max_level]
112 Elevator(const Graph &g,int max_level) :
114 _max_level(max_level),
115 _item_num(_max_level),
119 _first(_max_level+2),
120 _last_active(_max_level+2),
121 _highest_active(-1) {}
126 ///\param g The underlying graph
127 ///The range of the possible labels is [0...\c max_level],
128 ///where \c max_level is equal to the number of labeled items in the graph.
129 Elevator(const Graph &g) :
131 _max_level(countItems<Graph, Item>(g)),
132 _item_num(_max_level),
136 _first(_max_level+2),
137 _last_active(_max_level+2),
142 ///Activate item \c i.
143 void activate(Item i)
145 const int l=_level[i];
146 swap(_where[i],++_last_active[l]);
147 if(l>_highest_active) _highest_active=l;
150 ///Deactivate item \c i.
151 void deactivate(Item i)
153 swap(_where[i],_last_active[_level[i]]--);
154 _last_active[_level[i]]--;
155 while(_highest_active>=0 &&
156 _last_active[_highest_active]<_first[_highest_active])
160 ///Query whether item \c i is active
161 bool active(Item i) const { return _where[i]<=_last_active[_level[i]]; }
163 ///Return the level of item \c i.
164 int operator[](Item i) const { return _level[i]; }
166 ///Returns an active item on level \c l.
168 ///Returns an active item on level \c l.
170 ///Returns an active item on level \c l or \ref INVALID if there is no such
171 ///an item. (\c l must be from the range [0...\c max_level].
172 Item operator[](int l) const
174 return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
177 ///Return the number of items on level \c l.
180 return _first[l+1]-_first[l];
182 ///Return the number of active items on level \c l.
183 int &activesOnLevel(int l)
185 return _last_active[l]-_first[l]+1;
187 ///Return the maximum allowed level.
193 ///\name Highest Active Item
194 ///Functions for working with the highest level
199 ///Return a highest level active item.
201 ///Return a highest level active item.
203 ///\return the highest level active item or INVALID if there is no active
205 Item highestActive() const
207 return _highest_active>=0?*_last_active[_highest_active]:INVALID;
210 ///Return a highest active level.
212 ///Return a highest active level.
214 ///\return the level of the highest active item or -1 if there is no active
216 Item highestActiveLevel() const
218 return _highest_active;
221 ///Lift the highest active item by one.
223 ///Lift the item returned by highestActive() by one.
225 void liftHighestActive()
227 ++_level[*_last_active[_highest_active]];
228 swap(_last_active[_highest_active]--,_last_active[_highest_active+1]);
229 --_first[++_highest_active];
232 ///Lift the highest active item.
234 ///Lift the item returned by highestActive() to level \c new_level.
237 void liftHighestActiveTo(int new_level)
239 const Item li = *_last_active[_highest_active];
241 copy(--_first[_highest_active+1],_last_active[_highest_active]--);
242 for(int l=_highest_active+1;l<new_level;l++)
244 copy(--_first[l+1],_first[l]);
247 copy(li,_first[new_level]);
248 _level[li]=new_level;
249 _highest_active=new_level;
260 ///\name Initialization
261 ///Using this function you can initialize the levels of the item.
263 ///This initializatios is started with calling \c initStart().
265 ///items should be listed levels by levels statring with the lowest one
266 ///(with level 0). This is done by using \c initAddItem()
267 ///and \c initNewLevel(). Finally \c initFinish() must be called.
268 ///The items not listes will be put on the highest level.
271 ///Starts the initialization process.
276 _init_num=_items.begin();
277 _first[0]=_items.begin();
278 _last_active[0]=_items.begin()-1;
279 Vit n=_items.begin();
280 for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)
284 _level[i]=_max_level;
289 ///Add an item to the current level.
291 void initAddItem(Item i)
293 swap(_where[i],_init_num);
298 ///Start a new level.
300 ///Start a new level.
301 ///It shouldn't be used before the items on level 0 are listed.
305 _first[_init_lev]=_init_num;
306 _last_active[_init_lev]=_init_num-1;
309 ///Finalizes the initialization process.
313 for(_init_lev++;_init_lev<=_max_level;_init_lev++)
315 _first[_init_lev]=_init_num;
316 _last_active[_init_lev]=_init_num-1;
318 _first[_max_level+1]=_items.begin()+_item_num;
319 _last_active[_max_level+1]=_items.begin()+_item_num-1;
326 } //END OF NAMESPACE LEMON