1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/marci/gw_vs_not.cc Wed Mar 31 16:38:38 2004 +0000
1.3 @@ -0,0 +1,179 @@
1.4 +// -*- c++ -*-
1.5 +#include <iostream>
1.6 +#include <fstream>
1.7 +
1.8 +#include <list_graph.h>
1.9 +#include <smart_graph.h>
1.10 +#include <dimacs.h>
1.11 +#include <edmonds_karp.h>
1.12 +#include <time_measure.h>
1.13 +#include <graph_wrapper.h>
1.14 +
1.15 +using namespace hugo;
1.16 +
1.17 +// Use a DIMACS max flow file as stdin.
1.18 +// read_dimacs_demo < dimacs_max_flow_file
1.19 +
1.20 +int main(int, char **) {
1.21 +
1.22 + typedef ListGraph MutableGraph;
1.23 + //typedef SmartGraph Graph;
1.24 + typedef ListGraph Graph;
1.25 + typedef Graph::Node Node;
1.26 + typedef Graph::EdgeIt EdgeIt;
1.27 +
1.28 + Graph G;
1.29 + Node s, t;
1.30 + Graph::EdgeMap<int> cap(G);
1.31 + readDimacsMaxFlow(std::cin, G, s, t, cap);
1.32 +
1.33 + {
1.34 + typedef TrivGraphWrapper<const Graph> GW;
1.35 + GW gw(G);
1.36 + typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
1.37 + EMW cw(cap);
1.38 + Timer ts;
1.39 + GW::EdgeMap<int> flow(gw);
1.40 + MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw);
1.41 + int i;
1.42 +
1.43 + {
1.44 + std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
1.45 + for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
1.46 + ts.reset();
1.47 +
1.48 + i=0;
1.49 + while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
1.50 +
1.51 + std::cout << "elapsed time: " << ts << std::endl;
1.52 + std::cout << "number of augmentation phases: " << i << std::endl;
1.53 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.54 + }
1.55 +
1.56 + {
1.57 + std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
1.58 + for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
1.59 + ts.reset();
1.60 +
1.61 + i=0;
1.62 + while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
1.63 +
1.64 + std::cout << "elapsed time: " << ts << std::endl;
1.65 + std::cout << "number of augmentation phases: " << i << std::endl;
1.66 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.67 + }
1.68 +
1.69 + {
1.70 + std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
1.71 + for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
1.72 + ts.reset();
1.73 +
1.74 + i=0;
1.75 + while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
1.76 +
1.77 + std::cout << "elapsed time: " << ts << std::endl;
1.78 + std::cout << "number of augmentation phases: " << i << std::endl;
1.79 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.80 + }
1.81 +
1.82 + {
1.83 + std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
1.84 + for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
1.85 + ts.reset();
1.86 +
1.87 + i=0;
1.88 + while (max_flow_test.augmentOnShortestPath()) { ++i; }
1.89 +
1.90 + std::cout << "elapsed time: " << ts << std::endl;
1.91 + std::cout << "number of augmentation phases: " << i << std::endl;
1.92 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.93 + }
1.94 + }
1.95 +
1.96 +
1.97 +
1.98 +
1.99 + {
1.100 + typedef TrivGraphWrapper<const Graph> GW1;
1.101 + GW1 gw1(G);
1.102 + typedef TrivGraphWrapper<const GW1> GW2;
1.103 + GW2 gw2(gw1);
1.104 + typedef TrivGraphWrapper<const GW2> GW3;
1.105 + GW3 gw3(gw2);
1.106 + typedef TrivGraphWrapper<const GW3> GW4;
1.107 + GW4 gw4(gw3);
1.108 + typedef TrivGraphWrapper<const GW4> GW5;
1.109 + GW5 gw5(gw4);
1.110 + typedef TrivGraphWrapper<const GW5> GW6;
1.111 + GW6 gw6(gw5);
1.112 + typedef TrivGraphWrapper<const GW6> GW7;
1.113 + GW7 gw7(gw6);
1.114 + typedef TrivGraphWrapper<const GW7> GW8;
1.115 + GW8 gw8(gw7);
1.116 + typedef TrivGraphWrapper<const GW8> GW9;
1.117 + GW9 gw9(gw8);
1.118 + typedef TrivGraphWrapper<const GW9> GW;
1.119 + GW gw(gw9);
1.120 + typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
1.121 + EMW cw(cap);
1.122 + Timer ts;
1.123 + GW::EdgeMap<int> flow(gw);
1.124 + MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw);
1.125 + int i;
1.126 +
1.127 + {
1.128 + std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
1.129 + for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
1.130 + ts.reset();
1.131 +
1.132 + i=0;
1.133 + while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
1.134 +
1.135 + std::cout << "elapsed time: " << ts << std::endl;
1.136 + std::cout << "number of augmentation phases: " << i << std::endl;
1.137 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.138 + }
1.139 +
1.140 + {
1.141 + std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
1.142 + for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
1.143 + ts.reset();
1.144 +
1.145 + i=0;
1.146 + while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
1.147 +
1.148 + std::cout << "elapsed time: " << ts << std::endl;
1.149 + std::cout << "number of augmentation phases: " << i << std::endl;
1.150 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.151 + }
1.152 +
1.153 + {
1.154 + std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
1.155 + for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
1.156 + ts.reset();
1.157 +
1.158 + i=0;
1.159 + while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
1.160 +
1.161 + std::cout << "elapsed time: " << ts << std::endl;
1.162 + std::cout << "number of augmentation phases: " << i << std::endl;
1.163 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.164 + }
1.165 +
1.166 + {
1.167 + std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
1.168 + for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
1.169 + ts.reset();
1.170 +
1.171 + i=0;
1.172 + while (max_flow_test.augmentOnShortestPath()) { ++i; }
1.173 +
1.174 + std::cout << "elapsed time: " << ts << std::endl;
1.175 + std::cout << "number of augmentation phases: " << i << std::endl;
1.176 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.177 + }
1.178 + }
1.179 +
1.180 +
1.181 + return 0;
1.182 +}