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