Changeset 168:27fbd1559fb7 in lemon0.x for src/work/edmonds_karp.hh
 Timestamp:
 03/11/04 15:15:07 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@239
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/edmonds_karp.hh
r155 r168 280 280 281 281 typedef typename AugGraph::NodeMap<bool> ReachedMap; 282 BfsIterator5< AugGraph, AugOutEdgeIt,ReachedMap > res_bfs(res_graph);282 BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph); 283 283 res_bfs.pushAndSetReached(s); 284 284 … … 297 297 pred.set(w, e); 298 298 if (res_graph.valid(pred.get(v))) { 299 free.set(w, std::min(free.get(v), e.free()));299 free.set(w, std::min(free.get(v), res_graph.free(e))); 300 300 } else { 301 free.set(w, e.free());301 free.set(w, res_graph.free(e)); 302 302 } 303 303 if (res_graph.head(e)==t) { _augment=true; break; } … … 312 312 while (res_graph.valid(pred.get(n))) { 313 313 AugEdgeIt e=pred.get(n); 314 e.augment(augment_value); 314 res_graph.augment(e, augment_value); 315 //e.augment(augment_value); 315 316 n=res_graph.tail(e); 316 317 } … … 359 360 original_edge.set(f, e); 360 361 residual_capacity.update(); 361 residual_capacity.set(f, e.free());362 residual_capacity.set(f, res_graph.free(e)); 362 363 } 363 364 } … … 377 378 ++dfs; 378 379 if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { 379 //std::cout << "OutEdgeIt: " << dfs; 380 //std::cout << " aNode: " << F.aNode(dfs); 381 //std::cout << " bNode: " << F.bNode(dfs) << " "; 380 if (dfs.isBNodeNewlyReached()) { 381 // std::cout << "OutEdgeIt: " << dfs; 382 // std::cout << " aNode: " << F.aNode(dfs); 383 // std::cout << " bNode: " << F.bNode(dfs) << " "; 382 384 383 typename MutableGraph::NodeIt v=F.aNode(dfs); 384 typename MutableGraph::NodeIt w=F.bNode(dfs); 385 pred.set(w, dfs); 386 if (F.valid(pred.get(v))) { 387 free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); 385 typename MutableGraph::NodeIt v=F.aNode(dfs); 386 typename MutableGraph::NodeIt w=F.bNode(dfs); 387 pred.set(w, dfs); 388 if (F.valid(pred.get(v))) { 389 free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); 390 } else { 391 free.set(w, residual_capacity.get(dfs)); 392 } 393 if (w==tF) { 394 //std::cout << "AUGMENTATION"<<std::endl; 395 __augment=true; 396 _augment=true; 397 break; 398 } 399 388 400 } else { 389 free.set(w, residual_capacity.get(dfs)/*original_edge.get(dfs).free()*/);390 }391 if (w==tF) {392 //std::cout << "AUGMENTATION"<<std::endl;393 __augment=true;394 _augment=true;395 break;396 }397 } else {398 //std::cout << "OutEdgeIt: " << "invalid";399 //std::cout << " aNode: " << dfs.aNode();400 //std::cout << " bNode: " << "invalid" << " ";401 }402 if (dfs.isBNodeNewlyReached()) {403 //std::cout << "bNodeIsNewlyReached ";404 } else {405 //std::cout << "bNodeIsNotNewlyReached ";406 if (typename MutableGraph::OutEdgeIt(dfs).valid()) {407 //std::cout << "DELETE ";408 401 F.erase(typename MutableGraph::OutEdgeIt(dfs)); 409 402 } 410 403 } 411 //if (dfs.isANodeExamined()) {412 //std::cout << "aNodeIsExamined ";413 //} else {414 //std::cout << "aNodeIsNotExamined ";415 //}416 //std::cout<<std::endl;417 404 } 418 405 … … 422 409 while (F.valid(pred.get(n))) { 423 410 typename MutableGraph::EdgeIt e=pred.get(n); 424 original_edge.get(e).augment(augment_value); 411 res_graph.augment(original_edge.get(e), augment_value); 412 //original_edge.get(e).augment(augment_value); 425 413 n=F.tail(e); 426 414 if (residual_capacity.get(e)==augment_value) … … 428 416 else 429 417 residual_capacity.set(e, residual_capacity.get(e)augment_value); 418 } 419 } 420 421 } 422 423 return _augment; 424 } 425 bool augmentOnBlockingFlow2() { 426 bool _augment=false; 427 428 //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph; 429 typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph; 430 typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; 431 typedef typename EAugGraph::EdgeIt EAugEdgeIt; 432 433 EAugGraph res_graph(*G, *flow, *capacity); 434 435 //std::cout << "meg jo1" << std::endl; 436 437 //typedef typename EAugGraph::NodeMap<bool> ReachedMap; 438 BfsIterator4< 439 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, 440 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt, 441 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph); 442 443 //std::cout << "meg jo2" << std::endl; 444 445 bfs.pushAndSetReached(s); 446 //std::cout << "meg jo2.5" << std::endl; 447 448 //typename EAugGraph::NodeMap<int> dist(res_graph); //filled up with 0's 449 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>:: 450 NodeMap<int>& dist=res_graph.dist; 451 //std::cout << "meg jo2.6" << std::endl; 452 453 while ( !bfs.finished() ) { 454 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; 455 // EAugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); 456 //if (res_graph.valid(e)) { 457 // std::cout<<"a:"<<res_graph.tail(e)<<"b:"<<res_graph.head(e)<<std::endl; 458 //} 459 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 460 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); 461 } 462 463 ++bfs; 464 } //computing distances from s in the residual graph 465 466 467 //std::cout << "meg jo3" << std::endl; 468 469 // typedef typename EAugGraph::EachNodeIt EAugEachNodeIt; 470 // for(EAugEachNodeIt n=res_graph.template first<EAugEachNodeIt>(); res_graph.valid(n); res_graph.next(n)) { 471 // std::cout << "dist: " << dist.get(n) << std::endl; 472 // } 473 474 bool __augment=true; 475 476 while (__augment) { 477 // std::cout << "new iteration"<< std::endl; 478 479 __augment=false; 480 //computing blocking flow with dfs 481 typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap; 482 DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap > 483 dfs(res_graph); 484 typename EAugGraph::NodeMap<EAugEdgeIt> pred(res_graph); //invalid iterators 485 typename EAugGraph::NodeMap<Number> free(res_graph); 486 487 dfs.pushAndSetReached(s); 488 while (!dfs.finished()) { 489 ++dfs; 490 if (res_graph.valid(EAugOutEdgeIt(dfs))) { 491 if (dfs.isBNodeNewlyReached()) { 492 // std::cout << "OutEdgeIt: " << dfs; 493 // std::cout << " aNode: " << res_graph.aNode(dfs); 494 // std::cout << " res cap: " << EAugOutEdgeIt(dfs).free(); 495 // std::cout << " bNode: " << res_graph.bNode(dfs) << " "; 496 497 typename EAugGraph::NodeIt v=res_graph.aNode(dfs); 498 typename EAugGraph::NodeIt w=res_graph.bNode(dfs); 499 500 pred.set(w, EAugOutEdgeIt(dfs)); 501 502 //std::cout << EAugOutEdgeIt(dfs).free() << std::endl; 503 if (res_graph.valid(pred.get(v))) { 504 free.set(w, std::min(free.get(v), res_graph.free(/*EAugOutEdgeIt*/(dfs)))); 505 } else { 506 free.set(w, res_graph.free(/*EAugOutEdgeIt*/(dfs))); 507 } 508 509 if (w==t) { 510 // std::cout << "t is reached, AUGMENTATION"<<std::endl; 511 __augment=true; 512 _augment=true; 513 break; 514 } 515 } else { 516 // std::cout << "<<DELETE "; 517 // std::cout << " aNode: " << res_graph.aNode(dfs); 518 // std::cout << " res cap: " << EAugOutEdgeIt(dfs).free(); 519 // std::cout << " bNode: " << res_graph.bNode(dfs) << " "; 520 // std::cout << "DELETE>> "; 521 522 res_graph.erase(dfs); 523 } 524 } 525 526 } 527 528 if (__augment) { 529 typename EAugGraph::NodeIt n=t; 530 Number augment_value=free.get(t); 531 // std::cout << "av:" << augment_value << std::endl; 532 while (res_graph.valid(pred.get(n))) { 533 EAugEdgeIt e=pred.get(n); 534 res_graph.augment(e, augment_value); 535 //e.augment(augment_value); 536 n=res_graph.tail(e); 537 if (res_graph.free(e)==0) 538 res_graph.erase(e); 430 539 } 431 540 }
Note: See TracChangeset
for help on using the changeset viewer.