Changeset 197:fff43d9c7110 in lemon-0.x for src/work/edmonds_karp.h
- Timestamp:
- 03/17/04 18:04:41 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@274
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/edmonds_karp.h
r196 r197 565 565 for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { 566 566 if (S->get(s)) { 567 Number f=0;567 Number u=0; 568 568 for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) 569 f+=flow->get(e);570 if ( f<1) {569 u+=flow->get(e); 570 if (u<1) { 571 571 res_bfs.pushAndSetReached(s); 572 572 pred.set(s, AugEdge(INVALID)); … … 590 590 free.set(w, res_graph.free(e)); 591 591 } 592 if (T->get(res_graph.head(e))) { 593 n=res_graph.head(e); 594 _augment=true; 595 break; 592 n=res_graph.head(e); 593 if (T->get(n)) { 594 Number u=0; 595 for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f)) 596 u+=flow->get(f); 597 if (u<1) { 598 _augment=true; 599 break; 600 } 596 601 } 597 602 } … … 621 626 // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph); 622 627 623 // bfs.pushAndSetReached(s); 628 629 630 631 632 // //typename AugGraph::NodeMap<AugEdge> pred(res_graph); 633 // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { 634 // if (S->get(s)) { 635 // Number u=0; 636 // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) 637 // u+=flow->get(e); 638 // if (u<1) { 639 // res_bfs.pushAndSetReached(s); 640 // //pred.set(s, AugEdge(INVALID)); 641 // } 642 // } 643 // } 644 645 646 647 648 // //bfs.pushAndSetReached(s); 624 649 // typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's 625 650 // while ( !bfs.finished() ) { … … 713 738 // return _augment; 714 739 // } 715 // bool augmentOnBlockingFlow2() { 716 // bool _augment=false; 717 718 // //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph; 719 // typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph; 720 // typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; 721 // typedef typename EAugGraph::Edge EAugEdge; 722 723 // EAugGraph res_graph(*G, *flow, *capacity); 724 725 // //typedef typename EAugGraph::NodeMap<bool> ReachedMap; 726 // BfsIterator4< 727 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, 728 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt, 729 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph); 730 731 // bfs.pushAndSetReached(s); 732 733 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>:: 734 // NodeMap<int>& dist=res_graph.dist; 735 736 // while ( !bfs.finished() ) { 737 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; 738 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 739 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); 740 // } 741 // ++bfs; 742 // } //computing distances from s in the residual graph 743 744 // bool __augment=true; 745 746 // while (__augment) { 747 748 // __augment=false; 749 // //computing blocking flow with dfs 750 // typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap; 751 // DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap > 752 // dfs(res_graph); 753 // typename EAugGraph::NodeMap<EAugEdge> pred(res_graph); 754 // pred.set(s, EAugEdge(INVALID)); 755 // //invalid iterators for sources 756 757 // typename EAugGraph::NodeMap<Number> free(res_graph); 758 759 // dfs.pushAndSetReached(s); 760 // while (!dfs.finished()) { 761 // ++dfs; 762 // if (res_graph.valid(EAugOutEdgeIt(dfs))) { 763 // if (dfs.isBNodeNewlyReached()) { 740 bool augmentOnBlockingFlow2() { 741 bool _augment=false; 742 743 //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph; 744 typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph; 745 typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; 746 typedef typename EAugGraph::Edge EAugEdge; 747 748 EAugGraph res_graph(*G, *flow, *capacity); 749 750 //typedef typename EAugGraph::NodeMap<bool> ReachedMap; 751 BfsIterator4< 752 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, 753 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt, 754 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph); 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 bfs.pushAndSetReached(s); 765 //pred.set(s, AugEdge(INVALID)); 766 } 767 } 768 } 769 770 771 //bfs.pushAndSetReached(s); 772 773 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>:: 774 NodeMap<int>& dist=res_graph.dist; 775 776 while ( !bfs.finished() ) { 777 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; 778 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 779 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); 780 } 781 ++bfs; 782 } //computing distances from s in the residual graph 783 784 bool __augment=true; 785 786 while (__augment) { 787 788 __augment=false; 789 //computing blocking flow with dfs 790 typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap; 791 DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap > 792 dfs(res_graph); 793 typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID); 794 //pred.set(s, EAugEdge(INVALID)); 795 //invalid iterators for sources 796 797 typename EAugGraph::NodeMap<Number> free(res_graph); 798 799 800 //typename AugGraph::NodeMap<AugEdge> pred(res_graph); 801 for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { 802 if (S->get(s)) { 803 Number u=0; 804 for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) 805 u+=flow->get(e); 806 if (u<1) { 807 dfs.pushAndSetReached(s); 808 //pred.set(s, AugEdge(INVALID)); 809 } 810 } 811 } 812 813 814 815 //dfs.pushAndSetReached(s); 816 typename EAugGraph::Node n; 817 while (!dfs.finished()) { 818 ++dfs; 819 if (res_graph.valid(EAugOutEdgeIt(dfs))) { 820 if (dfs.isBNodeNewlyReached()) { 764 821 765 // typename EAugGraph::Node v=res_graph.aNode(dfs); 766 // typename EAugGraph::Node w=res_graph.bNode(dfs); 767 768 // pred.set(w, EAugOutEdgeIt(dfs)); 769 // if (res_graph.valid(pred.get(v))) { 770 // free.set(w, std::min(free.get(v), res_graph.free(dfs))); 771 // } else { 772 // free.set(w, res_graph.free(dfs)); 773 // } 774 775 // if (w==t) { 776 // __augment=true; 777 // _augment=true; 778 // break; 779 // } 780 // } else { 781 // res_graph.erase(dfs); 782 // } 783 // } 784 785 // } 786 787 // if (__augment) { 788 // typename EAugGraph::Node n=t; 789 // Number augment_value=free.get(t); 790 // while (res_graph.valid(pred.get(n))) { 791 // EAugEdge e=pred.get(n); 792 // res_graph.augment(e, augment_value); 793 // n=res_graph.tail(e); 794 // if (res_graph.free(e)==0) 795 // res_graph.erase(e); 796 // } 797 // } 798 799 // } 822 typename EAugGraph::Node v=res_graph.aNode(dfs); 823 typename EAugGraph::Node w=res_graph.bNode(dfs); 824 825 pred.set(w, EAugOutEdgeIt(dfs)); 826 if (res_graph.valid(pred.get(v))) { 827 free.set(w, std::min(free.get(v), res_graph.free(dfs))); 828 } else { 829 free.set(w, res_graph.free(dfs)); 830 } 831 832 n=w; 833 if (T->get(w)) { 834 Number u=0; 835 for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f)) 836 u+=flow->get(f); 837 if (u<1) { 838 __augment=true; 839 _augment=true; 840 break; 841 } 842 } 843 } else { 844 res_graph.erase(dfs); 845 } 846 } 847 848 } 849 850 if (__augment) { 851 // typename EAugGraph::Node n=t; 852 Number augment_value=free.get(n); 853 while (res_graph.valid(pred.get(n))) { 854 EAugEdge e=pred.get(n); 855 res_graph.augment(e, augment_value); 856 n=res_graph.tail(e); 857 if (res_graph.free(e)==0) 858 res_graph.erase(e); 859 } 860 } 861 862 } 800 863 801 //return _augment;802 //}864 return _augment; 865 } 803 866 void run() { 804 867 //int num_of_augmentations=0;
Note: See TracChangeset
for help on using the changeset viewer.