Circulation
Declared in lemon/circulation.h, in the group Maximum Flow Algorithms; the same class on the Doxygen site.
-
template< typename GR , typename LM , typename UM , typename SM , typename TR >
class Circulation Push-relabel algorithm for the network circulation problem.
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 \(G=(V,A)\) be a digraph, \(lower: A\rightarrow\mathbf{R}\) \(upper: A\rightarrow\mathbf{R}\cup\{\infty\}\) denote the lower and upper bounds on the arcs, for which \(lower(uv) \leq upper(uv)\) holds for all \(uv\in A\), and \(sup: V\rightarrow\mathbf{R}\) denotes the signed supply values of the nodes. If \(sup(u)>0\), then \(u\) is a supply node with \(sup(u)\) supply, if \(sup(u)<0\), then \(u\) is a demand node with \(-sup(u)\) demand. A feasible circulation is an \(f: A\rightarrow\mathbf{R}\) solution of the following problem.
\[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq sup(u) \quad \forall u\in V, \]\[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \]The sum of the supply values, i.e. \(\sum_{u\in V} sup(u)\) 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 \(\sum_{u\in V} sup(u)\) 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 proves that a feasible solution cannot exist.
Note that this algorithm also provides a feasible solution for the minimum cost flow problem.
- Template Parameters:
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 >.
TR – 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.
Execution Control
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.
-
inline void init()
Initializes the internal data structures.
Initializes the internal data structures and sets all flow values to the lower bound.
-
inline void greedyInit()
Initializes the internal data structures using a greedy approach.
Initializes the internal data structures using a greedy approach to construct the initial solution.
-
inline bool start()
Executes the algorithm.
This function executes the algorithm.
See also
See also
- Returns:
trueif a feasible circulation is found.
-
inline bool run()
Runs the algorithm.
This function runs the algorithm.
Note
Apart from the return value, c.run() is just a shortcut of the following code.
c.greedyInit(); c.start();
- Returns:
trueif a feasible circulation is found.
Query Functions
The results of the circulation algorithm can be obtained using these functions.
Either
run() or start() should be called before using them.-
inline const FlowMap & flowMap() const
Returns a const reference to the flow map.
Returns a const reference to the arc map storing the found flow.
-
inline bool barrier( const Node & node ) const
Returns
trueif the given node is in a barrier.Barrier is a set B of nodes for which
\[ \sum_{uv\in A: u\in B, v\notin B} upper(uv) - \sum_{uv\in A: u\notin B, v\in B} lower(uv) < \sum_{v\in B} sup(v) \]holds, i.e., whose supply exceeds what can leave it. The existence of a set with this property proves that a feasible circulation cannot exist.
This function returns
trueif the given node is in the found barrier. If a feasible circulation is found, the function gives backfalsefor every node.See also
See also
-
template< class BarrierMap >
inline void barrierMap( BarrierMap & bar ) const Gives back a barrier.
This function sets
barto the characteristic vector of the found barrier.barshould be a writable node map withbool(or convertible) value type.If a feasible circulation is found, the function gives back an empty set, so
bar[v] will befalsefor all nodesv.See also
See also
Note
This function calls barrier() for each node, so it runs in O(n) time.
Checker Functions
The feasibility of the results can be checked using these functions.
Either
run() or start() should be called before using them.-
inline bool checkFlow() const
Check if the found flow is a feasible circulation.
Check if the found flow is a feasible circulation,
-
inline bool checkBarrier() const
Check whether or not the last execution provides a barrier.
See also
See also
Public Functions
- inline Circulation( )
Constructor.
The constructor of the class.
- Parameters:
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 ~Circulation()
Destructor.
-
inline Circulation & lowerMap( const LowerMap & map )
Sets the lower bound map.
- Returns:
(*this)
-
inline Circulation & upperMap( const UpperMap & map )
Sets the upper bound (capacity) map.
- Returns:
(*this)
-
inline Circulation & supplyMap( const SupplyMap & map )
Sets the supply map.
- Returns:
(*this)
-
inline Circulation & flowMap( FlowMap & map )
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.
- Returns:
(*this)
-
inline Circulation & elevator( Elevator & elevator )
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.
- Returns:
(*this)
-
inline Circulation & tolerance( const Tolerance & tolerance )
Sets the tolerance used by the algorithm.
Sets the tolerance object used by the algorithm.
- Returns:
(*this)
Protected Functions
-
inline Circulation()
-
template< typename T >
struct SetFlowMap : public Circulation< Digraph , LowerMap , UpperMap , SupplyMap , SetFlowMapTraits< T > > Named parameter for setting FlowMap type.
Public Types
-
typedef Circulation< Digraph , LowerMap , UpperMap , SupplyMap , SetFlowMapTraits< T > > Create
-
typedef Circulation< Digraph , LowerMap , UpperMap , SupplyMap , SetFlowMapTraits< T > > Create
-
template< typename T >
struct SetElevator : public Circulation< Digraph , LowerMap , UpperMap , SupplyMap , SetElevatorTraits< T > > Named parameter for setting Elevator type. If this named parameter is used, then an external elevator object must be passed to the algorithm using the elevator() function before calling run() or init().
See also
Public Types
-
typedef Circulation< Digraph , LowerMap , UpperMap , SupplyMap , SetElevatorTraits< T > > Create
-
typedef Circulation< Digraph , LowerMap , UpperMap , SupplyMap , SetElevatorTraits< T > > Create
-
template< typename T >
struct SetStandardElevator : public Circulation< Digraph , LowerMap , UpperMap , SupplyMap , SetStandardElevatorTraits< T > > Named parameter for setting Elevator type with automatic allocation. The Elevator should have standard constructor interface to be able to automatically created by the algorithm (i.e. the digraph and the maximum level should be passed to it). However, an external elevator object could also be passed to the algorithm with the elevator() function before calling run() or init().
See also
Public Types
-
typedef Circulation< Digraph , LowerMap , UpperMap , SupplyMap , SetStandardElevatorTraits< T > > Create
-
typedef Circulation< Digraph , LowerMap , UpperMap , SupplyMap , SetStandardElevatorTraits< T > > Create