Changeset 269:07af3069c0b8 in lemon0.x for src/work/edmonds_karp.h
 Timestamp:
 03/31/04 17:50:21 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@375
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/edmonds_karp.h
r268 r269 250 250 template <typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap> 251 251 class MaxFlow { 252 public: 253 typedef typename GraphWrapper::Node Node; 254 typedef typename GraphWrapper::Edge Edge; 255 typedef typename GraphWrapper::EdgeIt EdgeIt; 256 typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; 257 typedef typename GraphWrapper::InEdgeIt InEdgeIt; 258 259 private: 252 protected: 253 typedef GraphWrapper GW; 254 typedef typename GW::Node Node; 255 typedef typename GW::Edge Edge; 256 typedef typename GW::EdgeIt EdgeIt; 257 typedef typename GW::OutEdgeIt OutEdgeIt; 258 typedef typename GW::InEdgeIt InEdgeIt; 260 259 //const Graph* G; 261 G raphWrappergw;260 GW gw; 262 261 Node s; 263 262 Node t; 264 263 FlowMap* flow; 265 264 const CapacityMap* capacity; 266 typedef ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap > 267 AugGraph; 268 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; 269 typedef typename AugGraph::Edge AugEdge; 270 265 typedef ResGraphWrapper<GW, Number, FlowMap, CapacityMap > ResGW; 266 typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt; 267 typedef typename ResGW::Edge ResGWEdge; 271 268 public: 272 MaxFlow(const GraphWrapper& _gw, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) : 269 270 MaxFlow(const GW& _gw, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) : 273 271 gw(_gw), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { } 272 274 273 bool augmentOnShortestPath() { 275 AugGraphres_graph(gw, *flow, *capacity);274 ResGW res_graph(gw, *flow, *capacity); 276 275 bool _augment=false; 277 276 278 typedef typename AugGraph::NodeMap<bool> ReachedMap;279 BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);280 res_bfs.pushAndSetReached(s);277 typedef typename ResGW::NodeMap<bool> ReachedMap; 278 BfsIterator5< ResGW, ReachedMap > bfs(res_graph); 279 bfs.pushAndSetReached(s); 281 280 282 typename AugGraph::NodeMap<AugEdge> pred(res_graph);283 pred.set(s, AugEdge(INVALID));281 typename ResGW::NodeMap<ResGWEdge> pred(res_graph); 282 pred.set(s, INVALID); 284 283 285 typename AugGraph::NodeMap<Number> free(res_graph);284 typename ResGW::NodeMap<Number> free(res_graph); 286 285 287 286 //searching for augmenting path 288 while ( ! res_bfs.finished() ) {289 AugOutEdgeIt e=res_bfs;290 if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {287 while ( !bfs.finished() ) { 288 ResGWOutEdgeIt e=bfs; 289 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 291 290 Node v=res_graph.tail(e); 292 291 Node w=res_graph.head(e); 293 292 pred.set(w, e); 294 293 if (res_graph.valid(pred.get(v))) { 295 free.set(w, std::min(free.get(v), res_graph. free(e)));294 free.set(w, std::min(free.get(v), res_graph.resCap(e))); 296 295 } else { 297 free.set(w, res_graph. free(e));296 free.set(w, res_graph.resCap(e)); 298 297 } 299 298 if (res_graph.head(e)==t) { _augment=true; break; } 300 299 } 301 300 302 ++ res_bfs;301 ++bfs; 303 302 } //end of searching augmenting path 304 303 … … 307 306 Number augment_value=free.get(t); 308 307 while (res_graph.valid(pred.get(n))) { 309 AugEdge e=pred.get(n);308 ResGWEdge e=pred.get(n); 310 309 res_graph.augment(e, augment_value); 311 310 n=res_graph.tail(e); … … 331 330 332 331 template<typename MutableGraph> bool augmentOnBlockingFlow() { 332 typedef MutableGraph MG; 333 333 bool _augment=false; 334 334 335 AugGraphres_graph(gw, *flow, *capacity);336 337 typedef typename AugGraph::NodeMap<bool> ReachedMap;338 BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);335 ResGW res_graph(gw, *flow, *capacity); 336 337 typedef typename ResGW::NodeMap<bool> ReachedMap; 338 BfsIterator5< ResGW, ReachedMap > bfs(res_graph); 339 339 340 340 bfs.pushAndSetReached(s); 341 //typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's342 DistanceMap< AugGraph> dist(res_graph);341 //typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's 342 DistanceMap<ResGW> dist(res_graph); 343 343 while ( !bfs.finished() ) { 344 AugOutEdgeIt e=bfs;344 ResGWOutEdgeIt e=bfs; 345 345 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 346 346 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); … … 349 349 } //computing distances from s in the residual graph 350 350 351 MutableGraph F; 352 typedef SubGraphWrapper<AugGraph, DistanceMap<AugGraph> > FilterResGraph; 353 FilterResGraph filter_res_graph(res_graph, dist); 354 typename AugGraph::NodeMap<typename MutableGraph::Node> 355 res_graph_to_F(res_graph); 356 for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { 351 MG F; 352 typedef SubGraphWrapper<ResGW, DistanceMap<ResGW> > FilterResGW; 353 FilterResGW filter_res_graph(res_graph, dist); 354 typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph); 355 for(typename ResGW::NodeIt n=res_graph.template first<typename ResGW::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { 357 356 res_graph_to_F.set(n, F.addNode()); 358 357 } 359 360 typename MutableGraph::Node sF=res_graph_to_F.get(s); 361 typename MutableGraph::Node tF=res_graph_to_F.get(t); 362 363 typename MutableGraph::EdgeMap<AugEdge> original_edge(F); 364 typename MutableGraph::EdgeMap<Number> residual_capacity(F); 358 359 typename MG::Node sF=res_graph_to_F.get(s); 360 typename MG::Node tF=res_graph_to_F.get(t); 361 typename MG::EdgeMap<ResGWEdge> original_edge(F); 362 typename MG::EdgeMap<Number> residual_capacity(F); 365 363 366 364 //Making F to the graph containing the edges of the residual graph 367 365 //which are in some shortest paths 368 for(typename FilterResG raph::EdgeIt e=filter_res_graph.template first<typename FilterResGraph::EdgeIt>(); filter_res_graph.valid(e); filter_res_graph.next(e)) {366 for(typename FilterResGW::EdgeIt e=filter_res_graph.template first<typename FilterResGW::EdgeIt>(); filter_res_graph.valid(e); filter_res_graph.next(e)) { 369 367 //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { 370 typename M utableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));368 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); 371 369 original_edge.update(); 372 370 original_edge.set(f, e); 373 371 residual_capacity.update(); 374 residual_capacity.set(f, res_graph. free(e));372 residual_capacity.set(f, res_graph.resCap(e)); 375 373 //} 376 374 } … … 381 379 __augment=false; 382 380 //computing blocking flow with dfs 383 typedef typename TrivGraphWrapper<M utableGraph>::NodeMap<bool> BlockingReachedMap;384 DfsIterator5< TrivGraphWrapper<M utableGraph>, BlockingReachedMap > dfs(F);385 typename M utableGraph::NodeMap<typename MutableGraph::Edge> pred(F);386 pred.set(sF, typename MutableGraph::Edge(INVALID));381 typedef typename TrivGraphWrapper<MG>::NodeMap<bool> BlockingReachedMap; 382 DfsIterator5< TrivGraphWrapper<MG>, BlockingReachedMap > dfs(F); 383 typename MG::NodeMap<typename MG::Edge> pred(F); 384 pred.set(sF, INVALID); 387 385 //invalid iterators for sources 388 386 389 typename M utableGraph::NodeMap<Number> free(F);387 typename MG::NodeMap<Number> free(F); 390 388 391 389 dfs.pushAndSetReached(sF); 392 390 while (!dfs.finished()) { 393 391 ++dfs; 394 if (F.valid( typename MutableGraph::OutEdgeIt(dfs))) {392 if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) { 395 393 if (dfs.isBNodeNewlyReached()) { 396 typename M utableGraph::Node v=F.aNode(dfs);397 typename M utableGraph::Node w=F.bNode(dfs);394 typename MG::Node v=F.aNode(dfs); 395 typename MG::Node w=F.bNode(dfs); 398 396 pred.set(w, dfs); 399 397 if (F.valid(pred.get(v))) { … … 409 407 410 408 } else { 411 F.erase( typename MutableGraph::OutEdgeIt(dfs));409 F.erase(/*typename MG::OutEdgeIt*/(dfs)); 412 410 } 413 411 } … … 415 413 416 414 if (__augment) { 417 typename M utableGraph::Node n=tF;415 typename MG::Node n=tF; 418 416 Number augment_value=free.get(tF); 419 417 while (F.valid(pred.get(n))) { 420 typename M utableGraph::Edge e=pred.get(n);418 typename MG::Edge e=pred.get(n); 421 419 res_graph.augment(original_edge.get(e), augment_value); 422 420 n=F.tail(e); … … 434 432 435 433 template<typename MutableGraph> bool augmentOnBlockingFlow1() { 434 typedef MutableGraph MG; 436 435 bool _augment=false; 437 436 438 AugGraphres_graph(gw, *flow, *capacity);437 ResGW res_graph(gw, *flow, *capacity); 439 438 440 439 //bfs for distances on the residual graph 441 typedef typename AugGraph::NodeMap<bool> ReachedMap;442 BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);440 typedef typename ResGW::NodeMap<bool> ReachedMap; 441 BfsIterator5< ResGW, ReachedMap > bfs(res_graph); 443 442 bfs.pushAndSetReached(s); 444 typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's443 typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's 445 444 446 445 //F will contain the physical copy of the residual graph 447 //with the set of edges which areon shortest paths 448 MutableGraph F; 449 typename AugGraph::NodeMap<typename MutableGraph::Node> 450 res_graph_to_F(res_graph); 451 for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { 446 //with the set of edges which are on shortest paths 447 MG F; 448 typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph); 449 for(typename ResGW::NodeIt n=res_graph.template first<typename ResGW::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { 452 450 res_graph_to_F.set(n, F.addNode()); 453 451 } 454 typename MutableGraph::Node sF=res_graph_to_F.get(s); 455 typename MutableGraph::Node tF=res_graph_to_F.get(t); 456 typename MutableGraph::EdgeMap<AugEdge> original_edge(F); 457 typename MutableGraph::EdgeMap<Number> residual_capacity(F); 452 453 typename MG::Node sF=res_graph_to_F.get(s); 454 typename MG::Node tF=res_graph_to_F.get(t); 455 typename MG::EdgeMap<ResGWEdge> original_edge(F); 456 typename MG::EdgeMap<Number> residual_capacity(F); 458 457 459 458 while ( !bfs.finished() ) { 460 AugOutEdgeIt e=bfs;459 ResGWOutEdgeIt e=bfs; 461 460 if (res_graph.valid(e)) { 462 461 if (bfs.isBNodeNewlyReached()) { 463 462 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); 464 typename M utableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));463 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); 465 464 original_edge.update(); 466 465 original_edge.set(f, e); 467 466 residual_capacity.update(); 468 residual_capacity.set(f, res_graph. free(e));467 residual_capacity.set(f, res_graph.resCap(e)); 469 468 } else { 470 469 if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) { 471 typename M utableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));470 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 471 original_edge.update(); 473 472 original_edge.set(f, e); 474 473 residual_capacity.update(); 475 residual_capacity.set(f, res_graph. free(e));474 residual_capacity.set(f, res_graph.resCap(e)); 476 475 } 477 476 } … … 485 484 __augment=false; 486 485 //computing blocking flow with dfs 487 typedef typename TrivGraphWrapper<M utableGraph>::NodeMap<bool> BlockingReachedMap;488 DfsIterator5< TrivGraphWrapper<M utableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);489 typename M utableGraph::NodeMap<typename MutableGraph::Edge> pred(F);490 pred.set(sF, typename MutableGraph::Edge(INVALID));486 typedef typename TrivGraphWrapper<MG>::NodeMap<bool> BlockingReachedMap; 487 DfsIterator5< TrivGraphWrapper<MG>, BlockingReachedMap > dfs(F); 488 typename MG::NodeMap<typename MG::Edge> pred(F); 489 pred.set(sF, INVALID); 491 490 //invalid iterators for sources 492 491 493 typename M utableGraph::NodeMap<Number> free(F);492 typename MG::NodeMap<Number> free(F); 494 493 495 494 dfs.pushAndSetReached(sF); 496 495 while (!dfs.finished()) { 497 496 ++dfs; 498 if (F.valid( typename MutableGraph::OutEdgeIt(dfs))) {497 if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) { 499 498 if (dfs.isBNodeNewlyReached()) { 500 typename M utableGraph::Node v=F.aNode(dfs);501 typename M utableGraph::Node w=F.bNode(dfs);499 typename MG::Node v=F.aNode(dfs); 500 typename MG::Node w=F.bNode(dfs); 502 501 pred.set(w, dfs); 503 502 if (F.valid(pred.get(v))) { … … 513 512 514 513 } else { 515 F.erase( typename MutableGraph::OutEdgeIt(dfs));514 F.erase(/*typename MG::OutEdgeIt*/(dfs)); 516 515 } 517 516 } … … 519 518 520 519 if (__augment) { 521 typename M utableGraph::Node n=tF;520 typename MG::Node n=tF; 522 521 Number augment_value=free.get(tF); 523 522 while (F.valid(pred.get(n))) { 524 typename M utableGraph::Edge e=pred.get(n);523 typename MG::Edge e=pred.get(n); 525 524 res_graph.augment(original_edge.get(e), augment_value); 526 525 n=F.tail(e); … … 533 532 534 533 } 534 535 return _augment; 536 } 537 538 bool augmentOnBlockingFlow2() { 539 bool _augment=false; 540 541 ResGW res_graph(gw, *flow, *capacity); 542 543 typedef typename ResGW::NodeMap<bool> ReachedMap; 544 BfsIterator5< ResGW, ReachedMap > bfs(res_graph); 545 546 bfs.pushAndSetReached(s); 547 DistanceMap<ResGW> dist(res_graph); 548 while ( !bfs.finished() ) { 549 ResGWOutEdgeIt e=bfs; 550 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 551 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); 552 } 553 ++bfs; 554 } //computing distances from s in the residual graph 555 556 //Subgraph containing the edges on some shortest paths 557 typedef SubGraphWrapper<ResGW, DistanceMap<ResGW> > FilterResGW; 558 FilterResGW filter_res_graph(res_graph, dist); 559 560 //Subgraph, which is able to delete edges which are already 561 //met by the dfs 562 typename FilterResGW::NodeMap<typename FilterResGW::OutEdgeIt> 563 first_out_edges(filter_res_graph); 564 typename FilterResGW::NodeIt v; 565 for(filter_res_graph.first(v); filter_res_graph.valid(v); 566 filter_res_graph.next(v)) 567 { 568 typename FilterResGW::OutEdgeIt e; 569 filter_res_graph.first(e, v); 570 first_out_edges.set(v, e); 571 } 572 typedef ErasingFirstGraphWrapper<FilterResGW, typename FilterResGW:: 573 NodeMap<typename FilterResGW::OutEdgeIt> > ErasingResGW; 574 ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges); 575 576 bool __augment=true; 577 578 while (__augment) { 579 580 __augment=false; 581 //computing blocking flow with dfs 582 typedef typename ErasingResGW::NodeMap<bool> BlockingReachedMap; 583 DfsIterator5< ErasingResGW, BlockingReachedMap > 584 dfs(erasing_res_graph); 585 typename ErasingResGW::NodeMap<typename ErasingResGW::OutEdgeIt> 586 pred(erasing_res_graph); 587 pred.set(s, INVALID); 588 //invalid iterators for sources 589 590 typename ErasingResGW::NodeMap<Number> free(erasing_res_graph); 591 592 dfs.pushAndSetReached(s); 593 while (!dfs.finished()) { 594 ++dfs; 595 if (erasing_res_graph.valid( 596 /*typename ErasingResGW::OutEdgeIt*/(dfs))) 597 { 598 if (dfs.isBNodeNewlyReached()) { 599 600 typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs); 601 typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs); 602 603 pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs)); 604 if (erasing_res_graph.valid(pred.get(v))) { 605 free.set(w, std::min(free.get(v), res_graph.resCap(dfs))); 606 } else { 607 free.set(w, res_graph.resCap(dfs)); 608 } 609 610 if (w==t) { 611 __augment=true; 612 _augment=true; 613 break; 614 } 615 } else { 616 erasing_res_graph.erase(dfs); 617 } 618 } 619 } 620 621 if (__augment) { 622 typename ErasingResGW::Node n=t; 623 Number augment_value=free.get(n); 624 while (erasing_res_graph.valid(pred.get(n))) { 625 typename ErasingResGW::OutEdgeIt e=pred.get(n); 626 res_graph.augment(e, augment_value); 627 n=erasing_res_graph.tail(e); 628 if (res_graph.resCap(e)==0) 629 erasing_res_graph.erase(e); 630 } 631 } 632 633 } //while (__augment) 535 634 536 635 return _augment; … … 625 724 // return _augment; 626 725 // } 627 // void run() { 628 // //int num_of_augmentations=0; 629 // while (augmentOnShortestPath()) { 630 // //while (augmentOnBlockingFlow<MutableGraph>()) { 631 // //std::cout << ++num_of_augmentations << " "; 632 // //std::cout<<std::endl; 633 // } 634 // } 635 // template<typename MutableGraph> void run() { 636 // //int num_of_augmentations=0; 637 // //while (augmentOnShortestPath()) { 638 // while (augmentOnBlockingFlow<MutableGraph>()) { 639 // //std::cout << ++num_of_augmentations << " "; 640 // //std::cout<<std::endl; 641 // } 642 // } 726 727 void run() { 728 //int num_of_augmentations=0; 729 while (augmentOnShortestPath()) { 730 //while (augmentOnBlockingFlow<MutableGraph>()) { 731 //std::cout << ++num_of_augmentations << " "; 732 //std::cout<<std::endl; 733 } 734 } 735 736 template<typename MutableGraph> void run() { 737 //int num_of_augmentations=0; 738 //while (augmentOnShortestPath()) { 739 while (augmentOnBlockingFlow<MutableGraph>()) { 740 //std::cout << ++num_of_augmentations << " "; 741 //std::cout<<std::endl; 742 } 743 } 744 643 745 Number flowValue() { 644 746 Number a=0; … … 649 751 return a; 650 752 } 753 651 754 }; 652 755 … … 685 788 686 789 // typedef typename AugGraph::NodeMap<bool> ReachedMap; 687 // BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);790 // BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > bfs(res_graph); 688 791 // typename AugGraph::NodeMap<AugEdge> pred(res_graph); 689 792 // for(NodeIt s=G>template first<NodeIt>(); G>valid(s); G>next(s)) { … … 693 796 // //u+=flow>get(e); 694 797 // //if (u<1) { 695 // res_bfs.pushAndSetReached(s);798 // bfs.pushAndSetReached(s); 696 799 // pred.set(s, AugEdge(INVALID)); 697 800 // //} … … 703 806 // Node n; 704 807 // //searching for augmenting path 705 // while ( ! res_bfs.finished() ) {706 // AugOutEdgeIt e= res_bfs;707 // if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {808 // while ( !bfs.finished() ) { 809 // AugOutEdgeIt e=bfs; 810 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 708 811 // Node v=res_graph.tail(e); 709 812 // Node w=res_graph.head(e); … … 726 829 // } 727 830 728 // ++ res_bfs;831 // ++bfs; 729 832 // } //end of searching augmenting path 730 833 … … 763 866 // // u+=flow>get(e); 764 867 // // if (u<1) { 765 // // res_bfs.pushAndSetReached(s);868 // // bfs.pushAndSetReached(s); 766 869 // // //pred.set(s, AugEdge(INVALID)); 767 870 // // } … … 1057 1160 1058 1161 // // typedef typename AugGraph::NodeMap<bool> ReachedMap; 1059 // // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);1162 // // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph); 1060 1163 // // for(typename std::list<Node>::const_iterator i=S.begin(); 1061 1164 // // i!=S.end(); ++i) { 1062 // // res_bfs.pushAndSetReached(*i);1165 // // bfs.pushAndSetReached(*i); 1063 1166 // // } 1064 // // // res_bfs.pushAndSetReached(s);1167 // // //bfs.pushAndSetReached(s); 1065 1168 1066 1169 // // typename AugGraph::NodeMap<AugEdge> pred(res_graph); … … 1070 1173 1071 1174 // // //searching for augmenting path 1072 // // while ( ! res_bfs.finished() ) {1073 // // AugOutEdgeIt e=/*AugOutEdgeIt*/( res_bfs);1074 // // if (e.valid() && res_bfs.isBNodeNewlyReached()) {1175 // // while ( !bfs.finished() ) { 1176 // // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); 1177 // // if (e.valid() && bfs.isBNodeNewlyReached()) { 1075 1178 // // Node v=res_graph.tail(e); 1076 1179 // // Node w=res_graph.head(e); … … 1088 1191 // // } 1089 1192 1090 // // ++ res_bfs;1193 // // ++bfs; 1091 1194 // // } //end of searching augmenting path 1092 1195
Note: See TracChangeset
for help on using the changeset viewer.