abLEMON 1.9.0-101-gccb8629
A maintained fork of LEMON
Loading...
Searching...
No Matches
CycleCanceling< GR , V , C > Class Template Reference

Implementation of cycle-canceling algorithms for finding a minimum cost flow. More...

#include <lemon/cycle_canceling.h>

Public Types

enum  ProblemType { INFEASIBLE , OPTIMAL , UNBOUNDED }
 Problem type constants for the run() function. More...
enum  Method { SIMPLE_CYCLE_CANCELING , MINIMUM_MEAN_CYCLE_CANCELING , CANCEL_AND_TIGHTEN }
 Constants for selecting the used method. More...
typedef GR Digraph
 The type of the digraph.
typedef V Value
 The type of the flow amounts, capacity bounds and supply values.
typedef C Cost
 The type of the arc costs.
typedef lemon::Tolerance< Value > FlowTolerance
 The type of the tolerance on the flows [see flowTolerance()].
typedef lemon::Tolerance< Cost > CostTolerance
 The type of the tolerance on the reduced costs [see costTolerance()].

Public Member Functions

 CycleCanceling (const GR &graph)
 Constructor.
Parameters

The parameters of the algorithm can be specified using these functions.

template< typename LowerMap >
CycleCanceling & lowerMap (const LowerMap &map)
 Set the lower bounds on the arcs.
template< typename UpperMap >
CycleCanceling & upperMap (const UpperMap &map)
 Set the upper bounds (capacities) on the arcs.
template< typename CostMap >
CycleCanceling & costMap (const CostMap &map)
 Set the costs of the arcs.
template< typename SupplyMap >
CycleCanceling & supplyMap (const SupplyMap &map)
 Set the supply values of the nodes.
CycleCanceling & stSupply (const Node &s, const Node &t, Value k)
 Set single source and target nodes and a supply value.
Execution control

The algorithm can be executed using run().

ProblemType run (Method method=CANCEL_AND_TIGHTEN)
 Run the algorithm.
std::vector< Arc > unboundedCycle () const
 The cycle that proves the problem unbounded.
std::vector< Node > infeasibleCut () const
 The set of nodes that proves the problem infeasible.
std::vector< std::vector< Node > > infeasibleCuts (int k) const
 The k sets of nodes that prove the problem infeasible best.
std::vector< std::vector< Node > > disjointInfeasibleCuts () const
 Disjoint sets of nodes that prove the problem infeasible.
std::vector< std::vector< Arc > > unboundedCycles (int k) const
 Arc-disjoint cycles that prove the problem unbounded.
CycleCanceling & tolerances (Value flow, Cost cost)
 Sets the tolerances on the flows and on the reduced costs.
FlowTolerance flowTolerance () const
 The tolerance on the flows in use.
CostTolerance costTolerance () const
 The tolerance on the reduced costs in use.
CycleCanceling & resetParams ()
 Reset all the parameters that have been given before.
CycleCanceling & reset ()
 Reset the internal data structures and all the parameters that have been given before.
Query Functions

The results of the algorithm can be obtained using these functions.
The run() function must be called before using them.

template< typename Number >
Number totalCost () const
 Return the total cost of the found flow.
Value flow (const Arc &a) const
 Return the flow on the given arc.
template< typename FlowMap >
void flowMap (FlowMap &map) const
 Copy the flow values (the primal solution) into the given map.
Cost potential (const Node &n) const
 Return the potential (dual value) of the given node.
template< typename PotentialMap >
void potentialMap (PotentialMap &map) const
 Copy the potential values (the dual solution) into the given map.

Public Attributes

const Value INF
 Constant for infinite upper bounds (capacities).

Detailed Description

template< typename GR , typename V , typename C >
class lemon::CycleCanceling< GR , V , C >

CycleCanceling implements three different cycle-canceling algorithms for finding a minimum cost flow [1], [28], [17]. The most efficent one is the Cancel-and-Tighten algorithm, thus it is the default method. It runs in strongly polynomial time \(O( n^2 m^2 \log n )\), but in practice, it is typically orders of magnitude slower than the scaling algorithms and NetworkSimplex. (For more information, see the module page.)

Most of the parameters of the problem (except for the digraph) can be given using separate functions, and the algorithm can be executed using the run() function. If some parameters are not specified, then default values will be used.

