COIN-OR::LEMON - Graph Library

source: lemon/test/preflow_test.cc @ 555:861a9d5ff283

Last change on this file since 555:861a9d5ff283 was 463:88ed40ad0d4f, checked in by Alpar Juttner <alpar@…>, 16 years ago

Happy New Year again

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