180 ::lemon::ignore_unused_variable_warning(b); |
180 ::lemon::ignore_unused_variable_warning(b); |
181 } |
181 } |
182 |
182 |
183 |
183 |
184 template <typename T> |
184 template <typename T> |
185 T cutValue (const SmartDigraph& g, |
185 T cutValue(const SmartDigraph& g, |
186 const SmartDigraph::NodeMap<bool>& cut, |
186 const SmartDigraph::NodeMap<bool>& cut, |
187 const SmartDigraph::ArcMap<T>& cap) { |
187 const SmartDigraph::ArcMap<T>& cap) { |
188 |
188 |
189 T c=0; |
189 T c = 0; |
190 for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) { |
190 for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) { |
191 if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e]; |
191 if (cut[g.source(e)] && !cut[g.target(e)]) c += cap[e]; |
192 } |
192 } |
193 return c; |
193 return c; |
194 } |
194 } |
195 |
195 |
196 template <typename T> |
196 template <typename T> |
215 if (sum != 0) return false; |
215 if (sum != 0) return false; |
216 } |
216 } |
217 return true; |
217 return true; |
218 } |
218 } |
219 |
219 |
220 void initFlowTest() |
220 void checkInitPreflow() |
221 { |
221 { |
222 DIGRAPH_TYPEDEFS(SmartDigraph); |
222 DIGRAPH_TYPEDEFS(SmartDigraph); |
223 |
223 |
224 SmartDigraph g; |
224 SmartDigraph g; |
225 SmartDigraph::ArcMap<int> cap(g),iflow(g); |
225 SmartDigraph::ArcMap<int> cap(g), iflow(g); |
226 Node s=g.addNode(); Node t=g.addNode(); |
226 Node s = g.addNode(); Node t = g.addNode(); |
227 Node n1=g.addNode(); Node n2=g.addNode(); |
227 Node n1 = g.addNode(); Node n2 = g.addNode(); |
228 Arc a; |
228 Arc a; |
229 a=g.addArc(s,n1); cap[a]=20; iflow[a]=20; |
229 a = g.addArc(s, n1); cap[a] = 20; iflow[a] = 20; |
230 a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0; |
230 a = g.addArc(n1, n2); cap[a] = 10; iflow[a] = 0; |
231 a=g.addArc(n2,t); cap[a]=20; iflow[a]=0; |
231 a = g.addArc(n2, t); cap[a] = 20; iflow[a] = 0; |
232 |
232 |
233 Preflow<SmartDigraph> pre(g,cap,s,t); |
233 Preflow<SmartDigraph> pre(g, cap, s, t); |
234 pre.init(iflow); |
234 pre.init(iflow); |
235 pre.startFirstPhase(); |
235 pre.startFirstPhase(); |
236 check(pre.flowValue() == 10, "The incorrect max flow value."); |
236 |
|
237 check(pre.flowValue() == 10, "Incorrect max flow value."); |
237 check(pre.minCut(s), "Wrong min cut (Node s)."); |
238 check(pre.minCut(s), "Wrong min cut (Node s)."); |
238 check(pre.minCut(n1), "Wrong min cut (Node n1)."); |
239 check(pre.minCut(n1), "Wrong min cut (Node n1)."); |
239 check(!pre.minCut(n2), "Wrong min cut (Node n2)."); |
240 check(!pre.minCut(n2), "Wrong min cut (Node n2)."); |
240 check(!pre.minCut(t), "Wrong min cut (Node t)."); |
241 check(!pre.minCut(t), "Wrong min cut (Node t)."); |
241 } |
242 } |
300 max_flow.minCutMap(min_cut2); |
301 max_flow.minCutMap(min_cut2); |
301 min_cut_value = cutValue(g, min_cut2, cap); |
302 min_cut_value = cutValue(g, min_cut2, cap); |
302 |
303 |
303 check(max_flow.flowValue() == min_cut_value && |
304 check(max_flow.flowValue() == min_cut_value && |
304 min_cut_value == 2 * flow_value, |
305 min_cut_value == 2 * flow_value, |
305 "The max flow value or the min cut value was not doubled"); |
306 "The max flow value or the min cut value was not doubled."); |
306 |
|
307 |
307 |
308 max_flow.flowMap(flow); |
308 max_flow.flowMap(flow); |
309 |
309 |
310 NodeIt tmp1(g, s); |
310 NodeIt tmp1(g, s); |
311 ++tmp1; |
311 ++tmp1; |
320 |
320 |
321 max_flow.run(); |
321 max_flow.run(); |
322 |
322 |
323 CutMap min_cut3(g); |
323 CutMap min_cut3(g); |
324 max_flow.minCutMap(min_cut3); |
324 max_flow.minCutMap(min_cut3); |
325 min_cut_value=cutValue(g, min_cut3, cap); |
325 min_cut_value = cutValue(g, min_cut3, cap); |
326 |
326 |
327 check(max_flow.flowValue() == min_cut_value, |
327 check(max_flow.flowValue() == min_cut_value, |
328 "The max flow value or the min cut value is wrong."); |
328 "The max flow value or the min cut value is wrong."); |
329 } |
329 } |
330 |
330 |
377 // Check Preflow |
377 // Check Preflow |
378 typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<int> > PType1; |
378 typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<int> > PType1; |
379 typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2; |
379 typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2; |
380 checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >(); |
380 checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >(); |
381 checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(); |
381 checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(); |
382 initFlowTest(); |
382 |
|
383 checkInitPreflow(); |
383 |
384 |
384 // Check EdmondsKarp |
385 // Check EdmondsKarp |
385 typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<int> > EKType1; |
386 typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<int> > EKType1; |
386 typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2; |
387 typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2; |
387 checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >(); |
388 checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >(); |
388 checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(); |
389 checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(); |
389 |
390 |
390 initFlowTest(); |
|
391 |
|
392 return 0; |
391 return 0; |
393 } |
392 } |