Changes in / [1391:411819b8702c:1390:f0f15d07bf51] in lemon
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/preflow.h
r1385 r1270 477 477 /// flow to the given \c flowMap. The \c flowMap should contain a 478 478 /// flow or at least a preflow, i.e. at each node excluding the 479 /// source node the incoming flow should begreater or equal to the479 /// source node the incoming flow should greater or equal to the 480 480 /// outgoing flow. 481 481 /// \return \c false if the given \c flowMap is not a preflow. … … 496 496 excess = (*_flow)[e]; 497 497 } 498 if ( _tolerance.negative(excess)&& n != _source) return false;498 if (excess < 0 && n != _source) return false; 499 499 (*_excess)[n] = excess; 500 500 } … … 640 640 (*_excess)[n] = excess; 641 641 642 if ( _tolerance.nonZero(excess)) {642 if (excess != 0) { 643 643 if (new_level + 1 < _level>maxLevel()) { 644 644 _level>liftHighestActive(new_level + 1); … … 721 721 (*_excess)[n] = excess; 722 722 723 if ( _tolerance.nonZero(excess)) {723 if (excess != 0) { 724 724 if (new_level + 1 < _level>maxLevel()) { 725 725 _level>liftActiveOn(level, new_level + 1); … … 792 792 if (!reached[n]) { 793 793 _level>dirtyTopButOne(n); 794 } else if ( _tolerance.positive((*_excess)[n])&& _target != n) {794 } else if ((*_excess)[n] > 0 && _target != n) { 795 795 _level>activate(n); 796 796 } … … 853 853 (*_excess)[n] = excess; 854 854 855 if ( _tolerance.nonZero(excess)) {855 if (excess != 0) { 856 856 if (new_level + 1 < _level>maxLevel()) { 857 857 _level>liftHighestActive(new_level + 1); 
test/max_flow_test.cc
r1385 r1270 27 27 #include <lemon/lgf_reader.h> 28 28 #include <lemon/elevator.h> 29 #include <lemon/tolerance.h>30 29 31 30 using namespace lemon; … … 67 66 "target 8\n"; 68 67 69 char test_lgf_float[] =70 "@nodes\n"71 "label\n"72 "0\n"73 "1\n"74 "2\n"75 "3\n"76 "4\n"77 "5\n"78 "6\n"79 "7\n"80 "8\n"81 "9\n"82 "@arcs\n"83 " capacity\n"84 "0 1 0.1\n"85 "0 2 0.1\n"86 "0 3 0.1\n"87 "1 4 0.1\n"88 "2 4 0.1\n"89 "3 4 0.1\n"90 "4 5 0.3\n"91 "5 6 0.1\n"92 "5 7 0.1\n"93 "5 8 0.1\n"94 "6 9 0.1\n"95 "7 9 0.1\n"96 "8 9 0.1\n"97 "@attributes\n"98 "source 0\n"99 "target 9\n";100 68 101 69 // Checks the general interface of a max flow algorithm … … 198 166 typedef concepts::Digraph Digraph; 199 167 typedef concepts::ReadMap<Digraph::Arc, Value> CapMap; 168 typedef Elevator<Digraph, Digraph::Node> Elev; 169 typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev; 200 170 201 171 Digraph g; … … 215 185 216 186 template <typename T> 217 T cutValue (const SmartDigraph& g,218 const SmartDigraph::NodeMap<bool>& cut,219 const SmartDigraph::ArcMap<T>& cap) {220 221 T c =0;222 for (SmartDigraph::ArcIt e(g); e !=INVALID; ++e) {223 if (cut[g.source(e)] && !cut[g.target(e)]) c +=cap[e];187 T cutValue (const SmartDigraph& g, 188 const SmartDigraph::NodeMap<bool>& cut, 189 const SmartDigraph::ArcMap<T>& cap) { 190 191 T c=0; 192 for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) { 193 if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e]; 224 194 } 225 195 return c; … … 230 200 const SmartDigraph::ArcMap<T>& flow, 231 201 const SmartDigraph::ArcMap<T>& cap, 232 SmartDigraph::Node s, SmartDigraph::Node t, 233 const Tolerance<T>& tol) { 202 SmartDigraph::Node s, SmartDigraph::Node t) { 234 203 235 204 for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) { 236 if ( tol.negative(flow[e])  tol.less(cap[e], flow[e])) return false;205 if (flow[e] < 0  flow[e] > cap[e]) return false; 237 206 } 238 207 … … 246 215 sum = flow[e]; 247 216 } 248 if ( tol.nonZero(sum)) return false;217 if (sum != 0) return false; 249 218 } 250 219 return true; 251 220 } 252 221 253 void checkInitPreflow()222 void initFlowTest() 254 223 { 255 224 DIGRAPH_TYPEDEFS(SmartDigraph); 256 225 257 226 SmartDigraph g; 258 SmartDigraph::ArcMap<int> cap(g), 259 Node s = g.addNode(); Node t =g.addNode();260 Node n1 = g.addNode(); Node n2 =g.addNode();227 SmartDigraph::ArcMap<int> cap(g),iflow(g); 228 Node s=g.addNode(); Node t=g.addNode(); 229 Node n1=g.addNode(); Node n2=g.addNode(); 261 230 Arc a; 262 a = g.addArc(s, n1); cap[a] = 20; iflow[a] =20;263 a = g.addArc(n1, n2); cap[a] = 10; iflow[a] =0;264 a = g.addArc(n2, t); cap[a] = 20; iflow[a] =0;265 266 Preflow<SmartDigraph> pre(g, cap, s,t);231 a=g.addArc(s,n1); cap[a]=20; iflow[a]=20; 232 a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0; 233 a=g.addArc(n2,t); cap[a]=20; iflow[a]=0; 234 235 Preflow<SmartDigraph> pre(g,cap,s,t); 267 236 pre.init(iflow); 268 237 pre.startFirstPhase(); 269 270 check(pre.flowValue() == 10, "Incorrect max flow value."); 238 check(pre.flowValue() == 10, "The incorrect max flow value."); 271 239 check(pre.minCut(s), "Wrong min cut (Node s)."); 272 240 check(pre.minCut(n1), "Wrong min cut (Node n1)."); … … 276 244 277 245 template <typename MF, typename SF> 278 void checkMaxFlowAlg( const char *input_lgf, typename MF::Value expected) {246 void checkMaxFlowAlg() { 279 247 typedef SmartDigraph Digraph; 280 248 DIGRAPH_TYPEDEFS(Digraph); … … 285 253 typedef BoolNodeMap CutMap; 286 254 287 Tolerance<Value> tol;288 289 255 Digraph g; 290 256 Node s, t; 291 257 CapMap cap(g); 292 std::istringstream input( input_lgf);293 DigraphReader<Digraph>(g, 258 std::istringstream input(test_lgf); 259 DigraphReader<Digraph>(g,input) 294 260 .arcMap("capacity", cap) 295 .node("source", 296 .node("target", 261 .node("source",s) 262 .node("target",t) 297 263 .run(); 298 264 … … 300 266 max_flow.run(); 301 267 302 check(!tol.different(expected, max_flow.flowValue()), 303 "Incorrect max flow value."); 304 check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol), 268 check(checkFlow(g, max_flow.flowMap(), cap, s, t), 305 269 "The flow is not feasible."); 306 270 … … 309 273 Value min_cut_value = cutValue(g, min_cut, cap); 310 274 311 check( !tol.different(expected, min_cut_value),312 " Incorrectmin cut value.");275 check(max_flow.flowValue() == min_cut_value, 276 "The max flow value is not equal to the min cut value."); 313 277 314 278 FlowMap flow(g); 315 for (ArcIt e(g); e != INVALID; ++e) flow[e] = 13 * max_flow.flowMap()[e]; 316 for (ArcIt e(g); e != INVALID; ++e) cap[e] = 17 * cap[e]; 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]; 317 284 max_flow.init(flow); 318 285 … … 323 290 min_cut_value = cutValue(g, min_cut1, cap); 324 291 325 check(!tol.different(17 * expected, max_flow.flowValue()), 326 "Incorrect max flow value."); 327 check(!tol.different(17 * expected, min_cut_value), 328 "Incorrect min cut value."); 292 check(max_flow.flowValue() == min_cut_value && 293 min_cut_value == 2 * flow_value, 294 "The max flow value or the min cut value is wrong."); 329 295 330 296 SF::startSecondPhase(max_flow); // start second phase of the algorithm 331 297 332 check(checkFlow(g, max_flow.flowMap(), cap, s, t , tol),298 check(checkFlow(g, max_flow.flowMap(), cap, s, t), 333 299 "The flow is not feasible."); 334 300 … … 337 303 min_cut_value = cutValue(g, min_cut2, cap); 338 304 339 check( !tol.different(17 * expected, max_flow.flowValue()),340 "Incorrect max flow value.");341 check(!tol.different(17 * expected, min_cut_value),342 "Incorrect min cut value."); 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 343 309 344 310 max_flow.flowMap(flow); … … 359 325 CutMap min_cut3(g); 360 326 max_flow.minCutMap(min_cut3); 361 min_cut_value =cutValue(g, min_cut3, cap);362 363 check( !tol.different(max_flow.flowValue(), min_cut_value),327 min_cut_value=cutValue(g, min_cut3, cap); 328 329 check(max_flow.flowValue() == min_cut_value, 364 330 "The max flow value or the min cut value is wrong."); 365 331 } … … 414 380 typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<int> > PType1; 415 381 typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2; 416 typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<double> > PType3; 417 418 checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >(test_lgf, 13); 419 checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf, 13); 420 checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf, 13); 421 422 checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf_float, 0.3); 423 checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf_float, 0.3); 424 425 checkInitPreflow(); 382 checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >(); 383 checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(); 384 initFlowTest(); 426 385 427 386 // Check EdmondsKarp 428 387 typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<int> > EKType1; 429 388 typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2; 430 typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<double> > EKType3; 431 432 checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >(test_lgf, 13); 433 checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf, 13); 434 checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf, 13); 435 436 checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf_float, 0.3); 437 checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf_float, 0.3); 389 checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >(); 390 checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(); 391 392 initFlowTest(); 438 393 439 394 return 0;
Note: See TracChangeset
for help on using the changeset viewer.