|
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library. |
|
4 * |
|
5 * Copyright (C) 2003-2008 |
|
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 ///\sa LinkedElevator |
|
46 /// |
|
47 ///\param Graph the underlying graph type |
|
48 ///\param Item Type of the items the data is assigned to (Graph::Node, |
|
49 ///Graph::Edge, Graph::UEdge) |
|
50 template<class Graph, class Item> |
|
51 class Elevator |
|
52 { |
|
53 public: |
|
54 |
|
55 typedef Item Key; |
|
56 typedef int Value; |
|
57 |
|
58 private: |
|
59 |
|
60 typedef typename std::vector<Item>::iterator Vit; |
|
61 typedef typename ItemSetTraits<Graph,Item>::template Map<Vit>::Type VitMap; |
|
62 typedef typename ItemSetTraits<Graph,Item>::template Map<int>::Type IntMap; |
|
63 |
|
64 const Graph &_g; |
|
65 int _max_level; |
|
66 int _item_num; |
|
67 VitMap _where; |
|
68 IntMap _level; |
|
69 std::vector<Item> _items; |
|
70 std::vector<Vit> _first; |
|
71 std::vector<Vit> _last_active; |
|
72 |
|
73 int _highest_active; |
|
74 |
|
75 void copy(Item i, Vit p) |
|
76 { |
|
77 _where[*p=i]=p; |
|
78 } |
|
79 void copy(Vit s, Vit p) |
|
80 { |
|
81 if(s!=p) |
|
82 { |
|
83 Item i=*s; |
|
84 *p=i; |
|
85 _where[i]=p; |
|
86 } |
|
87 } |
|
88 void swap(Vit i, Vit j) |
|
89 { |
|
90 Item ti=*i; |
|
91 Vit ct = _where[ti]; |
|
92 _where[ti]=_where[*i=*j]; |
|
93 _where[*j]=ct; |
|
94 *j=ti; |
|
95 } |
|
96 |
|
97 public: |
|
98 |
|
99 ///Constructor with given maximum level. |
|
100 |
|
101 ///Constructor with given maximum level. |
|
102 /// |
|
103 ///\param g The underlying graph |
|
104 ///\param max_level Set the range of the possible labels to |
|
105 ///[0...\c max_level] |
|
106 Elevator(const Graph &g,int max_level) : |
|
107 _g(g), |
|
108 _max_level(max_level), |
|
109 _item_num(_max_level), |
|
110 _where(g), |
|
111 _level(g,0), |
|
112 _items(_max_level), |
|
113 _first(_max_level+2), |
|
114 _last_active(_max_level+2), |
|
115 _highest_active(-1) {} |
|
116 ///Constructor. |
|
117 |
|
118 ///Constructor. |
|
119 /// |
|
120 ///\param g The underlying graph |
|
121 ///The range of the possible labels is [0...\c max_level], |
|
122 ///where \c max_level is equal to the number of labeled items in the graph. |
|
123 Elevator(const Graph &g) : |
|
124 _g(g), |
|
125 _max_level(countItems<Graph, Item>(g)), |
|
126 _item_num(_max_level), |
|
127 _where(g), |
|
128 _level(g,0), |
|
129 _items(_max_level), |
|
130 _first(_max_level+2), |
|
131 _last_active(_max_level+2), |
|
132 _highest_active(-1) |
|
133 { |
|
134 } |
|
135 |
|
136 ///Activate item \c i. |
|
137 |
|
138 ///Activate item \c i. |
|
139 ///\pre Item \c i shouldn't be active before. |
|
140 void activate(Item i) |
|
141 { |
|
142 const int l=_level[i]; |
|
143 swap(_where[i],++_last_active[l]); |
|
144 if(l>_highest_active) _highest_active=l; |
|
145 } |
|
146 |
|
147 ///Deactivate item \c i. |
|
148 |
|
149 ///Deactivate item \c i. |
|
150 ///\pre Item \c i must be active before. |
|
151 void deactivate(Item i) |
|
152 { |
|
153 swap(_where[i],_last_active[_level[i]]--); |
|
154 while(_highest_active>=0 && |
|
155 _last_active[_highest_active]<_first[_highest_active]) |
|
156 _highest_active--; |
|
157 } |
|
158 |
|
159 ///Query whether item \c i is active |
|
160 bool active(Item i) const { return _where[i]<=_last_active[_level[i]]; } |
|
161 |
|
162 ///Return the level of item \c i. |
|
163 int operator[](Item i) const { return _level[i]; } |
|
164 |
|
165 ///Return the number of items on level \c l. |
|
166 int onLevel(int l) const |
|
167 { |
|
168 return _first[l+1]-_first[l]; |
|
169 } |
|
170 ///Return true if the level is empty. |
|
171 bool emptyLevel(int l) const |
|
172 { |
|
173 return _first[l+1]-_first[l]==0; |
|
174 } |
|
175 ///Return the number of items above level \c l. |
|
176 int aboveLevel(int l) const |
|
177 { |
|
178 return _first[_max_level+1]-_first[l+1]; |
|
179 } |
|
180 ///Return the number of active items on level \c l. |
|
181 int activesOnLevel(int l) const |
|
182 { |
|
183 return _last_active[l]-_first[l]+1; |
|
184 } |
|
185 ///Return true if there is not active item on level \c l. |
|
186 bool activeFree(int l) const |
|
187 { |
|
188 return _last_active[l]<_first[l]; |
|
189 } |
|
190 ///Return the maximum allowed level. |
|
191 int maxLevel() const |
|
192 { |
|
193 return _max_level; |
|
194 } |
|
195 |
|
196 ///\name Highest Active Item |
|
197 ///Functions for working with the highest level |
|
198 ///active item. |
|
199 |
|
200 ///@{ |
|
201 |
|
202 ///Return a highest level active item. |
|
203 |
|
204 ///Return a highest level active item. |
|
205 /// |
|
206 ///\return the highest level active item or INVALID if there is no active |
|
207 ///item. |
|
208 Item highestActive() const |
|
209 { |
|
210 return _highest_active>=0?*_last_active[_highest_active]:INVALID; |
|
211 } |
|
212 |
|
213 ///Return a highest active level. |
|
214 |
|
215 ///Return a highest active level. |
|
216 /// |
|
217 ///\return the level of the highest active item or -1 if there is no active |
|
218 ///item. |
|
219 int highestActiveLevel() const |
|
220 { |
|
221 return _highest_active; |
|
222 } |
|
223 |
|
224 ///Lift the highest active item by one. |
|
225 |
|
226 ///Lift the item returned by highestActive() by one. |
|
227 /// |
|
228 void liftHighestActive() |
|
229 { |
|
230 ++_level[*_last_active[_highest_active]]; |
|
231 swap(_last_active[_highest_active]--,_last_active[_highest_active+1]); |
|
232 --_first[++_highest_active]; |
|
233 } |
|
234 |
|
235 ///Lift the highest active item. |
|
236 |
|
237 ///Lift the item returned by highestActive() to level \c new_level. |
|
238 /// |
|
239 ///\warning \c new_level must be strictly higher |
|
240 ///than the current level. |
|
241 /// |
|
242 void liftHighestActive(int new_level) |
|
243 { |
|
244 const Item li = *_last_active[_highest_active]; |
|
245 |
|
246 copy(--_first[_highest_active+1],_last_active[_highest_active]--); |
|
247 for(int l=_highest_active+1;l<new_level;l++) |
|
248 { |
|
249 copy(--_first[l+1],_first[l]); |
|
250 --_last_active[l]; |
|
251 } |
|
252 copy(li,_first[new_level]); |
|
253 _level[li]=new_level; |
|
254 _highest_active=new_level; |
|
255 } |
|
256 |
|
257 ///Lift the highest active item. |
|
258 |
|
259 ///Lift the item returned by highestActive() to the top level and |
|
260 ///deactivates it. |
|
261 /// |
|
262 ///\warning \c new_level must be strictly higher |
|
263 ///than the current level. |
|
264 /// |
|
265 void liftHighestActiveToTop() |
|
266 { |
|
267 const Item li = *_last_active[_highest_active]; |
|
268 |
|
269 copy(--_first[_highest_active+1],_last_active[_highest_active]--); |
|
270 for(int l=_highest_active+1;l<_max_level;l++) |
|
271 { |
|
272 copy(--_first[l+1],_first[l]); |
|
273 --_last_active[l]; |
|
274 } |
|
275 copy(li,_first[_max_level]); |
|
276 --_last_active[_max_level]; |
|
277 _level[li]=_max_level; |
|
278 |
|
279 while(_highest_active>=0 && |
|
280 _last_active[_highest_active]<_first[_highest_active]) |
|
281 _highest_active--; |
|
282 } |
|
283 |
|
284 ///@} |
|
285 |
|
286 ///\name Active Item on Certain Level |
|
287 ///Functions for working with the active items. |
|
288 |
|
289 ///@{ |
|
290 |
|
291 ///Returns an active item on level \c l. |
|
292 |
|
293 ///Returns an active item on level \c l. |
|
294 /// |
|
295 ///Returns an active item on level \c l or \ref INVALID if there is no such |
|
296 ///an item. (\c l must be from the range [0...\c max_level]. |
|
297 Item activeOn(int l) const |
|
298 { |
|
299 return _last_active[l]>=_first[l]?*_last_active[l]:INVALID; |
|
300 } |
|
301 |
|
302 ///Lifts the active item returned by \c activeOn() member function. |
|
303 |
|
304 ///Lifts the active item returned by \c activeOn() member function |
|
305 ///by one. |
|
306 Item liftActiveOn(int level) |
|
307 { |
|
308 ++_level[*_last_active[level]]; |
|
309 swap(_last_active[level]--, --_first[level+1]); |
|
310 if (level+1>_highest_active) ++_highest_active; |
|
311 } |
|
312 |
|
313 ///Lifts the active item returned by \c activeOn() member function. |
|
314 |
|
315 ///Lifts the active item returned by \c activeOn() member function |
|
316 ///to the given level. |
|
317 void liftActiveOn(int level, int new_level) |
|
318 { |
|
319 const Item ai = *_last_active[level]; |
|
320 |
|
321 copy(--_first[level+1], _last_active[level]--); |
|
322 for(int l=level+1;l<new_level;l++) |
|
323 { |
|
324 copy(_last_active[l],_first[l]); |
|
325 copy(--_first[l+1], _last_active[l]--); |
|
326 } |
|
327 copy(ai,_first[new_level]); |
|
328 _level[ai]=new_level; |
|
329 if (new_level>_highest_active) _highest_active=new_level; |
|
330 } |
|
331 |
|
332 ///Lifts the active item returned by \c activeOn() member function. |
|
333 |
|
334 ///Lifts the active item returned by \c activeOn() member function |
|
335 ///to the top level. |
|
336 void liftActiveToTop(int level) |
|
337 { |
|
338 const Item ai = *_last_active[level]; |
|
339 |
|
340 copy(--_first[level+1],_last_active[level]--); |
|
341 for(int l=level+1;l<_max_level;l++) |
|
342 { |
|
343 copy(_last_active[l],_first[l]); |
|
344 copy(--_first[l+1], _last_active[l]--); |
|
345 } |
|
346 copy(ai,_first[_max_level]); |
|
347 --_last_active[_max_level]; |
|
348 _level[ai]=_max_level; |
|
349 |
|
350 if (_highest_active==level) { |
|
351 while(_highest_active>=0 && |
|
352 _last_active[_highest_active]<_first[_highest_active]) |
|
353 _highest_active--; |
|
354 } |
|
355 } |
|
356 |
|
357 ///@} |
|
358 |
|
359 ///Lift an active item to a higher level. |
|
360 |
|
361 ///Lift an active item to a higher level. |
|
362 ///\param i The item to be lifted. It must be active. |
|
363 ///\param new_level The new level of \c i. It must be strictly higher |
|
364 ///than the current level. |
|
365 /// |
|
366 void lift(Item i, int new_level) |
|
367 { |
|
368 const int lo = _level[i]; |
|
369 const Vit w = _where[i]; |
|
370 |
|
371 copy(_last_active[lo],w); |
|
372 copy(--_first[lo+1],_last_active[lo]--); |
|
373 for(int l=lo+1;l<new_level;l++) |
|
374 { |
|
375 copy(_last_active[l],_first[l]); |
|
376 copy(--_first[l+1],_last_active[l]--); |
|
377 } |
|
378 copy(i,_first[new_level]); |
|
379 _level[i]=new_level; |
|
380 if(new_level>_highest_active) _highest_active=new_level; |
|
381 } |
|
382 |
|
383 ///Mark the node as it did not reach the max level |
|
384 |
|
385 ///Mark the node as it did not reach the max level. It sets the |
|
386 ///level to the under the max level value. The node will be never |
|
387 ///more activated because the push operation from the maximum |
|
388 ///level is forbidden in the push-relabel algorithms. The node |
|
389 ///should be lifted previously to the top level. |
|
390 void markToBottom(Item i) { |
|
391 _level[i] = _max_level - 1; |
|
392 } |
|
393 |
|
394 ///Lift all nodes on and above a level to the top (and deactivate them). |
|
395 |
|
396 ///This function lifts all nodes on and above level \c l to \c |
|
397 ///maxLevel(), and also deactivates them. |
|
398 void liftToTop(int l) |
|
399 { |
|
400 const Vit f=_first[l]; |
|
401 const Vit tl=_first[_max_level]; |
|
402 for(Vit i=f;i!=tl;++i) |
|
403 _level[*i]=_max_level; |
|
404 for(int i=l;i<=_max_level;i++) |
|
405 { |
|
406 _first[i]=f; |
|
407 _last_active[i]=f-1; |
|
408 } |
|
409 for(_highest_active=l-1; |
|
410 _highest_active>=0 && |
|
411 _last_active[_highest_active]<_first[_highest_active]; |
|
412 _highest_active--) ; |
|
413 } |
|
414 |
|
415 private: |
|
416 int _init_lev; |
|
417 Vit _init_num; |
|
418 |
|
419 public: |
|
420 |
|
421 ///\name Initialization |
|
422 ///Using this function you can initialize the levels of the item. |
|
423 ///\n |
|
424 ///This initializatios is started with calling \c initStart(). |
|
425 ///Then the |
|
426 ///items should be listed levels by levels statring with the lowest one |
|
427 ///(with level 0). This is done by using \c initAddItem() |
|
428 ///and \c initNewLevel(). Finally \c initFinish() must be called. |
|
429 ///The items not listed will be put on the highest level. |
|
430 ///@{ |
|
431 |
|
432 ///Start the initialization process. |
|
433 |
|
434 void initStart() |
|
435 { |
|
436 _init_lev=0; |
|
437 _init_num=_items.begin(); |
|
438 _first[0]=_items.begin(); |
|
439 _last_active[0]=_items.begin()-1; |
|
440 Vit n=_items.begin(); |
|
441 for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i) |
|
442 { |
|
443 *n=i; |
|
444 _where[i]=n; |
|
445 _level[i]=_max_level; |
|
446 ++n; |
|
447 } |
|
448 } |
|
449 |
|
450 ///Add an item to the current level. |
|
451 |
|
452 void initAddItem(Item i) |
|
453 { |
|
454 swap(_where[i],_init_num); |
|
455 _level[i]=_init_lev; |
|
456 ++_init_num; |
|
457 } |
|
458 |
|
459 ///Start a new level. |
|
460 |
|
461 ///Start a new level. |
|
462 ///It shouldn't be used before the items on level 0 are listed. |
|
463 void initNewLevel() |
|
464 { |
|
465 _init_lev++; |
|
466 _first[_init_lev]=_init_num; |
|
467 _last_active[_init_lev]=_init_num-1; |
|
468 } |
|
469 |
|
470 ///Finalize the initialization process. |
|
471 |
|
472 void initFinish() |
|
473 { |
|
474 for(_init_lev++;_init_lev<=_max_level;_init_lev++) |
|
475 { |
|
476 _first[_init_lev]=_init_num; |
|
477 _last_active[_init_lev]=_init_num-1; |
|
478 } |
|
479 _first[_max_level+1]=_items.begin()+_item_num; |
|
480 _last_active[_max_level+1]=_items.begin()+_item_num-1; |
|
481 _highest_active = -1; |
|
482 } |
|
483 |
|
484 ///@} |
|
485 |
|
486 }; |
|
487 |
|
488 ///Class for handling "labels" in push-relabel type algorithms. |
|
489 |
|
490 ///A class for handling "labels" in push-relabel type algorithms. |
|
491 /// |
|
492 ///\ingroup auxdat |
|
493 ///Using this class you can assign "labels" (nonnegative integer numbers) |
|
494 ///to the edges or nodes of a graph, manipulate and query them through |
|
495 ///operations typically arising in "push-relabel" type algorithms. |
|
496 /// |
|
497 ///Each item is either \em active or not, and you can also choose a |
|
498 ///highest level active item. |
|
499 /// |
|
500 ///\sa Elevator |
|
501 /// |
|
502 ///\param Graph the underlying graph type |
|
503 ///\param Item Type of the items the data is assigned to (Graph::Node, |
|
504 ///Graph::Edge, Graph::UEdge) |
|
505 template <class Graph, class Item> |
|
506 class LinkedElevator { |
|
507 public: |
|
508 |
|
509 typedef Item Key; |
|
510 typedef int Value; |
|
511 |
|
512 private: |
|
513 |
|
514 typedef typename ItemSetTraits<Graph,Item>:: |
|
515 template Map<Item>::Type ItemMap; |
|
516 typedef typename ItemSetTraits<Graph,Item>:: |
|
517 template Map<int>::Type IntMap; |
|
518 typedef typename ItemSetTraits<Graph,Item>:: |
|
519 template Map<bool>::Type BoolMap; |
|
520 |
|
521 const Graph &_graph; |
|
522 int _max_level; |
|
523 int _item_num; |
|
524 std::vector<Item> _first, _last; |
|
525 ItemMap _prev, _next; |
|
526 int _highest_active; |
|
527 IntMap _level; |
|
528 BoolMap _active; |
|
529 |
|
530 public: |
|
531 ///Constructor with given maximum level. |
|
532 |
|
533 ///Constructor with given maximum level. |
|
534 /// |
|
535 ///\param g The underlying graph |
|
536 ///\param max_level Set the range of the possible labels to |
|
537 ///[0...\c max_level] |
|
538 LinkedElevator(const Graph& graph, int max_level) |
|
539 : _graph(graph), _max_level(max_level), _item_num(_max_level), |
|
540 _first(_max_level + 1), _last(_max_level + 1), |
|
541 _prev(graph), _next(graph), |
|
542 _highest_active(-1), _level(graph), _active(graph) {} |
|
543 |
|
544 ///Constructor. |
|
545 |
|
546 ///Constructor. |
|
547 /// |
|
548 ///\param g The underlying graph |
|
549 ///The range of the possible labels is [0...\c max_level], |
|
550 ///where \c max_level is equal to the number of labeled items in the graph. |
|
551 LinkedElevator(const Graph& graph) |
|
552 : _graph(graph), _max_level(countItems<Graph, Item>(graph)), |
|
553 _item_num(_max_level), |
|
554 _first(_max_level + 1), _last(_max_level + 1), |
|
555 _prev(graph, INVALID), _next(graph, INVALID), |
|
556 _highest_active(-1), _level(graph), _active(graph) {} |
|
557 |
|
558 |
|
559 ///Activate item \c i. |
|
560 |
|
561 ///Activate item \c i. |
|
562 ///\pre Item \c i shouldn't be active before. |
|
563 void activate(Item i) { |
|
564 _active.set(i, true); |
|
565 |
|
566 int level = _level[i]; |
|
567 if (level > _highest_active) { |
|
568 _highest_active = level; |
|
569 } |
|
570 |
|
571 if (_prev[i] == INVALID || _active[_prev[i]]) return; |
|
572 //unlace |
|
573 _next.set(_prev[i], _next[i]); |
|
574 if (_next[i] != INVALID) { |
|
575 _prev.set(_next[i], _prev[i]); |
|
576 } else { |
|
577 _last[level] = _prev[i]; |
|
578 } |
|
579 //lace |
|
580 _next.set(i, _first[level]); |
|
581 _prev.set(_first[level], i); |
|
582 _prev.set(i, INVALID); |
|
583 _first[level] = i; |
|
584 |
|
585 } |
|
586 |
|
587 ///Deactivate item \c i. |
|
588 |
|
589 ///Deactivate item \c i. |
|
590 ///\pre Item \c i must be active before. |
|
591 void deactivate(Item i) { |
|
592 _active.set(i, false); |
|
593 int level = _level[i]; |
|
594 |
|
595 if (_next[i] == INVALID || !_active[_next[i]]) |
|
596 goto find_highest_level; |
|
597 |
|
598 //unlace |
|
599 _prev.set(_next[i], _prev[i]); |
|
600 if (_prev[i] != INVALID) { |
|
601 _next.set(_prev[i], _next[i]); |
|
602 } else { |
|
603 _first[_level[i]] = _next[i]; |
|
604 } |
|
605 //lace |
|
606 _prev.set(i, _last[level]); |
|
607 _next.set(_last[level], i); |
|
608 _next.set(i, INVALID); |
|
609 _last[level] = i; |
|
610 |
|
611 find_highest_level: |
|
612 if (level == _highest_active) { |
|
613 while (_highest_active >= 0 && activeFree(_highest_active)) |
|
614 --_highest_active; |
|
615 } |
|
616 } |
|
617 |
|
618 ///Query whether item \c i is active |
|
619 bool active(Item i) const { return _active[i]; } |
|
620 |
|
621 ///Return the level of item \c i. |
|
622 int operator[](Item i) const { return _level[i]; } |
|
623 |
|
624 ///Return the number of items on level \c l. |
|
625 int onLevel(int l) const { |
|
626 int num = 0; |
|
627 Item n = _first[l]; |
|
628 while (n != INVALID) { |
|
629 ++num; |
|
630 n = _next[n]; |
|
631 } |
|
632 return num; |
|
633 } |
|
634 |
|
635 ///Return true if the level is empty. |
|
636 bool emptyLevel(int l) const { |
|
637 return _first[l] == INVALID; |
|
638 } |
|
639 |
|
640 ///Return the number of items above level \c l. |
|
641 int aboveLevel(int l) const { |
|
642 int num = 0; |
|
643 for (int level = l + 1; level < _max_level; ++level) |
|
644 num += onLevel(level); |
|
645 return num; |
|
646 } |
|
647 |
|
648 ///Return the number of active items on level \c l. |
|
649 int activesOnLevel(int l) const { |
|
650 int num = 0; |
|
651 Item n = _first[l]; |
|
652 while (n != INVALID && _active[n]) { |
|
653 ++num; |
|
654 n = _next[n]; |
|
655 } |
|
656 return num; |
|
657 } |
|
658 |
|
659 ///Return true if there is not active item on level \c l. |
|
660 bool activeFree(int l) const { |
|
661 return _first[l] == INVALID || !_active[_first[l]]; |
|
662 } |
|
663 |
|
664 ///Return the maximum allowed level. |
|
665 int maxLevel() const { |
|
666 return _max_level; |
|
667 } |
|
668 |
|
669 ///\name Highest Active Item |
|
670 ///Functions for working with the highest level |
|
671 ///active item. |
|
672 |
|
673 ///@{ |
|
674 |
|
675 ///Return a highest level active item. |
|
676 |
|
677 ///Return a highest level active item. |
|
678 /// |
|
679 ///\return the highest level active item or INVALID if there is no |
|
680 ///active item. |
|
681 Item highestActive() const { |
|
682 return _highest_active >= 0 ? _first[_highest_active] : INVALID; |
|
683 } |
|
684 |
|
685 ///Return a highest active level. |
|
686 |
|
687 ///Return a highest active level. |
|
688 /// |
|
689 ///\return the level of the highest active item or -1 if there is |
|
690 ///no active item. |
|
691 int highestActiveLevel() const { |
|
692 return _highest_active; |
|
693 } |
|
694 |
|
695 ///Lift the highest active item by one. |
|
696 |
|
697 ///Lift the item returned by highestActive() by one. |
|
698 /// |
|
699 void liftHighestActive() { |
|
700 Item i = _first[_highest_active]; |
|
701 if (_next[i] != INVALID) { |
|
702 _prev.set(_next[i], INVALID); |
|
703 _first[_highest_active] = _next[i]; |
|
704 } else { |
|
705 _first[_highest_active] = INVALID; |
|
706 _last[_highest_active] = INVALID; |
|
707 } |
|
708 _level.set(i, ++_highest_active); |
|
709 if (_first[_highest_active] == INVALID) { |
|
710 _first[_highest_active] = i; |
|
711 _last[_highest_active] = i; |
|
712 _prev.set(i, INVALID); |
|
713 _next.set(i, INVALID); |
|
714 } else { |
|
715 _prev.set(_first[_highest_active], i); |
|
716 _next.set(i, _first[_highest_active]); |
|
717 _first[_highest_active] = i; |
|
718 } |
|
719 } |
|
720 |
|
721 ///Lift the highest active item. |
|
722 |
|
723 ///Lift the item returned by highestActive() to level \c new_level. |
|
724 /// |
|
725 ///\warning \c new_level must be strictly higher |
|
726 ///than the current level. |
|
727 /// |
|
728 void liftHighestActive(int new_level) { |
|
729 Item i = _first[_highest_active]; |
|
730 if (_next[i] != INVALID) { |
|
731 _prev.set(_next[i], INVALID); |
|
732 _first[_highest_active] = _next[i]; |
|
733 } else { |
|
734 _first[_highest_active] = INVALID; |
|
735 _last[_highest_active] = INVALID; |
|
736 } |
|
737 _level.set(i, _highest_active = new_level); |
|
738 if (_first[_highest_active] == INVALID) { |
|
739 _first[_highest_active] = _last[_highest_active] = i; |
|
740 _prev.set(i, INVALID); |
|
741 _next.set(i, INVALID); |
|
742 } else { |
|
743 _prev.set(_first[_highest_active], i); |
|
744 _next.set(i, _first[_highest_active]); |
|
745 _first[_highest_active] = i; |
|
746 } |
|
747 } |
|
748 |
|
749 ///Lift the highest active to top. |
|
750 |
|
751 ///Lift the item returned by highestActive() to the top level and |
|
752 ///deactivates the node. |
|
753 /// |
|
754 void liftHighestActiveToTop() { |
|
755 Item i = _first[_highest_active]; |
|
756 _level.set(i, _max_level); |
|
757 if (_next[i] != INVALID) { |
|
758 _prev.set(_next[i], INVALID); |
|
759 _first[_highest_active] = _next[i]; |
|
760 } else { |
|
761 _first[_highest_active] = INVALID; |
|
762 _last[_highest_active] = INVALID; |
|
763 } |
|
764 while (_highest_active >= 0 && activeFree(_highest_active)) |
|
765 --_highest_active; |
|
766 } |
|
767 |
|
768 ///@} |
|
769 |
|
770 ///\name Active Item on Certain Level |
|
771 ///Functions for working with the active items. |
|
772 |
|
773 ///@{ |
|
774 |
|
775 ///Returns an active item on level \c l. |
|
776 |
|
777 ///Returns an active item on level \c l. |
|
778 /// |
|
779 ///Returns an active item on level \c l or \ref INVALID if there is no such |
|
780 ///an item. (\c l must be from the range [0...\c max_level]. |
|
781 Item activeOn(int l) const |
|
782 { |
|
783 return _active[_first[l]] ? _first[l] : INVALID; |
|
784 } |
|
785 |
|
786 ///Lifts the active item returned by \c activeOn() member function. |
|
787 |
|
788 ///Lifts the active item returned by \c activeOn() member function |
|
789 ///by one. |
|
790 Item liftActiveOn(int l) |
|
791 { |
|
792 Item i = _first[l]; |
|
793 if (_next[i] != INVALID) { |
|
794 _prev.set(_next[i], INVALID); |
|
795 _first[l] = _next[i]; |
|
796 } else { |
|
797 _first[l] = INVALID; |
|
798 _last[l] = INVALID; |
|
799 } |
|
800 _level.set(i, ++l); |
|
801 if (_first[l] == INVALID) { |
|
802 _first[l] = _last[l] = i; |
|
803 _prev.set(i, INVALID); |
|
804 _next.set(i, INVALID); |
|
805 } else { |
|
806 _prev.set(_first[l], i); |
|
807 _next.set(i, _first[l]); |
|
808 _first[l] = i; |
|
809 } |
|
810 if (_highest_active < l) { |
|
811 _highest_active = l; |
|
812 } |
|
813 } |
|
814 |
|
815 /// \brief Lifts the active item returned by \c activeOn() member function. |
|
816 /// |
|
817 /// Lifts the active item returned by \c activeOn() member function |
|
818 /// to the given level. |
|
819 void liftActiveOn(int l, int new_level) |
|
820 { |
|
821 Item i = _first[l]; |
|
822 if (_next[i] != INVALID) { |
|
823 _prev.set(_next[i], INVALID); |
|
824 _first[l] = _next[i]; |
|
825 } else { |
|
826 _first[l] = INVALID; |
|
827 _last[l] = INVALID; |
|
828 } |
|
829 _level.set(i, l = new_level); |
|
830 if (_first[l] == INVALID) { |
|
831 _first[l] = _last[l] = i; |
|
832 _prev.set(i, INVALID); |
|
833 _next.set(i, INVALID); |
|
834 } else { |
|
835 _prev.set(_first[l], i); |
|
836 _next.set(i, _first[l]); |
|
837 _first[l] = i; |
|
838 } |
|
839 if (_highest_active < l) { |
|
840 _highest_active = l; |
|
841 } |
|
842 } |
|
843 |
|
844 ///Lifts the active item returned by \c activeOn() member function. |
|
845 |
|
846 ///Lifts the active item returned by \c activeOn() member function |
|
847 ///to the top level. |
|
848 void liftActiveToTop(int l) |
|
849 { |
|
850 Item i = _first[l]; |
|
851 if (_next[i] != INVALID) { |
|
852 _prev.set(_next[i], INVALID); |
|
853 _first[l] = _next[i]; |
|
854 } else { |
|
855 _first[l] = INVALID; |
|
856 _last[l] = INVALID; |
|
857 } |
|
858 _level.set(i, _max_level); |
|
859 if (l == _highest_active) { |
|
860 while (_highest_active >= 0 && activeFree(_highest_active)) |
|
861 --_highest_active; |
|
862 } |
|
863 } |
|
864 |
|
865 ///@} |
|
866 |
|
867 /// \brief Lift an active item to a higher level. |
|
868 /// |
|
869 /// Lift an active item to a higher level. |
|
870 /// \param i The item to be lifted. It must be active. |
|
871 /// \param new_level The new level of \c i. It must be strictly higher |
|
872 /// than the current level. |
|
873 /// |
|
874 void lift(Item i, int new_level) { |
|
875 if (_next[i] != INVALID) { |
|
876 _prev.set(_next[i], _prev[i]); |
|
877 } else { |
|
878 _last[new_level] = _prev[i]; |
|
879 } |
|
880 if (_prev[i] != INVALID) { |
|
881 _next.set(_prev[i], _next[i]); |
|
882 } else { |
|
883 _first[new_level] = _next[i]; |
|
884 } |
|
885 _level.set(i, new_level); |
|
886 if (_first[new_level] == INVALID) { |
|
887 _first[new_level] = _last[new_level] = i; |
|
888 _prev.set(i, INVALID); |
|
889 _next.set(i, INVALID); |
|
890 } else { |
|
891 _prev.set(_first[new_level], i); |
|
892 _next.set(i, _first[new_level]); |
|
893 _first[new_level] = i; |
|
894 } |
|
895 if (_highest_active < new_level) { |
|
896 _highest_active = new_level; |
|
897 } |
|
898 } |
|
899 |
|
900 ///Mark the node as it did not reach the max level |
|
901 |
|
902 ///Mark the node as it did not reach the max level. It sets the |
|
903 ///level to the under the max level value. The node will be never |
|
904 ///more activated because the push operation from the maximum |
|
905 ///level is forbidden in the push-relabel algorithms. The node |
|
906 ///should be lifted previously to the top level. |
|
907 void markToBottom(Item i) { |
|
908 _level.set(i, _max_level - 1); |
|
909 } |
|
910 |
|
911 ///Lift all nodes on and above a level to the top (and deactivate them). |
|
912 |
|
913 ///This function lifts all nodes on and above level \c l to \c |
|
914 ///maxLevel(), and also deactivates them. |
|
915 void liftToTop(int l) { |
|
916 for (int i = l + 1; _first[i] != INVALID; ++i) { |
|
917 Item n = _first[i]; |
|
918 while (n != INVALID) { |
|
919 _level.set(n, _max_level); |
|
920 n = _next[n]; |
|
921 } |
|
922 _first[i] = INVALID; |
|
923 _last[i] = INVALID; |
|
924 } |
|
925 if (_highest_active > l - 1) { |
|
926 _highest_active = l - 1; |
|
927 while (_highest_active >= 0 && activeFree(_highest_active)) |
|
928 --_highest_active; |
|
929 } |
|
930 } |
|
931 |
|
932 private: |
|
933 |
|
934 int _init_level; |
|
935 |
|
936 public: |
|
937 |
|
938 ///\name Initialization |
|
939 ///Using this function you can initialize the levels of the item. |
|
940 ///\n |
|
941 ///This initializatios is started with calling \c initStart(). |
|
942 ///Then the |
|
943 ///items should be listed levels by levels statring with the lowest one |
|
944 ///(with level 0). This is done by using \c initAddItem() |
|
945 ///and \c initNewLevel(). Finally \c initFinish() must be called. |
|
946 ///The items not listed will be put on the highest level. |
|
947 ///@{ |
|
948 |
|
949 ///Start the initialization process. |
|
950 |
|
951 void initStart() { |
|
952 |
|
953 for (int i = 0; i <= _max_level; ++i) { |
|
954 _first[i] = _last[i] = INVALID; |
|
955 } |
|
956 _init_level = 0; |
|
957 for(typename ItemSetTraits<Graph,Item>::ItemIt i(_graph); |
|
958 i != INVALID; ++i) { |
|
959 _level.set(i, _max_level); |
|
960 _active.set(i, false); |
|
961 } |
|
962 } |
|
963 |
|
964 ///Add an item to the current level. |
|
965 |
|
966 void initAddItem(Item i) { |
|
967 _level.set(i, _init_level); |
|
968 if (_last[_init_level] == INVALID) { |
|
969 _first[_init_level] = i; |
|
970 _last[_init_level] = i; |
|
971 _prev.set(i, INVALID); |
|
972 _next.set(i, INVALID); |
|
973 } else { |
|
974 _prev.set(i, _last[_init_level]); |
|
975 _next.set(i, INVALID); |
|
976 _next.set(_last[_init_level], i); |
|
977 _last[_init_level] = i; |
|
978 } |
|
979 } |
|
980 |
|
981 ///Start a new level. |
|
982 |
|
983 ///Start a new level. |
|
984 ///It shouldn't be used before the items on level 0 are listed. |
|
985 void initNewLevel() { |
|
986 ++_init_level; |
|
987 } |
|
988 |
|
989 ///Finalize the initialization process. |
|
990 |
|
991 void initFinish() { |
|
992 _highest_active = -1; |
|
993 } |
|
994 |
|
995 ///@} |
|
996 |
|
997 }; |
|
998 |
|
999 |
|
1000 } //END OF NAMESPACE LEMON |
|
1001 |
|
1002 #endif |
|
1003 |