COIN-OR::LEMON - Graph Library

source: lemon/test/max_flow_test.cc @ 1300:62dba6c90f35

Last change on this file since 1300:62dba6c90f35 was 1270:dceba191c00d, checked in by Alpar Juttner <alpar@…>, 11 years ago

Apply unify-sources.sh to the source tree

File size: 9.7 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
30using namespace lemon;
31
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
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
124      ::lemon::ignore_unused_variable_warning(fm);
125    }
126
127  };
128
129};
130
131// Checks the specific parts of Preflow's interface
132void 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;
139
140  Digraph g;
141  Digraph::Node n;
142  CapMap cap;
143
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;
150
151  const PreflowType::Elevator& elev = const_preflow_test.elevator();
152  preflow_test.elevator(const_cast<PreflowType::Elevator&>(elev));
153
154  bool b = preflow_test.init(cap);
155  preflow_test.startFirstPhase();
156  preflow_test.startSecondPhase();
157  preflow_test.runMinCut();
158
159  ::lemon::ignore_unused_variable_warning(b);
160}
161
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  typedef Elevator<Digraph, Digraph::Node> Elev;
169  typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
170
171  Digraph g;
172  Digraph::Node n;
173  CapMap cap;
174
175  EdmondsKarp<Digraph, CapMap> ek_test(g, cap, n, n);
176
177  ek_test.init(cap);
178  bool b = ek_test.checkedInit(cap);
179  b = ek_test.augment();
180  ek_test.start();
181
182  ::lemon::ignore_unused_variable_warning(b);
183}
184
185
186template <typename T>
187T cutValue (const SmartDigraph& g,
188              const SmartDigraph::NodeMap<bool>& cut,
189              const SmartDigraph::ArcMap<T>& cap) {
190
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}
197
198template <typename T>
199bool checkFlow(const SmartDigraph& g,
200               const SmartDigraph::ArcMap<T>& flow,
201               const SmartDigraph::ArcMap<T>& cap,
202               SmartDigraph::Node s, SmartDigraph::Node t) {
203
204  for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
205    if (flow[e] < 0 || flow[e] > cap[e]) return false;
206  }
207
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}
221
222void initFlowTest()
223{
224  DIGRAPH_TYPEDEFS(SmartDigraph);
225
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;
234
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}
244
245template <typename MF, typename SF>
246void checkMaxFlowAlg() {
247  typedef SmartDigraph Digraph;
248  DIGRAPH_TYPEDEFS(Digraph);
249
250  typedef typename MF::Value Value;
251  typedef Digraph::ArcMap<Value> CapMap;
252  typedef CapMap FlowMap;
253  typedef BoolNodeMap CutMap;
254
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();
264
265  MF max_flow(g, cap, s, t);
266  max_flow.run();
267
268  check(checkFlow(g, max_flow.flowMap(), cap, s, t),
269        "The flow is not feasible.");
270
271  CutMap min_cut(g);
272  max_flow.minCutMap(min_cut);
273  Value min_cut_value = cutValue(g, min_cut, cap);
274
275  check(max_flow.flowValue() == min_cut_value,
276        "The max flow value is not equal to the min cut value.");
277
278  FlowMap flow(g);
279  for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e];
280
281  Value flow_value = max_flow.flowValue();
282
283  for (ArcIt e(g); e != INVALID; ++e) cap[e] = 2 * cap[e];
284  max_flow.init(flow);
285
286  SF::startFirstPhase(max_flow);       // start first phase of the algorithm
287
288  CutMap min_cut1(g);
289  max_flow.minCutMap(min_cut1);
290  min_cut_value = cutValue(g, min_cut1, cap);
291
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.");
295
296  SF::startSecondPhase(max_flow);       // start second phase of the algorithm
297
298  check(checkFlow(g, max_flow.flowMap(), cap, s, t),
299        "The flow is not feasible.");
300
301  CutMap min_cut2(g);
302  max_flow.minCutMap(min_cut2);
303  min_cut_value = cutValue(g, min_cut2, cap);
304
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");
308
309
310  max_flow.flowMap(flow);
311
312  NodeIt tmp1(g, s);
313  ++tmp1;
314  if (tmp1 != INVALID) s = tmp1;
315
316  NodeIt tmp2(g, t);
317  ++tmp2;
318  if (tmp2 != INVALID) t = tmp2;
319
320  max_flow.source(s);
321  max_flow.target(t);
322
323  max_flow.run();
324
325  CutMap min_cut3(g);
326  max_flow.minCutMap(min_cut3);
327  min_cut_value=cutValue(g, min_cut3, cap);
328
329  check(max_flow.flowValue() == min_cut_value,
330        "The max flow value or the min cut value is wrong.");
331}
332
333// Struct for calling start functions of a general max flow algorithm
334template <typename MF>
335struct GeneralStartFunctions {
336
337  static void startFirstPhase(MF& mf) {
338    mf.start();
339  }
340
341  static void startSecondPhase(MF& mf) {
342    ::lemon::ignore_unused_variable_warning(mf);
343  }
344
345};
346
347// Struct for calling start functions of Preflow
348template <typename MF>
349struct PreflowStartFunctions {
350
351  static void startFirstPhase(MF& mf) {
352    mf.startFirstPhase();
353  }
354
355  static void startSecondPhase(MF& mf) {
356    mf.startSecondPhase();
357  }
358
359};
360
361int main() {
362
363  typedef concepts::Digraph GR;
364  typedef concepts::ReadMap<GR::Arc, int> CM1;
365  typedef concepts::ReadMap<GR::Arc, double> CM2;
366
367  // Check the interface of Preflow
368  checkConcept< MaxFlowClassConcept<GR, CM1>,
369                Preflow<GR, CM1> >();
370  checkConcept< MaxFlowClassConcept<GR, CM2>,
371                Preflow<GR, CM2> >();
372
373  // Check the interface of EdmondsKarp
374  checkConcept< MaxFlowClassConcept<GR, CM1>,
375                EdmondsKarp<GR, CM1> >();
376  checkConcept< MaxFlowClassConcept<GR, CM2>,
377                EdmondsKarp<GR, CM2> >();
378
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();
385
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> >();
391
392  initFlowTest();
393
394  return 0;
395}
Note: See TracBrowser for help on using the repository browser.