21 ///(for small values of \c k) having minimal total cost between 2 nodes |
21 ///(for small values of \c k) having minimal total cost between 2 nodes |
22 /// |
22 /// |
23 /// |
23 /// |
24 /// The class \ref hugo::MinCostFlows "MinCostFlows" implements |
24 /// The class \ref hugo::MinCostFlows "MinCostFlows" implements |
25 /// an algorithm for finding a flow of value \c k |
25 /// an algorithm for finding a flow of value \c k |
26 /// having minimal total cost |
26 /// having minimal total cost |
27 /// from a given source node to a given target node in an |
27 /// from a given source node to a given target node in an |
28 /// edge-weighted directed graph having nonnegative integer capacities. |
28 /// edge-weighted directed graph. To this end, |
29 /// The range of the length (weight or cost) function can be nonnegative reals but |
29 /// the edge-capacities and edge-weitghs have to be nonnegative. |
30 /// the range of the capacity function has to be the set of nonnegative integers. |
30 /// The edge-capacities should be integers, but the edge-weights can be |
31 /// This algorithm is intended to use only for for small values of \c k, since /// it is not a polinomial time algorithm for finding the minimum cost |
31 /// integers, reals or of other comparable numeric type. |
32 /// maximal flow (in order to find the minimum cost flow of value \c k it |
32 /// This algorithm is intended to use only for small values of \c k, |
|
33 /// since it is only polynomial in k, |
|
34 /// not in the length of k (which is log k). |
|
35 /// In order to find the minimum cost flow of value \c k it |
33 /// finds the minimum cost flow of value \c i for every |
36 /// finds the minimum cost flow of value \c i for every |
34 /// \c i between 0 and \c k). |
37 /// \c i between 0 and \c k. |
35 /// |
38 /// |
36 ///\param Graph The directed graph type the algorithm runs on. |
39 ///\param Graph The directed graph type the algorithm runs on. |
37 ///\param LengthMap The type of the length map. |
40 ///\param LengthMap The type of the length map. |
38 ///\param CapacityMap The capacity map type. |
41 ///\param CapacityMap The capacity map type. |
39 /// |
42 /// |
40 ///\author Attila Bernath |
43 ///\author Attila Bernath |
41 template <typename Graph, typename LengthMap, typename CapacityMap> |
44 template <typename Graph, typename LengthMap, typename CapacityMap> |
42 class MinCostFlows { |
45 class MinCostFlows { |
43 |
|
44 |
|
45 |
46 |
46 typedef typename LengthMap::ValueType Length; |
47 typedef typename LengthMap::ValueType Length; |
47 |
48 |
48 //Warning: this should be integer type |
49 //Warning: this should be integer type |
49 typedef typename CapacityMap::ValueType Capacity; |
50 typedef typename CapacityMap::ValueType Capacity; |