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>

List of all members.

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.

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines