Changeset 656:e6927fe719e6 in lemon for test/min_cost_flow_test.cc
 Timestamp:
 04/17/09 18:04:36 (14 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

test/min_cost_flow_test.cc
r654 r656 34 34 char test_lgf[] = 35 35 "@nodes\n" 36 "label sup1 sup2 sup3 \n"37 " 1 20 27 0 \n"38 " 2 4 0 0 \n"39 " 3 0 0 0 \n"40 " 4 0 0 0 \n"41 " 5 9 0 0 \n"42 " 6 6 0 0 \n"43 " 7 0 0 0 \n"44 " 8 0 0 0 \n"45 " 9 3 0 0 \n"46 " 10 2 0 0 \n"47 " 11 0 0 0 \n"48 " 12 20 27 0 \n"36 "label sup1 sup2 sup3 sup4 sup5\n" 37 " 1 20 27 0 20 30\n" 38 " 2 4 0 0 8 3\n" 39 " 3 0 0 0 0 0\n" 40 " 4 0 0 0 0 0\n" 41 " 5 9 0 0 6 11\n" 42 " 6 6 0 0 5 6\n" 43 " 7 0 0 0 0 0\n" 44 " 8 0 0 0 0 3\n" 45 " 9 3 0 0 0 0\n" 46 " 10 2 0 0 7 2\n" 47 " 11 0 0 0 10 0\n" 48 " 12 20 27 0 30 20\n" 49 49 "\n" 50 50 "@arcs\n" … … 77 77 78 78 79 enum ProblemType { 80 EQ, 81 GEQ, 82 LEQ 83 }; 84 79 85 // Check the interface of an MCF algorithm 80 86 template <typename GR, typename Flow, typename Cost> … … 98 104 .supplyMap(sup) 99 105 .stSupply(n, n, k) 106 .flowMap(flow) 107 .potentialMap(pot) 100 108 .run(); 101 102 const typename MCF::FlowMap &fm = mcf.flowMap();103 const typename MCF::PotentialMap &pm = mcf.potentialMap(); 104 105 v = mcf.totalCost();106 double x = mcf.template totalCost<double>(); 107 v = mcf.flow(a);108 v = mcf.potential(n);109 mcf.flowMap(flow);110 mcf.potentialMap(pot);109 110 const MCF& const_mcf = mcf; 111 112 const typename MCF::FlowMap &fm = const_mcf.flowMap(); 113 const typename MCF::PotentialMap &pm = const_mcf.potentialMap(); 114 115 v = const_mcf.totalCost(); 116 double x = const_mcf.template totalCost<double>(); 117 v = const_mcf.flow(a); 118 v = const_mcf.potential(n); 111 119 112 120 ignore_unused_variable_warning(fm); … … 143 151 typename SM, typename FM > 144 152 bool checkFlow( const GR& gr, const LM& lower, const UM& upper, 145 const SM& supply, const FM& flow ) 153 const SM& supply, const FM& flow, 154 ProblemType type = EQ ) 146 155 { 147 156 TEMPLATE_DIGRAPH_TYPEDEFS(GR); … … 157 166 for (InArcIt e(gr, n); e != INVALID; ++e) 158 167 sum = flow[e]; 159 if (sum != supply[n]) return false; 168 bool b = (type == EQ && sum == supply[n])  169 (type == GEQ && sum >= supply[n])  170 (type == LEQ && sum <= supply[n]); 171 if (!b) return false; 160 172 } 161 173 … … 166 178 // using the "Complementary Slackness" optimality condition 167 179 template < typename GR, typename LM, typename UM, 168 typename CM, typename FM, typename PM >180 typename CM, typename SM, typename FM, typename PM > 169 181 bool checkPotential( const GR& gr, const LM& lower, const UM& upper, 170 const CM& cost, const FM& flow, const PM& pi ) 182 const CM& cost, const SM& supply, const FM& flow, 183 const PM& pi ) 171 184 { 172 185 TEMPLATE_DIGRAPH_TYPEDEFS(GR); … … 180 193 (red_cost < 0 && flow[e] == upper[e]); 181 194 } 195 196 for (NodeIt n(gr); opt && n != INVALID; ++n) { 197 typename SM::Value sum = 0; 198 for (OutArcIt e(gr, n); e != INVALID; ++e) 199 sum += flow[e]; 200 for (InArcIt e(gr, n); e != INVALID; ++e) 201 sum = flow[e]; 202 opt = (sum == supply[n])  (pi[n] == 0); 203 } 204 182 205 return opt; 183 206 } … … 191 214 const CM& cost, const SM& supply, 192 215 bool result, typename CM::Value total, 193 const std::string &test_id = "" ) 216 const std::string &test_id = "", 217 ProblemType type = EQ ) 194 218 { 195 219 check(mcf_result == result, "Wrong result " + test_id); 196 220 if (result) { 197 check(checkFlow(gr, lower, upper, supply, mcf.flowMap() ),221 check(checkFlow(gr, lower, upper, supply, mcf.flowMap(), type), 198 222 "The flow is not feasible " + test_id); 199 223 check(mcf.totalCost() == total, "The flow is not optimal " + test_id); 200 check(checkPotential(gr, lower, upper, cost, mcf.flowMap(),224 check(checkPotential(gr, lower, upper, cost, supply, mcf.flowMap(), 201 225 mcf.potentialMap()), 202 226 "Wrong potentials " + test_id); … … 227 251 Digraph gr; 228 252 Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), u(gr); 229 Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr) ;253 Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr); 230 254 ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max()); 231 255 Node v, w; … … 240 264 .nodeMap("sup2", s2) 241 265 .nodeMap("sup3", s3) 266 .nodeMap("sup4", s4) 267 .nodeMap("sup5", s5) 242 268 .node("source", v) 243 269 .node("target", w) … … 248 274 NetworkSimplex<Digraph> mcf(gr); 249 275 276 // Check the equality form 250 277 mcf.upperMap(u).costMap(c); 251 278 checkMcf(mcf, mcf.supplyMap(s1).run(), … … 268 295 checkMcf(mcf, mcf.boundMaps(l2, u).run(), 269 296 gr, l2, u, cc, s3, false, 0, "#A8"); 297 298 // Check the GEQ form 299 mcf.reset().upperMap(u).costMap(c).supplyMap(s4); 300 checkMcf(mcf, mcf.run(), 301 gr, l1, u, c, s4, true, 3530, "#A9", GEQ); 302 mcf.problemType(mcf.GEQ); 303 checkMcf(mcf, mcf.lowerMap(l2).run(), 304 gr, l2, u, c, s4, true, 4540, "#A10", GEQ); 305 mcf.problemType(mcf.CARRY_SUPPLIES).supplyMap(s5); 306 checkMcf(mcf, mcf.run(), 307 gr, l2, u, c, s5, false, 0, "#A11", GEQ); 308 309 // Check the LEQ form 310 mcf.reset().problemType(mcf.LEQ); 311 mcf.upperMap(u).costMap(c).supplyMap(s5); 312 checkMcf(mcf, mcf.run(), 313 gr, l1, u, c, s5, true, 5080, "#A12", LEQ); 314 checkMcf(mcf, mcf.lowerMap(l2).run(), 315 gr, l2, u, c, s5, true, 5930, "#A13", LEQ); 316 mcf.problemType(mcf.SATISFY_DEMANDS).supplyMap(s4); 317 checkMcf(mcf, mcf.run(), 318 gr, l2, u, c, s4, false, 0, "#A14", LEQ); 270 319 } 271 320
Note: See TracChangeset
for help on using the changeset viewer.