r653:c7d160f73d52
Wed, 25 Mar 2009 21:37:50
[Not Reviewed]
0 comments (0 inline)
0
2
0
| ... | ... |
@@ -43,2 +43,8 @@ |
| 43 | 43 |
/// for finding a \ref min_cost_flow "minimum cost flow". |
| 44 |
/// This algorithm is a specialized version of the linear programming |
|
| 45 |
/// simplex method directly for the minimum cost flow problem. |
|
| 46 |
/// It is one of the most efficient solution methods. |
|
| 47 |
/// |
|
| 48 |
/// In general this class is the fastest implementation available |
|
| 49 |
/// in LEMON for the minimum cost flow problem. |
|
| 44 | 50 |
/// |
| ... | ... |
@@ -48,3 +54,3 @@ |
| 48 | 54 |
/// |
| 49 |
/// \warning |
|
| 55 |
/// \warning The value type must be a signed integer type. |
|
| 50 | 56 |
/// |
| ... | ... |
@@ -800,2 +806,7 @@ |
| 800 | 806 |
/// |
| 807 |
/// This function can be called more than once. All the parameters |
|
| 808 |
/// that have been given are kept for the next call, unless |
|
| 809 |
/// \ref reset() is called, thus only the modified parameters |
|
| 810 |
/// have to be set again. See \ref reset() for examples. |
|
| 811 |
/// |
|
| 801 | 812 |
/// \param pivot_rule The pivot rule that will be used during the |
| ... | ... |
@@ -808,2 +819,47 @@ |
| 808 | 819 |
|
| 820 |
/// \brief Reset all the parameters that have been given before. |
|
| 821 |
/// |
|
| 822 |
/// This function resets all the paramaters that have been given |
|
| 823 |
/// using \ref lowerMap(), \ref upperMap(), \ref capacityMap(), |
|
| 824 |
/// \ref boundMaps(), \ref costMap(), \ref supplyMap() and |
|
| 825 |
/// \ref stSupply() functions before. |
|
| 826 |
/// |
|
| 827 |
/// It is useful for multiple run() calls. If this function is not |
|
| 828 |
/// used, all the parameters given before are kept for the next |
|
| 829 |
/// \ref run() call. |
|
| 830 |
/// |
|
| 831 |
/// For example, |
|
| 832 |
/// \code |
|
| 833 |
/// NetworkSimplex<ListDigraph> ns(graph); |
|
| 834 |
/// |
|
| 835 |
/// // First run |
|
| 836 |
/// ns.lowerMap(lower).capacityMap(cap).costMap(cost) |
|
| 837 |
/// .supplyMap(sup).run(); |
|
| 838 |
/// |
|
| 839 |
/// // Run again with modified cost map (reset() is not called, |
|
| 840 |
/// // so only the cost map have to be set again) |
|
| 841 |
/// cost[e] += 100; |
|
| 842 |
/// ns.costMap(cost).run(); |
|
| 843 |
/// |
|
| 844 |
/// // Run again from scratch using reset() |
|
| 845 |
/// // (the lower bounds will be set to zero on all arcs) |
|
| 846 |
/// ns.reset(); |
|
| 847 |
/// ns.capacityMap(cap).costMap(cost) |
|
| 848 |
/// .supplyMap(sup).run(); |
|
| 849 |
/// \endcode |
|
| 850 |
/// |
|
| 851 |
/// \return <tt>(*this)</tt> |
|
| 852 |
NetworkSimplex& reset() {
|
|
| 853 |
delete _plower; |
|
| 854 |
delete _pupper; |
|
| 855 |
delete _pcost; |
|
| 856 |
delete _psupply; |
|
| 857 |
_plower = NULL; |
|
| 858 |
_pupper = NULL; |
|
| 859 |
_pcost = NULL; |
|
| 860 |
_psupply = NULL; |
|
| 861 |
_pstsup = false; |
|
| 862 |
return *this; |
|
| 863 |
} |
|
| 864 |
|
|
| 809 | 865 |
/// @} |
| ... | ... |
@@ -922,4 +978,4 @@ |
| 922 | 978 |
_supply.resize(all_node_num); |
| 923 |
_flow.resize(all_arc_num, 0); |
|
| 924 |
_pi.resize(all_node_num, 0); |
|
| 979 |
_flow.resize(all_arc_num); |
|
| 980 |
_pi.resize(all_node_num); |
|
| 925 | 981 |
|
| ... | ... |
@@ -932,3 +988,3 @@ |
| 932 | 988 |
_last_succ.resize(all_node_num); |
| 933 |
_state.resize(all_arc_num |
|
| 989 |
_state.resize(all_arc_num); |
|
| 934 | 990 |
|
| ... | ... |
@@ -988,2 +1044,4 @@ |
| 988 | 1044 |
_cost[i] = (*_pcost)[e]; |
| 1045 |
_flow[i] = 0; |
|
| 1046 |
_state[i] = STATE_LOWER; |
|
| 989 | 1047 |
} |
| ... | ... |
@@ -994,2 +1052,4 @@ |
| 994 | 1052 |
_target[i] = _node_id[_graph.target(e)]; |
| 1053 |
_flow[i] = 0; |
|
| 1054 |
_state[i] = STATE_LOWER; |
|
| 995 | 1055 |
} |
| ... | ... |
@@ -1034,2 +1094,5 @@ |
| 1034 | 1094 |
_pred[u] = e; |
| 1095 |
_cost[e] = max_cost; |
|
| 1096 |
_cap[e] = max_cap; |
|
| 1097 |
_state[e] = STATE_TREE; |
|
| 1035 | 1098 |
if (_supply[u] >= 0) {
|
| ... | ... |
@@ -1043,5 +1106,2 @@ |
| 1043 | 1106 |
} |
| 1044 |
_cost[e] = max_cost; |
|
| 1045 |
_cap[e] = max_cap; |
|
| 1046 |
_state[e] = STATE_TREE; |
|
| 1047 | 1107 |
} |
| ... | ... |
@@ -91,3 +91,4 @@ |
| 91 | 91 |
|
| 92 |
b = mcf. |
|
| 92 |
b = mcf.reset() |
|
| 93 |
.lowerMap(lower) |
|
| 93 | 94 |
.upperMap(upper) |
| ... | ... |
@@ -244,20 +245,23 @@ |
| 244 | 245 |
{
|
| 245 |
NetworkSimplex<Digraph> mcf1(gr), mcf2(gr), mcf3(gr), mcf4(gr), |
|
| 246 |
mcf5(gr), mcf6(gr), mcf7(gr), mcf8(gr); |
|
| 246 |
NetworkSimplex<Digraph> mcf(gr); |
|
| 247 | 247 |
|
| 248 |
|
|
| 248 |
mcf.upperMap(u).costMap(c); |
|
| 249 |
checkMcf(mcf, mcf.supplyMap(s1).run(), |
|
| 249 | 250 |
gr, l1, u, c, s1, true, 5240, "#A1"); |
| 250 |
checkMcf( |
|
| 251 |
checkMcf(mcf, mcf.stSupply(v, w, 27).run(), |
|
| 251 | 252 |
gr, l1, u, c, s2, true, 7620, "#A2"); |
| 252 |
|
|
| 253 |
mcf.lowerMap(l2); |
|
| 254 |
checkMcf(mcf, mcf.supplyMap(s1).run(), |
|
| 253 | 255 |
gr, l2, u, c, s1, true, 5970, "#A3"); |
| 254 |
checkMcf( |
|
| 256 |
checkMcf(mcf, mcf.stSupply(v, w, 27).run(), |
|
| 255 | 257 |
gr, l2, u, c, s2, true, 8010, "#A4"); |
| 256 |
|
|
| 258 |
mcf.reset(); |
|
| 259 |
checkMcf(mcf, mcf.supplyMap(s1).run(), |
|
| 257 | 260 |
gr, l1, cu, cc, s1, true, 74, "#A5"); |
| 258 |
checkMcf( |
|
| 261 |
checkMcf(mcf, mcf.lowerMap(l2).stSupply(v, w, 27).run(), |
|
| 259 | 262 |
gr, l2, cu, cc, s2, true, 94, "#A6"); |
| 260 |
|
|
| 263 |
mcf.reset(); |
|
| 264 |
checkMcf(mcf, mcf.run(), |
|
| 261 | 265 |
gr, l1, cu, cc, s3, true, 0, "#A7"); |
| 262 |
checkMcf( |
|
| 266 |
checkMcf(mcf, mcf.boundMaps(l2, u).run(), |
|
| 263 | 267 |
gr, l2, u, cc, s3, false, 0, "#A8"); |
| ... | ... |
@@ -267,19 +271,14 @@ |
| 267 | 271 |
{
|
| 268 |
NetworkSimplex<Digraph> mcf1(gr), mcf2(gr), mcf3(gr), mcf4(gr), mcf5(gr); |
|
| 269 |
NetworkSimplex<Digraph>::PivotRule pr; |
|
| 272 |
NetworkSimplex<Digraph> mcf(gr); |
|
| 273 |
mcf.supplyMap(s1).costMap(c).capacityMap(u).lowerMap(l2); |
|
| 270 | 274 |
|
| 271 |
pr = NetworkSimplex<Digraph>::FIRST_ELIGIBLE; |
|
| 272 |
checkMcf(mcf1, mcf1.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr), |
|
| 275 |
checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::FIRST_ELIGIBLE), |
|
| 273 | 276 |
gr, l2, u, c, s1, true, 5970, "#B1"); |
| 274 |
pr = NetworkSimplex<Digraph>::BEST_ELIGIBLE; |
|
| 275 |
checkMcf(mcf2, mcf2.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr), |
|
| 277 |
checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BEST_ELIGIBLE), |
|
| 276 | 278 |
gr, l2, u, c, s1, true, 5970, "#B2"); |
| 277 |
pr = NetworkSimplex<Digraph>::BLOCK_SEARCH; |
|
| 278 |
checkMcf(mcf3, mcf3.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr), |
|
| 279 |
checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BLOCK_SEARCH), |
|
| 279 | 280 |
gr, l2, u, c, s1, true, 5970, "#B3"); |
| 280 |
pr = NetworkSimplex<Digraph>::CANDIDATE_LIST; |
|
| 281 |
checkMcf(mcf4, mcf4.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr), |
|
| 281 |
checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::CANDIDATE_LIST), |
|
| 282 | 282 |
gr, l2, u, c, s1, true, 5970, "#B4"); |
| 283 |
pr = NetworkSimplex<Digraph>::ALTERING_LIST; |
|
| 284 |
checkMcf(mcf5, mcf5.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr), |
|
| 283 |
checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::ALTERING_LIST), |
|
| 285 | 284 |
gr, l2, u, c, s1, true, 5970, "#B5"); |
0 comments (0 inline)