34 /// \brief An efficient algorithm for finding a minimum cost flow. |
34 /// \brief An efficient algorithm for finding a minimum cost flow. |
35 /// |
35 /// |
36 /// \ref MinCostFlow provides an efficient algorithm for finding |
36 /// \ref MinCostFlow provides an efficient algorithm for finding |
37 /// a minimum cost flow. |
37 /// a minimum cost flow. |
38 /// |
38 /// |
39 /// \note \ref MinCostFlow is just an alias for \ref NetworkSimplex, |
39 /// This class is just an alias for \ref NetworkSimplex, |
40 /// which is the most efficient implementation for the minimum cost |
40 /// which is the most efficient algorithm for the minimum cost |
41 /// flow problem in the LEMON library according to our benchmark |
41 /// flow problem in LEMON according to our benchmark tests. |
42 /// tests. |
42 /// For the detailed documentation of this class see |
43 /// |
|
44 /// \note There are three implementations for the minimum cost flow |
|
45 /// problem, that can be used exactly the same way. |
|
46 /// - \ref CapacityScaling |
|
47 /// - \ref CycleCanceling |
|
48 /// - \ref NetworkSimplex |
|
49 /// |
|
50 /// \note For the detailed documentation of this class see |
|
51 /// \ref NetworkSimplex. |
43 /// \ref NetworkSimplex. |
52 /// |
44 /// |
53 /// \param Graph The directed graph type the algorithm runs on. |
45 /// There are four implementations for the minimum cost flow problem, |
54 /// \param LowerMap The type of the lower bound map. |
46 /// which can be used exactly the same way except for the fact that |
55 /// \param CapacityMap The type of the capacity (upper bound) map. |
47 /// \ref CycleCanceling does not provide dual solution (node |
56 /// \param CostMap The type of the cost (length) map. |
48 /// potentials) since it is a pure primal method. |
57 /// \param SupplyMap The type of the supply map. |
49 /// - \ref CapacityScaling The capacity scaling algorithm. |
|
50 /// - \ref CostScaling The cost scaling algorithm. |
|
51 /// - \ref CycleCanceling A cycle-canceling algorithm. |
|
52 /// - \ref NetworkSimplex The network simplex algorithm. |
|
53 /// |
|
54 /// \tparam Graph The directed graph type the algorithm runs on. |
|
55 /// \tparam LowerMap The type of the lower bound map. |
|
56 /// \tparam CapacityMap The type of the capacity (upper bound) map. |
|
57 /// \tparam CostMap The type of the cost (length) map. |
|
58 /// \tparam SupplyMap The type of the supply map. |
58 /// |
59 /// |
59 /// \warning |
60 /// \warning |
60 /// - Edge capacities and costs should be non-negative integers. |
61 /// - Edge capacities and costs should be \e non-negative \e integers. |
61 /// However \c CostMap::Value should be signed type. |
62 /// - Supply values should be \e signed \e integers. |
62 /// - Supply values should be signed integers. |
63 /// - \c LowerMap::Value must be convertible to \c CapacityMap::Value. |
63 /// - \c LowerMap::Value must be convertible to |
64 /// - \c CapacityMap::Value and \c SupplyMap::Value must be |
64 /// \c CapacityMap::Value and \c CapacityMap::Value must be |
65 /// convertible to each other. |
65 /// convertible to \c SupplyMap::Value. |
66 /// - All value types must be convertible to \c CostMap::Value, which |
|
67 /// must be signed type. |
66 /// |
68 /// |
67 /// \author Peter Kovacs |
69 /// \author Peter Kovacs |
68 |
70 |
69 template < typename Graph, |
71 template < typename Graph, |
70 typename LowerMap = typename Graph::template EdgeMap<int>, |
72 typename LowerMap = typename Graph::template EdgeMap<int>, |