Use tolerance in max_flow_test.cc (#608)
authorPeter Kovacs <kpeter@inf.elte.hu>
Thu, 22 Mar 2018 18:55:59 +0100
changeset 1383e018899c2926
parent 1382 e2732b9da429
child 1384 259e3a90ad97
Use tolerance in max_flow_test.cc (#608)
test/max_flow_test.cc
     1.1 --- a/test/max_flow_test.cc	Thu Mar 22 18:55:31 2018 +0100
     1.2 +++ b/test/max_flow_test.cc	Thu Mar 22 18:55:59 2018 +0100
     1.3 @@ -26,6 +26,7 @@
     1.4  #include <lemon/concepts/maps.h>
     1.5  #include <lemon/lgf_reader.h>
     1.6  #include <lemon/elevator.h>
     1.7 +#include <lemon/tolerance.h>
     1.8  
     1.9  using namespace lemon;
    1.10  
    1.11 @@ -65,7 +66,6 @@
    1.12    "source 1\n"
    1.13    "target 8\n";
    1.14  
    1.15 -
    1.16  // Checks the general interface of a max flow algorithm
    1.17  template <typename GR, typename CAP>
    1.18  struct MaxFlowClassConcept
    1.19 @@ -197,10 +197,11 @@
    1.20  bool checkFlow(const SmartDigraph& g,
    1.21                 const SmartDigraph::ArcMap<T>& flow,
    1.22                 const SmartDigraph::ArcMap<T>& cap,
    1.23 -               SmartDigraph::Node s, SmartDigraph::Node t) {
    1.24 +               SmartDigraph::Node s, SmartDigraph::Node t,
    1.25 +               const Tolerance<T>& tol) {
    1.26  
    1.27    for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
    1.28 -    if (flow[e] < 0 || flow[e] > cap[e]) return false;
    1.29 +    if (tol.negative(flow[e]) || tol.less(cap[e], flow[e])) return false;
    1.30    }
    1.31  
    1.32    for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) {
    1.33 @@ -212,7 +213,7 @@
    1.34      for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) {
    1.35        sum -= flow[e];
    1.36      }
    1.37 -    if (sum != 0) return false;
    1.38 +    if (tol.nonZero(sum)) return false;
    1.39    }
    1.40    return true;
    1.41  }
    1.42 @@ -251,6 +252,8 @@
    1.43    typedef CapMap FlowMap;
    1.44    typedef BoolNodeMap CutMap;
    1.45  
    1.46 +  Tolerance<Value> tol;
    1.47 +
    1.48    Digraph g;
    1.49    Node s, t;
    1.50    CapMap cap(g);
    1.51 @@ -264,14 +267,14 @@
    1.52    MF max_flow(g, cap, s, t);
    1.53    max_flow.run();
    1.54  
    1.55 -  check(checkFlow(g, max_flow.flowMap(), cap, s, t),
    1.56 +  check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol),
    1.57          "The flow is not feasible.");
    1.58  
    1.59    CutMap min_cut(g);
    1.60    max_flow.minCutMap(min_cut);
    1.61    Value min_cut_value = cutValue(g, min_cut, cap);
    1.62  
    1.63 -  check(max_flow.flowValue() == min_cut_value,
    1.64 +  check(!tol.different(max_flow.flowValue(), min_cut_value),
    1.65          "The max flow value is not equal to the min cut value.");
    1.66  
    1.67    FlowMap flow(g);
    1.68 @@ -288,21 +291,21 @@
    1.69    max_flow.minCutMap(min_cut1);
    1.70    min_cut_value = cutValue(g, min_cut1, cap);
    1.71  
    1.72 -  check(max_flow.flowValue() == min_cut_value &&
    1.73 -        min_cut_value == 2 * flow_value,
    1.74 +  check(!tol.different(max_flow.flowValue(), min_cut_value) &&
    1.75 +        !tol.different(min_cut_value, 2 * flow_value),
    1.76          "The max flow value or the min cut value is wrong.");
    1.77  
    1.78    SF::startSecondPhase(max_flow);       // start second phase of the algorithm
    1.79  
    1.80 -  check(checkFlow(g, max_flow.flowMap(), cap, s, t),
    1.81 +  check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol),
    1.82          "The flow is not feasible.");
    1.83  
    1.84    CutMap min_cut2(g);
    1.85    max_flow.minCutMap(min_cut2);
    1.86    min_cut_value = cutValue(g, min_cut2, cap);
    1.87  
    1.88 -  check(max_flow.flowValue() == min_cut_value &&
    1.89 -        min_cut_value == 2 * flow_value,
    1.90 +  check(!tol.different(max_flow.flowValue(), min_cut_value) &&
    1.91 +        !tol.different(min_cut_value, 2 * flow_value),
    1.92          "The max flow value or the min cut value was not doubled.");
    1.93  
    1.94    max_flow.flowMap(flow);
    1.95 @@ -324,7 +327,7 @@
    1.96    max_flow.minCutMap(min_cut3);
    1.97    min_cut_value = cutValue(g, min_cut3, cap);
    1.98  
    1.99 -  check(max_flow.flowValue() == min_cut_value,
   1.100 +  check(!tol.different(max_flow.flowValue(), min_cut_value),
   1.101          "The max flow value or the min cut value is wrong.");
   1.102  }
   1.103