Merge #1.3 related bugfix heads
authorAlpar Juttner <alpar@cs.elte.hu>
Wed, 17 Oct 2018 18:56:32 +0200
changeset 11692e0c2c25d63e
parent 1168 afcd33be243f
parent 1163 8db773f19586
child 1170 f425c93848fa
Merge #1.3 related bugfix heads
     1.1 --- a/lemon/preflow.h	Wed Oct 17 18:56:08 2018 +0200
     1.2 +++ b/lemon/preflow.h	Wed Oct 17 18:56:32 2018 +0200
     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	Wed Oct 17 18:56:08 2018 +0200
     2.2 +++ b/test/max_flow_test.cc	Wed Oct 17 18:56:32 2018 +0200
     2.3 @@ -26,6 +26,7 @@
     2.4  #include <lemon/concepts/maps.h>
     2.5  #include <lemon/lgf_reader.h>
     2.6  #include <lemon/elevator.h>
     2.7 +#include <lemon/tolerance.h>
     2.8  
     2.9  using namespace lemon;
    2.10  
    2.11 @@ -65,6 +66,37 @@
    2.12    "source 1\n"
    2.13    "target 8\n";
    2.14  
    2.15 +char test_lgf_float[] =
    2.16 +  "@nodes\n"
    2.17 +  "label\n"
    2.18 +  "0\n"
    2.19 +  "1\n"
    2.20 +  "2\n"
    2.21 +  "3\n"
    2.22 +  "4\n"
    2.23 +  "5\n"
    2.24 +  "6\n"
    2.25 +  "7\n"
    2.26 +  "8\n"
    2.27 +  "9\n"
    2.28 +  "@arcs\n"
    2.29 +  "      capacity\n"
    2.30 +  "0 1 0.1\n"
    2.31 +  "0 2 0.1\n"
    2.32 +  "0 3 0.1\n"
    2.33 +  "1 4 0.1\n"
    2.34 +  "2 4 0.1\n"
    2.35 +  "3 4 0.1\n"
    2.36 +  "4 5 0.3\n"
    2.37 +  "5 6 0.1\n"
    2.38 +  "5 7 0.1\n"
    2.39 +  "5 8 0.1\n"
    2.40 +  "6 9 0.1\n"
    2.41 +  "7 9 0.1\n"
    2.42 +  "8 9 0.1\n"
    2.43 +  "@attributes\n"
    2.44 +  "source 0\n"
    2.45 +  "target 9\n";
    2.46  
    2.47  // Checks the general interface of a max flow algorithm
    2.48  template <typename GR, typename CAP>
    2.49 @@ -165,8 +197,6 @@
    2.50    typedef int Value;
    2.51    typedef concepts::Digraph Digraph;
    2.52    typedef concepts::ReadMap<Digraph::Arc, Value> CapMap;
    2.53 -  typedef Elevator<Digraph, Digraph::Node> Elev;
    2.54 -  typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
    2.55  
    2.56    Digraph g;
    2.57    Digraph::Node n;
    2.58 @@ -184,13 +214,13 @@
    2.59  
    2.60  
    2.61  template <typename T>
    2.62 -T cutValue (const SmartDigraph& g,
    2.63 -              const SmartDigraph::NodeMap<bool>& cut,
    2.64 -              const SmartDigraph::ArcMap<T>& cap) {
    2.65 +T cutValue(const SmartDigraph& g,
    2.66 +           const SmartDigraph::NodeMap<bool>& cut,
    2.67 +           const SmartDigraph::ArcMap<T>& cap) {
    2.68  
    2.69 -  T c=0;
    2.70 -  for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) {
    2.71 -    if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e];
    2.72 +  T c = 0;
    2.73 +  for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
    2.74 +    if (cut[g.source(e)] && !cut[g.target(e)]) c += cap[e];
    2.75    }
    2.76    return c;
    2.77  }
    2.78 @@ -199,10 +229,11 @@
    2.79  bool checkFlow(const SmartDigraph& g,
    2.80                 const SmartDigraph::ArcMap<T>& flow,
    2.81                 const SmartDigraph::ArcMap<T>& cap,
    2.82 -               SmartDigraph::Node s, SmartDigraph::Node t) {
    2.83 +               SmartDigraph::Node s, SmartDigraph::Node t,
    2.84 +               const Tolerance<T>& tol) {
    2.85  
    2.86    for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
    2.87 -    if (flow[e] < 0 || flow[e] > cap[e]) return false;
    2.88 +    if (tol.negative(flow[e]) || tol.less(cap[e], flow[e])) return false;
    2.89    }
    2.90  
    2.91    for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) {
    2.92 @@ -214,28 +245,29 @@
    2.93      for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) {
    2.94        sum -= flow[e];
    2.95      }
    2.96 -    if (sum != 0) return false;
    2.97 +    if (tol.nonZero(sum)) return false;
    2.98    }
    2.99    return true;
   2.100  }
   2.101  
   2.102 -void initFlowTest()
   2.103 +void checkInitPreflow()
   2.104  {
   2.105    DIGRAPH_TYPEDEFS(SmartDigraph);
   2.106  
   2.107    SmartDigraph g;
   2.108 -  SmartDigraph::ArcMap<int> cap(g),iflow(g);
   2.109 -  Node s=g.addNode(); Node t=g.addNode();
   2.110 -  Node n1=g.addNode(); Node n2=g.addNode();
   2.111 +  SmartDigraph::ArcMap<int> cap(g), iflow(g);
   2.112 +  Node s = g.addNode(); Node t = g.addNode();
   2.113 +  Node n1 = g.addNode(); Node n2 = g.addNode();
   2.114    Arc a;
   2.115 -  a=g.addArc(s,n1); cap[a]=20; iflow[a]=20;
   2.116 -  a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0;
   2.117 -  a=g.addArc(n2,t); cap[a]=20; iflow[a]=0;
   2.118 +  a = g.addArc(s, n1); cap[a] = 20; iflow[a] = 20;
   2.119 +  a = g.addArc(n1, n2); cap[a] = 10; iflow[a] = 0;
   2.120 +  a = g.addArc(n2, t); cap[a] = 20; iflow[a] = 0;
   2.121  
   2.122 -  Preflow<SmartDigraph> pre(g,cap,s,t);
   2.123 +  Preflow<SmartDigraph> pre(g, cap, s, t);
   2.124    pre.init(iflow);
   2.125    pre.startFirstPhase();
   2.126 -  check(pre.flowValue() == 10, "The incorrect max flow value.");
   2.127 +
   2.128 +  check(pre.flowValue() == 10, "Incorrect max flow value.");
   2.129    check(pre.minCut(s), "Wrong min cut (Node s).");
   2.130    check(pre.minCut(n1), "Wrong min cut (Node n1).");
   2.131    check(!pre.minCut(n2), "Wrong min cut (Node n2).");
   2.132 @@ -243,7 +275,7 @@
   2.133  }
   2.134  
   2.135  template <typename MF, typename SF>
   2.136 -void checkMaxFlowAlg() {
   2.137 +void checkMaxFlowAlg(const char *input_lgf,  typename MF::Value expected) {
   2.138    typedef SmartDigraph Digraph;
   2.139    DIGRAPH_TYPEDEFS(Digraph);
   2.140  
   2.141 @@ -252,35 +284,36 @@
   2.142    typedef CapMap FlowMap;
   2.143    typedef BoolNodeMap CutMap;
   2.144  
   2.145 +  Tolerance<Value> tol;
   2.146 +
   2.147    Digraph g;
   2.148    Node s, t;
   2.149    CapMap cap(g);
   2.150 -  std::istringstream input(test_lgf);
   2.151 -  DigraphReader<Digraph>(g,input)
   2.152 +  std::istringstream input(input_lgf);
   2.153 +  DigraphReader<Digraph>(g, input)
   2.154        .arcMap("capacity", cap)
   2.155 -      .node("source",s)
   2.156 -      .node("target",t)
   2.157 +      .node("source", s)
   2.158 +      .node("target", t)
   2.159        .run();
   2.160  
   2.161    MF max_flow(g, cap, s, t);
   2.162    max_flow.run();
   2.163  
   2.164 -  check(checkFlow(g, max_flow.flowMap(), cap, s, t),
   2.165 +  check(!tol.different(expected, max_flow.flowValue()),
   2.166 +        "Incorrect max flow value.");
   2.167 +  check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol),
   2.168          "The flow is not feasible.");
   2.169  
   2.170    CutMap min_cut(g);
   2.171    max_flow.minCutMap(min_cut);
   2.172    Value min_cut_value = cutValue(g, min_cut, cap);
   2.173  
   2.174 -  check(max_flow.flowValue() == min_cut_value,
   2.175 -        "The max flow value is not equal to the min cut value.");
   2.176 +  check(!tol.different(expected, min_cut_value),
   2.177 +        "Incorrect min cut value.");
   2.178  
   2.179    FlowMap flow(g);
   2.180 -  for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e];
   2.181 -
   2.182 -  Value flow_value = max_flow.flowValue();
   2.183 -
   2.184 -  for (ArcIt e(g); e != INVALID; ++e) cap[e] = 2 * cap[e];
   2.185 +  for (ArcIt e(g); e != INVALID; ++e) flow[e] = 13 * max_flow.flowMap()[e];
   2.186 +  for (ArcIt e(g); e != INVALID; ++e) cap[e] = 17 * cap[e];
   2.187    max_flow.init(flow);
   2.188  
   2.189    SF::startFirstPhase(max_flow);       // start first phase of the algorithm
   2.190 @@ -289,23 +322,24 @@
   2.191    max_flow.minCutMap(min_cut1);
   2.192    min_cut_value = cutValue(g, min_cut1, cap);
   2.193  
   2.194 -  check(max_flow.flowValue() == min_cut_value &&
   2.195 -        min_cut_value == 2 * flow_value,
   2.196 -        "The max flow value or the min cut value is wrong.");
   2.197 +  check(!tol.different(17 * expected, max_flow.flowValue()),
   2.198 +        "Incorrect max flow value.");
   2.199 +  check(!tol.different(17 * expected, min_cut_value),
   2.200 +        "Incorrect min cut value.");
   2.201  
   2.202    SF::startSecondPhase(max_flow);       // start second phase of the algorithm
   2.203  
   2.204 -  check(checkFlow(g, max_flow.flowMap(), cap, s, t),
   2.205 +  check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol),
   2.206          "The flow is not feasible.");
   2.207  
   2.208    CutMap min_cut2(g);
   2.209    max_flow.minCutMap(min_cut2);
   2.210    min_cut_value = cutValue(g, min_cut2, cap);
   2.211  
   2.212 -  check(max_flow.flowValue() == min_cut_value &&
   2.213 -        min_cut_value == 2 * flow_value,
   2.214 -        "The max flow value or the min cut value was not doubled");
   2.215 -
   2.216 +  check(!tol.different(17 * expected, max_flow.flowValue()),
   2.217 +        "Incorrect max flow value.");
   2.218 +  check(!tol.different(17 * expected, min_cut_value),
   2.219 +        "Incorrect min cut value.");
   2.220  
   2.221    max_flow.flowMap(flow);
   2.222  
   2.223 @@ -324,9 +358,9 @@
   2.224  
   2.225    CutMap min_cut3(g);
   2.226    max_flow.minCutMap(min_cut3);
   2.227 -  min_cut_value=cutValue(g, min_cut3, cap);
   2.228 +  min_cut_value = cutValue(g, min_cut3, cap);
   2.229  
   2.230 -  check(max_flow.flowValue() == min_cut_value,
   2.231 +  check(!tol.different(max_flow.flowValue(), min_cut_value),
   2.232          "The max flow value or the min cut value is wrong.");
   2.233  }
   2.234  
   2.235 @@ -379,17 +413,28 @@
   2.236    // Check Preflow
   2.237    typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<int> > PType1;
   2.238    typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2;
   2.239 -  checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >();
   2.240 -  checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >();
   2.241 -  initFlowTest();
   2.242 +  typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<double> > PType3;
   2.243 +
   2.244 +  checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >(test_lgf, 13);
   2.245 +  checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf, 13);
   2.246 +  checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf, 13);
   2.247 +
   2.248 +  checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf_float, 0.3);
   2.249 +  checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf_float, 0.3);
   2.250 +
   2.251 +  checkInitPreflow();
   2.252  
   2.253    // Check EdmondsKarp
   2.254    typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<int> > EKType1;
   2.255    typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2;
   2.256 -  checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >();
   2.257 -  checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >();
   2.258 +  typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<double> > EKType3;
   2.259  
   2.260 -  initFlowTest();
   2.261 +  checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >(test_lgf, 13);
   2.262 +  checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf, 13);
   2.263 +  checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf, 13);
   2.264 +
   2.265 +  checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf_float, 0.3);
   2.266 +  checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf_float, 0.3);
   2.267  
   2.268    return 0;
   2.269  }