1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
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.
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.
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>
61 typedef typename ItemSetTraits<Graph,Item>::template Map<Vit>::Type VitMap;
62 typedef typename ItemSetTraits<Graph,Item>::template Map<int>::Type IntMap;
69 std::vector<Item> _items;
70 std::vector<Vit> _first;
71 std::vector<Vit> _last_active;
75 void copy(Item i, Vit p)
79 void copy(Vit s, Vit p)
88 void swap(Vit i, Vit j)
92 _where.set(ti,_where[*i=*j]);
99 ///Constructor with given maximum level.
101 ///Constructor with given maximum level.
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) :
108 _max_level(max_level),
109 _item_num(_max_level),
113 _first(_max_level+2),
114 _last_active(_max_level+2),
115 _highest_active(-1) {}
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) :
125 _max_level(countItems<Graph, Item>(g)),
126 _item_num(_max_level),
130 _first(_max_level+2),
131 _last_active(_max_level+2),
136 ///Activate item \c i.
138 ///Activate item \c i.
139 ///\pre Item \c i shouldn't be active before.
140 void activate(Item i)
142 const int l=_level[i];
143 swap(_where[i],++_last_active[l]);
144 if(l>_highest_active) _highest_active=l;
147 ///Deactivate item \c i.
149 ///Deactivate item \c i.
150 ///\pre Item \c i must be active before.
151 void deactivate(Item i)
153 swap(_where[i],_last_active[_level[i]]--);
154 while(_highest_active>=0 &&
155 _last_active[_highest_active]<_first[_highest_active])
159 ///Query whether item \c i is active
160 bool active(Item i) const { return _where[i]<=_last_active[_level[i]]; }
162 ///Return the level of item \c i.
163 int operator[](Item i) const { return _level[i]; }
165 ///Return the number of items on level \c l.
166 int onLevel(int l) const
168 return _first[l+1]-_first[l];
170 ///Return true if the level is empty.
171 bool emptyLevel(int l) const
173 return _first[l+1]-_first[l]==0;
175 ///Return the number of items above level \c l.
176 int aboveLevel(int l) const
178 return _first[_max_level+1]-_first[l+1];
180 ///Return the number of active items on level \c l.
181 int activesOnLevel(int l) const
183 return _last_active[l]-_first[l]+1;
185 ///Return true if there is not active item on level \c l.
186 bool activeFree(int l) const
188 return _last_active[l]<_first[l];
190 ///Return the maximum allowed level.
196 ///\name Highest Active Item
197 ///Functions for working with the highest level
202 ///Return a highest level active item.
204 ///Return a highest level active item.
206 ///\return the highest level active item or INVALID if there is no active
208 Item highestActive() const
210 return _highest_active>=0?*_last_active[_highest_active]:INVALID;
213 ///Return a highest active level.
215 ///Return a highest active level.
217 ///\return the level of the highest active item or -1 if there is no active
219 int highestActiveLevel() const
221 return _highest_active;
224 ///Lift the highest active item by one.
226 ///Lift the item returned by highestActive() by one.
228 void liftHighestActive()
230 Item it = *_last_active[_highest_active];
231 _level.set(it,_level[it]+1);
232 swap(_last_active[_highest_active]--,_last_active[_highest_active+1]);
233 --_first[++_highest_active];
236 ///Lift the highest active item.
238 ///Lift the item returned by highestActive() to level \c new_level.
240 ///\warning \c new_level must be strictly higher
241 ///than the current level.
243 void liftHighestActive(int new_level)
245 const Item li = *_last_active[_highest_active];
247 copy(--_first[_highest_active+1],_last_active[_highest_active]--);
248 for(int l=_highest_active+1;l<new_level;l++)
250 copy(--_first[l+1],_first[l]);
253 copy(li,_first[new_level]);
254 _level.set(li,new_level);
255 _highest_active=new_level;
258 ///Lift the highest active item.
260 ///Lift the item returned by highestActive() to the top level and
263 ///\warning \c new_level must be strictly higher
264 ///than the current level.
266 void liftHighestActiveToTop()
268 const Item li = *_last_active[_highest_active];
270 copy(--_first[_highest_active+1],_last_active[_highest_active]--);
271 for(int l=_highest_active+1;l<_max_level;l++)
273 copy(--_first[l+1],_first[l]);
276 copy(li,_first[_max_level]);
277 --_last_active[_max_level];
278 _level.set(li,_max_level);
280 while(_highest_active>=0 &&
281 _last_active[_highest_active]<_first[_highest_active])
287 ///\name Active Item on Certain Level
288 ///Functions for working with the active items.
292 ///Returns an active item on level \c l.
294 ///Returns an active item on level \c l.
296 ///Returns an active item on level \c l or \ref INVALID if there is no such
297 ///an item. (\c l must be from the range [0...\c max_level].
298 Item activeOn(int l) const
300 return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
303 ///Lifts the active item returned by \c activeOn() member function.
305 ///Lifts the active item returned by \c activeOn() member function
307 Item liftActiveOn(int level)
309 Item it =*_last_active[level];
310 _level.set(it,_level[it]+1);
311 swap(_last_active[level]--, --_first[level+1]);
312 if (level+1>_highest_active) ++_highest_active;
315 ///Lifts the active item returned by \c activeOn() member function.
317 ///Lifts the active item returned by \c activeOn() member function
318 ///to the given level.
319 void liftActiveOn(int level, int new_level)
321 const Item ai = *_last_active[level];
323 copy(--_first[level+1], _last_active[level]--);
324 for(int l=level+1;l<new_level;l++)
326 copy(_last_active[l],_first[l]);
327 copy(--_first[l+1], _last_active[l]--);
329 copy(ai,_first[new_level]);
330 _level.set(ai,new_level);
331 if (new_level>_highest_active) _highest_active=new_level;
334 ///Lifts the active item returned by \c activeOn() member function.
336 ///Lifts the active item returned by \c activeOn() member function
338 void liftActiveToTop(int level)
340 const Item ai = *_last_active[level];
342 copy(--_first[level+1],_last_active[level]--);
343 for(int l=level+1;l<_max_level;l++)
345 copy(_last_active[l],_first[l]);
346 copy(--_first[l+1], _last_active[l]--);
348 copy(ai,_first[_max_level]);
349 --_last_active[_max_level];
350 _level.set(ai,_max_level);
352 if (_highest_active==level) {
353 while(_highest_active>=0 &&
354 _last_active[_highest_active]<_first[_highest_active])
361 ///Lift an active item to a higher level.
363 ///Lift an active item to a higher level.
364 ///\param i The item to be lifted. It must be active.
365 ///\param new_level The new level of \c i. It must be strictly higher
366 ///than the current level.
368 void lift(Item i, int new_level)
370 const int lo = _level[i];
371 const Vit w = _where[i];
373 copy(_last_active[lo],w);
374 copy(--_first[lo+1],_last_active[lo]--);
375 for(int l=lo+1;l<new_level;l++)
377 copy(_last_active[l],_first[l]);
378 copy(--_first[l+1],_last_active[l]--);
380 copy(i,_first[new_level]);
381 _level.set(i,new_level);
382 if(new_level>_highest_active) _highest_active=new_level;
385 ///Move an inactive item to the top but one level (in a dirty way).
387 ///This function moves an inactive item to the top but one level.
388 ///It makes the underlying datastructure corrupt, so use is only if
389 ///you really know what it is for.
390 ///\pre The item is on the top level.
391 void dirtyTopButOne(Item i) {
392 _level.set(i,_max_level - 1);
395 ///Lift all items on and above a level to the top (and deactivate them).
397 ///This function lifts all items on and above level \c l to \c
398 ///maxLevel(), and also deactivates them.
399 void liftToTop(int l)
401 const Vit f=_first[l];
402 const Vit tl=_first[_max_level];
403 for(Vit i=f;i!=tl;++i)
404 _level.set(*i,_max_level);
405 for(int i=l;i<=_max_level;i++)
410 for(_highest_active=l-1;
411 _highest_active>=0 &&
412 _last_active[_highest_active]<_first[_highest_active];
422 ///\name Initialization
423 ///Using this function you can initialize the levels of the item.
425 ///This initializatios is started with calling \c initStart().
427 ///items should be listed levels by levels statring with the lowest one
428 ///(with level 0). This is done by using \c initAddItem()
429 ///and \c initNewLevel(). Finally \c initFinish() must be called.
430 ///The items not listed will be put on the highest level.
433 ///Start the initialization process.
438 _init_num=&_items[0];
439 _first[0]=&_items[0];
440 _last_active[0]=&_items[0]-1;
442 for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)
446 _level.set(i,_max_level);
451 ///Add an item to the current level.
453 void initAddItem(Item i)
455 swap(_where[i],_init_num);
456 _level.set(i,_init_lev);
460 ///Start a new level.
462 ///Start a new level.
463 ///It shouldn't be used before the items on level 0 are listed.
467 _first[_init_lev]=_init_num;
468 _last_active[_init_lev]=_init_num-1;
471 ///Finalize the initialization process.
475 for(_init_lev++;_init_lev<=_max_level;_init_lev++)
477 _first[_init_lev]=_init_num;
478 _last_active[_init_lev]=_init_num-1;
480 _first[_max_level+1]=&_items[0]+_item_num;
481 _last_active[_max_level+1]=&_items[0]+_item_num-1;
482 _highest_active = -1;
489 ///Class for handling "labels" in push-relabel type algorithms.
491 ///A class for handling "labels" in push-relabel type algorithms.
494 ///Using this class you can assign "labels" (nonnegative integer numbers)
495 ///to the edges or nodes of a graph, manipulate and query them through
496 ///operations typically arising in "push-relabel" type algorithms.
498 ///Each item is either \em active or not, and you can also choose a
499 ///highest level active item.
503 ///\param Graph the underlying graph type
504 ///\param Item Type of the items the data is assigned to (Graph::Node,
505 ///Graph::Edge, Graph::UEdge)
506 template <class Graph, class Item>
507 class LinkedElevator {
515 typedef typename ItemSetTraits<Graph,Item>::
516 template Map<Item>::Type ItemMap;
517 typedef typename ItemSetTraits<Graph,Item>::
518 template Map<int>::Type IntMap;
519 typedef typename ItemSetTraits<Graph,Item>::
520 template Map<bool>::Type BoolMap;
525 std::vector<Item> _first, _last;
526 ItemMap _prev, _next;
532 ///Constructor with given maximum level.
534 ///Constructor with given maximum level.
536 ///\param g The underlying graph
537 ///\param max_level Set the range of the possible labels to
538 ///[0...\c max_level]
539 LinkedElevator(const Graph& graph, int max_level)
540 : _graph(graph), _max_level(max_level), _item_num(_max_level),
541 _first(_max_level + 1), _last(_max_level + 1),
542 _prev(graph), _next(graph),
543 _highest_active(-1), _level(graph), _active(graph) {}
549 ///\param g The underlying graph
550 ///The range of the possible labels is [0...\c max_level],
551 ///where \c max_level is equal to the number of labeled items in the graph.
552 LinkedElevator(const Graph& graph)
553 : _graph(graph), _max_level(countItems<Graph, Item>(graph)),
554 _item_num(_max_level),
555 _first(_max_level + 1), _last(_max_level + 1),
556 _prev(graph, INVALID), _next(graph, INVALID),
557 _highest_active(-1), _level(graph), _active(graph) {}
560 ///Activate item \c i.
562 ///Activate item \c i.
563 ///\pre Item \c i shouldn't be active before.
564 void activate(Item i) {
565 _active.set(i, true);
567 int level = _level[i];
568 if (level > _highest_active) {
569 _highest_active = level;
572 if (_prev[i] == INVALID || _active[_prev[i]]) return;
574 _next.set(_prev[i], _next[i]);
575 if (_next[i] != INVALID) {
576 _prev.set(_next[i], _prev[i]);
578 _last[level] = _prev[i];
581 _next.set(i, _first[level]);
582 _prev.set(_first[level], i);
583 _prev.set(i, INVALID);
588 ///Deactivate item \c i.
590 ///Deactivate item \c i.
591 ///\pre Item \c i must be active before.
592 void deactivate(Item i) {
593 _active.set(i, false);
594 int level = _level[i];
596 if (_next[i] == INVALID || !_active[_next[i]])
597 goto find_highest_level;
600 _prev.set(_next[i], _prev[i]);
601 if (_prev[i] != INVALID) {
602 _next.set(_prev[i], _next[i]);
604 _first[_level[i]] = _next[i];
607 _prev.set(i, _last[level]);
608 _next.set(_last[level], i);
609 _next.set(i, INVALID);
613 if (level == _highest_active) {
614 while (_highest_active >= 0 && activeFree(_highest_active))
619 ///Query whether item \c i is active
620 bool active(Item i) const { return _active[i]; }
622 ///Return the level of item \c i.
623 int operator[](Item i) const { return _level[i]; }
625 ///Return the number of items on level \c l.
626 int onLevel(int l) const {
629 while (n != INVALID) {
636 ///Return true if the level is empty.
637 bool emptyLevel(int l) const {
638 return _first[l] == INVALID;
641 ///Return the number of items above level \c l.
642 int aboveLevel(int l) const {
644 for (int level = l + 1; level < _max_level; ++level)
645 num += onLevel(level);
649 ///Return the number of active items on level \c l.
650 int activesOnLevel(int l) const {
653 while (n != INVALID && _active[n]) {
660 ///Return true if there is not active item on level \c l.
661 bool activeFree(int l) const {
662 return _first[l] == INVALID || !_active[_first[l]];
665 ///Return the maximum allowed level.
666 int maxLevel() const {
670 ///\name Highest Active Item
671 ///Functions for working with the highest level
676 ///Return a highest level active item.
678 ///Return a highest level active item.
680 ///\return the highest level active item or INVALID if there is no
682 Item highestActive() const {
683 return _highest_active >= 0 ? _first[_highest_active] : INVALID;
686 ///Return a highest active level.
688 ///Return a highest active level.
690 ///\return the level of the highest active item or -1 if there is
692 int highestActiveLevel() const {
693 return _highest_active;
696 ///Lift the highest active item by one.
698 ///Lift the item returned by highestActive() by one.
700 void liftHighestActive() {
701 Item i = _first[_highest_active];
702 if (_next[i] != INVALID) {
703 _prev.set(_next[i], INVALID);
704 _first[_highest_active] = _next[i];
706 _first[_highest_active] = INVALID;
707 _last[_highest_active] = INVALID;
709 _level.set(i, ++_highest_active);
710 if (_first[_highest_active] == INVALID) {
711 _first[_highest_active] = i;
712 _last[_highest_active] = i;
713 _prev.set(i, INVALID);
714 _next.set(i, INVALID);
716 _prev.set(_first[_highest_active], i);
717 _next.set(i, _first[_highest_active]);
718 _first[_highest_active] = i;
722 ///Lift the highest active item.
724 ///Lift the item returned by highestActive() to level \c new_level.
726 ///\warning \c new_level must be strictly higher
727 ///than the current level.
729 void liftHighestActive(int new_level) {
730 Item i = _first[_highest_active];
731 if (_next[i] != INVALID) {
732 _prev.set(_next[i], INVALID);
733 _first[_highest_active] = _next[i];
735 _first[_highest_active] = INVALID;
736 _last[_highest_active] = INVALID;
738 _level.set(i, _highest_active = new_level);
739 if (_first[_highest_active] == INVALID) {
740 _first[_highest_active] = _last[_highest_active] = i;
741 _prev.set(i, INVALID);
742 _next.set(i, INVALID);
744 _prev.set(_first[_highest_active], i);
745 _next.set(i, _first[_highest_active]);
746 _first[_highest_active] = i;
750 ///Lift the highest active to top.
752 ///Lift the item returned by highestActive() to the top level and
753 ///deactivates the item.
755 void liftHighestActiveToTop() {
756 Item i = _first[_highest_active];
757 _level.set(i, _max_level);
758 if (_next[i] != INVALID) {
759 _prev.set(_next[i], INVALID);
760 _first[_highest_active] = _next[i];
762 _first[_highest_active] = INVALID;
763 _last[_highest_active] = INVALID;
765 while (_highest_active >= 0 && activeFree(_highest_active))
771 ///\name Active Item on Certain Level
772 ///Functions for working with the active items.
776 ///Returns an active item on level \c l.
778 ///Returns an active item on level \c l.
780 ///Returns an active item on level \c l or \ref INVALID if there is no such
781 ///an item. (\c l must be from the range [0...\c max_level].
782 Item activeOn(int l) const
784 return _active[_first[l]] ? _first[l] : INVALID;
787 ///Lifts the active item returned by \c activeOn() member function.
789 ///Lifts the active item returned by \c activeOn() member function
791 Item liftActiveOn(int l)
794 if (_next[i] != INVALID) {
795 _prev.set(_next[i], INVALID);
796 _first[l] = _next[i];
802 if (_first[l] == INVALID) {
803 _first[l] = _last[l] = i;
804 _prev.set(i, INVALID);
805 _next.set(i, INVALID);
807 _prev.set(_first[l], i);
808 _next.set(i, _first[l]);
811 if (_highest_active < l) {
816 /// \brief Lifts the active item returned by \c activeOn() member function.
818 /// Lifts the active item returned by \c activeOn() member function
819 /// to the given level.
820 void liftActiveOn(int l, int new_level)
823 if (_next[i] != INVALID) {
824 _prev.set(_next[i], INVALID);
825 _first[l] = _next[i];
830 _level.set(i, l = new_level);
831 if (_first[l] == INVALID) {
832 _first[l] = _last[l] = i;
833 _prev.set(i, INVALID);
834 _next.set(i, INVALID);
836 _prev.set(_first[l], i);
837 _next.set(i, _first[l]);
840 if (_highest_active < l) {
845 ///Lifts the active item returned by \c activeOn() member function.
847 ///Lifts the active item returned by \c activeOn() member function
849 void liftActiveToTop(int l)
852 if (_next[i] != INVALID) {
853 _prev.set(_next[i], INVALID);
854 _first[l] = _next[i];
859 _level.set(i, _max_level);
860 if (l == _highest_active) {
861 while (_highest_active >= 0 && activeFree(_highest_active))
868 /// \brief Lift an active item to a higher level.
870 /// Lift an active item to a higher level.
871 /// \param i The item to be lifted. It must be active.
872 /// \param new_level The new level of \c i. It must be strictly higher
873 /// than the current level.
875 void lift(Item i, int new_level) {
876 if (_next[i] != INVALID) {
877 _prev.set(_next[i], _prev[i]);
879 _last[new_level] = _prev[i];
881 if (_prev[i] != INVALID) {
882 _next.set(_prev[i], _next[i]);
884 _first[new_level] = _next[i];
886 _level.set(i, new_level);
887 if (_first[new_level] == INVALID) {
888 _first[new_level] = _last[new_level] = i;
889 _prev.set(i, INVALID);
890 _next.set(i, INVALID);
892 _prev.set(_first[new_level], i);
893 _next.set(i, _first[new_level]);
894 _first[new_level] = i;
896 if (_highest_active < new_level) {
897 _highest_active = new_level;
901 ///Move an inactive item to the top but one level (in a dirty way).
903 ///This function moves an inactive item to the top but one level.
904 ///It makes the underlying datastructure corrupt, so use is only if
905 ///you really know what it is for.
906 ///\pre The item is on the top level.
907 void dirtyTopButOne(Item i) {
908 _level.set(i, _max_level - 1);
911 ///Lift all items on and above a level to the top (and deactivate them).
913 ///This function lifts all items 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) {
918 while (n != INVALID) {
919 _level.set(n, _max_level);
925 if (_highest_active > l - 1) {
926 _highest_active = l - 1;
927 while (_highest_active >= 0 && activeFree(_highest_active))
938 ///\name Initialization
939 ///Using this function you can initialize the levels of the item.
941 ///This initializatios is started with calling \c initStart().
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.
949 ///Start the initialization process.
953 for (int i = 0; i <= _max_level; ++i) {
954 _first[i] = _last[i] = INVALID;
957 for(typename ItemSetTraits<Graph,Item>::ItemIt i(_graph);
959 _level.set(i, _max_level);
960 _active.set(i, false);
964 ///Add an item to the current level.
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);
974 _prev.set(i, _last[_init_level]);
975 _next.set(i, INVALID);
976 _next.set(_last[_init_level], i);
977 _last[_init_level] = i;
981 ///Start a new level.
983 ///Start a new level.
984 ///It shouldn't be used before the items on level 0 are listed.
985 void initNewLevel() {
989 ///Finalize the initialization process.
992 _highest_active = -1;
1000 } //END OF NAMESPACE LEMON