Changeset 100:f1de2ab64e1c in lemon-0.x for src/work
- Timestamp:
- 02/18/04 18:27:13 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@129
- Location:
- src/work
- Files:
-
- 3 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_copy-pre_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() { -
src/work/marci/edmonds_karp_demo.cc
r73 r100 20 20 readDimacsMaxFlow(std::cin, G, s, t, cap); 21 21 22 /* 23 double pre_time_copy=currTime(); 24 ListGraph F; 25 ListGraph::NodeMap<NodeIt> G_to_F(G); 26 typedef ListGraph::EachNodeIt EachNodeIt; 27 for(EachNodeIt n=G.first<EachNodeIt>(); n.valid(); ++n) { 28 G_to_F.set(n, F.addNode()); 29 } 30 for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { 31 F.addEdge(G_to_F.get(G.tail(e)), G_to_F.get(G.head(e))); 32 } 33 double post_time_copy=currTime(); 34 std::cout << "copy time: " << post_time_copy-pre_time_copy << " sec"<< std::endl; 35 */ 36 22 37 std::cout << "edmonds karp demo..." << std::endl; 23 38 ListGraph::EdgeMap<int> flow(G); //0 flow … … 25 40 double pre_time=currTime(); 26 41 MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap); 42 max_flow_test.augmentWithBlockingFlow(); 27 43 max_flow_test.run(); 28 44 double post_time=currTime(); -
src/work/marci/preflow_demo_jacint.cc
r89 r100 28 28 preflow_push_max_flow<ListGraph, int> max_flow_test(G, s, t, cap); 29 29 max_flow_test.run(); 30 ListGraph::NodeMap<bool> cut=max_flow_test.mincut(); 30 ListGraph::NodeMap<bool> cut(G); 31 max_flow_test.mincut(cut); 31 32 int cut_value=0; 32 33 for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { … … 51 52 preflow_push_hl<ListGraph, int> max_flow_test(G, s, t, cap); 52 53 max_flow_test.run(); 53 ListGraph::NodeMap<bool> cut=max_flow_test.mincut(); 54 ListGraph::NodeMap<bool> cut(G); 55 max_flow_test.mincut(cut); 54 56 int cut_value=0; 55 57 for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
Note: See TracChangeset
for help on using the changeset viewer.