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

 3 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 
src/work/marci/edmonds_karp_demo.cc
r268 r269 91 91 92 92 { 93 //std::cout << "SmartGraph..." << std::endl;94 93 typedef TrivGraphWrapper<const Graph> GW; 95 94 GW gw(G); … … 123 122 124 123 { 125 //std::cout << "SmartGraph..." << std::endl;126 124 typedef TrivGraphWrapper<const Graph> GW; 127 125 GW gw(G); … … 154 152 } 155 153 156 // { 157 // std::cout << "edmonds karp demo (onthefly blocking flow augmentation)..." << std::endl; 158 // Graph::EdgeMap<int> flow(G); //0 flow 159 160 // Timer ts; 161 // ts.reset(); 162 163 // MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap); 164 // int i=0; 165 // while (max_flow_test.augmentOnBlockingFlow2()) { 166 // // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 167 // // std::cout<<"("<<G.tail(e)<< ""<<flow.get(e)<<">"<<G.head(e)<<") "; 168 // // } 169 // // std::cout<<std::endl; 170 // ++i; 171 // } 172 173 // // std::cout << "maximum flow: "<< std::endl; 174 // // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 175 // // std::cout<<"("<<G.tail(e)<< ""<<flow.get(e)<<">"<<G.head(e)<<") "; 176 // // } 177 // // std::cout<<std::endl; 178 // std::cout << "elapsed time: " << ts << std::endl; 179 // std::cout << "number of augmentation phases: " << i << std::endl; 180 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 181 // } 154 { 155 typedef TrivGraphWrapper<const Graph> GW; 156 GW gw(G); 157 std::cout << "edmonds karp demo (onthefly blocking flow augmentation)..." << std::endl; 158 GW::EdgeMap<int> flow(G); //0 flow 159 160 Timer ts; 161 ts.reset(); 162 163 typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW; 164 EMW cw(cap); 165 MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw); 166 int i=0; 167 while (max_flow_test.augmentOnBlockingFlow2()) { 168 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 169 // std::cout<<"("<<G.tail(e)<< ""<<flow.get(e)<<">"<<G.head(e)<<") "; 170 // } 171 // std::cout<<std::endl; 172 ++i; 173 } 174 175 // std::cout << "maximum flow: "<< std::endl; 176 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 177 // std::cout<<"("<<G.tail(e)<< ""<<flow.get(e)<<">"<<G.head(e)<<") "; 178 // } 179 // std::cout<<std::endl; 180 std::cout << "elapsed time: " << ts << std::endl; 181 std::cout << "number of augmentation phases: " << i << std::endl; 182 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 183 } 182 184 183 185 { … … 190 192 ts.reset(); 191 193 192 //CM cm;193 194 typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW; 194 195 EMW cw(cap); 
src/work/marci/graph_wrapper.h
r266 r269 1000 1000 OutEdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() { 1001 1001 resG.gw.first(out, v); 1002 while( resG.gw.valid(out) && !(resG. free(out)>0) ) { resG.gw.next(out); }1002 while( resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); } 1003 1003 if (!resG.gw.valid(out)) { 1004 1004 out_or_in=0; 1005 1005 resG.gw.first(in, v); 1006 while( resG.gw.valid(in) && !(resG. free(in)>0) ) { resG.gw.next(in); }1006 while( resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); } 1007 1007 } 1008 1008 } … … 1012 1012 // Node v=/*resG>*/G>aNode(out); 1013 1013 // ++out; 1014 // while( out.valid() && !(Edge:: free()>0) ) { ++out; }1014 // while( out.valid() && !(Edge::resCap()>0) ) { ++out; } 1015 1015 // if (!out.valid()) { 1016 1016 // out_or_in=0; 1017 1017 // G>first(in, v); 1018 // while( in.valid() && !(Edge:: free()>0) ) { ++in; }1018 // while( in.valid() && !(Edge::resCap()>0) ) { ++in; } 1019 1019 // } 1020 1020 // } else { 1021 1021 // ++in; 1022 // while( in.valid() && !(Edge:: free()>0) ) { ++in; }1022 // while( in.valid() && !(Edge::resCap()>0) ) { ++in; } 1023 1023 // } 1024 1024 // return *this; … … 1038 1038 EdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG) : Edge() { 1039 1039 resG.gw.first(v); 1040 if (resG.gw.valid(v)) resG.gw.first(out, v); else out= /*OldOutEdgeIt*/(INVALID);1041 while (resG.gw.valid(out) && !(resG. free(out)>0) ) { resG.gw.next(out); }1040 if (resG.gw.valid(v)) resG.gw.first(out, v); else out=INVALID; 1041 while (resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); } 1042 1042 while (resG.gw.valid(v) && !resG.gw.valid(out)) { 1043 1043 resG.gw.next(v); 1044 1044 if (resG.gw.valid(v)) resG.gw.first(out, v); 1045 while (resG.gw.valid(out) && !(resG. free(out)>0) ) { resG.gw.next(out); }1045 while (resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); } 1046 1046 } 1047 1047 if (!resG.gw.valid(out)) { 1048 1048 out_or_in=0; 1049 1049 resG.gw.first(v); 1050 if (resG.gw.valid(v)) resG.gw.first(in, v); else in= /*OldInEdgeIt*/(INVALID);1051 while (resG.gw.valid(in) && !(resG. free(in)>0) ) { resG.gw.next(in); }1050 if (resG.gw.valid(v)) resG.gw.first(in, v); else in=INVALID; 1051 while (resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); } 1052 1052 while (resG.gw.valid(v) && !resG.gw.valid(in)) { 1053 1053 resG.gw.next(v); 1054 1054 if (resG.gw.valid(v)) resG.gw.first(in, v); 1055 while (resG.gw.valid(in) && !(resG. free(in)>0) ) { resG.gw.next(in); }1055 while (resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); } 1056 1056 } 1057 1057 } … … 1060 1060 // if (out_or_in) { 1061 1061 // ++out; 1062 // while (out.valid() && !(Edge:: free()>0) ) { ++out; }1062 // while (out.valid() && !(Edge::resCap()>0) ) { ++out; } 1063 1063 // while (v.valid() && !out.valid()) { 1064 1064 // ++v; 1065 1065 // if (v.valid()) G>first(out, v); 1066 // while (out.valid() && !(Edge:: free()>0) ) { ++out; }1066 // while (out.valid() && !(Edge::resCap()>0) ) { ++out; } 1067 1067 // } 1068 1068 // if (!out.valid()) { … … 1070 1070 // G>first(v); 1071 1071 // if (v.valid()) G>first(in, v); else in=OldInEdgeIt(); 1072 // while (in.valid() && !(Edge:: free()>0) ) { ++in; }1072 // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } 1073 1073 // while (v.valid() && !in.valid()) { 1074 1074 // ++v; 1075 1075 // if (v.valid()) G>first(in, v); 1076 // while (in.valid() && !(Edge:: free()>0) ) { ++in; }1076 // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } 1077 1077 // } 1078 1078 // } 1079 1079 // } else { 1080 1080 // ++in; 1081 // while (in.valid() && !(Edge:: free()>0) ) { ++in; }1081 // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } 1082 1082 // while (v.valid() && !in.valid()) { 1083 1083 // ++v; 1084 1084 // if (v.valid()) G>first(in, v); 1085 // while (in.valid() && !(Edge:: free()>0) ) { ++in; }1085 // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } 1086 1086 // } 1087 1087 // } … … 1106 1106 Node v=gw.aNode(e.out); 1107 1107 gw.next(e.out); 1108 while( gw.valid(e.out) && !( free(e.out)>0) ) { gw.next(e.out); }1108 while( gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); } 1109 1109 if (!gw.valid(e.out)) { 1110 1110 e.out_or_in=0; 1111 1111 gw.first(e.in, v); 1112 while( gw.valid(e.in) && !( free(e.in)>0) ) { gw.next(e.in); }1112 while( gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); } 1113 1113 } 1114 1114 } else { 1115 1115 gw.next(e.in); 1116 while( gw.valid(e.in) && !( free(e.in)>0) ) { gw.next(e.in); }1116 while( gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); } 1117 1117 } 1118 1118 return e; … … 1122 1122 if (e.out_or_in) { 1123 1123 gw.next(e.out); 1124 while (gw.valid(e.out) && !( free(e.out)>0) ) { gw.next(e.out); }1124 while (gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); } 1125 1125 while (gw.valid(e.v) && !gw.valid(e.out)) { 1126 1126 gw.next(e.v); 1127 1127 if (gw.valid(e.v)) gw.first(e.out, e.v); 1128 while (gw.valid(e.out) && !( free(e.out)>0) ) { gw.next(e.out); }1128 while (gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); } 1129 1129 } 1130 1130 if (!gw.valid(e.out)) { 1131 1131 e.out_or_in=0; 1132 1132 gw.first(e.v); 1133 if (gw.valid(e.v)) gw.first(e.in, e.v); else e.in= /*OldInEdgeIt*/(INVALID);1134 while (gw.valid(e.in) && !( free(e.in)>0) ) { gw.next(e.in); }1133 if (gw.valid(e.v)) gw.first(e.in, e.v); else e.in=INVALID; 1134 while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); } 1135 1135 while (gw.valid(e.v) && !gw.valid(e.in)) { 1136 1136 gw.next(e.v); 1137 1137 if (gw.valid(e.v)) gw.first(e.in, e.v); 1138 while (gw.valid(e.in) && !( free(e.in)>0) ) { gw.next(e.in); }1138 while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); } 1139 1139 } 1140 1140 } 1141 1141 } else { 1142 1142 gw.next(e.in); 1143 while (gw.valid(e.in) && !( free(e.in)>0) ) { gw.next(e.in); }1143 while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); } 1144 1144 while (gw.valid(e.v) && !gw.valid(e.in)) { 1145 1145 gw.next(e.v); 1146 1146 if (gw.valid(e.v)) gw.first(e.in, e.v); 1147 while (gw.valid(e.in) && !( free(e.in)>0) ) { gw.next(e.in); }1147 while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); } 1148 1148 } 1149 1149 } … … 1194 1194 } 1195 1195 1196 Number free(const Edge& e) const {1196 Number resCap(const Edge& e) const { 1197 1197 if (e.out_or_in) 1198 1198 return (capacity>get(e.out)flow>get(e.out)); … … 1201 1201 } 1202 1202 1203 Number free(OldOutEdgeIt out) const {1203 Number resCap(OldOutEdgeIt out) const { 1204 1204 return (capacity>get(out)flow>get(out)); 1205 1205 } 1206 1206 1207 Number free(OldInEdgeIt in) const {1207 Number resCap(OldInEdgeIt in) const { 1208 1208 return (flow>get(in)); 1209 1209 } … … 1246 1246 } 1247 1247 }; 1248 }; 1249 1250 //Subgraph on the same nodeset and partial edgeset 1251 template<typename GraphWrapper, typename FirstOutEdgesMap> 1252 class ErasingFirstGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> { 1253 protected: 1254 FirstOutEdgesMap* first_out_edges; 1255 public: 1256 typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node; 1257 typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt; 1258 typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge; 1259 typedef typename GraphWrapperSkeleton<GraphWrapper>::EdgeIt EdgeIt; 1260 typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt InEdgeIt; 1261 typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt OutEdgeIt; 1262 1263 ErasingFirstGraphWrapper(GraphWrapper _gw, FirstOutEdgesMap& _first_out_edges) : 1264 GraphWrapperSkeleton<GraphWrapper>(_gw), first_out_edges(&_first_out_edges) { } 1265 1266 template<typename I> I& first(I& i) const { 1267 gw.first(i); 1268 //while (gw.valid(i) && !filter_map>get(i)) { gw.next(i); } 1269 return i; 1270 } 1271 OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { 1272 e=first_out_edges>get(n); 1273 return e; 1274 } 1275 template<typename I, typename P> I& first(I& i, const P& p) const { 1276 gw.first(i, p); 1277 //while (gw.valid(i) && !filter_map>get(i)) { gw.next(i); } 1278 return i; 1279 } 1280 1281 //template<typename I> I getNext(const I& i) const { 1282 // return gw.getNext(i); 1283 //} 1284 template<typename I> I& next(I &i) const { 1285 gw.next(i); 1286 //while (gw.valid(i) && !filter_map>get(i)) { gw.next(i); } 1287 return i; 1288 } 1289 1290 template< typename It > It first() const { 1291 It e; this>first(e); return e; } 1292 1293 template< typename It > It first(const Node& v) const { 1294 It e; this>first(e, v); return e; } 1295 1296 void erase(const OutEdgeIt& e) const { 1297 OutEdgeIt f=e; 1298 this>next(f); 1299 first_out_edges>set(this>tail(e), f); 1300 } 1248 1301 }; 1249 1302
Note: See TracChangeset
for help on using the changeset viewer.