COIN-OR::LEMON - Graph Library

source: lemon/test/max_flow_test.cc @ 1381:e0ccc1f0268f

Last change on this file since 1381:e0ccc1f0268f was 1381:e0ccc1f0268f, checked in by Peter Kovacs <kpeter@…>, 2 years ago

Remove unused typedefs in max_flow_test.cc (#608)

File size: 9.6 KB
RevLine 
[404]1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
[1270]5 * Copyright (C) 2003-2013
[404]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
[442]19#include <iostream>
[404]20
21#include "test_tools.h"
22#include <lemon/smart_graph.h>
23#include <lemon/preflow.h>
[1228]24#include <lemon/edmonds_karp.h>
[404]25#include <lemon/concepts/digraph.h>
26#include <lemon/concepts/maps.h>
27#include <lemon/lgf_reader.h>
[409]28#include <lemon/elevator.h>
[404]29
30using namespace lemon;
31
[442]32char 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
[1228]68
69// Checks the general interface of a max flow algorithm
70template <typename GR, typename CAP>
71struct 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
[1262]124      ::lemon::ignore_unused_variable_warning(fm);
[1228]125    }
126
127  };
128
129};
130
131// Checks the specific parts of Preflow's interface
[409]132void checkPreflowCompile()
[404]133{
[1228]134  typedef int Value;
[404]135  typedef concepts::Digraph Digraph;
[1228]136  typedef concepts::ReadMap<Digraph::Arc, Value> CapMap;
[409]137  typedef Elevator<Digraph, Digraph::Node> Elev;
138  typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
139
[404]140  Digraph g;
[1228]141  Digraph::Node n;
[404]142  CapMap cap;
143
[632]144  typedef Preflow<Digraph, CapMap>
[1228]145      ::SetElevator<Elev>
146      ::SetStandardElevator<LinkedElev>
147      ::Create PreflowType;
[632]148  PreflowType preflow_test(g, cap, n, n);
149  const PreflowType& const_preflow_test = preflow_test;
[404]150
[736]151  const PreflowType::Elevator& elev = const_preflow_test.elevator();
152  preflow_test.elevator(const_cast<PreflowType::Elevator&>(elev));
[632]153
[1228]154  bool b = preflow_test.init(cap);
[404]155  preflow_test.startFirstPhase();
156  preflow_test.startSecondPhase();
157  preflow_test.runMinCut();
158
[1262]159  ::lemon::ignore_unused_variable_warning(b);
[404]160}
161
[1228]162// Checks the specific parts of EdmondsKarp's interface
163void checkEdmondsKarpCompile()
164{
165  typedef int Value;
166  typedef concepts::Digraph Digraph;
167  typedef concepts::ReadMap<Digraph::Arc, Value> CapMap;
168
169  Digraph g;
170  Digraph::Node n;
171  CapMap cap;
172
173  EdmondsKarp<Digraph, CapMap> ek_test(g, cap, n, n);
174
175  ek_test.init(cap);
176  bool b = ek_test.checkedInit(cap);
177  b = ek_test.augment();
178  ek_test.start();
179
[1262]180  ::lemon::ignore_unused_variable_warning(b);
[1228]181}
182
183
184template <typename T>
185T cutValue (const SmartDigraph& g,
[404]186              const SmartDigraph::NodeMap<bool>& cut,
[1228]187              const SmartDigraph::ArcMap<T>& cap) {
[404]188
[1228]189  T c=0;
[404]190  for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) {
191    if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e];
192  }
193  return c;
194}
195
[1228]196template <typename T>
[404]197bool checkFlow(const SmartDigraph& g,
[1228]198               const SmartDigraph::ArcMap<T>& flow,
199               const SmartDigraph::ArcMap<T>& cap,
[404]200               SmartDigraph::Node s, SmartDigraph::Node t) {
201
202  for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
203    if (flow[e] < 0 || flow[e] > cap[e]) return false;
204  }
205
206  for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) {
207    if (n == s || n == t) continue;
[1228]208    T sum = 0;
[404]209    for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) {
210      sum += flow[e];
211    }
212    for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) {
213      sum -= flow[e];
214    }
215    if (sum != 0) return false;
216  }
217  return true;
218}
219
[1027]220void initFlowTest()
221{
222  DIGRAPH_TYPEDEFS(SmartDigraph);
[1270]223
[1027]224  SmartDigraph g;
225  SmartDigraph::ArcMap<int> cap(g),iflow(g);
226  Node s=g.addNode(); Node t=g.addNode();
227  Node n1=g.addNode(); Node n2=g.addNode();
228  Arc a;
229  a=g.addArc(s,n1); cap[a]=20; iflow[a]=20;
230  a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0;
231  a=g.addArc(n2,t); cap[a]=20; iflow[a]=0;
232
233  Preflow<SmartDigraph> pre(g,cap,s,t);
234  pre.init(iflow);
235  pre.startFirstPhase();
236  check(pre.flowValue() == 10, "The incorrect max flow value.");
237  check(pre.minCut(s), "Wrong min cut (Node s).");
238  check(pre.minCut(n1), "Wrong min cut (Node n1).");
239  check(!pre.minCut(n2), "Wrong min cut (Node n2).");
240  check(!pre.minCut(t), "Wrong min cut (Node t).");
241}
242
[1228]243template <typename MF, typename SF>
244void checkMaxFlowAlg() {
245  typedef SmartDigraph Digraph;
246  DIGRAPH_TYPEDEFS(Digraph);
[1027]247
[1228]248  typedef typename MF::Value Value;
249  typedef Digraph::ArcMap<Value> CapMap;
250  typedef CapMap FlowMap;
251  typedef BoolNodeMap CutMap;
[404]252
253  Digraph g;
254  Node s, t;
255  CapMap cap(g);
[442]256  std::istringstream input(test_lgf);
[1228]257  DigraphReader<Digraph>(g,input)
258      .arcMap("capacity", cap)
259      .node("source",s)
260      .node("target",t)
261      .run();
[404]262
[1228]263  MF max_flow(g, cap, s, t);
264  max_flow.run();
[404]265
[1228]266  check(checkFlow(g, max_flow.flowMap(), cap, s, t),
[404]267        "The flow is not feasible.");
268
269  CutMap min_cut(g);
[1228]270  max_flow.minCutMap(min_cut);
271  Value min_cut_value = cutValue(g, min_cut, cap);
[404]272
[1228]273  check(max_flow.flowValue() == min_cut_value,
274        "The max flow value is not equal to the min cut value.");
[404]275
276  FlowMap flow(g);
[1228]277  for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e];
[404]278
[1228]279  Value flow_value = max_flow.flowValue();
[404]280
[1228]281  for (ArcIt e(g); e != INVALID; ++e) cap[e] = 2 * cap[e];
282  max_flow.init(flow);
283
284  SF::startFirstPhase(max_flow);       // start first phase of the algorithm
[404]285
286  CutMap min_cut1(g);
[1228]287  max_flow.minCutMap(min_cut1);
288  min_cut_value = cutValue(g, min_cut1, cap);
[404]289
[1228]290  check(max_flow.flowValue() == min_cut_value &&
291        min_cut_value == 2 * flow_value,
[404]292        "The max flow value or the min cut value is wrong.");
293
[1228]294  SF::startSecondPhase(max_flow);       // start second phase of the algorithm
[404]295
[1228]296  check(checkFlow(g, max_flow.flowMap(), cap, s, t),
[404]297        "The flow is not feasible.");
298
299  CutMap min_cut2(g);
[1228]300  max_flow.minCutMap(min_cut2);
301  min_cut_value = cutValue(g, min_cut2, cap);
[404]302
[1228]303  check(max_flow.flowValue() == min_cut_value &&
304        min_cut_value == 2 * flow_value,
305        "The max flow value or the min cut value was not doubled");
[404]306
307
[1228]308  max_flow.flowMap(flow);
[404]309
[1228]310  NodeIt tmp1(g, s);
[404]311  ++tmp1;
[1228]312  if (tmp1 != INVALID) s = tmp1;
[404]313
[1228]314  NodeIt tmp2(g, t);
[404]315  ++tmp2;
[1228]316  if (tmp2 != INVALID) t = tmp2;
[404]317
[1228]318  max_flow.source(s);
319  max_flow.target(t);
[404]320
[1228]321  max_flow.run();
[404]322
323  CutMap min_cut3(g);
[1228]324  max_flow.minCutMap(min_cut3);
325  min_cut_value=cutValue(g, min_cut3, cap);
[404]326
[1228]327  check(max_flow.flowValue() == min_cut_value,
328        "The max flow value or the min cut value is wrong.");
329}
[404]330
[1228]331// Struct for calling start functions of a general max flow algorithm
332template <typename MF>
333struct GeneralStartFunctions {
334
335  static void startFirstPhase(MF& mf) {
336    mf.start();
337  }
338
339  static void startSecondPhase(MF& mf) {
[1262]340    ::lemon::ignore_unused_variable_warning(mf);
[1228]341  }
342
343};
344
345// Struct for calling start functions of Preflow
346template <typename MF>
347struct PreflowStartFunctions {
348
349  static void startFirstPhase(MF& mf) {
350    mf.startFirstPhase();
351  }
352
353  static void startSecondPhase(MF& mf) {
354    mf.startSecondPhase();
355  }
356
357};
358
359int main() {
360
361  typedef concepts::Digraph GR;
362  typedef concepts::ReadMap<GR::Arc, int> CM1;
363  typedef concepts::ReadMap<GR::Arc, double> CM2;
364
365  // Check the interface of Preflow
366  checkConcept< MaxFlowClassConcept<GR, CM1>,
367                Preflow<GR, CM1> >();
368  checkConcept< MaxFlowClassConcept<GR, CM2>,
369                Preflow<GR, CM2> >();
370
371  // Check the interface of EdmondsKarp
372  checkConcept< MaxFlowClassConcept<GR, CM1>,
373                EdmondsKarp<GR, CM1> >();
374  checkConcept< MaxFlowClassConcept<GR, CM2>,
375                EdmondsKarp<GR, CM2> >();
376
377  // Check Preflow
378  typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<int> > PType1;
379  typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2;
380  checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >();
381  checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >();
382  initFlowTest();
[1270]383
[1228]384  // Check EdmondsKarp
385  typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<int> > EKType1;
386  typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2;
387  checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >();
388  checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >();
[404]389
[1027]390  initFlowTest();
[1270]391
[404]392  return 0;
393}
Note: See TracBrowser for help on using the repository browser.