COIN-OR::LEMON - Graph Library

source: lemon/test/max_flow_test.cc

Last change on this file was 1396:61fdd06833a6, checked in by Alpar Juttner <alpar@…>, 16 months ago

Fix warnings emitted by VS2017 (#614)

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