Changeset 1179:f6f6896a4724 in lemon for lemon
 Timestamp:
 11/15/12 07:17:48 (7 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/cycle_canceling.h
r1165 r1179 36 36 #include <lemon/bellman_ford.h> 37 37 #include <lemon/howard_mmc.h> 38 #include <lemon/hartmann_orlin_mmc.h> 38 39 39 40 namespace lemon { … … 928 929 // Execute the "Minimum Mean Cycle Canceling" method 929 930 void startMinMeanCycleCanceling() { 930 typedef SimplePath<StaticDigraph> SPath;931 typedef Path<StaticDigraph> SPath; 931 932 typedef typename SPath::ArcIt SPathArcIt; 932 933 typedef typename HowardMmc<StaticDigraph, CostArcMap> 933 ::template SetPath<SPath>::Create MMC; 934 ::template SetPath<SPath>::Create HwMmc; 935 typedef typename HartmannOrlinMmc<StaticDigraph, CostArcMap> 936 ::template SetPath<SPath>::Create HoMmc; 937 938 const double HW_ITER_LIMIT_FACTOR = 1.0; 939 const int HW_ITER_LIMIT_MIN_VALUE = 5; 940 941 const int hw_iter_limit = 942 std::max(static_cast<int>(HW_ITER_LIMIT_FACTOR * _node_num), 943 HW_ITER_LIMIT_MIN_VALUE); 934 944 935 945 SPath cycle; 936 MMCmmc(_sgr, _cost_map);937 mmc.cycle(cycle);946 HwMmc hw_mmc(_sgr, _cost_map); 947 hw_mmc.cycle(cycle); 938 948 buildResidualNetwork(); 939 while (mmc.findCycleMean() && mmc.cycleCost() < 0) { 940 // Find the cycle 941 mmc.findCycle(); 942 949 while (true) { 950 951 typename HwMmc::TerminationCause hw_tc = 952 hw_mmc.findCycleMean(hw_iter_limit); 953 if (hw_tc == HwMmc::ITERATION_LIMIT) { 954 // Howard's algorithm reached the iteration limit, start a 955 // strongly polynomial algorithm instead 956 HoMmc ho_mmc(_sgr, _cost_map); 957 ho_mmc.cycle(cycle); 958 // Find a minimum mean cycle (HartmannOrlin algorithm) 959 if (!(ho_mmc.findCycleMean() && ho_mmc.cycleCost() < 0)) break; 960 ho_mmc.findCycle(); 961 } else { 962 // Find a minimum mean cycle (Howard algorithm) 963 if (!(hw_tc == HwMmc::OPTIMAL && hw_mmc.cycleCost() < 0)) break; 964 hw_mmc.findCycle(); 965 } 966 943 967 // Compute delta value 944 968 Value delta = INF; … … 965 989 const double LIMIT_FACTOR = 1.0; 966 990 const int MIN_LIMIT = 5; 991 const double HW_ITER_LIMIT_FACTOR = 1.0; 992 const int HW_ITER_LIMIT_MIN_VALUE = 5; 993 994 const int hw_iter_limit = 995 std::max(static_cast<int>(HW_ITER_LIMIT_FACTOR * _node_num), 996 HW_ITER_LIMIT_MIN_VALUE); 967 997 968 998 // Contruct auxiliary data vectors … … 1138 1168 } 1139 1169 } else { 1140 typedef HowardMmc<StaticDigraph, CostArcMap> MMC; 1170 typedef HowardMmc<StaticDigraph, CostArcMap> HwMmc; 1171 typedef HartmannOrlinMmc<StaticDigraph, CostArcMap> HoMmc; 1141 1172 typedef typename BellmanFord<StaticDigraph, CostArcMap> 1142 1173 ::template SetDistMap<CostNodeMap>::Create BF; 1143 1174 1144 1175 // Set epsilon to the minimum cycle mean 1176 Cost cycle_cost = 0; 1177 int cycle_size = 1; 1145 1178 buildResidualNetwork(); 1146 MMC mmc(_sgr, _cost_map); 1147 mmc.findCycleMean(); 1148 epsilon = mmc.cycleMean(); 1149 Cost cycle_cost = mmc.cycleCost(); 1150 int cycle_size = mmc.cycleSize(); 1179 HwMmc hw_mmc(_sgr, _cost_map); 1180 if (hw_mmc.findCycleMean(hw_iter_limit) == HwMmc::ITERATION_LIMIT) { 1181 // Howard's algorithm reached the iteration limit, start a 1182 // strongly polynomial algorithm instead 1183 HoMmc ho_mmc(_sgr, _cost_map); 1184 ho_mmc.findCycleMean(); 1185 epsilon = ho_mmc.cycleMean(); 1186 cycle_cost = ho_mmc.cycleCost(); 1187 cycle_size = ho_mmc.cycleSize(); 1188 } else { 1189 // Set epsilon 1190 epsilon = hw_mmc.cycleMean(); 1191 cycle_cost = hw_mmc.cycleCost(); 1192 cycle_size = hw_mmc.cycleSize(); 1193 } 1151 1194 1152 1195 // Compute feasible potentials for the current epsilon
Note: See TracChangeset
for help on using the changeset viewer.