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.
| 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. 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. | |
| Elevator | ( | const GR & | graph, | |
| int | max_level | |||
| ) | [inline] |
Constructor with given maximum level.
| graph | The underlying graph. | |
| max_level | The maximum allowed level. Set the range of the possible labels to [0..max_level]. |
| Elevator | ( | const GR & | graph | ) | [inline] |
Constructor.
| 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. |
| void activate | ( | Item | i | ) | [inline] |
Activate item i.
i shouldn't be active before. | void deactivate | ( | Item | i | ) | [inline] |
Deactivate item i.
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.
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 | level | ) | [inline] |
Lift the active item returned by activeOn(level) by one.
| void liftActiveOn | ( | int | level, | |
| int | new_level | |||
| ) | [inline] |
Lift the active item returned by activeOn(level) to the given level.
| void liftActiveToTop | ( | int | level | ) | [inline] |
Lift the active item returned by activeOn(level) to the top level and deactivate it.
| void lift | ( | Item | i, | |
| int | new_level | |||
| ) | [inline] |
Lift an active item to a higher level.
| 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. |
| 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).
| 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.