36 ///(for small values of \c k) having minimal total cost between 2 nodes |
36 ///(for small values of \c k) having minimal total cost between 2 nodes |
37 /// |
37 /// |
38 /// |
38 /// |
39 /// The class \ref lemon::MinCostFlow "MinCostFlow" implements an |
39 /// The class \ref lemon::MinCostFlow "MinCostFlow" implements an |
40 /// algorithm for finding a flow of value \c k having minimal total |
40 /// algorithm for finding a flow of value \c k having minimal total |
41 /// cost from a given source node to a given target node in an |
41 /// cost from a given source node to a given target node in a |
42 /// edge-weighted directed graph. To this end, the edge-capacities |
42 /// directed graph with a cost function on the edges. To |
43 /// and edge-weights have to be nonnegative. The edge-capacities |
43 /// this end, the edge-capacities and edge-costs have to be |
44 /// should be integers, but the edge-weights can be integers, reals |
44 /// nonnegative. The edge-capacities should be integers, but the |
45 /// or of other comparable numeric type. This algorithm is intended |
45 /// edge-costs can be integers, reals or of other comparable |
46 /// to be used only for small values of \c k, since it is only |
46 /// numeric type. This algorithm is intended to be used only for |
47 /// polynomial in k, not in the length of k (which is log k): in |
47 /// small values of \c k, since it is only polynomial in k, not in |
48 /// order to find the minimum cost flow of value \c k it finds the |
48 /// the length of k (which is log k): in order to find the minimum |
49 /// minimum cost flow of value \c i for every \c i between 0 and \c |
49 /// cost flow of value \c k it finds the minimum cost flow of value |
50 /// k. |
50 /// \c i for every \c i between 0 and \c k. |
51 /// |
51 /// |
52 ///\param Graph The directed graph type the algorithm runs on. |
52 ///\param Graph The directed graph type the algorithm runs on. |
53 ///\param LengthMap The type of the length map. |
53 ///\param LengthMap The type of the length map. |
54 ///\param CapacityMap The capacity map type. |
54 ///\param CapacityMap The capacity map type. |
55 /// |
55 /// |
115 public : |
115 public : |
116 |
116 |
117 /*! \brief The constructor of the class. |
117 /*! \brief The constructor of the class. |
118 |
118 |
119 \param _g The directed graph the algorithm runs on. |
119 \param _g The directed graph the algorithm runs on. |
120 \param _length The length (weight or cost) of the edges. |
120 \param _length The length (cost) of the edges. |
121 \param _cap The capacity of the edges. |
121 \param _cap The capacity of the edges. |
122 \param _s Source node. |
122 \param _s Source node. |
123 \param _t Target node. |
123 \param _t Target node. |
124 */ |
124 */ |
125 MinCostFlow(Graph& _g, LengthMap& _length, CapacityMap& _cap, |
125 MinCostFlow(Graph& _g, LengthMap& _length, CapacityMap& _cap, |
201 for (typename Graph::OutEdgeIt e(g, s); e!=INVALID; ++e) i+=flow[e]; |
201 for (typename Graph::OutEdgeIt e(g, s); e!=INVALID; ++e) i+=flow[e]; |
202 for (typename Graph::InEdgeIt e(g, s); e!=INVALID; ++e) i-=flow[e]; |
202 for (typename Graph::InEdgeIt e(g, s); e!=INVALID; ++e) i-=flow[e]; |
203 return i; |
203 return i; |
204 } |
204 } |
205 |
205 |
206 /// Total weight of the found flow. |
206 /// Total cost of the found flow. |
207 |
207 |
208 /// This function gives back the total weight of the found flow. |
208 /// This function gives back the total cost of the found flow. |
209 Length totalLength(){ |
209 Length totalLength(){ |
210 return total_length; |
210 return total_length; |
211 } |
211 } |
212 |
212 |
213 ///Returns a const reference to the EdgeMap \c flow. |
213 ///Returns a const reference to the EdgeMap \c flow. |