Changeset 1385:8db773f19586 in lemon
 Timestamp:
 03/22/18 18:56:47 (2 years ago)
 Branch:
 default
 Children:
 1388:0fdf84c79bc1, 1391:411819b8702c, 1394:2e0c2c25d63e
 Phase:
 public
 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
r1384 r1385 67 67 "target 8\n"; 68 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"; 100 69 101 // Checks the general interface of a max flow algorithm 70 102 template <typename GR, typename CAP> … … 259 291 CapMap cap(g); 260 292 std::istringstream input(input_lgf); 261 DigraphReader<Digraph>(g, input)293 DigraphReader<Digraph>(g, input) 262 294 .arcMap("capacity", cap) 263 .node("source", s)264 .node("target", t)295 .node("source", s) 296 .node("target", t) 265 297 .run(); 266 298 … … 281 313 282 314 FlowMap flow(g); 283 for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e];284 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]; 285 317 max_flow.init(flow); 286 318 … … 291 323 min_cut_value = cutValue(g, min_cut1, cap); 292 324 293 check(!tol.different( 2* expected, max_flow.flowValue()),325 check(!tol.different(17 * expected, max_flow.flowValue()), 294 326 "Incorrect max flow value."); 295 check(!tol.different( 2* expected, min_cut_value),327 check(!tol.different(17 * expected, min_cut_value), 296 328 "Incorrect min cut value."); 297 329 … … 305 337 min_cut_value = cutValue(g, min_cut2, cap); 306 338 307 check(!tol.different( 2* expected, max_flow.flowValue()),339 check(!tol.different(17 * expected, max_flow.flowValue()), 308 340 "Incorrect max flow value."); 309 check(!tol.different( 2* expected, min_cut_value),341 check(!tol.different(17 * expected, min_cut_value), 310 342 "Incorrect min cut value."); 311 343 … … 383 415 typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2; 384 416 typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<double> > PType3; 417 385 418 checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >(test_lgf, 13); 386 419 checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf, 13); 387 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); 388 424 389 425 checkInitPreflow(); … … 393 429 typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2; 394 430 typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<double> > EKType3; 431 395 432 checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >(test_lgf, 13); 396 433 checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf, 13); 397 434 checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf, 13); 398 435 436 checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf_float, 0.3); 437 checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf_float, 0.3); 438 399 439 return 0; 400 440 }
Note: See TracChangeset
for help on using the changeset viewer.