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