Loading...
Searching...
No Matches
Elevator< GR, Item > Class Template Reference
Data Structures » Auxiliary Data Structures

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