Changeset 268:f4eb1ae59b50 in lemon-0.x for src/work/edmonds_karp.h
- Timestamp:
- 03/30/04 19:47:51 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@374
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/edmonds_karp.h
r266 r268 433 433 } 434 434 435 //template<typename MutableGraph> bool augmentOnBlockingFlow1() {436 //bool _augment=false;437 438 // AugGraph res_graph(*G, *flow, *capacity);439 440 ////bfs for distances on the residual graph441 //typedef typename AugGraph::NodeMap<bool> ReachedMap;442 //BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);443 //bfs.pushAndSetReached(s);444 //typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's445 446 ////F will contain the physical copy of the residual graph447 ////with the set of edges which areon shortest paths448 //MutableGraph F;449 //typename AugGraph::NodeMap<typename MutableGraph::Node>450 //res_graph_to_F(res_graph);451 //for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {452 //res_graph_to_F.set(n, F.addNode());453 //}454 //typename MutableGraph::Node sF=res_graph_to_F.get(s);455 //typename MutableGraph::Node tF=res_graph_to_F.get(t);456 //typename MutableGraph::EdgeMap<AugEdge> original_edge(F);457 //typename MutableGraph::EdgeMap<Number> residual_capacity(F);458 459 //while ( !bfs.finished() ) {460 //AugOutEdgeIt e=bfs;461 //if (res_graph.valid(e)) {462 //if (bfs.isBNodeNewlyReached()) {463 //dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);464 //typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));465 //original_edge.update();466 //original_edge.set(f, e);467 //residual_capacity.update();468 //residual_capacity.set(f, res_graph.free(e));469 //} else {470 //if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) {471 //typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));472 //original_edge.update();473 //original_edge.set(f, e);474 //residual_capacity.update();475 //residual_capacity.set(f, res_graph.free(e));476 //}477 //}478 //}479 //++bfs;480 //} //computing distances from s in the residual graph481 482 //bool __augment=true;483 484 //while (__augment) {485 //__augment=false;486 ////computing blocking flow with dfs487 //typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;488 //DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);489 //typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);490 //pred.set(sF, typename MutableGraph::Edge(INVALID));491 ////invalid iterators for sources492 493 //typename MutableGraph::NodeMap<Number> free(F);494 495 //dfs.pushAndSetReached(sF);496 //while (!dfs.finished()) {497 //++dfs;498 //if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {499 //if (dfs.isBNodeNewlyReached()) {500 //typename MutableGraph::Node v=F.aNode(dfs);501 //typename MutableGraph::Node w=F.bNode(dfs);502 //pred.set(w, dfs);503 //if (F.valid(pred.get(v))) {504 //free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));505 //} else {506 //free.set(w, residual_capacity.get(dfs));507 //}508 //if (w==tF) {509 //__augment=true;510 //_augment=true;511 //break;512 //}435 template<typename MutableGraph> bool augmentOnBlockingFlow1() { 436 bool _augment=false; 437 438 AugGraph res_graph(gw, *flow, *capacity); 439 440 //bfs for distances on the residual graph 441 typedef typename AugGraph::NodeMap<bool> ReachedMap; 442 BfsIterator5< AugGraph, ReachedMap > bfs(res_graph); 443 bfs.pushAndSetReached(s); 444 typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's 445 446 //F will contain the physical copy of the residual graph 447 //with the set of edges which areon shortest paths 448 MutableGraph F; 449 typename AugGraph::NodeMap<typename MutableGraph::Node> 450 res_graph_to_F(res_graph); 451 for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { 452 res_graph_to_F.set(n, F.addNode()); 453 } 454 typename MutableGraph::Node sF=res_graph_to_F.get(s); 455 typename MutableGraph::Node tF=res_graph_to_F.get(t); 456 typename MutableGraph::EdgeMap<AugEdge> original_edge(F); 457 typename MutableGraph::EdgeMap<Number> residual_capacity(F); 458 459 while ( !bfs.finished() ) { 460 AugOutEdgeIt e=bfs; 461 if (res_graph.valid(e)) { 462 if (bfs.isBNodeNewlyReached()) { 463 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); 464 typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); 465 original_edge.update(); 466 original_edge.set(f, e); 467 residual_capacity.update(); 468 residual_capacity.set(f, res_graph.free(e)); 469 } else { 470 if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) { 471 typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); 472 original_edge.update(); 473 original_edge.set(f, e); 474 residual_capacity.update(); 475 residual_capacity.set(f, res_graph.free(e)); 476 } 477 } 478 } 479 ++bfs; 480 } //computing distances from s in the residual graph 481 482 bool __augment=true; 483 484 while (__augment) { 485 __augment=false; 486 //computing blocking flow with dfs 487 typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap; 488 DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F); 489 typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F); 490 pred.set(sF, typename MutableGraph::Edge(INVALID)); 491 //invalid iterators for sources 492 493 typename MutableGraph::NodeMap<Number> free(F); 494 495 dfs.pushAndSetReached(sF); 496 while (!dfs.finished()) { 497 ++dfs; 498 if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { 499 if (dfs.isBNodeNewlyReached()) { 500 typename MutableGraph::Node v=F.aNode(dfs); 501 typename MutableGraph::Node w=F.bNode(dfs); 502 pred.set(w, dfs); 503 if (F.valid(pred.get(v))) { 504 free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); 505 } else { 506 free.set(w, residual_capacity.get(dfs)); 507 } 508 if (w==tF) { 509 __augment=true; 510 _augment=true; 511 break; 512 } 513 513 514 //} else {515 //F.erase(typename MutableGraph::OutEdgeIt(dfs));516 //}517 //}518 //}519 520 //if (__augment) {521 //typename MutableGraph::Node n=tF;522 //Number augment_value=free.get(tF);523 //while (F.valid(pred.get(n))) {524 //typename MutableGraph::Edge e=pred.get(n);525 //res_graph.augment(original_edge.get(e), augment_value);526 //n=F.tail(e);527 //if (residual_capacity.get(e)==augment_value)528 //F.erase(e);529 //else530 //residual_capacity.set(e, residual_capacity.get(e)-augment_value);531 //}532 //}514 } else { 515 F.erase(typename MutableGraph::OutEdgeIt(dfs)); 516 } 517 } 518 } 519 520 if (__augment) { 521 typename MutableGraph::Node n=tF; 522 Number augment_value=free.get(tF); 523 while (F.valid(pred.get(n))) { 524 typename MutableGraph::Edge e=pred.get(n); 525 res_graph.augment(original_edge.get(e), augment_value); 526 n=F.tail(e); 527 if (residual_capacity.get(e)==augment_value) 528 F.erase(e); 529 else 530 residual_capacity.set(e, residual_capacity.get(e)-augment_value); 531 } 532 } 533 533 534 //}534 } 535 535 536 // return _augment; 537 // } 536 return _augment; 537 } 538 538 539 // bool augmentOnBlockingFlow2() { 539 540 // bool _augment=false;
Note: See TracChangeset
for help on using the changeset viewer.