Template Parameters
GRThe digraph type the algorithm runs on.
VThe number type used for flow amounts, capacity bounds and supply values in the algorithm. By default, it is int.
CThe number type used for costs and potentials in the algorithm. By default, it is the same as V.
Warning
Both V and C must be signed number types.
With integer types all input data (capacities, supply values, and costs) must be integer. With floating-point types they need not be: an excess, a deficit or a residual capacity within 10^6 units in the last place of the largest supply or finite bound is taken as zero, and a reduced cost within 10^6 units in the last place of the largest cost as nonnegative, so that rounding errors neither keep the algorithm sending round-off around for ever nor make a feasible problem infeasible; the phases of Cancel-and-Tighten go on until epsilon is within the latter, which the optimal flow then meets.
Note
For more information about the three available methods, see Method.

Member Enumeration Documentation

◆ ProblemType

template< typename GR , typename V , typename C >
enum ProblemType

Enum type containing the problem type constants that can be returned by the run() function of the algorithm.

Enumerator
INFEASIBLE 

The problem has no feasible solution (flow).

OPTIMAL 

The problem has optimal solution (i.e. it is feasible and bounded), and the algorithm has found optimal flow and node potentials (primal and dual solutions).

UNBOUNDED 

The problem is feasible and its objective function is unbounded, i.e. there is a directed cycle having negative total cost and infinite upper bound.

◆ Method

template< typename GR , typename V , typename C >
enum Method

Enum type containing constants for selecting the used method for the run() function.

CycleCanceling provides three different cycle-canceling methods. By default, Cancel-and-Tighten is used, which is by far the most efficient and the most robust. However, the other methods can be selected using the run() function with the proper parameter.

Enumerator
SIMPLE_CYCLE_CANCELING 

A simple cycle-canceling method, which uses the Bellman-Ford algorithm for detecting negative cycles in the residual network. The number of Bellman-Ford iterations is bounded by a successively increased limit.

MINIMUM_MEAN_CYCLE_CANCELING 

The "Minimum Mean Cycle-Canceling" algorithm, which is a well-known strongly polynomial method [17]. It improves along a minimum mean cycle in each iteration. Its running time complexity is \(O( n^2 m^3 \log n )\).

CANCEL_AND_TIGHTEN 

The "Cancel-and-Tighten" algorithm, which can be viewed as an improved version of the previous method [17]. It is faster both in theory and in practice, its running time complexity is \(O( n^2 m^2 \log n )\).

Constructor & Destructor Documentation

◆ CycleCanceling()

template< typename GR , typename V , typename C >
CycleCanceling ( const GR & graph)
inline

The constructor of the class.

Parameters
graphThe digraph the algorithm runs on.

Member Function Documentation

◆ lowerMap()

template< typename GR , typename V , typename C >
template< typename LowerMap >
CycleCanceling & lowerMap ( const LowerMap & map)
inline

This function sets the lower bounds on the arcs. If it is not used before calling run(), the lower bounds will be set to zero on all arcs.

Parameters
mapAn arc map storing the lower bounds. Its Value type must be convertible to the Value type of the algorithm.
Returns
( * this )

◆ upperMap()

template< typename GR , typename V , typename C >
template< typename UpperMap >
CycleCanceling & upperMap ( const UpperMap & map)
inline

This function sets the upper bounds (capacities) on the arcs. If it is not used before calling run(), the upper bounds will be set to INF on all arcs (i.e. the flow value will be unbounded from above).

Parameters
mapAn arc map storing the upper bounds. Its Value type must be convertible to the Value type of the algorithm.
Returns
( * this )

◆ costMap()

template< typename GR , typename V , typename C >
template< typename CostMap >
CycleCanceling & costMap ( const CostMap & map)
inline

This function sets the costs of the arcs. If it is not used before calling run(), the costs will be set to 1 on all arcs.

Parameters
mapAn arc map storing the costs. Its Value type must be convertible to the Cost type of the algorithm.
Returns
( * this )

◆ supplyMap()

template< typename GR , typename V , typename C >
template< typename SupplyMap >
CycleCanceling & supplyMap ( const SupplyMap & map)
inline

This function sets the supply values of the nodes. If neither this function nor stSupply() is used before calling run(), the supply of each node will be set to zero.

Parameters
mapA node map storing the supply values. Its Value type must be convertible to the Value type of the algorithm.
Returns
( * this )

◆ stSupply()

template< typename GR , typename V , typename C >
CycleCanceling & stSupply ( const Node & s,
const Node & t,
Value k )
inline

This function sets a single source node and a single target node and the required flow value. If neither this function nor supplyMap() is used before calling run(), the supply of each node will be set to zero.

