1 | /* -*- C++ -*- |
---|
2 | * |
---|
3 | * This file is a part of LEMON, a generic C++ optimization library |
---|
4 | * |
---|
5 | * Copyright (C) 2003-2007 |
---|
6 | * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
---|
7 | * (Egervary Research Group on Combinatorial Optimization, EGRES). |
---|
8 | * |
---|
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. |
---|
12 | * |
---|
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 |
---|
15 | * purpose. |
---|
16 | * |
---|
17 | */ |
---|
18 | |
---|
19 | #ifndef LEMON_ELEVATOR_H |
---|
20 | #define LEMON_ELEVATOR_H |
---|
21 | |
---|
22 | ///\ingroup auxdat |
---|
23 | ///\file |
---|
24 | ///\brief Elevator class |
---|
25 | /// |
---|
26 | ///Elevator class implements an efficient data structure |
---|
27 | ///for labeling items in push-relabel type algorithms. |
---|
28 | /// |
---|
29 | |
---|
30 | #include <test/test_tools.h> |
---|
31 | namespace lemon { |
---|
32 | |
---|
33 | ///Class for handling "labels" in push-relabel type algorithms. |
---|
34 | |
---|
35 | ///A class for handling "labels" in push-relabel type algorithms. |
---|
36 | /// |
---|
37 | ///\ingroup auxdat |
---|
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. |
---|
41 | /// |
---|
42 | ///Each item is either \em active or not, and you can also choose a |
---|
43 | ///highest level active item. |
---|
44 | /// |
---|
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> |
---|
49 | class Elevator |
---|
50 | { |
---|
51 | public: |
---|
52 | typedef typename std::vector<Item>::iterator Vit; |
---|
53 | typedef DefaultMap<Graph,Item,Vit> VitMap; |
---|
54 | typedef DefaultMap<Graph,Item,int> IntMap; |
---|
55 | |
---|
56 | const Graph &_g; |
---|
57 | int _max_level; |
---|
58 | int _item_num; |
---|
59 | VitMap _where; |
---|
60 | IntMap _level; |
---|
61 | std::vector<Item> _items; |
---|
62 | std::vector<Vit> _first; |
---|
63 | std::vector<Vit> _last_active; |
---|
64 | |
---|
65 | int _highest_active; |
---|
66 | |
---|
67 | void copy(Item i, Vit p) |
---|
68 | { |
---|
69 | _where[*p=i]=p; |
---|
70 | } |
---|
71 | void copy(Vit s, Vit p) |
---|
72 | { |
---|
73 | if(s!=p) |
---|
74 | { |
---|
75 | Item i=*s; |
---|
76 | *p=i; |
---|
77 | _where[i]=p; |
---|
78 | } |
---|
79 | } |
---|
80 | void swap(Vit i, Vit j) |
---|
81 | { |
---|
82 | Item ti=*i; |
---|
83 | Vit ct = _where[ti]; |
---|
84 | _where[ti]=_where[*i=*j]; |
---|
85 | _where[*j]=ct; |
---|
86 | *j=ti; |
---|
87 | } |
---|
88 | |
---|
89 | void checkDs() const |
---|
90 | { |
---|
91 | for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i) |
---|
92 | { |
---|
93 | Vit w=_where[i]; |
---|
94 | int l=_level[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"); |
---|
98 | } |
---|
99 | for(int l=0;l<=_max_level;++l) |
---|
100 | { |
---|
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"); |
---|
104 | } |
---|
105 | check(_highest_active<0 || |
---|
106 | _first[_highest_active]<=_last_active[_highest_active], |
---|
107 | "GEBASZ: CORRUPT DS"); |
---|
108 | } |
---|
109 | |
---|
110 | public: |
---|
111 | ///Constructor with given maximum level. |
---|
112 | |
---|
113 | ///Constructor with given maximum level. |
---|
114 | /// |
---|
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) : |
---|
119 | _g(g), |
---|
120 | _max_level(max_level), |
---|
121 | _item_num(_max_level), |
---|
122 | _where(g), |
---|
123 | _level(g,0), |
---|
124 | _items(_max_level), |
---|
125 | _first(_max_level+2), |
---|
126 | _last_active(_max_level+2), |
---|
127 | _highest_active(-1) {} |
---|
128 | ///Constructor. |
---|
129 | |
---|
130 | ///Constructor. |
---|
131 | /// |
---|
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) : |
---|
136 | _g(g), |
---|
137 | _max_level(countItems<Graph, Item>(g)), |
---|
138 | _item_num(_max_level), |
---|
139 | _where(g), |
---|
140 | _level(g,0), |
---|
141 | _items(_max_level), |
---|
142 | _first(_max_level+2), |
---|
143 | _last_active(_max_level+2), |
---|
144 | _highest_active(-1) |
---|
145 | { |
---|
146 | } |
---|
147 | |
---|
148 | ///Activate item \c i. |
---|
149 | |
---|
150 | ///Activate item \c i. |
---|
151 | ///\pre Item \c i shouldn't be active before. |
---|
152 | void activate(Item i) |
---|
153 | { |
---|
154 | const int l=_level[i]; |
---|
155 | swap(_where[i],++_last_active[l]); |
---|
156 | if(l>_highest_active) _highest_active=l; |
---|
157 | } |
---|
158 | |
---|
159 | ///Deactivate item \c i. |
---|
160 | |
---|
161 | ///Deactivate item \c i. |
---|
162 | ///\pre Item \c i must be active before. |
---|
163 | void deactivate(Item i) |
---|
164 | { |
---|
165 | swap(_where[i],_last_active[_level[i]]--); |
---|
166 | while(_highest_active>=0 && |
---|
167 | _last_active[_highest_active]<_first[_highest_active]) |
---|
168 | _highest_active--; |
---|
169 | } |
---|
170 | |
---|
171 | ///Query whether item \c i is active |
---|
172 | bool active(Item i) const { return _where[i]<=_last_active[_level[i]]; } |
---|
173 | |
---|
174 | ///Return the level of item \c i. |
---|
175 | int operator[](Item i) const { return _level[i]; } |
---|
176 | |
---|
177 | ///Returns an active item on level \c l. |
---|
178 | |
---|
179 | ///Returns an active item on level \c l. |
---|
180 | /// |
---|
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 |
---|
184 | { |
---|
185 | return _last_active[l]>=_first[l]?*_last_active[l]:INVALID; |
---|
186 | } |
---|
187 | |
---|
188 | ///Return the number of items on level \c l. |
---|
189 | int onLevel(int l) const |
---|
190 | { |
---|
191 | return _first[l+1]-_first[l]; |
---|
192 | } |
---|
193 | ///Return the number of items above level \c l. |
---|
194 | int aboveLevel(int l) const |
---|
195 | { |
---|
196 | return _first[_max_level+1]-_first[l+1]; |
---|
197 | } |
---|
198 | ///Return the number of active items on level \c l. |
---|
199 | int activesOnLevel(int l) const |
---|
200 | { |
---|
201 | return _last_active[l]-_first[l]+1; |
---|
202 | } |
---|
203 | ///Return the maximum allowed level. |
---|
204 | int maxLevel() const |
---|
205 | { |
---|
206 | return _max_level; |
---|
207 | } |
---|
208 | |
---|
209 | ///\name Highest Active Item |
---|
210 | ///Functions for working with the highest level |
---|
211 | ///active item. |
---|
212 | |
---|
213 | ///@{ |
---|
214 | |
---|
215 | ///Return a highest level active item. |
---|
216 | |
---|
217 | ///Return a highest level active item. |
---|
218 | /// |
---|
219 | ///\return the highest level active item or INVALID if there is no active |
---|
220 | ///item. |
---|
221 | Item highestActive() const |
---|
222 | { |
---|
223 | return _highest_active>=0?*_last_active[_highest_active]:INVALID; |
---|
224 | } |
---|
225 | |
---|
226 | ///Return a highest active level. |
---|
227 | |
---|
228 | ///Return a highest active level. |
---|
229 | /// |
---|
230 | ///\return the level of the highest active item or -1 if there is no active |
---|
231 | ///item. |
---|
232 | int highestActiveLevel() const |
---|
233 | { |
---|
234 | return _highest_active; |
---|
235 | } |
---|
236 | |
---|
237 | ///Lift the highest active item by one. |
---|
238 | |
---|
239 | ///Lift the item returned by highestActive() by one. |
---|
240 | /// |
---|
241 | void liftHighestActive() |
---|
242 | { |
---|
243 | ++_level[*_last_active[_highest_active]]; |
---|
244 | swap(_last_active[_highest_active]--,_last_active[_highest_active+1]); |
---|
245 | --_first[++_highest_active]; |
---|
246 | } |
---|
247 | |
---|
248 | ///Lift the highest active item. |
---|
249 | |
---|
250 | ///Lift the item returned by highestActive() to level \c new_level. |
---|
251 | /// |
---|
252 | ///\warning \c new_level must be strictly higher |
---|
253 | ///than the current level. |
---|
254 | /// |
---|
255 | void liftHighestActiveTo(int new_level) |
---|
256 | { |
---|
257 | const Item li = *_last_active[_highest_active]; |
---|
258 | |
---|
259 | copy(--_first[_highest_active+1],_last_active[_highest_active]--); |
---|
260 | for(int l=_highest_active+1;l<new_level;l++) |
---|
261 | { |
---|
262 | copy(--_first[l+1],_first[l]); |
---|
263 | --_last_active[l]; |
---|
264 | } |
---|
265 | copy(li,_first[new_level]); |
---|
266 | _level[li]=new_level; |
---|
267 | _highest_active=new_level; |
---|
268 | } |
---|
269 | |
---|
270 | ///@} |
---|
271 | |
---|
272 | ///Lift an active item to a higher level. |
---|
273 | |
---|
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. |
---|
278 | /// |
---|
279 | void liftTo(Item i, int new_level) |
---|
280 | { |
---|
281 | const int lo = _level[i]; |
---|
282 | const Vit w = _where[i]; |
---|
283 | |
---|
284 | copy(_last_active[lo],w); |
---|
285 | copy(--_first[lo+1],_last_active[lo]--); |
---|
286 | for(int l=lo+1;l<new_level;l++) |
---|
287 | { |
---|
288 | copy(_last_active[l],_first[l]); |
---|
289 | copy(--_first[l+1],_last_active[l]--); |
---|
290 | } |
---|
291 | copy(i,_first[new_level]); |
---|
292 | _level[i]=new_level; |
---|
293 | if(new_level>_highest_active) _highest_active=new_level; |
---|
294 | } |
---|
295 | |
---|
296 | // void liftToTop(int l) |
---|
297 | // { |
---|
298 | // const Vit f=_first[l]; |
---|
299 | // for(int i=l;i<=_max_level;i++) |
---|
300 | // { |
---|
301 | // _first[i]=f; |
---|
302 | // _last_active[i]=f-1; |
---|
303 | // } |
---|
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--) ; |
---|
310 | // } |
---|
311 | |
---|
312 | ///Lift all nodes on and above a level to the top (and deactivate them). |
---|
313 | |
---|
314 | ///This function lifts all nodes on and above level \c l to \c maxLevel(), |
---|
315 | ///and |
---|
316 | ///also deactivates them. |
---|
317 | void liftToTop(int l) |
---|
318 | { |
---|
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++) |
---|
324 | { |
---|
325 | _first[i]=f; |
---|
326 | _last_active[i]=f-1; |
---|
327 | } |
---|
328 | for(_highest_active=l-1; |
---|
329 | _highest_active>=0 && |
---|
330 | _last_active[_highest_active]<_first[_highest_active]; |
---|
331 | _highest_active--) ; |
---|
332 | } |
---|
333 | |
---|
334 | private: |
---|
335 | int _init_lev; |
---|
336 | Vit _init_num; |
---|
337 | |
---|
338 | public: |
---|
339 | |
---|
340 | ///\name Initialization |
---|
341 | ///Using this function you can initialize the levels of the item. |
---|
342 | ///\n |
---|
343 | ///This initializatios is started with calling \c initStart(). |
---|
344 | ///Then the |
---|
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. |
---|
349 | ///@{ |
---|
350 | |
---|
351 | ///Start the initialization process. |
---|
352 | |
---|
353 | void initStart() |
---|
354 | { |
---|
355 | _init_lev=0; |
---|
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) |
---|
361 | { |
---|
362 | *n=i; |
---|
363 | _where[i]=n; |
---|
364 | _level[i]=_max_level; |
---|
365 | ++n; |
---|
366 | } |
---|
367 | } |
---|
368 | |
---|
369 | ///Add an item to the current level. |
---|
370 | |
---|
371 | void initAddItem(Item i) |
---|
372 | { |
---|
373 | swap(_where[i],_init_num); |
---|
374 | _level[i]=_init_lev; |
---|
375 | ++_init_num; |
---|
376 | } |
---|
377 | |
---|
378 | ///Start a new level. |
---|
379 | |
---|
380 | ///Start a new level. |
---|
381 | ///It shouldn't be used before the items on level 0 are listed. |
---|
382 | void initNewLevel() |
---|
383 | { |
---|
384 | _init_lev++; |
---|
385 | _first[_init_lev]=_init_num; |
---|
386 | _last_active[_init_lev]=_init_num-1; |
---|
387 | } |
---|
388 | |
---|
389 | ///Finalize the initialization process. |
---|
390 | |
---|
391 | void initFinish() |
---|
392 | { |
---|
393 | for(_init_lev++;_init_lev<=_max_level;_init_lev++) |
---|
394 | { |
---|
395 | _first[_init_lev]=_init_num; |
---|
396 | _last_active[_init_lev]=_init_num-1; |
---|
397 | } |
---|
398 | _first[_max_level+1]=_items.begin()+_item_num; |
---|
399 | _last_active[_max_level+1]=_items.begin()+_item_num-1; |
---|
400 | } |
---|
401 | |
---|
402 | ///@} |
---|
403 | |
---|
404 | }; |
---|
405 | |
---|
406 | } //END OF NAMESPACE LEMON |
---|
407 | |
---|
408 | #endif |
---|
409 | |
---|