LinkedElevator

Declared in lemon/elevator.h, in the group Auxiliary Data Structures; the same class on the Doxygen site.

template< class GR , class Item >
class LinkedElevator

Class for handling “labels” in push-relabel type algorithms.

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

Template Parameters:
  • GR – Type of the underlying graph.

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

Highest Active Item

Functions for working with the highest level active item.

inline Item highestActive() const

Return a highest level active item.

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

inline int highestActiveLevel() const

Return the highest active level.

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

inline void liftHighestActive()

Lift the highest active item by one.

Lift the item returned by highestActive() by one.

inline void liftHighestActive( int new_level )

Lift the highest active item to the given level.

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

Warning

new_level must be strictly higher than the current level.

inline void liftHighestActiveToTop()

Lift the highest active item to the top level.

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

Active Item on Certain Level

Functions for working with the active items.

inline Item activeOn( int l ) const

Return an active item on level l.

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

inline Item liftActiveOn( int l )

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

Returns:

The lifted item.

inline void liftActiveOn( int l , int new_level )

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

inline void liftActiveToTop( int l )

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

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

Initialization

Using these functions you can initialize the levels of the items.

inline void initStart()

Start the initialization process.

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.

inline void initAddItem( Item i )

Add an item to the current level.

inline void initNewLevel()

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

inline void initFinish()

Finalize the initialization process.

Public Types

typedef Item Key
typedef int Value

Public Functions

inline LinkedElevator( const GR & graph , int max_level )

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

inline LinkedElevator( const GR & graph )

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.

inline void activate( Item i )

Activate item i.

Pre:

Item i shouldn’t be active before.

inline void deactivate( Item i )

Deactivate item i.

Pre:

Item i must be active before.

inline bool active( Item i ) const

Query whether item i is active.

inline int operator[]( Item i ) const

Return the level of item i.

inline int onLevel( int l ) const

Return the number of items on level l.

inline bool emptyLevel( int l ) const

Return true if the level is empty.

inline int aboveLevel( int l ) const

Return the number of items above level l.

inline int activesOnLevel( int l ) const

Return the number of active items on level l.

inline bool activeFree( int l ) const

Return true if there is no active item on level l.

inline int maxLevel() const

Return the maximum allowed level.

inline void lift( Item i , int new_level )

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.

inline void dirtyTopButOne( Item i )

Move an inactive item to the top but one level (in a dirty way).

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.

Pre:

The item is on the top level.

inline void liftToTop( int l )

Lift all items on and above the given level to the top level.

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