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[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 ///Move an inactive item to the top but one level (in a dirty way).
385 ///This function moves an inactive item to the top but one level.
386 ///It makes the underlying datastructure corrupt, so use is only if
387 ///you really know what it is for.
388 ///\pre The item is on the top level.
389 void dirtyTopButOne(Item i) {
390 _level[i] = _max_level - 1;
393 ///Lift all items on and above a level to the top (and deactivate them).
395 ///This function lifts all items 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[0];
437 _first[0]=&_items[0];
438 _last_active[0]=&_items[0]-1;
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[0]+_item_num;
479 _last_active[_max_level+1]=&_items[0]+_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 item.
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 ///Move an inactive item to the top but one level (in a dirty way).
901 ///This function moves an inactive item to the top but one level.
902 ///It makes the underlying datastructure corrupt, so use is only if
903 ///you really know what it is for.
904 ///\pre The item is on the top level.
905 void dirtyTopButOne(Item i) {
906 _level.set(i, _max_level - 1);
909 ///Lift all items on and above a level to the top (and deactivate them).
911 ///This function lifts all items on and above level \c l to \c
912 ///maxLevel(), and also deactivates them.
913 void liftToTop(int l) {
914 for (int i = l + 1; _first[i] != INVALID; ++i) {
916 while (n != INVALID) {
917 _level.set(n, _max_level);
923 if (_highest_active > l - 1) {
924 _highest_active = l - 1;
925 while (_highest_active >= 0 && activeFree(_highest_active))
936 ///\name Initialization
937 ///Using this function you can initialize the levels of the item.
939 ///This initializatios is started with calling \c initStart().
941 ///items should be listed levels by levels statring with the lowest one
942 ///(with level 0). This is done by using \c initAddItem()
943 ///and \c initNewLevel(). Finally \c initFinish() must be called.
944 ///The items not listed will be put on the highest level.
947 ///Start the initialization process.
951 for (int i = 0; i <= _max_level; ++i) {
952 _first[i] = _last[i] = INVALID;
955 for(typename ItemSetTraits<Graph,Item>::ItemIt i(_graph);
957 _level.set(i, _max_level);
958 _active.set(i, false);
962 ///Add an item to the current level.
964 void initAddItem(Item i) {
965 _level.set(i, _init_level);
966 if (_last[_init_level] == INVALID) {
967 _first[_init_level] = i;
968 _last[_init_level] = i;
969 _prev.set(i, INVALID);
970 _next.set(i, INVALID);
972 _prev.set(i, _last[_init_level]);
973 _next.set(i, INVALID);
974 _next.set(_last[_init_level], i);
975 _last[_init_level] = i;
979 ///Start a new level.
981 ///Start a new level.
982 ///It shouldn't be used before the items on level 0 are listed.
983 void initNewLevel() {
987 ///Finalize the initialization process.
990 _highest_active = -1;
998 } //END OF NAMESPACE LEMON