class lemon::CostScaling< GR, V, C, TR >

CostScaling implements a cost scaling algorithm that performs push/augment and relabel operations for finding a minimum cost flow [AMO93], [GT90], [Gol97], [BKV98]. It is a highly efficient primal-dual solution method, which can be viewed as the generalization of the preflow push-relabel algorithm for the maximum flow problem.

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 CostScalingDefaultTraits<GR, V, C>. In most cases, this parameter should not be set directly, consider to use the named template parameters instead.

**Warning:**- Both number types must be signed and all input data must be integer.
- This algorithm does not support negative costs for such arcs that have infinite upper bound.

**Note:**- CostScaling provides three different internal methods, from which the most efficient one is used by default. For more information, see Method.

`#include <lemon/cost_scaling.h>`

## Classes | |

struct | SetLargeCost |

Named parameter for setting `LargeCost` type. More... | |

## Public Types | |

enum | ProblemType { INFEASIBLE, OPTIMAL, UNBOUNDED } |

Problem type constants for the | |

enum | Method { PUSH, AUGMENT, PARTIAL_AUGMENT } |

Constants for selecting the internal method. 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::LargeCost | LargeCost |

The large cost type. | |

typedef TR | Traits |

The traits class of the algorithm. | |

## Public Member Functions | |

CostScaling (const GR &graph) | |

Constructor. | |

Parameters | |

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

template<typename LowerMap > | |

CostScaling & | lowerMap (const LowerMap &map) |

Set the lower bounds on the arcs. | |

template<typename UpperMap > | |

CostScaling & | upperMap (const UpperMap &map) |

Set the upper bounds (capacities) on the arcs. | |

template<typename CostMap > | |

CostScaling & | costMap (const CostMap &map) |

Set the costs of the arcs. | |

template<typename SupplyMap > | |

CostScaling & | supplyMap (const SupplyMap &map) |

Set the supply values of the nodes. | |

CostScaling & | 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=PARTIAL_AUGMENT, int factor=8) |

Run the algorithm. | |

CostScaling & | resetParams () |

Reset all the parameters that have been given before. | |

CostScaling & | reset () |

Reset all the parameters that have been given before. | |

Query Functions | |

The results of the algorithm can be obtained using these functions. | |

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 |

Return the flow map (the primal solution). | |

Cost | potential (const Node &n) const |

Return the potential (dual value) of the given node. | |

template<typename PotentialMap > | |

void | potentialMap (PotentialMap &map) const |

Return the potential map (the dual solution). | |

## Public Attributes | |

const Value | INF |

Constant for infinite upper bounds (capacities). | |

## Private Member Functions | |

void | startAugment (int max_length) |

Execute the algorithm performing augment and relabel operations. | |

void | startPush () |

Execute the algorithm performing push and relabel operations. |

typedef TR::LargeCost LargeCost |

The large cost type used for internal computations. By default, it is `long`

`long`

if the `Cost`

type is integer, otherwise it is `double`

.

enum ProblemType |

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

**Enumerator:**

enum Method |

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

CostScaling provides three internal methods that differ mainly in their base operations, which are used in conjunction with the relabel operation. By default, the so called Partial Augment-Relabel method is used, which proved to be the most efficient and the most robust on various test inputs. However, the other methods can be selected using the run() function with the proper parameter.

**Enumerator:**

CostScaling | ( | const GR & | graph | ) | ` [inline]` |

The constructor of the class.

**Parameters:**-
graph The digraph the algorithm runs on.

CostScaling& 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:**-
map An arc map storing the lower bounds. Its `Value`

type must be convertible to the`Value`

type of the algorithm.

**Returns:**`(*this)`

CostScaling& 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:**-
map An arc map storing the upper bounds. Its `Value`

type must be convertible to the`Value`

type of the algorithm.

**Returns:**`(*this)`

CostScaling& 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:**-
map An arc map storing the costs. Its `Value`

type must be convertible to the`Cost`

type of the algorithm.

**Returns:**`(*this)`

CostScaling& 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:**-
map A node map storing the supply values. Its `Value`

type must be convertible to the`Value`

type of the algorithm.

**Returns:**`(*this)`

CostScaling& 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 such 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)`

ProblemType run | ( | Method | method = `PARTIAL_AUGMENT` , |

int | factor = `8` |
||

) | ` [inline]` |

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

CostScaling<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:**-
method The internal method that will be used in the algorithm. For more information, see Method. factor The cost scaling factor. It must be larger than one.

**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, Method
- resetParams(), reset()

CostScaling& 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,

CostScaling<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)`

CostScaling& reset | ( | ) | ` [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. If this function is not used, all the parameters given before are kept for the next run() call. However, the underlying digraph must not be modified after this class have been constructed, since it copies and extends the graph.

**Returns:**`(*this)`

Number totalCost | ( | ) | const` [inline]` |

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

**Note:**- The return type of the function can be specified as a template parameter. For example, It is useful if the total cost cannot be stored in the
`cs.totalCost<double>();`

`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.

Generated on Wed Nov 9 2011 11:44:20 by 1.7.3