Changeset 1228:45befc97b1bc in lemon for test/max_flow_test.cc
 Timestamp:
 02/28/13 23:44:35 (7 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 moved
Legend:
 Unmodified
 Added
 Removed

test/max_flow_test.cc
r1173 r1228 22 22 #include <lemon/smart_graph.h> 23 23 #include <lemon/preflow.h> 24 #include <lemon/edmonds_karp.h> 24 25 #include <lemon/concepts/digraph.h> 25 26 #include <lemon/concepts/maps.h> … … 65 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 132 void checkPreflowCompile() 68 133 { 69 typedef int V Type;134 typedef int Value; 70 135 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 136 typedef concepts::ReadMap<Digraph::Arc, Value> CapMap; 78 137 typedef Elevator<Digraph, Digraph::Node> Elev; 79 138 typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev; 80 139 81 140 Digraph g; 82 Node n; 83 Arc e; 141 Digraph::Node n; 84 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 144 typedef Preflow<Digraph, CapMap> 92 ::SetFlowMap<FlowMap> 93 ::SetElevator<Elev> 94 ::SetStandardElevator<LinkedElev> 95 ::Create PreflowType; 145 ::SetElevator<Elev> 146 ::SetStandardElevator<LinkedElev> 147 ::Create PreflowType; 96 148 PreflowType preflow_test(g, cap, n, n); 97 149 const PreflowType& const_preflow_test = preflow_test; … … 99 151 const PreflowType::Elevator& elev = const_preflow_test.elevator(); 100 152 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); 153 154 bool b = preflow_test.init(cap); 112 155 preflow_test.startFirstPhase(); 113 156 preflow_test.startSecondPhase(); 114 preflow_test.run();115 157 preflow_test.runMinCut(); 116 158 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, 159 ignore_unused_variable_warning(b); 160 } 161 162 // Checks the specific parts of EdmondsKarp's interface 163 void checkEdmondsKarpCompile() 164 { 165 typedef int Value; 166 typedef concepts::Digraph Digraph; 167 typedef concepts::ReadMap<Digraph::Arc, Value> CapMap; 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 188 const SmartDigraph::NodeMap<bool>& cut, 128 const SmartDigraph::ArcMap< int>& cap) {129 130 intc=0;189 const SmartDigraph::ArcMap<T>& cap) { 190 191 T c=0; 131 192 for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) { 132 193 if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e]; … … 135 196 } 136 197 198 template <typename T> 137 199 bool checkFlow(const SmartDigraph& g, 138 const SmartDigraph::ArcMap< int>& flow,139 const SmartDigraph::ArcMap< int>& cap,200 const SmartDigraph::ArcMap<T>& flow, 201 const SmartDigraph::ArcMap<T>& cap, 140 202 SmartDigraph::Node s, SmartDigraph::Node t) { 141 203 … … 146 208 for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) { 147 209 if (n == s  n == t) continue; 148 intsum = 0;210 T sum = 0; 149 211 for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) { 150 212 sum += flow[e]; … … 181 243 } 182 244 183 184 int main() { 185 245 template <typename MF, typename SF> 246 void checkMaxFlowAlg() { 186 247 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; 248 DIGRAPH_TYPEDEFS(Digraph); 249 250 typedef typename MF::Value Value; 251 typedef Digraph::ArcMap<Value> CapMap; 252 typedef CapMap FlowMap; 253 typedef BoolNodeMap CutMap; 196 254 197 255 Digraph g; … … 199 257 CapMap cap(g); 200 258 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),259 DigraphReader<Digraph>(g,input) 260 .arcMap("capacity", cap) 261 .node("source",s) 262 .node("target",t) 263 .run(); 264 265 MF max_flow(g, cap, s, t); 266 max_flow.run(); 267 268 check(checkFlow(g, max_flow.flowMap(), cap, s, t), 211 269 "The flow is not feasible."); 212 270 213 271 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.");272 max_flow.minCutMap(min_cut); 273 Value min_cut_value = cutValue(g, min_cut, cap); 274 275 check(max_flow.flowValue() == min_cut_value, 276 "The max flow value is not equal to the min cut value."); 219 277 220 278 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(); 279 for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e]; 280 281 Value flow_value = max_flow.flowValue(); 282 283 for (ArcIt e(g); e != INVALID; ++e) cap[e] = 2 * cap[e]; 284 max_flow.init(flow); 285 286 SF::startFirstPhase(max_flow); // start first phase of the algorithm 228 287 229 288 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,289 max_flow.minCutMap(min_cut1); 290 min_cut_value = cutValue(g, min_cut1, cap); 291 292 check(max_flow.flowValue() == min_cut_value && 293 min_cut_value == 2 * flow_value, 235 294 "The max flow value or the min cut value is wrong."); 236 295 237 preflow_test.startSecondPhase();238 239 check(checkFlow(g, preflow_test.flowMap(), cap, s, t),296 SF::startSecondPhase(max_flow); // start second phase of the algorithm 297 298 check(checkFlow(g, max_flow.flowMap(), cap, s, t), 240 299 "The flow is not feasible."); 241 300 242 301 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 werenot doubled");249 250 251 preflow_test.flowMap(flow);252 253 NodeIt tmp1(g, s);302 max_flow.minCutMap(min_cut2); 303 min_cut_value = cutValue(g, min_cut2, cap); 304 305 check(max_flow.flowValue() == min_cut_value && 306 min_cut_value == 2 * flow_value, 307 "The max flow value or the min cut value was not doubled"); 308 309 310 max_flow.flowMap(flow); 311 312 NodeIt tmp1(g, s); 254 313 ++tmp1; 255 if ( tmp1 != INVALID ) s=tmp1;256 257 NodeIt tmp2(g, t);314 if (tmp1 != INVALID) s = tmp1; 315 316 NodeIt tmp2(g, t); 258 317 ++tmp2; 259 if ( tmp2 != INVALID ) t=tmp2;260 261 preflow_test.source(s);262 preflow_test.target(t);263 264 preflow_test.run();318 if (tmp2 != INVALID) t = tmp2; 319 320 max_flow.source(s); 321 max_flow.target(t); 322 323 max_flow.run(); 265 324 266 325 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."); 326 max_flow.minCutMap(min_cut3); 327 min_cut_value=cutValue(g, min_cut3, cap); 328 329 check(max_flow.flowValue() == min_cut_value, 330 "The max flow value or the min cut value is wrong."); 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 392 initFlowTest();
Note: See TracChangeset
for help on using the changeset viewer.