Fix tolerance usage in Preflow algorithm (#608)
authorPeter Kovacs <kpeter@inf.elte.hu>
Thu, 22 Mar 2018 18:56:47 +0100
changeset 11638db773f19586
parent 1162 259e3a90ad97
child 1166 411819b8702c
child 1169 2e0c2c25d63e
Fix tolerance usage in Preflow algorithm (#608)
lemon/preflow.h
test/max_flow_test.cc
     1.1 --- a/lemon/preflow.h	Thu Mar 22 18:56:26 2018 +0100
     1.2 +++ b/lemon/preflow.h	Thu Mar 22 18:56:47 2018 +0100
     1.3 @@ -476,7 +476,7 @@
     1.4      /// Initializes the internal data structures and sets the initial
     1.5      /// flow to the given \c flowMap. The \c flowMap should contain a
     1.6      /// flow or at least a preflow, i.e. at each node excluding the
     1.7 -    /// source node the incoming flow should greater or equal to the
     1.8 +    /// source node the incoming flow should be greater or equal to the
     1.9      /// outgoing flow.
    1.10      /// \return \c false if the given \c flowMap is not a preflow.
    1.11      template <typename FlowMap>
    1.12 @@ -495,7 +495,7 @@
    1.13          for (OutArcIt e(_graph, n); e != INVALID; ++e) {
    1.14            excess -= (*_flow)[e];
    1.15          }
    1.16 -        if (excess < 0 && n != _source) return false;
    1.17 +        if (_tolerance.negative(excess) && n != _source) return false;
    1.18          (*_excess)[n] = excess;
    1.19        }
    1.20  
    1.21 @@ -639,7 +639,7 @@
    1.22  
    1.23            (*_excess)[n] = excess;
    1.24  
    1.25 -          if (excess != 0) {
    1.26 +          if (_tolerance.nonZero(excess)) {
    1.27              if (new_level + 1 < _level->maxLevel()) {
    1.28                _level->liftHighestActive(new_level + 1);
    1.29              } else {
    1.30 @@ -720,7 +720,7 @@
    1.31  
    1.32            (*_excess)[n] = excess;
    1.33  
    1.34 -          if (excess != 0) {
    1.35 +          if (_tolerance.nonZero(excess)) {
    1.36              if (new_level + 1 < _level->maxLevel()) {
    1.37                _level->liftActiveOn(level, new_level + 1);
    1.38              } else {
    1.39 @@ -791,7 +791,7 @@
    1.40        for (NodeIt n(_graph); n != INVALID; ++n) {
    1.41          if (!reached[n]) {
    1.42            _level->dirtyTopButOne(n);
    1.43 -        } else if ((*_excess)[n] > 0 && _target != n) {
    1.44 +        } else if (_tolerance.positive((*_excess)[n]) && _target != n) {
    1.45            _level->activate(n);
    1.46          }
    1.47        }
    1.48 @@ -852,7 +852,7 @@
    1.49  
    1.50          (*_excess)[n] = excess;
    1.51  
    1.52 -        if (excess != 0) {
    1.53 +        if (_tolerance.nonZero(excess)) {
    1.54            if (new_level + 1 < _level->maxLevel()) {
    1.55              _level->liftHighestActive(new_level + 1);
    1.56            } else {
     2.1 --- a/test/max_flow_test.cc	Thu Mar 22 18:56:26 2018 +0100
     2.2 +++ b/test/max_flow_test.cc	Thu Mar 22 18:56:47 2018 +0100
     2.3 @@ -66,6 +66,38 @@
     2.4    "source 1\n"
     2.5    "target 8\n";
     2.6  
     2.7 +char test_lgf_float[] =
     2.8 +  "@nodes\n"
     2.9 +  "label\n"
    2.10 +  "0\n"
    2.11 +  "1\n"
    2.12 +  "2\n"
    2.13 +  "3\n"
    2.14 +  "4\n"
    2.15 +  "5\n"
    2.16 +  "6\n"
    2.17 +  "7\n"
    2.18 +  "8\n"
    2.19 +  "9\n"
    2.20 +  "@arcs\n"
    2.21 +  "      capacity\n"
    2.22 +  "0 1 0.1\n"
    2.23 +  "0 2 0.1\n"
    2.24 +  "0 3 0.1\n"
    2.25 +  "1 4 0.1\n"
    2.26 +  "2 4 0.1\n"
    2.27 +  "3 4 0.1\n"
    2.28 +  "4 5 0.3\n"
    2.29 +  "5 6 0.1\n"
    2.30 +  "5 7 0.1\n"
    2.31 +  "5 8 0.1\n"
    2.32 +  "6 9 0.1\n"
    2.33 +  "7 9 0.1\n"
    2.34 +  "8 9 0.1\n"
    2.35 +  "@attributes\n"
    2.36 +  "source 0\n"
    2.37 +  "target 9\n";
    2.38 +
    2.39  // Checks the general interface of a max flow algorithm
    2.40  template <typename GR, typename CAP>
    2.41  struct MaxFlowClassConcept
    2.42 @@ -258,10 +290,10 @@
    2.43    Node s, t;
    2.44    CapMap cap(g);
    2.45    std::istringstream input(input_lgf);
    2.46 -  DigraphReader<Digraph>(g,input)
    2.47 +  DigraphReader<Digraph>(g, input)
    2.48        .arcMap("capacity", cap)
    2.49 -      .node("source",s)
    2.50 -      .node("target",t)
    2.51 +      .node("source", s)
    2.52 +      .node("target", t)
    2.53        .run();
    2.54  
    2.55    MF max_flow(g, cap, s, t);
    2.56 @@ -280,8 +312,8 @@
    2.57          "Incorrect min cut value.");
    2.58  
    2.59    FlowMap flow(g);
    2.60 -  for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e];
    2.61 -  for (ArcIt e(g); e != INVALID; ++e) cap[e] = 2 * cap[e];
    2.62 +  for (ArcIt e(g); e != INVALID; ++e) flow[e] = 13 * max_flow.flowMap()[e];
    2.63 +  for (ArcIt e(g); e != INVALID; ++e) cap[e] = 17 * cap[e];
    2.64    max_flow.init(flow);
    2.65  
    2.66    SF::startFirstPhase(max_flow);       // start first phase of the algorithm
    2.67 @@ -290,9 +322,9 @@
    2.68    max_flow.minCutMap(min_cut1);
    2.69    min_cut_value = cutValue(g, min_cut1, cap);
    2.70  
    2.71 -  check(!tol.different(2 * expected, max_flow.flowValue()),
    2.72 +  check(!tol.different(17 * expected, max_flow.flowValue()),
    2.73          "Incorrect max flow value.");
    2.74 -  check(!tol.different(2 * expected, min_cut_value),
    2.75 +  check(!tol.different(17 * expected, min_cut_value),
    2.76          "Incorrect min cut value.");
    2.77  
    2.78    SF::startSecondPhase(max_flow);       // start second phase of the algorithm
    2.79 @@ -304,9 +336,9 @@
    2.80    max_flow.minCutMap(min_cut2);
    2.81    min_cut_value = cutValue(g, min_cut2, cap);
    2.82  
    2.83 -  check(!tol.different(2 * expected, max_flow.flowValue()),
    2.84 +  check(!tol.different(17 * expected, max_flow.flowValue()),
    2.85          "Incorrect max flow value.");
    2.86 -  check(!tol.different(2 * expected, min_cut_value),
    2.87 +  check(!tol.different(17 * expected, min_cut_value),
    2.88          "Incorrect min cut value.");
    2.89  
    2.90    max_flow.flowMap(flow);
    2.91 @@ -382,19 +414,27 @@
    2.92    typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<int> > PType1;
    2.93    typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2;
    2.94    typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<double> > PType3;
    2.95 +
    2.96    checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >(test_lgf, 13);
    2.97    checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf, 13);
    2.98    checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf, 13);
    2.99  
   2.100 +  checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf_float, 0.3);
   2.101 +  checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf_float, 0.3);
   2.102 +
   2.103    checkInitPreflow();
   2.104  
   2.105    // Check EdmondsKarp
   2.106    typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<int> > EKType1;
   2.107    typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2;
   2.108    typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<double> > EKType3;
   2.109 +
   2.110    checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >(test_lgf, 13);
   2.111    checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf, 13);
   2.112    checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf, 13);
   2.113  
   2.114 +  checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf_float, 0.3);
   2.115 +  checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf_float, 0.3);
   2.116 +
   2.117    return 0;
   2.118  }