All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
List of all members | Classes | Public Types | Public Member Functions | Public Attributes
CapacityScaling< GR, V, C, TR > Class Template Reference

Detailed Description

template<typename GR, typename V, typename C, typename TR>
class lemon::CapacityScaling< GR, V, C, TR >

CapacityScaling implements the capacity scaling version of the successive shortest path algorithm for finding a minimum cost flow [1], [12]. It is an efficient dual solution method, which runs in polynomial time \(O(m\log U (n+m)\log n)\), where U denotes the maximum of node supply and arc capacity values.

This algorithm is typically slower than CostScaling and NetworkSimplex, but in special cases, it can be more efficient than them. (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.
TRThe traits class that defines various types used by the algorithm. By default, it is CapacityScalingDefaultTraits<GR, V, C>. In most cases, this parameter should not be set directly, consider to use the named template parameters instead.
Warning
Both V and C must be signed number types.
Capacity bounds and supply values must be integer, but arc costs can be arbitrary real numbers.
This algorithm does not support negative costs for arcs having infinite upper bound.

#include <lemon/capacity_scaling.h>

Classes

struct  SetHeap
 Named parameter for setting Heap type. More...
 

Public Types

enum  ProblemType { INFEASIBLE, OPTIMAL, UNBOUNDED }
 Problem type constants for the run() function. More...
 
typedef TR::Digraph Digraph
 The type of the digraph.
 
typedef TR::Value Value
 The type of the flow amounts, capacity bounds and supply values.
 
typedef TR::Cost Cost
 The type of the arc costs.
 
typedef TR::Heap Heap
 The type of the heap used for internal Dijkstra computations.
 
typedef TR Traits
 The traits class of the algorithm.
 

Public Member Functions

 CapacityScaling (const GR &graph)
 Constructor.
 
Parameters

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

template<typename LowerMap >
CapacityScalinglowerMap (const LowerMap &map)
 Set the lower bounds on the arcs.
 
template<typename UpperMap >
CapacityScalingupperMap (const UpperMap &map)
 Set the upper bounds (capacities) on the arcs.
 
template<typename CostMap >
CapacityScalingcostMap (const CostMap &map)
 Set the costs of the arcs.
 
template<typename SupplyMap >
CapacityScalingsupplyMap (const SupplyMap &map)
 Set the supply values of the nodes.
 
CapacityScalingstSupply (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 (int factor=4)
 Run the algorithm.
 
CapacityScalingresetParams ()
 Reset all the parameters that have been given before.
 
CapacityScalingreset ()
 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).
 

Member Enumeration Documentation

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 digraph contains an arc of negative cost and infinite upper bound. It means that the objective function is unbounded on that arc, however, note that it could actually be bounded over the feasible flows, but this algroithm cannot handle these cases.

Constructor & Destructor Documentation

CapacityScaling ( const GR &  graph)
inline

The constructor of the class.

Parameters
graphThe digraph the algorithm runs on.

Member Function Documentation

CapacityScaling& 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)
CapacityScaling& 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)
CapacityScaling& 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)
CapacityScaling& 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)
CapacityScaling& 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)
ProblemType run ( int  factor = 4)
inline

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

CapacityScaling<ListDigraph> cs(graph);
cs.lowerMap(lower).upperMap(upper).costMap(cost)
.supplyMap(sup).run();

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
factorThe capacity scaling factor. It must be larger than one to use scaling. If it is less or equal to one, then scaling will be disabled.
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 digraph contains an arc of negative cost and infinite upper bound. It means that the objective function is unbounded on that arc, however, note that it could actually be bounded over the feasible flows, but this algroithm cannot handle these cases.
See Also
ProblemType
resetParams(), reset()
CapacityScaling& 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,

CapacityScaling<ListDigraph> cs(graph);
// First run
cs.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;
cs.costMap(cost).run();
// Run again from scratch using resetParams()
// (the lower bounds will be set to zero on all arcs)
cs.resetParams();
cs.upperMap(capacity).costMap(cost)
.supplyMap(sup).run();
Returns
(*this)
See Also
reset(), run()
CapacityScaling& 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()
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,
cs.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.
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.
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.
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.
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

const Value INF

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