Changeset 206:47f62d789fe7 in lemon0.x
 Timestamp:
 03/19/04 10:09:20 (16 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@298
 Location:
 src/work
 Files:

 3 edited
Legend:
 Unmodified
 Added
 Removed

src/work/edmonds_karp.h
r198 r206 357 357 } 358 358 } 359 360 bool __augment=true; 361 362 while (__augment) { 363 __augment=false; 364 //computing blocking flow with dfs 365 typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap; 366 DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F); 367 typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F); 368 pred.set(sF, typename MutableGraph::Edge(INVALID)); 369 //invalid iterators for sources 370 371 typename MutableGraph::NodeMap<Number> free(F); 372 373 dfs.pushAndSetReached(sF); 374 while (!dfs.finished()) { 375 ++dfs; 376 if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { 377 if (dfs.isBNodeNewlyReached()) { 378 typename MutableGraph::Node v=F.aNode(dfs); 379 typename MutableGraph::Node w=F.bNode(dfs); 380 pred.set(w, dfs); 381 if (F.valid(pred.get(v))) { 382 free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); 383 } else { 384 free.set(w, residual_capacity.get(dfs)); 385 } 386 if (w==tF) { 387 __augment=true; 388 _augment=true; 389 break; 390 } 391 392 } else { 393 F.erase(typename MutableGraph::OutEdgeIt(dfs)); 394 } 395 } 396 } 397 398 if (__augment) { 399 typename MutableGraph::Node n=tF; 400 Number augment_value=free.get(tF); 401 while (F.valid(pred.get(n))) { 402 typename MutableGraph::Edge e=pred.get(n); 403 res_graph.augment(original_edge.get(e), augment_value); 404 n=F.tail(e); 405 if (residual_capacity.get(e)==augment_value) 406 F.erase(e); 407 else 408 residual_capacity.set(e, residual_capacity.get(e)augment_value); 409 } 410 } 411 412 } 413 414 return _augment; 415 } 416 template<typename MutableGraph> bool augmentOnBlockingFlow1() { 417 bool _augment=false; 418 419 AugGraph res_graph(*G, *flow, *capacity); 420 421 //bfs for distances on the residual graph 422 typedef typename AugGraph::NodeMap<bool> ReachedMap; 423 BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph); 424 bfs.pushAndSetReached(s); 425 typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's 426 427 //F will contain the physical copy of the residual graph 428 //with the set of edges which areon shortest paths 429 MutableGraph F; 430 typename AugGraph::NodeMap<typename MutableGraph::Node> 431 res_graph_to_F(res_graph); 432 for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { 433 res_graph_to_F.set(n, F.addNode()); 434 } 435 typename MutableGraph::Node sF=res_graph_to_F.get(s); 436 typename MutableGraph::Node tF=res_graph_to_F.get(t); 437 typename MutableGraph::EdgeMap<AugEdge> original_edge(F); 438 typename MutableGraph::EdgeMap<Number> residual_capacity(F); 439 440 while ( !bfs.finished() ) { 441 AugOutEdgeIt e=bfs; 442 if (res_graph.valid(e)) { 443 if (bfs.isBNodeNewlyReached()) { 444 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); 445 typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); 446 original_edge.update(); 447 original_edge.set(f, e); 448 residual_capacity.update(); 449 residual_capacity.set(f, res_graph.free(e)); 450 } else { 451 if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) { 452 typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); 453 original_edge.update(); 454 original_edge.set(f, e); 455 residual_capacity.update(); 456 residual_capacity.set(f, res_graph.free(e)); 457 } 458 } 459 } 460 ++bfs; 461 } //computing distances from s in the residual graph 359 462 360 463 bool __augment=true; 
src/work/marci/dimacs.h
r180 r206 26 26 getline(is, str); 27 27 break; 28 // case 't': //type29 // getline(is, str);30 // break;31 28 case 'p': //problem definition 32 29 is >> problem >> n >> m; 
src/work/marci/edmonds_karp_demo.cc
r188 r206 35 35 typedef ListGraph MutableGraph; 36 36 37 //typedef SmartGraph Graph;38 typedef ListGraph Graph;37 typedef SmartGraph Graph; 38 //typedef ListGraph Graph; 39 39 typedef Graph::Node Node; 40 40 typedef Graph::EdgeIt EdgeIt; … … 115 115 116 116 { 117 std::cout << "SmartGraph..." << std::endl; 118 std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl; 119 Graph::EdgeMap<int> flow(G); //0 flow 120 121 Timer ts; 122 ts.reset(); 123 124 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap); 125 //max_flow_test.augmentWithBlockingFlow<Graph>(); 126 int i=0; 127 while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { 128 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 129 // std::cout<<"("<<G.tail(e)<< ""<<flow.get(e)<<">"<<G.head(e)<<") "; 130 // } 131 // std::cout<<std::endl; 132 ++i; 133 } 134 135 // std::cout << "maximum flow: "<< std::endl; 136 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 137 // std::cout<<"("<<G.tail(e)<< ""<<flow.get(e)<<">"<<G.head(e)<<") "; 138 // } 139 // std::cout<<std::endl; 140 std::cout << "elapsed time: " << ts << std::endl; 141 std::cout << "number of augmentation phases: " << i << std::endl; 142 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 143 } 144 145 { 117 146 std::cout << "edmonds karp demo (onthefly blocking flow augmentation)..." << std::endl; 118 147 Graph::EdgeMap<int> flow(G); //0 flow
Note: See TracChangeset
for help on using the changeset viewer.