62 "9 5 16 5\n" |
63 "9 5 16 5\n" |
63 "@attributes\n" |
64 "@attributes\n" |
64 "source 1\n" |
65 "source 1\n" |
65 "target 8\n"; |
66 "target 8\n"; |
66 |
67 |
|
68 |
|
69 // Checks the general interface of a max flow algorithm |
|
70 template <typename GR, typename CAP> |
|
71 struct 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 ignore_unused_variable_warning(fm); |
|
125 } |
|
126 |
|
127 }; |
|
128 |
|
129 }; |
|
130 |
|
131 // Checks the specific parts of Preflow's interface |
67 void checkPreflowCompile() |
132 void checkPreflowCompile() |
68 { |
133 { |
69 typedef int VType; |
134 typedef int Value; |
70 typedef concepts::Digraph Digraph; |
135 typedef concepts::Digraph Digraph; |
71 |
136 typedef concepts::ReadMap<Digraph::Arc, Value> CapMap; |
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; |
137 typedef Elevator<Digraph, Digraph::Node> Elev; |
79 typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev; |
138 typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev; |
80 |
139 |
81 Digraph g; |
140 Digraph g; |
82 Node n; |
141 Digraph::Node n; |
83 Arc e; |
|
84 CapMap cap; |
142 CapMap cap; |
85 FlowMap flow; |
|
86 CutMap cut; |
|
87 VType v; |
|
88 bool b; |
|
89 ignore_unused_variable_warning(v,b); |
|
90 |
143 |
91 typedef Preflow<Digraph, CapMap> |
144 typedef Preflow<Digraph, CapMap> |
92 ::SetFlowMap<FlowMap> |
145 ::SetElevator<Elev> |
93 ::SetElevator<Elev> |
146 ::SetStandardElevator<LinkedElev> |
94 ::SetStandardElevator<LinkedElev> |
147 ::Create PreflowType; |
95 ::Create PreflowType; |
|
96 PreflowType preflow_test(g, cap, n, n); |
148 PreflowType preflow_test(g, cap, n, n); |
97 const PreflowType& const_preflow_test = preflow_test; |
149 const PreflowType& const_preflow_test = preflow_test; |
98 |
150 |
99 const PreflowType::Elevator& elev = const_preflow_test.elevator(); |
151 const PreflowType::Elevator& elev = const_preflow_test.elevator(); |
100 preflow_test.elevator(const_cast<PreflowType::Elevator&>(elev)); |
152 preflow_test.elevator(const_cast<PreflowType::Elevator&>(elev)); |
101 PreflowType::Tolerance tol = const_preflow_test.tolerance(); |
153 |
102 preflow_test.tolerance(tol); |
154 bool b = preflow_test.init(cap); |
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(); |
155 preflow_test.startFirstPhase(); |
113 preflow_test.startSecondPhase(); |
156 preflow_test.startSecondPhase(); |
114 preflow_test.run(); |
|
115 preflow_test.runMinCut(); |
157 preflow_test.runMinCut(); |
116 |
158 |
117 v = const_preflow_test.flowValue(); |
159 ignore_unused_variable_warning(b); |
118 v = const_preflow_test.flow(e); |
160 } |
119 const FlowMap& fm = const_preflow_test.flowMap(); |
161 |
120 b = const_preflow_test.minCut(n); |
162 // Checks the specific parts of EdmondsKarp's interface |
121 const_preflow_test.minCutMap(cut); |
163 void checkEdmondsKarpCompile() |
122 |
164 { |
123 ignore_unused_variable_warning(fm); |
165 typedef int Value; |
124 } |
166 typedef concepts::Digraph Digraph; |
125 |
167 typedef concepts::ReadMap<Digraph::Arc, Value> CapMap; |
126 int cutValue (const SmartDigraph& g, |
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 ignore_unused_variable_warning(b); |
|
183 } |
|
184 |
|
185 |
|
186 template <typename T> |
|
187 T cutValue (const SmartDigraph& g, |
127 const SmartDigraph::NodeMap<bool>& cut, |
188 const SmartDigraph::NodeMap<bool>& cut, |
128 const SmartDigraph::ArcMap<int>& cap) { |
189 const SmartDigraph::ArcMap<T>& cap) { |
129 |
190 |
130 int c=0; |
191 T c=0; |
131 for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) { |
192 for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) { |
132 if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e]; |
193 if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e]; |
133 } |
194 } |
134 return c; |
195 return c; |
135 } |
196 } |
136 |
197 |
|
198 template <typename T> |
137 bool checkFlow(const SmartDigraph& g, |
199 bool checkFlow(const SmartDigraph& g, |
138 const SmartDigraph::ArcMap<int>& flow, |
200 const SmartDigraph::ArcMap<T>& flow, |
139 const SmartDigraph::ArcMap<int>& cap, |
201 const SmartDigraph::ArcMap<T>& cap, |
140 SmartDigraph::Node s, SmartDigraph::Node t) { |
202 SmartDigraph::Node s, SmartDigraph::Node t) { |
141 |
203 |
142 for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) { |
204 for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) { |
143 if (flow[e] < 0 || flow[e] > cap[e]) return false; |
205 if (flow[e] < 0 || flow[e] > cap[e]) return false; |
144 } |
206 } |
145 |
207 |
146 for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) { |
208 for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) { |
147 if (n == s || n == t) continue; |
209 if (n == s || n == t) continue; |
148 int sum = 0; |
210 T sum = 0; |
149 for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) { |
211 for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) { |
150 sum += flow[e]; |
212 sum += flow[e]; |
151 } |
213 } |
152 for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) { |
214 for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) { |
153 sum -= flow[e]; |
215 sum -= flow[e]; |
178 check(pre.minCut(n1), "Wrong min cut (Node n1)."); |
240 check(pre.minCut(n1), "Wrong min cut (Node n1)."); |
179 check(!pre.minCut(n2), "Wrong min cut (Node n2)."); |
241 check(!pre.minCut(n2), "Wrong min cut (Node n2)."); |
180 check(!pre.minCut(t), "Wrong min cut (Node t)."); |
242 check(!pre.minCut(t), "Wrong min cut (Node t)."); |
181 } |
243 } |
182 |
244 |
183 |
245 template <typename MF, typename SF> |
184 int main() { |
246 void checkMaxFlowAlg() { |
185 |
|
186 typedef SmartDigraph Digraph; |
247 typedef SmartDigraph Digraph; |
187 |
248 DIGRAPH_TYPEDEFS(Digraph); |
188 typedef Digraph::Node Node; |
249 |
189 typedef Digraph::NodeIt NodeIt; |
250 typedef typename MF::Value Value; |
190 typedef Digraph::ArcIt ArcIt; |
251 typedef Digraph::ArcMap<Value> CapMap; |
191 typedef Digraph::ArcMap<int> CapMap; |
252 typedef CapMap FlowMap; |
192 typedef Digraph::ArcMap<int> FlowMap; |
253 typedef BoolNodeMap CutMap; |
193 typedef Digraph::NodeMap<bool> CutMap; |
|
194 |
|
195 typedef Preflow<Digraph, CapMap> PType; |
|
196 |
254 |
197 Digraph g; |
255 Digraph g; |
198 Node s, t; |
256 Node s, t; |
199 CapMap cap(g); |
257 CapMap cap(g); |
200 std::istringstream input(test_lgf); |
258 std::istringstream input(test_lgf); |
201 DigraphReader<Digraph>(g,input). |
259 DigraphReader<Digraph>(g,input) |
202 arcMap("capacity", cap). |
260 .arcMap("capacity", cap) |
203 node("source",s). |
261 .node("source",s) |
204 node("target",t). |
262 .node("target",t) |
205 run(); |
263 .run(); |
206 |
264 |
207 PType preflow_test(g, cap, s, t); |
265 MF max_flow(g, cap, s, t); |
208 preflow_test.run(); |
266 max_flow.run(); |
209 |
267 |
210 check(checkFlow(g, preflow_test.flowMap(), cap, s, t), |
268 check(checkFlow(g, max_flow.flowMap(), cap, s, t), |
211 "The flow is not feasible."); |
269 "The flow is not feasible."); |
212 |
270 |
213 CutMap min_cut(g); |
271 CutMap min_cut(g); |
214 preflow_test.minCutMap(min_cut); |
272 max_flow.minCutMap(min_cut); |
215 int min_cut_value=cutValue(g,min_cut,cap); |
273 Value min_cut_value = cutValue(g, min_cut, cap); |
216 |
274 |
217 check(preflow_test.flowValue() == min_cut_value, |
275 check(max_flow.flowValue() == min_cut_value, |
218 "The max flow value is not equal to the three min cut values."); |
276 "The max flow value is not equal to the min cut value."); |
219 |
277 |
220 FlowMap flow(g); |
278 FlowMap flow(g); |
221 for(ArcIt e(g); e!=INVALID; ++e) flow[e] = preflow_test.flowMap()[e]; |
279 for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e]; |
222 |
280 |
223 int flow_value=preflow_test.flowValue(); |
281 Value flow_value = max_flow.flowValue(); |
224 |
282 |
225 for(ArcIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e]; |
283 for (ArcIt e(g); e != INVALID; ++e) cap[e] = 2 * cap[e]; |
226 preflow_test.init(flow); |
284 max_flow.init(flow); |
227 preflow_test.startFirstPhase(); |
285 |
|
286 SF::startFirstPhase(max_flow); // start first phase of the algorithm |
228 |
287 |
229 CutMap min_cut1(g); |
288 CutMap min_cut1(g); |
230 preflow_test.minCutMap(min_cut1); |
289 max_flow.minCutMap(min_cut1); |
231 min_cut_value=cutValue(g,min_cut1,cap); |
290 min_cut_value = cutValue(g, min_cut1, cap); |
232 |
291 |
233 check(preflow_test.flowValue() == min_cut_value && |
292 check(max_flow.flowValue() == min_cut_value && |
234 min_cut_value == 2*flow_value, |
293 min_cut_value == 2 * flow_value, |
235 "The max flow value or the min cut value is wrong."); |
294 "The max flow value or the min cut value is wrong."); |
236 |
295 |
237 preflow_test.startSecondPhase(); |
296 SF::startSecondPhase(max_flow); // start second phase of the algorithm |
238 |
297 |
239 check(checkFlow(g, preflow_test.flowMap(), cap, s, t), |
298 check(checkFlow(g, max_flow.flowMap(), cap, s, t), |
240 "The flow is not feasible."); |
299 "The flow is not feasible."); |
241 |
300 |
242 CutMap min_cut2(g); |
301 CutMap min_cut2(g); |
243 preflow_test.minCutMap(min_cut2); |
302 max_flow.minCutMap(min_cut2); |
244 min_cut_value=cutValue(g,min_cut2,cap); |
303 min_cut_value = cutValue(g, min_cut2, cap); |
245 |
304 |
246 check(preflow_test.flowValue() == min_cut_value && |
305 check(max_flow.flowValue() == min_cut_value && |
247 min_cut_value == 2*flow_value, |
306 min_cut_value == 2 * flow_value, |
248 "The max flow value or the three min cut values were not doubled"); |
307 "The max flow value or the min cut value was not doubled"); |
249 |
308 |
250 |
309 |
251 preflow_test.flowMap(flow); |
310 max_flow.flowMap(flow); |
252 |
311 |
253 NodeIt tmp1(g,s); |
312 NodeIt tmp1(g, s); |
254 ++tmp1; |
313 ++tmp1; |
255 if ( tmp1 != INVALID ) s=tmp1; |
314 if (tmp1 != INVALID) s = tmp1; |
256 |
315 |
257 NodeIt tmp2(g,t); |
316 NodeIt tmp2(g, t); |
258 ++tmp2; |
317 ++tmp2; |
259 if ( tmp2 != INVALID ) t=tmp2; |
318 if (tmp2 != INVALID) t = tmp2; |
260 |
319 |
261 preflow_test.source(s); |
320 max_flow.source(s); |
262 preflow_test.target(t); |
321 max_flow.target(t); |
263 |
322 |
264 preflow_test.run(); |
323 max_flow.run(); |
265 |
324 |
266 CutMap min_cut3(g); |
325 CutMap min_cut3(g); |
267 preflow_test.minCutMap(min_cut3); |
326 max_flow.minCutMap(min_cut3); |
268 min_cut_value=cutValue(g,min_cut3,cap); |
327 min_cut_value=cutValue(g, min_cut3, cap); |
269 |
328 |
270 |
329 check(max_flow.flowValue() == min_cut_value, |
271 check(preflow_test.flowValue() == min_cut_value, |
330 "The max flow value or the min cut value is wrong."); |
272 "The max flow value or the three min cut values are incorrect."); |
331 } |
|
332 |
|
333 // Struct for calling start functions of a general max flow algorithm |
|
334 template <typename MF> |
|
335 struct GeneralStartFunctions { |
|
336 |
|
337 static void startFirstPhase(MF& mf) { |
|
338 mf.start(); |
|
339 } |
|
340 |
|
341 static void startSecondPhase(MF& mf) { |
|
342 ignore_unused_variable_warning(mf); |
|
343 } |
|
344 |
|
345 }; |
|
346 |
|
347 // Struct for calling start functions of Preflow |
|
348 template <typename MF> |
|
349 struct 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 |
|
361 int 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> >(); |
273 |
391 |
274 initFlowTest(); |
392 initFlowTest(); |
275 |
393 |
276 return 0; |
394 return 0; |
277 } |
395 } |