|
1 #ifndef EDMONDS_KARP_HH |
|
2 #define EDMONDS_KARP_HH |
|
3 |
|
4 #include <algorithm> |
|
5 #include <list> |
|
6 #include <iterator> |
|
7 |
|
8 #include <bfs_iterator.hh> |
|
9 //#include <time_measure.h> |
|
10 |
|
11 namespace hugo { |
|
12 |
|
13 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap> |
|
14 class ResGraph { |
|
15 public: |
|
16 typedef typename Graph::NodeIt NodeIt; |
|
17 typedef typename Graph::EachNodeIt EachNodeIt; |
|
18 private: |
|
19 typedef typename Graph::SymEdgeIt OldSymEdgeIt; |
|
20 const Graph& G; |
|
21 FlowMap& flow; |
|
22 const CapacityMap& capacity; |
|
23 public: |
|
24 ResGraph(const Graph& _G, FlowMap& _flow, |
|
25 const CapacityMap& _capacity) : |
|
26 G(_G), flow(_flow), capacity(_capacity) { } |
|
27 |
|
28 class EdgeIt; |
|
29 class OutEdgeIt; |
|
30 friend class EdgeIt; |
|
31 friend class OutEdgeIt; |
|
32 |
|
33 class EdgeIt { |
|
34 friend class ResGraph<Graph, Number, FlowMap, CapacityMap>; |
|
35 protected: |
|
36 const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG; |
|
37 OldSymEdgeIt sym; |
|
38 public: |
|
39 EdgeIt() { } |
|
40 //EdgeIt(const EdgeIt& e) : resG(e.resG), sym(e.sym) { } |
|
41 Number free() const { |
|
42 if (resG->G.aNode(sym)==resG->G.tail(sym)) { |
|
43 return (resG->capacity.get(sym)-resG->flow.get(sym)); |
|
44 } else { |
|
45 return (resG->flow.get(sym)); |
|
46 } |
|
47 } |
|
48 bool valid() const { return sym.valid(); } |
|
49 void augment(Number a) const { |
|
50 if (resG->G.aNode(sym)==resG->G.tail(sym)) { |
|
51 resG->flow.set(sym, resG->flow.get(sym)+a); |
|
52 //resG->flow[sym]+=a; |
|
53 } else { |
|
54 resG->flow.set(sym, resG->flow.get(sym)-a); |
|
55 //resG->flow[sym]-=a; |
|
56 } |
|
57 } |
|
58 }; |
|
59 |
|
60 class OutEdgeIt : public EdgeIt { |
|
61 friend class ResGraph<Graph, Number, FlowMap, CapacityMap>; |
|
62 public: |
|
63 OutEdgeIt() { } |
|
64 //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; } |
|
65 private: |
|
66 OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) { |
|
67 resG=&_resG; |
|
68 sym=resG->G.template first<OldSymEdgeIt>(v); |
|
69 while( sym.valid() && !(free()>0) ) { ++sym; } |
|
70 } |
|
71 public: |
|
72 OutEdgeIt& operator++() { |
|
73 ++sym; |
|
74 while( sym.valid() && !(free()>0) ) { ++sym; } |
|
75 return *this; |
|
76 } |
|
77 }; |
|
78 |
|
79 void getFirst(OutEdgeIt& e, NodeIt v) const { |
|
80 e=OutEdgeIt(*this, v); |
|
81 } |
|
82 void getFirst(EachNodeIt& v) const { G.getFirst(v); } |
|
83 |
|
84 template< typename It > |
|
85 It first() const { |
|
86 It e; |
|
87 getFirst(e); |
|
88 return e; |
|
89 } |
|
90 |
|
91 template< typename It > |
|
92 It first(NodeIt v) const { |
|
93 It e; |
|
94 getFirst(e, v); |
|
95 return e; |
|
96 } |
|
97 |
|
98 NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); } |
|
99 NodeIt head(EdgeIt e) const { return G.bNode(e.sym); } |
|
100 |
|
101 NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); } |
|
102 NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); } |
|
103 |
|
104 int id(NodeIt v) const { return G.id(v); } |
|
105 |
|
106 template <typename S> |
|
107 class NodeMap { |
|
108 typename Graph::NodeMap<S> node_map; |
|
109 public: |
|
110 NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { } |
|
111 NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { } |
|
112 void set(NodeIt nit, S a) { node_map.set(nit, a); } |
|
113 S get(NodeIt nit) const { return node_map.get(nit); } |
|
114 S& operator[](NodeIt nit) { return node_map[nit]; } |
|
115 const S& operator[](NodeIt nit) const { return node_map[nit]; } |
|
116 }; |
|
117 |
|
118 }; |
|
119 |
|
120 |
|
121 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap> |
|
122 class ResGraph2 { |
|
123 public: |
|
124 typedef typename Graph::NodeIt NodeIt; |
|
125 typedef typename Graph::EachNodeIt EachNodeIt; |
|
126 private: |
|
127 //typedef typename Graph::SymEdgeIt OldSymEdgeIt; |
|
128 typedef typename Graph::OutEdgeIt OldOutEdgeIt; |
|
129 typedef typename Graph::InEdgeIt OldInEdgeIt; |
|
130 |
|
131 const Graph& G; |
|
132 FlowMap& flow; |
|
133 const CapacityMap& capacity; |
|
134 public: |
|
135 ResGraph2(const Graph& _G, FlowMap& _flow, |
|
136 const CapacityMap& _capacity) : |
|
137 G(_G), flow(_flow), capacity(_capacity) { } |
|
138 |
|
139 class EdgeIt; |
|
140 class OutEdgeIt; |
|
141 friend class EdgeIt; |
|
142 friend class OutEdgeIt; |
|
143 |
|
144 class EdgeIt { |
|
145 friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>; |
|
146 protected: |
|
147 const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG; |
|
148 //OldSymEdgeIt sym; |
|
149 OldOutEdgeIt out; |
|
150 OldInEdgeIt in; |
|
151 bool out_or_in; //true, iff out |
|
152 public: |
|
153 EdgeIt() : out_or_in(true) { } |
|
154 Number free() const { |
|
155 if (out_or_in) { |
|
156 return (resG->capacity.get(out)-resG->flow.get(out)); |
|
157 } else { |
|
158 return (resG->flow.get(in)); |
|
159 } |
|
160 } |
|
161 bool valid() const { |
|
162 return out_or_in && out.valid() || in.valid(); } |
|
163 void augment(Number a) const { |
|
164 if (out_or_in) { |
|
165 resG->flow.set(out, resG->flow.get(out)+a); |
|
166 } else { |
|
167 resG->flow.set(in, resG->flow.get(in)-a); |
|
168 } |
|
169 } |
|
170 }; |
|
171 |
|
172 class OutEdgeIt : public EdgeIt { |
|
173 friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>; |
|
174 public: |
|
175 OutEdgeIt() { } |
|
176 private: |
|
177 OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) { |
|
178 resG=&_resG; |
|
179 out=resG->G.template first<OldOutEdgeIt>(v); |
|
180 while( out.valid() && !(free()>0) ) { ++out; } |
|
181 if (!out.valid()) { |
|
182 out_or_in=0; |
|
183 in=resG->G.template first<OldInEdgeIt>(v); |
|
184 while( in.valid() && !(free()>0) ) { ++in; } |
|
185 } |
|
186 } |
|
187 public: |
|
188 OutEdgeIt& operator++() { |
|
189 if (out_or_in) { |
|
190 NodeIt v=resG->G.aNode(out); |
|
191 ++out; |
|
192 while( out.valid() && !(free()>0) ) { ++out; } |
|
193 if (!out.valid()) { |
|
194 out_or_in=0; |
|
195 in=resG->G.template first<OldInEdgeIt>(v); |
|
196 while( in.valid() && !(free()>0) ) { ++in; } |
|
197 } |
|
198 } else { |
|
199 ++in; |
|
200 while( in.valid() && !(free()>0) ) { ++in; } |
|
201 } |
|
202 return *this; |
|
203 } |
|
204 }; |
|
205 |
|
206 void getFirst(OutEdgeIt& e, NodeIt v) const { |
|
207 e=OutEdgeIt(*this, v); |
|
208 } |
|
209 void getFirst(EachNodeIt& v) const { G.getFirst(v); } |
|
210 |
|
211 template< typename It > |
|
212 It first() const { |
|
213 It e; |
|
214 getFirst(e); |
|
215 return e; |
|
216 } |
|
217 |
|
218 template< typename It > |
|
219 It first(NodeIt v) const { |
|
220 It e; |
|
221 getFirst(e, v); |
|
222 return e; |
|
223 } |
|
224 |
|
225 NodeIt tail(EdgeIt e) const { |
|
226 return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } |
|
227 NodeIt head(EdgeIt e) const { |
|
228 return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } |
|
229 |
|
230 NodeIt aNode(OutEdgeIt e) const { |
|
231 return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } |
|
232 NodeIt bNode(OutEdgeIt e) const { |
|
233 return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } |
|
234 |
|
235 int id(NodeIt v) const { return G.id(v); } |
|
236 |
|
237 template <typename S> |
|
238 class NodeMap { |
|
239 typename Graph::NodeMap<S> node_map; |
|
240 public: |
|
241 NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { } |
|
242 NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { } |
|
243 void set(NodeIt nit, S a) { node_map.set(nit, a); } |
|
244 S get(NodeIt nit) const { return node_map.get(nit); } |
|
245 }; |
|
246 }; |
|
247 |
|
248 |
|
249 template <typename Graph, typename Number, typename FlowMap, typename CapacityMap> |
|
250 class MaxFlow { |
|
251 public: |
|
252 typedef typename Graph::NodeIt NodeIt; |
|
253 typedef typename Graph::EdgeIt EdgeIt; |
|
254 typedef typename Graph::EachEdgeIt EachEdgeIt; |
|
255 typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
256 typedef typename Graph::InEdgeIt InEdgeIt; |
|
257 |
|
258 private: |
|
259 const Graph* G; |
|
260 NodeIt s; |
|
261 NodeIt t; |
|
262 FlowMap* flow; |
|
263 const CapacityMap* capacity; |
|
264 typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph; |
|
265 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; |
|
266 typedef typename AugGraph::EdgeIt AugEdgeIt; |
|
267 |
|
268 //AugGraph res_graph; |
|
269 //typedef typename AugGraph::NodeMap<bool> ReachedMap; |
|
270 //typename AugGraph::NodeMap<AugEdgeIt> pred; |
|
271 //typename AugGraph::NodeMap<Number> free; |
|
272 public: |
|
273 MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : |
|
274 G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) //, |
|
275 //res_graph(G, flow, capacity), pred(res_graph), free(res_graph) |
|
276 { } |
|
277 bool augmentOnShortestPath() { |
|
278 AugGraph res_graph(*G, *flow, *capacity); |
|
279 bool _augment=false; |
|
280 |
|
281 typedef typename AugGraph::NodeMap<bool> ReachedMap; |
|
282 BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph); |
|
283 res_bfs.pushAndSetReached(s); |
|
284 |
|
285 typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph); |
|
286 //filled up with invalid iterators |
|
287 //pred.set(s, AugEdgeIt()); |
|
288 |
|
289 typename AugGraph::NodeMap<Number> free(res_graph); |
|
290 |
|
291 //searching for augmenting path |
|
292 while ( !res_bfs.finished() ) { |
|
293 AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs); |
|
294 if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) { |
|
295 NodeIt v=res_graph.tail(e); |
|
296 NodeIt w=res_graph.head(e); |
|
297 pred.set(w, e); |
|
298 if (res_graph.valid(pred.get(v))) { |
|
299 free.set(w, std::min(free.get(v), res_graph.free(e))); |
|
300 } else { |
|
301 free.set(w, res_graph.free(e)); |
|
302 } |
|
303 if (res_graph.head(e)==t) { _augment=true; break; } |
|
304 } |
|
305 |
|
306 ++res_bfs; |
|
307 } //end of searching augmenting path |
|
308 |
|
309 if (_augment) { |
|
310 NodeIt n=t; |
|
311 Number augment_value=free.get(t); |
|
312 while (res_graph.valid(pred.get(n))) { |
|
313 AugEdgeIt e=pred.get(n); |
|
314 res_graph.augment(e, augment_value); |
|
315 //e.augment(augment_value); |
|
316 n=res_graph.tail(e); |
|
317 } |
|
318 } |
|
319 |
|
320 return _augment; |
|
321 } |
|
322 |
|
323 template<typename MutableGraph> bool augmentOnBlockingFlow() { |
|
324 bool _augment=false; |
|
325 |
|
326 AugGraph res_graph(*G, *flow, *capacity); |
|
327 |
|
328 typedef typename AugGraph::NodeMap<bool> ReachedMap; |
|
329 BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph); |
|
330 |
|
331 bfs.pushAndSetReached(s); |
|
332 typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's |
|
333 while ( !bfs.finished() ) { |
|
334 AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); |
|
335 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
|
336 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
|
337 } |
|
338 |
|
339 ++bfs; |
|
340 } //computing distances from s in the residual graph |
|
341 |
|
342 MutableGraph F; |
|
343 typename AugGraph::NodeMap<NodeIt> res_graph_to_F(res_graph); |
|
344 for(typename AugGraph::EachNodeIt n=res_graph.template first<typename AugGraph::EachNodeIt>(); res_graph.valid(n); res_graph.next(n)) { |
|
345 res_graph_to_F.set(n, F.addNode()); |
|
346 } |
|
347 |
|
348 typename MutableGraph::NodeIt sF=res_graph_to_F.get(s); |
|
349 typename MutableGraph::NodeIt tF=res_graph_to_F.get(t); |
|
350 |
|
351 typename MutableGraph::EdgeMap<AugEdgeIt> original_edge(F); |
|
352 typename MutableGraph::EdgeMap<Number> residual_capacity(F); |
|
353 |
|
354 //Making F to the graph containing the edges of the residual graph |
|
355 //which are in some shortest paths |
|
356 for(typename AugGraph::EachEdgeIt e=res_graph.template first<typename AugGraph::EachEdgeIt>(); res_graph.valid(e); res_graph.next(e)) { |
|
357 if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { |
|
358 typename MutableGraph::EdgeIt f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
|
359 original_edge.update(); |
|
360 original_edge.set(f, e); |
|
361 residual_capacity.update(); |
|
362 residual_capacity.set(f, res_graph.free(e)); |
|
363 } |
|
364 } |
|
365 |
|
366 bool __augment=true; |
|
367 |
|
368 while (__augment) { |
|
369 __augment=false; |
|
370 //computing blocking flow with dfs |
|
371 typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap; |
|
372 DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F); |
|
373 typename MutableGraph::NodeMap<EdgeIt> pred(F); //invalid iterators |
|
374 typename MutableGraph::NodeMap<Number> free(F); |
|
375 |
|
376 dfs.pushAndSetReached(sF); |
|
377 while (!dfs.finished()) { |
|
378 ++dfs; |
|
379 if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { |
|
380 if (dfs.isBNodeNewlyReached()) { |
|
381 // std::cout << "OutEdgeIt: " << dfs; |
|
382 // std::cout << " aNode: " << F.aNode(dfs); |
|
383 // std::cout << " bNode: " << F.bNode(dfs) << " "; |
|
384 |
|
385 typename MutableGraph::NodeIt v=F.aNode(dfs); |
|
386 typename MutableGraph::NodeIt w=F.bNode(dfs); |
|
387 pred.set(w, dfs); |
|
388 if (F.valid(pred.get(v))) { |
|
389 free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); |
|
390 } else { |
|
391 free.set(w, residual_capacity.get(dfs)); |
|
392 } |
|
393 if (w==tF) { |
|
394 //std::cout << "AUGMENTATION"<<std::endl; |
|
395 __augment=true; |
|
396 _augment=true; |
|
397 break; |
|
398 } |
|
399 |
|
400 } else { |
|
401 F.erase(typename MutableGraph::OutEdgeIt(dfs)); |
|
402 } |
|
403 } |
|
404 } |
|
405 |
|
406 if (__augment) { |
|
407 typename MutableGraph::NodeIt n=tF; |
|
408 Number augment_value=free.get(tF); |
|
409 while (F.valid(pred.get(n))) { |
|
410 typename MutableGraph::EdgeIt e=pred.get(n); |
|
411 res_graph.augment(original_edge.get(e), augment_value); |
|
412 //original_edge.get(e).augment(augment_value); |
|
413 n=F.tail(e); |
|
414 if (residual_capacity.get(e)==augment_value) |
|
415 F.erase(e); |
|
416 else |
|
417 residual_capacity.set(e, residual_capacity.get(e)-augment_value); |
|
418 } |
|
419 } |
|
420 |
|
421 } |
|
422 |
|
423 return _augment; |
|
424 } |
|
425 bool augmentOnBlockingFlow2() { |
|
426 bool _augment=false; |
|
427 |
|
428 //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph; |
|
429 typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph; |
|
430 typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; |
|
431 typedef typename EAugGraph::EdgeIt EAugEdgeIt; |
|
432 |
|
433 EAugGraph res_graph(*G, *flow, *capacity); |
|
434 |
|
435 //std::cout << "meg jo1" << std::endl; |
|
436 |
|
437 //typedef typename EAugGraph::NodeMap<bool> ReachedMap; |
|
438 BfsIterator4< |
|
439 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, |
|
440 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt, |
|
441 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph); |
|
442 |
|
443 //std::cout << "meg jo2" << std::endl; |
|
444 |
|
445 bfs.pushAndSetReached(s); |
|
446 //std::cout << "meg jo2.5" << std::endl; |
|
447 |
|
448 //typename EAugGraph::NodeMap<int> dist(res_graph); //filled up with 0's |
|
449 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>:: |
|
450 NodeMap<int>& dist=res_graph.dist; |
|
451 //std::cout << "meg jo2.6" << std::endl; |
|
452 |
|
453 while ( !bfs.finished() ) { |
|
454 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; |
|
455 // EAugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); |
|
456 //if (res_graph.valid(e)) { |
|
457 // std::cout<<"a:"<<res_graph.tail(e)<<"b:"<<res_graph.head(e)<<std::endl; |
|
458 //} |
|
459 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
|
460 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
|
461 } |
|
462 |
|
463 ++bfs; |
|
464 } //computing distances from s in the residual graph |
|
465 |
|
466 |
|
467 //std::cout << "meg jo3" << std::endl; |
|
468 |
|
469 // typedef typename EAugGraph::EachNodeIt EAugEachNodeIt; |
|
470 // for(EAugEachNodeIt n=res_graph.template first<EAugEachNodeIt>(); res_graph.valid(n); res_graph.next(n)) { |
|
471 // std::cout << "dist: " << dist.get(n) << std::endl; |
|
472 // } |
|
473 |
|
474 bool __augment=true; |
|
475 |
|
476 while (__augment) { |
|
477 // std::cout << "new iteration"<< std::endl; |
|
478 |
|
479 __augment=false; |
|
480 //computing blocking flow with dfs |
|
481 typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap; |
|
482 DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap > |
|
483 dfs(res_graph); |
|
484 typename EAugGraph::NodeMap<EAugEdgeIt> pred(res_graph); //invalid iterators |
|
485 typename EAugGraph::NodeMap<Number> free(res_graph); |
|
486 |
|
487 dfs.pushAndSetReached(s); |
|
488 while (!dfs.finished()) { |
|
489 ++dfs; |
|
490 if (res_graph.valid(EAugOutEdgeIt(dfs))) { |
|
491 if (dfs.isBNodeNewlyReached()) { |
|
492 // std::cout << "OutEdgeIt: " << dfs; |
|
493 // std::cout << " aNode: " << res_graph.aNode(dfs); |
|
494 // std::cout << " res cap: " << EAugOutEdgeIt(dfs).free(); |
|
495 // std::cout << " bNode: " << res_graph.bNode(dfs) << " "; |
|
496 |
|
497 typename EAugGraph::NodeIt v=res_graph.aNode(dfs); |
|
498 typename EAugGraph::NodeIt w=res_graph.bNode(dfs); |
|
499 |
|
500 pred.set(w, EAugOutEdgeIt(dfs)); |
|
501 |
|
502 //std::cout << EAugOutEdgeIt(dfs).free() << std::endl; |
|
503 if (res_graph.valid(pred.get(v))) { |
|
504 free.set(w, std::min(free.get(v), res_graph.free(/*EAugOutEdgeIt*/(dfs)))); |
|
505 } else { |
|
506 free.set(w, res_graph.free(/*EAugOutEdgeIt*/(dfs))); |
|
507 } |
|
508 |
|
509 if (w==t) { |
|
510 // std::cout << "t is reached, AUGMENTATION"<<std::endl; |
|
511 __augment=true; |
|
512 _augment=true; |
|
513 break; |
|
514 } |
|
515 } else { |
|
516 // std::cout << "<<DELETE "; |
|
517 // std::cout << " aNode: " << res_graph.aNode(dfs); |
|
518 // std::cout << " res cap: " << EAugOutEdgeIt(dfs).free(); |
|
519 // std::cout << " bNode: " << res_graph.bNode(dfs) << " "; |
|
520 // std::cout << "DELETE>> "; |
|
521 |
|
522 res_graph.erase(dfs); |
|
523 } |
|
524 } |
|
525 |
|
526 } |
|
527 |
|
528 if (__augment) { |
|
529 typename EAugGraph::NodeIt n=t; |
|
530 Number augment_value=free.get(t); |
|
531 // std::cout << "av:" << augment_value << std::endl; |
|
532 while (res_graph.valid(pred.get(n))) { |
|
533 EAugEdgeIt e=pred.get(n); |
|
534 res_graph.augment(e, augment_value); |
|
535 //e.augment(augment_value); |
|
536 n=res_graph.tail(e); |
|
537 if (res_graph.free(e)==0) |
|
538 res_graph.erase(e); |
|
539 } |
|
540 } |
|
541 |
|
542 } |
|
543 |
|
544 return _augment; |
|
545 } |
|
546 void run() { |
|
547 //int num_of_augmentations=0; |
|
548 while (augmentOnShortestPath()) { |
|
549 //while (augmentOnBlockingFlow<MutableGraph>()) { |
|
550 //std::cout << ++num_of_augmentations << " "; |
|
551 //std::cout<<std::endl; |
|
552 } |
|
553 } |
|
554 template<typename MutableGraph> void run() { |
|
555 //int num_of_augmentations=0; |
|
556 //while (augmentOnShortestPath()) { |
|
557 while (augmentOnBlockingFlow<MutableGraph>()) { |
|
558 //std::cout << ++num_of_augmentations << " "; |
|
559 //std::cout<<std::endl; |
|
560 } |
|
561 } |
|
562 Number flowValue() { |
|
563 Number a=0; |
|
564 OutEdgeIt e; |
|
565 for(G->getFirst(e, s); G->valid(e); G->next(e)) { |
|
566 a+=flow->get(e); |
|
567 } |
|
568 return a; |
|
569 } |
|
570 }; |
|
571 |
|
572 |
|
573 // template <typename Graph, typename Number, typename FlowMap, typename CapacityMap> |
|
574 // class MaxFlow2 { |
|
575 // public: |
|
576 // typedef typename Graph::NodeIt NodeIt; |
|
577 // typedef typename Graph::EdgeIt EdgeIt; |
|
578 // typedef typename Graph::EachEdgeIt EachEdgeIt; |
|
579 // typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
580 // typedef typename Graph::InEdgeIt InEdgeIt; |
|
581 // private: |
|
582 // const Graph& G; |
|
583 // std::list<NodeIt>& S; |
|
584 // std::list<NodeIt>& T; |
|
585 // FlowMap& flow; |
|
586 // const CapacityMap& capacity; |
|
587 // typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph; |
|
588 // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; |
|
589 // typedef typename AugGraph::EdgeIt AugEdgeIt; |
|
590 // typename Graph::NodeMap<bool> SMap; |
|
591 // typename Graph::NodeMap<bool> TMap; |
|
592 // public: |
|
593 // MaxFlow2(const Graph& _G, std::list<NodeIt>& _S, std::list<NodeIt>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) { |
|
594 // for(typename std::list<NodeIt>::const_iterator i=S.begin(); |
|
595 // i!=S.end(); ++i) { |
|
596 // SMap.set(*i, true); |
|
597 // } |
|
598 // for (typename std::list<NodeIt>::const_iterator i=T.begin(); |
|
599 // i!=T.end(); ++i) { |
|
600 // TMap.set(*i, true); |
|
601 // } |
|
602 // } |
|
603 // bool augment() { |
|
604 // AugGraph res_graph(G, flow, capacity); |
|
605 // bool _augment=false; |
|
606 // NodeIt reached_t_node; |
|
607 |
|
608 // typedef typename AugGraph::NodeMap<bool> ReachedMap; |
|
609 // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph); |
|
610 // for(typename std::list<NodeIt>::const_iterator i=S.begin(); |
|
611 // i!=S.end(); ++i) { |
|
612 // res_bfs.pushAndSetReached(*i); |
|
613 // } |
|
614 // //res_bfs.pushAndSetReached(s); |
|
615 |
|
616 // typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph); |
|
617 // //filled up with invalid iterators |
|
618 |
|
619 // typename AugGraph::NodeMap<Number> free(res_graph); |
|
620 |
|
621 // //searching for augmenting path |
|
622 // while ( !res_bfs.finished() ) { |
|
623 // AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs); |
|
624 // if (e.valid() && res_bfs.isBNodeNewlyReached()) { |
|
625 // NodeIt v=res_graph.tail(e); |
|
626 // NodeIt w=res_graph.head(e); |
|
627 // pred.set(w, e); |
|
628 // if (pred.get(v).valid()) { |
|
629 // free.set(w, std::min(free.get(v), e.free())); |
|
630 // } else { |
|
631 // free.set(w, e.free()); |
|
632 // } |
|
633 // if (TMap.get(res_graph.head(e))) { |
|
634 // _augment=true; |
|
635 // reached_t_node=res_graph.head(e); |
|
636 // break; |
|
637 // } |
|
638 // } |
|
639 |
|
640 // ++res_bfs; |
|
641 // } //end of searching augmenting path |
|
642 |
|
643 // if (_augment) { |
|
644 // NodeIt n=reached_t_node; |
|
645 // Number augment_value=free.get(reached_t_node); |
|
646 // while (pred.get(n).valid()) { |
|
647 // AugEdgeIt e=pred.get(n); |
|
648 // e.augment(augment_value); |
|
649 // n=res_graph.tail(e); |
|
650 // } |
|
651 // } |
|
652 |
|
653 // return _augment; |
|
654 // } |
|
655 // void run() { |
|
656 // while (augment()) { } |
|
657 // } |
|
658 // Number flowValue() { |
|
659 // Number a=0; |
|
660 // for(typename std::list<NodeIt>::const_iterator i=S.begin(); |
|
661 // i!=S.end(); ++i) { |
|
662 // for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) { |
|
663 // a+=flow.get(e); |
|
664 // } |
|
665 // for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) { |
|
666 // a-=flow.get(e); |
|
667 // } |
|
668 // } |
|
669 // return a; |
|
670 // } |
|
671 // }; |
|
672 |
|
673 |
|
674 |
|
675 } // namespace hugo |
|
676 |
|
677 #endif //EDMONDS_KARP_HH |