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 1394 2e0c2c25d63e
parent 1384 259e3a90ad97
child 1396 61fdd06833a6
equal deleted inserted replaced
7:b99740d69768 8:c7beeff6dbfb 
    64   "9 5 16    5\n"
 
    64   "9 5 16    5\n"
 
    65   "@attributes\n"
 
    65   "@attributes\n"
 
    66   "source 1\n"
 
    66   "source 1\n"
 
    67   "target 8\n";
 
    67   "target 8\n";
 
    68 
    68 
       
    69 char test_lgf_float[] =
 
       
    70   "@nodes\n"
 
       
    71   "label\n"
 
       
    72   "0\n"
 
       
    73   "1\n"
 
       
    74   "2\n"
 
       
    75   "3\n"
 
       
    76   "4\n"
 
       
    77   "5\n"
 
       
    78   "6\n"
 
       
    79   "7\n"
 
       
    80   "8\n"
 
       
    81   "9\n"
 
       
    82   "@arcs\n"
 
       
    83   "      capacity\n"
 
       
    84   "0 1 0.1\n"
 
       
    85   "0 2 0.1\n"
 
       
    86   "0 3 0.1\n"
 
       
    87   "1 4 0.1\n"
 
       
    88   "2 4 0.1\n"
 
       
    89   "3 4 0.1\n"
 
       
    90   "4 5 0.3\n"
 
       
    91   "5 6 0.1\n"
 
       
    92   "5 7 0.1\n"
 
       
    93   "5 8 0.1\n"
 
       
    94   "6 9 0.1\n"
 
       
    95   "7 9 0.1\n"
 
       
    96   "8 9 0.1\n"
 
       
    97   "@attributes\n"
 
       
    98   "source 0\n"
 
       
    99   "target 9\n";
 
       
   100 
    69 // Checks the general interface of a max flow algorithm
 
   101 // Checks the general interface of a max flow algorithm
 
    70 template <typename GR, typename CAP>
 
   102 template <typename GR, typename CAP>
 
    71 struct MaxFlowClassConcept
 
   103 struct MaxFlowClassConcept
 
    72 {
 
   104 {
 
    73 
   105 
   256 
   288 
   257   Digraph g;
 
   289   Digraph g;
 
   258   Node s, t;
 
   290   Node s, t;
 
   259   CapMap cap(g);
 
   291   CapMap cap(g);
 
   260   std::istringstream input(input_lgf);
 
   292   std::istringstream input(input_lgf);
 
   261   DigraphReader<Digraph>(g,input)
 
   293   DigraphReader<Digraph>(g, input)
 
   262       .arcMap("capacity", cap)
 
   294       .arcMap("capacity", cap)
 
   263       .node("source",s)
 
   295       .node("source", s)
 
   264       .node("target",t)
 
   296       .node("target", t)
 
   265       .run();
 
   297       .run();
 
   266 
   298 
   267   MF max_flow(g, cap, s, t);
 
   299   MF max_flow(g, cap, s, t);
 
   268   max_flow.run();
 
   300   max_flow.run();
 
   269 
   301 
   278 
   310 
   279   check(!tol.different(expected, min_cut_value),
 
   311   check(!tol.different(expected, min_cut_value),
 
   280         "Incorrect min cut value.");
 
   312         "Incorrect min cut value.");
 
   281 
   313 
   282   FlowMap flow(g);
 
   314   FlowMap flow(g);
 
   283   for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e];
 
   315   for (ArcIt e(g); e != INVALID; ++e) flow[e] = 13 * max_flow.flowMap()[e];
 
   284   for (ArcIt e(g); e != INVALID; ++e) cap[e] = 2 * cap[e];
 
   316   for (ArcIt e(g); e != INVALID; ++e) cap[e] = 17 * cap[e];
 
   285   max_flow.init(flow);
 
   317   max_flow.init(flow);
 
   286 
   318 
   287   SF::startFirstPhase(max_flow);       // start first phase of the algorithm
 
   319   SF::startFirstPhase(max_flow);       // start first phase of the algorithm
 
   288 
   320 
   289   CutMap min_cut1(g);
 
   321   CutMap min_cut1(g);
 
   290   max_flow.minCutMap(min_cut1);
 
   322   max_flow.minCutMap(min_cut1);
 
   291   min_cut_value = cutValue(g, min_cut1, cap);
 
   323   min_cut_value = cutValue(g, min_cut1, cap);
 
   292 
   324 
   293   check(!tol.different(2 * expected, max_flow.flowValue()),
 
   325   check(!tol.different(17 * expected, max_flow.flowValue()),
 
   294         "Incorrect max flow value.");
 
   326         "Incorrect max flow value.");
 
   295   check(!tol.different(2 * expected, min_cut_value),
 
   327   check(!tol.different(17 * expected, min_cut_value),
 
   296         "Incorrect min cut value.");
 
   328         "Incorrect min cut value.");
 
   297 
   329 
   298   SF::startSecondPhase(max_flow);       // start second phase of the algorithm
 
   330   SF::startSecondPhase(max_flow);       // start second phase of the algorithm
 
   299 
   331 
   300   check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol),
 
   332   check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol),
 
   302 
   334 
   303   CutMap min_cut2(g);
 
   335   CutMap min_cut2(g);
 
   304   max_flow.minCutMap(min_cut2);
 
   336   max_flow.minCutMap(min_cut2);
 
   305   min_cut_value = cutValue(g, min_cut2, cap);
 
   337   min_cut_value = cutValue(g, min_cut2, cap);
 
   306 
   338 
   307   check(!tol.different(2 * expected, max_flow.flowValue()),
 
   339   check(!tol.different(17 * expected, max_flow.flowValue()),
 
   308         "Incorrect max flow value.");
 
   340         "Incorrect max flow value.");
 
   309   check(!tol.different(2 * expected, min_cut_value),
 
   341   check(!tol.different(17 * expected, min_cut_value),
 
   310         "Incorrect min cut value.");
 
   342         "Incorrect min cut value.");
 
   311 
   343 
   312   max_flow.flowMap(flow);
 
   344   max_flow.flowMap(flow);
 
   313 
   345 
   314   NodeIt tmp1(g, s);
 
   346   NodeIt tmp1(g, s);
 
   380 
   412 
   381   // Check Preflow
 
   413   // Check Preflow
 
   382   typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<int> > PType1;
 
   414   typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<int> > PType1;
 
   383   typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2;
 
   415   typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2;
 
   384   typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<double> > PType3;
 
   416   typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<double> > PType3;
 
       
   417 
   385   checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >(test_lgf, 13);
 
   418   checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >(test_lgf, 13);
 
   386   checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf, 13);
 
   419   checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf, 13);
 
   387   checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf, 13);
 
   420   checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf, 13);
 
       
   421 
       
   422   checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf_float, 0.3);
 
       
   423   checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf_float, 0.3);
 
   388 
   424 
   389   checkInitPreflow();
 
   425   checkInitPreflow();
 
   390 
   426 
   391   // Check EdmondsKarp
 
   427   // Check EdmondsKarp
 
   392   typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<int> > EKType1;
 
   428   typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<int> > EKType1;
 
   393   typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2;
 
   429   typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2;
 
   394   typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<double> > EKType3;
 
   430   typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<double> > EKType3;
 
       
   431 
   395   checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >(test_lgf, 13);
 
   432   checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >(test_lgf, 13);
 
   396   checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf, 13);
 
   433   checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf, 13);
 
   397   checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf, 13);
 
   434   checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf, 13);
 
   398 
   435 
       
   436   checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf_float, 0.3);
 
       
   437   checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf_float, 0.3);
 
       
   438 
   399   return 0;
 
   439   return 0;
 
   400 }
 
   440 }
lemon