Changeset 191:efea403c9595 in lemon0.x for src/work/edmonds_karp.h
 Timestamp:
 03/17/04 14:33:13 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@268
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/edmonds_karp.h
r175 r191 267 267 typedef typename AugGraph::Edge AugEdge; 268 268 269 //AugGraph res_graph;270 //typedef typename AugGraph::NodeMap<bool> ReachedMap;271 //typename AugGraph::NodeMap<AugEdge> pred;272 //typename AugGraph::NodeMap<Number> free;273 269 public: 274 270 MaxFlow(const Graph& _G, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) : 275 G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) //, 276 //res_graph(G, flow, capacity), pred(res_graph), free(res_graph) 277 { } 271 G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { } 278 272 bool augmentOnShortestPath() { 279 273 AugGraph res_graph(*G, *flow, *capacity); … … 291 285 //searching for augmenting path 292 286 while ( !res_bfs.finished() ) { 293 AugOutEdgeIt e= /*AugOutEdgeIt*/(res_bfs);287 AugOutEdgeIt e=res_bfs; 294 288 if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) { 295 289 Node v=res_graph.tail(e); … … 313 307 AugEdge e=pred.get(n); 314 308 res_graph.augment(e, augment_value); 315 //e.augment(augment_value);316 309 n=res_graph.tail(e); 317 310 } … … 321 314 } 322 315 323 template<typename MutableGraph> bool augmentOnBlockingFlow() { 324 325 // std::cout << "number of nodes: " << G>nodeNum() << std::endl; 326 // typename Graph::NodeIt n; 327 // G>first(n); 328 // for( ; G>valid(n); G>next(n)) { 329 // std::cout << G>id(n) << std::endl; 330 // } 331 // std::cout << "meg elek 1"; 332 333 // for(typename Graph::NodeIt n=G>template first<typename Graph::NodeIt>(); G>valid(n); G>next(n)) { 334 // std::cout << G>id(n) << std::endl; 335 // } 336 // std::cout << "meg elek 2"; 337 316 template<typename MutableGraph> bool augmentOnBlockingFlow() { 338 317 bool _augment=false; 339 318 … … 346 325 typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's 347 326 while ( !bfs.finished() ) { 348 AugOutEdgeIt e= /*AugOutEdgeIt*/(bfs);327 AugOutEdgeIt e=bfs; 349 328 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 350 329 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); … … 353 332 ++bfs; 354 333 } //computing distances from s in the residual graph 355 356 // for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {357 // std::cout << res_graph.id(n) << std::endl;358 // }359 // std::cout << "meg elek";360 334 361 335 MutableGraph F; … … 384 358 } 385 359 386 // for(typename MutableGraph::NodeIt n=F.template first<typename MutableGraph::NodeIt>(); F.valid(n); F.next(n)) {387 // std::cout << F.id(n) << std::endl;388 // }389 390 360 bool __augment=true; 391 361 … … 406 376 if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { 407 377 if (dfs.isBNodeNewlyReached()) { 408 // std::cout << "OutEdgeIt: " << dfs;409 // std::cout << " aNode: " << F.aNode(dfs);410 // std::cout << " bNode: " << F.bNode(dfs) << " ";411 412 378 typename MutableGraph::Node v=F.aNode(dfs); 413 379 typename MutableGraph::Node w=F.bNode(dfs); … … 419 385 } 420 386 if (w==tF) { 421 //std::cout << "AUGMENTATION"<<std::endl;422 387 __augment=true; 423 388 _augment=true; … … 437 402 typename MutableGraph::Edge e=pred.get(n); 438 403 res_graph.augment(original_edge.get(e), augment_value); 439 //original_edge.get(e).augment(augment_value);440 404 n=F.tail(e); 441 405 if (residual_capacity.get(e)==augment_value) … … 460 424 EAugGraph res_graph(*G, *flow, *capacity); 461 425 462 //std::cout << "meg jo1" << std::endl;463 464 426 //typedef typename EAugGraph::NodeMap<bool> ReachedMap; 465 427 BfsIterator4< … … 468 430 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph); 469 431 470 //std::cout << "meg jo2" << std::endl;471 472 432 bfs.pushAndSetReached(s); 473 //std::cout << "meg jo2.5" << std::endl; 474 475 //typename EAugGraph::NodeMap<int> dist(res_graph); //filled up with 0's 433 476 434 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>:: 477 435 NodeMap<int>& dist=res_graph.dist; 478 //std::cout << "meg jo2.6" << std::endl;479 436 480 437 while ( !bfs.finished() ) { 481 438 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; 482 // EAugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);483 //if (res_graph.valid(e)) {484 // std::cout<<"a:"<<res_graph.tail(e)<<"b:"<<res_graph.head(e)<<std::endl;485 //}486 439 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 487 440 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); 488 441 } 489 490 442 ++bfs; 491 443 } //computing distances from s in the residual graph 492 444 493 494 //std::cout << "meg jo3" << std::endl;495 496 // typedef typename EAugGraph::NodeIt EAugNodeIt;497 // for(EAugNodeIt n=res_graph.template first<EAugNodeIt>(); res_graph.valid(n); res_graph.next(n)) {498 // std::cout << "dist: " << dist.get(n) << std::endl;499 // }500 501 445 bool __augment=true; 502 446 503 447 while (__augment) { 504 // std::cout << "new iteration"<< std::endl;505 448 506 449 __augment=false; … … 520 463 if (res_graph.valid(EAugOutEdgeIt(dfs))) { 521 464 if (dfs.isBNodeNewlyReached()) { 522 // std::cout << "OutEdgeIt: " << dfs;523 // std::cout << " aNode: " << res_graph.aNode(dfs);524 // std::cout << " res cap: " << EAugOutEdgeIt(dfs).free();525 // std::cout << " bNode: " << res_graph.bNode(dfs) << " ";526 465 527 466 typename EAugGraph::Node v=res_graph.aNode(dfs); … … 529 468 530 469 pred.set(w, EAugOutEdgeIt(dfs)); 531 532 //std::cout << EAugOutEdgeIt(dfs).free() << std::endl;533 470 if (res_graph.valid(pred.get(v))) { 534 free.set(w, std::min(free.get(v), res_graph.free( /*EAugOutEdgeIt*/(dfs))));471 free.set(w, std::min(free.get(v), res_graph.free(dfs))); 535 472 } else { 536 free.set(w, res_graph.free( /*EAugOutEdgeIt*/(dfs)));473 free.set(w, res_graph.free(dfs)); 537 474 } 538 475 539 476 if (w==t) { 540 // std::cout << "t is reached, AUGMENTATION"<<std::endl;541 477 __augment=true; 542 478 _augment=true; … … 544 480 } 545 481 } else { 546 // std::cout << "<<DELETE ";547 // std::cout << " aNode: " << res_graph.aNode(dfs);548 // std::cout << " res cap: " << EAugOutEdgeIt(dfs).free();549 // std::cout << " bNode: " << res_graph.bNode(dfs) << " ";550 // std::cout << "DELETE>> ";551 552 482 res_graph.erase(dfs); 553 483 } … … 559 489 typename EAugGraph::Node n=t; 560 490 Number augment_value=free.get(t); 561 // std::cout << "av:" << augment_value << std::endl;562 491 while (res_graph.valid(pred.get(n))) { 563 492 EAugEdge e=pred.get(n); 564 493 res_graph.augment(e, augment_value); 565 //e.augment(augment_value);566 494 n=res_graph.tail(e); 567 495 if (res_graph.free(e)==0)
Note: See TracChangeset
for help on using the changeset viewer.