COIN-OR::LEMON - Graph Library

Changeset 1383:e018899c2926 in lemon


Ignore:
Timestamp:
03/22/18 18:55:59 (7 months ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Use tolerance in max_flow_test.cc (#608)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • test/max_flow_test.cc

    r1382 r1383  
    2727#include <lemon/lgf_reader.h>
    2828#include <lemon/elevator.h>
     29#include <lemon/tolerance.h>
    2930
    3031using namespace lemon;
     
    6667  "target 8\n";
    6768
    68 
    6969// Checks the general interface of a max flow algorithm
    7070template <typename GR, typename CAP>
     
    198198               const SmartDigraph::ArcMap<T>& flow,
    199199               const SmartDigraph::ArcMap<T>& cap,
    200                SmartDigraph::Node s, SmartDigraph::Node t) {
     200               SmartDigraph::Node s, SmartDigraph::Node t,
     201               const Tolerance<T>& tol) {
    201202
    202203  for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
    203     if (flow[e] < 0 || flow[e] > cap[e]) return false;
     204    if (tol.negative(flow[e]) || tol.less(cap[e], flow[e])) return false;
    204205  }
    205206
     
    213214      sum -= flow[e];
    214215    }
    215     if (sum != 0) return false;
     216    if (tol.nonZero(sum)) return false;
    216217  }
    217218  return true;
     
    251252  typedef CapMap FlowMap;
    252253  typedef BoolNodeMap CutMap;
     254
     255  Tolerance<Value> tol;
    253256
    254257  Digraph g;
     
    265268  max_flow.run();
    266269
    267   check(checkFlow(g, max_flow.flowMap(), cap, s, t),
     270  check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol),
    268271        "The flow is not feasible.");
    269272
     
    272275  Value min_cut_value = cutValue(g, min_cut, cap);
    273276
    274   check(max_flow.flowValue() == min_cut_value,
     277  check(!tol.different(max_flow.flowValue(), min_cut_value),
    275278        "The max flow value is not equal to the min cut value.");
    276279
     
    289292  min_cut_value = cutValue(g, min_cut1, cap);
    290293
    291   check(max_flow.flowValue() == min_cut_value &&
    292         min_cut_value == 2 * flow_value,
     294  check(!tol.different(max_flow.flowValue(), min_cut_value) &&
     295        !tol.different(min_cut_value, 2 * flow_value),
    293296        "The max flow value or the min cut value is wrong.");
    294297
    295298  SF::startSecondPhase(max_flow);       // start second phase of the algorithm
    296299
    297   check(checkFlow(g, max_flow.flowMap(), cap, s, t),
     300  check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol),
    298301        "The flow is not feasible.");
    299302
     
    302305  min_cut_value = cutValue(g, min_cut2, cap);
    303306
    304   check(max_flow.flowValue() == min_cut_value &&
    305         min_cut_value == 2 * flow_value,
     307  check(!tol.different(max_flow.flowValue(), min_cut_value) &&
     308        !tol.different(min_cut_value, 2 * flow_value),
    306309        "The max flow value or the min cut value was not doubled.");
    307310
     
    325328  min_cut_value = cutValue(g, min_cut3, cap);
    326329
    327   check(max_flow.flowValue() == min_cut_value,
     330  check(!tol.different(max_flow.flowValue(), min_cut_value),
    328331        "The max flow value or the min cut value is wrong.");
    329332}
Note: See TracChangeset for help on using the changeset viewer.