Changeset 472:052af4060f3e in lemon0.x for src/work/jacint
 Timestamp:
 04/29/04 17:58:34 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@629
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/jacint/preflow.h
r471 r472 45 45 46 46 #include <graph_wrapper.h> 47 #include <bfs_iterator.h> 48 #include <invalid.h> 49 #include <maps.h> 50 #include <for_each_macros.h> 51 47 52 48 53 namespace hugo { … … 112 117 bool augmentOnBlockingFlow2(); 113 118 114 //Returns the maximum value of a flow. 115 Num flowValue() { 116 return excess[t]; 119 /// Returns the actual flow value. 120 /// More precisely, it returns the negative excess of s, thus 121 /// this works also for preflows. 122 Num flowValue() { 123 Num a=0; 124 FOR_EACH_INC_LOC(OutEdgeIt, e, *g, s) a+=(*flow)[e]; 125 FOR_EACH_INC_LOC(InEdgeIt, e, *g, s) a=(*flow)[e]; 126 return a; 117 127 } 118 128 … … 434 444 void relabel(Node w, int newlevel, VecStack& active, 435 445 VecNode& level_list, NNMap& left, 436 NNMap& right, int& b, int& k, bool what_heur ) { 446 NNMap& right, int& b, int& k, bool what_heur ) 447 { 437 448 438 449 Num lev=level[w]; … … 498 509 499 510 } //relabel 511 512 513 template<typename MapGraphWrapper> 514 class DistanceMap { 515 protected: 516 const MapGraphWrapper* g; 517 typename MapGraphWrapper::template NodeMap<int> dist; 518 public: 519 DistanceMap(MapGraphWrapper& _g) : g(&_g), dist(*g, g>nodeNum()) { } 520 void set(const typename MapGraphWrapper::Node& n, int a) { 521 dist.set(n, a); 522 } 523 int operator[](const typename MapGraphWrapper::Node& n) 524 { return dist[n]; } 525 // int get(const typename MapGraphWrapper::Node& n) const { 526 // return dist[n]; } 527 // bool get(const typename MapGraphWrapper::Edge& e) const { 528 // return (dist.get(g>tail(e))<dist.get(g>head(e))); } 529 bool operator[](const typename MapGraphWrapper::Edge& e) const { 530 return (dist[g>tail(e)]<dist[g>head(e)]); 531 } 532 }; 500 533 501 534 }; … … 675 708 676 709 677 678 679 680 681 710 template <typename Graph, typename Num, typename CapMap, typename FlowMap> 711 bool Preflow<Graph, Num, CapMap, FlowMap>::augmentOnShortestPath() 712 { 713 ResGW res_graph(*g, *capacity, *flow); 714 bool _augment=false; 715 716 //ReachedMap level(res_graph); 717 FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0); 718 BfsIterator<ResGW, ReachedMap> bfs(res_graph, level); 719 bfs.pushAndSetReached(s); 720 721 typename ResGW::template NodeMap<ResGWEdge> pred(res_graph); 722 pred.set(s, INVALID); 723 724 typename ResGW::template NodeMap<Num> free(res_graph); 725 726 //searching for augmenting path 727 while ( !bfs.finished() ) { 728 ResGWOutEdgeIt e=bfs; 729 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 730 Node v=res_graph.tail(e); 731 Node w=res_graph.head(e); 732 pred.set(w, e); 733 if (res_graph.valid(pred[v])) { 734 free.set(w, std::min(free[v], res_graph.resCap(e))); 735 } else { 736 free.set(w, res_graph.resCap(e)); 737 } 738 if (res_graph.head(e)==t) { _augment=true; break; } 739 } 740 741 ++bfs; 742 } //end of searching augmenting path 743 744 if (_augment) { 745 Node n=t; 746 Num augment_value=free[t]; 747 while (res_graph.valid(pred[n])) { 748 ResGWEdge e=pred[n]; 749 res_graph.augment(e, augment_value); 750 n=res_graph.tail(e); 751 } 752 } 753 754 return _augment; 755 } 756 757 758 759 760 761 762 763 764 765 template <typename Graph, typename Num, typename CapMap, typename FlowMap> 766 template<typename MutableGraph> 767 bool Preflow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow() 768 { 769 typedef MutableGraph MG; 770 bool _augment=false; 771 772 ResGW res_graph(*g, *capacity, *flow); 773 774 //bfs for distances on the residual graph 775 //ReachedMap level(res_graph); 776 FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0); 777 BfsIterator<ResGW, ReachedMap> bfs(res_graph, level); 778 bfs.pushAndSetReached(s); 779 typename ResGW::template NodeMap<int> 780 dist(res_graph); //filled up with 0's 781 782 //F will contain the physical copy of the residual graph 783 //with the set of edges which are on shortest paths 784 MG F; 785 typename ResGW::template NodeMap<typename MG::Node> 786 res_graph_to_F(res_graph); 787 { 788 typename ResGW::NodeIt n; 789 for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) { 790 res_graph_to_F.set(n, F.addNode()); 791 } 792 } 793 794 typename MG::Node sF=res_graph_to_F[s]; 795 typename MG::Node tF=res_graph_to_F[t]; 796 typename MG::template EdgeMap<ResGWEdge> original_edge(F); 797 typename MG::template EdgeMap<Num> residual_capacity(F); 798 799 while ( !bfs.finished() ) { 800 ResGWOutEdgeIt e=bfs; 801 if (res_graph.valid(e)) { 802 if (bfs.isBNodeNewlyReached()) { 803 dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1); 804 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]); 805 original_edge.update(); 806 original_edge.set(f, e); 807 residual_capacity.update(); 808 residual_capacity.set(f, res_graph.resCap(e)); 809 } else { 810 if (dist[res_graph.head(e)]==(dist[res_graph.tail(e)]+1)) { 811 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]); 812 original_edge.update(); 813 original_edge.set(f, e); 814 residual_capacity.update(); 815 residual_capacity.set(f, res_graph.resCap(e)); 816 } 817 } 818 } 819 ++bfs; 820 } //computing distances from s in the residual graph 821 822 bool __augment=true; 823 824 while (__augment) { 825 __augment=false; 826 //computing blocking flow with dfs 827 DfsIterator< MG, typename MG::template NodeMap<bool> > dfs(F); 828 typename MG::template NodeMap<typename MG::Edge> pred(F); 829 pred.set(sF, INVALID); 830 //invalid iterators for sources 831 832 typename MG::template NodeMap<Num> free(F); 833 834 dfs.pushAndSetReached(sF); 835 while (!dfs.finished()) { 836 ++dfs; 837 if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) { 838 if (dfs.isBNodeNewlyReached()) { 839 typename MG::Node v=F.aNode(dfs); 840 typename MG::Node w=F.bNode(dfs); 841 pred.set(w, dfs); 842 if (F.valid(pred[v])) { 843 free.set(w, std::min(free[v], residual_capacity[dfs])); 844 } else { 845 free.set(w, residual_capacity[dfs]); 846 } 847 if (w==tF) { 848 __augment=true; 849 _augment=true; 850 break; 851 } 852 853 } else { 854 F.erase(/*typename MG::OutEdgeIt*/(dfs)); 855 } 856 } 857 } 858 859 if (__augment) { 860 typename MG::Node n=tF; 861 Num augment_value=free[tF]; 862 while (F.valid(pred[n])) { 863 typename MG::Edge e=pred[n]; 864 res_graph.augment(original_edge[e], augment_value); 865 n=F.tail(e); 866 if (residual_capacity[e]==augment_value) 867 F.erase(e); 868 else 869 residual_capacity.set(e, residual_capacity[e]augment_value); 870 } 871 } 872 873 } 874 875 return _augment; 876 } 877 878 879 880 881 882 883 template <typename Graph, typename Num, typename CapMap, typename FlowMap> 884 bool Preflow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow2() 885 { 886 bool _augment=false; 887 888 ResGW res_graph(*g, *capacity, *flow); 889 890 //ReachedMap level(res_graph); 891 FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0); 892 BfsIterator<ResGW, ReachedMap> bfs(res_graph, level); 893 894 bfs.pushAndSetReached(s); 895 DistanceMap<ResGW> dist(res_graph); 896 while ( !bfs.finished() ) { 897 ResGWOutEdgeIt e=bfs; 898 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 899 dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1); 900 } 901 ++bfs; 902 } //computing distances from s in the residual graph 903 904 //Subgraph containing the edges on some shortest paths 905 ConstMap<typename ResGW::Node, bool> true_map(true); 906 typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>, 907 DistanceMap<ResGW> > FilterResGW; 908 FilterResGW filter_res_graph(res_graph, true_map, dist); 909 910 //Subgraph, which is able to delete edges which are already 911 //met by the dfs 912 typename FilterResGW::template NodeMap<typename FilterResGW::OutEdgeIt> 913 first_out_edges(filter_res_graph); 914 typename FilterResGW::NodeIt v; 915 for(filter_res_graph.first(v); filter_res_graph.valid(v); 916 filter_res_graph.next(v)) 917 { 918 typename FilterResGW::OutEdgeIt e; 919 filter_res_graph.first(e, v); 920 first_out_edges.set(v, e); 921 } 922 typedef ErasingFirstGraphWrapper<FilterResGW, typename FilterResGW:: 923 template NodeMap<typename FilterResGW::OutEdgeIt> > ErasingResGW; 924 ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges); 925 926 bool __augment=true; 927 928 while (__augment) { 929 930 __augment=false; 931 //computing blocking flow with dfs 932 DfsIterator< ErasingResGW, 933 typename ErasingResGW::template NodeMap<bool> > 934 dfs(erasing_res_graph); 935 typename ErasingResGW:: 936 template NodeMap<typename ErasingResGW::OutEdgeIt> 937 pred(erasing_res_graph); 938 pred.set(s, INVALID); 939 //invalid iterators for sources 940 941 typename ErasingResGW::template NodeMap<Num> 942 free1(erasing_res_graph); 943 944 dfs.pushAndSetReached( 945 typename ErasingResGW::Node( 946 typename FilterResGW::Node( 947 typename ResGW::Node(s) 948 ) 949 ) 950 ); 951 while (!dfs.finished()) { 952 ++dfs; 953 if (erasing_res_graph.valid( 954 typename ErasingResGW::OutEdgeIt(dfs))) 955 { 956 if (dfs.isBNodeNewlyReached()) { 957 958 typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs); 959 typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs); 960 961 pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs)); 962 if (erasing_res_graph.valid(pred[v])) { 963 free1.set(w, std::min(free1[v], res_graph.resCap( 964 typename ErasingResGW::OutEdgeIt(dfs)))); 965 } else { 966 free1.set(w, res_graph.resCap( 967 typename ErasingResGW::OutEdgeIt(dfs))); 968 } 969 970 if (w==t) { 971 __augment=true; 972 _augment=true; 973 break; 974 } 975 } else { 976 erasing_res_graph.erase(dfs); 977 } 978 } 979 } 980 981 if (__augment) { 982 typename ErasingResGW::Node n=typename FilterResGW::Node(typename ResGW::Node(t)); 983 // typename ResGW::NodeMap<Num> a(res_graph); 984 // typename ResGW::Node b; 985 // Num j=a[b]; 986 // typename FilterResGW::NodeMap<Num> a1(filter_res_graph); 987 // typename FilterResGW::Node b1; 988 // Num j1=a1[b1]; 989 // typename ErasingResGW::NodeMap<Num> a2(erasing_res_graph); 990 // typename ErasingResGW::Node b2; 991 // Num j2=a2[b2]; 992 Num augment_value=free1[n]; 993 while (erasing_res_graph.valid(pred[n])) { 994 typename ErasingResGW::OutEdgeIt e=pred[n]; 995 res_graph.augment(e, augment_value); 996 n=erasing_res_graph.tail(e); 997 if (res_graph.resCap(e)==0) 998 erasing_res_graph.erase(e); 999 } 1000 } 1001 1002 } //while (__augment) 1003 1004 return _augment; 1005 } 682 1006 683 1007
Note: See TracChangeset
for help on using the changeset viewer.