|
| | CapacityScaling (const GR &graph) |
| | Constructor.
|
The parameters of the algorithm can be specified using these functions.
|
| template< typename LowerMap > |
| CapacityScaling & | lowerMap (const LowerMap &map) |
| | Set the lower bounds on the arcs.
|
| template< typename UpperMap > |
| CapacityScaling & | upperMap (const UpperMap &map) |
| | Set the upper bounds (capacities) on the arcs.
|
| template< typename CostMap > |
| CapacityScaling & | costMap (const CostMap &map) |
| | Set the costs of the arcs.
|
| template< typename SupplyMap > |
| CapacityScaling & | supplyMap (const SupplyMap &map) |
| | Set the supply values of the nodes.
|
| CapacityScaling & | stSupply (const Node &s, const Node &t, Value k) |
| | Set single source and target nodes and a supply value.
|
The algorithm can be executed using run().
|
| ProblemType | run (int factor=4) |
| | 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.
|
| CapacityScaling & | 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.
|
| CapacityScaling & | resetParams () |
| | Reset all the parameters that have been given before.
|
| CapacityScaling & | reset () |
| | Reset the internal data structures and all the parameters that have been given before.
|
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.
|
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], [13]. 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
-
| GR | The digraph type the algorithm runs on. |
| V | The number type used for flow amounts, capacity bounds and supply values in the algorithm. By default, it is int. |
| C | The number type used for costs and potentials in the algorithm. By default, it is the same as V. |
| TR | The 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.
-
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 last phase sends any amount above the former.
template< typename GR , typename V , typename C , typename TR >
| 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
-
| s | The source node. |
| t | The target node. |
| k | The required amount of flow from node s to node t (i.e. the supply of s and the demand of t). |
- Returns
- ( * this )
template< typename GR , typename V , typename C , typename TR >
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
-
| factor | The 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 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
-
resetParams(), reset()
template< typename GR , typename V , typename C , typename TR >
| 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.
template< typename GR , typename V , typename C , typename TR >
| 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 that the search for a shortest augmenting path reaches from a node with excess without finding a deficit, 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.
template< typename GR , typename V , typename C , typename TR >
| 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.
template< typename GR , typename V , typename C , typename TR >
| 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.
template< typename GR , typename V , typename C , typename TR >
| CapacityScaling & 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 )
template< typename GR , typename V , typename C , typename TR >
| 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 );
cs.lowerMap( lower )
.upperMap( upper )
.costMap( cost )
.supplyMap( sup )
.run();
cost[ e ] += 100;
cs.costMap( cost ).run();
cs.resetParams();
cs.upperMap( capacity ).costMap( cost ).supplyMap( sup ).run();
- Returns
- ( * this )
- See also
- reset(), run()
template< typename GR , typename V , typename C , typename TR >
| CapacityScaling & reset |
( |
| ) |
|
|
inline |