This class implements a push-relabel algorithm for the network circulation problem. It is to find a feasible circulation when lower and upper bounds are given for the flow values on the arcs and lower bounds are given for the difference between the outgoing and incoming flow at the nodes.
The exact formulation of this problem is the following. Let be a digraph,
denote the lower and upper bounds on the arcs, for which
holds for all
, and
denotes the signed supply values of the nodes. If
, then
is a supply node with
supply, if
, then
is a demand node with
demand. A feasible circulation is an
solution of the following problem.
The sum of the supply values, i.e. must be zero or negative in order to have a feasible solution (since the sum of the expressions on the left-hand side of the inequalities is zero). It means that the total demand must be greater or equal to the total supply and all the supplies have to be carried out from the supply nodes, but there could be demands that are not satisfied. If
is zero, then all the supply/demand constraints have to be satisfied with equality, i.e. all demands have to be satisfied and all supplies have to be used.
If you need the opposite inequalities in the supply/demand constraints (i.e. the total demand is less than the total supply and all the demands have to be satisfied while there could be supplies that are not used), then you could easily transform the problem to the above form by reversing the direction of the arcs and taking the negative of the supply values (e.g. using ReverseDigraph and NegMap adaptors).
This algorithm either calculates a feasible circulation, or provides a barrier, which prooves that a feasible soultion cannot exist.
Note that this algorithm also provides a feasible solution for the minimum cost flow problem.
GR | The type of the digraph the algorithm runs on. |
LM | The type of the lower bound map. The default map type is GR::ArcMap<int>. |
UM | The type of the upper bound (capacity) map. The default map type is LM . |
SM | The type of the supply map. The default map type is GR::NodeMap<UM::Value>. |
#include <lemon/circulation.h>
Classes | |
struct | SetElevator |
Named parameter for setting Elevator type More... | |
struct | SetFlowMap |
Named parameter for setting FlowMap type More... | |
struct | SetStandardElevator |
Named parameter for setting Elevator type with automatic allocation More... | |
Public Types | |
typedef TR | Traits |
The traits class of the algorithm. | |
typedef Traits::Digraph | Digraph |
The type of the digraph the algorithm runs on. | |
typedef Traits::Value | Value |
The type of the flow and supply values. | |
typedef Traits::LowerMap | LowerMap |
The type of the lower bound map. | |
typedef Traits::UpperMap | UpperMap |
The type of the upper bound (capacity) map. | |
typedef Traits::SupplyMap | SupplyMap |
The type of the supply map. | |
typedef Traits::FlowMap | FlowMap |
The type of the flow map. | |
typedef Traits::Elevator | Elevator |
The type of the elevator. | |
typedef Traits::Tolerance | Tolerance |
The type of the tolerance. | |
Public Member Functions | |
Circulation (const Digraph &graph, const LowerMap &lower, const UpperMap &upper, const SupplyMap &supply) | |
Constructor. | |
~Circulation () | |
Destructor. | |
Circulation & | lowerMap (const LowerMap &map) |
Sets the lower bound map. | |
Circulation & | upperMap (const UpperMap &map) |
Sets the upper bound (capacity) map. | |
Circulation & | supplyMap (const SupplyMap &map) |
Sets the supply map. | |
Circulation & | flowMap (FlowMap &map) |
Sets the flow map. | |
Circulation & | elevator (Elevator &elevator) |
Sets the elevator used by algorithm. | |
const Elevator & | elevator () const |
Returns a const reference to the elevator. | |
Circulation & | tolerance (const Tolerance &tolerance) |
const Tolerance & | tolerance () const |
Execution Control | |
void | init () |
Initializes the internal data structures. | |
void | greedyInit () |
Initializes the internal data structures using a greedy approach. | |
bool | start () |
Executes the algorithm. | |
bool | run () |
Runs the algorithm. | |
Query Functions | |
Value | flow (const Arc &arc) const |
Returns the flow value on the given arc. | |
const FlowMap & | flowMap () const |
Returns a const reference to the flow map. | |
bool | barrier (const Node &node) const |
Returns true if the given node is in a barrier. | |
template<class BarrierMap > | |
void | barrierMap (BarrierMap &bar) const |
Gives back a barrier. | |
Checker Functions | |
bool | checkFlow () const |
Check if the found flow is a feasible circulation. | |
bool | checkBarrier () const |
Check whether or not the last execution provides a barrier. | |
|
inline |
The constructor of the class.
graph | The digraph the algorithm runs on. |
lower | The lower bounds for the flow values on the arcs. |
upper | The upper bounds (capacities) for the flow values on the arcs. |
supply | The signed supply values of the nodes. |
|
inline |
Sets the lower bound map.
(*this)
|
inline |
Sets the upper bound (capacity) map.
(*this)
|
inline |
Sets the supply map.
(*this)
|
inline |
|
inline |
|
inline |
|
inline |
Sets the tolerance used by algorithm.
|
inline |
Returns a const reference to the tolerance.
|
inline |
Initializes the internal data structures and sets all flow values to the lower bound.
|
inline |
Initializes the internal data structures using a greedy approach to construct the initial solution.
|
inline |
This function executes the algorithm.
true
if a feasible circulation is found.
|
inline |
This function runs the algorithm.
true
if a feasible circulation is found.
|
inline |
|
inline |
|
inline |
Barrier is a set B of nodes for which
holds. The existence of a set with this property prooves that a feasible circualtion cannot exist.
This function returns true
if the given node is in the found barrier. If a feasible circulation is found, the function gives back false
for every node.
|
inline |
This function sets bar
to the characteristic vector of the found barrier. bar
should be a writable node map with bool
(or convertible) value type.
If a feasible circulation is found, the function gives back an empty set, so bar
[v] will be false
for all nodes v
.
|
inline |
Check if the found flow is a feasible circulation,
|
inline |
Check whether or not the last execution provides a barrier.