COIN-OR::LEMON - Graph Library

Changeset 1385:8db773f19586 in lemon


Ignore:
Timestamp:
03/22/18 18:56:47 (5 months ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Children:
1388:0fdf84c79bc1, 1391:411819b8702c
Message:

Fix tolerance usage in Preflow algorithm (#608)

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/preflow.h

    r1270 r1385  
    477477    /// flow to the given \c flowMap. The \c flowMap should contain a 
    478478    /// flow or at least a preflow, i.e. at each node excluding the 
    479     /// source node the incoming flow should greater or equal to the 
     479    /// source node the incoming flow should be greater or equal to the 
    480480    /// outgoing flow. 
    481481    /// \return \c false if the given \c flowMap is not a preflow. 
     
    496496          excess -= (*_flow)[e]; 
    497497        } 
    498         if (excess < 0 && n != _source) return false; 
     498        if (_tolerance.negative(excess) && n != _source) return false; 
    499499        (*_excess)[n] = excess; 
    500500      } 
     
    640640          (*_excess)[n] = excess; 
    641641 
    642           if (excess != 0) { 
     642          if (_tolerance.nonZero(excess)) { 
    643643            if (new_level + 1 < _level->maxLevel()) { 
    644644              _level->liftHighestActive(new_level + 1); 
     
    721721          (*_excess)[n] = excess; 
    722722 
    723           if (excess != 0) { 
     723          if (_tolerance.nonZero(excess)) { 
    724724            if (new_level + 1 < _level->maxLevel()) { 
    725725              _level->liftActiveOn(level, new_level + 1); 
     
    792792        if (!reached[n]) { 
    793793          _level->dirtyTopButOne(n); 
    794         } else if ((*_excess)[n] > 0 && _target != n) { 
     794        } else if (_tolerance.positive((*_excess)[n]) && _target != n) { 
    795795          _level->activate(n); 
    796796        } 
     
    853853        (*_excess)[n] = excess; 
    854854 
    855         if (excess != 0) { 
     855        if (_tolerance.nonZero(excess)) { 
    856856          if (new_level + 1 < _level->maxLevel()) { 
    857857            _level->liftHighestActive(new_level + 1); 
  • test/max_flow_test.cc

    r1384 r1385  
    6767  "target 8\n"; 
    6868 
     69char 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 
    69101// Checks the general interface of a max flow algorithm 
    70102template <typename GR, typename CAP> 
     
    259291  CapMap cap(g); 
    260292  std::istringstream input(input_lgf); 
    261   DigraphReader<Digraph>(g,input) 
     293  DigraphReader<Digraph>(g, input) 
    262294      .arcMap("capacity", cap) 
    263       .node("source",s) 
    264       .node("target",t) 
     295      .node("source", s) 
     296      .node("target", t) 
    265297      .run(); 
    266298 
     
    281313 
    282314  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]; 
    285317  max_flow.init(flow); 
    286318 
     
    291323  min_cut_value = cutValue(g, min_cut1, cap); 
    292324 
    293   check(!tol.different(2 * expected, max_flow.flowValue()), 
     325  check(!tol.different(17 * expected, max_flow.flowValue()), 
    294326        "Incorrect max flow value."); 
    295   check(!tol.different(2 * expected, min_cut_value), 
     327  check(!tol.different(17 * expected, min_cut_value), 
    296328        "Incorrect min cut value."); 
    297329 
     
    305337  min_cut_value = cutValue(g, min_cut2, cap); 
    306338 
    307   check(!tol.different(2 * expected, max_flow.flowValue()), 
     339  check(!tol.different(17 * expected, max_flow.flowValue()), 
    308340        "Incorrect max flow value."); 
    309   check(!tol.different(2 * expected, min_cut_value), 
     341  check(!tol.different(17 * expected, min_cut_value), 
    310342        "Incorrect min cut value."); 
    311343 
     
    383415  typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2; 
    384416  typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<double> > PType3; 
     417 
    385418  checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >(test_lgf, 13); 
    386419  checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf, 13); 
    387420  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); 
    388424 
    389425  checkInitPreflow(); 
     
    393429  typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2; 
    394430  typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<double> > EKType3; 
     431 
    395432  checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >(test_lgf, 13); 
    396433  checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf, 13); 
    397434  checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf, 13); 
    398435 
     436  checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf_float, 0.3); 
     437  checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf_float, 0.3); 
     438 
    399439  return 0; 
    400440} 
Note: See TracChangeset for help on using the changeset viewer.