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
- Template Parameters:
GR – Type of the underlying graph.
Item – Type of the items the data is assigned to (
GR::Node,GR::ArcorGR::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_levelmust 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
lor INVALID if there is no such an item. (lmust 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) usinginitAddItem()andinitNewLevel(). FinallyinitFinish()must be called. The items not listed are put on the highest 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 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], wheremax_levelis equal to the number of labeled items in the graph.
-
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
lto the top level and deactivates them.