34 |
34 |
35 ///\brief Implementation of an algorithm for finding a flow of value \c k |
35 ///\brief Implementation of an algorithm for finding a flow of value \c k |
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 |
39 /// The class \ref lemon::MinCostFlow "MinCostFlow" implements an |
40 /// an algorithm for finding a flow of value \c k |
40 /// algorithm for finding a flow of value \c k having minimal total |
41 /// having minimal total cost |
41 /// cost from a given source node to a given target node in an |
42 /// from a given source node to a given target node in an |
42 /// edge-weighted directed graph. To this end, the edge-capacities |
43 /// edge-weighted directed graph. To this end, |
43 /// and edge-weights have to be nonnegative. The edge-capacities |
44 /// the edge-capacities and edge-weitghs have to be nonnegative. |
44 /// should be integers, but the edge-weights can be integers, reals |
45 /// The edge-capacities should be integers, but the edge-weights can be |
45 /// or of other comparable numeric type. This algorithm is intended |
46 /// integers, reals or of other comparable numeric type. |
46 /// to be used only for small values of \c k, since it is only |
47 /// This algorithm is intended to use only for small values of \c k, |
47 /// polynomial in k, not in the length of k (which is log k): in |
48 /// since it is only polynomial in k, |
48 /// order to find the minimum cost flow of value \c k it finds the |
49 /// not in the length of k (which is log k). |
49 /// minimum cost flow of value \c i for every \c i between 0 and \c |
50 /// In order to find the minimum cost flow of value \c k it |
50 /// k. |
51 /// finds the minimum cost flow of value \c i for every |
|
52 /// \c i between 0 and \c k. |
|
53 /// |
51 /// |
54 ///\param Graph The directed graph type the algorithm runs on. |
52 ///\param Graph The directed graph type the algorithm runs on. |
55 ///\param LengthMap The type of the length map. |
53 ///\param LengthMap The type of the length map. |
56 ///\param CapacityMap The capacity map type. |
54 ///\param CapacityMap The capacity map type. |
57 /// |
55 /// |
147 |
145 |
148 //We have to change the potential |
146 //We have to change the potential |
149 for(typename ResGW::NodeIt n(res_graph); n!=INVALID; ++n) |
147 for(typename ResGW::NodeIt n(res_graph); n!=INVALID; ++n) |
150 potential.set(n, potential[n]+dijkstra.distMap()[n]); |
148 potential.set(n, potential[n]+dijkstra.distMap()[n]); |
151 |
149 |
152 //Augmenting on the sortest path |
150 //Augmenting on the shortest path |
153 Node n=t; |
151 Node n=t; |
154 ResGraphEdge e; |
152 ResGraphEdge e; |
155 while (n!=s){ |
153 while (n!=s){ |
156 e = dijkstra.pred(n); |
154 e = dijkstra.pred(n); |
157 n = dijkstra.predNode(n); |
155 n = dijkstra.predNode(n); |
224 const PotentialMap &getPotential() const { return potential;} |
222 const PotentialMap &getPotential() const { return potential;} |
225 |
223 |
226 /*! \brief Checking the complementary slackness optimality criteria. |
224 /*! \brief Checking the complementary slackness optimality criteria. |
227 |
225 |
228 This function checks, whether the given flow and potential |
226 This function checks, whether the given flow and potential |
229 satisfiy the complementary slackness cnditions (i.e. these are optimal). |
227 satisfy the complementary slackness conditions (i.e. these are optimal). |
230 This function only checks optimality, doesn't bother with feasibility. |
228 This function only checks optimality, doesn't bother with feasibility. |
231 For testing purpose. |
229 For testing purpose. |
232 */ |
230 */ |
233 bool checkComplementarySlackness(){ |
231 bool checkComplementarySlackness(){ |
234 Length mod_pot; |
232 Length mod_pot; |