[174] | 1 | // -*- c++ -*- |
---|
| 2 | #include <iostream> |
---|
| 3 | #include <fstream> |
---|
| 4 | #include <string> |
---|
| 5 | |
---|
[642] | 6 | #include <sage_graph.h> |
---|
[921] | 7 | #include <lemon/list_graph.h> |
---|
| 8 | #include <lemon/smart_graph.h> |
---|
| 9 | #include <lemon/dimacs.h> |
---|
| 10 | #include <lemon/max_flow.h> |
---|
[762] | 11 | #include <augmenting_flow.h> |
---|
[921] | 12 | #include <lemon/time_measure.h> |
---|
[762] | 13 | #include <for_each_macros.h> |
---|
[174] | 14 | |
---|
[921] | 15 | using namespace lemon; |
---|
[174] | 16 | |
---|
| 17 | // Use a DIMACS max flow file as stdin. |
---|
| 18 | // read_dimacs_demo dimacs_max_flow_file |
---|
| 19 | |
---|
| 20 | int main(int, char** argv) { |
---|
| 21 | |
---|
| 22 | std::string in=argv[1]; |
---|
[642] | 23 | typedef SageGraph MutableGraph; |
---|
[174] | 24 | |
---|
| 25 | { |
---|
[642] | 26 | typedef SageGraph Graph; |
---|
[174] | 27 | typedef Graph::Node Node; |
---|
| 28 | typedef Graph::EdgeIt EdgeIt; |
---|
| 29 | |
---|
[577] | 30 | Graph g; |
---|
[174] | 31 | Node s, t; |
---|
[577] | 32 | Graph::EdgeMap<int> cap(g); |
---|
[174] | 33 | std::ifstream ins(in.c_str()); |
---|
[577] | 34 | //readDimacsMaxFlow(ins, g, s, t, cap); |
---|
| 35 | readDimacs(ins, g, cap, s, t); |
---|
[174] | 36 | |
---|
[334] | 37 | Timer ts; |
---|
[577] | 38 | Graph::EdgeMap<int> flow(g); //0 flow |
---|
[334] | 39 | MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
---|
[577] | 40 | max_flow_test(g, s, t, cap, flow/*, true*/); |
---|
[762] | 41 | AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
---|
| 42 | augmenting_flow_test(g, s, t, cap, flow/*, true*/); |
---|
[334] | 43 | |
---|
[642] | 44 | std::cout << "SageGraph ..." << std::endl; |
---|
[334] | 45 | |
---|
[174] | 46 | { |
---|
[334] | 47 | std::cout << "preflow ..." << std::endl; |
---|
| 48 | ts.reset(); |
---|
[476] | 49 | max_flow_test.run(); |
---|
[334] | 50 | std::cout << "elapsed time: " << ts << std::endl; |
---|
[476] | 51 | std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
---|
[334] | 52 | } |
---|
[174] | 53 | |
---|
[334] | 54 | { |
---|
| 55 | std::cout << "physical blocking flow augmentation ..." << std::endl; |
---|
[777] | 56 | for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); |
---|
[174] | 57 | ts.reset(); |
---|
| 58 | int i=0; |
---|
[762] | 59 | while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } |
---|
[174] | 60 | std::cout << "elapsed time: " << ts << std::endl; |
---|
| 61 | std::cout << "number of augmentation phases: " << i << std::endl; |
---|
[762] | 62 | std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
---|
[174] | 63 | } |
---|
| 64 | |
---|
[476] | 65 | // { |
---|
| 66 | // std::cout << "faster physical blocking flow augmentation ..." << std::endl; |
---|
[577] | 67 | // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
---|
[476] | 68 | // ts.reset(); |
---|
| 69 | // int i=0; |
---|
| 70 | // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; } |
---|
| 71 | // std::cout << "elapsed time: " << ts << std::endl; |
---|
| 72 | // std::cout << "number of augmentation phases: " << i << std::endl; |
---|
| 73 | // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
---|
| 74 | // } |
---|
[174] | 75 | |
---|
| 76 | { |
---|
[334] | 77 | std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; |
---|
[777] | 78 | for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); |
---|
[334] | 79 | ts.reset(); |
---|
| 80 | int i=0; |
---|
[762] | 81 | while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; } |
---|
[334] | 82 | std::cout << "elapsed time: " << ts << std::endl; |
---|
| 83 | std::cout << "number of augmentation phases: " << i << std::endl; |
---|
[762] | 84 | std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
---|
[334] | 85 | } |
---|
[174] | 86 | |
---|
[334] | 87 | { |
---|
| 88 | std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
---|
[777] | 89 | for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); |
---|
[174] | 90 | ts.reset(); |
---|
| 91 | int i=0; |
---|
[762] | 92 | while (augmenting_flow_test.augmentOnShortestPath()) { ++i; } |
---|
[174] | 93 | std::cout << "elapsed time: " << ts << std::endl; |
---|
| 94 | std::cout << "number of augmentation phases: " << i << std::endl; |
---|
[762] | 95 | std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
---|
[174] | 96 | } |
---|
| 97 | } |
---|
| 98 | |
---|
| 99 | { |
---|
| 100 | typedef SmartGraph Graph; |
---|
| 101 | typedef Graph::Node Node; |
---|
| 102 | typedef Graph::EdgeIt EdgeIt; |
---|
| 103 | |
---|
[577] | 104 | Graph g; |
---|
[174] | 105 | Node s, t; |
---|
[577] | 106 | Graph::EdgeMap<int> cap(g); |
---|
[174] | 107 | std::ifstream ins(in.c_str()); |
---|
[577] | 108 | //readDimacsMaxFlow(ins, g, s, t, cap); |
---|
| 109 | readDimacs(ins, g, cap, s, t); |
---|
[174] | 110 | |
---|
[334] | 111 | Timer ts; |
---|
[577] | 112 | Graph::EdgeMap<int> flow(g); //0 flow |
---|
[334] | 113 | MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
---|
[577] | 114 | max_flow_test(g, s, t, cap, flow/*, true*/); |
---|
[762] | 115 | AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
---|
| 116 | augmenting_flow_test(g, s, t, cap, flow/*, true*/); |
---|
[476] | 117 | // MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
---|
[577] | 118 | // max_flow_test(g, s, t, cap, flow); |
---|
[334] | 119 | |
---|
[642] | 120 | std::cout << "SmartGraph ..." << std::endl; |
---|
[334] | 121 | |
---|
[174] | 122 | { |
---|
[334] | 123 | std::cout << "preflow ..." << std::endl; |
---|
[777] | 124 | for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); |
---|
[334] | 125 | ts.reset(); |
---|
[476] | 126 | max_flow_test.run(); |
---|
[334] | 127 | std::cout << "elapsed time: " << ts << std::endl; |
---|
[476] | 128 | std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
---|
[334] | 129 | } |
---|
[174] | 130 | |
---|
[334] | 131 | { |
---|
| 132 | std::cout << "physical blocking flow augmentation ..." << std::endl; |
---|
[777] | 133 | for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); |
---|
[174] | 134 | ts.reset(); |
---|
| 135 | int i=0; |
---|
[762] | 136 | while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } |
---|
[174] | 137 | std::cout << "elapsed time: " << ts << std::endl; |
---|
| 138 | std::cout << "number of augmentation phases: " << i << std::endl; |
---|
[762] | 139 | std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
---|
[174] | 140 | } |
---|
| 141 | |
---|
[476] | 142 | // { |
---|
| 143 | // std::cout << "faster physical blocking flow augmentation ..." << std::endl; |
---|
[577] | 144 | // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
---|
[476] | 145 | // ts.reset(); |
---|
| 146 | // int i=0; |
---|
| 147 | // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; } |
---|
| 148 | // std::cout << "elapsed time: " << ts << std::endl; |
---|
| 149 | // std::cout << "number of augmentation phases: " << i << std::endl; |
---|
| 150 | // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
---|
| 151 | // } |
---|
[174] | 152 | |
---|
| 153 | { |
---|
[334] | 154 | std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; |
---|
[777] | 155 | for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); |
---|
[334] | 156 | ts.reset(); |
---|
| 157 | int i=0; |
---|
[762] | 158 | while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; } |
---|
[334] | 159 | std::cout << "elapsed time: " << ts << std::endl; |
---|
| 160 | std::cout << "number of augmentation phases: " << i << std::endl; |
---|
[762] | 161 | std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
---|
[334] | 162 | } |
---|
[174] | 163 | |
---|
[334] | 164 | { |
---|
| 165 | std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
---|
[777] | 166 | for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); |
---|
[174] | 167 | ts.reset(); |
---|
| 168 | int i=0; |
---|
[762] | 169 | while (augmenting_flow_test.augmentOnShortestPath()) { ++i; } |
---|
[174] | 170 | std::cout << "elapsed time: " << ts << std::endl; |
---|
| 171 | std::cout << "number of augmentation phases: " << i << std::endl; |
---|
[762] | 172 | std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
---|
[174] | 173 | } |
---|
| 174 | } |
---|
| 175 | |
---|
[642] | 176 | { |
---|
| 177 | typedef ListGraph Graph; |
---|
| 178 | typedef Graph::Node Node; |
---|
| 179 | typedef Graph::EdgeIt EdgeIt; |
---|
| 180 | |
---|
| 181 | Graph g; |
---|
| 182 | Node s, t; |
---|
| 183 | Graph::EdgeMap<int> cap(g); |
---|
| 184 | std::ifstream ins(in.c_str()); |
---|
| 185 | //readDimacsMaxFlow(ins, g, s, t, cap); |
---|
| 186 | readDimacs(ins, g, cap, s, t); |
---|
| 187 | |
---|
| 188 | Timer ts; |
---|
| 189 | Graph::EdgeMap<int> flow(g); //0 flow |
---|
| 190 | MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
---|
| 191 | max_flow_test(g, s, t, cap, flow/*, true*/); |
---|
[762] | 192 | AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
---|
| 193 | augmenting_flow_test(g, s, t, cap, flow/*, true*/); |
---|
[642] | 194 | // MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
---|
| 195 | // max_flow_test(g, s, t, cap, flow); |
---|
| 196 | |
---|
| 197 | std::cout << "ListGraph ..." << std::endl; |
---|
| 198 | |
---|
| 199 | { |
---|
| 200 | std::cout << "preflow ..." << std::endl; |
---|
[777] | 201 | for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); |
---|
[642] | 202 | ts.reset(); |
---|
| 203 | max_flow_test.run(); |
---|
| 204 | std::cout << "elapsed time: " << ts << std::endl; |
---|
| 205 | std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
---|
| 206 | } |
---|
| 207 | |
---|
| 208 | { |
---|
| 209 | std::cout << "physical blocking flow augmentation ..." << std::endl; |
---|
[777] | 210 | for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); |
---|
[642] | 211 | ts.reset(); |
---|
| 212 | int i=0; |
---|
[762] | 213 | while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } |
---|
[642] | 214 | std::cout << "elapsed time: " << ts << std::endl; |
---|
| 215 | std::cout << "number of augmentation phases: " << i << std::endl; |
---|
[762] | 216 | std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
---|
[642] | 217 | } |
---|
| 218 | |
---|
| 219 | // { |
---|
| 220 | // std::cout << "faster physical blocking flow augmentation ..." << std::endl; |
---|
| 221 | // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
---|
| 222 | // ts.reset(); |
---|
| 223 | // int i=0; |
---|
| 224 | // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; } |
---|
| 225 | // std::cout << "elapsed time: " << ts << std::endl; |
---|
| 226 | // std::cout << "number of augmentation phases: " << i << std::endl; |
---|
| 227 | // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
---|
| 228 | // } |
---|
| 229 | |
---|
| 230 | { |
---|
| 231 | std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; |
---|
[777] | 232 | for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); |
---|
[642] | 233 | ts.reset(); |
---|
| 234 | int i=0; |
---|
[762] | 235 | while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; } |
---|
[642] | 236 | std::cout << "elapsed time: " << ts << std::endl; |
---|
| 237 | std::cout << "number of augmentation phases: " << i << std::endl; |
---|
[762] | 238 | std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
---|
[642] | 239 | } |
---|
| 240 | |
---|
| 241 | { |
---|
| 242 | std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
---|
[777] | 243 | for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); |
---|
[642] | 244 | ts.reset(); |
---|
| 245 | int i=0; |
---|
[762] | 246 | while (augmenting_flow_test.augmentOnShortestPath()) { ++i; } |
---|
[642] | 247 | std::cout << "elapsed time: " << ts << std::endl; |
---|
| 248 | std::cout << "number of augmentation phases: " << i << std::endl; |
---|
[762] | 249 | std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
---|
[642] | 250 | } |
---|
| 251 | } |
---|
| 252 | |
---|
[174] | 253 | return 0; |
---|
| 254 | } |
---|