Changeset 268:f4eb1ae59b50 in lemon0.x for src
 Timestamp:
 03/30/04 19:47:51 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@374
 Location:
 src/work
 Files:

 2 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; 
src/work/marci/edmonds_karp_demo.cc
r267 r268 122 122 } 123 123 124 { 125 //std::cout << "SmartGraph..." << std::endl; 126 typedef TrivGraphWrapper<const Graph> GW; 127 GW gw(G); 128 std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl; 129 GW::EdgeMap<int> flow(G); //0 flow 130 131 Timer ts; 132 ts.reset(); 133 134 typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW; 135 EMW cw(cap); 136 MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw); 137 int i=0; 138 while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { 139 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 140 // std::cout<<"("<<G.tail(e)<< ""<<flow.get(e)<<">"<<G.head(e)<<") "; 141 // } 142 // std::cout<<std::endl; 143 ++i; 144 } 145 146 // std::cout << "maximum flow: "<< std::endl; 147 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 148 // std::cout<<"("<<G.tail(e)<< ""<<flow.get(e)<<">"<<G.head(e)<<") "; 149 // } 150 // std::cout<<std::endl; 151 std::cout << "elapsed time: " << ts << std::endl; 152 std::cout << "number of augmentation phases: " << i << std::endl; 153 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 154 } 155 124 156 // { 125 // //std::cout << "SmartGraph..." << std::endl; 126 // std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl; 157 // std::cout << "edmonds karp demo (onthefly blocking flow augmentation)..." << std::endl; 127 158 // Graph::EdgeMap<int> flow(G); //0 flow 128 159 … … 132 163 // MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap); 133 164 // int i=0; 134 // while (max_flow_test.augmentOnBlockingFlow 1<MutableGraph>()) {165 // while (max_flow_test.augmentOnBlockingFlow2()) { 135 166 // // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 136 167 // // std::cout<<"("<<G.tail(e)<< ""<<flow.get(e)<<">"<<G.head(e)<<") "; … … 150 181 // } 151 182 152 // {153 // std::cout << "edmonds karp demo (onthefly blocking flow augmentation)..." << std::endl;154 // Graph::EdgeMap<int> flow(G); //0 flow155 156 // Timer ts;157 // ts.reset();158 159 // MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);160 // int i=0;161 // while (max_flow_test.augmentOnBlockingFlow2()) {162 // // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {163 // // std::cout<<"("<<G.tail(e)<< ""<<flow.get(e)<<">"<<G.head(e)<<") ";164 // // }165 // // std::cout<<std::endl;166 // ++i;167 // }168 169 // // std::cout << "maximum flow: "<< std::endl;170 // // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {171 // // std::cout<<"("<<G.tail(e)<< ""<<flow.get(e)<<">"<<G.head(e)<<") ";172 // // }173 // // std::cout<<std::endl;174 // std::cout << "elapsed time: " << ts << std::endl;175 // std::cout << "number of augmentation phases: " << i << std::endl;176 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;177 // }178 179 183 { 180 184 typedef TrivGraphWrapper<const Graph> GW;
Note: See TracChangeset
for help on using the changeset viewer.