Changeset 211:9222a9b8b323 in lemon0.x for src/work/jacint/preflow.cc
 Timestamp:
 03/19/04 23:16:05 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@306
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/jacint/preflow.cc
r113 r211 2 2 #include <fstream> 3 3 4 #include <list_graph.h h>5 #include <dimacs.h h>4 #include <list_graph.h> 5 #include <dimacs.h> 6 6 #include <preflow.h> 7 7 #include <time_measure.h> … … 12 12 // read_dimacs_demo < dimacs_max_flow_file 13 13 int main(int, char **) { 14 typedef ListGraph::Node It NodeIt;15 typedef ListGraph::E achEdgeIt EachEdgeIt;14 typedef ListGraph::Node Node; 15 typedef ListGraph::EdgeIt EdgeIt; 16 16 17 17 ListGraph G; 18 Node Its, t;18 Node s, t; 19 19 ListGraph::EdgeMap<int> cap(G); 20 20 readDimacsMaxFlow(std::cin, G, s, t, cap); … … 25 25 26 26 for ( int i=1; i!=11; ++i ) { 27 ListGraph::EdgeMap<int> flow(G); 27 28 double pre_time=currTime(); 28 preflow<ListGraph, int> max_flow_test(G, s, t, cap); 29 Preflow<ListGraph, int> max_flow_test(G, s, t, cap, flow); 30 max_flow_test.run(); 29 31 double post_time=currTime(); 30 32 if ( mintime > post_timepre_time ) mintime = post_timepre_time; 31 33 } 32 34 33 double pre_time=currTime();34 preflow<ListGraph, int> max_flow_test(G, s, t, cap);35 double post_time=currTime();36 35 ListGraph::EdgeMap<int> flow(G); 36 Preflow<ListGraph, int> max_flow_test(G, s, t, cap, flow); 37 max_flow_test.run(); 38 37 39 ListGraph::NodeMap<bool> cut(G); 38 40 max_flow_test.minCut(cut); 39 41 int min_cut_value=0; 40 for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { 42 EdgeIt e; 43 for(G.first(e); G.valid(e); G.next(e)) { 41 44 if (cut.get(G.tail(e)) && !cut.get(G.head(e))) min_cut_value+=cap.get(e); 42 45 } … … 45 48 max_flow_test.minMinCut(cut1); 46 49 int min_min_cut_value=0; 47 for( EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {50 for(G.first(e); G.valid(e); G.next(e)) { 48 51 if (cut.get(G.tail(e)) && !cut.get(G.head(e))) 49 52 min_min_cut_value+=cap.get(e); … … 53 56 max_flow_test.maxMinCut(cut2); 54 57 int max_min_cut_value=0; 55 for( EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {58 for(G.first(e); G.valid(e); G.next(e)) { 56 59 if (cut2.get(G.tail(e)) && !cut2.get(G.head(e))) 57 60 max_min_cut_value+=cap.get(e); … … 59 62 60 63 std::cout << "min time of 10 runs: " << mintime << " sec"<< std::endl; 61 std::cout << "phase 0: " << max_flow_test.timepre_time 62 << " sec"<< std::endl; 63 std::cout << "phase 1: " << post_timemax_flow_test.time 64 << " sec"<< std::endl; 65 std::cout << "flow value: "<< max_flow_test.maxFlow() << std::endl; 64 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 66 65 std::cout << "min cut value: "<< min_cut_value << std::endl; 67 66 std::cout << "min min cut value: "<< min_min_cut_value << std::endl;
Note: See TracChangeset
for help on using the changeset viewer.