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

 2 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 
src/work/marci/edmonds_karp_demo.cc
r465 r472 6 6 #include <smart_graph.h> 7 7 #include <dimacs.h> 8 #include <edmonds_karp.h>8 //#include <edmonds_karp.h> 9 9 #include <time_measure.h> 10 10 //#include <graph_wrapper.h> 11 11 #include <preflow.h> 12 #include <preflow_res.h>12 //#include <preflow_res.h> 13 13 #include <for_each_macros.h> 14 14 … … 73 73 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 74 74 pre_flow_test(G, s, t, cap, flow/*, true*/); 75 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >76 pre_flow_ize(G, s, t, cap, flow/*, false*/);75 // Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 76 // pre_flow_ize(G, s, t, cap, flow/*, false*/); 77 77 // PreflowRes<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 78 78 // pre_flow_res(G, s, t, cap, flow/*, true*/); 79 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >80 max_flow_test(G, s, t, cap, flow);79 //MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 80 // max_flow_test(G, s, t, cap, flow); 81 81 82 82 { … … 92 92 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); 93 93 ts.reset(); 94 pre_flow_ ize.preflow(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);94 pre_flow_test.preflow(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW); 95 95 std::cout << "elapsed time: " << ts << std::endl; 96 std::cout << "flow value: "<< pre_flow_ ize.flowValue() << std::endl;96 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl; 97 97 } 98 98 … … 111 111 ts.reset(); 112 112 int i=0; 113 while ( max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }113 while (pre_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } 114 114 std::cout << "elapsed time: " << ts << std::endl; 115 115 std::cout << "number of augmentation phases: " << i << std::endl; 116 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;116 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl; 117 117 } 118 118 119 {120 std::cout << "faster physical blocking flow augmentation ..." << std::endl;121 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);122 ts.reset();123 int i=0;124 while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }125 std::cout << "elapsed time: " << ts << std::endl;126 std::cout << "number of augmentation phases: " << i << std::endl;127 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;128 }119 // { 120 // std::cout << "faster physical blocking flow augmentation ..." << std::endl; 121 // FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); 122 // ts.reset(); 123 // int i=0; 124 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; } 125 // std::cout << "elapsed time: " << ts << std::endl; 126 // std::cout << "number of augmentation phases: " << i << std::endl; 127 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 128 // } 129 129 130 130 { … … 133 133 ts.reset(); 134 134 int i=0; 135 while ( max_flow_test.augmentOnBlockingFlow2()) { ++i; }135 while (pre_flow_test.augmentOnBlockingFlow2()) { ++i; } 136 136 std::cout << "elapsed time: " << ts << std::endl; 137 137 std::cout << "number of augmentation phases: " << i << std::endl; 138 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;138 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl; 139 139 } 140 140 … … 144 144 ts.reset(); 145 145 int i=0; 146 while ( max_flow_test.augmentOnShortestPath()) { ++i; }146 while (pre_flow_test.augmentOnShortestPath()) { ++i; } 147 147 std::cout << "elapsed time: " << ts << std::endl; 148 148 std::cout << "number of augmentation phases: " << i << std::endl; 149 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;149 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl; 150 150 } 151 151
Note: See TracChangeset
for help on using the changeset viewer.