equal
deleted
inserted
replaced
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 a flow of value \c k (for small values of \c k) having minimal total cost |
8 |
8 |
9 #include <iostream> |
9 #include <iostream> |
10 #include <dijkstra.h> |
10 #include <hugo/dijkstra.h> |
11 #include <graph_wrapper.h> |
11 #include <graph_wrapper.h> |
12 #include <maps.h> |
12 #include <hugo/maps.h> |
13 #include <vector.h> |
13 #include <vector> |
14 #include <for_each_macros.h> |
14 #include <for_each_macros.h> |
15 |
15 |
16 namespace hugo { |
16 namespace hugo { |
17 |
17 |
18 /// \addtogroup galgs |
18 /// \addtogroup galgs |
83 const LengthMap& length; |
83 const LengthMap& length; |
84 const CapacityMap& capacity; |
84 const CapacityMap& capacity; |
85 |
85 |
86 //auxiliary variables |
86 //auxiliary variables |
87 |
87 |
88 //The value is 1 iff the edge is reversed. |
88 //To store the flow |
89 //If the algorithm has finished, the edges of the seeked paths are |
|
90 //exactly those that are reversed |
|
91 EdgeIntMap flow; |
89 EdgeIntMap flow; |
|
90 //To store the potentila (dual variables) |
92 typename Graph::template NodeMap<Length> potential; |
91 typename Graph::template NodeMap<Length> potential; |
93 |
92 |
94 //Container to store found paths |
93 //Container to store found paths |
95 std::vector< std::vector<Edge> > paths; |
94 //std::vector< std::vector<Edge> > paths; |
96 //typedef DirPath<Graph> DPath; |
95 //typedef DirPath<Graph> DPath; |
97 //DPath paths; |
96 //DPath paths; |
98 |
97 |
99 |
98 |
100 Length total_length; |
99 Length total_length; |
184 ///Assumes that \c run() has been run and nothing changed since then. |
183 ///Assumes that \c run() has been run and nothing changed since then. |
185 Length totalLength(){ |
184 Length totalLength(){ |
186 return total_length; |
185 return total_length; |
187 } |
186 } |
188 |
187 |
|
188 //This function checks, whether the given solution is optimal |
|
189 //Running after a \c run() should return with true |
|
190 bool checkSolution(){ |
|
191 Length mod_pot; |
|
192 Length fl_e; |
|
193 FOR_EACH_LOC(typename Graph::EdgeIt, e, G){ |
|
194 //C^{\Pi}_{i,j} |
|
195 mod_pot = length[e]-potential[G.head(e)]+potential[G.head(e)]; |
|
196 fl_e = flow[e]; |
|
197 if (0<fl_e && fl_e<capacity[e]){ |
|
198 if (mod_pot != 0) |
|
199 return false; |
|
200 } |
|
201 else{ |
|
202 if (mod_pot > 0 && fl_e != 0) |
|
203 return false; |
|
204 if (mod_pot < 0 && fl_e != capacity[e]) |
|
205 return false; |
|
206 } |
|
207 } |
|
208 return true; |
|
209 } |
|
210 |
189 /* |
211 /* |
190 ///\todo To be implemented later |
212 ///\todo To be implemented later |
191 |
213 |
192 ///This function gives back the \c j-th path in argument p. |
214 ///This function gives back the \c j-th path in argument p. |
193 ///Assumes that \c run() has been run and nothing changed since then. |
215 ///Assumes that \c run() has been run and nothing changed since then. |