r653:c7d160f73d52
Wed, 25 Mar 2009 21:37:50
[Not Reviewed]
0 comments (0 inline)
0
2
0
| ... | ... |
@@ -38,18 +38,24 @@ |
| 38 | 38 |
|
| 39 | 39 |
/// \brief Implementation of the primal Network Simplex algorithm |
| 40 | 40 |
/// for finding a \ref min_cost_flow "minimum cost flow". |
| 41 | 41 |
/// |
| 42 | 42 |
/// \ref NetworkSimplex implements the primal Network Simplex algorithm |
| 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 |
/// |
| 45 | 51 |
/// \tparam GR The digraph type the algorithm runs on. |
| 46 | 52 |
/// \tparam V The value type used in the algorithm. |
| 47 | 53 |
/// By default it is \c int. |
| 48 | 54 |
/// |
| 49 |
/// \warning |
|
| 55 |
/// \warning The value type must be a signed integer type. |
|
| 50 | 56 |
/// |
| 51 | 57 |
/// \note %NetworkSimplex provides five different pivot rule |
| 52 | 58 |
/// implementations. For more information see \ref PivotRule. |
| 53 | 59 |
template <typename GR, typename V = int> |
| 54 | 60 |
class NetworkSimplex |
| 55 | 61 |
{
|
| ... | ... |
@@ -795,20 +801,70 @@ |
| 795 | 801 |
/// \code |
| 796 | 802 |
/// NetworkSimplex<ListDigraph> ns(graph); |
| 797 | 803 |
/// ns.boundMaps(lower, upper).costMap(cost) |
| 798 | 804 |
/// .supplyMap(sup).run(); |
| 799 | 805 |
/// \endcode |
| 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 |
| 802 | 813 |
/// algorithm. For more information see \ref PivotRule. |
| 803 | 814 |
/// |
| 804 | 815 |
/// \return \c true if a feasible flow can be found. |
| 805 | 816 |
bool run(PivotRule pivot_rule = BLOCK_SEARCH) {
|
| 806 | 817 |
return init() && start(pivot_rule); |
| 807 | 818 |
} |
| 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 |
/// @} |
| 810 | 866 |
|
| 811 | 867 |
/// \name Query Functions |
| 812 | 868 |
/// The results of the algorithm can be obtained using these |
| 813 | 869 |
/// functions.\n |
| 814 | 870 |
/// The \ref run() function must be called before using them. |
| ... | ... |
@@ -917,23 +973,23 @@ |
| 917 | 973 |
_source.resize(all_arc_num); |
| 918 | 974 |
_target.resize(all_arc_num); |
| 919 | 975 |
|
| 920 | 976 |
_cap.resize(all_arc_num); |
| 921 | 977 |
_cost.resize(all_arc_num); |
| 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 |
|
| 926 | 982 |
_parent.resize(all_node_num); |
| 927 | 983 |
_pred.resize(all_node_num); |
| 928 | 984 |
_forward.resize(all_node_num); |
| 929 | 985 |
_thread.resize(all_node_num); |
| 930 | 986 |
_rev_thread.resize(all_node_num); |
| 931 | 987 |
_succ_num.resize(all_node_num); |
| 932 | 988 |
_last_succ.resize(all_node_num); |
| 933 |
_state.resize(all_arc_num |
|
| 989 |
_state.resize(all_arc_num); |
|
| 934 | 990 |
|
| 935 | 991 |
// Initialize node related data |
| 936 | 992 |
bool valid_supply = true; |
| 937 | 993 |
if (!_pstsup && !_psupply) {
|
| 938 | 994 |
_pstsup = true; |
| 939 | 995 |
_psource = _ptarget = NodeIt(_graph); |
| ... | ... |
@@ -983,18 +1039,22 @@ |
| 983 | 1039 |
for (int i = 0; i != _arc_num; ++i) {
|
| 984 | 1040 |
Arc e = _arc_ref[i]; |
| 985 | 1041 |
_source[i] = _node_id[_graph.source(e)]; |
| 986 | 1042 |
_target[i] = _node_id[_graph.target(e)]; |
| 987 | 1043 |
_cap[i] = (*_pupper)[e]; |
| 988 | 1044 |
_cost[i] = (*_pcost)[e]; |
| 1045 |
_flow[i] = 0; |
|
| 1046 |
_state[i] = STATE_LOWER; |
|
| 989 | 1047 |
} |
| 990 | 1048 |
} else {
|
| 991 | 1049 |
for (int i = 0; i != _arc_num; ++i) {
|
| 992 | 1050 |
Arc e = _arc_ref[i]; |
| 993 | 1051 |
_source[i] = _node_id[_graph.source(e)]; |
| 994 | 1052 |
_target[i] = _node_id[_graph.target(e)]; |
| 1053 |
_flow[i] = 0; |
|
| 1054 |
_state[i] = STATE_LOWER; |
|
| 995 | 1055 |
} |
| 996 | 1056 |
if (_pupper) {
|
| 997 | 1057 |
for (int i = 0; i != _arc_num; ++i) |
| 998 | 1058 |
_cap[i] = (*_pupper)[_arc_ref[i]]; |
| 999 | 1059 |
} else {
|
| 1000 | 1060 |
Value val = std::numeric_limits<Value>::max(); |
| ... | ... |
@@ -1029,24 +1089,24 @@ |
| 1029 | 1089 |
_thread[u] = u + 1; |
| 1030 | 1090 |
_rev_thread[u + 1] = u; |
| 1031 | 1091 |
_succ_num[u] = 1; |
| 1032 | 1092 |
_last_succ[u] = u; |
| 1033 | 1093 |
_parent[u] = _root; |
| 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) {
|
| 1036 | 1099 |
_flow[e] = _supply[u]; |
| 1037 | 1100 |
_forward[u] = true; |
| 1038 | 1101 |
_pi[u] = -max_cost; |
| 1039 | 1102 |
} else {
|
| 1040 | 1103 |
_flow[e] = -_supply[u]; |
| 1041 | 1104 |
_forward[u] = false; |
| 1042 | 1105 |
_pi[u] = max_cost; |
| 1043 | 1106 |
} |
| 1044 |
_cost[e] = max_cost; |
|
| 1045 |
_cap[e] = max_cap; |
|
| 1046 |
_state[e] = STATE_TREE; |
|
| 1047 | 1107 |
} |
| 1048 | 1108 |
|
| 1049 | 1109 |
return true; |
| 1050 | 1110 |
} |
| 1051 | 1111 |
|
| 1052 | 1112 |
// Find the join node |
| ... | ... |
@@ -86,13 +86,14 @@ |
| 86 | 86 |
struct Constraints {
|
| 87 | 87 |
void constraints() {
|
| 88 | 88 |
checkConcept<concepts::Digraph, GR>(); |
| 89 | 89 |
|
| 90 | 90 |
MCF mcf(g); |
| 91 | 91 |
|
| 92 |
b = mcf. |
|
| 92 |
b = mcf.reset() |
|
| 93 |
.lowerMap(lower) |
|
| 93 | 94 |
.upperMap(upper) |
| 94 | 95 |
.capacityMap(upper) |
| 95 | 96 |
.boundMaps(lower, upper) |
| 96 | 97 |
.costMap(cost) |
| 97 | 98 |
.supplyMap(sup) |
| 98 | 99 |
.stSupply(n, n, k) |
| ... | ... |
@@ -239,51 +240,49 @@ |
| 239 | 240 |
.node("source", v)
|
| 240 | 241 |
.node("target", w)
|
| 241 | 242 |
.run(); |
| 242 | 243 |
|
| 243 | 244 |
// A. Test NetworkSimplex with the default pivot rule |
| 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"); |
| 264 | 268 |
} |
| 265 | 269 |
|
| 266 | 270 |
// B. Test NetworkSimplex with each pivot rule |
| 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"); |
| 286 | 285 |
} |
| 287 | 286 |
|
| 288 | 287 |
return 0; |
| 289 | 288 |
} |
0 comments (0 inline)