This class implements a push-relabel algorithm for the networkcirculation 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.
The traits class that defines various types used by the algorithm. By default, it is CirculationDefaultTraits<GR, LM, UM, SM>. In most cases, this parameter should not be set directly, consider to use the named template parameters instead.
The simplest way to execute the algorithm is to call .\n If you need better control on the initial solution or the execution, you have to call one of the init() functions first, then the start() function.
Sets the flow map. If you don't use this function before calling run() or init(), an instance will be allocated automatically. The destructor deallocates this automatically allocated map, of course.
Sets the elevator used by algorithm. If you don't use this function before calling run() or init(), an instance will be allocated automatically. The destructor deallocates this automatically allocated elevator, of course.
template<typename GR , typename LM , typename UM , typename SM , typename TR >
bool barrier
(
const Node &
node
)
const
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.
Precondition
Either run() or init() must be called before using this function.