equal
deleted
inserted
replaced
2 #ifndef HUGO_MINCOSTFLOW_H |
2 #ifndef HUGO_MINCOSTFLOW_H |
3 #define HUGO_MINCOSTFLOW_H |
3 #define HUGO_MINCOSTFLOW_H |
4 |
4 |
5 ///\ingroup galgs |
5 ///\ingroup galgs |
6 ///\file |
6 ///\file |
7 ///\brief An algorithm for finding a flow of value \c k (for small values of \c k) having minimal total cost |
7 ///\brief An algorithm for finding the minimum cost flow of given value in an uncapacitated network |
8 |
|
9 |
8 |
10 #include <hugo/dijkstra.h> |
9 #include <hugo/dijkstra.h> |
11 #include <hugo/graph_wrapper.h> |
10 #include <hugo/graph_wrapper.h> |
12 #include <hugo/maps.h> |
11 #include <hugo/maps.h> |
13 #include <vector> |
12 #include <vector> |
16 namespace hugo { |
15 namespace hugo { |
17 |
16 |
18 /// \addtogroup galgs |
17 /// \addtogroup galgs |
19 /// @{ |
18 /// @{ |
20 |
19 |
21 ///\brief Implementation of an algorithm for finding a flow of value \c k |
20 ///\brief Implementation of an algorithm for finding the minimum cost flow |
22 ///(for small values of \c k) having minimal total cost between 2 nodes |
21 /// of given value in an uncapacitated network |
23 /// |
22 /// |
24 /// |
23 /// |
25 /// The class \ref hugo::MinCostFlow "MinCostFlow" implements |
24 /// The class \ref hugo::MinCostFlow "MinCostFlow" implements |
26 /// an algorithm for solving the following general minimum cost flow problem> |
25 /// an algorithm for solving the following general minimum cost flow problem> |
27 /// |
26 /// |
170 Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length); |
169 Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length); |
171 |
170 |
172 |
171 |
173 while (max_excess > 0){ |
172 while (max_excess > 0){ |
174 |
173 |
|
174 /* |
|
175 * Beginning of the delta scaling phase |
|
176 */ |
175 |
177 |
176 //Merge and stuff |
178 //Merge and stuff |
177 |
179 |
178 Node s = excess_nodes.top(); |
180 Node s = excess_nodes.top(); |
179 SupplyDemand max_excess = excess_nodes[s]; |
181 SupplyDemand max_excess = excess_nodes[s]; |
181 if (max_excess < dificit_nodes[t]){ |
183 if (max_excess < dificit_nodes[t]){ |
182 max_excess = dificit_nodes[t]; |
184 max_excess = dificit_nodes[t]; |
183 } |
185 } |
184 |
186 |
185 |
187 |
186 while(max_excess > ){ |
188 while(max_excess > 0){ |
187 |
189 |
188 |
190 |
189 //s es t valasztasa |
191 //s es t valasztasa |
190 |
192 |
191 //Dijkstra part |
193 //Dijkstra part |