lemon-1.3: test/max_flow_test.cc@2126945deb6a

     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  */

    19 #include <iostream>

    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>

    30 using namespace lemon;

    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";

    69 // Checks the general interface of a max flow algorithm

    70 template <typename GR, typename CAP>

    71 struct MaxFlowClassConcept

    72 {

    74   template <typename MF>

    75   struct Constraints {

    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;

    83     GR g;

    84     Node n;

    85     Arc e;

    86     CAP cap;

    87     FlowMap flow;

    88     CutMap cut;

    89     Value v;

    90     bool b;

    92     void constraints() {

    93       checkConcept<concepts::Digraph, GR>();

    95       const Constraints& me = *this;

    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;

   104       max_flow

   105           .capacityMap(cap)

   106           .flowMap(flow)

   107           .source(n)

   108           .target(n);

   110       typename MaxFlowType::Tolerance tol = const_max_flow.tolerance();

   111       max_flow.tolerance(tol);

   113       max_flow.init();

   114       max_flow.init(cap);

   115       max_flow.run();

   117       v = const_max_flow.flowValue();

   118       v = const_max_flow.flow(e);

   119       const FlowMap& fm = const_max_flow.flowMap();

   121       b = const_max_flow.minCut(n);

   122       const_max_flow.minCutMap(cut);

   124       ::lemon::ignore_unused_variable_warning(fm);

   125     }

   127   };

   129 };

   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;

   140   Digraph g;

   141   Digraph::Node n;

   142   CapMap cap;

   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;

   151   const PreflowType::Elevator& elev = const_preflow_test.elevator();

   152   preflow_test.elevator(const_cast<PreflowType::Elevator&>(elev));

   154   bool b = preflow_test.init(cap);

   155   preflow_test.startFirstPhase();

   156   preflow_test.startSecondPhase();

   157   preflow_test.runMinCut();

   159   ::lemon::ignore_unused_variable_warning(b);

   160 }

   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;

   171   Digraph g;

   172   Digraph::Node n;

   173   CapMap cap;

   175   EdmondsKarp<Digraph, CapMap> ek_test(g, cap, n, n);

   177   ek_test.init(cap);

   178   bool b = ek_test.checkedInit(cap);

   179   b = ek_test.augment();

   180   ek_test.start();

   182   ::lemon::ignore_unused_variable_warning(b);

   183 }

   186 template <typename T>

   187 T cutValue (const SmartDigraph& g,

   188               const SmartDigraph::NodeMap<bool>& cut,

   189               const SmartDigraph::ArcMap<T>& cap) {

   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 }

   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) {

   204   for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {

   205     if (flow[e] < 0 || flow[e] > cap[e]) return false;

   206   }

   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 }

   222 void initFlowTest()

   223 {

   224   DIGRAPH_TYPEDEFS(SmartDigraph);

   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;

   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 }

   245 template <typename MF, typename SF>

   246 void checkMaxFlowAlg() {

   247   typedef SmartDigraph Digraph;

   248   DIGRAPH_TYPEDEFS(Digraph);

   250   typedef typename MF::Value Value;

   251   typedef Digraph::ArcMap<Value> CapMap;

   252   typedef CapMap FlowMap;

   253   typedef BoolNodeMap CutMap;

   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();

   265   MF max_flow(g, cap, s, t);

   266   max_flow.run();

   268   check(checkFlow(g, max_flow.flowMap(), cap, s, t),

   269         "The flow is not feasible.");

   271   CutMap min_cut(g);

   272   max_flow.minCutMap(min_cut);

   273   Value min_cut_value = cutValue(g, min_cut, cap);

   275   check(max_flow.flowValue() == min_cut_value,

   276         "The max flow value is not equal to the min cut value.");

   278   FlowMap flow(g);

   279   for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e];

   281   Value flow_value = max_flow.flowValue();

   283   for (ArcIt e(g); e != INVALID; ++e) cap[e] = 2 * cap[e];

   284   max_flow.init(flow);

   286   SF::startFirstPhase(max_flow);       // start first phase of the algorithm

   288   CutMap min_cut1(g);

   289   max_flow.minCutMap(min_cut1);

   290   min_cut_value = cutValue(g, min_cut1, cap);

   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.");

   296   SF::startSecondPhase(max_flow);       // start second phase of the algorithm

   298   check(checkFlow(g, max_flow.flowMap(), cap, s, t),

   299         "The flow is not feasible.");

   301   CutMap min_cut2(g);

   302   max_flow.minCutMap(min_cut2);

   303   min_cut_value = cutValue(g, min_cut2, cap);

   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");

   310   max_flow.flowMap(flow);

   312   NodeIt tmp1(g, s);

   313   ++tmp1;

   314   if (tmp1 != INVALID) s = tmp1;

   316   NodeIt tmp2(g, t);

   317   ++tmp2;

   318   if (tmp2 != INVALID) t = tmp2;

   320   max_flow.source(s);

   321   max_flow.target(t);

   323   max_flow.run();

   325   CutMap min_cut3(g);

   326   max_flow.minCutMap(min_cut3);

   327   min_cut_value=cutValue(g, min_cut3, cap);

   329   check(max_flow.flowValue() == min_cut_value,

   330         "The max flow value or the min cut value is wrong.");

   331 }

   333 // Struct for calling start functions of a general max flow algorithm

   334 template <typename MF>

   335 struct GeneralStartFunctions {

   337   static void startFirstPhase(MF& mf) {

   338     mf.start();

   339   }

   341   static void startSecondPhase(MF& mf) {

   342     ::lemon::ignore_unused_variable_warning(mf);

   343   }

   345 };

   347 // Struct for calling start functions of Preflow

   348 template <typename MF>

   349 struct PreflowStartFunctions {

   351   static void startFirstPhase(MF& mf) {

   352     mf.startFirstPhase();

   353   }

   355   static void startSecondPhase(MF& mf) {

   356     mf.startSecondPhase();

   357   }

   359 };

   361 int main() {

   363   typedef concepts::Digraph GR;

   364   typedef concepts::ReadMap<GR::Arc, int> CM1;

   365   typedef concepts::ReadMap<GR::Arc, double> CM2;

   367   // Check the interface of Preflow

   368   checkConcept< MaxFlowClassConcept<GR, CM1>,

   369                 Preflow<GR, CM1> >();

   370   checkConcept< MaxFlowClassConcept<GR, CM2>,

   371                 Preflow<GR, CM2> >();

   373   // Check the interface of EdmondsKarp

   374   checkConcept< MaxFlowClassConcept<GR, CM1>,

   375                 EdmondsKarp<GR, CM1> >();

   376   checkConcept< MaxFlowClassConcept<GR, CM2>,

   377                 EdmondsKarp<GR, CM2> >();

   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();

   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> >();

   392   initFlowTest();

   394   return 0;

   395 }

author	Alpar Juttner <alpar@cs.elte.hu>
	Fri, 22 May 2015 17:47:18 +0200
changeset 1152	2126945deb6a
parent 1087	dd1443e4a34c
child 1159	e0ccc1f0268f
permissions	-rw-r--r--