Using this function has the same effect as using supplyMap() with a map in which k is assigned to s, -k is assigned to t and all other nodes have zero supply value.

Parameters
sThe source node.
tThe target node.
kThe required amount of flow from node s to node t (i.e. the supply of s and the demand of t).
Returns
( * this )

◆ run()

template< typename GR , typename V , typename C >
ProblemType run ( Method method = CANCEL_AND_TIGHTEN)
inline

This function runs the algorithm. The paramters can be specified using functions lowerMap(), upperMap(), costMap(), supplyMap(), stSupply(). For example,

cc.lowerMap( lower )
.upperMap( upper )
.costMap( cost )
.supplyMap( sup )
.run();
CycleCanceling( const GR & graph )
Constructor.
Definition cycle_canceling.h:290

This function can be called more than once. All the given parameters are kept for the next call, unless resetParams() or reset() is used, thus only the modified parameters have to be set again. If the underlying digraph was also modified after the construction of the class (or the last reset() call), then the reset() function must be called.

Parameters
methodThe cycle-canceling method that will be used. For more information, see Method.
Returns
INFEASIBLE if no feasible flow exists,
OPTIMAL if the problem has optimal solution (i.e. it is feasible and bounded), and the algorithm has found optimal flow and node potentials (primal and dual solutions),
UNBOUNDED if the problem is feasible and its objective function is unbounded, i.e. there is a directed cycle having negative total cost and infinite upper bound.
See also
ProblemType, Method
resetParams(), reset()

◆ unboundedCycle()

template< typename GR , typename V , typename C >
std::vector< Arc > unboundedCycle ( ) const
inline

This function gives a directed cycle of negative cost whose arcs have infinite upper bounds, in the direction of the flow, which proves the problem unbounded since the last run() found it feasible, as in unboundedCycle(). It is found by the algorithm of Bellman and Ford on the arcs of infinite upper bound, and it is empty if the last run() did not return UNBOUNDED.

◆ infeasibleCut()

template< typename GR , typename V , typename C >
std::vector< Node > infeasibleCut ( ) const
inline

