Elevator< GR, Item > Class Template Reference

Detailed Description

template<class GR, class Item>
class lemon::Elevator< 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

LinkedElevator

Parameters

GR	Type of the underlying graph.
Item	Type of the items the data is assigned to (GR::Node, GR::Arc or GR::Edge).

#include <lemon/elevator.h>

Public Member Functions
	Elevator (const GR &graph, int max_level)
	Constructor with given maximum level.
	Elevator (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 level l 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 level)
	Lift the active item returned by activeOn(level) by one.
void	liftActiveOn (int level, int new_level)
	Lift the active item returned by activeOn(level) to the given level.
void	liftActiveToTop (int level)
	Lift the active item returned by activeOn(level) to the top level.
Initialization
Using these functions you can initialize the levels of the items.
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

Elevator() [1/2]

template<class GR, class Item>

Elevator ( const GR & graph, int max_level )

inline

Constructor with given maximum level.

Parameters

graph	The underlying graph.
max_level	The maximum allowed level. Set the range of the possible labels to [0..max_level].

Elevator() [2/2]

template<class GR, class Item>

Elevator ( const GR & graph )

inline

Constructor.

Parameters

graph

The 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

activate()

template<class GR, class Item>

void activate ( Item i )

inline

Activate item i.

Precondition

Item i shouldn't be active before.

deactivate()

template<class GR, class Item>

void deactivate ( Item i )

inline

Deactivate item i.

Precondition

Item i must be active before.

highestActive()

template<class GR, class Item>

Item highestActive ( ) const

inline

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

highestActiveLevel()

template<class GR, class Item>

int highestActiveLevel ( ) const

inline

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

liftHighestActive() [1/2]

template<class GR, class Item>

void liftHighestActive ( )

inline

Lift the item returned by highestActive() by one.

liftHighestActive() [2/2]

template<class GR, class Item>

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.

liftHighestActiveToTop()

template<class GR, class Item>

void liftHighestActiveToTop ( )

inline

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

activeOn()

template<class GR, class Item>

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].

liftActiveOn() [1/2]

template<class GR, class Item>

Item liftActiveOn ( int level )

inline

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

liftActiveOn() [2/2]

template<class GR, class Item>

void liftActiveOn ( int level, int new_level )

inline

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

liftActiveToTop()

template<class GR, class Item>

void liftActiveToTop ( int level )

inline

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

lift()

template<class GR, class Item>

void lift ( Item i, int new_level )

inline

Lift an active item to a higher level.

Parameters

i	The item to be lifted. It must be active.
new_level	The new level of i. It must be strictly higher than the current level.

dirtyTopButOne()

template<class GR, class Item>

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.

liftToTop()

template<class GR, class Item>

void liftToTop ( int l )

inline

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

initStart()

template<class GR, class Item>

void initStart ( )

inline

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.

initNewLevel()

template<class GR, class Item>

void initNewLevel ( )

inline

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