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/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 |
|
29 using namespace lemon; |
|
30 |
|
31 char 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 |
|
67 void 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 VType v; |
|
88 bool b; |
|
89 ignore_unused_variable_warning(v,b); |
|
90 |
|
91 typedef Preflow<Digraph, CapMap> |
|
92 ::SetFlowMap<FlowMap> |
|
93 ::SetElevator<Elev> |
|
94 ::SetStandardElevator<LinkedElev> |
|
95 ::Create PreflowType; |
|
96 PreflowType preflow_test(g, cap, n, n); |
|
97 const PreflowType& const_preflow_test = preflow_test; |
|
98 |
|
99 const PreflowType::Elevator& elev = const_preflow_test.elevator(); |
|
100 preflow_test.elevator(const_cast<PreflowType::Elevator&>(elev)); |
|
101 PreflowType::Tolerance tol = const_preflow_test.tolerance(); |
|
102 preflow_test.tolerance(tol); |
|
103 |
|
104 preflow_test |
|
105 .capacityMap(cap) |
|
106 .flowMap(flow) |
|
107 .source(n) |
|
108 .target(n); |
|
109 |
|
110 preflow_test.init(); |
|
111 preflow_test.init(cap); |
|
112 preflow_test.startFirstPhase(); |
|
113 preflow_test.startSecondPhase(); |
|
114 preflow_test.run(); |
|
115 preflow_test.runMinCut(); |
|
116 |
|
117 v = const_preflow_test.flowValue(); |
|
118 v = const_preflow_test.flow(e); |
|
119 const FlowMap& fm = const_preflow_test.flowMap(); |
|
120 b = const_preflow_test.minCut(n); |
|
121 const_preflow_test.minCutMap(cut); |
|
122 |
|
123 ignore_unused_variable_warning(fm); |
|
124 } |
|
125 |
|
126 int cutValue (const SmartDigraph& g, |
|
127 const SmartDigraph::NodeMap<bool>& cut, |
|
128 const SmartDigraph::ArcMap<int>& cap) { |
|
129 |
|
130 int c=0; |
|
131 for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) { |
|
132 if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e]; |
|
133 } |
|
134 return c; |
|
135 } |
|
136 |
|
137 bool checkFlow(const SmartDigraph& g, |
|
138 const SmartDigraph::ArcMap<int>& flow, |
|
139 const SmartDigraph::ArcMap<int>& cap, |
|
140 SmartDigraph::Node s, SmartDigraph::Node t) { |
|
141 |
|
142 for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) { |
|
143 if (flow[e] < 0 || flow[e] > cap[e]) return false; |
|
144 } |
|
145 |
|
146 for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) { |
|
147 if (n == s || n == t) continue; |
|
148 int sum = 0; |
|
149 for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) { |
|
150 sum += flow[e]; |
|
151 } |
|
152 for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) { |
|
153 sum -= flow[e]; |
|
154 } |
|
155 if (sum != 0) return false; |
|
156 } |
|
157 return true; |
|
158 } |
|
159 |
|
160 void initFlowTest() |
|
161 { |
|
162 DIGRAPH_TYPEDEFS(SmartDigraph); |
|
163 |
|
164 SmartDigraph g; |
|
165 SmartDigraph::ArcMap<int> cap(g),iflow(g); |
|
166 Node s=g.addNode(); Node t=g.addNode(); |
|
167 Node n1=g.addNode(); Node n2=g.addNode(); |
|
168 Arc a; |
|
169 a=g.addArc(s,n1); cap[a]=20; iflow[a]=20; |
|
170 a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0; |
|
171 a=g.addArc(n2,t); cap[a]=20; iflow[a]=0; |
|
172 |
|
173 Preflow<SmartDigraph> pre(g,cap,s,t); |
|
174 pre.init(iflow); |
|
175 pre.startFirstPhase(); |
|
176 check(pre.flowValue() == 10, "The incorrect max flow value."); |
|
177 check(pre.minCut(s), "Wrong min cut (Node s)."); |
|
178 check(pre.minCut(n1), "Wrong min cut (Node n1)."); |
|
179 check(!pre.minCut(n2), "Wrong min cut (Node n2)."); |
|
180 check(!pre.minCut(t), "Wrong min cut (Node t)."); |
|
181 } |
|
182 |
|
183 |
|
184 int main() { |
|
185 |
|
186 typedef SmartDigraph Digraph; |
|
187 |
|
188 typedef Digraph::Node Node; |
|
189 typedef Digraph::NodeIt NodeIt; |
|
190 typedef Digraph::ArcIt ArcIt; |
|
191 typedef Digraph::ArcMap<int> CapMap; |
|
192 typedef Digraph::ArcMap<int> FlowMap; |
|
193 typedef Digraph::NodeMap<bool> CutMap; |
|
194 |
|
195 typedef Preflow<Digraph, CapMap> PType; |
|
196 |
|
197 Digraph g; |
|
198 Node s, t; |
|
199 CapMap cap(g); |
|
200 std::istringstream input(test_lgf); |
|
201 DigraphReader<Digraph>(g,input). |
|
202 arcMap("capacity", cap). |
|
203 node("source",s). |
|
204 node("target",t). |
|
205 run(); |
|
206 |
|
207 PType preflow_test(g, cap, s, t); |
|
208 preflow_test.run(); |
|
209 |
|
210 check(checkFlow(g, preflow_test.flowMap(), cap, s, t), |
|
211 "The flow is not feasible."); |
|
212 |
|
213 CutMap min_cut(g); |
|
214 preflow_test.minCutMap(min_cut); |
|
215 int min_cut_value=cutValue(g,min_cut,cap); |
|
216 |
|
217 check(preflow_test.flowValue() == min_cut_value, |
|
218 "The max flow value is not equal to the three min cut values."); |
|
219 |
|
220 FlowMap flow(g); |
|
221 for(ArcIt e(g); e!=INVALID; ++e) flow[e] = preflow_test.flowMap()[e]; |
|
222 |
|
223 int flow_value=preflow_test.flowValue(); |
|
224 |
|
225 for(ArcIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e]; |
|
226 preflow_test.init(flow); |
|
227 preflow_test.startFirstPhase(); |
|
228 |
|
229 CutMap min_cut1(g); |
|
230 preflow_test.minCutMap(min_cut1); |
|
231 min_cut_value=cutValue(g,min_cut1,cap); |
|
232 |
|
233 check(preflow_test.flowValue() == min_cut_value && |
|
234 min_cut_value == 2*flow_value, |
|
235 "The max flow value or the min cut value is wrong."); |
|
236 |
|
237 preflow_test.startSecondPhase(); |
|
238 |
|
239 check(checkFlow(g, preflow_test.flowMap(), cap, s, t), |
|
240 "The flow is not feasible."); |
|
241 |
|
242 CutMap min_cut2(g); |
|
243 preflow_test.minCutMap(min_cut2); |
|
244 min_cut_value=cutValue(g,min_cut2,cap); |
|
245 |
|
246 check(preflow_test.flowValue() == min_cut_value && |
|
247 min_cut_value == 2*flow_value, |
|
248 "The max flow value or the three min cut values were not doubled"); |
|
249 |
|
250 |
|
251 preflow_test.flowMap(flow); |
|
252 |
|
253 NodeIt tmp1(g,s); |
|
254 ++tmp1; |
|
255 if ( tmp1 != INVALID ) s=tmp1; |
|
256 |
|
257 NodeIt tmp2(g,t); |
|
258 ++tmp2; |
|
259 if ( tmp2 != INVALID ) t=tmp2; |
|
260 |
|
261 preflow_test.source(s); |
|
262 preflow_test.target(t); |
|
263 |
|
264 preflow_test.run(); |
|
265 |
|
266 CutMap min_cut3(g); |
|
267 preflow_test.minCutMap(min_cut3); |
|
268 min_cut_value=cutValue(g,min_cut3,cap); |
|
269 |
|
270 |
|
271 check(preflow_test.flowValue() == min_cut_value, |
|
272 "The max flow value or the three min cut values are incorrect."); |
|
273 |
|
274 initFlowTest(); |
|
275 |
|
276 return 0; |
|
277 } |
|