1.1 --- a/src/work/marci/gw_vs_not.cc Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,179 +0,0 @@
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 lemon;
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 -}