COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/elevator.h @ 2512:371cf309fc3c

Last change on this file since 2512:371cf309fc3c was 2512:371cf309fc3c, checked in by Balazs Dezso, 12 years ago

Elevator: slight changes in elevator interface
LinkedElevator?: based on linked lists

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