57 |
57 |
58 //searching for augmenting path |
58 //searching for augmenting path |
59 while ( !bfs.finished() ) { |
59 while ( !bfs.finished() ) { |
60 ResGWOutEdgeIt e=bfs; |
60 ResGWOutEdgeIt e=bfs; |
61 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
61 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
62 Node v=res_graph.tail(e); |
62 Node v=res_graph.source(e); |
63 Node w=res_graph.head(e); |
63 Node w=res_graph.target(e); |
64 pred.set(w, e); |
64 pred.set(w, e); |
65 if (res_graph.valid(pred[v])) { |
65 if (res_graph.valid(pred[v])) { |
66 free.set(w, std::min(free[v], res_graph.resCap(e))); |
66 free.set(w, std::min(free[v], res_graph.resCap(e))); |
67 } else { |
67 } else { |
68 free.set(w, res_graph.resCap(e)); |
68 free.set(w, res_graph.resCap(e)); |
69 } |
69 } |
70 if (res_graph.head(e)==t) { _augment=true; break; } |
70 if (res_graph.target(e)==t) { _augment=true; break; } |
71 } |
71 } |
72 |
72 |
73 ++bfs; |
73 ++bfs; |
74 } //end of searching augmenting path |
74 } //end of searching augmenting path |
75 |
75 |
99 int operator[](const typename MapGraphWrapper::Node& n) |
99 int operator[](const typename MapGraphWrapper::Node& n) |
100 { return dist[n]; } |
100 { return dist[n]; } |
101 // int get(const typename MapGraphWrapper::Node& n) const { |
101 // int get(const typename MapGraphWrapper::Node& n) const { |
102 // return dist[n]; } |
102 // return dist[n]; } |
103 // bool get(const typename MapGraphWrapper::Edge& e) const { |
103 // bool get(const typename MapGraphWrapper::Edge& e) const { |
104 // return (dist.get(g->tail(e))<dist.get(g->head(e))); } |
104 // return (dist.get(g->source(e))<dist.get(g->target(e))); } |
105 bool operator[](const typename MapGraphWrapper::Edge& e) const { |
105 bool operator[](const typename MapGraphWrapper::Edge& e) const { |
106 return (dist[g->tail(e)]<dist[g->head(e)]); |
106 return (dist[g->source(e)]<dist[g->target(e)]); |
107 } |
107 } |
108 }; |
108 }; |
109 |
109 |
110 template<typename MutableGraph> bool augmentOnBlockingFlow() { |
110 template<typename MutableGraph> bool augmentOnBlockingFlow() { |
111 typedef MutableGraph MG; |
111 typedef MutableGraph MG; |
121 //typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's |
121 //typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's |
122 DistanceMap<ResGW> dist(res_graph); |
122 DistanceMap<ResGW> dist(res_graph); |
123 while ( !bfs.finished() ) { |
123 while ( !bfs.finished() ) { |
124 ResGWOutEdgeIt e=bfs; |
124 ResGWOutEdgeIt e=bfs; |
125 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
125 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
126 dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1); |
126 dist.set(res_graph.target(e), dist[res_graph.source(e)]+1); |
127 } |
127 } |
128 ++bfs; |
128 ++bfs; |
129 } //computing distances from s in the residual graph |
129 } //computing distances from s in the residual graph |
130 |
130 |
131 MG F; |
131 MG F; |
150 //Making F to the graph containing the edges of the residual graph |
150 //Making F to the graph containing the edges of the residual graph |
151 //which are in some shortest paths |
151 //which are in some shortest paths |
152 { |
152 { |
153 typename FilterResGW::EdgeIt e; |
153 typename FilterResGW::EdgeIt e; |
154 for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) { |
154 for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) { |
155 //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { |
155 //if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) { |
156 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]); |
156 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], res_graph_to_F[res_graph.target(e)]); |
157 original_edge.update(); |
157 original_edge.update(); |
158 original_edge.set(f, e); |
158 original_edge.set(f, e); |
159 residual_capacity.update(); |
159 residual_capacity.update(); |
160 residual_capacity.set(f, res_graph.resCap(e)); |
160 residual_capacity.set(f, res_graph.resCap(e)); |
161 //} |
161 //} |
204 typename MG::Node n=tF; |
204 typename MG::Node n=tF; |
205 Num augment_value=free[tF]; |
205 Num augment_value=free[tF]; |
206 while (F.valid(pred[n])) { |
206 while (F.valid(pred[n])) { |
207 typename MG::Edge e=pred[n]; |
207 typename MG::Edge e=pred[n]; |
208 res_graph.augment(original_edge[e], augment_value); |
208 res_graph.augment(original_edge[e], augment_value); |
209 n=F.tail(e); |
209 n=F.source(e); |
210 if (residual_capacity[e]==augment_value) |
210 if (residual_capacity[e]==augment_value) |
211 F.erase(e); |
211 F.erase(e); |
212 else |
212 else |
213 residual_capacity.set(e, residual_capacity[e]-augment_value); |
213 residual_capacity.set(e, residual_capacity[e]-augment_value); |
214 } |
214 } |
252 |
252 |
253 while ( !bfs.finished() ) { |
253 while ( !bfs.finished() ) { |
254 ResGWOutEdgeIt e=bfs; |
254 ResGWOutEdgeIt e=bfs; |
255 if (res_graph.valid(e)) { |
255 if (res_graph.valid(e)) { |
256 if (bfs.isBNodeNewlyReached()) { |
256 if (bfs.isBNodeNewlyReached()) { |
257 dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1); |
257 dist.set(res_graph.target(e), dist[res_graph.source(e)]+1); |
258 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]); |
258 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], res_graph_to_F[res_graph.target(e)]); |
259 original_edge.update(); |
259 original_edge.update(); |
260 original_edge.set(f, e); |
260 original_edge.set(f, e); |
261 residual_capacity.update(); |
261 residual_capacity.update(); |
262 residual_capacity.set(f, res_graph.resCap(e)); |
262 residual_capacity.set(f, res_graph.resCap(e)); |
263 } else { |
263 } else { |
264 if (dist[res_graph.head(e)]==(dist[res_graph.tail(e)]+1)) { |
264 if (dist[res_graph.target(e)]==(dist[res_graph.source(e)]+1)) { |
265 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]); |
265 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], res_graph_to_F[res_graph.target(e)]); |
266 original_edge.update(); |
266 original_edge.update(); |
267 original_edge.set(f, e); |
267 original_edge.set(f, e); |
268 residual_capacity.update(); |
268 residual_capacity.update(); |
269 residual_capacity.set(f, res_graph.resCap(e)); |
269 residual_capacity.set(f, res_graph.resCap(e)); |
270 } |
270 } |
314 typename MG::Node n=tF; |
314 typename MG::Node n=tF; |
315 Num augment_value=free[tF]; |
315 Num augment_value=free[tF]; |
316 while (F.valid(pred[n])) { |
316 while (F.valid(pred[n])) { |
317 typename MG::Edge e=pred[n]; |
317 typename MG::Edge e=pred[n]; |
318 res_graph.augment(original_edge[e], augment_value); |
318 res_graph.augment(original_edge[e], augment_value); |
319 n=F.tail(e); |
319 n=F.source(e); |
320 if (residual_capacity[e]==augment_value) |
320 if (residual_capacity[e]==augment_value) |
321 F.erase(e); |
321 F.erase(e); |
322 else |
322 else |
323 residual_capacity.set(e, residual_capacity[e]-augment_value); |
323 residual_capacity.set(e, residual_capacity[e]-augment_value); |
324 } |
324 } |
341 bfs.pushAndSetReached(s); |
341 bfs.pushAndSetReached(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[res_graph.tail(e)]+1); |
346 dist.set(res_graph.target(e), dist[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 //Subgraph containing the edges on some shortest paths |
351 //Subgraph containing the edges on some shortest paths |
438 // Num j2=a2[b2]; |
438 // Num j2=a2[b2]; |
439 Num augment_value=free1[n]; |
439 Num augment_value=free1[n]; |
440 while (erasing_res_graph.valid(pred[n])) { |
440 while (erasing_res_graph.valid(pred[n])) { |
441 typename ErasingResGW::OutEdgeIt e=pred[n]; |
441 typename ErasingResGW::OutEdgeIt e=pred[n]; |
442 res_graph.augment(e, augment_value); |
442 res_graph.augment(e, augment_value); |
443 n=erasing_res_graph.tail(e); |
443 n=erasing_res_graph.source(e); |
444 if (res_graph.resCap(e)==0) |
444 if (res_graph.resCap(e)==0) |
445 erasing_res_graph.erase(e); |
445 erasing_res_graph.erase(e); |
446 } |
446 } |
447 } |
447 } |
448 |
448 |
533 // Node n; |
533 // Node n; |
534 // //searching for augmenting path |
534 // //searching for augmenting path |
535 // while ( !bfs.finished() ) { |
535 // while ( !bfs.finished() ) { |
536 // AugOutEdgeIt e=bfs; |
536 // AugOutEdgeIt e=bfs; |
537 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
537 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
538 // Node v=res_graph.tail(e); |
538 // Node v=res_graph.source(e); |
539 // Node w=res_graph.head(e); |
539 // Node w=res_graph.target(e); |
540 // pred.set(w, e); |
540 // pred.set(w, e); |
541 // if (res_graph.valid(pred.get(v))) { |
541 // if (res_graph.valid(pred.get(v))) { |
542 // free.set(w, std::min(free.get(v), res_graph.free(e))); |
542 // free.set(w, std::min(free.get(v), res_graph.free(e))); |
543 // } else { |
543 // } else { |
544 // free.set(w, res_graph.free(e)); |
544 // free.set(w, res_graph.free(e)); |
545 // } |
545 // } |
546 // n=res_graph.head(e); |
546 // n=res_graph.target(e); |
547 // if (T->get(n) && (used.get(n)<1) ) { |
547 // if (T->get(n) && (used.get(n)<1) ) { |
548 // //Num u=0; |
548 // //Num u=0; |
549 // //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f)) |
549 // //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f)) |
550 // //u+=flow->get(f); |
550 // //u+=flow->get(f); |
551 // //if (u<1) { |
551 // //if (u<1) { |
563 // used.set(n, 1); //mind2 vegen jav |
563 // used.set(n, 1); //mind2 vegen jav |
564 // Num augment_value=free.get(n); |
564 // Num augment_value=free.get(n); |
565 // while (res_graph.valid(pred.get(n))) { |
565 // while (res_graph.valid(pred.get(n))) { |
566 // AugEdge e=pred.get(n); |
566 // AugEdge e=pred.get(n); |
567 // res_graph.augment(e, augment_value); |
567 // res_graph.augment(e, augment_value); |
568 // n=res_graph.tail(e); |
568 // n=res_graph.source(e); |
569 // } |
569 // } |
570 // used.set(n, 1); //mind2 vegen jav |
570 // used.set(n, 1); //mind2 vegen jav |
571 // } |
571 // } |
572 |
572 |
573 // return _augment; |
573 // return _augment; |
604 // // //bfs.pushAndSetReached(s); |
604 // // //bfs.pushAndSetReached(s); |
605 // // typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's |
605 // // typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's |
606 // // while ( !bfs.finished() ) { |
606 // // while ( !bfs.finished() ) { |
607 // // AugOutEdgeIt e=bfs; |
607 // // AugOutEdgeIt e=bfs; |
608 // // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
608 // // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
609 // // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
609 // // dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); |
610 // // } |
610 // // } |
611 |
611 |
612 // // ++bfs; |
612 // // ++bfs; |
613 // // } //computing distances from s in the residual graph |
613 // // } //computing distances from s in the residual graph |
614 |
614 |
626 // // typename MutableGraph::EdgeMap<Num> residual_capacity(F); |
626 // // typename MutableGraph::EdgeMap<Num> residual_capacity(F); |
627 |
627 |
628 // // //Making F to the graph containing the edges of the residual graph |
628 // // //Making F to the graph containing the edges of the residual graph |
629 // // //which are in some shortest paths |
629 // // //which are in some shortest paths |
630 // // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) { |
630 // // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) { |
631 // // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { |
631 // // if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) { |
632 // // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
632 // // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); |
633 // // original_edge.update(); |
633 // // original_edge.update(); |
634 // // original_edge.set(f, e); |
634 // // original_edge.set(f, e); |
635 // // residual_capacity.update(); |
635 // // residual_capacity.update(); |
636 // // residual_capacity.set(f, res_graph.free(e)); |
636 // // residual_capacity.set(f, res_graph.free(e)); |
637 // // } |
637 // // } |
679 // // typename MutableGraph::Node n=tF; |
679 // // typename MutableGraph::Node n=tF; |
680 // // Num augment_value=free.get(tF); |
680 // // Num augment_value=free.get(tF); |
681 // // while (F.valid(pred.get(n))) { |
681 // // while (F.valid(pred.get(n))) { |
682 // // typename MutableGraph::Edge e=pred.get(n); |
682 // // typename MutableGraph::Edge e=pred.get(n); |
683 // // res_graph.augment(original_edge.get(e), augment_value); |
683 // // res_graph.augment(original_edge.get(e), augment_value); |
684 // // n=F.tail(e); |
684 // // n=F.source(e); |
685 // // if (residual_capacity.get(e)==augment_value) |
685 // // if (residual_capacity.get(e)==augment_value) |
686 // // F.erase(e); |
686 // // F.erase(e); |
687 // // else |
687 // // else |
688 // // residual_capacity.set(e, residual_capacity.get(e)-augment_value); |
688 // // residual_capacity.set(e, residual_capacity.get(e)-augment_value); |
689 // // } |
689 // // } |
730 // NodeMap<int>& dist=res_graph.dist; |
730 // NodeMap<int>& dist=res_graph.dist; |
731 |
731 |
732 // while ( !bfs.finished() ) { |
732 // while ( !bfs.finished() ) { |
733 // typename ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>::OutEdgeIt e=bfs; |
733 // typename ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>::OutEdgeIt e=bfs; |
734 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
734 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
735 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
735 // dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); |
736 // } |
736 // } |
737 // ++bfs; |
737 // ++bfs; |
738 // } //computing distances from s in the residual graph |
738 // } //computing distances from s in the residual graph |
739 |
739 |
740 // bool __augment=true; |
740 // bool __augment=true; |
807 // // typename EAugGraph::Node n=t; |
807 // // typename EAugGraph::Node n=t; |
808 // Num augment_value=free.get(n); |
808 // Num augment_value=free.get(n); |
809 // while (res_graph.valid(pred.get(n))) { |
809 // while (res_graph.valid(pred.get(n))) { |
810 // EAugEdge e=pred.get(n); |
810 // EAugEdge e=pred.get(n); |
811 // res_graph.augment(e, augment_value); |
811 // res_graph.augment(e, augment_value); |
812 // n=res_graph.tail(e); |
812 // n=res_graph.source(e); |
813 // if (res_graph.free(e)==0) |
813 // if (res_graph.free(e)==0) |
814 // res_graph.erase(e); |
814 // res_graph.erase(e); |
815 // } |
815 // } |
816 // } |
816 // } |
817 |
817 |
900 |
900 |
901 // // //searching for augmenting path |
901 // // //searching for augmenting path |
902 // // while ( !bfs.finished() ) { |
902 // // while ( !bfs.finished() ) { |
903 // // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); |
903 // // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); |
904 // // if (e.valid() && bfs.isBNodeNewlyReached()) { |
904 // // if (e.valid() && bfs.isBNodeNewlyReached()) { |
905 // // Node v=res_graph.tail(e); |
905 // // Node v=res_graph.source(e); |
906 // // Node w=res_graph.head(e); |
906 // // Node w=res_graph.target(e); |
907 // // pred.set(w, e); |
907 // // pred.set(w, e); |
908 // // if (pred.get(v).valid()) { |
908 // // if (pred.get(v).valid()) { |
909 // // free.set(w, std::min(free.get(v), e.free())); |
909 // // free.set(w, std::min(free.get(v), e.free())); |
910 // // } else { |
910 // // } else { |
911 // // free.set(w, e.free()); |
911 // // free.set(w, e.free()); |
912 // // } |
912 // // } |
913 // // if (TMap.get(res_graph.head(e))) { |
913 // // if (TMap.get(res_graph.target(e))) { |
914 // // _augment=true; |
914 // // _augment=true; |
915 // // reached_t_node=res_graph.head(e); |
915 // // reached_t_node=res_graph.target(e); |
916 // // break; |
916 // // break; |
917 // // } |
917 // // } |
918 // // } |
918 // // } |
919 |
919 |
920 // // ++bfs; |
920 // // ++bfs; |
924 // // Node n=reached_t_node; |
924 // // Node n=reached_t_node; |
925 // // Num augment_value=free.get(reached_t_node); |
925 // // Num augment_value=free.get(reached_t_node); |
926 // // while (pred.get(n).valid()) { |
926 // // while (pred.get(n).valid()) { |
927 // // AugEdge e=pred.get(n); |
927 // // AugEdge e=pred.get(n); |
928 // // e.augment(augment_value); |
928 // // e.augment(augment_value); |
929 // // n=res_graph.tail(e); |
929 // // n=res_graph.source(e); |
930 // // } |
930 // // } |
931 // // } |
931 // // } |
932 |
932 |
933 // // return _augment; |
933 // // return _augment; |
934 // // } |
934 // // } |