Changeset 266:4cec4981dfd1 in lemon-0.x for src/work/edmonds_karp.h
- Timestamp:
- 03/30/04 19:16:53 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@372
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/edmonds_karp.h
r265 r266 248 248 249 249 250 template <typename Graph , typename Number, typename FlowMap, typename CapacityMap>250 template <typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap> 251 251 class MaxFlow { 252 252 public: 253 typedef typename Graph ::Node Node;254 typedef typename Graph ::Edge Edge;255 typedef typename Graph ::EdgeIt EdgeIt;256 typedef typename Graph ::OutEdgeIt OutEdgeIt;257 typedef typename Graph ::InEdgeIt InEdgeIt;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 258 259 259 private: 260 const Graph* G; 260 //const Graph* G; 261 GraphWrapper gw; 261 262 Node s; 262 263 Node t; 263 264 FlowMap* flow; 264 265 const CapacityMap* capacity; 265 typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph; 266 typedef ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap > 267 AugGraph; 266 268 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; 267 269 typedef typename AugGraph::Edge AugEdge; 268 270 269 271 public: 270 MaxFlow(const Graph & _G, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :271 G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }272 MaxFlow(const GraphWrapper& _gw, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) : 273 gw(_gw), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { } 272 274 bool augmentOnShortestPath() { 273 AugGraph res_graph( *G, *flow, *capacity);275 AugGraph res_graph(gw, *flow, *capacity); 274 276 bool _augment=false; 275 277 … … 314 316 } 315 317 316 // template<typename MutableGraph> bool augmentOnBlockingFlow() { 317 // bool _augment=false; 318 319 // AugGraph res_graph(*G, *flow, *capacity); 320 321 // typedef typename AugGraph::NodeMap<bool> ReachedMap; 322 // BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph); 323 324 // bfs.pushAndSetReached(s); 325 // typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's 326 // while ( !bfs.finished() ) { 327 // AugOutEdgeIt e=bfs; 328 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 329 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); 330 // } 331 332 // ++bfs; 333 // } //computing distances from s in the residual graph 334 335 // MutableGraph F; 336 // typename AugGraph::NodeMap<typename MutableGraph::Node> 337 // res_graph_to_F(res_graph); 338 // for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { 339 // res_graph_to_F.set(n, F.addNode()); 340 // } 341 342 // typename MutableGraph::Node sF=res_graph_to_F.get(s); 343 // typename MutableGraph::Node tF=res_graph_to_F.get(t); 344 345 // typename MutableGraph::EdgeMap<AugEdge> original_edge(F); 346 // typename MutableGraph::EdgeMap<Number> residual_capacity(F); 347 348 // //Making F to the graph containing the edges of the residual graph 349 // //which are in some shortest paths 350 // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) { 351 // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { 352 // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); 353 // original_edge.update(); 354 // original_edge.set(f, e); 355 // residual_capacity.update(); 356 // residual_capacity.set(f, res_graph.free(e)); 357 // } 358 // } 359 360 // bool __augment=true; 361 362 // while (__augment) { 363 // __augment=false; 364 // //computing blocking flow with dfs 365 // typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap; 366 // DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F); 367 // typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F); 368 // pred.set(sF, typename MutableGraph::Edge(INVALID)); 369 // //invalid iterators for sources 370 371 // typename MutableGraph::NodeMap<Number> free(F); 372 373 // dfs.pushAndSetReached(sF); 374 // while (!dfs.finished()) { 375 // ++dfs; 376 // if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { 377 // if (dfs.isBNodeNewlyReached()) { 378 // typename MutableGraph::Node v=F.aNode(dfs); 379 // typename MutableGraph::Node w=F.bNode(dfs); 380 // pred.set(w, dfs); 381 // if (F.valid(pred.get(v))) { 382 // free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); 383 // } else { 384 // free.set(w, residual_capacity.get(dfs)); 385 // } 386 // if (w==tF) { 387 // __augment=true; 388 // _augment=true; 389 // break; 390 // } 391 392 // } else { 393 // F.erase(typename MutableGraph::OutEdgeIt(dfs)); 394 // } 395 // } 396 // } 397 398 // if (__augment) { 399 // typename MutableGraph::Node n=tF; 400 // Number augment_value=free.get(tF); 401 // while (F.valid(pred.get(n))) { 402 // typename MutableGraph::Edge e=pred.get(n); 403 // res_graph.augment(original_edge.get(e), augment_value); 404 // n=F.tail(e); 405 // if (residual_capacity.get(e)==augment_value) 406 // F.erase(e); 407 // else 408 // residual_capacity.set(e, residual_capacity.get(e)-augment_value); 409 // } 410 // } 411 412 // } 413 414 // return _augment; 415 // } 416 417 template<typename GraphWrapper> 318 template<typename MapGraphWrapper> 418 319 class DistanceMap { 419 320 protected: 420 GraphWrapper gw;421 typename GraphWrapper::NodeMap<int> dist;321 MapGraphWrapper gw; 322 typename MapGraphWrapper::NodeMap<int> dist; 422 323 public: 423 DistanceMap(GraphWrapper& _gw) : gw(_gw), dist(_gw, _gw.nodeNum()) { } 424 //NodeMap(const ListGraph& _G, T a) : 425 //G(_G), container(G.node_id, a) { } 426 void set(const typename GraphWrapper::Node& n, int a) { dist[n]=a; } 427 int get(const typename GraphWrapper::Node& n) const { return dist[n]; } 428 bool get(const typename GraphWrapper::Edge& e) const { 324 DistanceMap(MapGraphWrapper& _gw) : gw(_gw), dist(_gw, _gw.nodeNum()) { } 325 void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; } 326 int get(const typename MapGraphWrapper::Node& n) const { return dist[n]; } 327 bool get(const typename MapGraphWrapper::Edge& e) const { 429 328 return (dist.get(gw.tail(e))<dist.get(gw.head(e))); 430 329 } 431 //typename std::vector<T>::reference operator[](Node n) {432 //return container[/*G.id(n)*/n.node->id]; }433 //typename std::vector<T>::const_reference operator[](Node n) const {434 //return container[/*G.id(n)*/n.node->id];435 330 }; 436 331 … … 438 333 bool _augment=false; 439 334 440 AugGraph res_graph( *G, *flow, *capacity);335 AugGraph res_graph(gw, *flow, *capacity); 441 336 442 337 typedef typename AugGraph::NodeMap<bool> ReachedMap; … … 454 349 } //computing distances from s in the residual graph 455 350 456 // MutableGraph F;457 // typename AugGraph::NodeMap<typename MutableGraph::Node>458 // res_graph_to_F(res_graph);459 // for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {460 // res_graph_to_F.set(n, F.addNode());461 // }462 463 // typename MutableGraph::Node sF=res_graph_to_F.get(s);464 // typename MutableGraph::Node tF=res_graph_to_F.get(t);465 466 // typename MutableGraph::EdgeMap<AugEdge> original_edge(F);467 // typename MutableGraph::EdgeMap<Number> residual_capacity(F);468 469 // //Making F to the graph containing the edges of the residual graph470 // //which are in some shortest paths471 // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {472 // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {473 // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));474 // original_edge.update();475 // original_edge.set(f, e);476 // residual_capacity.update();477 // residual_capacity.set(f, res_graph.free(e));478 // }479 // }480 481 351 MutableGraph F; 482 //typedef SubGraphWrapper<AugGraph, DistanceMap<AugGraph> > FilterResGraph;483 //FilterResGraph filter_res_graph(res_graph, dist);352 typedef SubGraphWrapper<AugGraph, DistanceMap<AugGraph> > FilterResGraph; 353 FilterResGraph filter_res_graph(res_graph, dist); 484 354 typename AugGraph::NodeMap<typename MutableGraph::Node> 485 355 res_graph_to_F(res_graph); … … 496 366 //Making F to the graph containing the edges of the residual graph 497 367 //which are in some shortest paths 498 for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); 499 res_graph.valid(e); 500 res_graph.next(e)) { 501 if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { 368 for(typename FilterResGraph::EdgeIt e=filter_res_graph.template first<typename FilterResGraph::EdgeIt>(); filter_res_graph.valid(e); filter_res_graph.next(e)) { 369 //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { 502 370 typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); 503 371 original_edge.update(); … … 505 373 residual_capacity.update(); 506 374 residual_capacity.set(f, res_graph.free(e)); 507 }375 //} 508 376 } 509 377 … … 565 433 } 566 434 567 template<typename MutableGraph> bool augmentOnBlockingFlow1() { 568 bool _augment=false; 569 570 AugGraph res_graph(*G, *flow, *capacity); 571 572 //bfs for distances on the residual graph 573 typedef typename AugGraph::NodeMap<bool> ReachedMap; 574 BfsIterator5< AugGraph, ReachedMap > bfs(res_graph); 575 bfs.pushAndSetReached(s); 576 typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's 577 578 //F will contain the physical copy of the residual graph 579 //with the set of edges which areon shortest paths 580 MutableGraph F; 581 typename AugGraph::NodeMap<typename MutableGraph::Node> 582 res_graph_to_F(res_graph); 583 for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { 584 res_graph_to_F.set(n, F.addNode()); 585 } 586 typename MutableGraph::Node sF=res_graph_to_F.get(s); 587 typename MutableGraph::Node tF=res_graph_to_F.get(t); 588 typename MutableGraph::EdgeMap<AugEdge> original_edge(F); 589 typename MutableGraph::EdgeMap<Number> residual_capacity(F); 590 591 while ( !bfs.finished() ) { 592 AugOutEdgeIt e=bfs; 593 if (res_graph.valid(e)) { 594 if (bfs.isBNodeNewlyReached()) { 595 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); 596 typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); 597 original_edge.update(); 598 original_edge.set(f, e); 599 residual_capacity.update(); 600 residual_capacity.set(f, res_graph.free(e)); 601 } else { 602 if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) { 603 typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); 604 original_edge.update(); 605 original_edge.set(f, e); 606 residual_capacity.update(); 607 residual_capacity.set(f, res_graph.free(e)); 608 } 609 } 610 } 611 ++bfs; 612 } //computing distances from s in the residual graph 613 614 bool __augment=true; 615 616 while (__augment) { 617 __augment=false; 618 //computing blocking flow with dfs 619 typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap; 620 DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F); 621 typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F); 622 pred.set(sF, typename MutableGraph::Edge(INVALID)); 623 //invalid iterators for sources 624 625 typename MutableGraph::NodeMap<Number> free(F); 626 627 dfs.pushAndSetReached(sF); 628 while (!dfs.finished()) { 629 ++dfs; 630 if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { 631 if (dfs.isBNodeNewlyReached()) { 632 typename MutableGraph::Node v=F.aNode(dfs); 633 typename MutableGraph::Node w=F.bNode(dfs); 634 pred.set(w, dfs); 635 if (F.valid(pred.get(v))) { 636 free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); 637 } else { 638 free.set(w, residual_capacity.get(dfs)); 639 } 640 if (w==tF) { 641 __augment=true; 642 _augment=true; 643 break; 644 } 645 646 } else { 647 F.erase(typename MutableGraph::OutEdgeIt(dfs)); 648 } 649 } 650 } 651 652 if (__augment) { 653 typename MutableGraph::Node n=tF; 654 Number augment_value=free.get(tF); 655 while (F.valid(pred.get(n))) { 656 typename MutableGraph::Edge e=pred.get(n); 657 res_graph.augment(original_edge.get(e), augment_value); 658 n=F.tail(e); 659 if (residual_capacity.get(e)==augment_value) 660 F.erase(e); 661 else 662 residual_capacity.set(e, residual_capacity.get(e)-augment_value); 663 } 664 } 665 666 } 667 668 return _augment; 669 } 670 bool augmentOnBlockingFlow2() { 671 bool _augment=false; 672 673 //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph; 674 typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph; 675 typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; 676 typedef typename EAugGraph::Edge EAugEdge; 677 678 EAugGraph res_graph(*G, *flow, *capacity); 679 680 //typedef typename EAugGraph::NodeMap<bool> ReachedMap; 681 BfsIterator5< 682 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, 683 /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/ 684 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph); 685 686 bfs.pushAndSetReached(s); 687 688 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>:: 689 NodeMap<int>& dist=res_graph.dist; 690 691 while ( !bfs.finished() ) { 692 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; 693 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 694 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); 695 } 696 ++bfs; 697 } //computing distances from s in the residual graph 698 699 bool __augment=true; 700 701 while (__augment) { 702 703 __augment=false; 704 //computing blocking flow with dfs 705 typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap; 706 DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap > 707 dfs(res_graph); 708 typename EAugGraph::NodeMap<EAugEdge> pred(res_graph); 709 pred.set(s, EAugEdge(INVALID)); 710 //invalid iterators for sources 711 712 typename EAugGraph::NodeMap<Number> free(res_graph); 713 714 dfs.pushAndSetReached(s); 715 while (!dfs.finished()) { 716 ++dfs; 717 if (res_graph.valid(EAugOutEdgeIt(dfs))) { 718 if (dfs.isBNodeNewlyReached()) { 719 720 typename EAugGraph::Node v=res_graph.aNode(dfs); 721 typename EAugGraph::Node w=res_graph.bNode(dfs); 722 723 pred.set(w, EAugOutEdgeIt(dfs)); 724 if (res_graph.valid(pred.get(v))) { 725 free.set(w, std::min(free.get(v), res_graph.free(dfs))); 726 } else { 727 free.set(w, res_graph.free(dfs)); 728 } 729 730 if (w==t) { 731 __augment=true; 732 _augment=true; 733 break; 734 } 735 } else { 736 res_graph.erase(dfs); 737 } 738 } 739 740 } 741 742 if (__augment) { 743 typename EAugGraph::Node n=t; 744 Number augment_value=free.get(t); 745 while (res_graph.valid(pred.get(n))) { 746 EAugEdge e=pred.get(n); 747 res_graph.augment(e, augment_value); 748 n=res_graph.tail(e); 749 if (res_graph.free(e)==0) 750 res_graph.erase(e); 751 } 752 } 753 754 } 755 756 return _augment; 757 } 758 void run() { 759 //int num_of_augmentations=0; 760 while (augmentOnShortestPath()) { 761 //while (augmentOnBlockingFlow<MutableGraph>()) { 762 //std::cout << ++num_of_augmentations << " "; 763 //std::cout<<std::endl; 764 } 765 } 766 template<typename MutableGraph> void run() { 767 //int num_of_augmentations=0; 768 //while (augmentOnShortestPath()) { 769 while (augmentOnBlockingFlow<MutableGraph>()) { 770 //std::cout << ++num_of_augmentations << " "; 771 //std::cout<<std::endl; 772 } 773 } 774 Number flowValue() { 775 Number a=0; 776 OutEdgeIt e; 777 for(G->/*getF*/first(e, s); G->valid(e); G->next(e)) { 778 a+=flow->get(e); 779 } 780 return a; 781 } 782 }; 783 784 785 template <typename Graph, typename Number, typename FlowMap, typename CapacityMap> 786 class MaxMatching { 787 public: 788 typedef typename Graph::Node Node; 789 typedef typename Graph::NodeIt NodeIt; 790 typedef typename Graph::Edge Edge; 791 typedef typename Graph::EdgeIt EdgeIt; 792 typedef typename Graph::OutEdgeIt OutEdgeIt; 793 typedef typename Graph::InEdgeIt InEdgeIt; 794 795 typedef typename Graph::NodeMap<bool> SMap; 796 typedef typename Graph::NodeMap<bool> TMap; 797 private: 798 const Graph* G; 799 SMap* S; 800 TMap* T; 801 //Node s; 802 //Node t; 803 FlowMap* flow; 804 const CapacityMap* capacity; 805 typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph; 806 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; 807 typedef typename AugGraph::Edge AugEdge; 808 typename Graph::NodeMap<int> used; //0 809 810 public: 811 MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) : 812 G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { } 813 bool augmentOnShortestPath() { 814 AugGraph res_graph(*G, *flow, *capacity); 815 bool _augment=false; 816 817 typedef typename AugGraph::NodeMap<bool> ReachedMap; 818 BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph); 819 typename AugGraph::NodeMap<AugEdge> pred(res_graph); 820 for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { 821 if ((S->get(s)) && (used.get(s)<1) ) { 822 //Number u=0; 823 //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) 824 //u+=flow->get(e); 825 //if (u<1) { 826 res_bfs.pushAndSetReached(s); 827 pred.set(s, AugEdge(INVALID)); 828 //} 829 } 830 } 831 832 typename AugGraph::NodeMap<Number> free(res_graph); 833 834 Node n; 835 //searching for augmenting path 836 while ( !res_bfs.finished() ) { 837 AugOutEdgeIt e=res_bfs; 838 if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) { 839 Node v=res_graph.tail(e); 840 Node w=res_graph.head(e); 841 pred.set(w, e); 842 if (res_graph.valid(pred.get(v))) { 843 free.set(w, std::min(free.get(v), res_graph.free(e))); 844 } else { 845 free.set(w, res_graph.free(e)); 846 } 847 n=res_graph.head(e); 848 if (T->get(n) && (used.get(n)<1) ) { 849 //Number u=0; 850 //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f)) 851 //u+=flow->get(f); 852 //if (u<1) { 853 _augment=true; 854 break; 855 //} 856 } 857 } 858 859 ++res_bfs; 860 } //end of searching augmenting path 861 862 if (_augment) { 863 //Node n=t; 864 used.set(n, 1); //mind2 vegen jav 865 Number augment_value=free.get(n); 866 while (res_graph.valid(pred.get(n))) { 867 AugEdge e=pred.get(n); 868 res_graph.augment(e, augment_value); 869 n=res_graph.tail(e); 870 } 871 used.set(n, 1); //mind2 vegen jav 872 } 873 874 return _augment; 875 } 876 877 // template<typename MutableGraph> bool augmentOnBlockingFlow() { 435 // template<typename MutableGraph> bool augmentOnBlockingFlow1() { 878 436 // bool _augment=false; 879 437 880 438 // AugGraph res_graph(*G, *flow, *capacity); 881 439 440 // //bfs for distances on the residual graph 882 441 // typedef typename AugGraph::NodeMap<bool> ReachedMap; 883 // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph); 884 885 886 887 888 889 // //typename AugGraph::NodeMap<AugEdge> pred(res_graph); 890 // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { 891 // if (S->get(s)) { 892 // Number u=0; 893 // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) 894 // u+=flow->get(e); 895 // if (u<1) { 896 // res_bfs.pushAndSetReached(s); 897 // //pred.set(s, AugEdge(INVALID)); 898 // } 899 // } 900 // } 901 902 903 904 905 // //bfs.pushAndSetReached(s); 442 // BfsIterator5< AugGraph, ReachedMap > bfs(res_graph); 443 // bfs.pushAndSetReached(s); 906 444 // typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's 907 // while ( !bfs.finished() ) { 908 // AugOutEdgeIt e=bfs; 909 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 910 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); 911 // } 912 913 // ++bfs; 914 // } //computing distances from s in the residual graph 915 445 446 // //F will contain the physical copy of the residual graph 447 // //with the set of edges which areon shortest paths 916 448 // MutableGraph F; 917 449 // typename AugGraph::NodeMap<typename MutableGraph::Node> … … 920 452 // res_graph_to_F.set(n, F.addNode()); 921 453 // } 922 923 454 // typename MutableGraph::Node sF=res_graph_to_F.get(s); 924 455 // typename MutableGraph::Node tF=res_graph_to_F.get(t); 925 926 456 // typename MutableGraph::EdgeMap<AugEdge> original_edge(F); 927 457 // typename MutableGraph::EdgeMap<Number> residual_capacity(F); 928 458 929 // //Making F to the graph containing the edges of the residual graph 930 // //which are in some shortest paths 931 // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) { 932 // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { 933 // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); 934 // original_edge.update(); 935 // original_edge.set(f, e); 936 // residual_capacity.update(); 937 // residual_capacity.set(f, res_graph.free(e)); 938 // } 939 // } 459 // while ( !bfs.finished() ) { 460 // AugOutEdgeIt e=bfs; 461 // if (res_graph.valid(e)) { 462 // if (bfs.isBNodeNewlyReached()) { 463 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); 464 // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); 465 // original_edge.update(); 466 // original_edge.set(f, e); 467 // residual_capacity.update(); 468 // residual_capacity.set(f, res_graph.free(e)); 469 // } else { 470 // if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) { 471 // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); 472 // original_edge.update(); 473 // original_edge.set(f, e); 474 // residual_capacity.update(); 475 // residual_capacity.set(f, res_graph.free(e)); 476 // } 477 // } 478 // } 479 // ++bfs; 480 // } //computing distances from s in the residual graph 940 481 941 482 // bool __augment=true; … … 944 485 // __augment=false; 945 486 // //computing blocking flow with dfs 946 // typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;947 // DfsIterator 4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);487 // typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap; 488 // DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F); 948 489 // typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F); 949 490 // pred.set(sF, typename MutableGraph::Edge(INVALID)); … … 995 536 // return _augment; 996 537 // } 997 bool augmentOnBlockingFlow2() { 998 bool _augment=false; 999 1000 //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph; 1001 typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph; 1002 typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; 1003 typedef typename EAugGraph::Edge EAugEdge; 1004 1005 EAugGraph res_graph(*G, *flow, *capacity); 1006 1007 //typedef typename EAugGraph::NodeMap<bool> ReachedMap; 1008 BfsIterator5< 1009 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, 1010 /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/ 1011 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph); 1012 1013 1014 //typename AugGraph::NodeMap<AugEdge> pred(res_graph); 1015 for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { 1016 if (S->get(s)) { 1017 Number u=0; 1018 for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) 1019 u+=flow->get(e); 1020 if (u<1) { 1021 bfs.pushAndSetReached(s); 1022 //pred.set(s, AugEdge(INVALID)); 1023 } 1024 } 1025 } 1026 538 // bool augmentOnBlockingFlow2() { 539 // bool _augment=false; 540 541 // //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph; 542 // typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph; 543 // typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; 544 // typedef typename EAugGraph::Edge EAugEdge; 545 546 // EAugGraph res_graph(*G, *flow, *capacity); 547 548 // //typedef typename EAugGraph::NodeMap<bool> ReachedMap; 549 // BfsIterator5< 550 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, 551 // /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/ 552 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph); 1027 553 1028 //bfs.pushAndSetReached(s); 1029 1030 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>:: 1031 NodeMap<int>& dist=res_graph.dist; 1032 1033 while ( !bfs.finished() ) { 1034 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; 1035 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 1036 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); 1037 } 1038 ++bfs; 1039 } //computing distances from s in the residual graph 1040 1041 bool __augment=true; 1042 1043 while (__augment) { 1044 1045 __augment=false; 1046 //computing blocking flow with dfs 1047 typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap; 1048 DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap > 1049 dfs(res_graph); 1050 typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID); 1051 //pred.set(s, EAugEdge(INVALID)); 1052 //invalid iterators for sources 1053 1054 typename EAugGraph::NodeMap<Number> free(res_graph); 1055 1056 1057 //typename AugGraph::NodeMap<AugEdge> pred(res_graph); 1058 for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { 1059 if (S->get(s)) { 1060 Number u=0; 1061 for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) 1062 u+=flow->get(e); 1063 if (u<1) { 1064 dfs.pushAndSetReached(s); 1065 //pred.set(s, AugEdge(INVALID)); 1066 } 1067 } 1068 } 1069 1070 1071 1072 //dfs.pushAndSetReached(s); 1073 typename EAugGraph::Node n; 1074 while (!dfs.finished()) { 1075 ++dfs; 1076 if (res_graph.valid(EAugOutEdgeIt(dfs))) { 1077 if (dfs.isBNodeNewlyReached()) { 554 // bfs.pushAndSetReached(s); 555 556 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>:: 557 // NodeMap<int>& dist=res_graph.dist; 558 559 // while ( !bfs.finished() ) { 560 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; 561 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 562 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); 563 // } 564 // ++bfs; 565 // } //computing distances from s in the residual graph 566 567 // bool __augment=true; 568 569 // while (__augment) { 570 571 // __augment=false; 572 // //computing blocking flow with dfs 573 // typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap; 574 // DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap > 575 // dfs(res_graph); 576 // typename EAugGraph::NodeMap<EAugEdge> pred(res_graph); 577 // pred.set(s, EAugEdge(INVALID)); 578 // //invalid iterators for sources 579 580 // typename EAugGraph::NodeMap<Number> free(res_graph); 581 582 // dfs.pushAndSetReached(s); 583 // while (!dfs.finished()) { 584 // ++dfs; 585 // if (res_graph.valid(EAugOutEdgeIt(dfs))) { 586 // if (dfs.isBNodeNewlyReached()) { 1078 587 1079 typename EAugGraph::Node v=res_graph.aNode(dfs); 1080 typename EAugGraph::Node w=res_graph.bNode(dfs); 1081 1082 pred.set(w, EAugOutEdgeIt(dfs)); 1083 if (res_graph.valid(pred.get(v))) { 1084 free.set(w, std::min(free.get(v), res_graph.free(dfs))); 1085 } else { 1086 free.set(w, res_graph.free(dfs)); 1087 } 1088 1089 n=w; 1090 if (T->get(w)) { 1091 Number u=0; 1092 for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f)) 1093 u+=flow->get(f); 1094 if (u<1) { 1095 __augment=true; 1096 _augment=true; 1097 break; 1098 } 1099 } 1100 } else { 1101 res_graph.erase(dfs); 1102 } 1103 } 1104 1105 } 1106 1107 if (__augment) { 1108 // typename EAugGraph::Node n=t; 1109 Number augment_value=free.get(n); 1110 while (res_graph.valid(pred.get(n))) { 1111 EAugEdge e=pred.get(n); 1112 res_graph.augment(e, augment_value); 1113 n=res_graph.tail(e); 1114 if (res_graph.free(e)==0) 1115 res_graph.erase(e); 1116 } 1117 } 588 // typename EAugGraph::Node v=res_graph.aNode(dfs); 589 // typename EAugGraph::Node w=res_graph.bNode(dfs); 590 591 // pred.set(w, EAugOutEdgeIt(dfs)); 592 // if (res_graph.valid(pred.get(v))) { 593 // free.set(w, std::min(free.get(v), res_graph.free(dfs))); 594 // } else { 595 // free.set(w, res_graph.free(dfs)); 596 // } 597 598 // if (w==t) { 599 // __augment=true; 600 // _augment=true; 601 // break; 602 // } 603 // } else { 604 // res_graph.erase(dfs); 605 // } 606 // } 607 608 // } 609 610 // if (__augment) { 611 // typename EAugGraph::Node n=t; 612 // Number augment_value=free.get(t); 613 // while (res_graph.valid(pred.get(n))) { 614 // EAugEdge e=pred.get(n); 615 // res_graph.augment(e, augment_value); 616 // n=res_graph.tail(e); 617 // if (res_graph.free(e)==0) 618 // res_graph.erase(e); 619 // } 620 // } 1118 621 1119 }622 // } 1120 623 1121 return _augment;1122 }1123 void run() {1124 //int num_of_augmentations=0;1125 while (augmentOnShortestPath()) {1126 //while (augmentOnBlockingFlow<MutableGraph>()) {1127 //std::cout << ++num_of_augmentations << " ";1128 //std::cout<<std::endl;1129 }1130 }624 // return _augment; 625 // } 626 // void run() { 627 // //int num_of_augmentations=0; 628 // while (augmentOnShortestPath()) { 629 // //while (augmentOnBlockingFlow<MutableGraph>()) { 630 // //std::cout << ++num_of_augmentations << " "; 631 // //std::cout<<std::endl; 632 // } 633 // } 1131 634 // template<typename MutableGraph> void run() { 1132 635 // //int num_of_augmentations=0; … … 1136 639 // //std::cout<<std::endl; 1137 640 // } 1138 // } 641 // } 1139 642 Number flowValue() { 1140 643 Number a=0; 1141 EdgeIt e;1142 for( G->/*getF*/first(e); G->valid(e); G->next(e)) {644 OutEdgeIt e; 645 for(gw.first(e, s); gw.valid(e); gw.next(e)) { 1143 646 a+=flow->get(e); 1144 647 } … … 1148 651 1149 652 1150 1151 1152 1153 1154 653 // template <typename Graph, typename Number, typename FlowMap, typename CapacityMap> 1155 // class Max Flow2{654 // class MaxMatching { 1156 655 // public: 1157 656 // typedef typename Graph::Node Node; 657 // typedef typename Graph::NodeIt NodeIt; 1158 658 // typedef typename Graph::Edge Edge; 1159 659 // typedef typename Graph::EdgeIt EdgeIt; 1160 660 // typedef typename Graph::OutEdgeIt OutEdgeIt; 1161 661 // typedef typename Graph::InEdgeIt InEdgeIt; 662 663 // typedef typename Graph::NodeMap<bool> SMap; 664 // typedef typename Graph::NodeMap<bool> TMap; 1162 665 // private: 1163 // const Graph& G; 1164 // std::list<Node>& S; 1165 // std::list<Node>& T; 1166 // FlowMap& flow; 1167 // const CapacityMap& capacity; 666 // const Graph* G; 667 // SMap* S; 668 // TMap* T; 669 // //Node s; 670 // //Node t; 671 // FlowMap* flow; 672 // const CapacityMap* capacity; 1168 673 // typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph; 1169 674 // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; 1170 675 // typedef typename AugGraph::Edge AugEdge; 1171 // typename Graph::NodeMap< bool> SMap;1172 // typename Graph::NodeMap<bool> TMap; 676 // typename Graph::NodeMap<int> used; //0 677 1173 678 // public: 1174 // MaxFlow2(const Graph& _G, std::list<Node>& _S, std::list<Node>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) { 1175 // for(typename std::list<Node>::const_iterator i=S.begin(); 1176 // i!=S.end(); ++i) { 1177 // SMap.set(*i, true); 1178 // } 1179 // for (typename std::list<Node>::const_iterator i=T.begin(); 1180 // i!=T.end(); ++i) { 1181 // TMap.set(*i, true); 1182 // } 1183 // } 1184 // bool augment() { 1185 // AugGraph res_graph(G, flow, capacity); 679 // MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) : 680 // G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { } 681 // bool augmentOnShortestPath() { 682 // AugGraph res_graph(*G, *flow, *capacity); 1186 683 // bool _augment=false; 1187 // Node reached_t_node;1188 684 1189 685 // typedef typename AugGraph::NodeMap<bool> ReachedMap; 1190 // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph); 1191 // for(typename std::list<Node>::const_iterator i=S.begin(); 1192 // i!=S.end(); ++i) { 1193 // res_bfs.pushAndSetReached(*i); 686 // BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph); 687 // typename AugGraph::NodeMap<AugEdge> pred(res_graph); 688 // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { 689 // if ((S->get(s)) && (used.get(s)<1) ) { 690 // //Number u=0; 691 // //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) 692 // //u+=flow->get(e); 693 // //if (u<1) { 694 // res_bfs.pushAndSetReached(s); 695 // pred.set(s, AugEdge(INVALID)); 696 // //} 697 // } 1194 698 // } 1195 // //res_bfs.pushAndSetReached(s);1196 1197 // typename AugGraph::NodeMap<AugEdge> pred(res_graph);1198 // //filled up with invalid iterators1199 699 1200 700 // typename AugGraph::NodeMap<Number> free(res_graph); 1201 701 702 // Node n; 1202 703 // //searching for augmenting path 1203 704 // while ( !res_bfs.finished() ) { 1204 // AugOutEdgeIt e= /*AugOutEdgeIt*/(res_bfs);1205 // if ( e.valid() && res_bfs.isBNodeNewlyReached()) {705 // AugOutEdgeIt e=res_bfs; 706 // if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) { 1206 707 // Node v=res_graph.tail(e); 1207 708 // Node w=res_graph.head(e); 1208 709 // pred.set(w, e); 1209 // if ( pred.get(v).valid()) {1210 // free.set(w, std::min(free.get(v), e.free()));710 // if (res_graph.valid(pred.get(v))) { 711 // free.set(w, std::min(free.get(v), res_graph.free(e))); 1211 712 // } else { 1212 // free.set(w, e.free());713 // free.set(w, res_graph.free(e)); 1213 714 // } 1214 // if (TMap.get(res_graph.head(e))) { 1215 // _augment=true; 1216 // reached_t_node=res_graph.head(e); 1217 // break; 715 // n=res_graph.head(e); 716 // if (T->get(n) && (used.get(n)<1) ) { 717 // //Number u=0; 718 // //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f)) 719 // //u+=flow->get(f); 720 // //if (u<1) { 721 // _augment=true; 722 // break; 723 // //} 1218 724 // } 1219 725 // } … … 1223 729 1224 730 // if (_augment) { 1225 // Node n=reached_t_node; 1226 // Number augment_value=free.get(reached_t_node); 1227 // while (pred.get(n).valid()) { 731 // //Node n=t; 732 // used.set(n, 1); //mind2 vegen jav 733 // Number augment_value=free.get(n); 734 // while (res_graph.valid(pred.get(n))) { 1228 735 // AugEdge e=pred.get(n); 1229 // e.augment(augment_value);736 // res_graph.augment(e, augment_value); 1230 737 // n=res_graph.tail(e); 1231 738 // } 739 // used.set(n, 1); //mind2 vegen jav 1232 740 // } 1233 741 742 // return _augment; 743 // } 744 745 // // template<typename MutableGraph> bool augmentOnBlockingFlow() { 746 // // bool _augment=false; 747 748 // // AugGraph res_graph(*G, *flow, *capacity); 749 750 // // typedef typename AugGraph::NodeMap<bool> ReachedMap; 751 // // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph); 752 753 754 755 756 757 // // //typename AugGraph::NodeMap<AugEdge> pred(res_graph); 758 // // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { 759 // // if (S->get(s)) { 760 // // Number u=0; 761 // // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) 762 // // u+=flow->get(e); 763 // // if (u<1) { 764 // // res_bfs.pushAndSetReached(s); 765 // // //pred.set(s, AugEdge(INVALID)); 766 // // } 767 // // } 768 // // } 769 770 771 772 773 // // //bfs.pushAndSetReached(s); 774 // // typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's 775 // // while ( !bfs.finished() ) { 776 // // AugOutEdgeIt e=bfs; 777 // // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 778 // // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); 779 // // } 780 781 // // ++bfs; 782 // // } //computing distances from s in the residual graph 783 784 // // MutableGraph F; 785 // // typename AugGraph::NodeMap<typename MutableGraph::Node> 786 // // res_graph_to_F(res_graph); 787 // // for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { 788 // // res_graph_to_F.set(n, F.addNode()); 789 // // } 790 791 // // typename MutableGraph::Node sF=res_graph_to_F.get(s); 792 // // typename MutableGraph::Node tF=res_graph_to_F.get(t); 793 794 // // typename MutableGraph::EdgeMap<AugEdge> original_edge(F); 795 // // typename MutableGraph::EdgeMap<Number> residual_capacity(F); 796 797 // // //Making F to the graph containing the edges of the residual graph 798 // // //which are in some shortest paths 799 // // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) { 800 // // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { 801 // // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); 802 // // original_edge.update(); 803 // // original_edge.set(f, e); 804 // // residual_capacity.update(); 805 // // residual_capacity.set(f, res_graph.free(e)); 806 // // } 807 // // } 808 809 // // bool __augment=true; 810 811 // // while (__augment) { 812 // // __augment=false; 813 // // //computing blocking flow with dfs 814 // // typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap; 815 // // DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F); 816 // // typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F); 817 // // pred.set(sF, typename MutableGraph::Edge(INVALID)); 818 // // //invalid iterators for sources 819 820 // // typename MutableGraph::NodeMap<Number> free(F); 821 822 // // dfs.pushAndSetReached(sF); 823 // // while (!dfs.finished()) { 824 // // ++dfs; 825 // // if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { 826 // // if (dfs.isBNodeNewlyReached()) { 827 // // typename MutableGraph::Node v=F.aNode(dfs); 828 // // typename MutableGraph::Node w=F.bNode(dfs); 829 // // pred.set(w, dfs); 830 // // if (F.valid(pred.get(v))) { 831 // // free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); 832 // // } else { 833 // // free.set(w, residual_capacity.get(dfs)); 834 // // } 835 // // if (w==tF) { 836 // // __augment=true; 837 // // _augment=true; 838 // // break; 839 // // } 840 841 // // } else { 842 // // F.erase(typename MutableGraph::OutEdgeIt(dfs)); 843 // // } 844 // // } 845 // // } 846 847 // // if (__augment) { 848 // // typename MutableGraph::Node n=tF; 849 // // Number augment_value=free.get(tF); 850 // // while (F.valid(pred.get(n))) { 851 // // typename MutableGraph::Edge e=pred.get(n); 852 // // res_graph.augment(original_edge.get(e), augment_value); 853 // // n=F.tail(e); 854 // // if (residual_capacity.get(e)==augment_value) 855 // // F.erase(e); 856 // // else 857 // // residual_capacity.set(e, residual_capacity.get(e)-augment_value); 858 // // } 859 // // } 860 861 // // } 862 863 // // return _augment; 864 // // } 865 // bool augmentOnBlockingFlow2() { 866 // bool _augment=false; 867 868 // //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph; 869 // typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph; 870 // typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; 871 // typedef typename EAugGraph::Edge EAugEdge; 872 873 // EAugGraph res_graph(*G, *flow, *capacity); 874 875 // //typedef typename EAugGraph::NodeMap<bool> ReachedMap; 876 // BfsIterator5< 877 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, 878 // /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/ 879 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph); 880 881 882 // //typename AugGraph::NodeMap<AugEdge> pred(res_graph); 883 // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { 884 // if (S->get(s)) { 885 // Number u=0; 886 // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) 887 // u+=flow->get(e); 888 // if (u<1) { 889 // bfs.pushAndSetReached(s); 890 // //pred.set(s, AugEdge(INVALID)); 891 // } 892 // } 893 // } 894 895 896 // //bfs.pushAndSetReached(s); 897 898 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>:: 899 // NodeMap<int>& dist=res_graph.dist; 900 901 // while ( !bfs.finished() ) { 902 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; 903 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 904 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); 905 // } 906 // ++bfs; 907 // } //computing distances from s in the residual graph 908 909 // bool __augment=true; 910 911 // while (__augment) { 912 913 // __augment=false; 914 // //computing blocking flow with dfs 915 // typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap; 916 // DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap > 917 // dfs(res_graph); 918 // typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID); 919 // //pred.set(s, EAugEdge(INVALID)); 920 // //invalid iterators for sources 921 922 // typename EAugGraph::NodeMap<Number> free(res_graph); 923 924 925 // //typename AugGraph::NodeMap<AugEdge> pred(res_graph); 926 // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { 927 // if (S->get(s)) { 928 // Number u=0; 929 // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) 930 // u+=flow->get(e); 931 // if (u<1) { 932 // dfs.pushAndSetReached(s); 933 // //pred.set(s, AugEdge(INVALID)); 934 // } 935 // } 936 // } 937 938 939 940 // //dfs.pushAndSetReached(s); 941 // typename EAugGraph::Node n; 942 // while (!dfs.finished()) { 943 // ++dfs; 944 // if (res_graph.valid(EAugOutEdgeIt(dfs))) { 945 // if (dfs.isBNodeNewlyReached()) { 946 947 // typename EAugGraph::Node v=res_graph.aNode(dfs); 948 // typename EAugGraph::Node w=res_graph.bNode(dfs); 949 950 // pred.set(w, EAugOutEdgeIt(dfs)); 951 // if (res_graph.valid(pred.get(v))) { 952 // free.set(w, std::min(free.get(v), res_graph.free(dfs))); 953 // } else { 954 // free.set(w, res_graph.free(dfs)); 955 // } 956 957 // n=w; 958 // if (T->get(w)) { 959 // Number u=0; 960 // for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f)) 961 // u+=flow->get(f); 962 // if (u<1) { 963 // __augment=true; 964 // _augment=true; 965 // break; 966 // } 967 // } 968 // } else { 969 // res_graph.erase(dfs); 970 // } 971 // } 972 973 // } 974 975 // if (__augment) { 976 // // typename EAugGraph::Node n=t; 977 // Number augment_value=free.get(n); 978 // while (res_graph.valid(pred.get(n))) { 979 // EAugEdge e=pred.get(n); 980 // res_graph.augment(e, augment_value); 981 // n=res_graph.tail(e); 982 // if (res_graph.free(e)==0) 983 // res_graph.erase(e); 984 // } 985 // } 986 987 // } 988 1234 989 // return _augment; 1235 990 // } 1236 991 // void run() { 1237 // while (augment()) { } 992 // //int num_of_augmentations=0; 993 // while (augmentOnShortestPath()) { 994 // //while (augmentOnBlockingFlow<MutableGraph>()) { 995 // //std::cout << ++num_of_augmentations << " "; 996 // //std::cout<<std::endl; 997 // } 1238 998 // } 999 // // template<typename MutableGraph> void run() { 1000 // // //int num_of_augmentations=0; 1001 // // //while (augmentOnShortestPath()) { 1002 // // while (augmentOnBlockingFlow<MutableGraph>()) { 1003 // // //std::cout << ++num_of_augmentations << " "; 1004 // // //std::cout<<std::endl; 1005 // // } 1006 // // } 1239 1007 // Number flowValue() { 1240 1008 // Number a=0; 1241 // for(typename std::list<Node>::const_iterator i=S.begin(); 1242 // i!=S.end(); ++i) { 1243 // for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) { 1244 // a+=flow.get(e); 1245 // } 1246 // for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) { 1247 // a-=flow.get(e); 1248 // } 1009 // EdgeIt e; 1010 // for(G->/*getF*/first(e); G->valid(e); G->next(e)) { 1011 // a+=flow->get(e); 1249 1012 // } 1250 1013 // return a; … … 1254 1017 1255 1018 1019 1020 1021 1022 // // template <typename Graph, typename Number, typename FlowMap, typename CapacityMap> 1023 // // class MaxFlow2 { 1024 // // public: 1025 // // typedef typename Graph::Node Node; 1026 // // typedef typename Graph::Edge Edge; 1027 // // typedef typename Graph::EdgeIt EdgeIt; 1028 // // typedef typename Graph::OutEdgeIt OutEdgeIt; 1029 // // typedef typename Graph::InEdgeIt InEdgeIt; 1030 // // private: 1031 // // const Graph& G; 1032 // // std::list<Node>& S; 1033 // // std::list<Node>& T; 1034 // // FlowMap& flow; 1035 // // const CapacityMap& capacity; 1036 // // typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph; 1037 // // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; 1038 // // typedef typename AugGraph::Edge AugEdge; 1039 // // typename Graph::NodeMap<bool> SMap; 1040 // // typename Graph::NodeMap<bool> TMap; 1041 // // public: 1042 // // MaxFlow2(const Graph& _G, std::list<Node>& _S, std::list<Node>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) { 1043 // // for(typename std::list<Node>::const_iterator i=S.begin(); 1044 // // i!=S.end(); ++i) { 1045 // // SMap.set(*i, true); 1046 // // } 1047 // // for (typename std::list<Node>::const_iterator i=T.begin(); 1048 // // i!=T.end(); ++i) { 1049 // // TMap.set(*i, true); 1050 // // } 1051 // // } 1052 // // bool augment() { 1053 // // AugGraph res_graph(G, flow, capacity); 1054 // // bool _augment=false; 1055 // // Node reached_t_node; 1056 1057 // // typedef typename AugGraph::NodeMap<bool> ReachedMap; 1058 // // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph); 1059 // // for(typename std::list<Node>::const_iterator i=S.begin(); 1060 // // i!=S.end(); ++i) { 1061 // // res_bfs.pushAndSetReached(*i); 1062 // // } 1063 // // //res_bfs.pushAndSetReached(s); 1064 1065 // // typename AugGraph::NodeMap<AugEdge> pred(res_graph); 1066 // // //filled up with invalid iterators 1067 1068 // // typename AugGraph::NodeMap<Number> free(res_graph); 1069 1070 // // //searching for augmenting path 1071 // // while ( !res_bfs.finished() ) { 1072 // // AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs); 1073 // // if (e.valid() && res_bfs.isBNodeNewlyReached()) { 1074 // // Node v=res_graph.tail(e); 1075 // // Node w=res_graph.head(e); 1076 // // pred.set(w, e); 1077 // // if (pred.get(v).valid()) { 1078 // // free.set(w, std::min(free.get(v), e.free())); 1079 // // } else { 1080 // // free.set(w, e.free()); 1081 // // } 1082 // // if (TMap.get(res_graph.head(e))) { 1083 // // _augment=true; 1084 // // reached_t_node=res_graph.head(e); 1085 // // break; 1086 // // } 1087 // // } 1088 1089 // // ++res_bfs; 1090 // // } //end of searching augmenting path 1091 1092 // // if (_augment) { 1093 // // Node n=reached_t_node; 1094 // // Number augment_value=free.get(reached_t_node); 1095 // // while (pred.get(n).valid()) { 1096 // // AugEdge e=pred.get(n); 1097 // // e.augment(augment_value); 1098 // // n=res_graph.tail(e); 1099 // // } 1100 // // } 1101 1102 // // return _augment; 1103 // // } 1104 // // void run() { 1105 // // while (augment()) { } 1106 // // } 1107 // // Number flowValue() { 1108 // // Number a=0; 1109 // // for(typename std::list<Node>::const_iterator i=S.begin(); 1110 // // i!=S.end(); ++i) { 1111 // // for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) { 1112 // // a+=flow.get(e); 1113 // // } 1114 // // for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) { 1115 // // a-=flow.get(e); 1116 // // } 1117 // // } 1118 // // return a; 1119 // // } 1120 // // }; 1121 1122 1256 1123 } // namespace hugo 1257 1124
Note: See TracChangeset
for help on using the changeset viewer.