COIN-OR::LEMON - Graph Library

Changeset 2512:371cf309fc3c in lemon-0.x for lemon


Ignore:
Timestamp:
11/14/07 18:44:42 (16 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3377
Message:

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

Location:
lemon
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • lemon/bits/traits.h

    r2391 r2512  
     1
    12/* -*- C++ -*-
    23 *
     
    5859    public:
    5960      typedef typename Graph::template NodeMap<_Value> Parent;
     61      typedef typename Graph::template NodeMap<_Value> Type;
    6062      typedef typename Parent::Value Value;
    6163
     
    9597    public:
    9698      typedef typename Graph::template EdgeMap<_Value> Parent;
     99      typedef typename Graph::template EdgeMap<_Value> Type;
    97100      typedef typename Parent::Value Value;
    98101
     
    131134    public:
    132135      typedef typename Graph::template UEdgeMap<_Value> Parent;
     136      typedef typename Graph::template UEdgeMap<_Value> Type;
    133137      typedef typename Parent::Value Value;
    134138
     
    167171    public:
    168172      typedef typename Graph::template ANodeMap<_Value> Parent;
     173      typedef typename Graph::template ANodeMap<_Value> Type;
    169174      typedef typename Parent::Value Value;
    170175
     
    203208    public:
    204209      typedef typename Graph::template BNodeMap<_Value> Parent;
     210      typedef typename Graph::template BNodeMap<_Value> Type;
    205211      typedef typename Parent::Value Value;
    206212
  • lemon/circulation.h

    r2450 r2512  
    254254        if(!_tol.positive(exc)) _levels.deactivate(act);
    255255        else if(mlevel==_node_num) {
    256           _levels.liftHighestActiveTo(_node_num);
     256          _levels.liftHighestActiveToTop();
    257257#ifdef LEMON_CIRCULATION_DEBUG
    258258          std::cerr << "  Lift to level " << _node_num << std::endl;
     
    261261        }
    262262        else {
    263           _levels.liftHighestActiveTo(mlevel+1);
     263          _levels.liftHighestActive(mlevel+1);
    264264#ifdef LEMON_CIRCULATION_DEBUG
    265265          std::cerr << "  Lift to level " << mlevel+1 << std::endl;
  • lemon/elevator.h

    r2391 r2512  
    4343  ///highest level active item.
    4444  ///
     45  ///\sa LinkedElevator
     46  ///
    4547  ///\param Graph the underlying graph type
    4648  ///\param Item Type of the items the data is assigned to (Graph::Node,
     
    4951  class Elevator
    5052  {
    51   public:
     53  private:
     54
     55    typedef Item Key;
     56    typedef int Value;
     57
    5258    typedef typename std::vector<Item>::iterator Vit;
    53     typedef DefaultMap<Graph,Item,Vit> VitMap;
    54     typedef DefaultMap<Graph,Item,int> IntMap;
     59    typedef typename ItemSetTraits<Graph,Item>::template Map<Vit>::Type VitMap;
     60    typedef typename ItemSetTraits<Graph,Item>::template Map<int>::Type IntMap;
    5561
    5662    const Graph &_g;
     
    8793    }
    8894   
    89     void checkDs() const
    90     {
    91       for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)
    92         {
    93           Vit w=_where[i];
    94           int l=_level[i];
    95           check(*w==i,"GEBASZ: CORRUPT DS");
    96           check(_first[l]<=w,"GEBASZ: CORRUPT DS");
    97           check(_first[l+1]>w,"GEBASZ: CORRUPT DS");
    98         }
    99       for(int l=0;l<=_max_level;++l)
    100         {
    101           check(_first[l]<=_last_active[l]+1,"GEBASZ: CORRUPT DS");
    102           check(_last_active[l]<_first[l+1],"GEBASZ: CORRUPT DS");
    103           check(_first[l]<=_first[l+1],"GEBASZ: CORRUPT DS");
    104         }
    105       check(_highest_active<0 ||
    106             _first[_highest_active]<=_last_active[_highest_active],
    107             "GEBASZ: CORRUPT DS");
    108     }
    109 
    11095  public:
     96       
    11197    ///Constructor with given maximum level.
    11298
     
    145131    {
    146132    }
    147  
     133   
    148134    ///Activate item \c i.
    149135
     
    175161    int operator[](Item i) const { return _level[i]; }
    176162
    177     ///Returns an active item on level \c l.
    178 
    179     ///Returns an active item on level \c l.
    180     ///
    181     ///Returns an active item on level \c l or \ref INVALID if there is no such
    182     ///an item. (\c l must be from the range [0...\c max_level].
    183     Item operator[](int l) const
    184     {
    185       return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
    186     }
    187 
    188163    ///Return the number of items on level \c l.
    189164    int onLevel(int l) const
     
    191166      return _first[l+1]-_first[l];
    192167    }
     168    ///Return true if the level is empty.
     169    bool emptyLevel(int l) const
     170    {
     171      return _first[l+1]-_first[l]==0;
     172    }
    193173    ///Return the number of items above level \c l.
    194174    int aboveLevel(int l) const
     
    200180    {
    201181      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];
    202187    }
    203188    ///Return the maximum allowed level.
     
    253238    ///than the current level.
    254239    ///
    255     void liftHighestActiveTo(int new_level)
     240    void liftHighestActive(int new_level)
    256241    {
    257242      const Item li = *_last_active[_highest_active];
     
    267252      _highest_active=new_level;
    268253    }
    269    
     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
    270355    ///@}
    271356   
     
    277362    ///than the current level.
    278363    ///
    279     void liftTo(Item i, int new_level)
     364    void lift(Item i, int new_level)
    280365    {
    281366      const int lo = _level[i];
     
    293378      if(new_level>_highest_active) _highest_active=new_level;
    294379    }
    295 
    296 //     void liftToTop(int l)
    297 //     {
    298 //       const Vit f=_first[l];
    299 //       for(int i=l;i<=_max_level;i++)
    300 //      {
    301 //        _first[i]=f;
    302 //        _last_active[i]=f-1;
    303 //      }
    304 //       for(Vit i=f;i!=_items.end();++i)
    305 //      _level[*i]=_max_level;
    306 //       for(_highest_active=l-1;
    307 //        _highest_active>=0 &&
    308 //          _last_active[_highest_active]<_first[_highest_active];
    309 //        _highest_active--) ;
    310 //     }
    311380   
    312381    ///Lift all nodes on and above a level to the top (and deactivate them).
    313382
    314     ///This function lifts all nodes on and above level \c l to \c maxLevel(),
    315     ///and
    316     ///also deactivates them.
     383    ///This function lifts all nodes on and above level \c l to \c
     384    ///maxLevel(), and also deactivates them.
    317385    void liftToTop(int l)
    318386    {
     
    398466      _first[_max_level+1]=_items.begin()+_item_num;
    399467      _last_active[_max_level+1]=_items.begin()+_item_num-1;
     468      _highest_active = -1;
    400469    }
    401470
     
    404473  };
    405474
     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
    406973} //END OF NAMESPACE LEMON
    407974
  • lemon/pr_bipartite_matching.h

    r2466 r2512  
    180180        if(nlevel<_node_num) {
    181181          if(nlevel>=actlevel)
    182             _levels.liftHighestActiveTo(nlevel+1);
     182            _levels.liftHighestActive(nlevel+1);
    183183          bact=_g.bNode(_matching[_g.aNode(bedge)]);
    184184          if(--_cov[bact]<1) {
     
    191191        }
    192192        else {
    193           if(_node_num>actlevel)
    194             _levels.liftHighestActiveTo(_node_num);
    195           _levels.deactivate(act);
    196         }
    197 
    198         if(_levels.onLevel(actlevel)==0)
     193          _levels.liftHighestActiveToTop();
     194        }
     195
     196        if(_levels.emptyLevel(actlevel))
    199197          _levels.liftToTop(actlevel);
    200198      }
     
    247245        if(nlevel<_node_num) {
    248246          if(nlevel>=actlevel)
    249             _levels.liftHighestActiveTo(nlevel+1);
     247            _levels.liftHighestActive(nlevel+1);
    250248          bact=_g.bNode(_matching[_g.aNode(bedge)]);
    251249          if(--_cov[bact]<1) {
     
    258256        }
    259257        else {
    260           if(_node_num>actlevel)
    261             _levels.liftHighestActiveTo(_node_num);
    262           _levels.deactivate(act);
    263         }
    264 
    265         if(_levels.onLevel(actlevel)==0)
     258          _levels.liftHighestActiveToTop();
     259        }
     260
     261        if(_levels.emptyLevel(actlevel))
    266262          _empty_level=actlevel;
    267263          return false;
Note: See TracChangeset for help on using the changeset viewer.