COIN-OR::LEMON - Graph Library

Changeset 2348:5ef61c97bf1b in lemon-0.x


Ignore:
Timestamp:
01/22/07 11:22:14 (11 years ago)
Author:
alpar
Branch:
default
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3140
Message:
  • Some bugfixes
  • Better doc
  • liftToTop(), liftTo() added
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/elevator.h

    r2347 r2348  
    8787    } 
    8888     
    89     void checkDs()  
     89    void checkDs() const 
    9090    { 
    9191      for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i) 
     
    9696          check(_first[l]<=w,"GEBASZ: CORRUPT DS"); 
    9797          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"); 
    98104        } 
    99105      check(_highest_active<0 || 
     
    152158    { 
    153159      swap(_where[i],_last_active[_level[i]]--); 
    154       _last_active[_level[i]]--; 
    155160      while(_highest_active>=0 && 
    156161            _last_active[_highest_active]<_first[_highest_active]) 
     
    176181 
    177182    ///Return the number of items on level \c l. 
    178     int &onLevel(int l) 
     183    int onLevel(int l) const 
    179184    { 
    180185      return _first[l+1]-_first[l]; 
    181186    } 
     187    ///Return the number of items above level \c l. 
     188    int aboveLevel(int l) const 
     189    { 
     190      return _first[_max_level+1]-_first[l+1]; 
     191    } 
    182192    ///Return the number of active items on level \c l. 
    183     int &activesOnLevel(int l) 
     193    int activesOnLevel(int l) const 
    184194    { 
    185195      return _last_active[l]-_first[l]+1; 
     
    234244    ///Lift the item returned by highestActive() to level \c new_level. 
    235245    /// 
     246    ///\warning \c new_level must be strictly higher 
     247    ///than the current level. 
    236248    /// 
    237249    void liftHighestActiveTo(int new_level)  
     
    247259      copy(li,_first[new_level]); 
    248260      _level[li]=new_level; 
    249           _highest_active=new_level; 
     261      _highest_active=new_level; 
    250262    } 
    251263     
    252264    ///@} 
     265     
     266    ///Lift an active item to a higher level. 
     267 
     268    ///Lift an active item to a higher level. 
     269    ///\params i The item to be lifted. It must be active. 
     270    ///\params new_level The new level of \c i. It must be strictly higher 
     271    ///than the current level. 
     272    /// 
     273    void liftTo(Item i, int new_level)  
     274    { 
     275      const int lo = _level[i]; 
     276      const Vit w = _where[i]; 
     277 
     278      copy(_last_active[lo],w); 
     279      copy(--_first[lo+1],_last_active[lo]--); 
     280      for(int l=lo+1;l<new_level;l++) 
     281        { 
     282          copy(_last_active[l],_first[l]); 
     283          copy(--_first[l+1],_last_active[l]--); 
     284        } 
     285      copy(i,_first[new_level]); 
     286      _level[i]=new_level; 
     287      if(new_level>_highest_active) _highest_active=new_level; 
     288    } 
     289 
     290//     void liftToTop(int l)  
     291//     { 
     292//       const Vit f=_first[l]; 
     293//       for(int i=l;i<=_max_level;i++) 
     294//      { 
     295//        _first[i]=f; 
     296//        _last_active[i]=f-1; 
     297//      } 
     298//       for(Vit i=f;i!=_items.end();++i) 
     299//      _level[*i]=_max_level; 
     300//       for(_highest_active=l-1; 
     301//        _highest_active>=0 && 
     302//          _last_active[_highest_active]<_first[_highest_active]; 
     303//        _highest_active--) ; 
     304//     } 
     305     
     306    ///Lift all nodes on and above a level to the top (and deactivate them). 
     307 
     308    ///This function lifts all nodes on and above level \c l to \c maxLevel(), 
     309    ///and 
     310    ///also deactivates them. 
     311    void liftToTop(int l)  
     312    { 
     313      const Vit f=_first[l]; 
     314      const Vit tl=_first[_max_level]; 
     315      for(Vit i=f;i!=tl;++i) 
     316        _level[*i]=_max_level; 
     317      for(int i=l;i<=_max_level;i++) 
     318        { 
     319          _first[i]=f; 
     320          _last_active[i]=f-1; 
     321        } 
     322      for(_highest_active=l-1; 
     323          _highest_active>=0 && 
     324            _last_active[_highest_active]<_first[_highest_active]; 
     325          _highest_active--) ; 
     326    } 
    253327     
    254328  private: 
     
    266340    ///(with level 0). This is done by using \c initAddItem() 
    267341    ///and \c initNewLevel(). Finally \c initFinish() must be called. 
    268     ///The items not listes will be put on the highest level. 
     342    ///The items not listed will be put on the highest level. 
    269343    ///@{ 
    270344 
    271     ///Starts the initialization process. 
     345    ///Start the initialization process. 
    272346 
    273347    void initStart()  
     
    307381    } 
    308382 
    309     ///Finalizes the initialization process. 
     383    ///Finalize the initialization process. 
    310384 
    311385    void initFinish() 
Note: See TracChangeset for help on using the changeset viewer.