Changeset 100:f1de2ab64e1c in lemon0.x for src/work/edmonds_karp.hh
 Timestamp:
 02/18/04 18:27:13 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@129
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/edmonds_karp.hh
r94 r100 7 7 8 8 #include <bfs_iterator.hh> 9 #include <time_measure.h> 9 10 10 11 namespace marci { … … 444 445 return _augment; 445 446 } 447 bool augmentWithBlockingFlow() { 448 BfsIterator4< Graph, OutEdgeIt, typename Graph::NodeMap<bool> > bfs(G); 449 bfs.pushAndSetReached(s); 450 typename Graph::NodeMap<int> dist(G); //filled up with 0's 451 while ( !bfs.finished() ) { 452 OutEdgeIt e=OutEdgeIt(bfs); 453 if (e.valid() && bfs.isBNodeNewlyReached()) { 454 dist.set(G.head(e), dist.get(G.tail(e))+1); 455 //NodeIt v=res_graph.tail(e); 456 //NodeIt w=res_graph.head(e); 457 //pred.set(w, e); 458 //if (pred.get(v).valid()) { 459 // free.set(w, std::min(free.get(v), e.free())); 460 //} else { 461 // free.set(w, e.free()); 462 //} 463 //if (res_graph.head(e)==t) { _augment=true; break; } 464 } 465 466 ++bfs; 467 } //end of searching augmenting path 468 469 double pre_time_copy=currTime(); 470 typedef Graph MutableGraph; 471 MutableGraph F; 472 typename Graph::NodeMap<NodeIt> G_to_F(G); 473 for(typename Graph::EachNodeIt n=G.template first<typename Graph::EachNodeIt>(); n.valid(); ++n) { 474 G_to_F.set(n, F.addNode()); 475 } 476 for(typename Graph::EachEdgeIt e=G.template first<typename Graph::EachEdgeIt>(); e.valid(); ++e) { 477 if (dist.get(G.head(e))==dist.get(G.tail(e))+1) { 478 F.addEdge(G_to_F.get(G.tail(e)), G_to_F.get(G.head(e))); 479 } 480 } 481 double post_time_copy=currTime(); 482 std::cout << "copy time: " << post_time_copypre_time_copy << " sec"<< std::endl; 483 484 return 0; 485 } 446 486 void run() { 447 while (augment()) { } 487 //int num_of_augmentations=0; 488 while (augment()) { 489 //std::cout << ++num_of_augmentations << " "; 490 //std::cout<<std::endl; 491 } 448 492 } 449 493 Number flowValue() {
Note: See TracChangeset
for help on using the changeset viewer.