test/max_flow_test.cc
changeset 1169 8db773f19586
parent 1168 259e3a90ad97
child 1178 61fdd06833a6
     1.1 --- a/test/max_flow_test.cc	Thu Mar 22 18:56:26 2018 +0100
     1.2 +++ b/test/max_flow_test.cc	Thu Mar 22 18:56:47 2018 +0100
     1.3 @@ -66,6 +66,38 @@
     1.4    "source 1\n"
     1.5    "target 8\n";
     1.6  
     1.7 +char test_lgf_float[] =
     1.8 +  "@nodes\n"
     1.9 +  "label\n"
    1.10 +  "0\n"
    1.11 +  "1\n"
    1.12 +  "2\n"
    1.13 +  "3\n"
    1.14 +  "4\n"
    1.15 +  "5\n"
    1.16 +  "6\n"
    1.17 +  "7\n"
    1.18 +  "8\n"
    1.19 +  "9\n"
    1.20 +  "@arcs\n"
    1.21 +  "      capacity\n"
    1.22 +  "0 1 0.1\n"
    1.23 +  "0 2 0.1\n"
    1.24 +  "0 3 0.1\n"
    1.25 +  "1 4 0.1\n"
    1.26 +  "2 4 0.1\n"
    1.27 +  "3 4 0.1\n"
    1.28 +  "4 5 0.3\n"
    1.29 +  "5 6 0.1\n"
    1.30 +  "5 7 0.1\n"
    1.31 +  "5 8 0.1\n"
    1.32 +  "6 9 0.1\n"
    1.33 +  "7 9 0.1\n"
    1.34 +  "8 9 0.1\n"
    1.35 +  "@attributes\n"
    1.36 +  "source 0\n"
    1.37 +  "target 9\n";
    1.38 +
    1.39  // Checks the general interface of a max flow algorithm
    1.40  template <typename GR, typename CAP>
    1.41  struct MaxFlowClassConcept
    1.42 @@ -258,10 +290,10 @@
    1.43    Node s, t;
    1.44    CapMap cap(g);
    1.45    std::istringstream input(input_lgf);
    1.46 -  DigraphReader<Digraph>(g,input)
    1.47 +  DigraphReader<Digraph>(g, input)
    1.48        .arcMap("capacity", cap)
    1.49 -      .node("source",s)
    1.50 -      .node("target",t)
    1.51 +      .node("source", s)
    1.52 +      .node("target", t)
    1.53        .run();
    1.54  
    1.55    MF max_flow(g, cap, s, t);
    1.56 @@ -280,8 +312,8 @@
    1.57          "Incorrect min cut value.");
    1.58  
    1.59    FlowMap flow(g);
    1.60 -  for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e];
    1.61 -  for (ArcIt e(g); e != INVALID; ++e) cap[e] = 2 * cap[e];
    1.62 +  for (ArcIt e(g); e != INVALID; ++e) flow[e] = 13 * max_flow.flowMap()[e];
    1.63 +  for (ArcIt e(g); e != INVALID; ++e) cap[e] = 17 * cap[e];
    1.64    max_flow.init(flow);
    1.65  
    1.66    SF::startFirstPhase(max_flow);       // start first phase of the algorithm
    1.67 @@ -290,9 +322,9 @@
    1.68    max_flow.minCutMap(min_cut1);
    1.69    min_cut_value = cutValue(g, min_cut1, cap);
    1.70  
    1.71 -  check(!tol.different(2 * expected, max_flow.flowValue()),
    1.72 +  check(!tol.different(17 * expected, max_flow.flowValue()),
    1.73          "Incorrect max flow value.");
    1.74 -  check(!tol.different(2 * expected, min_cut_value),
    1.75 +  check(!tol.different(17 * expected, min_cut_value),
    1.76          "Incorrect min cut value.");
    1.77  
    1.78    SF::startSecondPhase(max_flow);       // start second phase of the algorithm
    1.79 @@ -304,9 +336,9 @@
    1.80    max_flow.minCutMap(min_cut2);
    1.81    min_cut_value = cutValue(g, min_cut2, cap);
    1.82  
    1.83 -  check(!tol.different(2 * expected, max_flow.flowValue()),
    1.84 +  check(!tol.different(17 * expected, max_flow.flowValue()),
    1.85          "Incorrect max flow value.");
    1.86 -  check(!tol.different(2 * expected, min_cut_value),
    1.87 +  check(!tol.different(17 * expected, min_cut_value),
    1.88          "Incorrect min cut value.");
    1.89  
    1.90    max_flow.flowMap(flow);
    1.91 @@ -382,19 +414,27 @@
    1.92    typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<int> > PType1;
    1.93    typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2;
    1.94    typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<double> > PType3;
    1.95 +
    1.96    checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >(test_lgf, 13);
    1.97    checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf, 13);
    1.98    checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf, 13);
    1.99  
   1.100 +  checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf_float, 0.3);
   1.101 +  checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf_float, 0.3);
   1.102 +
   1.103    checkInitPreflow();
   1.104  
   1.105    // Check EdmondsKarp
   1.106    typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<int> > EKType1;
   1.107    typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2;
   1.108    typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<double> > EKType3;
   1.109 +
   1.110    checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >(test_lgf, 13);
   1.111    checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf, 13);
   1.112    checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf, 13);
   1.113  
   1.114 +  checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf_float, 0.3);
   1.115 +  checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf_float, 0.3);
   1.116 +
   1.117    return 0;
   1.118  }