1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/marci/lg_vs_sg_vs_sg.cc Fri May 14 18:33:17 2004 +0000
1.3 @@ -0,0 +1,250 @@
1.4 +// -*- c++ -*-
1.5 +#include <iostream>
1.6 +#include <fstream>
1.7 +#include <string>
1.8 +
1.9 +#include <sage_graph.h>
1.10 +#include <hugo/list_graph.h>
1.11 +#include <hugo/smart_graph.h>
1.12 +#include <hugo/dimacs.h>
1.13 +#include <max_flow.h>
1.14 +#include <hugo/time_measure.h>
1.15 +#include <hugo/for_each_macros.h>
1.16 +
1.17 +using namespace hugo;
1.18 +
1.19 +// Use a DIMACS max flow file as stdin.
1.20 +// read_dimacs_demo dimacs_max_flow_file
1.21 +
1.22 +int main(int, char** argv) {
1.23 +
1.24 + std::string in=argv[1];
1.25 + typedef SageGraph MutableGraph;
1.26 +
1.27 + {
1.28 + typedef SageGraph Graph;
1.29 + typedef Graph::Node Node;
1.30 + typedef Graph::EdgeIt EdgeIt;
1.31 +
1.32 + Graph g;
1.33 + Node s, t;
1.34 + Graph::EdgeMap<int> cap(g);
1.35 + std::ifstream ins(in.c_str());
1.36 + //readDimacsMaxFlow(ins, g, s, t, cap);
1.37 + readDimacs(ins, g, cap, s, t);
1.38 +
1.39 + Timer ts;
1.40 + Graph::EdgeMap<int> flow(g); //0 flow
1.41 + MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.42 + max_flow_test(g, s, t, cap, flow/*, true*/);
1.43 +
1.44 + std::cout << "SageGraph ..." << std::endl;
1.45 +
1.46 + {
1.47 + std::cout << "preflow ..." << std::endl;
1.48 + ts.reset();
1.49 + max_flow_test.run();
1.50 + std::cout << "elapsed time: " << ts << std::endl;
1.51 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.52 + }
1.53 +
1.54 + {
1.55 + std::cout << "physical blocking flow augmentation ..." << std::endl;
1.56 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.57 + ts.reset();
1.58 + int i=0;
1.59 + while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
1.60 + std::cout << "elapsed time: " << ts << std::endl;
1.61 + std::cout << "number of augmentation phases: " << i << std::endl;
1.62 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.63 + }
1.64 +
1.65 +// {
1.66 +// std::cout << "faster physical blocking flow augmentation ..." << std::endl;
1.67 +// FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.68 +// ts.reset();
1.69 +// int i=0;
1.70 +// while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
1.71 +// std::cout << "elapsed time: " << ts << std::endl;
1.72 +// std::cout << "number of augmentation phases: " << i << std::endl;
1.73 +// std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.74 +// }
1.75 +
1.76 + {
1.77 + std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
1.78 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.79 + ts.reset();
1.80 + int i=0;
1.81 + while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
1.82 + std::cout << "elapsed time: " << ts << std::endl;
1.83 + std::cout << "number of augmentation phases: " << i << std::endl;
1.84 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.85 + }
1.86 +
1.87 + {
1.88 + std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
1.89 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.90 + ts.reset();
1.91 + int i=0;
1.92 + while (max_flow_test.augmentOnShortestPath()) { ++i; }
1.93 + std::cout << "elapsed time: " << ts << std::endl;
1.94 + std::cout << "number of augmentation phases: " << i << std::endl;
1.95 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.96 + }
1.97 + }
1.98 +
1.99 + {
1.100 + typedef SmartGraph Graph;
1.101 + typedef Graph::Node Node;
1.102 + typedef Graph::EdgeIt EdgeIt;
1.103 +
1.104 + Graph g;
1.105 + Node s, t;
1.106 + Graph::EdgeMap<int> cap(g);
1.107 + std::ifstream ins(in.c_str());
1.108 + //readDimacsMaxFlow(ins, g, s, t, cap);
1.109 + readDimacs(ins, g, cap, s, t);
1.110 +
1.111 + Timer ts;
1.112 + Graph::EdgeMap<int> flow(g); //0 flow
1.113 + MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.114 + max_flow_test(g, s, t, cap, flow/*, true*/);
1.115 + // MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.116 + // max_flow_test(g, s, t, cap, flow);
1.117 +
1.118 + std::cout << "SmartGraph ..." << std::endl;
1.119 +
1.120 + {
1.121 + std::cout << "preflow ..." << std::endl;
1.122 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.123 + ts.reset();
1.124 + max_flow_test.run();
1.125 + std::cout << "elapsed time: " << ts << std::endl;
1.126 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.127 + }
1.128 +
1.129 + {
1.130 + std::cout << "physical blocking flow augmentation ..." << std::endl;
1.131 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.132 + ts.reset();
1.133 + int i=0;
1.134 + while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
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 << "faster physical blocking flow augmentation ..." << std::endl;
1.142 +// FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.143 +// ts.reset();
1.144 +// int i=0;
1.145 +// while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
1.146 +// std::cout << "elapsed time: " << ts << std::endl;
1.147 +// std::cout << "number of augmentation phases: " << i << std::endl;
1.148 +// std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.149 +// }
1.150 +
1.151 + {
1.152 + std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
1.153 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.154 + ts.reset();
1.155 + int i=0;
1.156 + while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
1.157 + std::cout << "elapsed time: " << ts << std::endl;
1.158 + std::cout << "number of augmentation phases: " << i << std::endl;
1.159 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.160 + }
1.161 +
1.162 + {
1.163 + std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
1.164 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.165 + ts.reset();
1.166 + int i=0;
1.167 + while (max_flow_test.augmentOnShortestPath()) { ++i; }
1.168 + std::cout << "elapsed time: " << ts << std::endl;
1.169 + std::cout << "number of augmentation phases: " << i << std::endl;
1.170 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.171 + }
1.172 + }
1.173 +
1.174 + {
1.175 + typedef ListGraph Graph;
1.176 + typedef Graph::Node Node;
1.177 + typedef Graph::EdgeIt EdgeIt;
1.178 +
1.179 + Graph g;
1.180 + Node s, t;
1.181 + Graph::EdgeMap<int> cap(g);
1.182 + std::ifstream ins(in.c_str());
1.183 + //readDimacsMaxFlow(ins, g, s, t, cap);
1.184 + readDimacs(ins, g, cap, s, t);
1.185 +
1.186 + Timer ts;
1.187 + Graph::EdgeMap<int> flow(g); //0 flow
1.188 + MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.189 + max_flow_test(g, s, t, cap, flow/*, true*/);
1.190 + // MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.191 + // max_flow_test(g, s, t, cap, flow);
1.192 +
1.193 + std::cout << "ListGraph ..." << std::endl;
1.194 +
1.195 + {
1.196 + std::cout << "preflow ..." << std::endl;
1.197 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.198 + ts.reset();
1.199 + max_flow_test.run();
1.200 + std::cout << "elapsed time: " << ts << std::endl;
1.201 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.202 + }
1.203 +
1.204 + {
1.205 + std::cout << "physical blocking flow augmentation ..." << std::endl;
1.206 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.207 + ts.reset();
1.208 + int i=0;
1.209 + while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
1.210 + std::cout << "elapsed time: " << ts << std::endl;
1.211 + std::cout << "number of augmentation phases: " << i << std::endl;
1.212 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.213 + }
1.214 +
1.215 +// {
1.216 +// std::cout << "faster physical blocking flow augmentation ..." << std::endl;
1.217 +// FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.218 +// ts.reset();
1.219 +// int i=0;
1.220 +// while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
1.221 +// std::cout << "elapsed time: " << ts << std::endl;
1.222 +// std::cout << "number of augmentation phases: " << i << std::endl;
1.223 +// std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.224 +// }
1.225 +
1.226 + {
1.227 + std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
1.228 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.229 + ts.reset();
1.230 + int i=0;
1.231 + while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
1.232 + std::cout << "elapsed time: " << ts << std::endl;
1.233 + std::cout << "number of augmentation phases: " << i << std::endl;
1.234 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.235 + }
1.236 +
1.237 + {
1.238 + std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
1.239 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.240 + ts.reset();
1.241 + int i=0;
1.242 + while (max_flow_test.augmentOnShortestPath()) { ++i; }
1.243 + std::cout << "elapsed time: " << ts << std::endl;
1.244 + std::cout << "number of augmentation phases: " << i << std::endl;
1.245 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.246 + }
1.247 + }
1.248 +
1.249 +
1.250 +
1.251 +
1.252 + return 0;
1.253 +}