COIN-OR::LEMON - Graph Library

source: lemon/test/edmonds_karp_test.cc @ 1224:92a884824429

Last change on this file since 1224:92a884824429 was 1224:92a884824429, checked in by Antal Nemes <thoneyvazul@…>, 13 years ago

Port Edmonds-Karp algorithm from svn -r3524 (#177)

File size: 5.4 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-2010
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/edmonds_karp.h>
24#include <lemon/concepts/digraph.h>
25#include <lemon/concepts/maps.h>
26#include <lemon/lgf_reader.h>
27
28using namespace lemon;
29
30char test_lgf[] =
31  "@nodes\n"
32  "label\n"
33  "0\n"
34  "1\n"
35  "2\n"
36  "3\n"
37  "4\n"
38  "5\n"
39  "6\n"
40  "7\n"
41  "8\n"
42  "9\n"
43  "@arcs\n"
44  "    label capacity\n"
45  "0 1 0     20\n"
46  "0 2 1     0\n"
47  "1 1 2     3\n"
48  "1 2 3     8\n"
49  "1 3 4     8\n"
50  "2 5 5     5\n"
51  "3 2 6     5\n"
52  "3 5 7     5\n"
53  "3 6 8     5\n"
54  "4 3 9     3\n"
55  "5 7 10    3\n"
56  "5 6 11    10\n"
57  "5 8 12    10\n"
58  "6 8 13    8\n"
59  "8 9 14    20\n"
60  "8 1 15    5\n"
61  "9 5 16    5\n"
62  "@attributes\n"
63  "source 1\n"
64  "target 8\n";
65
66void checkEdmondKarpCompile() {
67  typedef int VType;
68  typedef concepts::Digraph Digraph;
69
70  typedef Digraph::Node Node;
71  typedef Digraph::Arc Arc;
72  typedef concepts::ReadMap<Arc,VType> CapMap;
73  typedef concepts::ReadWriteMap<Arc,VType> FlowMap;
74  typedef concepts::WriteMap<Node,bool> CutMap;
75
76  Digraph g;
77  Node n;
78  Arc e;
79  CapMap cap;
80  FlowMap flow;
81  CutMap cut;
82  VType v;
83  bool b;
84  ignore_unused_variable_warning(v,b);
85  typedef EdmondsKarp<Digraph, CapMap>
86              ::DefFlowMap<FlowMap>
87              ::Create EKType;
88  EKType ek_test(g, cap, n, n);
89  const EKType& const_ek_test = ek_test;
90
91  EKType::Tolerance tol = const_ek_test.tolerance();
92  ek_test.tolerance(tol);
93
94  ek_test
95    .capacityMap(cap)
96    .flowMap(flow)
97    .source(n)
98    .target(n);
99
100  ek_test.init();
101  ek_test.start();
102
103  v = const_ek_test.flowValue();
104  v = const_ek_test.flow(e);
105
106  const FlowMap& fm = const_ek_test.flowMap();
107  b = const_ek_test.minCut(n);
108  const_ek_test.minCutMap(cut);
109
110  ignore_unused_variable_warning(fm);
111}
112
113int cutValue (const SmartDigraph& g,
114              const SmartDigraph::NodeMap<bool>& cut,
115              const SmartDigraph::ArcMap<int>& cap) {
116
117  int c=0;
118  for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) {
119    if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e];
120  }
121  return c;
122}
123
124bool checkFlow(const SmartDigraph& g,
125               const SmartDigraph::ArcMap<int>& flow,
126               const SmartDigraph::ArcMap<int>& cap,
127               SmartDigraph::Node s, SmartDigraph::Node t) {
128
129  for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
130    if (flow[e] < 0 || flow[e] > cap[e]) return false;
131  }
132
133  for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) {
134    if (n == s || n == t) continue;
135    int sum = 0;
136    for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) {
137      sum += flow[e];
138    }
139    for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) {
140      sum -= flow[e];
141    }
142    if (sum != 0) return false;
143  }
144  return true;
145}
146
147int main() {
148
149  typedef SmartDigraph Digraph;
150
151  typedef Digraph::Node Node;
152  typedef Digraph::NodeIt NodeIt;
153  typedef Digraph::ArcIt ArcIt;
154  typedef Digraph::ArcMap<int> CapMap;
155  typedef Digraph::ArcMap<int> FlowMap;
156  typedef Digraph::NodeMap<bool> CutMap;
157
158  typedef EdmondsKarp<Digraph, CapMap> EKType;
159
160  Digraph g;
161  Node s, t;
162  CapMap cap(g);
163  std::istringstream input(test_lgf);
164  DigraphReader<Digraph>(g,input).
165    arcMap("capacity", cap).
166    node("source",s).
167    node("target",t).
168    run();
169
170  EKType ek_test(g, cap, s, t);
171  ek_test.run();
172
173  check(checkFlow(g, ek_test.flowMap(), cap, s, t),
174        "The flow is not feasible.");
175
176  CutMap min_cut(g);
177  ek_test.minCutMap(min_cut);
178  int min_cut_value=cutValue(g,min_cut,cap);
179
180  check(ek_test.flowValue() == min_cut_value,
181        "The max flow value is not equal to the three min cut values.");
182
183  FlowMap flow(g);
184  for(ArcIt e(g); e!=INVALID; ++e) flow[e] = ek_test.flowMap()[e];
185
186  int flow_value=ek_test.flowValue();
187
188  for(ArcIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e];
189  ek_test.flowInit(flow);
190  ek_test.start();
191
192  CutMap min_cut1(g);
193  ek_test.minCutMap(min_cut1);
194  min_cut_value=cutValue(g,min_cut1,cap);
195
196  check(ek_test.flowValue() == min_cut_value &&
197        min_cut_value == 2*flow_value,
198        "The max flow value or the min cut value is wrong.");
199
200  check(checkFlow(g, ek_test.flowMap(), cap, s, t),
201        "The flow is not feasible.");
202
203  CutMap min_cut2(g);
204  ek_test.minCutMap(min_cut2);
205  min_cut_value=cutValue(g,min_cut2,cap);
206
207  check(ek_test.flowValue() == min_cut_value &&
208        min_cut_value == 2*flow_value,
209        "The max flow value or the three min cut values were not doubled.");
210
211
212  ek_test.flowMap(flow);
213
214  NodeIt tmp1(g,s);
215  ++tmp1;
216  if ( tmp1 != INVALID ) s=tmp1;
217
218  NodeIt tmp2(g,t);
219  ++tmp2;
220  if ( tmp2 != INVALID ) t=tmp2;
221
222  ek_test.source(s);
223  ek_test.target(t);
224
225  ek_test.run();
226
227  CutMap min_cut3(g);
228  ek_test.minCutMap(min_cut3);
229  min_cut_value=cutValue(g,min_cut3,cap);
230
231
232  check(ek_test.flowValue() == min_cut_value,
233        "The max flow value or the three min cut values are incorrect.");
234
235  return 0;
236}
Note: See TracBrowser for help on using the repository browser.