3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2008
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.
32 ///Class for handling "labels" in push-relabel type algorithms.
34 ///A class for handling "labels" in push-relabel type algorithms.
37 ///Using this class you can assign "labels" (nonnegative integer numbers)
38 ///to the edges or nodes of a graph, manipulate and query them through
39 ///operations typically arising in "push-relabel" type algorithms.
41 ///Each item is either \em active or not, and you can also choose a
42 ///highest level active item.
46 ///\param Graph the underlying graph type
47 ///\param Item Type of the items the data is assigned to (Graph::Node,
48 ///Graph::Edge, Graph::UEdge)
49 template<class Graph, class Item>
59 typedef typename std::vector<Item>::iterator Vit;
60 typedef typename ItemSetTraits<Graph,Item>::template Map<Vit>::Type VitMap;
61 typedef typename ItemSetTraits<Graph,Item>::template Map<int>::Type IntMap;
68 std::vector<Item> _items;
69 std::vector<Vit> _first;
70 std::vector<Vit> _last_active;
74 void copy(Item i, Vit p)
78 void copy(Vit s, Vit p)
87 void swap(Vit i, Vit j)
91 _where[ti]=_where[*i=*j];
98 ///Constructor with given maximum level.
100 ///Constructor with given maximum level.
102 ///\param g The underlying graph
103 ///\param max_level Set the range of the possible labels to
104 ///[0...\c max_level]
105 Elevator(const Graph &g,int max_level) :
107 _max_level(max_level),
108 _item_num(_max_level),
112 _first(_max_level+2),
113 _last_active(_max_level+2),
114 _highest_active(-1) {}
119 ///\param g The underlying graph
120 ///The range of the possible labels is [0...\c max_level],
121 ///where \c max_level is equal to the number of labeled items in the graph.
122 Elevator(const Graph &g) :
124 _max_level(countItems<Graph, Item>(g)),
125 _item_num(_max_level),
129 _first(_max_level+2),
130 _last_active(_max_level+2),
135 ///Activate item \c i.
137 ///Activate item \c i.
138 ///\pre Item \c i shouldn't be active before.
139 void activate(Item i)
141 const int l=_level[i];
142 swap(_where[i],++_last_active[l]);
143 if(l>_highest_active) _highest_active=l;
146 ///Deactivate item \c i.
148 ///Deactivate item \c i.
149 ///\pre Item \c i must be active before.
150 void deactivate(Item i)
152 swap(_where[i],_last_active[_level[i]]--);
153 while(_highest_active>=0 &&
154 _last_active[_highest_active]<_first[_highest_active])
158 ///Query whether item \c i is active
159 bool active(Item i) const { return _where[i]<=_last_active[_level[i]]; }
161 ///Return the level of item \c i.
162 int operator[](Item i) const { return _level[i]; }
164 ///Return the number of items on level \c l.
165 int onLevel(int l) const
167 return _first[l+1]-_first[l];
169 ///Return true if the level is empty.
170 bool emptyLevel(int l) const
172 return _first[l+1]-_first[l]==0;
174 ///Return the number of items above level \c l.
175 int aboveLevel(int l) const
177 return _first[_max_level+1]-_first[l+1];
179 ///Return the number of active items on level \c l.
180 int activesOnLevel(int l) const
182 return _last_active[l]-_first[l]+1;
184 ///Return true if there is not active item on level \c l.
185 bool activeFree(int l) const
187 return _last_active[l]<_first[l];
189 ///Return the maximum allowed level.
195 ///\name Highest Active Item
196 ///Functions for working with the highest level
201 ///Return a highest level active item.
203 ///Return a highest level active item.
205 ///\return the highest level active item or INVALID if there is no active
207 Item highestActive() const
209 return _highest_active>=0?*_last_active[_highest_active]:INVALID;
212 ///Return a highest active level.
214 ///Return a highest active level.
216 ///\return the level of the highest active item or -1 if there is no active
218 int highestActiveLevel() const
220 return _highest_active;
223 ///Lift the highest active item by one.
225 ///Lift the item returned by highestActive() by one.
227 void liftHighestActive()
229 ++_level[*_last_active[_highest_active]];
230 swap(_last_active[_highest_active]--,_last_active[_highest_active+1]);
231 --_first[++_highest_active];
234 ///Lift the highest active item.
236 ///Lift the item returned by highestActive() to level \c new_level.
238 ///\warning \c new_level must be strictly higher
239 ///than the current level.
241 void liftHighestActive(int new_level)
243 const Item li = *_last_active[_highest_active];
245 copy(--_first[_highest_active+1],_last_active[_highest_active]--);
246 for(int l=_highest_active+1;l<new_level;l++)
248 copy(--_first[l+1],_first[l]);
251 copy(li,_first[new_level]);
252 _level[li]=new_level;
253 _highest_active=new_level;
256 ///Lift the highest active item.
258 ///Lift the item returned by highestActive() to the top level and
261 ///\warning \c new_level must be strictly higher
262 ///than the current level.
264 void liftHighestActiveToTop()
266 const Item li = *_last_active[_highest_active];
268 copy(--_first[_highest_active+1],_last_active[_highest_active]--);
269 for(int l=_highest_active+1;l<_max_level;l++)
271 copy(--_first[l+1],_first[l]);
274 copy(li,_first[_max_level]);
275 --_last_active[_max_level];
276 _level[li]=_max_level;
278 while(_highest_active>=0 &&
279 _last_active[_highest_active]<_first[_highest_active])
285 ///\name Active Item on Certain Level
286 ///Functions for working with the active items.
290 ///Returns an active item on level \c l.
292 ///Returns an active item on level \c l.
294 ///Returns an active item on level \c l or \ref INVALID if there is no such
295 ///an item. (\c l must be from the range [0...\c max_level].
296 Item activeOn(int l) const
298 return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
301 ///Lifts the active item returned by \c activeOn() member function.
303 ///Lifts the active item returned by \c activeOn() member function
305 Item liftActiveOn(int level)
307 ++_level[*_last_active[level]];
308 swap(_last_active[level]--, --_first[level+1]);
309 if (level+1>_highest_active) ++_highest_active;
312 ///Lifts the active item returned by \c activeOn() member function.
314 ///Lifts the active item returned by \c activeOn() member function
315 ///to the given level.
316 void liftActiveOn(int level, int new_level)
318 const Item ai = *_last_active[level];
320 copy(--_first[level+1], _last_active[level]--);
321 for(int l=level+1;l<new_level;l++)
323 copy(_last_active[l],_first[l]);
324 copy(--_first[l+1], _last_active[l]--);
326 copy(ai,_first[new_level]);
327 _level[ai]=new_level;
328 if (new_level>_highest_active) _highest_active=new_level;
331 ///Lifts the active item returned by \c activeOn() member function.
333 ///Lifts the active item returned by \c activeOn() member function
335 void liftActiveToTop(int level)
337 const Item ai = *_last_active[level];
339 copy(--_first[level+1],_last_active[level]--);
340 for(int l=level+1;l<_max_level;l++)
342 copy(_last_active[l],_first[l]);
343 copy(--_first[l+1], _last_active[l]--);
345 copy(ai,_first[_max_level]);
346 --_last_active[_max_level];
347 _level[ai]=_max_level;
349 if (_highest_active==level) {
350 while(_highest_active>=0 &&
351 _last_active[_highest_active]<_first[_highest_active])
358 ///Lift an active item to a higher level.
360 ///Lift an active item to a higher level.
361 ///\param i The item to be lifted. It must be active.
362 ///\param new_level The new level of \c i. It must be strictly higher
363 ///than the current level.
365 void lift(Item i, int new_level)
367 const int lo = _level[i];
368 const Vit w = _where[i];
370 copy(_last_active[lo],w);
371 copy(--_first[lo+1],_last_active[lo]--);
372 for(int l=lo+1;l<new_level;l++)
374 copy(_last_active[l],_first[l]);
375 copy(--_first[l+1],_last_active[l]--);
377 copy(i,_first[new_level]);
379 if(new_level>_highest_active) _highest_active=new_level;
382 ///Mark the node as it did not reach the max level
384 ///Mark the node as it did not reach the max level. It sets the
385 ///level to the under the max level value. The node will be never
386 ///more activated because the push operation from the maximum
387 ///level is forbidden in the push-relabel algorithms. The node
388 ///should be lifted previously to the top level.
389 void markToBottom(Item i) {
390 _level[i] = _max_level - 1;
393 ///Lift all nodes on and above a level to the top (and deactivate them).
395 ///This function lifts all nodes on and above level \c l to \c
396 ///maxLevel(), and also deactivates them.
397 void liftToTop(int l)
399 const Vit f=_first[l];
400 const Vit tl=_first[_max_level];
401 for(Vit i=f;i!=tl;++i)
402 _level[*i]=_max_level;
403 for(int i=l;i<=_max_level;i++)
408 for(_highest_active=l-1;
409 _highest_active>=0 &&
410 _last_active[_highest_active]<_first[_highest_active];
420 ///\name Initialization
421 ///Using this function you can initialize the levels of the item.
423 ///This initializatios is started with calling \c initStart().
425 ///items should be listed levels by levels statring with the lowest one
426 ///(with level 0). This is done by using \c initAddItem()
427 ///and \c initNewLevel(). Finally \c initFinish() must be called.
428 ///The items not listed will be put on the highest level.
431 ///Start the initialization process.
436 _init_num=_items.begin();
437 _first[0]=_items.begin();
438 _last_active[0]=_items.begin()-1;
439 Vit n=_items.begin();
440 for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)
444 _level[i]=_max_level;
449 ///Add an item to the current level.
451 void initAddItem(Item i)
453 swap(_where[i],_init_num);
458 ///Start a new level.
460 ///Start a new level.
461 ///It shouldn't be used before the items on level 0 are listed.
465 _first[_init_lev]=_init_num;
466 _last_active[_init_lev]=_init_num-1;
469 ///Finalize the initialization process.
473 for(_init_lev++;_init_lev<=_max_level;_init_lev++)
475 _first[_init_lev]=_init_num;
476 _last_active[_init_lev]=_init_num-1;
478 _first[_max_level+1]=_items.begin()+_item_num;
479 _last_active[_max_level+1]=_items.begin()+_item_num-1;
480 _highest_active = -1;
487 ///Class for handling "labels" in push-relabel type algorithms.
489 ///A class for handling "labels" in push-relabel type algorithms.
492 ///Using this class you can assign "labels" (nonnegative integer numbers)
493 ///to the edges or nodes of a graph, manipulate and query them through
494 ///operations typically arising in "push-relabel" type algorithms.
496 ///Each item is either \em active or not, and you can also choose a
497 ///highest level active item.
501 ///\param Graph the underlying graph type
502 ///\param Item Type of the items the data is assigned to (Graph::Node,
503 ///Graph::Edge, Graph::UEdge)
504 template <class Graph, class Item>
505 class LinkedElevator {
513 typedef typename ItemSetTraits<Graph,Item>::
514 template Map<Item>::Type ItemMap;
515 typedef typename ItemSetTraits<Graph,Item>::
516 template Map<int>::Type IntMap;
517 typedef typename ItemSetTraits<Graph,Item>::
518 template Map<bool>::Type BoolMap;
523 std::vector<Item> _first, _last;
524 ItemMap _prev, _next;
530 ///Constructor with given maximum level.
532 ///Constructor with given maximum level.
534 ///\param g The underlying graph
535 ///\param max_level Set the range of the possible labels to
536 ///[0...\c max_level]
537 LinkedElevator(const Graph& graph, int max_level)
538 : _graph(graph), _max_level(max_level), _item_num(_max_level),
539 _first(_max_level + 1), _last(_max_level + 1),
540 _prev(graph), _next(graph),
541 _highest_active(-1), _level(graph), _active(graph) {}
547 ///\param g The underlying graph
548 ///The range of the possible labels is [0...\c max_level],
549 ///where \c max_level is equal to the number of labeled items in the graph.
550 LinkedElevator(const Graph& graph)
551 : _graph(graph), _max_level(countItems<Graph, Item>(graph)),
552 _item_num(_max_level),
553 _first(_max_level + 1), _last(_max_level + 1),
554 _prev(graph, INVALID), _next(graph, INVALID),
555 _highest_active(-1), _level(graph), _active(graph) {}
558 ///Activate item \c i.
560 ///Activate item \c i.
561 ///\pre Item \c i shouldn't be active before.
562 void activate(Item i) {
563 _active.set(i, true);
565 int level = _level[i];
566 if (level > _highest_active) {
567 _highest_active = level;
570 if (_prev[i] == INVALID || _active[_prev[i]]) return;
572 _next.set(_prev[i], _next[i]);
573 if (_next[i] != INVALID) {
574 _prev.set(_next[i], _prev[i]);
576 _last[level] = _prev[i];
579 _next.set(i, _first[level]);
580 _prev.set(_first[level], i);
581 _prev.set(i, INVALID);
586 ///Deactivate item \c i.
588 ///Deactivate item \c i.
589 ///\pre Item \c i must be active before.
590 void deactivate(Item i) {
591 _active.set(i, false);
592 int level = _level[i];
594 if (_next[i] == INVALID || !_active[_next[i]])
595 goto find_highest_level;
598 _prev.set(_next[i], _prev[i]);
599 if (_prev[i] != INVALID) {
600 _next.set(_prev[i], _next[i]);
602 _first[_level[i]] = _next[i];
605 _prev.set(i, _last[level]);
606 _next.set(_last[level], i);
607 _next.set(i, INVALID);
611 if (level == _highest_active) {
612 while (_highest_active >= 0 && activeFree(_highest_active))
617 ///Query whether item \c i is active
618 bool active(Item i) const { return _active[i]; }
620 ///Return the level of item \c i.
621 int operator[](Item i) const { return _level[i]; }
623 ///Return the number of items on level \c l.
624 int onLevel(int l) const {
627 while (n != INVALID) {
634 ///Return true if the level is empty.
635 bool emptyLevel(int l) const {
636 return _first[l] == INVALID;
639 ///Return the number of items above level \c l.
640 int aboveLevel(int l) const {
642 for (int level = l + 1; level < _max_level; ++level)
643 num += onLevel(level);
647 ///Return the number of active items on level \c l.
648 int activesOnLevel(int l) const {
651 while (n != INVALID && _active[n]) {
658 ///Return true if there is not active item on level \c l.
659 bool activeFree(int l) const {
660 return _first[l] == INVALID || !_active[_first[l]];
663 ///Return the maximum allowed level.
664 int maxLevel() const {
668 ///\name Highest Active Item
669 ///Functions for working with the highest level
674 ///Return a highest level active item.
676 ///Return a highest level active item.
678 ///\return the highest level active item or INVALID if there is no
680 Item highestActive() const {
681 return _highest_active >= 0 ? _first[_highest_active] : INVALID;
684 ///Return a highest active level.
686 ///Return a highest active level.
688 ///\return the level of the highest active item or -1 if there is
690 int highestActiveLevel() const {
691 return _highest_active;
694 ///Lift the highest active item by one.
696 ///Lift the item returned by highestActive() by one.
698 void liftHighestActive() {
699 Item i = _first[_highest_active];
700 if (_next[i] != INVALID) {
701 _prev.set(_next[i], INVALID);
702 _first[_highest_active] = _next[i];
704 _first[_highest_active] = INVALID;
705 _last[_highest_active] = INVALID;
707 _level.set(i, ++_highest_active);
708 if (_first[_highest_active] == INVALID) {
709 _first[_highest_active] = i;
710 _last[_highest_active] = i;
711 _prev.set(i, INVALID);
712 _next.set(i, INVALID);
714 _prev.set(_first[_highest_active], i);
715 _next.set(i, _first[_highest_active]);
716 _first[_highest_active] = i;
720 ///Lift the highest active item.
722 ///Lift the item returned by highestActive() to level \c new_level.
724 ///\warning \c new_level must be strictly higher
725 ///than the current level.
727 void liftHighestActive(int new_level) {
728 Item i = _first[_highest_active];
729 if (_next[i] != INVALID) {
730 _prev.set(_next[i], INVALID);
731 _first[_highest_active] = _next[i];
733 _first[_highest_active] = INVALID;
734 _last[_highest_active] = INVALID;
736 _level.set(i, _highest_active = new_level);
737 if (_first[_highest_active] == INVALID) {
738 _first[_highest_active] = _last[_highest_active] = i;
739 _prev.set(i, INVALID);
740 _next.set(i, INVALID);
742 _prev.set(_first[_highest_active], i);
743 _next.set(i, _first[_highest_active]);
744 _first[_highest_active] = i;
748 ///Lift the highest active to top.
750 ///Lift the item returned by highestActive() to the top level and
751 ///deactivates the node.
753 void liftHighestActiveToTop() {
754 Item i = _first[_highest_active];
755 _level.set(i, _max_level);
756 if (_next[i] != INVALID) {
757 _prev.set(_next[i], INVALID);
758 _first[_highest_active] = _next[i];
760 _first[_highest_active] = INVALID;
761 _last[_highest_active] = INVALID;
763 while (_highest_active >= 0 && activeFree(_highest_active))
769 ///\name Active Item on Certain Level
770 ///Functions for working with the active items.
774 ///Returns an active item on level \c l.
776 ///Returns an active item on level \c l.
778 ///Returns an active item on level \c l or \ref INVALID if there is no such
779 ///an item. (\c l must be from the range [0...\c max_level].
780 Item activeOn(int l) const
782 return _active[_first[l]] ? _first[l] : INVALID;
785 ///Lifts the active item returned by \c activeOn() member function.
787 ///Lifts the active item returned by \c activeOn() member function
789 Item liftActiveOn(int l)
792 if (_next[i] != INVALID) {
793 _prev.set(_next[i], INVALID);
794 _first[l] = _next[i];
800 if (_first[l] == INVALID) {
801 _first[l] = _last[l] = i;
802 _prev.set(i, INVALID);
803 _next.set(i, INVALID);
805 _prev.set(_first[l], i);
806 _next.set(i, _first[l]);
809 if (_highest_active < l) {
814 /// \brief Lifts the active item returned by \c activeOn() member function.
816 /// Lifts the active item returned by \c activeOn() member function
817 /// to the given level.
818 void liftActiveOn(int l, int new_level)
821 if (_next[i] != INVALID) {
822 _prev.set(_next[i], INVALID);
823 _first[l] = _next[i];
828 _level.set(i, l = new_level);
829 if (_first[l] == INVALID) {
830 _first[l] = _last[l] = i;
831 _prev.set(i, INVALID);
832 _next.set(i, INVALID);
834 _prev.set(_first[l], i);
835 _next.set(i, _first[l]);
838 if (_highest_active < l) {
843 ///Lifts the active item returned by \c activeOn() member function.
845 ///Lifts the active item returned by \c activeOn() member function
847 void liftActiveToTop(int l)
850 if (_next[i] != INVALID) {
851 _prev.set(_next[i], INVALID);
852 _first[l] = _next[i];
857 _level.set(i, _max_level);
858 if (l == _highest_active) {
859 while (_highest_active >= 0 && activeFree(_highest_active))
866 /// \brief Lift an active item to a higher level.
868 /// Lift an active item to a higher level.
869 /// \param i The item to be lifted. It must be active.
870 /// \param new_level The new level of \c i. It must be strictly higher
871 /// than the current level.
873 void lift(Item i, int new_level) {
874 if (_next[i] != INVALID) {
875 _prev.set(_next[i], _prev[i]);
877 _last[new_level] = _prev[i];
879 if (_prev[i] != INVALID) {
880 _next.set(_prev[i], _next[i]);
882 _first[new_level] = _next[i];
884 _level.set(i, new_level);
885 if (_first[new_level] == INVALID) {
886 _first[new_level] = _last[new_level] = i;
887 _prev.set(i, INVALID);
888 _next.set(i, INVALID);
890 _prev.set(_first[new_level], i);
891 _next.set(i, _first[new_level]);
892 _first[new_level] = i;
894 if (_highest_active < new_level) {
895 _highest_active = new_level;
899 ///Mark the node as it did not reach the max level
901 ///Mark the node as it did not reach the max level. It sets the
902 ///level to the under the max level value. The node will be never
903 ///more activated because the push operation from the maximum
904 ///level is forbidden in the push-relabel algorithms. The node
905 ///should be lifted previously to the top level.
906 void markToBottom(Item i) {
907 _level.set(i, _max_level - 1);
910 ///Lift all nodes on and above a level to the top (and deactivate them).
912 ///This function lifts all nodes on and above level \c l to \c
913 ///maxLevel(), and also deactivates them.
914 void liftToTop(int l) {
915 for (int i = l + 1; _first[i] != INVALID; ++i) {
917 while (n != INVALID) {
918 _level.set(n, _max_level);
924 if (_highest_active > l - 1) {
925 _highest_active = l - 1;
926 while (_highest_active >= 0 && activeFree(_highest_active))
937 ///\name Initialization
938 ///Using this function you can initialize the levels of the item.
940 ///This initializatios is started with calling \c initStart().
942 ///items should be listed levels by levels statring with the lowest one
943 ///(with level 0). This is done by using \c initAddItem()
944 ///and \c initNewLevel(). Finally \c initFinish() must be called.
945 ///The items not listed will be put on the highest level.
948 ///Start the initialization process.
952 for (int i = 0; i <= _max_level; ++i) {
953 _first[i] = _last[i] = INVALID;
956 for(typename ItemSetTraits<Graph,Item>::ItemIt i(_graph);
958 _level.set(i, _max_level);
959 _active.set(i, false);
963 ///Add an item to the current level.
965 void initAddItem(Item i) {
966 _level.set(i, _init_level);
967 if (_last[_init_level] == INVALID) {
968 _first[_init_level] = i;
969 _last[_init_level] = i;
970 _prev.set(i, INVALID);
971 _next.set(i, INVALID);
973 _prev.set(i, _last[_init_level]);
974 _next.set(i, INVALID);
975 _next.set(_last[_init_level], i);
976 _last[_init_level] = i;
980 ///Start a new level.
982 ///Start a new level.
983 ///It shouldn't be used before the items on level 0 are listed.
984 void initNewLevel() {
988 ///Finalize the initialization process.
991 _highest_active = -1;
999 } //END OF NAMESPACE LEMON