39 OldSymEdgeIt sym; |
39 OldSymEdgeIt sym; |
40 public: |
40 public: |
41 Edge() { } |
41 Edge() { } |
42 //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { } |
42 //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { } |
43 Number free() const { |
43 Number free() const { |
44 if (resG->G.aNode(sym)==resG->G.tail(sym)) { |
44 if (resG->G.aNode(sym)==resG->G.source(sym)) { |
45 return (resG->capacity.get(sym)-resG->flow.get(sym)); |
45 return (resG->capacity.get(sym)-resG->flow.get(sym)); |
46 } else { |
46 } else { |
47 return (resG->flow.get(sym)); |
47 return (resG->flow.get(sym)); |
48 } |
48 } |
49 } |
49 } |
50 bool valid() const { return sym.valid(); } |
50 bool valid() const { return sym.valid(); } |
51 void augment(Number a) const { |
51 void augment(Number a) const { |
52 if (resG->G.aNode(sym)==resG->G.tail(sym)) { |
52 if (resG->G.aNode(sym)==resG->G.source(sym)) { |
53 resG->flow.set(sym, resG->flow.get(sym)+a); |
53 resG->flow.set(sym, resG->flow.get(sym)+a); |
54 //resG->flow[sym]+=a; |
54 //resG->flow[sym]+=a; |
55 } else { |
55 } else { |
56 resG->flow.set(sym, resG->flow.get(sym)-a); |
56 resG->flow.set(sym, resG->flow.get(sym)-a); |
57 //resG->flow[sym]-=a; |
57 //resG->flow[sym]-=a; |
95 It e; |
95 It e; |
96 /*getF*/first(e, v); |
96 /*getF*/first(e, v); |
97 return e; |
97 return e; |
98 } |
98 } |
99 |
99 |
100 Node tail(Edge e) const { return G.aNode(e.sym); } |
100 Node source(Edge e) const { return G.aNode(e.sym); } |
101 Node head(Edge e) const { return G.bNode(e.sym); } |
101 Node target(Edge e) const { return G.bNode(e.sym); } |
102 |
102 |
103 Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); } |
103 Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); } |
104 Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); } |
104 Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); } |
105 |
105 |
106 int id(Node v) const { return G.id(v); } |
106 int id(Node v) const { return G.id(v); } |
222 It e; |
222 It e; |
223 /*getF*/first(e, v); |
223 /*getF*/first(e, v); |
224 return e; |
224 return e; |
225 } |
225 } |
226 |
226 |
227 Node tail(Edge e) const { |
227 Node source(Edge e) const { |
228 return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } |
228 return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } |
229 Node head(Edge e) const { |
229 Node target(Edge e) const { |
230 return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } |
230 return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } |
231 |
231 |
232 Node aNode(OutEdgeIt e) const { |
232 Node aNode(OutEdgeIt e) const { |
233 return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } |
233 return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } |
234 Node bNode(OutEdgeIt e) const { |
234 Node bNode(OutEdgeIt e) const { |
284 |
284 |
285 //searching for augmenting path |
285 //searching for augmenting path |
286 while ( !bfs.finished() ) { |
286 while ( !bfs.finished() ) { |
287 ResGWOutEdgeIt e=bfs; |
287 ResGWOutEdgeIt e=bfs; |
288 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
288 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
289 Node v=res_graph.tail(e); |
289 Node v=res_graph.source(e); |
290 Node w=res_graph.head(e); |
290 Node w=res_graph.target(e); |
291 pred.set(w, e); |
291 pred.set(w, e); |
292 if (res_graph.valid(pred.get(v))) { |
292 if (res_graph.valid(pred.get(v))) { |
293 free.set(w, std::min(free.get(v), res_graph.resCap(e))); |
293 free.set(w, std::min(free.get(v), res_graph.resCap(e))); |
294 } else { |
294 } else { |
295 free.set(w, res_graph.resCap(e)); |
295 free.set(w, res_graph.resCap(e)); |
296 } |
296 } |
297 if (res_graph.head(e)==t) { _augment=true; break; } |
297 if (res_graph.target(e)==t) { _augment=true; break; } |
298 } |
298 } |
299 |
299 |
300 ++bfs; |
300 ++bfs; |
301 } //end of searching augmenting path |
301 } //end of searching augmenting path |
302 |
302 |
321 public: |
321 public: |
322 DistanceMap(MapGraphWrapper& _g) : g(&_g), dist(*g, g->nodeNum()) { } |
322 DistanceMap(MapGraphWrapper& _g) : g(&_g), dist(*g, g->nodeNum()) { } |
323 void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; } |
323 void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; } |
324 int get(const typename MapGraphWrapper::Node& n) const { return dist[n]; } |
324 int get(const typename MapGraphWrapper::Node& n) const { return dist[n]; } |
325 bool get(const typename MapGraphWrapper::Edge& e) const { |
325 bool get(const typename MapGraphWrapper::Edge& e) const { |
326 return (dist.get(g->tail(e))<dist.get(g->head(e))); |
326 return (dist.get(g->source(e))<dist.get(g->target(e))); |
327 } |
327 } |
328 }; |
328 }; |
329 |
329 |
330 template<typename MutableGraph> bool augmentOnBlockingFlow() { |
330 template<typename MutableGraph> bool augmentOnBlockingFlow() { |
331 typedef MutableGraph MG; |
331 typedef MutableGraph MG; |
340 //typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's |
340 //typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's |
341 DistanceMap<ResGW> dist(res_graph); |
341 DistanceMap<ResGW> dist(res_graph); |
342 while ( !bfs.finished() ) { |
342 while ( !bfs.finished() ) { |
343 ResGWOutEdgeIt e=bfs; |
343 ResGWOutEdgeIt e=bfs; |
344 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
344 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
345 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
345 dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); |
346 } |
346 } |
347 ++bfs; |
347 ++bfs; |
348 } //computing distances from s in the residual graph |
348 } //computing distances from s in the residual graph |
349 |
349 |
350 MG F; |
350 MG F; |
366 //Making F to the graph containing the edges of the residual graph |
366 //Making F to the graph containing the edges of the residual graph |
367 //which are in some shortest paths |
367 //which are in some shortest paths |
368 { |
368 { |
369 typename FilterResGW::EdgeIt e; |
369 typename FilterResGW::EdgeIt e; |
370 for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) { |
370 for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) { |
371 //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { |
371 //if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) { |
372 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
372 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); |
373 original_edge.update(); |
373 original_edge.update(); |
374 original_edge.set(f, e); |
374 original_edge.set(f, e); |
375 residual_capacity.update(); |
375 residual_capacity.update(); |
376 residual_capacity.set(f, res_graph.resCap(e)); |
376 residual_capacity.set(f, res_graph.resCap(e)); |
377 //} |
377 //} |
420 typename MG::Node n=tF; |
420 typename MG::Node n=tF; |
421 Number augment_value=free.get(tF); |
421 Number augment_value=free.get(tF); |
422 while (F.valid(pred.get(n))) { |
422 while (F.valid(pred.get(n))) { |
423 typename MG::Edge e=pred.get(n); |
423 typename MG::Edge e=pred.get(n); |
424 res_graph.augment(original_edge.get(e), augment_value); |
424 res_graph.augment(original_edge.get(e), augment_value); |
425 n=F.tail(e); |
425 n=F.source(e); |
426 if (residual_capacity.get(e)==augment_value) |
426 if (residual_capacity.get(e)==augment_value) |
427 F.erase(e); |
427 F.erase(e); |
428 else |
428 else |
429 residual_capacity.set(e, residual_capacity.get(e)-augment_value); |
429 residual_capacity.set(e, residual_capacity.get(e)-augment_value); |
430 } |
430 } |
465 |
465 |
466 while ( !bfs.finished() ) { |
466 while ( !bfs.finished() ) { |
467 ResGWOutEdgeIt e=bfs; |
467 ResGWOutEdgeIt e=bfs; |
468 if (res_graph.valid(e)) { |
468 if (res_graph.valid(e)) { |
469 if (bfs.isBNodeNewlyReached()) { |
469 if (bfs.isBNodeNewlyReached()) { |
470 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
470 dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); |
471 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
471 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); |
472 original_edge.update(); |
472 original_edge.update(); |
473 original_edge.set(f, e); |
473 original_edge.set(f, e); |
474 residual_capacity.update(); |
474 residual_capacity.update(); |
475 residual_capacity.set(f, res_graph.resCap(e)); |
475 residual_capacity.set(f, res_graph.resCap(e)); |
476 } else { |
476 } else { |
477 if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) { |
477 if (dist.get(res_graph.target(e))==(dist.get(res_graph.source(e))+1)) { |
478 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
478 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); |
479 original_edge.update(); |
479 original_edge.update(); |
480 original_edge.set(f, e); |
480 original_edge.set(f, e); |
481 residual_capacity.update(); |
481 residual_capacity.update(); |
482 residual_capacity.set(f, res_graph.resCap(e)); |
482 residual_capacity.set(f, res_graph.resCap(e)); |
483 } |
483 } |
528 typename MG::Node n=tF; |
528 typename MG::Node n=tF; |
529 Number augment_value=free.get(tF); |
529 Number augment_value=free.get(tF); |
530 while (F.valid(pred.get(n))) { |
530 while (F.valid(pred.get(n))) { |
531 typename MG::Edge e=pred.get(n); |
531 typename MG::Edge e=pred.get(n); |
532 res_graph.augment(original_edge.get(e), augment_value); |
532 res_graph.augment(original_edge.get(e), augment_value); |
533 n=F.tail(e); |
533 n=F.source(e); |
534 if (residual_capacity.get(e)==augment_value) |
534 if (residual_capacity.get(e)==augment_value) |
535 F.erase(e); |
535 F.erase(e); |
536 else |
536 else |
537 residual_capacity.set(e, residual_capacity.get(e)-augment_value); |
537 residual_capacity.set(e, residual_capacity.get(e)-augment_value); |
538 } |
538 } |
554 bfs.pushAndSetReached(s); |
554 bfs.pushAndSetReached(s); |
555 DistanceMap<ResGW> dist(res_graph); |
555 DistanceMap<ResGW> dist(res_graph); |
556 while ( !bfs.finished() ) { |
556 while ( !bfs.finished() ) { |
557 ResGWOutEdgeIt e=bfs; |
557 ResGWOutEdgeIt e=bfs; |
558 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
558 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
559 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
559 dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); |
560 } |
560 } |
561 ++bfs; |
561 ++bfs; |
562 } //computing distances from s in the residual graph |
562 } //computing distances from s in the residual graph |
563 |
563 |
564 //Subgraph containing the edges on some shortest paths |
564 //Subgraph containing the edges on some shortest paths |
630 typename ErasingResGW::Node n=t; |
630 typename ErasingResGW::Node n=t; |
631 Number augment_value=free.get(n); |
631 Number augment_value=free.get(n); |
632 while (erasing_res_graph.valid(pred.get(n))) { |
632 while (erasing_res_graph.valid(pred.get(n))) { |
633 typename ErasingResGW::OutEdgeIt e=pred.get(n); |
633 typename ErasingResGW::OutEdgeIt e=pred.get(n); |
634 res_graph.augment(e, augment_value); |
634 res_graph.augment(e, augment_value); |
635 n=erasing_res_graph.tail(e); |
635 n=erasing_res_graph.source(e); |
636 if (res_graph.resCap(e)==0) |
636 if (res_graph.resCap(e)==0) |
637 erasing_res_graph.erase(e); |
637 erasing_res_graph.erase(e); |
638 } |
638 } |
639 } |
639 } |
640 |
640 |
725 // Node n; |
725 // Node n; |
726 // //searching for augmenting path |
726 // //searching for augmenting path |
727 // while ( !bfs.finished() ) { |
727 // while ( !bfs.finished() ) { |
728 // AugOutEdgeIt e=bfs; |
728 // AugOutEdgeIt e=bfs; |
729 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
729 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
730 // Node v=res_graph.tail(e); |
730 // Node v=res_graph.source(e); |
731 // Node w=res_graph.head(e); |
731 // Node w=res_graph.target(e); |
732 // pred.set(w, e); |
732 // pred.set(w, e); |
733 // if (res_graph.valid(pred.get(v))) { |
733 // if (res_graph.valid(pred.get(v))) { |
734 // free.set(w, std::min(free.get(v), res_graph.free(e))); |
734 // free.set(w, std::min(free.get(v), res_graph.free(e))); |
735 // } else { |
735 // } else { |
736 // free.set(w, res_graph.free(e)); |
736 // free.set(w, res_graph.free(e)); |
737 // } |
737 // } |
738 // n=res_graph.head(e); |
738 // n=res_graph.target(e); |
739 // if (T->get(n) && (used.get(n)<1) ) { |
739 // if (T->get(n) && (used.get(n)<1) ) { |
740 // //Number u=0; |
740 // //Number u=0; |
741 // //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f)) |
741 // //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f)) |
742 // //u+=flow->get(f); |
742 // //u+=flow->get(f); |
743 // //if (u<1) { |
743 // //if (u<1) { |
755 // used.set(n, 1); //mind2 vegen jav |
755 // used.set(n, 1); //mind2 vegen jav |
756 // Number augment_value=free.get(n); |
756 // Number augment_value=free.get(n); |
757 // while (res_graph.valid(pred.get(n))) { |
757 // while (res_graph.valid(pred.get(n))) { |
758 // AugEdge e=pred.get(n); |
758 // AugEdge e=pred.get(n); |
759 // res_graph.augment(e, augment_value); |
759 // res_graph.augment(e, augment_value); |
760 // n=res_graph.tail(e); |
760 // n=res_graph.source(e); |
761 // } |
761 // } |
762 // used.set(n, 1); //mind2 vegen jav |
762 // used.set(n, 1); //mind2 vegen jav |
763 // } |
763 // } |
764 |
764 |
765 // return _augment; |
765 // return _augment; |
796 // // //bfs.pushAndSetReached(s); |
796 // // //bfs.pushAndSetReached(s); |
797 // // typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's |
797 // // typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's |
798 // // while ( !bfs.finished() ) { |
798 // // while ( !bfs.finished() ) { |
799 // // AugOutEdgeIt e=bfs; |
799 // // AugOutEdgeIt e=bfs; |
800 // // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
800 // // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
801 // // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
801 // // dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); |
802 // // } |
802 // // } |
803 |
803 |
804 // // ++bfs; |
804 // // ++bfs; |
805 // // } //computing distances from s in the residual graph |
805 // // } //computing distances from s in the residual graph |
806 |
806 |
818 // // typename MutableGraph::EdgeMap<Number> residual_capacity(F); |
818 // // typename MutableGraph::EdgeMap<Number> residual_capacity(F); |
819 |
819 |
820 // // //Making F to the graph containing the edges of the residual graph |
820 // // //Making F to the graph containing the edges of the residual graph |
821 // // //which are in some shortest paths |
821 // // //which are in some shortest paths |
822 // // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) { |
822 // // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) { |
823 // // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { |
823 // // if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) { |
824 // // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
824 // // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); |
825 // // original_edge.update(); |
825 // // original_edge.update(); |
826 // // original_edge.set(f, e); |
826 // // original_edge.set(f, e); |
827 // // residual_capacity.update(); |
827 // // residual_capacity.update(); |
828 // // residual_capacity.set(f, res_graph.free(e)); |
828 // // residual_capacity.set(f, res_graph.free(e)); |
829 // // } |
829 // // } |
871 // // typename MutableGraph::Node n=tF; |
871 // // typename MutableGraph::Node n=tF; |
872 // // Number augment_value=free.get(tF); |
872 // // Number augment_value=free.get(tF); |
873 // // while (F.valid(pred.get(n))) { |
873 // // while (F.valid(pred.get(n))) { |
874 // // typename MutableGraph::Edge e=pred.get(n); |
874 // // typename MutableGraph::Edge e=pred.get(n); |
875 // // res_graph.augment(original_edge.get(e), augment_value); |
875 // // res_graph.augment(original_edge.get(e), augment_value); |
876 // // n=F.tail(e); |
876 // // n=F.source(e); |
877 // // if (residual_capacity.get(e)==augment_value) |
877 // // if (residual_capacity.get(e)==augment_value) |
878 // // F.erase(e); |
878 // // F.erase(e); |
879 // // else |
879 // // else |
880 // // residual_capacity.set(e, residual_capacity.get(e)-augment_value); |
880 // // residual_capacity.set(e, residual_capacity.get(e)-augment_value); |
881 // // } |
881 // // } |
922 // NodeMap<int>& dist=res_graph.dist; |
922 // NodeMap<int>& dist=res_graph.dist; |
923 |
923 |
924 // while ( !bfs.finished() ) { |
924 // while ( !bfs.finished() ) { |
925 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; |
925 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; |
926 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
926 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
927 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
927 // dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); |
928 // } |
928 // } |
929 // ++bfs; |
929 // ++bfs; |
930 // } //computing distances from s in the residual graph |
930 // } //computing distances from s in the residual graph |
931 |
931 |
932 // bool __augment=true; |
932 // bool __augment=true; |
999 // // typename EAugGraph::Node n=t; |
999 // // typename EAugGraph::Node n=t; |
1000 // Number augment_value=free.get(n); |
1000 // Number augment_value=free.get(n); |
1001 // while (res_graph.valid(pred.get(n))) { |
1001 // while (res_graph.valid(pred.get(n))) { |
1002 // EAugEdge e=pred.get(n); |
1002 // EAugEdge e=pred.get(n); |
1003 // res_graph.augment(e, augment_value); |
1003 // res_graph.augment(e, augment_value); |
1004 // n=res_graph.tail(e); |
1004 // n=res_graph.source(e); |
1005 // if (res_graph.free(e)==0) |
1005 // if (res_graph.free(e)==0) |
1006 // res_graph.erase(e); |
1006 // res_graph.erase(e); |
1007 // } |
1007 // } |
1008 // } |
1008 // } |
1009 |
1009 |
1092 |
1092 |
1093 // // //searching for augmenting path |
1093 // // //searching for augmenting path |
1094 // // while ( !bfs.finished() ) { |
1094 // // while ( !bfs.finished() ) { |
1095 // // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); |
1095 // // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); |
1096 // // if (e.valid() && bfs.isBNodeNewlyReached()) { |
1096 // // if (e.valid() && bfs.isBNodeNewlyReached()) { |
1097 // // Node v=res_graph.tail(e); |
1097 // // Node v=res_graph.source(e); |
1098 // // Node w=res_graph.head(e); |
1098 // // Node w=res_graph.target(e); |
1099 // // pred.set(w, e); |
1099 // // pred.set(w, e); |
1100 // // if (pred.get(v).valid()) { |
1100 // // if (pred.get(v).valid()) { |
1101 // // free.set(w, std::min(free.get(v), e.free())); |
1101 // // free.set(w, std::min(free.get(v), e.free())); |
1102 // // } else { |
1102 // // } else { |
1103 // // free.set(w, e.free()); |
1103 // // free.set(w, e.free()); |
1104 // // } |
1104 // // } |
1105 // // if (TMap.get(res_graph.head(e))) { |
1105 // // if (TMap.get(res_graph.target(e))) { |
1106 // // _augment=true; |
1106 // // _augment=true; |
1107 // // reached_t_node=res_graph.head(e); |
1107 // // reached_t_node=res_graph.target(e); |
1108 // // break; |
1108 // // break; |
1109 // // } |
1109 // // } |
1110 // // } |
1110 // // } |
1111 |
1111 |
1112 // // ++bfs; |
1112 // // ++bfs; |
1116 // // Node n=reached_t_node; |
1116 // // Node n=reached_t_node; |
1117 // // Number augment_value=free.get(reached_t_node); |
1117 // // Number augment_value=free.get(reached_t_node); |
1118 // // while (pred.get(n).valid()) { |
1118 // // while (pred.get(n).valid()) { |
1119 // // AugEdge e=pred.get(n); |
1119 // // AugEdge e=pred.get(n); |
1120 // // e.augment(augment_value); |
1120 // // e.augment(augment_value); |
1121 // // n=res_graph.tail(e); |
1121 // // n=res_graph.source(e); |
1122 // // } |
1122 // // } |
1123 // // } |
1123 // // } |
1124 |
1124 |
1125 // // return _augment; |
1125 // // return _augment; |
1126 // // } |
1126 // // } |