Changeset 476:cfe550761745 in lemon0.x for src/work/marci/max_flow_demo.cc
 Timestamp:
 04/29/04 18:25:03 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@633
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/marci/max_flow_demo.cc
r475 r476 6 6 #include <smart_graph.h> 7 7 #include <dimacs.h> 8 //#include <edmonds_karp.h>9 8 #include <time_measure.h> 10 9 //#include <graph_wrapper.h> … … 71 70 Timer ts; 72 71 Graph::EdgeMap<int> flow(G); //0 flow 73 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 74 pre_flow_test(G, s, t, cap, flow/*, true*/); 75 // Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 76 // pre_flow_ize(G, s, t, cap, flow/*, false*/); 77 // PreflowRes<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 78 // pre_flow_res(G, s, t, cap, flow/*, true*/); 79 //MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 80 // max_flow_test(G, s, t, cap, flow); 72 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 73 max_flow_test(G, s, t, cap, flow); 81 74 82 75 { 83 76 std::cout << "preflow ..." << std::endl; 84 77 ts.reset(); 85 pre_flow_test.run();78 max_flow_test.run(); 86 79 std::cout << "elapsed time: " << ts << std::endl; 87 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;80 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 88 81 } 89 82 … … 92 85 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); 93 86 ts.reset(); 94 pre_flow_test.preflow(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);87 max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW); 95 88 std::cout << "elapsed time: " << ts << std::endl; 96 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;89 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 97 90 } 98 91 … … 111 104 ts.reset(); 112 105 int i=0; 113 while ( pre_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }106 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } 114 107 std::cout << "elapsed time: " << ts << std::endl; 115 108 std::cout << "number of augmentation phases: " << i << std::endl; 116 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;109 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 117 110 } 118 111 … … 133 126 ts.reset(); 134 127 int i=0; 135 while ( pre_flow_test.augmentOnBlockingFlow2()) { ++i; }128 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; } 136 129 std::cout << "elapsed time: " << ts << std::endl; 137 130 std::cout << "number of augmentation phases: " << i << std::endl; 138 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;131 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 139 132 } 140 133 … … 144 137 ts.reset(); 145 138 int i=0; 146 while ( pre_flow_test.augmentOnShortestPath()) { ++i; }139 while (max_flow_test.augmentOnShortestPath()) { ++i; } 147 140 std::cout << "elapsed time: " << ts << std::endl; 148 141 std::cout << "number of augmentation phases: " << i << std::endl; 149 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;142 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 150 143 } 151 144
Note: See TracChangeset
for help on using the changeset viewer.