38 OldSymEdgeIt sym; |
38 OldSymEdgeIt sym; |
39 public: |
39 public: |
40 Edge() { } |
40 Edge() { } |
41 //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { } |
41 //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { } |
42 Number free() const { |
42 Number free() const { |
43 if (resG->G.aNode(sym)==resG->G.tail(sym)) { |
43 if (resG->G.aNode(sym)==resG->G.source(sym)) { |
44 return (resG->capacity.get(sym)-resG->flow.get(sym)); |
44 return (resG->capacity.get(sym)-resG->flow.get(sym)); |
45 } else { |
45 } else { |
46 return (resG->flow.get(sym)); |
46 return (resG->flow.get(sym)); |
47 } |
47 } |
48 } |
48 } |
49 bool valid() const { return sym.valid(); } |
49 bool valid() const { return sym.valid(); } |
50 void augment(Number a) const { |
50 void augment(Number a) const { |
51 if (resG->G.aNode(sym)==resG->G.tail(sym)) { |
51 if (resG->G.aNode(sym)==resG->G.source(sym)) { |
52 resG->flow.set(sym, resG->flow.get(sym)+a); |
52 resG->flow.set(sym, resG->flow.get(sym)+a); |
53 //resG->flow[sym]+=a; |
53 //resG->flow[sym]+=a; |
54 } else { |
54 } else { |
55 resG->flow.set(sym, resG->flow.get(sym)-a); |
55 resG->flow.set(sym, resG->flow.get(sym)-a); |
56 //resG->flow[sym]-=a; |
56 //resG->flow[sym]-=a; |
94 It e; |
94 It e; |
95 /*getF*/first(e, v); |
95 /*getF*/first(e, v); |
96 return e; |
96 return e; |
97 } |
97 } |
98 |
98 |
99 Node tail(Edge e) const { return G.aNode(e.sym); } |
99 Node source(Edge e) const { return G.aNode(e.sym); } |
100 Node head(Edge e) const { return G.bNode(e.sym); } |
100 Node target(Edge e) const { return G.bNode(e.sym); } |
101 |
101 |
102 Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); } |
102 Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); } |
103 Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); } |
103 Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); } |
104 |
104 |
105 int id(Node v) const { return G.id(v); } |
105 int id(Node v) const { return G.id(v); } |
221 It e; |
221 It e; |
222 /*getF*/first(e, v); |
222 /*getF*/first(e, v); |
223 return e; |
223 return e; |
224 } |
224 } |
225 |
225 |
226 Node tail(Edge e) const { |
226 Node source(Edge e) const { |
227 return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } |
227 return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } |
228 Node head(Edge e) const { |
228 Node target(Edge e) const { |
229 return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } |
229 return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } |
230 |
230 |
231 Node aNode(OutEdgeIt e) const { |
231 Node aNode(OutEdgeIt e) const { |
232 return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } |
232 return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } |
233 Node bNode(OutEdgeIt e) const { |
233 Node bNode(OutEdgeIt e) const { |
285 |
285 |
286 //searching for augmenting path |
286 //searching for augmenting path |
287 while ( !bfs.finished() ) { |
287 while ( !bfs.finished() ) { |
288 ResGWOutEdgeIt e=bfs; |
288 ResGWOutEdgeIt e=bfs; |
289 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
289 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
290 Node v=res_graph.tail(e); |
290 Node v=res_graph.source(e); |
291 Node w=res_graph.head(e); |
291 Node w=res_graph.target(e); |
292 pred.set(w, e); |
292 pred.set(w, e); |
293 if (res_graph.valid(pred.get(v))) { |
293 if (res_graph.valid(pred.get(v))) { |
294 free.set(w, std::min(free.get(v), res_graph.resCap(e))); |
294 free.set(w, std::min(free.get(v), res_graph.resCap(e))); |
295 } else { |
295 } else { |
296 free.set(w, res_graph.resCap(e)); |
296 free.set(w, res_graph.resCap(e)); |
297 } |
297 } |
298 if (res_graph.head(e)==t) { _augment=true; break; } |
298 if (res_graph.target(e)==t) { _augment=true; break; } |
299 } |
299 } |
300 |
300 |
301 ++bfs; |
301 ++bfs; |
302 } //end of searching augmenting path |
302 } //end of searching augmenting path |
303 |
303 |
322 public: |
322 public: |
323 DistanceMap(MapGraphWrapper& _gw) : gw(_gw), dist(_gw, _gw.nodeNum()) { } |
323 DistanceMap(MapGraphWrapper& _gw) : gw(_gw), dist(_gw, _gw.nodeNum()) { } |
324 void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; } |
324 void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; } |
325 int get(const typename MapGraphWrapper::Node& n) const { return dist[n]; } |
325 int get(const typename MapGraphWrapper::Node& n) const { return dist[n]; } |
326 bool get(const typename MapGraphWrapper::Edge& e) const { |
326 bool get(const typename MapGraphWrapper::Edge& e) const { |
327 return (dist.get(gw.tail(e))<dist.get(gw.head(e))); |
327 return (dist.get(gw.source(e))<dist.get(gw.target(e))); |
328 } |
328 } |
329 }; |
329 }; |
330 |
330 |
331 template<typename MutableGraph> bool augmentOnBlockingFlow() { |
331 template<typename MutableGraph> bool augmentOnBlockingFlow() { |
332 typedef MutableGraph MG; |
332 typedef MutableGraph MG; |
341 //typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's |
341 //typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's |
342 DistanceMap<ResGW> dist(res_graph); |
342 DistanceMap<ResGW> dist(res_graph); |
343 while ( !bfs.finished() ) { |
343 while ( !bfs.finished() ) { |
344 ResGWOutEdgeIt e=bfs; |
344 ResGWOutEdgeIt e=bfs; |
345 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
345 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
346 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
346 dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); |
347 } |
347 } |
348 ++bfs; |
348 ++bfs; |
349 } //computing distances from s in the residual graph |
349 } //computing distances from s in the residual graph |
350 |
350 |
351 MG F; |
351 MG F; |
367 //Making F to the graph containing the edges of the residual graph |
367 //Making F to the graph containing the edges of the residual graph |
368 //which are in some shortest paths |
368 //which are in some shortest paths |
369 { |
369 { |
370 typename FilterResGW::EdgeIt e; |
370 typename FilterResGW::EdgeIt e; |
371 for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) { |
371 for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) { |
372 //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { |
372 //if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) { |
373 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
373 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); |
374 original_edge.update(); |
374 original_edge.update(); |
375 original_edge.set(f, e); |
375 original_edge.set(f, e); |
376 residual_capacity.update(); |
376 residual_capacity.update(); |
377 residual_capacity.set(f, res_graph.resCap(e)); |
377 residual_capacity.set(f, res_graph.resCap(e)); |
378 //} |
378 //} |
421 typename MG::Node n=tF; |
421 typename MG::Node n=tF; |
422 Number augment_value=free.get(tF); |
422 Number augment_value=free.get(tF); |
423 while (F.valid(pred.get(n))) { |
423 while (F.valid(pred.get(n))) { |
424 typename MG::Edge e=pred.get(n); |
424 typename MG::Edge e=pred.get(n); |
425 res_graph.augment(original_edge.get(e), augment_value); |
425 res_graph.augment(original_edge.get(e), augment_value); |
426 n=F.tail(e); |
426 n=F.source(e); |
427 if (residual_capacity.get(e)==augment_value) |
427 if (residual_capacity.get(e)==augment_value) |
428 F.erase(e); |
428 F.erase(e); |
429 else |
429 else |
430 residual_capacity.set(e, residual_capacity.get(e)-augment_value); |
430 residual_capacity.set(e, residual_capacity.get(e)-augment_value); |
431 } |
431 } |
466 |
466 |
467 while ( !bfs.finished() ) { |
467 while ( !bfs.finished() ) { |
468 ResGWOutEdgeIt e=bfs; |
468 ResGWOutEdgeIt e=bfs; |
469 if (res_graph.valid(e)) { |
469 if (res_graph.valid(e)) { |
470 if (bfs.isBNodeNewlyReached()) { |
470 if (bfs.isBNodeNewlyReached()) { |
471 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
471 dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); |
472 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
472 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); |
473 original_edge.update(); |
473 original_edge.update(); |
474 original_edge.set(f, e); |
474 original_edge.set(f, e); |
475 residual_capacity.update(); |
475 residual_capacity.update(); |
476 residual_capacity.set(f, res_graph.resCap(e)); |
476 residual_capacity.set(f, res_graph.resCap(e)); |
477 } else { |
477 } else { |
478 if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) { |
478 if (dist.get(res_graph.target(e))==(dist.get(res_graph.source(e))+1)) { |
479 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
479 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); |
480 original_edge.update(); |
480 original_edge.update(); |
481 original_edge.set(f, e); |
481 original_edge.set(f, e); |
482 residual_capacity.update(); |
482 residual_capacity.update(); |
483 residual_capacity.set(f, res_graph.resCap(e)); |
483 residual_capacity.set(f, res_graph.resCap(e)); |
484 } |
484 } |
529 typename MG::Node n=tF; |
529 typename MG::Node n=tF; |
530 Number augment_value=free.get(tF); |
530 Number augment_value=free.get(tF); |
531 while (F.valid(pred.get(n))) { |
531 while (F.valid(pred.get(n))) { |
532 typename MG::Edge e=pred.get(n); |
532 typename MG::Edge e=pred.get(n); |
533 res_graph.augment(original_edge.get(e), augment_value); |
533 res_graph.augment(original_edge.get(e), augment_value); |
534 n=F.tail(e); |
534 n=F.source(e); |
535 if (residual_capacity.get(e)==augment_value) |
535 if (residual_capacity.get(e)==augment_value) |
536 F.erase(e); |
536 F.erase(e); |
537 else |
537 else |
538 residual_capacity.set(e, residual_capacity.get(e)-augment_value); |
538 residual_capacity.set(e, residual_capacity.get(e)-augment_value); |
539 } |
539 } |
555 bfs.pushAndSetReached(s); |
555 bfs.pushAndSetReached(s); |
556 DistanceMap<ResGW> dist(res_graph); |
556 DistanceMap<ResGW> dist(res_graph); |
557 while ( !bfs.finished() ) { |
557 while ( !bfs.finished() ) { |
558 ResGWOutEdgeIt e=bfs; |
558 ResGWOutEdgeIt e=bfs; |
559 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
559 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
560 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
560 dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); |
561 } |
561 } |
562 ++bfs; |
562 ++bfs; |
563 } //computing distances from s in the residual graph |
563 } //computing distances from s in the residual graph |
564 |
564 |
565 //Subgraph containing the edges on some shortest paths |
565 //Subgraph containing the edges on some shortest paths |
631 typename ErasingResGW::Node n=t; |
631 typename ErasingResGW::Node n=t; |
632 Number augment_value=free.get(n); |
632 Number augment_value=free.get(n); |
633 while (erasing_res_graph.valid(pred.get(n))) { |
633 while (erasing_res_graph.valid(pred.get(n))) { |
634 typename ErasingResGW::OutEdgeIt e=pred.get(n); |
634 typename ErasingResGW::OutEdgeIt e=pred.get(n); |
635 res_graph.augment(e, augment_value); |
635 res_graph.augment(e, augment_value); |
636 n=erasing_res_graph.tail(e); |
636 n=erasing_res_graph.source(e); |
637 if (res_graph.resCap(e)==0) |
637 if (res_graph.resCap(e)==0) |
638 erasing_res_graph.erase(e); |
638 erasing_res_graph.erase(e); |
639 } |
639 } |
640 } |
640 } |
641 |
641 |
666 // NodeMap<int>& dist=res_graph.dist; |
666 // NodeMap<int>& dist=res_graph.dist; |
667 |
667 |
668 // while ( !bfs.finished() ) { |
668 // while ( !bfs.finished() ) { |
669 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; |
669 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; |
670 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
670 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
671 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
671 // dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); |
672 // } |
672 // } |
673 // ++bfs; |
673 // ++bfs; |
674 // } //computing distances from s in the residual graph |
674 // } //computing distances from s in the residual graph |
675 |
675 |
676 // bool __augment=true; |
676 // bool __augment=true; |
720 // typename EAugGraph::Node n=t; |
720 // typename EAugGraph::Node n=t; |
721 // Number augment_value=free.get(t); |
721 // Number augment_value=free.get(t); |
722 // while (res_graph.valid(pred.get(n))) { |
722 // while (res_graph.valid(pred.get(n))) { |
723 // EAugEdge e=pred.get(n); |
723 // EAugEdge e=pred.get(n); |
724 // res_graph.augment(e, augment_value); |
724 // res_graph.augment(e, augment_value); |
725 // n=res_graph.tail(e); |
725 // n=res_graph.source(e); |
726 // if (res_graph.free(e)==0) |
726 // if (res_graph.free(e)==0) |
727 // res_graph.erase(e); |
727 // res_graph.erase(e); |
728 // } |
728 // } |
729 // } |
729 // } |
730 |
730 |
815 // Node n; |
815 // Node n; |
816 // //searching for augmenting path |
816 // //searching for augmenting path |
817 // while ( !bfs.finished() ) { |
817 // while ( !bfs.finished() ) { |
818 // AugOutEdgeIt e=bfs; |
818 // AugOutEdgeIt e=bfs; |
819 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
819 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
820 // Node v=res_graph.tail(e); |
820 // Node v=res_graph.source(e); |
821 // Node w=res_graph.head(e); |
821 // Node w=res_graph.target(e); |
822 // pred.set(w, e); |
822 // pred.set(w, e); |
823 // if (res_graph.valid(pred.get(v))) { |
823 // if (res_graph.valid(pred.get(v))) { |
824 // free.set(w, std::min(free.get(v), res_graph.free(e))); |
824 // free.set(w, std::min(free.get(v), res_graph.free(e))); |
825 // } else { |
825 // } else { |
826 // free.set(w, res_graph.free(e)); |
826 // free.set(w, res_graph.free(e)); |
827 // } |
827 // } |
828 // n=res_graph.head(e); |
828 // n=res_graph.target(e); |
829 // if (T->get(n) && (used.get(n)<1) ) { |
829 // if (T->get(n) && (used.get(n)<1) ) { |
830 // //Number u=0; |
830 // //Number u=0; |
831 // //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f)) |
831 // //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f)) |
832 // //u+=flow->get(f); |
832 // //u+=flow->get(f); |
833 // //if (u<1) { |
833 // //if (u<1) { |
845 // used.set(n, 1); //mind2 vegen jav |
845 // used.set(n, 1); //mind2 vegen jav |
846 // Number augment_value=free.get(n); |
846 // Number augment_value=free.get(n); |
847 // while (res_graph.valid(pred.get(n))) { |
847 // while (res_graph.valid(pred.get(n))) { |
848 // AugEdge e=pred.get(n); |
848 // AugEdge e=pred.get(n); |
849 // res_graph.augment(e, augment_value); |
849 // res_graph.augment(e, augment_value); |
850 // n=res_graph.tail(e); |
850 // n=res_graph.source(e); |
851 // } |
851 // } |
852 // used.set(n, 1); //mind2 vegen jav |
852 // used.set(n, 1); //mind2 vegen jav |
853 // } |
853 // } |
854 |
854 |
855 // return _augment; |
855 // return _augment; |
886 // // //bfs.pushAndSetReached(s); |
886 // // //bfs.pushAndSetReached(s); |
887 // // typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's |
887 // // typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's |
888 // // while ( !bfs.finished() ) { |
888 // // while ( !bfs.finished() ) { |
889 // // AugOutEdgeIt e=bfs; |
889 // // AugOutEdgeIt e=bfs; |
890 // // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
890 // // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
891 // // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
891 // // dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); |
892 // // } |
892 // // } |
893 |
893 |
894 // // ++bfs; |
894 // // ++bfs; |
895 // // } //computing distances from s in the residual graph |
895 // // } //computing distances from s in the residual graph |
896 |
896 |
908 // // typename MutableGraph::EdgeMap<Number> residual_capacity(F); |
908 // // typename MutableGraph::EdgeMap<Number> residual_capacity(F); |
909 |
909 |
910 // // //Making F to the graph containing the edges of the residual graph |
910 // // //Making F to the graph containing the edges of the residual graph |
911 // // //which are in some shortest paths |
911 // // //which are in some shortest paths |
912 // // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) { |
912 // // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) { |
913 // // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { |
913 // // if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) { |
914 // // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
914 // // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); |
915 // // original_edge.update(); |
915 // // original_edge.update(); |
916 // // original_edge.set(f, e); |
916 // // original_edge.set(f, e); |
917 // // residual_capacity.update(); |
917 // // residual_capacity.update(); |
918 // // residual_capacity.set(f, res_graph.free(e)); |
918 // // residual_capacity.set(f, res_graph.free(e)); |
919 // // } |
919 // // } |
961 // // typename MutableGraph::Node n=tF; |
961 // // typename MutableGraph::Node n=tF; |
962 // // Number augment_value=free.get(tF); |
962 // // Number augment_value=free.get(tF); |
963 // // while (F.valid(pred.get(n))) { |
963 // // while (F.valid(pred.get(n))) { |
964 // // typename MutableGraph::Edge e=pred.get(n); |
964 // // typename MutableGraph::Edge e=pred.get(n); |
965 // // res_graph.augment(original_edge.get(e), augment_value); |
965 // // res_graph.augment(original_edge.get(e), augment_value); |
966 // // n=F.tail(e); |
966 // // n=F.source(e); |
967 // // if (residual_capacity.get(e)==augment_value) |
967 // // if (residual_capacity.get(e)==augment_value) |
968 // // F.erase(e); |
968 // // F.erase(e); |
969 // // else |
969 // // else |
970 // // residual_capacity.set(e, residual_capacity.get(e)-augment_value); |
970 // // residual_capacity.set(e, residual_capacity.get(e)-augment_value); |
971 // // } |
971 // // } |
1012 // NodeMap<int>& dist=res_graph.dist; |
1012 // NodeMap<int>& dist=res_graph.dist; |
1013 |
1013 |
1014 // while ( !bfs.finished() ) { |
1014 // while ( !bfs.finished() ) { |
1015 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; |
1015 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; |
1016 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
1016 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
1017 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
1017 // dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); |
1018 // } |
1018 // } |
1019 // ++bfs; |
1019 // ++bfs; |
1020 // } //computing distances from s in the residual graph |
1020 // } //computing distances from s in the residual graph |
1021 |
1021 |
1022 // bool __augment=true; |
1022 // bool __augment=true; |
1089 // // typename EAugGraph::Node n=t; |
1089 // // typename EAugGraph::Node n=t; |
1090 // Number augment_value=free.get(n); |
1090 // Number augment_value=free.get(n); |
1091 // while (res_graph.valid(pred.get(n))) { |
1091 // while (res_graph.valid(pred.get(n))) { |
1092 // EAugEdge e=pred.get(n); |
1092 // EAugEdge e=pred.get(n); |
1093 // res_graph.augment(e, augment_value); |
1093 // res_graph.augment(e, augment_value); |
1094 // n=res_graph.tail(e); |
1094 // n=res_graph.source(e); |
1095 // if (res_graph.free(e)==0) |
1095 // if (res_graph.free(e)==0) |
1096 // res_graph.erase(e); |
1096 // res_graph.erase(e); |
1097 // } |
1097 // } |
1098 // } |
1098 // } |
1099 |
1099 |
1182 |
1182 |
1183 // // //searching for augmenting path |
1183 // // //searching for augmenting path |
1184 // // while ( !bfs.finished() ) { |
1184 // // while ( !bfs.finished() ) { |
1185 // // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); |
1185 // // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); |
1186 // // if (e.valid() && bfs.isBNodeNewlyReached()) { |
1186 // // if (e.valid() && bfs.isBNodeNewlyReached()) { |
1187 // // Node v=res_graph.tail(e); |
1187 // // Node v=res_graph.source(e); |
1188 // // Node w=res_graph.head(e); |
1188 // // Node w=res_graph.target(e); |
1189 // // pred.set(w, e); |
1189 // // pred.set(w, e); |
1190 // // if (pred.get(v).valid()) { |
1190 // // if (pred.get(v).valid()) { |
1191 // // free.set(w, std::min(free.get(v), e.free())); |
1191 // // free.set(w, std::min(free.get(v), e.free())); |
1192 // // } else { |
1192 // // } else { |
1193 // // free.set(w, e.free()); |
1193 // // free.set(w, e.free()); |
1194 // // } |
1194 // // } |
1195 // // if (TMap.get(res_graph.head(e))) { |
1195 // // if (TMap.get(res_graph.target(e))) { |
1196 // // _augment=true; |
1196 // // _augment=true; |
1197 // // reached_t_node=res_graph.head(e); |
1197 // // reached_t_node=res_graph.target(e); |
1198 // // break; |
1198 // // break; |
1199 // // } |
1199 // // } |
1200 // // } |
1200 // // } |
1201 |
1201 |
1202 // // ++bfs; |
1202 // // ++bfs; |
1206 // // Node n=reached_t_node; |
1206 // // Node n=reached_t_node; |
1207 // // Number augment_value=free.get(reached_t_node); |
1207 // // Number augment_value=free.get(reached_t_node); |
1208 // // while (pred.get(n).valid()) { |
1208 // // while (pred.get(n).valid()) { |
1209 // // AugEdge e=pred.get(n); |
1209 // // AugEdge e=pred.get(n); |
1210 // // e.augment(augment_value); |
1210 // // e.augment(augment_value); |
1211 // // n=res_graph.tail(e); |
1211 // // n=res_graph.source(e); |
1212 // // } |
1212 // // } |
1213 // // } |
1213 // // } |
1214 |
1214 |
1215 // // return _augment; |
1215 // // return _augment; |
1216 // // } |
1216 // // } |