test/max_flow_test.cc
changeset 1168 259e3a90ad97
parent 1167 e018899c2926
child 1169 8db773f19586
equal deleted inserted replaced
6:76da304bdabd 7:b99740d69768
   241   check(!pre.minCut(n2), "Wrong min cut (Node n2).");
   241   check(!pre.minCut(n2), "Wrong min cut (Node n2).");
   242   check(!pre.minCut(t), "Wrong min cut (Node t).");
   242   check(!pre.minCut(t), "Wrong min cut (Node t).");
   243 }
   243 }
   244 
   244 
   245 template <typename MF, typename SF>
   245 template <typename MF, typename SF>
   246 void checkMaxFlowAlg() {
   246 void checkMaxFlowAlg(const char *input_lgf,  typename MF::Value expected) {
   247   typedef SmartDigraph Digraph;
   247   typedef SmartDigraph Digraph;
   248   DIGRAPH_TYPEDEFS(Digraph);
   248   DIGRAPH_TYPEDEFS(Digraph);
   249 
   249 
   250   typedef typename MF::Value Value;
   250   typedef typename MF::Value Value;
   251   typedef Digraph::ArcMap<Value> CapMap;
   251   typedef Digraph::ArcMap<Value> CapMap;
   255   Tolerance<Value> tol;
   255   Tolerance<Value> tol;
   256 
   256 
   257   Digraph g;
   257   Digraph g;
   258   Node s, t;
   258   Node s, t;
   259   CapMap cap(g);
   259   CapMap cap(g);
   260   std::istringstream input(test_lgf);
   260   std::istringstream input(input_lgf);
   261   DigraphReader<Digraph>(g,input)
   261   DigraphReader<Digraph>(g,input)
   262       .arcMap("capacity", cap)
   262       .arcMap("capacity", cap)
   263       .node("source",s)
   263       .node("source",s)
   264       .node("target",t)
   264       .node("target",t)
   265       .run();
   265       .run();
   266 
   266 
   267   MF max_flow(g, cap, s, t);
   267   MF max_flow(g, cap, s, t);
   268   max_flow.run();
   268   max_flow.run();
   269 
   269 
       
   270   check(!tol.different(expected, max_flow.flowValue()),
       
   271         "Incorrect max flow value.");
   270   check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol),
   272   check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol),
   271         "The flow is not feasible.");
   273         "The flow is not feasible.");
   272 
   274 
   273   CutMap min_cut(g);
   275   CutMap min_cut(g);
   274   max_flow.minCutMap(min_cut);
   276   max_flow.minCutMap(min_cut);
   275   Value min_cut_value = cutValue(g, min_cut, cap);
   277   Value min_cut_value = cutValue(g, min_cut, cap);
   276 
   278 
   277   check(!tol.different(max_flow.flowValue(), min_cut_value),
   279   check(!tol.different(expected, min_cut_value),
   278         "The max flow value is not equal to the min cut value.");
   280         "Incorrect min cut value.");
   279 
   281 
   280   FlowMap flow(g);
   282   FlowMap flow(g);
   281   for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e];
   283   for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e];
   282 
       
   283   Value flow_value = max_flow.flowValue();
       
   284 
       
   285   for (ArcIt e(g); e != INVALID; ++e) cap[e] = 2 * cap[e];
   284   for (ArcIt e(g); e != INVALID; ++e) cap[e] = 2 * cap[e];
   286   max_flow.init(flow);
   285   max_flow.init(flow);
   287 
   286 
   288   SF::startFirstPhase(max_flow);       // start first phase of the algorithm
   287   SF::startFirstPhase(max_flow);       // start first phase of the algorithm
   289 
   288 
   290   CutMap min_cut1(g);
   289   CutMap min_cut1(g);
   291   max_flow.minCutMap(min_cut1);
   290   max_flow.minCutMap(min_cut1);
   292   min_cut_value = cutValue(g, min_cut1, cap);
   291   min_cut_value = cutValue(g, min_cut1, cap);
   293 
   292 
   294   check(!tol.different(max_flow.flowValue(), min_cut_value) &&
   293   check(!tol.different(2 * expected, max_flow.flowValue()),
   295         !tol.different(min_cut_value, 2 * flow_value),
   294         "Incorrect max flow value.");
   296         "The max flow value or the min cut value is wrong.");
   295   check(!tol.different(2 * expected, min_cut_value),
       
   296         "Incorrect min cut value.");
   297 
   297 
   298   SF::startSecondPhase(max_flow);       // start second phase of the algorithm
   298   SF::startSecondPhase(max_flow);       // start second phase of the algorithm
   299 
   299 
   300   check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol),
   300   check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol),
   301         "The flow is not feasible.");
   301         "The flow is not feasible.");
   302 
   302 
   303   CutMap min_cut2(g);
   303   CutMap min_cut2(g);
   304   max_flow.minCutMap(min_cut2);
   304   max_flow.minCutMap(min_cut2);
   305   min_cut_value = cutValue(g, min_cut2, cap);
   305   min_cut_value = cutValue(g, min_cut2, cap);
   306 
   306 
   307   check(!tol.different(max_flow.flowValue(), min_cut_value) &&
   307   check(!tol.different(2 * expected, max_flow.flowValue()),
   308         !tol.different(min_cut_value, 2 * flow_value),
   308         "Incorrect max flow value.");
   309         "The max flow value or the min cut value was not doubled.");
   309   check(!tol.different(2 * expected, min_cut_value),
       
   310         "Incorrect min cut value.");
   310 
   311 
   311   max_flow.flowMap(flow);
   312   max_flow.flowMap(flow);
   312 
   313 
   313   NodeIt tmp1(g, s);
   314   NodeIt tmp1(g, s);
   314   ++tmp1;
   315   ++tmp1;
   378                 EdmondsKarp<GR, CM2> >();
   379                 EdmondsKarp<GR, CM2> >();
   379 
   380 
   380   // Check Preflow
   381   // Check Preflow
   381   typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<int> > PType1;
   382   typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<int> > PType1;
   382   typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2;
   383   typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2;
   383   checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >();
   384   typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<double> > PType3;
   384   checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >();
   385   checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >(test_lgf, 13);
       
   386   checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf, 13);
       
   387   checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf, 13);
   385 
   388 
   386   checkInitPreflow();
   389   checkInitPreflow();
   387 
   390 
   388   // Check EdmondsKarp
   391   // Check EdmondsKarp
   389   typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<int> > EKType1;
   392   typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<int> > EKType1;
   390   typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2;
   393   typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2;
   391   checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >();
   394   typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<double> > EKType3;
   392   checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >();
   395   checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >(test_lgf, 13);
       
   396   checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf, 13);
       
   397   checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf, 13);
   393 
   398 
   394   return 0;
   399   return 0;
   395 }
   400 }