24 class OutEdgeIt; |
26 class OutEdgeIt; |
25 friend class EdgeIt; |
27 friend class EdgeIt; |
26 friend class OutEdgeIt; |
28 friend class OutEdgeIt; |
27 |
29 |
28 class EdgeIt { |
30 class EdgeIt { |
29 friend class ResGraph<Graph, T, FlowMap, CapacityMap>; |
31 friend class ResGraph<Graph, Number, FlowMap, CapacityMap>; |
30 protected: |
32 protected: |
31 const ResGraph<Graph, T, FlowMap, CapacityMap>* resG; |
33 const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG; |
32 OldSymEdgeIt sym; |
34 OldSymEdgeIt sym; |
33 public: |
35 public: |
34 EdgeIt() { } |
36 EdgeIt() { } |
35 //EdgeIt(const EdgeIt& e) : resG(e.resG), sym(e.sym) { } |
37 //EdgeIt(const EdgeIt& e) : resG(e.resG), sym(e.sym) { } |
36 T free() const { |
38 Number free() const { |
37 if (resG->G.aNode(sym)==resG->G.tail(sym)) { |
39 if (resG->G.aNode(sym)==resG->G.tail(sym)) { |
38 return (resG->capacity.get(sym)-resG->flow.get(sym)); |
40 return (resG->capacity.get(sym)-resG->flow.get(sym)); |
39 } else { |
41 } else { |
40 return (resG->flow.get(sym)); |
42 return (resG->flow.get(sym)); |
41 } |
43 } |
42 } |
44 } |
43 bool valid() const { return sym.valid(); } |
45 bool valid() const { return sym.valid(); } |
44 void augment(T a) const { |
46 void augment(Number a) const { |
45 if (resG->G.aNode(sym)==resG->G.tail(sym)) { |
47 if (resG->G.aNode(sym)==resG->G.tail(sym)) { |
46 resG->flow.set(sym, resG->flow.get(sym)+a); |
48 resG->flow.set(sym, resG->flow.get(sym)+a); |
|
49 //resG->flow[sym]+=a; |
47 } else { |
50 } else { |
48 resG->flow.set(sym, resG->flow.get(sym)-a); |
51 resG->flow.set(sym, resG->flow.get(sym)-a); |
|
52 //resG->flow[sym]-=a; |
49 } |
53 } |
50 } |
54 } |
51 }; |
55 }; |
52 |
56 |
53 class OutEdgeIt : public EdgeIt { |
57 class OutEdgeIt : public EdgeIt { |
54 friend class ResGraph<Graph, T, FlowMap, CapacityMap>; |
58 friend class ResGraph<Graph, Number, FlowMap, CapacityMap>; |
55 public: |
59 public: |
56 OutEdgeIt() { } |
60 OutEdgeIt() { } |
57 //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; } |
61 //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; } |
58 private: |
62 private: |
59 OutEdgeIt(const ResGraph<Graph, T, FlowMap, CapacityMap>& _resG, NodeIt v) { |
63 OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) { |
60 resG=&_resG; |
64 resG=&_resG; |
61 sym=resG->G.template first<OldSymEdgeIt>(v); |
65 sym=resG->G.template first<OldSymEdgeIt>(v); |
62 while( sym.valid() && !(free()>0) ) { ++sym; } |
66 while( sym.valid() && !(free()>0) ) { ++sym; } |
63 } |
67 } |
64 public: |
68 public: |
65 OutEdgeIt& operator++() { |
69 OutEdgeIt& operator++() { |
66 ++sym; |
70 ++sym; |
67 while( sym.valid() && !(free()>0) ) { ++sym; } |
71 while( sym.valid() && !(free()>0) ) { ++sym; } |
|
72 return *this; |
|
73 } |
|
74 }; |
|
75 |
|
76 void getFirst(OutEdgeIt& e, NodeIt v) const { |
|
77 e=OutEdgeIt(*this, v); |
|
78 } |
|
79 void getFirst(EachNodeIt& v) const { G.getFirst(v); } |
|
80 |
|
81 template< typename It > |
|
82 It first() const { |
|
83 It e; |
|
84 getFirst(e); |
|
85 return e; |
|
86 } |
|
87 |
|
88 template< typename It > |
|
89 It first(NodeIt v) const { |
|
90 It e; |
|
91 getFirst(e, v); |
|
92 return e; |
|
93 } |
|
94 |
|
95 NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); } |
|
96 NodeIt head(EdgeIt e) const { return G.bNode(e.sym); } |
|
97 |
|
98 NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); } |
|
99 NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); } |
|
100 |
|
101 int id(NodeIt v) const { return G.id(v); } |
|
102 |
|
103 template <typename S> |
|
104 class NodeMap { |
|
105 typename Graph::NodeMap<S> node_map; |
|
106 public: |
|
107 NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { } |
|
108 NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { } |
|
109 void set(NodeIt nit, S a) { node_map.set(nit, a); } |
|
110 S get(NodeIt nit) const { return node_map.get(nit); } |
|
111 S& operator[](NodeIt nit) { return node_map[nit]; } |
|
112 const S& operator[](NodeIt nit) const { return node_map[nit]; } |
|
113 }; |
|
114 |
|
115 }; |
|
116 |
|
117 |
|
118 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap> |
|
119 class ResGraph2 { |
|
120 typedef typename Graph::NodeIt NodeIt; |
|
121 typedef typename Graph::EachNodeIt EachNodeIt; |
|
122 //typedef typename Graph::SymEdgeIt OldSymEdgeIt; |
|
123 typedef typename Graph::OutEdgeIt OldOutEdgeIt; |
|
124 typedef typename Graph::InEdgeIt OldInEdgeIt; |
|
125 |
|
126 const Graph& G; |
|
127 FlowMap& flow; |
|
128 const CapacityMap& capacity; |
|
129 public: |
|
130 ResGraph2(const Graph& _G, FlowMap& _flow, |
|
131 const CapacityMap& _capacity) : |
|
132 G(_G), flow(_flow), capacity(_capacity) { } |
|
133 |
|
134 class EdgeIt; |
|
135 class OutEdgeIt; |
|
136 friend class EdgeIt; |
|
137 friend class OutEdgeIt; |
|
138 |
|
139 class EdgeIt { |
|
140 friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>; |
|
141 protected: |
|
142 const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG; |
|
143 //OldSymEdgeIt sym; |
|
144 OldOutEdgeIt out; |
|
145 OldInEdgeIt in; |
|
146 bool out_or_in; //1, iff out |
|
147 public: |
|
148 EdgeIt() : out_or_in(1) { } |
|
149 Number free() const { |
|
150 if (out_or_in) { |
|
151 return (resG->capacity.get(out)-resG->flow.get(out)); |
|
152 } else { |
|
153 return (resG->flow.get(in)); |
|
154 } |
|
155 } |
|
156 bool valid() const { |
|
157 return out_or_in && out.valid() || in.valid(); } |
|
158 void augment(Number a) const { |
|
159 if (out_or_in) { |
|
160 resG->flow.set(out, resG->flow.get(out)+a); |
|
161 } else { |
|
162 resG->flow.set(in, resG->flow.get(in)-a); |
|
163 } |
|
164 } |
|
165 }; |
|
166 |
|
167 class OutEdgeIt : public EdgeIt { |
|
168 friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>; |
|
169 public: |
|
170 OutEdgeIt() { } |
|
171 private: |
|
172 OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) { |
|
173 resG=&_resG; |
|
174 out=resG->G.template first<OldOutEdgeIt>(v); |
|
175 while( out.valid() && !(free()>0) ) { ++out; } |
|
176 if (!out.valid()) { |
|
177 out_or_in=0; |
|
178 in=resG->G.template first<OldInEdgeIt>(v); |
|
179 while( in.valid() && !(free()>0) ) { ++in; } |
|
180 } |
|
181 } |
|
182 public: |
|
183 OutEdgeIt& operator++() { |
|
184 if (out_or_in) { |
|
185 NodeIt v=resG->G.aNode(out); |
|
186 ++out; |
|
187 while( out.valid() && !(free()>0) ) { ++out; } |
|
188 if (!out.valid()) { |
|
189 out_or_in=0; |
|
190 in=resG->G.template first<OldInEdgeIt>(v); |
|
191 while( in.valid() && !(free()>0) ) { ++in; } |
|
192 } |
|
193 } else { |
|
194 ++in; |
|
195 while( in.valid() && !(free()>0) ) { ++in; } |
|
196 } |
68 return *this; |
197 return *this; |
69 } |
198 } |
70 }; |
199 }; |
71 |
200 |
72 void getFirst(OutEdgeIt& e, NodeIt v) const { |
201 void getFirst(OutEdgeIt& e, NodeIt v) const { |
86 It e; |
215 It e; |
87 getFirst(e, v); |
216 getFirst(e, v); |
88 return e; |
217 return e; |
89 } |
218 } |
90 |
219 |
91 NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); } |
220 NodeIt tail(EdgeIt e) const { |
92 NodeIt head(EdgeIt e) const { return G.bNode(e.sym); } |
221 return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } |
93 |
222 NodeIt head(EdgeIt e) const { |
94 NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); } |
223 return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } |
95 NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); } |
224 |
|
225 NodeIt aNode(OutEdgeIt e) const { |
|
226 return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } |
|
227 NodeIt bNode(OutEdgeIt e) const { |
|
228 return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } |
96 |
229 |
97 int id(NodeIt v) const { return G.id(v); } |
230 int id(NodeIt v) const { return G.id(v); } |
98 |
231 |
99 template <typename S> |
232 template <typename S> |
100 class NodeMap { |
233 class NodeMap { |
101 typename Graph::NodeMap<S> node_map; |
234 typename Graph::NodeMap<S> node_map; |
102 public: |
235 public: |
103 NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G) : node_map(_G.G) { } |
236 NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { } |
104 NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { } |
237 NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { } |
105 void set(NodeIt nit, S a) { node_map.set(nit, a); } |
238 void set(NodeIt nit, S a) { node_map.set(nit, a); } |
106 S get(NodeIt nit) const { return node_map.get(nit); } |
239 S get(NodeIt nit) const { return node_map.get(nit); } |
107 }; |
240 }; |
108 |
|
109 }; |
241 }; |
110 |
242 |
111 template <typename Graph, typename T, typename FlowMap, typename CapacityMap> |
243 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap> |
|
244 class ResGraph3 { |
|
245 typedef typename Graph::NodeIt NodeIt; |
|
246 typedef typename Graph::EachNodeIt EachNodeIt; |
|
247 //typedef typename Graph::SymEdgeIt OldSymEdgeIt; |
|
248 typedef typename Graph::OutEdgeIt OldOutEdgeIt; |
|
249 typedef typename Graph::InEdgeIt OldInEdgeIt; |
|
250 |
|
251 const Graph& G; |
|
252 FlowMap& flow; |
|
253 const CapacityMap& capacity; |
|
254 public: |
|
255 ResGraph3(const Graph& _G, FlowMap& _flow, |
|
256 const CapacityMap& _capacity) : |
|
257 G(_G), flow(_flow), capacity(_capacity) { } |
|
258 |
|
259 class EdgeIt; |
|
260 class OutEdgeIt; |
|
261 friend class EdgeIt; |
|
262 friend class OutEdgeIt; |
|
263 |
|
264 class EdgeIt { |
|
265 friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>; |
|
266 protected: |
|
267 //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG; |
|
268 const Graph* G; |
|
269 FlowMap* flow; |
|
270 const CapacityMap* capacity; |
|
271 //OldSymEdgeIt sym; |
|
272 OldOutEdgeIt out; |
|
273 OldInEdgeIt in; |
|
274 bool out_or_in; //1, iff out |
|
275 public: |
|
276 EdgeIt() : out_or_in(1) { } |
|
277 Number free() const { |
|
278 if (out_or_in) { |
|
279 return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out)); |
|
280 } else { |
|
281 return (/*resG->*/flow->get(in)); |
|
282 } |
|
283 } |
|
284 bool valid() const { |
|
285 return out_or_in && out.valid() || in.valid(); } |
|
286 void augment(Number a) const { |
|
287 if (out_or_in) { |
|
288 /*resG->*/flow->set(out, /*resG->*/flow->get(out)+a); |
|
289 } else { |
|
290 /*resG->*/flow->set(in, /*resG->*/flow->get(in)-a); |
|
291 } |
|
292 } |
|
293 }; |
|
294 |
|
295 class OutEdgeIt : public EdgeIt { |
|
296 friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>; |
|
297 public: |
|
298 OutEdgeIt() { } |
|
299 private: |
|
300 OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) { |
|
301 G=&_G; |
|
302 flow=&_flow; |
|
303 capacity=&_capacity; |
|
304 out=/*resG->*/G->template first<OldOutEdgeIt>(v); |
|
305 while( out.valid() && !(free()>0) ) { ++out; } |
|
306 if (!out.valid()) { |
|
307 out_or_in=0; |
|
308 in=/*resG->*/G->template first<OldInEdgeIt>(v); |
|
309 while( in.valid() && !(free()>0) ) { ++in; } |
|
310 } |
|
311 } |
|
312 public: |
|
313 OutEdgeIt& operator++() { |
|
314 if (out_or_in) { |
|
315 NodeIt v=/*resG->*/G->aNode(out); |
|
316 ++out; |
|
317 while( out.valid() && !(free()>0) ) { ++out; } |
|
318 if (!out.valid()) { |
|
319 out_or_in=0; |
|
320 in=/*resG->*/G->template first<OldInEdgeIt>(v); |
|
321 while( in.valid() && !(free()>0) ) { ++in; } |
|
322 } |
|
323 } else { |
|
324 ++in; |
|
325 while( in.valid() && !(free()>0) ) { ++in; } |
|
326 } |
|
327 return *this; |
|
328 } |
|
329 }; |
|
330 |
|
331 void getFirst(OutEdgeIt& e, NodeIt v) const { |
|
332 e=OutEdgeIt(G, v, flow, capacity); |
|
333 } |
|
334 void getFirst(EachNodeIt& v) const { G.getFirst(v); } |
|
335 |
|
336 template< typename It > |
|
337 It first() const { |
|
338 It e; |
|
339 getFirst(e); |
|
340 return e; |
|
341 } |
|
342 |
|
343 template< typename It > |
|
344 It first(NodeIt v) const { |
|
345 It e; |
|
346 getFirst(e, v); |
|
347 return e; |
|
348 } |
|
349 |
|
350 NodeIt tail(EdgeIt e) const { |
|
351 return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } |
|
352 NodeIt head(EdgeIt e) const { |
|
353 return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } |
|
354 |
|
355 NodeIt aNode(OutEdgeIt e) const { |
|
356 return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } |
|
357 NodeIt bNode(OutEdgeIt e) const { |
|
358 return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } |
|
359 |
|
360 int id(NodeIt v) const { return G.id(v); } |
|
361 |
|
362 template <typename S> |
|
363 class NodeMap { |
|
364 typename Graph::NodeMap<S> node_map; |
|
365 public: |
|
366 NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { } |
|
367 NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { } |
|
368 void set(NodeIt nit, S a) { node_map.set(nit, a); } |
|
369 S get(NodeIt nit) const { return node_map.get(nit); } |
|
370 }; |
|
371 |
|
372 }; |
|
373 |
|
374 |
|
375 template <typename Graph, typename Number, typename FlowMap, typename CapacityMap> |
112 class MaxFlow { |
376 class MaxFlow { |
113 typedef typename Graph::NodeIt NodeIt; |
377 typedef typename Graph::NodeIt NodeIt; |
114 typedef typename Graph::EdgeIt EdgeIt; |
378 typedef typename Graph::EdgeIt EdgeIt; |
115 typedef typename Graph::EachEdgeIt EachEdgeIt; |
379 typedef typename Graph::EachEdgeIt EachEdgeIt; |
116 typedef typename Graph::OutEdgeIt OutEdgeIt; |
380 typedef typename Graph::OutEdgeIt OutEdgeIt; |
118 const Graph& G; |
382 const Graph& G; |
119 NodeIt s; |
383 NodeIt s; |
120 NodeIt t; |
384 NodeIt t; |
121 FlowMap& flow; |
385 FlowMap& flow; |
122 const CapacityMap& capacity; |
386 const CapacityMap& capacity; |
123 typedef ResGraph<Graph, T, FlowMap, CapacityMap > AugGraph; |
387 typedef ResGraph3<Graph, Number, FlowMap, CapacityMap > AugGraph; |
124 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; |
388 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; |
125 typedef typename AugGraph::EdgeIt AugEdgeIt; |
389 typedef typename AugGraph::EdgeIt AugEdgeIt; |
|
390 |
|
391 //AugGraph res_graph; |
|
392 //typedef typename AugGraph::NodeMap<bool> ReachedMap; |
|
393 //typename AugGraph::NodeMap<AugEdgeIt> pred; |
|
394 //typename AugGraph::NodeMap<int> free; |
126 public: |
395 public: |
127 MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) { } |
396 MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : |
|
397 G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) //, |
|
398 //res_graph(G, flow, capacity), pred(res_graph), free(res_graph) |
|
399 { } |
128 bool augment() { |
400 bool augment() { |
129 AugGraph res_graph(G, flow, capacity); |
401 AugGraph res_graph(G, flow, capacity); |
130 bool _augment=false; |
402 bool _augment=false; |
131 |
403 |
132 typedef typename AugGraph::NodeMap<bool> ReachedMap; |
404 typedef typename AugGraph::NodeMap<bool> ReachedMap; |
133 BfsIterator2< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph); |
405 BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph); |
134 res_bfs.pushAndSetReached(s); |
406 res_bfs.pushAndSetReached(s); |
135 |
407 |
136 typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph); |
408 typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph); |
137 //filled with invalid iterators |
409 //filled up with invalid iterators |
|
410 //pred.set(s, AugEdgeIt()); |
138 |
411 |
139 typename AugGraph::NodeMap<int> free(res_graph); |
412 typename AugGraph::NodeMap<int> free(res_graph); |
140 |
413 |
141 //searching for augmenting path |
414 //searching for augmenting path |
142 while ( !res_bfs.finished() ) { |
415 while ( !res_bfs.finished() ) { |
169 return _augment; |
442 return _augment; |
170 } |
443 } |
171 void run() { |
444 void run() { |
172 while (augment()) { } |
445 while (augment()) { } |
173 } |
446 } |
174 T flowValue() { |
447 Number flowValue() { |
175 T a=0; |
448 Number a=0; |
176 for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) { |
449 for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) { |
177 a+=flow.get(i); |
450 a+=flow.get(i); |
178 } |
451 } |
179 return a; |
452 return a; |
180 } |
453 } |
181 }; |
454 }; |
182 |
455 |
|
456 |
|
457 /* |
|
458 template <typename Graph> |
|
459 class IteratorBoolNodeMap { |
|
460 typedef typename Graph::NodeIt NodeIt; |
|
461 typedef typename Graph::EachNodeIt EachNodeIt; |
|
462 class BoolItem { |
|
463 public: |
|
464 bool value; |
|
465 NodeIt prev; |
|
466 NodeIt next; |
|
467 BoolItem() : value(false), prev(), next() {} |
|
468 }; |
|
469 NodeIt first_true; |
|
470 //NodeIt last_true; |
|
471 NodeIt first_false; |
|
472 //NodeIt last_false; |
|
473 const Graph& G; |
|
474 typename Graph::NodeMap<BoolItem> container; |
|
475 public: |
|
476 typedef bool ValueType; |
|
477 typedef NodeIt KeyType; |
|
478 IteratorBoolNodeMap(const Graph& _G) : G(_G), container(G), first_true(NodeIt()) { |
|
479 //for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) { |
|
480 //BoolItem b=container.get(e); |
|
481 //b.me=e; |
|
482 //container.set(b); |
|
483 //} |
|
484 G.getFirst(first_false); |
|
485 NodeIt e_prev; |
|
486 for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) { |
|
487 container[e].prev=e_prev; |
|
488 if (e_prev.valid()) container[e_prev].next=e; |
|
489 e_prev=e; |
|
490 } |
|
491 } |
|
492 //NodeMap(const Graph& _G, T a) : |
|
493 // G(_G), container(G.node_id, a) { } |
|
494 //FIXME |
|
495 void set(NodeIt nit, T a) { container[G.id(nit)]=a; } |
|
496 T get(NodeIt nit) const { return container[G.id(nit)]; } |
|
497 //void resize() { container.resize(G.node_id); } |
|
498 //void resize(T a) { container.resize(G.node_id, a); } |
|
499 }; |
|
500 */ |
|
501 |
|
502 |
|
503 template <typename Graph, typename Number, typename FlowMap, typename CapacityMap> |
|
504 class MaxFlow2 { |
|
505 typedef typename Graph::NodeIt NodeIt; |
|
506 typedef typename Graph::EdgeIt EdgeIt; |
|
507 typedef typename Graph::EachEdgeIt EachEdgeIt; |
|
508 typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
509 typedef typename Graph::InEdgeIt InEdgeIt; |
|
510 const Graph& G; |
|
511 std::list<NodeIt>& S; |
|
512 std::list<NodeIt>& T; |
|
513 FlowMap& flow; |
|
514 const CapacityMap& capacity; |
|
515 typedef ResGraph<Graph, Number, FlowMap, CapacityMap > AugGraph; |
|
516 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; |
|
517 typedef typename AugGraph::EdgeIt AugEdgeIt; |
|
518 typename Graph::NodeMap<bool> SMap; |
|
519 typename Graph::NodeMap<bool> TMap; |
|
520 public: |
|
521 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) { |
|
522 for(typename std::list<NodeIt>::const_iterator i=S.begin(); |
|
523 i!=S.end(); ++i) { |
|
524 SMap.set(*i, true); |
|
525 } |
|
526 for (typename std::list<NodeIt>::const_iterator i=T.begin(); |
|
527 i!=T.end(); ++i) { |
|
528 TMap.set(*i, true); |
|
529 } |
|
530 } |
|
531 bool augment() { |
|
532 AugGraph res_graph(G, flow, capacity); |
|
533 bool _augment=false; |
|
534 NodeIt reached_t_node; |
|
535 |
|
536 typedef typename AugGraph::NodeMap<bool> ReachedMap; |
|
537 BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph); |
|
538 for(typename std::list<NodeIt>::const_iterator i=S.begin(); |
|
539 i!=S.end(); ++i) { |
|
540 res_bfs.pushAndSetReached(*i); |
|
541 } |
|
542 //res_bfs.pushAndSetReached(s); |
|
543 |
|
544 typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph); |
|
545 //filled up with invalid iterators |
|
546 |
|
547 typename AugGraph::NodeMap<int> free(res_graph); |
|
548 |
|
549 //searching for augmenting path |
|
550 while ( !res_bfs.finished() ) { |
|
551 AugOutEdgeIt e=AugOutEdgeIt(res_bfs); |
|
552 if (e.valid() && res_bfs.isBNodeNewlyReached()) { |
|
553 NodeIt v=res_graph.tail(e); |
|
554 NodeIt w=res_graph.head(e); |
|
555 pred.set(w, e); |
|
556 if (pred.get(v).valid()) { |
|
557 free.set(w, std::min(free.get(v), e.free())); |
|
558 } else { |
|
559 free.set(w, e.free()); |
|
560 } |
|
561 if (TMap.get(res_graph.head(e))) { |
|
562 _augment=true; |
|
563 reached_t_node=res_graph.head(e); |
|
564 break; |
|
565 } |
|
566 } |
|
567 |
|
568 ++res_bfs; |
|
569 } //end of searching augmenting path |
|
570 |
|
571 if (_augment) { |
|
572 NodeIt n=reached_t_node; |
|
573 Number augment_value=free.get(reached_t_node); |
|
574 while (pred.get(n).valid()) { |
|
575 AugEdgeIt e=pred.get(n); |
|
576 e.augment(augment_value); |
|
577 n=res_graph.tail(e); |
|
578 } |
|
579 } |
|
580 |
|
581 return _augment; |
|
582 } |
|
583 void run() { |
|
584 while (augment()) { } |
|
585 } |
|
586 Number flowValue() { |
|
587 Number a=0; |
|
588 for(typename std::list<NodeIt>::const_iterator i=S.begin(); |
|
589 i!=S.end(); ++i) { |
|
590 for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) { |
|
591 a+=flow.get(e); |
|
592 } |
|
593 for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) { |
|
594 a-=flow.get(e); |
|
595 } |
|
596 } |
|
597 return a; |
|
598 } |
|
599 }; |
|
600 |
|
601 |
|
602 |
183 } // namespace marci |
603 } // namespace marci |
184 |
604 |
185 #endif //EDMONDS_KARP_HH |
605 #endif //EDMONDS_KARP_HH |