test/max_flow_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Sun, 11 Aug 2013 21:56:21 +0200
changeset 1098 cf6084618b1b
parent 1087 dd1443e4a34c
child 1165 e0ccc1f0268f
permissions -rw-r--r--
Merge headmerge to the default branch
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2013
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #include <iostream>
    20 
    21 #include "test_tools.h"
    22 #include <lemon/smart_graph.h>
    23 #include <lemon/preflow.h>
    24 #include <lemon/edmonds_karp.h>
    25 #include <lemon/concepts/digraph.h>
    26 #include <lemon/concepts/maps.h>
    27 #include <lemon/lgf_reader.h>
    28 #include <lemon/elevator.h>
    29 
    30 using namespace lemon;
    31 
    32 char test_lgf[] =
    33   "@nodes\n"
    34   "label\n"
    35   "0\n"
    36   "1\n"
    37   "2\n"
    38   "3\n"
    39   "4\n"
    40   "5\n"
    41   "6\n"
    42   "7\n"
    43   "8\n"
    44   "9\n"
    45   "@arcs\n"
    46   "    label capacity\n"
    47   "0 1 0     20\n"
    48   "0 2 1     0\n"
    49   "1 1 2     3\n"
    50   "1 2 3     8\n"
    51   "1 3 4     8\n"
    52   "2 5 5     5\n"
    53   "3 2 6     5\n"
    54   "3 5 7     5\n"
    55   "3 6 8     5\n"
    56   "4 3 9     3\n"
    57   "5 7 10    3\n"
    58   "5 6 11    10\n"
    59   "5 8 12    10\n"
    60   "6 8 13    8\n"
    61   "8 9 14    20\n"
    62   "8 1 15    5\n"
    63   "9 5 16    5\n"
    64   "@attributes\n"
    65   "source 1\n"
    66   "target 8\n";
    67 
    68 
    69 // Checks the general interface of a max flow algorithm
    70 template <typename GR, typename CAP>
    71 struct MaxFlowClassConcept
    72 {
    73 
    74   template <typename MF>
    75   struct Constraints {
    76 
    77     typedef typename GR::Node Node;
    78     typedef typename GR::Arc Arc;
    79     typedef typename CAP::Value Value;
    80     typedef concepts::ReadWriteMap<Arc, Value> FlowMap;
    81     typedef concepts::WriteMap<Node, bool> CutMap;
    82 
    83     GR g;
    84     Node n;
    85     Arc e;
    86     CAP cap;
    87     FlowMap flow;
    88     CutMap cut;
    89     Value v;
    90     bool b;
    91 
    92     void constraints() {
    93       checkConcept<concepts::Digraph, GR>();
    94 
    95       const Constraints& me = *this;
    96 
    97       typedef typename MF
    98           ::template SetFlowMap<FlowMap>
    99           ::Create MaxFlowType;
   100       typedef typename MF::Create MaxFlowType2;
   101       MaxFlowType max_flow(me.g, me.cap, me.n, me.n);
   102       const MaxFlowType& const_max_flow = max_flow;
   103 
   104       max_flow
   105           .capacityMap(cap)
   106           .flowMap(flow)
   107           .source(n)
   108           .target(n);
   109 
   110       typename MaxFlowType::Tolerance tol = const_max_flow.tolerance();
   111       max_flow.tolerance(tol);
   112 
   113       max_flow.init();
   114       max_flow.init(cap);
   115       max_flow.run();
   116 
   117       v = const_max_flow.flowValue();
   118       v = const_max_flow.flow(e);
   119       const FlowMap& fm = const_max_flow.flowMap();
   120 
   121       b = const_max_flow.minCut(n);
   122       const_max_flow.minCutMap(cut);
   123 
   124       ::lemon::ignore_unused_variable_warning(fm);
   125     }
   126 
   127   };
   128 
   129 };
   130 
   131 // Checks the specific parts of Preflow's interface
   132 void checkPreflowCompile()
   133 {
   134   typedef int Value;
   135   typedef concepts::Digraph Digraph;
   136   typedef concepts::ReadMap<Digraph::Arc, Value> CapMap;
   137   typedef Elevator<Digraph, Digraph::Node> Elev;
   138   typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
   139 
   140   Digraph g;
   141   Digraph::Node n;
   142   CapMap cap;
   143 
   144   typedef Preflow<Digraph, CapMap>
   145       ::SetElevator<Elev>
   146       ::SetStandardElevator<LinkedElev>
   147       ::Create PreflowType;
   148   PreflowType preflow_test(g, cap, n, n);
   149   const PreflowType& const_preflow_test = preflow_test;
   150 
   151   const PreflowType::Elevator& elev = const_preflow_test.elevator();
   152   preflow_test.elevator(const_cast<PreflowType::Elevator&>(elev));
   153 
   154   bool b = preflow_test.init(cap);
   155   preflow_test.startFirstPhase();
   156   preflow_test.startSecondPhase();
   157   preflow_test.runMinCut();
   158 
   159   ::lemon::ignore_unused_variable_warning(b);
   160 }
   161 
   162 // Checks the specific parts of EdmondsKarp's interface
   163 void checkEdmondsKarpCompile()
   164 {
   165   typedef int Value;
   166   typedef concepts::Digraph Digraph;
   167   typedef concepts::ReadMap<Digraph::Arc, Value> CapMap;
   168   typedef Elevator<Digraph, Digraph::Node> Elev;
   169   typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
   170 
   171   Digraph g;
   172   Digraph::Node n;
   173   CapMap cap;
   174 
   175   EdmondsKarp<Digraph, CapMap> ek_test(g, cap, n, n);
   176 
   177   ek_test.init(cap);
   178   bool b = ek_test.checkedInit(cap);
   179   b = ek_test.augment();
   180   ek_test.start();
   181 
   182   ::lemon::ignore_unused_variable_warning(b);
   183 }
   184 
   185 
   186 template <typename T>
   187 T cutValue (const SmartDigraph& g,
   188               const SmartDigraph::NodeMap<bool>& cut,
   189               const SmartDigraph::ArcMap<T>& cap) {
   190 
   191   T c=0;
   192   for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) {
   193     if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e];
   194   }
   195   return c;
   196 }
   197 
   198 template <typename T>
   199 bool checkFlow(const SmartDigraph& g,
   200                const SmartDigraph::ArcMap<T>& flow,
   201                const SmartDigraph::ArcMap<T>& cap,
   202                SmartDigraph::Node s, SmartDigraph::Node t) {
   203 
   204   for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
   205     if (flow[e] < 0 || flow[e] > cap[e]) return false;
   206   }
   207 
   208   for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) {
   209     if (n == s || n == t) continue;
   210     T sum = 0;
   211     for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) {
   212       sum += flow[e];
   213     }
   214     for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) {
   215       sum -= flow[e];
   216     }
   217     if (sum != 0) return false;
   218   }
   219   return true;
   220 }
   221 
   222 void initFlowTest()
   223 {
   224   DIGRAPH_TYPEDEFS(SmartDigraph);
   225 
   226   SmartDigraph g;
   227   SmartDigraph::ArcMap<int> cap(g),iflow(g);
   228   Node s=g.addNode(); Node t=g.addNode();
   229   Node n1=g.addNode(); Node n2=g.addNode();
   230   Arc a;
   231   a=g.addArc(s,n1); cap[a]=20; iflow[a]=20;
   232   a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0;
   233   a=g.addArc(n2,t); cap[a]=20; iflow[a]=0;
   234 
   235   Preflow<SmartDigraph> pre(g,cap,s,t);
   236   pre.init(iflow);
   237   pre.startFirstPhase();
   238   check(pre.flowValue() == 10, "The incorrect max flow value.");
   239   check(pre.minCut(s), "Wrong min cut (Node s).");
   240   check(pre.minCut(n1), "Wrong min cut (Node n1).");
   241   check(!pre.minCut(n2), "Wrong min cut (Node n2).");
   242   check(!pre.minCut(t), "Wrong min cut (Node t).");
   243 }
   244 
   245 template <typename MF, typename SF>
   246 void checkMaxFlowAlg() {
   247   typedef SmartDigraph Digraph;
   248   DIGRAPH_TYPEDEFS(Digraph);
   249 
   250   typedef typename MF::Value Value;
   251   typedef Digraph::ArcMap<Value> CapMap;
   252   typedef CapMap FlowMap;
   253   typedef BoolNodeMap CutMap;
   254 
   255   Digraph g;
   256   Node s, t;
   257   CapMap cap(g);
   258   std::istringstream input(test_lgf);
   259   DigraphReader<Digraph>(g,input)
   260       .arcMap("capacity", cap)
   261       .node("source",s)
   262       .node("target",t)
   263       .run();
   264 
   265   MF max_flow(g, cap, s, t);
   266   max_flow.run();
   267 
   268   check(checkFlow(g, max_flow.flowMap(), cap, s, t),
   269         "The flow is not feasible.");
   270 
   271   CutMap min_cut(g);
   272   max_flow.minCutMap(min_cut);
   273   Value min_cut_value = cutValue(g, min_cut, cap);
   274 
   275   check(max_flow.flowValue() == min_cut_value,
   276         "The max flow value is not equal to the min cut value.");
   277 
   278   FlowMap flow(g);
   279   for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e];
   280 
   281   Value flow_value = max_flow.flowValue();
   282 
   283   for (ArcIt e(g); e != INVALID; ++e) cap[e] = 2 * cap[e];
   284   max_flow.init(flow);
   285 
   286   SF::startFirstPhase(max_flow);       // start first phase of the algorithm
   287 
   288   CutMap min_cut1(g);
   289   max_flow.minCutMap(min_cut1);
   290   min_cut_value = cutValue(g, min_cut1, cap);
   291 
   292   check(max_flow.flowValue() == min_cut_value &&
   293         min_cut_value == 2 * flow_value,
   294         "The max flow value or the min cut value is wrong.");
   295 
   296   SF::startSecondPhase(max_flow);       // start second phase of the algorithm
   297 
   298   check(checkFlow(g, max_flow.flowMap(), cap, s, t),
   299         "The flow is not feasible.");
   300 
   301   CutMap min_cut2(g);
   302   max_flow.minCutMap(min_cut2);
   303   min_cut_value = cutValue(g, min_cut2, cap);
   304 
   305   check(max_flow.flowValue() == min_cut_value &&
   306         min_cut_value == 2 * flow_value,
   307         "The max flow value or the min cut value was not doubled");
   308 
   309 
   310   max_flow.flowMap(flow);
   311 
   312   NodeIt tmp1(g, s);
   313   ++tmp1;
   314   if (tmp1 != INVALID) s = tmp1;
   315 
   316   NodeIt tmp2(g, t);
   317   ++tmp2;
   318   if (tmp2 != INVALID) t = tmp2;
   319 
   320   max_flow.source(s);
   321   max_flow.target(t);
   322 
   323   max_flow.run();
   324 
   325   CutMap min_cut3(g);
   326   max_flow.minCutMap(min_cut3);
   327   min_cut_value=cutValue(g, min_cut3, cap);
   328 
   329   check(max_flow.flowValue() == min_cut_value,
   330         "The max flow value or the min cut value is wrong.");
   331 }
   332 
   333 // Struct for calling start functions of a general max flow algorithm
   334 template <typename MF>
   335 struct GeneralStartFunctions {
   336 
   337   static void startFirstPhase(MF& mf) {
   338     mf.start();
   339   }
   340 
   341   static void startSecondPhase(MF& mf) {
   342     ::lemon::ignore_unused_variable_warning(mf);
   343   }
   344 
   345 };
   346 
   347 // Struct for calling start functions of Preflow
   348 template <typename MF>
   349 struct PreflowStartFunctions {
   350 
   351   static void startFirstPhase(MF& mf) {
   352     mf.startFirstPhase();
   353   }
   354 
   355   static void startSecondPhase(MF& mf) {
   356     mf.startSecondPhase();
   357   }
   358 
   359 };
   360 
   361 int main() {
   362 
   363   typedef concepts::Digraph GR;
   364   typedef concepts::ReadMap<GR::Arc, int> CM1;
   365   typedef concepts::ReadMap<GR::Arc, double> CM2;
   366 
   367   // Check the interface of Preflow
   368   checkConcept< MaxFlowClassConcept<GR, CM1>,
   369                 Preflow<GR, CM1> >();
   370   checkConcept< MaxFlowClassConcept<GR, CM2>,
   371                 Preflow<GR, CM2> >();
   372 
   373   // Check the interface of EdmondsKarp
   374   checkConcept< MaxFlowClassConcept<GR, CM1>,
   375                 EdmondsKarp<GR, CM1> >();
   376   checkConcept< MaxFlowClassConcept<GR, CM2>,
   377                 EdmondsKarp<GR, CM2> >();
   378 
   379   // Check Preflow
   380   typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<int> > PType1;
   381   typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2;
   382   checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >();
   383   checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >();
   384   initFlowTest();
   385 
   386   // Check EdmondsKarp
   387   typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<int> > EKType1;
   388   typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2;
   389   checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >();
   390   checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >();
   391 
   392   initFlowTest();
   393 
   394   return 0;
   395 }