Changeset 333:e0a80761dfd9 in lemon-0.x for src/work/marci/edmonds_karp_demo.cc
- Timestamp:
- 04/15/04 22:19:26 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@452
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/marci/edmonds_karp_demo.cc
r330 r333 10 10 //#include <graph_wrapper.h> 11 11 #include <preflow.h> 12 #include <for_each_macros.h> 12 13 13 14 using namespace hugo; … … 67 68 Graph::EdgeMap<int> cap(G); 68 69 readDimacsMaxFlow(std::cin, G, s, t, cap); 70 Timer ts; 71 Graph::EdgeMap<int> flow(G); //0 flow 72 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 73 pre_flow_test(G, s, t, cap, flow); 74 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 75 max_flow_test(G, s, t, cap, flow); 69 76 70 77 { 71 78 std::cout << "preflow ..." << std::endl; 72 Graph::EdgeMap<int> flow(G); //0 flow73 74 Timer ts;75 79 ts.reset(); 76 77 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 78 max_flow_test(G, s, t, cap, flow); 79 max_flow_test.run(); 80 // int i=0; 81 // while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { 82 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 83 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; 84 // } 85 // std::cout<<std::endl; 86 // ++i; 87 // } 88 89 // std::cout << "maximum flow: "<< std::endl; 90 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 91 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; 92 // } 93 // std::cout<<std::endl; 80 pre_flow_test.run(); 94 81 std::cout << "elapsed time: " << ts << std::endl; 95 // std::cout << "number of augmentation phases: " << i << std::endl; 96 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 82 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl; 97 83 } 98 84 99 85 { 100 86 std::cout << "physical blocking flow augmentation ..." << std::endl; 101 Graph::EdgeMap<int> flow(G); //0 flow 102 103 Timer ts; 87 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); 104 88 ts.reset(); 105 106 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >107 max_flow_test(G, s, t, cap, flow);108 89 int i=0; 109 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { 110 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 111 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; 112 // } 113 // std::cout<<std::endl; 114 ++i; 115 } 116 117 // std::cout << "maximum flow: "<< std::endl; 118 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 119 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; 120 // } 121 // std::cout<<std::endl; 90 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } 122 91 std::cout << "elapsed time: " << ts << std::endl; 123 92 std::cout << "number of augmentation phases: " << i << std::endl; … … 127 96 { 128 97 std::cout << "faster physical blocking flow augmentation ..." << std::endl; 129 Graph::EdgeMap<int> flow(G); //0 flow 130 131 Timer ts; 98 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); 132 99 ts.reset(); 133 134 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >135 max_flow_test(G, s, t, cap, flow);136 100 int i=0; 137 while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { 138 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 139 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; 140 // } 141 // std::cout<<std::endl; 142 ++i; 143 } 144 145 // std::cout << "maximum flow: "<< std::endl; 146 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 147 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; 148 // } 149 // std::cout<<std::endl; 101 while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; } 150 102 std::cout << "elapsed time: " << ts << std::endl; 151 103 std::cout << "number of augmentation phases: " << i << std::endl; … … 155 107 { 156 108 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; 157 Graph::EdgeMap<int> flow(G); //0 flow 158 159 Timer ts; 109 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); 160 110 ts.reset(); 161 162 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >163 max_flow_test(G, s, t, cap, flow);164 111 int i=0; 165 while (max_flow_test.augmentOnBlockingFlow2()) { 166 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 167 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; 168 // } 169 // std::cout<<std::endl; 170 ++i; 171 } 172 173 // std::cout << "maximum flow: "<< std::endl; 174 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 175 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; 176 // } 177 // std::cout<<std::endl; 112 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; } 178 113 std::cout << "elapsed time: " << ts << std::endl; 179 114 std::cout << "number of augmentation phases: " << i << std::endl; … … 183 118 { 184 119 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; 185 Graph::EdgeMap<int> flow(G); //0 flow 186 187 Timer ts; 120 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); 188 121 ts.reset(); 189 190 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >191 max_flow_test(G, s, t, cap, flow);192 122 int i=0; 193 while (max_flow_test.augmentOnShortestPath()) { 194 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 195 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; 196 // } 197 // std::cout<<std::endl; 198 ++i; 199 } 200 201 // std::cout << "maximum flow: "<< std::endl; 202 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 203 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; 204 // } 205 // std::cout<<std::endl; 123 while (max_flow_test.augmentOnShortestPath()) { ++i; } 206 124 std::cout << "elapsed time: " << ts << std::endl; 207 125 std::cout << "number of augmentation phases: " << i << std::endl;
Note: See TracChangeset
for help on using the changeset viewer.