Consider the CPXMIP_OPTIMAL_TOL status as OPTIMAL too.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
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" (nonnegative 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 for(int l=0;l<=_max_level;++l)
101 check(_first[l]<=_last_active[l]+1,"GEBASZ: CORRUPT DS");
102 check(_last_active[l]<_first[l+1],"GEBASZ: CORRUPT DS");
103 check(_first[l]<=_first[l+1],"GEBASZ: CORRUPT DS");
105 check(_highest_active<0 ||
106 _first[_highest_active]<=_last_active[_highest_active],
107 "GEBASZ: CORRUPT DS");
111 ///Constructor with given maximum level.
113 ///Constructor with given maximum level.
115 ///\param g The underlying graph
116 ///\param max_level Set the range of the possible labels to
117 ///[0...\c max_level]
118 Elevator(const Graph &g,int max_level) :
120 _max_level(max_level),
121 _item_num(_max_level),
125 _first(_max_level+2),
126 _last_active(_max_level+2),
127 _highest_active(-1) {}
132 ///\param g The underlying graph
133 ///The range of the possible labels is [0...\c max_level],
134 ///where \c max_level is equal to the number of labeled items in the graph.
135 Elevator(const Graph &g) :
137 _max_level(countItems<Graph, Item>(g)),
138 _item_num(_max_level),
142 _first(_max_level+2),
143 _last_active(_max_level+2),
148 ///Activate item \c i.
150 ///Activate item \c i.
151 ///\pre Item \c i shouldn't be active before.
152 void activate(Item i)
154 const int l=_level[i];
155 swap(_where[i],++_last_active[l]);
156 if(l>_highest_active) _highest_active=l;
159 ///Deactivate item \c i.
161 ///Deactivate item \c i.
162 ///\pre Item \c i must be active before.
163 void deactivate(Item i)
165 swap(_where[i],_last_active[_level[i]]--);
166 while(_highest_active>=0 &&
167 _last_active[_highest_active]<_first[_highest_active])
171 ///Query whether item \c i is active
172 bool active(Item i) const { return _where[i]<=_last_active[_level[i]]; }
174 ///Return the level of item \c i.
175 int operator[](Item i) const { return _level[i]; }
177 ///Returns an active item on level \c l.
179 ///Returns an active item on level \c l.
181 ///Returns an active item on level \c l or \ref INVALID if there is no such
182 ///an item. (\c l must be from the range [0...\c max_level].
183 Item operator[](int l) const
185 return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
188 ///Return the number of items on level \c l.
189 int onLevel(int l) const
191 return _first[l+1]-_first[l];
193 ///Return the number of items above level \c l.
194 int aboveLevel(int l) const
196 return _first[_max_level+1]-_first[l+1];
198 ///Return the number of active items on level \c l.
199 int activesOnLevel(int l) const
201 return _last_active[l]-_first[l]+1;
203 ///Return the maximum allowed level.
209 ///\name Highest Active Item
210 ///Functions for working with the highest level
215 ///Return a highest level active item.
217 ///Return a highest level active item.
219 ///\return the highest level active item or INVALID if there is no active
221 Item highestActive() const
223 return _highest_active>=0?*_last_active[_highest_active]:INVALID;
226 ///Return a highest active level.
228 ///Return a highest active level.
230 ///\return the level of the highest active item or -1 if there is no active
232 int highestActiveLevel() const
234 return _highest_active;
237 ///Lift the highest active item by one.
239 ///Lift the item returned by highestActive() by one.
241 void liftHighestActive()
243 ++_level[*_last_active[_highest_active]];
244 swap(_last_active[_highest_active]--,_last_active[_highest_active+1]);
245 --_first[++_highest_active];
248 ///Lift the highest active item.
250 ///Lift the item returned by highestActive() to level \c new_level.
252 ///\warning \c new_level must be strictly higher
253 ///than the current level.
255 void liftHighestActiveTo(int new_level)
257 const Item li = *_last_active[_highest_active];
259 copy(--_first[_highest_active+1],_last_active[_highest_active]--);
260 for(int l=_highest_active+1;l<new_level;l++)
262 copy(--_first[l+1],_first[l]);
265 copy(li,_first[new_level]);
266 _level[li]=new_level;
267 _highest_active=new_level;
272 ///Lift an active item to a higher level.
274 ///Lift an active item to a higher level.
275 ///\param i The item to be lifted. It must be active.
276 ///\param new_level The new level of \c i. It must be strictly higher
277 ///than the current level.
279 void liftTo(Item i, int new_level)
281 const int lo = _level[i];
282 const Vit w = _where[i];
284 copy(_last_active[lo],w);
285 copy(--_first[lo+1],_last_active[lo]--);
286 for(int l=lo+1;l<new_level;l++)
288 copy(_last_active[l],_first[l]);
289 copy(--_first[l+1],_last_active[l]--);
291 copy(i,_first[new_level]);
293 if(new_level>_highest_active) _highest_active=new_level;
296 // void liftToTop(int l)
298 // const Vit f=_first[l];
299 // for(int i=l;i<=_max_level;i++)
302 // _last_active[i]=f-1;
304 // for(Vit i=f;i!=_items.end();++i)
305 // _level[*i]=_max_level;
306 // for(_highest_active=l-1;
307 // _highest_active>=0 &&
308 // _last_active[_highest_active]<_first[_highest_active];
309 // _highest_active--) ;
312 ///Lift all nodes on and above a level to the top (and deactivate them).
314 ///This function lifts all nodes on and above level \c l to \c maxLevel(),
316 ///also deactivates them.
317 void liftToTop(int l)
319 const Vit f=_first[l];
320 const Vit tl=_first[_max_level];
321 for(Vit i=f;i!=tl;++i)
322 _level[*i]=_max_level;
323 for(int i=l;i<=_max_level;i++)
328 for(_highest_active=l-1;
329 _highest_active>=0 &&
330 _last_active[_highest_active]<_first[_highest_active];
340 ///\name Initialization
341 ///Using this function you can initialize the levels of the item.
343 ///This initializatios is started with calling \c initStart().
345 ///items should be listed levels by levels statring with the lowest one
346 ///(with level 0). This is done by using \c initAddItem()
347 ///and \c initNewLevel(). Finally \c initFinish() must be called.
348 ///The items not listed will be put on the highest level.
351 ///Start the initialization process.
356 _init_num=_items.begin();
357 _first[0]=_items.begin();
358 _last_active[0]=_items.begin()-1;
359 Vit n=_items.begin();
360 for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)
364 _level[i]=_max_level;
369 ///Add an item to the current level.
371 void initAddItem(Item i)
373 swap(_where[i],_init_num);
378 ///Start a new level.
380 ///Start a new level.
381 ///It shouldn't be used before the items on level 0 are listed.
385 _first[_init_lev]=_init_num;
386 _last_active[_init_lev]=_init_num-1;
389 ///Finalize the initialization process.
393 for(_init_lev++;_init_lev<=_max_level;_init_lev++)
395 _first[_init_lev]=_init_num;
396 _last_active[_init_lev]=_init_num-1;
398 _first[_max_level+1]=_items.begin()+_item_num;
399 _last_active[_max_level+1]=_items.begin()+_item_num-1;
406 } //END OF NAMESPACE LEMON