COIN-OR::LEMON - Graph Library

Changeset 1385:8db773f19586 in lemon


Ignore:
Timestamp:
03/22/18 18:56:47 (7 months ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Children:
1388:0fdf84c79bc1, 1391:411819b8702c, 1394:2e0c2c25d63e
Phase:
public
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.