Improve max flow test method: set expected flow value (#608)
authorPeter Kovacs <kpeter@inf.elte.hu>
Thu, 22 Mar 2018 18:56:26 +0100
changeset 1168259e3a90ad97
parent 1167 e018899c2926
child 1169 8db773f19586
Improve max flow test method: set expected flow value (#608)
test/max_flow_test.cc
     1.1 --- a/test/max_flow_test.cc	Thu Mar 22 18:55:59 2018 +0100
     1.2 +++ b/test/max_flow_test.cc	Thu Mar 22 18:56:26 2018 +0100
     1.3 @@ -243,7 +243,7 @@
     1.4  }
     1.5  
     1.6  template <typename MF, typename SF>
     1.7 -void checkMaxFlowAlg() {
     1.8 +void checkMaxFlowAlg(const char *input_lgf,  typename MF::Value expected) {
     1.9    typedef SmartDigraph Digraph;
    1.10    DIGRAPH_TYPEDEFS(Digraph);
    1.11  
    1.12 @@ -257,7 +257,7 @@
    1.13    Digraph g;
    1.14    Node s, t;
    1.15    CapMap cap(g);
    1.16 -  std::istringstream input(test_lgf);
    1.17 +  std::istringstream input(input_lgf);
    1.18    DigraphReader<Digraph>(g,input)
    1.19        .arcMap("capacity", cap)
    1.20        .node("source",s)
    1.21 @@ -267,6 +267,8 @@
    1.22    MF max_flow(g, cap, s, t);
    1.23    max_flow.run();
    1.24  
    1.25 +  check(!tol.different(expected, max_flow.flowValue()),
    1.26 +        "Incorrect max flow value.");
    1.27    check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol),
    1.28          "The flow is not feasible.");
    1.29  
    1.30 @@ -274,14 +276,11 @@
    1.31    max_flow.minCutMap(min_cut);
    1.32    Value min_cut_value = cutValue(g, min_cut, cap);
    1.33  
    1.34 -  check(!tol.different(max_flow.flowValue(), min_cut_value),
    1.35 -        "The max flow value is not equal to the min cut value.");
    1.36 +  check(!tol.different(expected, min_cut_value),
    1.37 +        "Incorrect min cut value.");
    1.38  
    1.39    FlowMap flow(g);
    1.40    for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e];
    1.41 -
    1.42 -  Value flow_value = max_flow.flowValue();
    1.43 -
    1.44    for (ArcIt e(g); e != INVALID; ++e) cap[e] = 2 * cap[e];
    1.45    max_flow.init(flow);
    1.46  
    1.47 @@ -291,9 +290,10 @@
    1.48    max_flow.minCutMap(min_cut1);
    1.49    min_cut_value = cutValue(g, min_cut1, cap);
    1.50  
    1.51 -  check(!tol.different(max_flow.flowValue(), min_cut_value) &&
    1.52 -        !tol.different(min_cut_value, 2 * flow_value),
    1.53 -        "The max flow value or the min cut value is wrong.");
    1.54 +  check(!tol.different(2 * expected, max_flow.flowValue()),
    1.55 +        "Incorrect max flow value.");
    1.56 +  check(!tol.different(2 * expected, min_cut_value),
    1.57 +        "Incorrect min cut value.");
    1.58  
    1.59    SF::startSecondPhase(max_flow);       // start second phase of the algorithm
    1.60  
    1.61 @@ -304,9 +304,10 @@
    1.62    max_flow.minCutMap(min_cut2);
    1.63    min_cut_value = cutValue(g, min_cut2, cap);
    1.64  
    1.65 -  check(!tol.different(max_flow.flowValue(), min_cut_value) &&
    1.66 -        !tol.different(min_cut_value, 2 * flow_value),
    1.67 -        "The max flow value or the min cut value was not doubled.");
    1.68 +  check(!tol.different(2 * expected, max_flow.flowValue()),
    1.69 +        "Incorrect max flow value.");
    1.70 +  check(!tol.different(2 * expected, min_cut_value),
    1.71 +        "Incorrect min cut value.");
    1.72  
    1.73    max_flow.flowMap(flow);
    1.74  
    1.75 @@ -380,16 +381,20 @@
    1.76    // Check Preflow
    1.77    typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<int> > PType1;
    1.78    typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2;
    1.79 -  checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >();
    1.80 -  checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >();
    1.81 +  typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<double> > PType3;
    1.82 +  checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >(test_lgf, 13);
    1.83 +  checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf, 13);
    1.84 +  checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf, 13);
    1.85  
    1.86    checkInitPreflow();
    1.87  
    1.88    // Check EdmondsKarp
    1.89    typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<int> > EKType1;
    1.90    typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2;
    1.91 -  checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >();
    1.92 -  checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >();
    1.93 +  typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<double> > EKType3;
    1.94 +  checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >(test_lgf, 13);
    1.95 +  checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf, 13);
    1.96 +  checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf, 13);
    1.97  
    1.98    return 0;
    1.99  }