32 #include <lemon/math.h> |
32 #include <lemon/math.h> |
33 #include <lemon/static_graph.h> |
33 #include <lemon/static_graph.h> |
34 #include <lemon/adaptors.h> |
34 #include <lemon/adaptors.h> |
35 #include <lemon/circulation.h> |
35 #include <lemon/circulation.h> |
36 #include <lemon/bellman_ford.h> |
36 #include <lemon/bellman_ford.h> |
37 #include <lemon/howard.h> |
37 #include <lemon/howard_mmc.h> |
38 |
38 |
39 namespace lemon { |
39 namespace lemon { |
40 |
40 |
41 /// \addtogroup min_cost_flow_algs |
41 /// \addtogroup min_cost_flow_algs |
42 /// @{ |
42 /// @{ |
922 |
922 |
923 // Execute the "Minimum Mean Cycle Canceling" method |
923 // Execute the "Minimum Mean Cycle Canceling" method |
924 void startMinMeanCycleCanceling() { |
924 void startMinMeanCycleCanceling() { |
925 typedef SimplePath<StaticDigraph> SPath; |
925 typedef SimplePath<StaticDigraph> SPath; |
926 typedef typename SPath::ArcIt SPathArcIt; |
926 typedef typename SPath::ArcIt SPathArcIt; |
927 typedef typename Howard<StaticDigraph, CostArcMap> |
927 typedef typename HowardMmc<StaticDigraph, CostArcMap> |
928 ::template SetPath<SPath>::Create MMC; |
928 ::template SetPath<SPath>::Create MMC; |
929 |
929 |
930 SPath cycle; |
930 SPath cycle; |
931 MMC mmc(_sgr, _cost_map); |
931 MMC mmc(_sgr, _cost_map); |
932 mmc.cycle(cycle); |
932 mmc.cycle(cycle); |
933 buildResidualNetwork(); |
933 buildResidualNetwork(); |
934 while (mmc.findMinMean() && mmc.cycleLength() < 0) { |
934 while (mmc.findCycleMean() && mmc.cycleCost() < 0) { |
935 // Find the cycle |
935 // Find the cycle |
936 mmc.findCycle(); |
936 mmc.findCycle(); |
937 |
937 |
938 // Compute delta value |
938 // Compute delta value |
939 Value delta = INF; |
939 Value delta = INF; |
1130 curr = _cost[a] + pu - pi[_target[a]]; |
1130 curr = _cost[a] + pu - pi[_target[a]]; |
1131 if (-curr > epsilon) epsilon = -curr; |
1131 if (-curr > epsilon) epsilon = -curr; |
1132 } |
1132 } |
1133 } |
1133 } |
1134 } else { |
1134 } else { |
1135 typedef Howard<StaticDigraph, CostArcMap> MMC; |
1135 typedef HowardMmc<StaticDigraph, CostArcMap> MMC; |
1136 typedef typename BellmanFord<StaticDigraph, CostArcMap> |
1136 typedef typename BellmanFord<StaticDigraph, CostArcMap> |
1137 ::template SetDistMap<CostNodeMap>::Create BF; |
1137 ::template SetDistMap<CostNodeMap>::Create BF; |
1138 |
1138 |
1139 // Set epsilon to the minimum cycle mean |
1139 // Set epsilon to the minimum cycle mean |
1140 buildResidualNetwork(); |
1140 buildResidualNetwork(); |
1141 MMC mmc(_sgr, _cost_map); |
1141 MMC mmc(_sgr, _cost_map); |
1142 mmc.findMinMean(); |
1142 mmc.findCycleMean(); |
1143 epsilon = -mmc.cycleMean(); |
1143 epsilon = -mmc.cycleMean(); |
1144 Cost cycle_cost = mmc.cycleLength(); |
1144 Cost cycle_cost = mmc.cycleCost(); |
1145 int cycle_size = mmc.cycleArcNum(); |
1145 int cycle_size = mmc.cycleSize(); |
1146 |
1146 |
1147 // Compute feasible potentials for the current epsilon |
1147 // Compute feasible potentials for the current epsilon |
1148 for (int i = 0; i != int(_cost_vec.size()); ++i) { |
1148 for (int i = 0; i != int(_cost_vec.size()); ++i) { |
1149 _cost_vec[i] = cycle_size * _cost_vec[i] - cycle_cost; |
1149 _cost_vec[i] = cycle_size * _cost_vec[i] - cycle_cost; |
1150 } |
1150 } |