All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
CycleCanceling implements three different cycle-canceling algorithms for finding a minimum cost flow [1], [24], [16]. The most efficent one is the Cancel-and-Tighten algorithm, thus it is the default method. It runs in strongly polynomial time 
, 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.
| 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. |
V and C must be signed number types. #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. | |
Public Member Functions | |
| CycleCanceling (const GR &graph) | |
| Constructor. More... | |
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. More... | |
| template<typename UpperMap > | |
| CycleCanceling & | upperMap (const UpperMap &map) |
| Set the upper bounds (capacities) on the arcs. More... | |
| template<typename CostMap > | |
| CycleCanceling & | costMap (const CostMap &map) |
| Set the costs of the arcs. More... | |
| template<typename SupplyMap > | |
| CycleCanceling & | supplyMap (const SupplyMap &map) |
| Set the supply values of the nodes. More... | |
| CycleCanceling & | stSupply (const Node &s, const Node &t, Value k) |
| Set single source and target nodes and a supply value. More... | |
Execution control | |
The algorithm can be executed using run(). | |
| ProblemType | run (Method method=CANCEL_AND_TIGHTEN) |
| Run the algorithm. More... | |
| CycleCanceling & | resetParams () |
| Reset all the parameters that have been given before. More... | |
| CycleCanceling & | reset () |
| Reset the internal data structures and all the parameters that have been given before. More... | |
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. More... | |
| Value | flow (const Arc &a) const |
| Return the flow on the given arc. More... | |
| template<typename FlowMap > | |
| void | flowMap (FlowMap &map) const |
| Copy the flow values (the primal solution) into the given map. More... | |
| Cost | potential (const Node &n) const |
| Return the potential (dual value) of the given node. More... | |
| template<typename PotentialMap > | |
| void | potentialMap (PotentialMap &map) const |
| Copy the potential values (the dual solution) into the given map. More... | |
Public Attributes | |
| const Value | INF |
| Constant for infinite upper bounds (capacities). More... | |
| enum ProblemType |
Enum type containing the problem type constants that can be returned by the run() function of the algorithm.
| 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 [16]. It improves along a minimum mean cycle in each iteration. Its running time complexity is |
| CANCEL_AND_TIGHTEN |
The "Cancel-and-Tighten" algorithm, which can be viewed as an improved version of the previous method [16]. It is faster both in theory and in practice, its running time complexity is |
|
inline |
The constructor of the class.
| graph | The digraph the algorithm runs on. |
|
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.
| map | An arc map storing the lower bounds. Its Value type must be convertible to the Value type of the algorithm. |
. (*this)
|
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).
| map | An arc map storing the upper bounds. Its Value type must be convertible to the Value type of the algorithm. |
(*this)
|
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.
| map | An arc map storing the costs. Its Value type must be convertible to the Cost type of the algorithm. |
(*this)
|
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.
| map | A node map storing the supply values. Its Value type must be convertible to the Value type of the algorithm. |
(*this)
|
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.
| 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). |
(*this)
|
inline |
This function runs the algorithm. The paramters can be specified using functions lowerMap(), upperMap(), costMap(), supplyMap(), stSupply(). For example,
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.
| method | The cycle-canceling method that will be used. For more information, see Method. |
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.
|
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,
(*this)
|
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.
(*this)
|
inline |
This function returns the total cost of the found flow. Its complexity is O(m).
Cost type of the algorithm, which is the default return type of the function.
|
inline |
This function returns the flow on the given arc.
|
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.
|
inline |
This function returns the potential (dual value) of the given node.
|
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.
| const Value INF |
Constant for infinite upper bounds (capacities). It is std::numeric_limits<Value>::infinity() if available, std::numeric_limits<Value>::max() otherwise.
1.8.5