equal
deleted
inserted
replaced
90 //To store the flow |
90 //To store the flow |
91 EdgeIntMap flow; |
91 EdgeIntMap flow; |
92 //To store the potentila (dual variables) |
92 //To store the potentila (dual variables) |
93 typename Graph::template NodeMap<Length> potential; |
93 typename Graph::template NodeMap<Length> potential; |
94 |
94 |
95 //Container to store found paths |
|
96 //std::vector< std::vector<Edge> > paths; |
|
97 //typedef DirPath<Graph> DPath; |
|
98 //DPath paths; |
|
99 |
|
100 |
95 |
101 Length total_length; |
96 Length total_length; |
102 |
97 |
103 |
98 |
104 public : |
99 public : |
149 if (!dijkstra.reached(t)){ |
144 if (!dijkstra.reached(t)){ |
150 //There are no k paths from s to t |
145 //There are no k paths from s to t |
151 break; |
146 break; |
152 }; |
147 }; |
153 |
148 |
|
149 //We have to copy the potential |
|
150 FOR_EACH_LOC(typename ResGraphType::NodeIt, n, res_graph){ |
|
151 potential[n] += dijkstra.distMap()[n]; |
|
152 } |
|
153 /* |
154 { |
154 { |
155 //We have to copy the potential |
155 //We have to copy the potential |
156 typename ResGraphType::NodeIt n; |
156 typename ResGraphType::NodeIt n; |
157 for ( res_graph.first(n) ; res_graph.valid(n) ; res_graph.next(n) ) { |
157 for ( res_graph.first(n) ; res_graph.valid(n) ; res_graph.next(n) ) { |
158 potential[n] += dijkstra.distMap()[n]; |
158 potential[n] += dijkstra.distMap()[n]; |
159 } |
159 } |
160 } |
160 } |
161 |
161 */ |
162 |
162 |
163 //Augmenting on the sortest path |
163 //Augmenting on the sortest path |
164 Node n=t; |
164 Node n=t; |
165 ResGraphEdge e; |
165 ResGraphEdge e; |
166 while (n!=s){ |
166 while (n!=s){ |
223 } |
223 } |
224 } |
224 } |
225 return true; |
225 return true; |
226 } |
226 } |
227 |
227 |
228 /* |
|
229 ///\todo To be implemented later |
|
230 |
|
231 ///This function gives back the \c j-th path in argument p. |
|
232 ///Assumes that \c run() has been run and nothing changed since then. |
|
233 /// \warning It is assumed that \c p is constructed to be a path of graph \c G. If \c j is greater than the result of previous \c run, then the result here will be an empty path. |
|
234 template<typename DirPath> |
|
235 void getPath(DirPath& p, int j){ |
|
236 p.clear(); |
|
237 typename DirPath::Builder B(p); |
|
238 for(typename std::vector<Edge>::iterator i=paths[j].begin(); |
|
239 i!=paths[j].end(); ++i ){ |
|
240 B.pushBack(*i); |
|
241 } |
|
242 |
|
243 B.commit(); |
|
244 } |
|
245 |
|
246 */ |
|
247 |
228 |
248 }; //class MinCostFlows |
229 }; //class MinCostFlows |
249 |
230 |
250 ///@} |
231 ///@} |
251 |
232 |
252 } //namespace hugo |
233 } //namespace hugo |
253 |
234 |
254 #endif //HUGO_MINCOSTFLOW_H |
235 #endif //HUGO_MINCOSTFLOWS_H |