Redesigned CapacityScaling algorithm with almost the same interface.
The new version does not use the ResidualGraphAdaptor for performance reasons.
Scaling can be enabled and disabled with a parameter of the run() function.
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.
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>
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;
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[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 ++_level[*_last_active[_highest_active]];
231 swap(_last_active[_highest_active]--,_last_active[_highest_active+1]);
232 --_first[++_highest_active];
235 ///Lift the highest active item.
237 ///Lift the item returned by highestActive() to level \c new_level.
239 ///\warning \c new_level must be strictly higher
240 ///than the current level.
242 void liftHighestActive(int new_level)
244 const Item li = *_last_active[_highest_active];
246 copy(--_first[_highest_active+1],_last_active[_highest_active]--);
247 for(int l=_highest_active+1;l<new_level;l++)
249 copy(--_first[l+1],_first[l]);
252 copy(li,_first[new_level]);
253 _level[li]=new_level;
254 _highest_active=new_level;
257 ///Lift the highest active item.
259 ///Lift the item returned by highestActive() to the top level and
262 ///\warning \c new_level must be strictly higher
263 ///than the current level.
265 void liftHighestActiveToTop()
267 const Item li = *_last_active[_highest_active];
269 copy(--_first[_highest_active+1],_last_active[_highest_active]--);
270 for(int l=_highest_active+1;l<_max_level;l++)
272 copy(--_first[l+1],_first[l]);
275 copy(li,_first[_max_level]);
276 --_last_active[_max_level];
277 _level[li]=_max_level;
279 while(_highest_active>=0 &&
280 _last_active[_highest_active]<_first[_highest_active])
286 ///\name Active Item on Certain Level
287 ///Functions for working with the active items.
291 ///Returns an active item on level \c l.
293 ///Returns an active item on level \c l.
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
299 return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
302 ///Lifts the active item returned by \c activeOn() member function.
304 ///Lifts the active item returned by \c activeOn() member function
306 Item liftActiveOn(int level)
308 ++_level[*_last_active[level]];
309 swap(_last_active[level]--, --_first[level+1]);
310 if (level+1>_highest_active) ++_highest_active;
313 ///Lifts the active item returned by \c activeOn() member function.
315 ///Lifts the active item returned by \c activeOn() member function
316 ///to the given level.
317 void liftActiveOn(int level, int new_level)
319 const Item ai = *_last_active[level];
321 copy(--_first[level+1], _last_active[level]--);
322 for(int l=level+1;l<new_level;l++)
324 copy(_last_active[l],_first[l]);
325 copy(--_first[l+1], _last_active[l]--);
327 copy(ai,_first[new_level]);
328 _level[ai]=new_level;
329 if (new_level>_highest_active) _highest_active=new_level;
332 ///Lifts the active item returned by \c activeOn() member function.
334 ///Lifts the active item returned by \c activeOn() member function
336 void liftActiveToTop(int level)
338 const Item ai = *_last_active[level];
340 copy(--_first[level+1],_last_active[level]--);
341 for(int l=level+1;l<_max_level;l++)
343 copy(_last_active[l],_first[l]);
344 copy(--_first[l+1], _last_active[l]--);
346 copy(ai,_first[_max_level]);
347 --_last_active[_max_level];
348 _level[ai]=_max_level;
350 if (_highest_active==level) {
351 while(_highest_active>=0 &&
352 _last_active[_highest_active]<_first[_highest_active])
359 ///Lift an active item to a higher level.
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.
366 void lift(Item i, int new_level)
368 const int lo = _level[i];
369 const Vit w = _where[i];
371 copy(_last_active[lo],w);
372 copy(--_first[lo+1],_last_active[lo]--);
373 for(int l=lo+1;l<new_level;l++)
375 copy(_last_active[l],_first[l]);
376 copy(--_first[l+1],_last_active[l]--);
378 copy(i,_first[new_level]);
380 if(new_level>_highest_active) _highest_active=new_level;
383 ///Mark the node as it did not reach the max level
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;
394 ///Lift all nodes on and above a level to the top (and deactivate them).
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)
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++)
409 for(_highest_active=l-1;
410 _highest_active>=0 &&
411 _last_active[_highest_active]<_first[_highest_active];
421 ///\name Initialization
422 ///Using this function you can initialize the levels of the item.
424 ///This initializatios is started with calling \c initStart().
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.
432 ///Start the initialization process.
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)
445 _level[i]=_max_level;
450 ///Add an item to the current level.
452 void initAddItem(Item i)
454 swap(_where[i],_init_num);
459 ///Start a new level.
461 ///Start a new level.
462 ///It shouldn't be used before the items on level 0 are listed.
466 _first[_init_lev]=_init_num;
467 _last_active[_init_lev]=_init_num-1;
470 ///Finalize the initialization process.
474 for(_init_lev++;_init_lev<=_max_level;_init_lev++)
476 _first[_init_lev]=_init_num;
477 _last_active[_init_lev]=_init_num-1;
479 _first[_max_level+1]=_items.begin()+_item_num;
480 _last_active[_max_level+1]=_items.begin()+_item_num-1;
481 _highest_active = -1;
488 ///Class for handling "labels" in push-relabel type algorithms.
490 ///A class for handling "labels" in push-relabel type algorithms.
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.
497 ///Each item is either \em active or not, and you can also choose a
498 ///highest level active item.
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 {
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;
524 std::vector<Item> _first, _last;
525 ItemMap _prev, _next;
531 ///Constructor with given maximum level.
533 ///Constructor with given maximum level.
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) {}
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) {}
559 ///Activate item \c i.
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);
566 int level = _level[i];
567 if (level > _highest_active) {
568 _highest_active = level;
571 if (_prev[i] == INVALID || _active[_prev[i]]) return;
573 _next.set(_prev[i], _next[i]);
574 if (_next[i] != INVALID) {
575 _prev.set(_next[i], _prev[i]);
577 _last[level] = _prev[i];
580 _next.set(i, _first[level]);
581 _prev.set(_first[level], i);
582 _prev.set(i, INVALID);
587 ///Deactivate item \c i.
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];
595 if (_next[i] == INVALID || !_active[_next[i]])
596 goto find_highest_level;
599 _prev.set(_next[i], _prev[i]);
600 if (_prev[i] != INVALID) {
601 _next.set(_prev[i], _next[i]);
603 _first[_level[i]] = _next[i];
606 _prev.set(i, _last[level]);
607 _next.set(_last[level], i);
608 _next.set(i, INVALID);
612 if (level == _highest_active) {
613 while (_highest_active >= 0 && activeFree(_highest_active))
618 ///Query whether item \c i is active
619 bool active(Item i) const { return _active[i]; }
621 ///Return the level of item \c i.
622 int operator[](Item i) const { return _level[i]; }
624 ///Return the number of items on level \c l.
625 int onLevel(int l) const {
628 while (n != INVALID) {
635 ///Return true if the level is empty.
636 bool emptyLevel(int l) const {
637 return _first[l] == INVALID;
640 ///Return the number of items above level \c l.
641 int aboveLevel(int l) const {
643 for (int level = l + 1; level < _max_level; ++level)
644 num += onLevel(level);
648 ///Return the number of active items on level \c l.
649 int activesOnLevel(int l) const {
652 while (n != INVALID && _active[n]) {
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]];
664 ///Return the maximum allowed level.
665 int maxLevel() const {
669 ///\name Highest Active Item
670 ///Functions for working with the highest level
675 ///Return a highest level active item.
677 ///Return a highest level active item.
679 ///\return the highest level active item or INVALID if there is no
681 Item highestActive() const {
682 return _highest_active >= 0 ? _first[_highest_active] : INVALID;
685 ///Return a highest active level.
687 ///Return a highest active level.
689 ///\return the level of the highest active item or -1 if there is
691 int highestActiveLevel() const {
692 return _highest_active;
695 ///Lift the highest active item by one.
697 ///Lift the item returned by highestActive() by one.
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];
705 _first[_highest_active] = INVALID;
706 _last[_highest_active] = INVALID;
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);
715 _prev.set(_first[_highest_active], i);
716 _next.set(i, _first[_highest_active]);
717 _first[_highest_active] = i;
721 ///Lift the highest active item.
723 ///Lift the item returned by highestActive() to level \c new_level.
725 ///\warning \c new_level must be strictly higher
726 ///than the current level.
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];
734 _first[_highest_active] = INVALID;
735 _last[_highest_active] = INVALID;
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);
743 _prev.set(_first[_highest_active], i);
744 _next.set(i, _first[_highest_active]);
745 _first[_highest_active] = i;
749 ///Lift the highest active to top.
751 ///Lift the item returned by highestActive() to the top level and
752 ///deactivates the node.
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];
761 _first[_highest_active] = INVALID;
762 _last[_highest_active] = INVALID;
764 while (_highest_active >= 0 && activeFree(_highest_active))
770 ///\name Active Item on Certain Level
771 ///Functions for working with the active items.
775 ///Returns an active item on level \c l.
777 ///Returns an active item on level \c l.
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
783 return _active[_first[l]] ? _first[l] : INVALID;
786 ///Lifts the active item returned by \c activeOn() member function.
788 ///Lifts the active item returned by \c activeOn() member function
790 Item liftActiveOn(int l)
793 if (_next[i] != INVALID) {
794 _prev.set(_next[i], INVALID);
795 _first[l] = _next[i];
801 if (_first[l] == INVALID) {
802 _first[l] = _last[l] = i;
803 _prev.set(i, INVALID);
804 _next.set(i, INVALID);
806 _prev.set(_first[l], i);
807 _next.set(i, _first[l]);
810 if (_highest_active < l) {
815 /// \brief Lifts the active item returned by \c activeOn() member function.
817 /// Lifts the active item returned by \c activeOn() member function
818 /// to the given level.
819 void liftActiveOn(int l, int new_level)
822 if (_next[i] != INVALID) {
823 _prev.set(_next[i], INVALID);
824 _first[l] = _next[i];
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);
835 _prev.set(_first[l], i);
836 _next.set(i, _first[l]);
839 if (_highest_active < l) {
844 ///Lifts the active item returned by \c activeOn() member function.
846 ///Lifts the active item returned by \c activeOn() member function
848 void liftActiveToTop(int l)
851 if (_next[i] != INVALID) {
852 _prev.set(_next[i], INVALID);
853 _first[l] = _next[i];
858 _level.set(i, _max_level);
859 if (l == _highest_active) {
860 while (_highest_active >= 0 && activeFree(_highest_active))
867 /// \brief Lift an active item to a higher level.
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.
874 void lift(Item i, int new_level) {
875 if (_next[i] != INVALID) {
876 _prev.set(_next[i], _prev[i]);
878 _last[new_level] = _prev[i];
880 if (_prev[i] != INVALID) {
881 _next.set(_prev[i], _next[i]);
883 _first[new_level] = _next[i];
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);
891 _prev.set(_first[new_level], i);
892 _next.set(i, _first[new_level]);
893 _first[new_level] = i;
895 if (_highest_active < new_level) {
896 _highest_active = new_level;
900 ///Mark the node as it did not reach the max level
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);
911 ///Lift all nodes on and above a level to the top (and deactivate them).
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) {
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