All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
List of all members | Public Member Functions
LinkedElevator< GR, Item > Class Template Reference

Detailed Description

template<class GR, class Item>
class lemon::LinkedElevator< GR, Item >

A class for handling "labels" in push-relabel type algorithms.

Using this class you can assign "labels" (nonnegative integer numbers) to the edges or nodes of a graph, manipulate and query them through operations typically arising in "push-relabel" type algorithms.

Each item is either active or not, and you can also choose a highest level active item.

See Also
Elevator
Parameters
GRType of the underlying graph.
ItemType of the items the data is assigned to (GR::Node, GR::Arc or GR::Edge).

#include <lemon/elevator.h>

Public Member Functions

 LinkedElevator (const GR &graph, int max_level)
 Constructor with given maximum level.
 
 LinkedElevator (const GR &graph)
 Constructor.
 
void activate (Item i)
 Activate item i.
 
void deactivate (Item i)
 Deactivate item i.
 
bool active (Item i) const
 Query whether item i is active.
 
int operator[] (Item i) const
 Return the level of item i.
 
int onLevel (int l) const
 Return the number of items on level l.
 
bool emptyLevel (int l) const
 Return true if the level is empty.
 
int aboveLevel (int l) const
 Return the number of items above level l.
 
int activesOnLevel (int l) const
 Return the number of active items on level l.
 
bool activeFree (int l) const
 Return true if there is no active item on level l.
 
int maxLevel () const
 Return the maximum allowed level.
 
void lift (Item i, int new_level)
 Lift an active item to a higher level.
 
void dirtyTopButOne (Item i)
 Move an inactive item to the top but one level (in a dirty way).
 
void liftToTop (int l)
 Lift all items on and above the given level to the top level.
 
Highest Active Item

Functions for working with the highest level active item.

Item highestActive () const
 Return a highest level active item.
 
int highestActiveLevel () const
 Return the highest active level.
 
void liftHighestActive ()
 Lift the highest active item by one.
 
void liftHighestActive (int new_level)
 Lift the highest active item to the given level.
 
void liftHighestActiveToTop ()
 Lift the highest active item to the top level.
 
Active Item on Certain Level

Functions for working with the active items.

Item activeOn (int l) const
 Return an active item on level l.
 
Item liftActiveOn (int l)
 Lift the active item returned by activeOn(l) by one.
 
void liftActiveOn (int l, int new_level)
 Lift the active item returned by activeOn(l) to the given level.
 
void liftActiveToTop (int l)
 Lift the active item returned by activeOn(l) to the top level.
 
Initialization

Using these functions you can initialize the levels of the items.
The initialization must be started with calling initStart(). Then the items should be listed level by level starting with the lowest one (level 0) using initAddItem() and initNewLevel(). Finally initFinish() must be called. The items not listed are put on the highest level.

void initStart ()
 Start the initialization process.
 
void initAddItem (Item i)
 Add an item to the current level.
 
void initNewLevel ()
 Start a new level.
 
void initFinish ()
 Finalize the initialization process.
 

Constructor & Destructor Documentation

LinkedElevator ( const GR &  graph,
int  max_level 
)
inline

Constructor with given maximum level.

Parameters
graphThe underlying graph.
max_levelThe maximum allowed level. Set the range of the possible labels to [0..max_level].
LinkedElevator ( const GR &  graph)
inline

Constructor.

Parameters
graphThe underlying graph. Set the range of the possible labels to [0..max_level], where max_level is equal to the number of labeled items in the graph.

Member Function Documentation

void activate ( Item  i)
inline

Activate item i.

Precondition
Item i shouldn't be active before.
void deactivate ( Item  i)
inline

Deactivate item i.

Precondition
Item i must be active before.
Item highestActive ( ) const
inline

Return a highest level active item or INVALID if there is no active item.

int highestActiveLevel ( ) const
inline

Return the level of the highest active item or -1 if there is no active item.

void liftHighestActive ( )
inline

Lift the item returned by highestActive() by one.

void liftHighestActive ( int  new_level)
inline

Lift the item returned by highestActive() to level new_level.

Warning
new_level must be strictly higher than the current level.
void liftHighestActiveToTop ( )
inline

Lift the item returned by highestActive() to the top level and deactivate it.

Item activeOn ( int  l) const
inline

Return an active item on level l or INVALID if there is no such an item. (l must be from the range [0...max_level].

Item liftActiveOn ( int  l)
inline

Lift the active item returned by activeOn(l) by one.

void liftActiveOn ( int  l,
int  new_level 
)
inline

Lift the active item returned by activeOn(l) to the given level.

void liftActiveToTop ( int  l)
inline

Lift the active item returned by activeOn(l) to the top level and deactivate it.

void lift ( Item  i,
int  new_level 
)
inline

Lift an active item to a higher level.

Parameters
iThe item to be lifted. It must be active.
new_levelThe new level of i. It must be strictly higher than the current level.
void dirtyTopButOne ( Item  i)
inline

This function moves an inactive item from the top level to the top but one level (in a dirty way).

Warning
It makes the underlying datastructure corrupt, so use it only if you really know what it is for.
Precondition
The item is on the top level.
void liftToTop ( int  l)
inline

This function lifts all items on and above level l to the top level and deactivates them.

void initNewLevel ( )
inline

Start a new level. It shouldn't be used before the items on level 0 are listed.