COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/elevator.h @ 2633:4f47c0f6be04

Last change on this file since 2633:4f47c0f6be04 was 2633:4f47c0f6be04, checked in by Alpar Juttner, 11 years ago

Remove a faulty include from elevator.h

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-2008
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
30namespace lemon {
31
32  ///Class for handling "labels" in push-relabel type algorithms.
33 
34  ///A class for handling "labels" in push-relabel type algorithms.
35  ///
36  ///\ingroup auxdat
37  ///Using this class you can assign "labels" (nonnegative integer numbers)
38  ///to the edges or nodes of a graph, manipulate and query them through
39  ///operations typically arising in "push-relabel" type algorithms.
40  ///
41  ///Each item is either \em active or not, and you can also choose a
42  ///highest level active item.
43  ///
44  ///\sa LinkedElevator
45  ///
46  ///\param Graph the underlying graph type
47  ///\param Item Type of the items the data is assigned to (Graph::Node,
48  ///Graph::Edge, Graph::UEdge)
49  template<class Graph, class Item>
50  class Elevator
51  {
52  public:
53
54    typedef Item Key;
55    typedef int Value;
56
57  private:
58
59    typedef typename std::vector<Item>::iterator Vit;
60    typedef typename ItemSetTraits<Graph,Item>::template Map<Vit>::Type VitMap;
61    typedef typename ItemSetTraits<Graph,Item>::template Map<int>::Type IntMap;
62
63    const Graph &_g;
64    int _max_level;
65    int _item_num;
66    VitMap _where;
67    IntMap _level;
68    std::vector<Item> _items;
69    std::vector<Vit> _first;
70    std::vector<Vit> _last_active;
71
72    int _highest_active;
73
74    void copy(Item i, Vit p)
75    {
76      _where[*p=i]=p;
77    }
78    void copy(Vit s, Vit p)
79    {
80      if(s!=p)
81        {
82          Item i=*s;
83          *p=i;
84          _where[i]=p;
85        }
86    }
87    void swap(Vit i, Vit j)
88    {
89      Item ti=*i;
90      Vit ct = _where[ti];
91      _where[ti]=_where[*i=*j];
92      _where[*j]=ct;
93      *j=ti;
94    }
95   
96  public:
97       
98    ///Constructor with given maximum level.
99
100    ///Constructor with given maximum level.
101    ///
102    ///\param g The underlying graph
103    ///\param max_level Set the range of the possible labels to
104    ///[0...\c max_level]
105    Elevator(const Graph &g,int max_level) :
106      _g(g),
107      _max_level(max_level),
108      _item_num(_max_level),
109      _where(g),
110      _level(g,0),
111      _items(_max_level),
112      _first(_max_level+2),
113      _last_active(_max_level+2),
114      _highest_active(-1) {}
115    ///Constructor.
116
117    ///Constructor.
118    ///
119    ///\param g The underlying graph
120    ///The range of the possible labels is [0...\c max_level],
121    ///where \c max_level is equal to the number of labeled items in the graph.
122    Elevator(const Graph &g) :
123      _g(g),
124      _max_level(countItems<Graph, Item>(g)),
125      _item_num(_max_level),
126      _where(g),
127      _level(g,0),
128      _items(_max_level),
129      _first(_max_level+2),
130      _last_active(_max_level+2),
131      _highest_active(-1)
132    {
133    }
134   
135    ///Activate item \c i.
136
137    ///Activate item \c i.
138    ///\pre Item \c i shouldn't be active before.
139    void activate(Item i)
140    {
141      const int l=_level[i];
142      swap(_where[i],++_last_active[l]);
143      if(l>_highest_active) _highest_active=l;
144    }
145 
146    ///Deactivate item \c i.
147
148    ///Deactivate item \c i.
149    ///\pre Item \c i must be active before.
150    void deactivate(Item i) 
151    {
152      swap(_where[i],_last_active[_level[i]]--);
153      while(_highest_active>=0 &&
154            _last_active[_highest_active]<_first[_highest_active])
155        _highest_active--;
156    }
157
158    ///Query whether item \c i is active
159    bool active(Item i) const { return _where[i]<=_last_active[_level[i]]; }
160   
161    ///Return the level of item \c i.
162    int operator[](Item i) const { return _level[i]; }
163
164    ///Return the number of items on level \c l.
165    int onLevel(int l) const
166    {
167      return _first[l+1]-_first[l];
168    }
169    ///Return true if the level is empty.
170    bool emptyLevel(int l) const
171    {
172      return _first[l+1]-_first[l]==0;
173    }
174    ///Return the number of items above level \c l.
175    int aboveLevel(int l) const
176    {
177      return _first[_max_level+1]-_first[l+1];
178    }
179    ///Return the number of active items on level \c l.
180    int activesOnLevel(int l) const
181    {
182      return _last_active[l]-_first[l]+1;
183    }
184    ///Return true if there is not active item on level \c l.
185    bool activeFree(int l) const
186    {
187      return _last_active[l]<_first[l];
188    }
189    ///Return the maximum allowed level.
190    int maxLevel() const
191    {
192      return _max_level;
193    }   
194
195    ///\name Highest Active Item
196    ///Functions for working with the highest level
197    ///active item.
198
199    ///@{
200
201    ///Return a highest level active item.
202 
203    ///Return a highest level active item.
204    ///
205    ///\return the highest level active item or INVALID if there is no active
206    ///item.
207    Item highestActive() const
208    {
209      return _highest_active>=0?*_last_active[_highest_active]:INVALID;
210    }
211
212    ///Return a highest active level.
213
214    ///Return a highest active level.
215    ///
216    ///\return the level of the highest active item or -1 if there is no active
217    ///item.
218    int highestActiveLevel() const
219    {
220      return _highest_active;
221    }
222
223    ///Lift the highest active item by one.
224
225    ///Lift the item returned by highestActive() by one.
226    ///
227    void liftHighestActive()
228    {
229      ++_level[*_last_active[_highest_active]];
230      swap(_last_active[_highest_active]--,_last_active[_highest_active+1]);
231      --_first[++_highest_active];
232    }
233
234    ///Lift the highest active item.
235
236    ///Lift the item returned by highestActive() to level \c new_level.
237    ///
238    ///\warning \c new_level must be strictly higher
239    ///than the current level.
240    ///
241    void liftHighestActive(int new_level)
242    {
243      const Item li = *_last_active[_highest_active];
244     
245      copy(--_first[_highest_active+1],_last_active[_highest_active]--);
246      for(int l=_highest_active+1;l<new_level;l++)
247        {
248          copy(--_first[l+1],_first[l]);
249          --_last_active[l];
250        }
251      copy(li,_first[new_level]);
252      _level[li]=new_level;
253      _highest_active=new_level;
254    }
255
256    ///Lift the highest active item.
257
258    ///Lift the item returned by highestActive() to the top level and
259    ///deactivates it.
260    ///
261    ///\warning \c new_level must be strictly higher
262    ///than the current level.
263    ///
264    void liftHighestActiveToTop()
265    {
266      const Item li = *_last_active[_highest_active];
267     
268      copy(--_first[_highest_active+1],_last_active[_highest_active]--);
269      for(int l=_highest_active+1;l<_max_level;l++)
270        {
271          copy(--_first[l+1],_first[l]);
272          --_last_active[l];
273        }
274      copy(li,_first[_max_level]);
275      --_last_active[_max_level];
276      _level[li]=_max_level;
277
278      while(_highest_active>=0 &&
279            _last_active[_highest_active]<_first[_highest_active])
280        _highest_active--;
281    }
282   
283    ///@}
284   
285    ///\name Active Item on Certain Level
286    ///Functions for working with the active items.
287
288    ///@{
289
290    ///Returns an active item on level \c l.
291   
292    ///Returns an active item on level \c l.
293    ///
294    ///Returns an active item on level \c l or \ref INVALID if there is no such
295    ///an item. (\c l must be from the range [0...\c max_level].
296    Item activeOn(int l) const
297    {
298      return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
299    }
300
301    ///Lifts the active item returned by \c activeOn() member function.
302   
303    ///Lifts the active item returned by \c activeOn() member function
304    ///by one.
305    Item liftActiveOn(int level)
306    {
307      ++_level[*_last_active[level]];
308      swap(_last_active[level]--, --_first[level+1]);
309      if (level+1>_highest_active) ++_highest_active;
310    }
311
312    ///Lifts the active item returned by \c activeOn() member function.
313   
314    ///Lifts the active item returned by \c activeOn() member function
315    ///to the given level.
316    void liftActiveOn(int level, int new_level)
317    {
318      const Item ai = *_last_active[level];
319     
320      copy(--_first[level+1], _last_active[level]--);
321      for(int l=level+1;l<new_level;l++)
322        {
323          copy(_last_active[l],_first[l]);
324          copy(--_first[l+1], _last_active[l]--);
325        }
326      copy(ai,_first[new_level]);
327      _level[ai]=new_level;
328      if (new_level>_highest_active) _highest_active=new_level;
329    }
330
331    ///Lifts the active item returned by \c activeOn() member function.
332   
333    ///Lifts the active item returned by \c activeOn() member function
334    ///to the top level.
335    void liftActiveToTop(int level)
336    {
337      const Item ai = *_last_active[level];
338     
339      copy(--_first[level+1],_last_active[level]--);
340      for(int l=level+1;l<_max_level;l++)
341        {
342          copy(_last_active[l],_first[l]);
343          copy(--_first[l+1], _last_active[l]--);
344        }
345      copy(ai,_first[_max_level]);
346      --_last_active[_max_level];
347      _level[ai]=_max_level;
348
349      if (_highest_active==level) {
350        while(_highest_active>=0 &&
351              _last_active[_highest_active]<_first[_highest_active])
352          _highest_active--;
353      }
354    }
355
356    ///@}
357   
358    ///Lift an active item to a higher level.
359
360    ///Lift an active item to a higher level.
361    ///\param i The item to be lifted. It must be active.
362    ///\param new_level The new level of \c i. It must be strictly higher
363    ///than the current level.
364    ///
365    void lift(Item i, int new_level)
366    {
367      const int lo = _level[i];
368      const Vit w = _where[i];
369
370      copy(_last_active[lo],w);
371      copy(--_first[lo+1],_last_active[lo]--);
372      for(int l=lo+1;l<new_level;l++)
373        {
374          copy(_last_active[l],_first[l]);
375          copy(--_first[l+1],_last_active[l]--);
376        }
377      copy(i,_first[new_level]);
378      _level[i]=new_level;
379      if(new_level>_highest_active) _highest_active=new_level;
380    }
381
382    ///Mark the node as it did not reach the max level
383   
384    ///Mark the node as it did not reach the max level. It sets the
385    ///level to the under the max level value. The node will be never
386    ///more activated because the push operation from the maximum
387    ///level is forbidden in the push-relabel algorithms. The node
388    ///should be lifted previously to the top level.
389    void markToBottom(Item i) {
390      _level[i] = _max_level - 1;
391    }
392   
393    ///Lift all nodes on and above a level to the top (and deactivate them).
394
395    ///This function lifts all nodes on and above level \c l to \c
396    ///maxLevel(), and also deactivates them.
397    void liftToTop(int l)
398    {
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++)
404        {
405          _first[i]=f;
406          _last_active[i]=f-1;
407        }
408      for(_highest_active=l-1;
409          _highest_active>=0 &&
410            _last_active[_highest_active]<_first[_highest_active];
411          _highest_active--) ;
412    }
413   
414  private:
415    int _init_lev;
416    Vit _init_num;
417
418  public:
419
420    ///\name Initialization
421    ///Using this function you can initialize the levels of the item.
422    ///\n
423    ///This initializatios is started with calling \c initStart().
424    ///Then the
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.
429    ///@{
430
431    ///Start the initialization process.
432
433    void initStart()
434    {
435      _init_lev=0;
436      _init_num=_items.begin();
437      _first[0]=_items.begin();
438      _last_active[0]=_items.begin()-1;
439      Vit n=_items.begin();
440      for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)
441        {
442          *n=i;
443          _where[i]=n;
444          _level[i]=_max_level;
445          ++n;
446        }
447    }
448
449    ///Add an item to the current level.
450
451    void initAddItem(Item i)
452    {
453     swap(_where[i],_init_num);
454      _level[i]=_init_lev;
455      ++_init_num;
456    }
457
458    ///Start a new level.
459
460    ///Start a new level.
461    ///It shouldn't be used before the items on level 0 are listed.
462    void initNewLevel()
463    {
464      _init_lev++;
465      _first[_init_lev]=_init_num;
466      _last_active[_init_lev]=_init_num-1;
467    }
468
469    ///Finalize the initialization process.
470
471    void initFinish()
472    {
473      for(_init_lev++;_init_lev<=_max_level;_init_lev++)
474        {
475          _first[_init_lev]=_init_num;
476          _last_active[_init_lev]=_init_num-1;
477        }
478      _first[_max_level+1]=_items.begin()+_item_num;
479      _last_active[_max_level+1]=_items.begin()+_item_num-1;
480      _highest_active = -1;
481    }
482
483    ///@}
484
485  };
486
487  ///Class for handling "labels" in push-relabel type algorithms.
488 
489  ///A class for handling "labels" in push-relabel type algorithms.
490  ///
491  ///\ingroup auxdat
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.
495  ///
496  ///Each item is either \em active or not, and you can also choose a
497  ///highest level active item.
498  ///
499  ///\sa Elevator
500  ///
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 {
506  public:
507
508    typedef Item Key;
509    typedef int Value;
510
511  private:
512
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;
519
520    const Graph &_graph;
521    int _max_level;
522    int _item_num;
523    std::vector<Item> _first, _last;
524    ItemMap _prev, _next;   
525    int _highest_active;
526    IntMap _level;
527    BoolMap _active;
528   
529  public:
530    ///Constructor with given maximum level.
531
532    ///Constructor with given maximum level.
533    ///
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) {}
542
543    ///Constructor.
544
545    ///Constructor.
546    ///
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) {}
556 
557
558    ///Activate item \c i.
559
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);
564
565      int level = _level[i];
566      if (level > _highest_active) {
567        _highest_active = level;
568      }
569
570      if (_prev[i] == INVALID || _active[_prev[i]]) return;         
571      //unlace
572      _next.set(_prev[i], _next[i]);
573      if (_next[i] != INVALID) {
574        _prev.set(_next[i], _prev[i]);
575      } else {
576        _last[level] = _prev[i];
577      }
578      //lace
579      _next.set(i, _first[level]);
580      _prev.set(_first[level], i);
581      _prev.set(i, INVALID);
582      _first[level] = i;
583
584    }
585 
586    ///Deactivate item \c i.
587
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];
593
594      if (_next[i] == INVALID || !_active[_next[i]])
595        goto find_highest_level;
596
597      //unlace
598      _prev.set(_next[i], _prev[i]);
599      if (_prev[i] != INVALID) {
600        _next.set(_prev[i], _next[i]);
601      } else {
602        _first[_level[i]] = _next[i];
603      }
604      //lace
605      _prev.set(i, _last[level]);
606      _next.set(_last[level], i);
607      _next.set(i, INVALID);
608      _last[level] = i;
609     
610    find_highest_level:
611      if (level == _highest_active) {
612        while (_highest_active >= 0 && activeFree(_highest_active))
613          --_highest_active;
614      }
615    }
616
617    ///Query whether item \c i is active
618    bool active(Item i) const { return _active[i]; }
619   
620    ///Return the level of item \c i.
621    int operator[](Item i) const { return _level[i]; }
622   
623    ///Return the number of items on level \c l.
624    int onLevel(int l) const {
625      int num = 0;
626      Item n = _first[l];
627      while (n != INVALID) {
628        ++num;
629        n = _next[n];
630      }
631      return num;
632    }
633
634    ///Return true if the level is empty.
635    bool emptyLevel(int l) const {
636      return _first[l] == INVALID;
637    }
638
639    ///Return the number of items above level \c l.
640    int aboveLevel(int l) const {
641      int num = 0;
642      for (int level = l + 1; level < _max_level; ++level)
643        num += onLevel(level);
644      return num;
645    }
646
647    ///Return the number of active items on level \c l.
648    int activesOnLevel(int l) const {
649      int num = 0;
650      Item n = _first[l];
651      while (n != INVALID && _active[n]) {
652        ++num;
653        n = _next[n];
654      }
655      return num;
656    }
657
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]];
661    }
662
663    ///Return the maximum allowed level.
664    int maxLevel() const {
665      return _max_level;
666    }   
667
668    ///\name Highest Active Item
669    ///Functions for working with the highest level
670    ///active item.
671
672    ///@{
673
674    ///Return a highest level active item.
675 
676    ///Return a highest level active item.
677    ///
678    ///\return the highest level active item or INVALID if there is no
679    ///active item.
680    Item highestActive() const {
681      return _highest_active >= 0 ? _first[_highest_active] : INVALID;
682    }
683
684    ///Return a highest active level.
685
686    ///Return a highest active level.
687    ///
688    ///\return the level of the highest active item or -1 if there is
689    ///no active item.
690    int highestActiveLevel() const {
691      return _highest_active;
692    }
693
694    ///Lift the highest active item by one.
695
696    ///Lift the item returned by highestActive() by one.
697    ///
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];
703      } else {
704        _first[_highest_active] = INVALID;
705        _last[_highest_active] = INVALID;
706      }
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);
713      } else {
714        _prev.set(_first[_highest_active], i);
715        _next.set(i, _first[_highest_active]);
716        _first[_highest_active] = i;
717      }
718    }
719
720    ///Lift the highest active item.
721
722    ///Lift the item returned by highestActive() to level \c new_level.
723    ///
724    ///\warning \c new_level must be strictly higher
725    ///than the current level.
726    ///
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];
732      } else {
733        _first[_highest_active] = INVALID;
734        _last[_highest_active] = INVALID;
735      }
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);
741      } else {
742        _prev.set(_first[_highest_active], i);
743        _next.set(i, _first[_highest_active]);
744        _first[_highest_active] = i;
745      }
746    }
747
748    ///Lift the highest active to top.
749
750    ///Lift the item returned by highestActive() to the top level and
751    ///deactivates the node.
752    ///
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];
759      } else {
760        _first[_highest_active] = INVALID;
761        _last[_highest_active] = INVALID;
762      }
763      while (_highest_active >= 0 && activeFree(_highest_active))
764        --_highest_active;
765    }
766   
767    ///@}
768
769    ///\name Active Item on Certain Level
770    ///Functions for working with the active items.
771
772    ///@{
773
774    ///Returns an active item on level \c l.
775   
776    ///Returns an active item on level \c l.
777    ///
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
781    {
782      return _active[_first[l]] ? _first[l] : INVALID;
783    }
784
785    ///Lifts the active item returned by \c activeOn() member function.
786   
787    ///Lifts the active item returned by \c activeOn() member function
788    ///by one.
789    Item liftActiveOn(int l)
790    {
791      Item i = _first[l];
792      if (_next[i] != INVALID) {
793        _prev.set(_next[i], INVALID);
794        _first[l] = _next[i];
795      } else {
796        _first[l] = INVALID;
797        _last[l] = INVALID;
798      }
799      _level.set(i, ++l);
800      if (_first[l] == INVALID) {
801        _first[l] = _last[l] = i;
802        _prev.set(i, INVALID);
803        _next.set(i, INVALID);
804      } else {
805        _prev.set(_first[l], i);
806        _next.set(i, _first[l]);
807        _first[l] = i;
808      }
809      if (_highest_active < l) {
810        _highest_active = l;
811      }
812    }
813
814    /// \brief Lifts the active item returned by \c activeOn() member function.
815    ///   
816    /// Lifts the active item returned by \c activeOn() member function
817    /// to the given level.
818    void liftActiveOn(int l, int new_level)
819    {
820      Item i = _first[l];
821      if (_next[i] != INVALID) {
822        _prev.set(_next[i], INVALID);
823        _first[l] = _next[i];
824      } else {
825        _first[l] = INVALID;
826        _last[l] = INVALID;
827      }
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);
833      } else {
834        _prev.set(_first[l], i);
835        _next.set(i, _first[l]);
836        _first[l] = i;
837      }
838      if (_highest_active < l) {
839        _highest_active = l;
840      }
841    }
842
843    ///Lifts the active item returned by \c activeOn() member function.
844   
845    ///Lifts the active item returned by \c activeOn() member function
846    ///to the top level.
847    void liftActiveToTop(int l)
848    {
849      Item i = _first[l];
850      if (_next[i] != INVALID) {
851        _prev.set(_next[i], INVALID);
852        _first[l] = _next[i];
853      } else {
854        _first[l] = INVALID;
855        _last[l] = INVALID;
856      }
857      _level.set(i, _max_level);
858      if (l == _highest_active) {
859        while (_highest_active >= 0 && activeFree(_highest_active))
860          --_highest_active;
861      }
862    }
863
864    ///@}
865   
866    /// \brief Lift an active item to a higher level.
867    ///
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.
872    ///
873    void lift(Item i, int new_level) {
874      if (_next[i] != INVALID) {
875        _prev.set(_next[i], _prev[i]);
876      } else {
877        _last[new_level] = _prev[i];
878      }
879      if (_prev[i] != INVALID) {
880        _next.set(_prev[i], _next[i]);
881      } else {
882        _first[new_level] = _next[i];
883      }
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);
889      } else {
890        _prev.set(_first[new_level], i);
891        _next.set(i, _first[new_level]);
892        _first[new_level] = i;
893      }
894      if (_highest_active < new_level) {
895        _highest_active = new_level;
896      }
897    }
898   
899    ///Mark the node as it did not reach the max level
900   
901    ///Mark the node as it did not reach the max level. It sets the
902    ///level to the under the max level value. The node will be never
903    ///more activated because the push operation from the maximum
904    ///level is forbidden in the push-relabel algorithms. The node
905    ///should be lifted previously to the top level.
906    void markToBottom(Item i) {
907      _level.set(i, _max_level - 1);
908    }
909
910    ///Lift all nodes on and above a level to the top (and deactivate them).
911
912    ///This function lifts all nodes on and above level \c l to \c
913    ///maxLevel(), and also deactivates them.
914    void liftToTop(int l)  {
915      for (int i = l + 1; _first[i] != INVALID; ++i) {
916        Item n = _first[i];
917        while (n != INVALID) {
918          _level.set(n, _max_level);
919          n = _next[n];
920        }
921        _first[i] = INVALID;
922        _last[i] = INVALID;
923      }
924      if (_highest_active > l - 1) {
925        _highest_active = l - 1;
926        while (_highest_active >= 0 && activeFree(_highest_active))
927          --_highest_active;
928      }
929    }
930   
931  private:
932
933    int _init_level;
934
935  public:
936
937    ///\name Initialization
938    ///Using this function you can initialize the levels of the item.
939    ///\n
940    ///This initializatios is started with calling \c initStart().
941    ///Then the
942    ///items should be listed levels by levels statring with the lowest one
943    ///(with level 0). This is done by using \c initAddItem()
944    ///and \c initNewLevel(). Finally \c initFinish() must be called.
945    ///The items not listed will be put on the highest level.
946    ///@{
947
948    ///Start the initialization process.
949
950    void initStart() {
951     
952      for (int i = 0; i <= _max_level; ++i) {
953        _first[i] = _last[i] = INVALID;
954      }
955      _init_level = 0;
956      for(typename ItemSetTraits<Graph,Item>::ItemIt i(_graph);
957          i != INVALID; ++i) {
958        _level.set(i, _max_level);
959        _active.set(i, false);
960      }
961    }
962
963    ///Add an item to the current level.
964
965    void initAddItem(Item i) {
966      _level.set(i, _init_level);
967      if (_last[_init_level] == INVALID) {
968        _first[_init_level] = i;
969        _last[_init_level] = i;
970        _prev.set(i, INVALID);
971        _next.set(i, INVALID);
972      } else {
973        _prev.set(i, _last[_init_level]);
974        _next.set(i, INVALID);
975        _next.set(_last[_init_level], i);
976        _last[_init_level] = i;
977      }
978    }
979
980    ///Start a new level.
981
982    ///Start a new level.
983    ///It shouldn't be used before the items on level 0 are listed.
984    void initNewLevel() {
985      ++_init_level;
986    }
987
988    ///Finalize the initialization process.
989
990    void initFinish() {
991      _highest_active = -1;
992    }
993
994    ///@}
995
996  };
997
998
999} //END OF NAMESPACE LEMON
1000
1001#endif
1002
Note: See TracBrowser for help on using the repository browser.