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.
| Graph | the underlying graph type | |
| Item | Type of the items the data is assigned to (Graph::Node, Graph::Edge, Graph::UEdge) |
#include <lemon/elevator.h>
Public Member Functions | |
| LinkedElevator (const Graph &graph, int max_level) | |
| Constructor with given maximum level. | |
| LinkedElevator (const Graph &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 the level 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 not 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 | markToBottom (Item i) |
| Mark the node as it did not reach the max level. | |
| void | liftToTop (int l) |
| Lift all nodes on and above a level to the top (and deactivate them). | |
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 a highest active level. | |
| void | liftHighestActive () |
| Lift the highest active item by one. | |
| void | liftHighestActive (int new_level) |
| Lift the highest active item. | |
| void | liftHighestActiveToTop () |
| Lift the highest active to top. | |
Active Item on Certain Level | |
Functions for working with the active items. | |
| Item | activeOn (int l) const |
Returns an active item on level l. | |
| Item | liftActiveOn (int l) |
Lifts the active item returned by activeOn() member function. | |
| void | liftActiveOn (int l, int new_level) |
Lifts the active item returned by activeOn() member function. | |
| void | liftActiveToTop (int l) |
Lifts the active item returned by activeOn() member function. | |
Initialization | |
Using this function you can initialize the levels of the item. This initializatios is started with calling initStart(). Then the items should be listed levels by levels statring with the lowest one (with level 0). This is done by using initAddItem() and initNewLevel(). Finally initFinish() must be called. The items not listed will be 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. | |
| LinkedElevator | ( | const Graph & | graph, | |
| int | max_level | |||
| ) | [inline] |
Constructor with given maximum level.
| g | The underlying graph | |
| max_level | Set the range of the possible labels to [0...max_level] |
| LinkedElevator | ( | const Graph & | graph | ) | [inline] |
Constructor.
| g | The underlying graph The range of the possible labels is [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.
| int highestActiveLevel | ( | ) | const [inline] |
Return a highest active level.
| 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 deactivates the node.
| Item activeOn | ( | int | l | ) | const [inline] |
Returns an active item on level l.
Returns 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 | l | ) | [inline] |
Lifts the active item returned by activeOn() member function by one.
| void liftActiveOn | ( | int | l, | |
| int | new_level | |||
| ) | [inline] |
Lifts the active item returned by activeOn() member function to the given level.
| void liftActiveToTop | ( | int | l | ) | [inline] |
Lifts the active item returned by activeOn() member function to the top level.
| 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 markToBottom | ( | Item | i | ) | [inline] |
Mark the node as it did not reach the max level. It sets the level to the under the max level value. The node will be never more activated because the push operation from the maximum level is forbidden in the push-relabel algorithms. The node should be lifted previously to the top level.
| void liftToTop | ( | int | l | ) | [inline] |
This function lifts all nodes on and above level l to maxLevel(), and also deactivates them.
| void initNewLevel | ( | ) | [inline] |
Start a new level. It shouldn't be used before the items on level 0 are listed.
1.5.9