Mercuriallemon / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
test/max_flow_test.cc
changeset 1383 e018899c2926
parent 1382 e2732b9da429
child 1384 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>
lemon