1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/marci/experiment/edmonds_karp_demo_1.cc Sat Apr 03 17:26:46 2004 +0000
1.3 @@ -0,0 +1,218 @@
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_1.h>
1.12 +#include <time_measure.h>
1.13 +#include <graph_wrapper_1.h>
1.14 +
1.15 +class CM {
1.16 +public:
1.17 + template<typename T> int get(T) const {return 1;}
1.18 +};
1.19 +
1.20 +using namespace hugo;
1.21 +
1.22 +// Use a DIMACS max flow file as stdin.
1.23 +// read_dimacs_demo < dimacs_max_flow_file
1.24 +
1.25 +
1.26 +// struct Ize {
1.27 +// };
1.28 +
1.29 +// struct Mize {
1.30 +// Ize bumm;
1.31 +// };
1.32 +
1.33 +// template <typename B>
1.34 +// class Huha {
1.35 +// public:
1.36 +// int u;
1.37 +// B brr;
1.38 +// };
1.39 +
1.40 +
1.41 +int main(int, char **) {
1.42 +
1.43 + typedef ListGraph MutableGraph;
1.44 +
1.45 + //typedef SmartGraph Graph;
1.46 + typedef ListGraph Graph;
1.47 + typedef Graph::Node Node;
1.48 + typedef Graph::EdgeIt EdgeIt;
1.49 +
1.50 +
1.51 +// Mize mize[10];
1.52 +// Mize bize[0];
1.53 +// Mize zize;
1.54 +// typedef Mize Tize[0];
1.55 +
1.56 +// std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl;
1.57 +// std::cout << sizeof(bize) << std::endl;
1.58 +
1.59 +
1.60 +// Huha<Tize> k;
1.61 +// std::cout << sizeof(k) << std::endl;
1.62 +
1.63 +
1.64 +// struct Bumm {
1.65 +// //int a;
1.66 +// bool b;
1.67 +// };
1.68 +
1.69 +// std::cout << sizeof(Bumm) << std::endl;
1.70 +
1.71 +
1.72 + Graph G;
1.73 + Node s, t;
1.74 + Graph::EdgeMap<int> cap(G);
1.75 + readDimacsMaxFlow(std::cin, G, s, t, cap);
1.76 +
1.77 +// typedef TrivGraphWrapper<Graph> TGW;
1.78 +// TGW gw(G);
1.79 +// TGW::NodeIt sw;
1.80 +// gw./*getF*/first(sw);
1.81 +// std::cout << "p1:" << gw.nodeNum() << std::endl;
1.82 +// gw.erase(sw);
1.83 +// std::cout << "p2:" << gw.nodeNum() << std::endl;
1.84 +
1.85 +// typedef const Graph cLG;
1.86 +// typedef TrivGraphWrapper<const cLG> CTGW;
1.87 +// CTGW cgw(G);
1.88 +// CTGW::NodeIt csw;
1.89 +// cgw./*getF*/first(csw);
1.90 +// std::cout << "p1:" << cgw.nodeNum() << std::endl;
1.91 +// //cgw.erase(csw);
1.92 +// std::cout << "p2:" << cgw.nodeNum() << std::endl;
1.93 +
1.94 +
1.95 + {
1.96 + typedef TrivGraphWrapper<const Graph> GW;
1.97 + GW gw(G);
1.98 + std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
1.99 + GW::EdgeMap<int> flow(gw); //0 flow
1.100 +
1.101 + Timer ts;
1.102 + ts.reset();
1.103 +
1.104 + typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
1.105 + EMW cw(cap);
1.106 + MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw);
1.107 + int i=0;
1.108 + while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) {
1.109 +// for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
1.110 +// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
1.111 +// }
1.112 +// std::cout<<std::endl;
1.113 + ++i;
1.114 + }
1.115 +
1.116 +// std::cout << "maximum flow: "<< std::endl;
1.117 +// for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
1.118 +// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
1.119 +// }
1.120 +// std::cout<<std::endl;
1.121 + std::cout << "elapsed time: " << ts << std::endl;
1.122 + std::cout << "number of augmentation phases: " << i << std::endl;
1.123 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.124 + }
1.125 +
1.126 + {
1.127 + typedef TrivGraphWrapper<const Graph> GW;
1.128 + GW gw(G);
1.129 + std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
1.130 + GW::EdgeMap<int> flow(gw); //0 flow
1.131 +
1.132 + Timer ts;
1.133 + ts.reset();
1.134 +
1.135 + typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
1.136 + EMW cw(cap);
1.137 + MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw);
1.138 + int i=0;
1.139 + while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
1.140 +// for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
1.141 +// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
1.142 +// }
1.143 +// std::cout<<std::endl;
1.144 + ++i;
1.145 + }
1.146 +
1.147 +// std::cout << "maximum flow: "<< std::endl;
1.148 +// for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
1.149 +// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
1.150 +// }
1.151 +// std::cout<<std::endl;
1.152 + std::cout << "elapsed time: " << ts << std::endl;
1.153 + std::cout << "number of augmentation phases: " << i << std::endl;
1.154 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.155 + }
1.156 +
1.157 + {
1.158 + typedef TrivGraphWrapper<const Graph> GW;
1.159 + GW gw(G);
1.160 + std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
1.161 + GW::EdgeMap<int> flow(gw); //0 flow
1.162 +
1.163 + Timer ts;
1.164 + ts.reset();
1.165 +
1.166 + typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
1.167 + EMW cw(cap);
1.168 + MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw);
1.169 + int i=0;
1.170 + while (max_flow_test.augmentOnBlockingFlow2()) {
1.171 +// for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
1.172 +// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
1.173 +// }
1.174 +// std::cout<<std::endl;
1.175 + ++i;
1.176 + }
1.177 +
1.178 +// std::cout << "maximum flow: "<< std::endl;
1.179 +// for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
1.180 +// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
1.181 +// }
1.182 +// std::cout<<std::endl;
1.183 + std::cout << "elapsed time: " << ts << std::endl;
1.184 + std::cout << "number of augmentation phases: " << i << std::endl;
1.185 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.186 + }
1.187 +
1.188 + {
1.189 + typedef TrivGraphWrapper<const Graph> GW;
1.190 + GW gw(G);
1.191 + std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
1.192 + GW::EdgeMap<int> flow(gw); //0 flow
1.193 +
1.194 + Timer ts;
1.195 + ts.reset();
1.196 +
1.197 + typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
1.198 + EMW cw(cap);
1.199 + MaxFlow<GW, int, GW::EdgeMap<int>, EMW> max_flow_test(gw, s, t, flow, cw);
1.200 + int i=0;
1.201 + while (max_flow_test.augmentOnShortestPath()) {
1.202 +// for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
1.203 +// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
1.204 +// }
1.205 +// std::cout<<std::endl;
1.206 + ++i;
1.207 + }
1.208 +
1.209 +// std::cout << "maximum flow: "<< std::endl;
1.210 +// for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
1.211 +// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
1.212 +// }
1.213 +// std::cout<<std::endl;
1.214 + std::cout << "elapsed time: " << ts << std::endl;
1.215 + std::cout << "number of augmentation phases: " << i << std::endl;
1.216 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.217 + }
1.218 +
1.219 +
1.220 + return 0;
1.221 +}