test/max_flow_test.cc
changeset 1167 e018899c2926
parent 1166 e2732b9da429
child 1168 259e3a90ad97
equal deleted inserted replaced
5:c646cfa1601e 6:76da304bdabd
    24 #include <lemon/edmonds_karp.h>
    24 #include <lemon/edmonds_karp.h>
    25 #include <lemon/concepts/digraph.h>
    25 #include <lemon/concepts/digraph.h>
    26 #include <lemon/concepts/maps.h>
    26 #include <lemon/concepts/maps.h>
    27 #include <lemon/lgf_reader.h>
    27 #include <lemon/lgf_reader.h>
    28 #include <lemon/elevator.h>
    28 #include <lemon/elevator.h>
       
    29 #include <lemon/tolerance.h>
    29 
    30 
    30 using namespace lemon;
    31 using namespace lemon;
    31 
    32 
    32 char test_lgf[] =
    33 char test_lgf[] =
    33   "@nodes\n"
    34   "@nodes\n"
    63   "9 5 16    5\n"
    64   "9 5 16    5\n"
    64   "@attributes\n"
    65   "@attributes\n"
    65   "source 1\n"
    66   "source 1\n"
    66   "target 8\n";
    67   "target 8\n";
    67 
    68 
    68 
       
    69 // Checks the general interface of a max flow algorithm
    69 // Checks the general interface of a max flow algorithm
    70 template <typename GR, typename CAP>
    70 template <typename GR, typename CAP>
    71 struct MaxFlowClassConcept
    71 struct MaxFlowClassConcept
    72 {
    72 {
    73 
    73 
   195 
   195 
   196 template <typename T>
   196 template <typename T>
   197 bool checkFlow(const SmartDigraph& g,
   197 bool checkFlow(const SmartDigraph& g,
   198                const SmartDigraph::ArcMap<T>& flow,
   198                const SmartDigraph::ArcMap<T>& flow,
   199                const SmartDigraph::ArcMap<T>& cap,
   199                const SmartDigraph::ArcMap<T>& cap,
   200                SmartDigraph::Node s, SmartDigraph::Node t) {
   200                SmartDigraph::Node s, SmartDigraph::Node t,
       
   201                const Tolerance<T>& tol) {
   201 
   202 
   202   for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
   203   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;
   204   }
   205   }
   205 
   206 
   206   for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) {
   207   for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) {
   207     if (n == s || n == t) continue;
   208     if (n == s || n == t) continue;
   208     T sum = 0;
   209     T sum = 0;
   210       sum += flow[e];
   211       sum += flow[e];
   211     }
   212     }
   212     for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) {
   213     for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) {
   213       sum -= flow[e];
   214       sum -= flow[e];
   214     }
   215     }
   215     if (sum != 0) return false;
   216     if (tol.nonZero(sum)) return false;
   216   }
   217   }
   217   return true;
   218   return true;
   218 }
   219 }
   219 
   220 
   220 void checkInitPreflow()
   221 void checkInitPreflow()
   248 
   249 
   249   typedef typename MF::Value Value;
   250   typedef typename MF::Value Value;
   250   typedef Digraph::ArcMap<Value> CapMap;
   251   typedef Digraph::ArcMap<Value> CapMap;
   251   typedef CapMap FlowMap;
   252   typedef CapMap FlowMap;
   252   typedef BoolNodeMap CutMap;
   253   typedef BoolNodeMap CutMap;
       
   254 
       
   255   Tolerance<Value> tol;
   253 
   256 
   254   Digraph g;
   257   Digraph g;
   255   Node s, t;
   258   Node s, t;
   256   CapMap cap(g);
   259   CapMap cap(g);
   257   std::istringstream input(test_lgf);
   260   std::istringstream input(test_lgf);
   262       .run();
   265       .run();
   263 
   266 
   264   MF max_flow(g, cap, s, t);
   267   MF max_flow(g, cap, s, t);
   265   max_flow.run();
   268   max_flow.run();
   266 
   269 
   267   check(checkFlow(g, max_flow.flowMap(), cap, s, t),
   270   check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol),
   268         "The flow is not feasible.");
   271         "The flow is not feasible.");
   269 
   272 
   270   CutMap min_cut(g);
   273   CutMap min_cut(g);
   271   max_flow.minCutMap(min_cut);
   274   max_flow.minCutMap(min_cut);
   272   Value min_cut_value = cutValue(g, min_cut, cap);
   275   Value min_cut_value = cutValue(g, min_cut, cap);
   273 
   276 
   274   check(max_flow.flowValue() == min_cut_value,
   277   check(!tol.different(max_flow.flowValue(), min_cut_value),
   275         "The max flow value is not equal to the min cut value.");
   278         "The max flow value is not equal to the min cut value.");
   276 
   279 
   277   FlowMap flow(g);
   280   FlowMap flow(g);
   278   for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e];
   281   for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e];
   279 
   282 
   286 
   289 
   287   CutMap min_cut1(g);
   290   CutMap min_cut1(g);
   288   max_flow.minCutMap(min_cut1);
   291   max_flow.minCutMap(min_cut1);
   289   min_cut_value = cutValue(g, min_cut1, cap);
   292   min_cut_value = cutValue(g, min_cut1, cap);
   290 
   293 
   291   check(max_flow.flowValue() == min_cut_value &&
   294   check(!tol.different(max_flow.flowValue(), min_cut_value) &&
   292         min_cut_value == 2 * flow_value,
   295         !tol.different(min_cut_value, 2 * flow_value),
   293         "The max flow value or the min cut value is wrong.");
   296         "The max flow value or the min cut value is wrong.");
   294 
   297 
   295   SF::startSecondPhase(max_flow);       // start second phase of the algorithm
   298   SF::startSecondPhase(max_flow);       // start second phase of the algorithm
   296 
   299 
   297   check(checkFlow(g, max_flow.flowMap(), cap, s, t),
   300   check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol),
   298         "The flow is not feasible.");
   301         "The flow is not feasible.");
   299 
   302 
   300   CutMap min_cut2(g);
   303   CutMap min_cut2(g);
   301   max_flow.minCutMap(min_cut2);
   304   max_flow.minCutMap(min_cut2);
   302   min_cut_value = cutValue(g, min_cut2, cap);
   305   min_cut_value = cutValue(g, min_cut2, cap);
   303 
   306 
   304   check(max_flow.flowValue() == min_cut_value &&
   307   check(!tol.different(max_flow.flowValue(), min_cut_value) &&
   305         min_cut_value == 2 * flow_value,
   308         !tol.different(min_cut_value, 2 * flow_value),
   306         "The max flow value or the min cut value was not doubled.");
   309         "The max flow value or the min cut value was not doubled.");
   307 
   310 
   308   max_flow.flowMap(flow);
   311   max_flow.flowMap(flow);
   309 
   312 
   310   NodeIt tmp1(g, s);
   313   NodeIt tmp1(g, s);
   322 
   325 
   323   CutMap min_cut3(g);
   326   CutMap min_cut3(g);
   324   max_flow.minCutMap(min_cut3);
   327   max_flow.minCutMap(min_cut3);
   325   min_cut_value = cutValue(g, min_cut3, cap);
   328   min_cut_value = cutValue(g, min_cut3, cap);
   326 
   329 
   327   check(max_flow.flowValue() == min_cut_value,
   330   check(!tol.different(max_flow.flowValue(), min_cut_value),
   328         "The max flow value or the min cut value is wrong.");
   331         "The max flow value or the min cut value is wrong.");
   329 }
   332 }
   330 
   333 
   331 // Struct for calling start functions of a general max flow algorithm
   334 // Struct for calling start functions of a general max flow algorithm
   332 template <typename MF>
   335 template <typename MF>