Changes in / [1387:50b7e16a135a:1388:0fdf84c79bc1] in lemon
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/preflow.h
r1270 r1385 477 477 /// flow to the given \c flowMap. The \c flowMap should contain a 478 478 /// flow or at least a preflow, i.e. at each node excluding the 479 /// source node the incoming flow should greater or equal to the479 /// source node the incoming flow should be greater or equal to the 480 480 /// outgoing flow. 481 481 /// \return \c false if the given \c flowMap is not a preflow. … … 496 496 excess = (*_flow)[e]; 497 497 } 498 if ( excess < 0&& n != _source) return false;498 if (_tolerance.negative(excess) && n != _source) return false; 499 499 (*_excess)[n] = excess; 500 500 } … … 640 640 (*_excess)[n] = excess; 641 641 642 if ( excess != 0) {642 if (_tolerance.nonZero(excess)) { 643 643 if (new_level + 1 < _level>maxLevel()) { 644 644 _level>liftHighestActive(new_level + 1); … … 721 721 (*_excess)[n] = excess; 722 722 723 if ( excess != 0) {723 if (_tolerance.nonZero(excess)) { 724 724 if (new_level + 1 < _level>maxLevel()) { 725 725 _level>liftActiveOn(level, new_level + 1); … … 792 792 if (!reached[n]) { 793 793 _level>dirtyTopButOne(n); 794 } else if ( (*_excess)[n] > 0&& _target != n) {794 } else if (_tolerance.positive((*_excess)[n]) && _target != n) { 795 795 _level>activate(n); 796 796 } … … 853 853 (*_excess)[n] = excess; 854 854 855 if ( excess != 0) {855 if (_tolerance.nonZero(excess)) { 856 856 if (new_level + 1 < _level>maxLevel()) { 857 857 _level>liftHighestActive(new_level + 1); 
test/max_flow_test.cc
r1270 r1385 27 27 #include <lemon/lgf_reader.h> 28 28 #include <lemon/elevator.h> 29 #include <lemon/tolerance.h> 29 30 30 31 using namespace lemon; … … 66 67 "target 8\n"; 67 68 69 char test_lgf_float[] = 70 "@nodes\n" 71 "label\n" 72 "0\n" 73 "1\n" 74 "2\n" 75 "3\n" 76 "4\n" 77 "5\n" 78 "6\n" 79 "7\n" 80 "8\n" 81 "9\n" 82 "@arcs\n" 83 " capacity\n" 84 "0 1 0.1\n" 85 "0 2 0.1\n" 86 "0 3 0.1\n" 87 "1 4 0.1\n" 88 "2 4 0.1\n" 89 "3 4 0.1\n" 90 "4 5 0.3\n" 91 "5 6 0.1\n" 92 "5 7 0.1\n" 93 "5 8 0.1\n" 94 "6 9 0.1\n" 95 "7 9 0.1\n" 96 "8 9 0.1\n" 97 "@attributes\n" 98 "source 0\n" 99 "target 9\n"; 68 100 69 101 // Checks the general interface of a max flow algorithm … … 166 198 typedef concepts::Digraph Digraph; 167 199 typedef concepts::ReadMap<Digraph::Arc, Value> CapMap; 168 typedef Elevator<Digraph, Digraph::Node> Elev;169 typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;170 200 171 201 Digraph g; … … 185 215 186 216 template <typename T> 187 T cutValue 188 189 190 191 T c =0;192 for (SmartDigraph::ArcIt e(g); e!=INVALID; ++e) {193 if (cut[g.source(e)] && !cut[g.target(e)]) c +=cap[e];217 T cutValue(const SmartDigraph& g, 218 const SmartDigraph::NodeMap<bool>& cut, 219 const SmartDigraph::ArcMap<T>& cap) { 220 221 T c = 0; 222 for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) { 223 if (cut[g.source(e)] && !cut[g.target(e)]) c += cap[e]; 194 224 } 195 225 return c; … … 200 230 const SmartDigraph::ArcMap<T>& flow, 201 231 const SmartDigraph::ArcMap<T>& cap, 202 SmartDigraph::Node s, SmartDigraph::Node t) { 232 SmartDigraph::Node s, SmartDigraph::Node t, 233 const Tolerance<T>& tol) { 203 234 204 235 for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) { 205 if ( flow[e] < 0  flow[e] > cap[e]) return false;236 if (tol.negative(flow[e])  tol.less(cap[e], flow[e])) return false; 206 237 } 207 238 … … 215 246 sum = flow[e]; 216 247 } 217 if ( sum != 0) return false;248 if (tol.nonZero(sum)) return false; 218 249 } 219 250 return true; 220 251 } 221 252 222 void initFlowTest()253 void checkInitPreflow() 223 254 { 224 255 DIGRAPH_TYPEDEFS(SmartDigraph); 225 256 226 257 SmartDigraph g; 227 SmartDigraph::ArcMap<int> cap(g), iflow(g);228 Node s =g.addNode(); Node t=g.addNode();229 Node n1 =g.addNode(); Node n2=g.addNode();258 SmartDigraph::ArcMap<int> cap(g), iflow(g); 259 Node s = g.addNode(); Node t = g.addNode(); 260 Node n1 = g.addNode(); Node n2 = g.addNode(); 230 261 Arc a; 231 a =g.addArc(s,n1); cap[a]=20; iflow[a]=20;232 a =g.addArc(n1,n2); cap[a]=10; iflow[a]=0;233 a =g.addArc(n2,t); cap[a]=20; iflow[a]=0;234 235 Preflow<SmartDigraph> pre(g, cap,s,t);262 a = g.addArc(s, n1); cap[a] = 20; iflow[a] = 20; 263 a = g.addArc(n1, n2); cap[a] = 10; iflow[a] = 0; 264 a = g.addArc(n2, t); cap[a] = 20; iflow[a] = 0; 265 266 Preflow<SmartDigraph> pre(g, cap, s, t); 236 267 pre.init(iflow); 237 268 pre.startFirstPhase(); 238 check(pre.flowValue() == 10, "The incorrect max flow value."); 269 270 check(pre.flowValue() == 10, "Incorrect max flow value."); 239 271 check(pre.minCut(s), "Wrong min cut (Node s)."); 240 272 check(pre.minCut(n1), "Wrong min cut (Node n1)."); … … 244 276 245 277 template <typename MF, typename SF> 246 void checkMaxFlowAlg( ) {278 void checkMaxFlowAlg(const char *input_lgf, typename MF::Value expected) { 247 279 typedef SmartDigraph Digraph; 248 280 DIGRAPH_TYPEDEFS(Digraph); … … 253 285 typedef BoolNodeMap CutMap; 254 286 287 Tolerance<Value> tol; 288 255 289 Digraph g; 256 290 Node s, t; 257 291 CapMap cap(g); 258 std::istringstream input( test_lgf);259 DigraphReader<Digraph>(g, input)292 std::istringstream input(input_lgf); 293 DigraphReader<Digraph>(g, input) 260 294 .arcMap("capacity", cap) 261 .node("source", s)262 .node("target", t)295 .node("source", s) 296 .node("target", t) 263 297 .run(); 264 298 … … 266 300 max_flow.run(); 267 301 268 check(checkFlow(g, max_flow.flowMap(), cap, s, t), 302 check(!tol.different(expected, max_flow.flowValue()), 303 "Incorrect max flow value."); 304 check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol), 269 305 "The flow is not feasible."); 270 306 … … 273 309 Value min_cut_value = cutValue(g, min_cut, cap); 274 310 275 check( max_flow.flowValue() == min_cut_value,276 " The max flow value is not equal to themin cut value.");311 check(!tol.different(expected, min_cut_value), 312 "Incorrect min cut value."); 277 313 278 314 FlowMap flow(g); 279 for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e]; 280 281 Value flow_value = max_flow.flowValue(); 282 283 for (ArcIt e(g); e != INVALID; ++e) cap[e] = 2 * cap[e]; 315 for (ArcIt e(g); e != INVALID; ++e) flow[e] = 13 * max_flow.flowMap()[e]; 316 for (ArcIt e(g); e != INVALID; ++e) cap[e] = 17 * cap[e]; 284 317 max_flow.init(flow); 285 318 … … 290 323 min_cut_value = cutValue(g, min_cut1, cap); 291 324 292 check(max_flow.flowValue() == min_cut_value && 293 min_cut_value == 2 * flow_value, 294 "The max flow value or the min cut value is wrong."); 325 check(!tol.different(17 * expected, max_flow.flowValue()), 326 "Incorrect max flow value."); 327 check(!tol.different(17 * expected, min_cut_value), 328 "Incorrect min cut value."); 295 329 296 330 SF::startSecondPhase(max_flow); // start second phase of the algorithm 297 331 298 check(checkFlow(g, max_flow.flowMap(), cap, s, t ),332 check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol), 299 333 "The flow is not feasible."); 300 334 … … 303 337 min_cut_value = cutValue(g, min_cut2, cap); 304 338 305 check( max_flow.flowValue() == min_cut_value &&306 min_cut_value == 2 * flow_value,307 "The max flow value or the min cut value was not doubled");308 339 check(!tol.different(17 * expected, max_flow.flowValue()), 340 "Incorrect max flow value."); 341 check(!tol.different(17 * expected, min_cut_value), 342 "Incorrect min cut value."); 309 343 310 344 max_flow.flowMap(flow); … … 325 359 CutMap min_cut3(g); 326 360 max_flow.minCutMap(min_cut3); 327 min_cut_value =cutValue(g, min_cut3, cap);328 329 check( max_flow.flowValue() == min_cut_value,361 min_cut_value = cutValue(g, min_cut3, cap); 362 363 check(!tol.different(max_flow.flowValue(), min_cut_value), 330 364 "The max flow value or the min cut value is wrong."); 331 365 } … … 380 414 typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<int> > PType1; 381 415 typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2; 382 checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >(); 383 checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(); 384 initFlowTest(); 416 typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<double> > PType3; 417 418 checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >(test_lgf, 13); 419 checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf, 13); 420 checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf, 13); 421 422 checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf_float, 0.3); 423 checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf_float, 0.3); 424 425 checkInitPreflow(); 385 426 386 427 // Check EdmondsKarp 387 428 typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<int> > EKType1; 388 429 typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2; 389 checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >(); 390 checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(); 391 392 initFlowTest(); 430 typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<double> > EKType3; 431 432 checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >(test_lgf, 13); 433 checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf, 13); 434 checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf, 13); 435 436 checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf_float, 0.3); 437 checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf_float, 0.3); 393 438 394 439 return 0;
Note: See TracChangeset
for help on using the changeset viewer.