This function gives a set \(N'\) of nodes whose supply exceeds what can leave it, i.e.,

\[ \sum_{u\in N'} sup(u) > \sum_{uv\in A, u\in N', v\notin N'} upper(uv) - \sum_{uv\in A, u\notin N', v\in N'} lower(uv) \]

with no arc of infinite upper bound out of \(N'\), which proves the problem infeasible since the last run() found it so. It is the set that the algorithm has at hand when it finds no feasible flow, at no further cost: the nodes above the level that the push-relabel algorithm of its starting flow leaves empty, together with the node it was lifting, from which no residual arc leaves; if that set does not prove it (in floating point, beyond the round-off), it is the set of largest violation, from a maximum flow, as in infeasibleCut(). It is empty if the last run() did not return INFEASIBLE, or if, in floating point, the inequality does not hold beyond the round-off.

◆ infeasibleCuts()

template< typename GR , typename V , typename C >
std::vector< std::vector< Node > > infeasibleCuts ( int k) const
inline

This function gives the k sets of nodes of largest violation of the inequality of infeasibleCut(), i.e., of the supply less what can leave the set, in the order of their violations, at most k and only those that prove the problem infeasible: Lawler's partition by the nodes that a set contains or not, with a maximum flow for each part (Hamacher, Picard and Queyranne, 1984), i.e., at most n maximum flows for each set. They are empty if the last run() did not return INFEASIBLE.

◆ disjointInfeasibleCuts()

template< typename GR , typename V , typename C >
std::vector< std::vector< Node > > disjointInfeasibleCuts ( ) const
inline

This function gives sets of nodes that prove the problem infeasible as infeasibleCut() does and that are pairwise disjoint, with no arc between two of them: the weakly connected components of the set of infeasibleCut() whose violation is positive, in the order of their violations, which sum to at least the violation of that set. They are empty if the last run() did not return INFEASIBLE.

◆ unboundedCycles()

template< typename GR , typename V , typename C >
std::vector< std::vector< Arc > > unboundedCycles ( int k) const
inline

This function gives at most k directed cycles of negative cost whose arcs have infinite upper bounds, pairwise arc-disjoint, in the order of their mean costs: the cycles of minimum mean cost of the strongly connected components of those arcs, which one run of Howard's algorithm gives together and are pairwise node-disjoint, the first being of minimum mean of all, then those of the arcs not yet taken, and so on while fewer than k are found. The cycle of minimum total cost would be NP-hard to find. They are empty if the last run() did not return UNBOUNDED.

◆ tolerances()

template< typename GR , typename V , typename C >
CycleCanceling & tolerances ( Value flow,
Cost cost )
inline

An excess, a deficit or a residual capacity within the tolerance on the flows is taken as zero, and a reduced cost above the opposite of the tolerance on the costs as nonnegative. A negative value, the default, leaves the tolerance to the algorithm: zero for an exact type, and otherwise 10^6 units in the last place of the largest supply or finite bound and of the largest cost, respectively. With floating-point data, a tolerance of zero lets rounding errors keep the algorithm going for ever, as in LEMON 1.3.1.

Returns
( * this )

◆ flowTolerance()

template< typename GR , typename V , typename C >
FlowTolerance flowTolerance ( ) const
inline

The one set by tolerances(), if any, and otherwise the one of the data [see tolerances()] that the last run() used (zero before the first one), as a Tolerance, whose epsilon is zero for an exact type.

◆ costTolerance()

template< typename GR , typename V , typename C >
CostTolerance costTolerance ( ) const
inline

As flowTolerance(), for the reduced costs.

◆ resetParams()

template< typename GR , typename V , typename C >
CycleCanceling & resetParams ( )
inline

This function resets all the paramaters that have been given before using functions lowerMap(), upperMap(), costMap(), supplyMap(), stSupply().

It is useful for multiple run() calls. Basically, all the given parameters are kept for the next run() call, unless resetParams() or reset() is used. If the underlying digraph was also modified after the construction of the class or the last reset() call, then the reset() function must be used, otherwise resetParams() is sufficient.

For example,

// First run
cc.lowerMap( lower )
.upperMap( upper )
.costMap( cost )
.supplyMap( sup )
.run();
// Run again with modified cost map (resetParams() is not called,
// so only the cost map have to be set again)
cost[ e ] += 100;
cc.costMap( cost ).run();
// Run again from scratch using resetParams()
// (the lower bounds will be set to zero on all arcs)
cc.resetParams();
cc.upperMap( capacity ).costMap( cost ).supplyMap( sup ).run();
Returns
( * this )
See also
reset(), run()

◆ reset()

template< typename GR , typename V , typename C >
CycleCanceling & reset ( )
inline

This function resets the internal data structures and all the paramaters that have been given before using functions lowerMap(), upperMap(), costMap(), supplyMap(), stSupply().

It is useful for multiple run() calls. Basically, all the given parameters are kept for the next run() call, unless resetParams() or reset() is used. If the underlying digraph was also modified after the construction of the class or the last reset() call, then the reset() function must be used, otherwise resetParams() is sufficient.

See resetParams() for examples.

Returns
( * this )
See also
resetParams(), run()

◆ totalCost()

template< typename GR , typename V , typename C >
template< typename Number >
Number totalCost ( ) const
inline

This function returns the total cost of the found flow. Its complexity is O(m).

Note
The return type of the function can be specified as a template parameter. For example,
cc.totalCost< double >();
It is useful if the total cost cannot be stored in the Cost type of the algorithm, which is the default return type of the function.
Precondition
run() must be called before using this function.

◆ flow()

template< typename GR , typename V , typename C >
Value flow ( const Arc & a) const
inline

This function returns the flow on the given arc.

Precondition
run() must be called before using this function.

◆ flowMap()

template< typename GR , typename V , typename C >
template< typename FlowMap >
void flowMap ( FlowMap & map) const
inline

This function copies the flow value on each arc into the given map. The Value type of the algorithm must be convertible to the Value type of the map.

Precondition
run() must be called before using this function.

◆ potential()

template< typename GR , typename V , typename C >
Cost potential ( const Node & n) const
inline

This function returns the potential (dual value) of the given node.

Precondition
run() must be called before using this function.

◆ potentialMap()

template< typename GR , typename V , typename C >
template< typename PotentialMap >
void potentialMap ( PotentialMap & map) const
inline

This function copies the potential (dual value) of each node into the given map. The Cost type of the algorithm must be convertible to the Value type of the map.

Precondition
run() must be called before using this function.

Member Data Documentation

◆ INF

template< typename GR , typename V , typename C >
const Value INF

Constant for infinite upper bounds (capacities). It is std::numeric_limits< Value >::infinity() if available, (std::numeric_limits< Value >::max)() otherwise.