nem hekkelunk.
1 #ifndef EDMONDS_KARP_HH
2 #define EDMONDS_KARP_HH
8 #include <bfs_iterator.hh>
9 //#include <time_measure.h>
13 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
16 typedef typename Graph::NodeIt NodeIt;
17 typedef typename Graph::EachNodeIt EachNodeIt;
19 typedef typename Graph::SymEdgeIt OldSymEdgeIt;
22 const CapacityMap& capacity;
24 ResGraph(const Graph& _G, FlowMap& _flow,
25 const CapacityMap& _capacity) :
26 G(_G), flow(_flow), capacity(_capacity) { }
31 friend class OutEdgeIt;
34 friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
36 const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;
40 //EdgeIt(const EdgeIt& e) : resG(e.resG), sym(e.sym) { }
42 if (resG->G.aNode(sym)==resG->G.tail(sym)) {
43 return (resG->capacity.get(sym)-resG->flow.get(sym));
45 return (resG->flow.get(sym));
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);
54 resG->flow.set(sym, resG->flow.get(sym)-a);
60 class OutEdgeIt : public EdgeIt {
61 friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
64 //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
66 OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) {
68 sym=resG->G.template first<OldSymEdgeIt>(v);
69 while( sym.valid() && !(free()>0) ) { ++sym; }
72 OutEdgeIt& operator++() {
74 while( sym.valid() && !(free()>0) ) { ++sym; }
79 void getFirst(OutEdgeIt& e, NodeIt v) const {
80 e=OutEdgeIt(*this, v);
82 void getFirst(EachNodeIt& v) const { G.getFirst(v); }
84 template< typename It >
91 template< typename It >
92 It first(NodeIt v) const {
98 NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); }
99 NodeIt head(EdgeIt e) const { return G.bNode(e.sym); }
101 NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
102 NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
104 int id(NodeIt v) const { return G.id(v); }
106 template <typename S>
108 typename Graph::NodeMap<S> node_map;
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]; }
121 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
124 typedef typename Graph::NodeIt NodeIt;
125 typedef typename Graph::EachNodeIt EachNodeIt;
127 //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
128 typedef typename Graph::OutEdgeIt OldOutEdgeIt;
129 typedef typename Graph::InEdgeIt OldInEdgeIt;
133 const CapacityMap& capacity;
135 ResGraph2(const Graph& _G, FlowMap& _flow,
136 const CapacityMap& _capacity) :
137 G(_G), flow(_flow), capacity(_capacity) { }
142 friend class OutEdgeIt;
145 friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
147 const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;
151 bool out_or_in; //1, iff out
153 EdgeIt() : out_or_in(1) { }
154 Number free() const {
156 return (resG->capacity.get(out)-resG->flow.get(out));
158 return (resG->flow.get(in));
162 return out_or_in && out.valid() || in.valid(); }
163 void augment(Number a) const {
165 resG->flow.set(out, resG->flow.get(out)+a);
167 resG->flow.set(in, resG->flow.get(in)-a);
172 class OutEdgeIt : public EdgeIt {
173 friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
177 OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) {
179 out=resG->G.template first<OldOutEdgeIt>(v);
180 while( out.valid() && !(free()>0) ) { ++out; }
183 in=resG->G.template first<OldInEdgeIt>(v);
184 while( in.valid() && !(free()>0) ) { ++in; }
188 OutEdgeIt& operator++() {
190 NodeIt v=resG->G.aNode(out);
192 while( out.valid() && !(free()>0) ) { ++out; }
195 in=resG->G.template first<OldInEdgeIt>(v);
196 while( in.valid() && !(free()>0) ) { ++in; }
200 while( in.valid() && !(free()>0) ) { ++in; }
206 void getFirst(OutEdgeIt& e, NodeIt v) const {
207 e=OutEdgeIt(*this, v);
209 void getFirst(EachNodeIt& v) const { G.getFirst(v); }
211 template< typename It >
218 template< typename It >
219 It first(NodeIt v) const {
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)); }
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)); }
235 int id(NodeIt v) const { return G.id(v); }
237 template <typename S>
239 typename Graph::NodeMap<S> node_map;
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); }
248 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
251 typedef typename Graph::NodeIt NodeIt;
252 typedef typename Graph::EachNodeIt EachNodeIt;
255 //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
256 typedef typename Graph::OutEdgeIt OldOutEdgeIt;
257 typedef typename Graph::InEdgeIt OldInEdgeIt;
260 const CapacityMap& capacity;
262 ResGraph3(const Graph& _G, FlowMap& _flow,
263 const CapacityMap& _capacity) :
264 G(_G), flow(_flow), capacity(_capacity) { }
269 friend class OutEdgeIt;
272 friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;
274 //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG;
277 const CapacityMap* capacity;
281 bool out_or_in; //1, iff out
283 EdgeIt() : out_or_in(1) { }
284 //EdgeIt(const EdgeIt& e) : G(e.G), flow(e.flow), capacity(e.capacity), out(e.out), in(e.in), out_or_in(e.out_or_in) { }
285 Number free() const {
287 return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
289 return (/*resG->*/flow->get(in));
293 return out_or_in && out.valid() || in.valid(); }
294 void augment(Number a) const {
296 /*resG->*/flow->set(out, /*resG->*/flow->get(out)+a);
298 /*resG->*/flow->set(in, /*resG->*/flow->get(in)-a);
305 std::cout << G->id(G->tail(out)) << "--"<< G->id(out) <<"->"<< G->id(G->head(out));
307 std::cout << "invalid";
312 std::cout << G->id(G->head(in)) << "<-"<< G->id(in) <<"--"<< G->id(G->tail(in));
314 std::cout << "invalid";
316 std::cout << std::endl;
320 class OutEdgeIt : public EdgeIt {
321 friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;
325 OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) {
329 //out=/*resG->*/G->template first<OldOutEdgeIt>(v);
331 while( out.valid() && !(free()>0) ) { ++out; }
334 //in=/*resG->*/G->template first<OldInEdgeIt>(v);
336 while( in.valid() && !(free()>0) ) { ++in; }
340 OutEdgeIt& operator++() {
342 NodeIt v=/*resG->*/G->aNode(out);
344 while( out.valid() && !(free()>0) ) { ++out; }
347 G->getFirst(in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
348 while( in.valid() && !(free()>0) ) { ++in; }
352 while( in.valid() && !(free()>0) ) { ++in; }
358 class EachEdgeIt : public EdgeIt {
359 typename Graph::EachNodeIt v;
362 //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { }
363 EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) {
369 if (v.valid()) G->getFirst(out, v); else out=OldOutEdgeIt();
370 while (out.valid() && !(free()>0) ) { ++out; }
371 while (v.valid() && !out.valid()) {
373 if (v.valid()) G->getFirst(out, v);
374 while (out.valid() && !(free()>0) ) { ++out; }
379 if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
380 while (in.valid() && !(free()>0) ) { ++in; }
381 while (v.valid() && !in.valid()) {
383 if (v.valid()) G->getFirst(in, v);
384 while (in.valid() && !(free()>0) ) { ++in; }
388 EachEdgeIt& operator++() {
391 while (out.valid() && !(free()>0) ) { ++out; }
392 while (v.valid() && !out.valid()) {
394 if (v.valid()) G->getFirst(out, v);
395 while (out.valid() && !(free()>0) ) { ++out; }
400 if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
401 while (in.valid() && !(free()>0) ) { ++in; }
402 while (v.valid() && !in.valid()) {
404 if (v.valid()) G->getFirst(in, v);
405 while (in.valid() && !(free()>0) ) { ++in; }
410 while (in.valid() && !(free()>0) ) { ++in; }
411 while (v.valid() && !in.valid()) {
413 if (v.valid()) G->getFirst(in, v);
414 while (in.valid() && !(free()>0) ) { ++in; }
421 void getFirst(OutEdgeIt& e, NodeIt v) const {
422 e=OutEdgeIt(G, v, flow, capacity);
424 void getFirst(EachEdgeIt& e) const {
425 e=EachEdgeIt(G, flow, capacity);
427 void getFirst(EachNodeIt& v) const { G.getFirst(v); }
429 template< typename It >
436 template< typename It >
437 It first(NodeIt v) const {
443 NodeIt tail(EdgeIt e) const {
444 return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
445 NodeIt head(EdgeIt e) const {
446 return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
448 NodeIt aNode(OutEdgeIt e) const {
449 return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
450 NodeIt bNode(OutEdgeIt e) const {
451 return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
453 int id(NodeIt v) const { return G.id(v); }
455 template <typename S>
457 typename Graph::NodeMap<S> node_map;
459 NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
460 NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
461 void set(NodeIt nit, S a) { node_map.set(nit, a); }
462 S get(NodeIt nit) const { return node_map.get(nit); }
468 template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
471 typedef typename Graph::NodeIt NodeIt;
472 typedef typename Graph::EdgeIt EdgeIt;
473 typedef typename Graph::EachEdgeIt EachEdgeIt;
474 typedef typename Graph::OutEdgeIt OutEdgeIt;
475 typedef typename Graph::InEdgeIt InEdgeIt;
482 const CapacityMap& capacity;
483 typedef ResGraph3<Graph, Number, FlowMap, CapacityMap > AugGraph;
484 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
485 typedef typename AugGraph::EdgeIt AugEdgeIt;
487 //AugGraph res_graph;
488 //typedef typename AugGraph::NodeMap<bool> ReachedMap;
489 //typename AugGraph::NodeMap<AugEdgeIt> pred;
490 //typename AugGraph::NodeMap<Number> free;
492 MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) :
493 G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) //,
494 //res_graph(G, flow, capacity), pred(res_graph), free(res_graph)
496 bool augmentOnShortestPath() {
497 AugGraph res_graph(G, flow, capacity);
500 typedef typename AugGraph::NodeMap<bool> ReachedMap;
501 BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
502 res_bfs.pushAndSetReached(s);
504 typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
505 //filled up with invalid iterators
506 //pred.set(s, AugEdgeIt());
508 typename AugGraph::NodeMap<Number> free(res_graph);
510 //searching for augmenting path
511 while ( !res_bfs.finished() ) {
512 AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
513 if (e.valid() && res_bfs.isBNodeNewlyReached()) {
514 NodeIt v=res_graph.tail(e);
515 NodeIt w=res_graph.head(e);
517 if (pred.get(v).valid()) {
518 free.set(w, std::min(free.get(v), e.free()));
520 free.set(w, e.free());
522 if (res_graph.head(e)==t) { _augment=true; break; }
526 } //end of searching augmenting path
530 Number augment_value=free.get(t);
531 while (pred.get(n).valid()) {
532 AugEdgeIt e=pred.get(n);
533 e.augment(augment_value);
540 template<typename MutableGraph> bool augmentOnBlockingFlow() {
543 AugGraph res_graph(G, flow, capacity);
545 typedef typename AugGraph::NodeMap<bool> ReachedMap;
546 BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
548 bfs.pushAndSetReached(s);
549 typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
550 while ( !bfs.finished() ) {
551 AugOutEdgeIt e=AugOutEdgeIt(bfs);
552 if (e.valid() && bfs.isBNodeNewlyReached()) {
553 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
557 } //computing distances from s in the residual graph
560 typename AugGraph::NodeMap<NodeIt> res_graph_to_F(res_graph);
561 for(typename AugGraph::EachNodeIt n=res_graph.template first<typename AugGraph::EachNodeIt>(); n.valid(); ++n) {
562 res_graph_to_F.set(n, F.addNode());
565 typename MutableGraph::NodeIt sF=res_graph_to_F.get(s);
566 typename MutableGraph::NodeIt tF=res_graph_to_F.get(t);
568 typename MutableGraph::EdgeMap<AugEdgeIt> original_edge(F);
569 typename MutableGraph::EdgeMap<Number> free_on_edge(F);
571 //Making F to the graph containing the edges of the residual graph
572 //which are in some shortest paths
573 for(typename AugGraph::EachEdgeIt e=res_graph.template first<typename AugGraph::EachEdgeIt>(); e.valid(); ++e) {
574 if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
575 typename MutableGraph::EdgeIt f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
576 original_edge.update();
577 original_edge.set(f, e);
578 free_on_edge.update();
579 free_on_edge.set(f, e.free());
587 //computing blocking flow with dfs
588 typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
589 DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
590 typename MutableGraph::NodeMap<EdgeIt> pred(F); //invalid iterators
591 typename MutableGraph::NodeMap<Number> free(F);
593 dfs.pushAndSetReached(sF);
594 while (!dfs.finished()) {
596 if (typename MutableGraph::OutEdgeIt(dfs).valid()) {
597 //std::cout << "OutEdgeIt: " << dfs;
598 //std::cout << " aNode: " << F.aNode(dfs);
599 //std::cout << " bNode: " << F.bNode(dfs) << " ";
601 typename MutableGraph::NodeIt v=F.aNode(dfs);
602 typename MutableGraph::NodeIt w=F.bNode(dfs);
604 if (pred.get(v).valid()) {
605 free.set(w, std::min(free.get(v), free_on_edge.get(dfs)));
607 free.set(w, free_on_edge.get(dfs)/*original_edge.get(dfs).free()*/);
610 //std::cout << "AUGMENTATION"<<std::endl;
616 //std::cout << "OutEdgeIt: " << "invalid";
617 //std::cout << " aNode: " << dfs.aNode();
618 //std::cout << " bNode: " << "invalid" << " ";
620 if (dfs.isBNodeNewlyReached()) {
621 //std::cout << "bNodeIsNewlyReached ";
623 //std::cout << "bNodeIsNotNewlyReached ";
624 if (typename MutableGraph::OutEdgeIt(dfs).valid()) {
625 //std::cout << "DELETE ";
626 F.erase(typename MutableGraph::OutEdgeIt(dfs));
629 //if (dfs.isANodeExamined()) {
630 //std::cout << "aNodeIsExamined ";
632 //std::cout << "aNodeIsNotExamined ";
634 //std::cout<<std::endl;
638 typename MutableGraph::NodeIt n=tF;
639 Number augment_value=free.get(tF);
640 while (pred.get(n).valid()) {
641 typename MutableGraph::EdgeIt e=pred.get(n);
642 original_edge.get(e).augment(augment_value);
653 //int num_of_augmentations=0;
654 while (augmentOnShortestPath()) {
655 //while (augmentOnBlockingFlow<MutableGraph>()) {
656 //std::cout << ++num_of_augmentations << " ";
657 //std::cout<<std::endl;
660 template<typename MutableGraph> void run() {
661 //int num_of_augmentations=0;
662 //while (augmentOnShortestPath()) {
663 while (augmentOnBlockingFlow<MutableGraph>()) {
664 //std::cout << ++num_of_augmentations << " ";
665 //std::cout<<std::endl;
670 for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) {
679 template <typename Graph>
680 class IteratorBoolNodeMap {
681 typedef typename Graph::NodeIt NodeIt;
682 typedef typename Graph::EachNodeIt EachNodeIt;
688 BoolItem() : value(false), prev(), next() {}
695 typename Graph::NodeMap<BoolItem> container;
697 typedef bool ValueType;
698 typedef NodeIt KeyType;
699 IteratorBoolNodeMap(const Graph& _G) : G(_G), container(G), first_true(NodeIt()) {
700 //for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {
701 //BoolItem b=container.get(e);
705 G.getFirst(first_false);
707 for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {
708 container[e].prev=e_prev;
709 if (e_prev.valid()) container[e_prev].next=e;
713 //NodeMap(const Graph& _G, T a) :
714 // G(_G), container(G.node_id, a) { }
716 void set(NodeIt nit, T a) { container[G.id(nit)]=a; }
717 T get(NodeIt nit) const { return container[G.id(nit)]; }
718 //void update() { container.resize(G.node_id); }
719 //void update(T a) { container.resize(G.node_id, a); }
724 template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
727 typedef typename Graph::NodeIt NodeIt;
728 typedef typename Graph::EdgeIt EdgeIt;
729 typedef typename Graph::EachEdgeIt EachEdgeIt;
730 typedef typename Graph::OutEdgeIt OutEdgeIt;
731 typedef typename Graph::InEdgeIt InEdgeIt;
734 std::list<NodeIt>& S;
735 std::list<NodeIt>& T;
737 const CapacityMap& capacity;
738 typedef ResGraph<Graph, Number, FlowMap, CapacityMap > AugGraph;
739 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
740 typedef typename AugGraph::EdgeIt AugEdgeIt;
741 typename Graph::NodeMap<bool> SMap;
742 typename Graph::NodeMap<bool> TMap;
744 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) {
745 for(typename std::list<NodeIt>::const_iterator i=S.begin();
749 for (typename std::list<NodeIt>::const_iterator i=T.begin();
755 AugGraph res_graph(G, flow, capacity);
757 NodeIt reached_t_node;
759 typedef typename AugGraph::NodeMap<bool> ReachedMap;
760 BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
761 for(typename std::list<NodeIt>::const_iterator i=S.begin();
763 res_bfs.pushAndSetReached(*i);
765 //res_bfs.pushAndSetReached(s);
767 typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
768 //filled up with invalid iterators
770 typename AugGraph::NodeMap<Number> free(res_graph);
772 //searching for augmenting path
773 while ( !res_bfs.finished() ) {
774 AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
775 if (e.valid() && res_bfs.isBNodeNewlyReached()) {
776 NodeIt v=res_graph.tail(e);
777 NodeIt w=res_graph.head(e);
779 if (pred.get(v).valid()) {
780 free.set(w, std::min(free.get(v), e.free()));
782 free.set(w, e.free());
784 if (TMap.get(res_graph.head(e))) {
786 reached_t_node=res_graph.head(e);
792 } //end of searching augmenting path
795 NodeIt n=reached_t_node;
796 Number augment_value=free.get(reached_t_node);
797 while (pred.get(n).valid()) {
798 AugEdgeIt e=pred.get(n);
799 e.augment(augment_value);
807 while (augment()) { }
811 for(typename std::list<NodeIt>::const_iterator i=S.begin();
813 for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
816 for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
828 #endif //EDMONDS_KARP_HH