1.1 --- a/src/work/marci/experiment/edmonds_karp_demo.cc Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,218 +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 -class CM {
1.16 -public:
1.17 - template<typename T> int get(T) const {return 1;}
1.18 -};
1.19 -
1.20 -using namespace lemon;
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.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(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.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(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.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(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.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(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.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(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.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(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.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(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.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(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 -}