Changeset 193:84c19824322a in lemon0.x for src/work/edmonds_karp.h
 Timestamp:
 03/17/04 16:01:04 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@270
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/edmonds_karp.h
r191 r193 527 527 } 528 528 }; 529 530 531 template <typename Graph, typename Number, typename FlowMap, typename CapacityMap> 532 class MaxMatching { 533 public: 534 typedef typename Graph::Node Node; 535 typedef typename Graph::Edge Edge; 536 typedef typename Graph::EdgeIt EdgeIt; 537 typedef typename Graph::OutEdgeIt OutEdgeIt; 538 typedef typename Graph::InEdgeIt InEdgeIt; 539 540 typedef typename Graph::NodeMap<bool> SMap; 541 typedef typename Graph::NodeMap<bool> TMap; 542 private: 543 const Graph* G; 544 SMap* S; 545 TMap* T; 546 //Node s; 547 //Node t; 548 FlowMap* flow; 549 const CapacityMap* capacity; 550 typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph; 551 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; 552 typedef typename AugGraph::Edge AugEdge; 553 554 public: 555 MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) : 556 G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity) { } 557 bool augmentOnShortestPath() { 558 AugGraph res_graph(*G, *flow, *capacity); 559 bool _augment=false; 560 561 typedef typename AugGraph::NodeMap<bool> ReachedMap; 562 BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph); 563 typename AugGraph::NodeMap<AugEdge> pred(res_graph); 564 for(NodeIt s=G>template first<NodeIt>(); G>valid(s); G>next(s)) { 565 Number f=0; 566 for(OutEdgeIt e=G>template first<OutEdgeIt>(); G>valid(e); G>next(e)) 567 f+=flow>get(e); 568 if (f<1) { 569 res_bfs.pushAndSetReached(s); 570 pred.set(s, AugEdge(INVALID)); 571 } 572 } 573 574 typename AugGraph::NodeMap<Number> free(res_graph); 575 576 Node n; 577 //searching for augmenting path 578 while ( !res_bfs.finished() ) { 579 AugOutEdgeIt e=res_bfs; 580 if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) { 581 Node v=res_graph.tail(e); 582 Node w=res_graph.head(e); 583 pred.set(w, e); 584 if (res_graph.valid(pred.get(v))) { 585 free.set(w, std::min(free.get(v), res_graph.free(e))); 586 } else { 587 free.set(w, res_graph.free(e)); 588 } 589 if (TMap(res_graph.head(e))) { 590 n=res_graph.head(e); 591 _augment=true; 592 break; 593 } 594 } 595 596 ++res_bfs; 597 } //end of searching augmenting path 598 599 if (_augment) { 600 //Node n=t; 601 Number augment_value=free.get(t); 602 while (res_graph.valid(pred.get(n))) { 603 AugEdge e=pred.get(n); 604 res_graph.augment(e, augment_value); 605 n=res_graph.tail(e); 606 } 607 } 608 609 return _augment; 610 } 611 612 // template<typename MutableGraph> bool augmentOnBlockingFlow() { 613 // bool _augment=false; 614 615 // AugGraph res_graph(*G, *flow, *capacity); 616 617 // typedef typename AugGraph::NodeMap<bool> ReachedMap; 618 // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph); 619 620 // bfs.pushAndSetReached(s); 621 // typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's 622 // while ( !bfs.finished() ) { 623 // AugOutEdgeIt e=bfs; 624 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 625 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); 626 // } 627 628 // ++bfs; 629 // } //computing distances from s in the residual graph 630 631 // MutableGraph F; 632 // typename AugGraph::NodeMap<typename MutableGraph::Node> 633 // res_graph_to_F(res_graph); 634 // for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { 635 // res_graph_to_F.set(n, F.addNode()); 636 // } 637 638 // typename MutableGraph::Node sF=res_graph_to_F.get(s); 639 // typename MutableGraph::Node tF=res_graph_to_F.get(t); 640 641 // typename MutableGraph::EdgeMap<AugEdge> original_edge(F); 642 // typename MutableGraph::EdgeMap<Number> residual_capacity(F); 643 644 // //Making F to the graph containing the edges of the residual graph 645 // //which are in some shortest paths 646 // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) { 647 // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { 648 // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); 649 // original_edge.update(); 650 // original_edge.set(f, e); 651 // residual_capacity.update(); 652 // residual_capacity.set(f, res_graph.free(e)); 653 // } 654 // } 655 656 // bool __augment=true; 657 658 // while (__augment) { 659 // __augment=false; 660 // //computing blocking flow with dfs 661 // typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap; 662 // DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F); 663 // typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F); 664 // pred.set(sF, typename MutableGraph::Edge(INVALID)); 665 // //invalid iterators for sources 666 667 // typename MutableGraph::NodeMap<Number> free(F); 668 669 // dfs.pushAndSetReached(sF); 670 // while (!dfs.finished()) { 671 // ++dfs; 672 // if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { 673 // if (dfs.isBNodeNewlyReached()) { 674 // typename MutableGraph::Node v=F.aNode(dfs); 675 // typename MutableGraph::Node w=F.bNode(dfs); 676 // pred.set(w, dfs); 677 // if (F.valid(pred.get(v))) { 678 // free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); 679 // } else { 680 // free.set(w, residual_capacity.get(dfs)); 681 // } 682 // if (w==tF) { 683 // __augment=true; 684 // _augment=true; 685 // break; 686 // } 687 688 // } else { 689 // F.erase(typename MutableGraph::OutEdgeIt(dfs)); 690 // } 691 // } 692 // } 693 694 // if (__augment) { 695 // typename MutableGraph::Node n=tF; 696 // Number augment_value=free.get(tF); 697 // while (F.valid(pred.get(n))) { 698 // typename MutableGraph::Edge e=pred.get(n); 699 // res_graph.augment(original_edge.get(e), augment_value); 700 // n=F.tail(e); 701 // if (residual_capacity.get(e)==augment_value) 702 // F.erase(e); 703 // else 704 // residual_capacity.set(e, residual_capacity.get(e)augment_value); 705 // } 706 // } 707 708 // } 709 710 // return _augment; 711 // } 712 // bool augmentOnBlockingFlow2() { 713 // bool _augment=false; 714 715 // //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph; 716 // typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph; 717 // typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; 718 // typedef typename EAugGraph::Edge EAugEdge; 719 720 // EAugGraph res_graph(*G, *flow, *capacity); 721 722 // //typedef typename EAugGraph::NodeMap<bool> ReachedMap; 723 // BfsIterator4< 724 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, 725 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt, 726 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph); 727 728 // bfs.pushAndSetReached(s); 729 730 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>:: 731 // NodeMap<int>& dist=res_graph.dist; 732 733 // while ( !bfs.finished() ) { 734 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; 735 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 736 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); 737 // } 738 // ++bfs; 739 // } //computing distances from s in the residual graph 740 741 // bool __augment=true; 742 743 // while (__augment) { 744 745 // __augment=false; 746 // //computing blocking flow with dfs 747 // typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap; 748 // DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap > 749 // dfs(res_graph); 750 // typename EAugGraph::NodeMap<EAugEdge> pred(res_graph); 751 // pred.set(s, EAugEdge(INVALID)); 752 // //invalid iterators for sources 753 754 // typename EAugGraph::NodeMap<Number> free(res_graph); 755 756 // dfs.pushAndSetReached(s); 757 // while (!dfs.finished()) { 758 // ++dfs; 759 // if (res_graph.valid(EAugOutEdgeIt(dfs))) { 760 // if (dfs.isBNodeNewlyReached()) { 761 762 // typename EAugGraph::Node v=res_graph.aNode(dfs); 763 // typename EAugGraph::Node w=res_graph.bNode(dfs); 764 765 // pred.set(w, EAugOutEdgeIt(dfs)); 766 // if (res_graph.valid(pred.get(v))) { 767 // free.set(w, std::min(free.get(v), res_graph.free(dfs))); 768 // } else { 769 // free.set(w, res_graph.free(dfs)); 770 // } 771 772 // if (w==t) { 773 // __augment=true; 774 // _augment=true; 775 // break; 776 // } 777 // } else { 778 // res_graph.erase(dfs); 779 // } 780 // } 781 782 // } 783 784 // if (__augment) { 785 // typename EAugGraph::Node n=t; 786 // Number augment_value=free.get(t); 787 // while (res_graph.valid(pred.get(n))) { 788 // EAugEdge e=pred.get(n); 789 // res_graph.augment(e, augment_value); 790 // n=res_graph.tail(e); 791 // if (res_graph.free(e)==0) 792 // res_graph.erase(e); 793 // } 794 // } 795 796 // } 797 798 // return _augment; 799 // } 800 void run() { 801 //int num_of_augmentations=0; 802 while (augmentOnShortestPath()) { 803 //while (augmentOnBlockingFlow<MutableGraph>()) { 804 //std::cout << ++num_of_augmentations << " "; 805 //std::cout<<std::endl; 806 } 807 } 808 template<typename MutableGraph> void run() { 809 //int num_of_augmentations=0; 810 //while (augmentOnShortestPath()) { 811 while (augmentOnBlockingFlow<MutableGraph>()) { 812 //std::cout << ++num_of_augmentations << " "; 813 //std::cout<<std::endl; 814 } 815 } 816 Number flowValue() { 817 Number a=0; 818 OutEdgeIt e; 819 for(G>/*getF*/first(e, s); G>valid(e); G>next(e)) { 820 a+=flow>get(e); 821 } 822 return a; 823 } 824 }; 825 826 827 828 529 829 530 830
Note: See TracChangeset
for help on using the changeset viewer.