COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/elevator.h @ 2543:a0443c411220

Last change on this file since 2543:a0443c411220 was 2524:44675961f645, checked in by Balazs Dezso, 16 years ago

Bug fix resetting activeness of node at initialization

File size: 26.0 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
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>
31namespace 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
Note: See TracBrowser for help on using the repository browser.