1.1 --- a/src/work/marci/lg_vs_sg.cc Fri May 14 18:28:57 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,250 +0,0 @@
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 -}
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/work/marci/lg_vs_sg_vs_sg.cc Fri May 14 18:33:17 2004 +0000
2.3 @@ -0,0 +1,250 @@
2.4 +// -*- c++ -*-
2.5 +#include <iostream>
2.6 +#include <fstream>
2.7 +#include <string>
2.8 +
2.9 +#include <sage_graph.h>
2.10 +#include <hugo/list_graph.h>
2.11 +#include <hugo/smart_graph.h>
2.12 +#include <hugo/dimacs.h>
2.13 +#include <max_flow.h>
2.14 +#include <hugo/time_measure.h>
2.15 +#include <hugo/for_each_macros.h>
2.16 +
2.17 +using namespace hugo;
2.18 +
2.19 +// Use a DIMACS max flow file as stdin.
2.20 +// read_dimacs_demo dimacs_max_flow_file
2.21 +
2.22 +int main(int, char** argv) {
2.23 +
2.24 + std::string in=argv[1];
2.25 + typedef SageGraph MutableGraph;
2.26 +
2.27 + {
2.28 + typedef SageGraph Graph;
2.29 + typedef Graph::Node Node;
2.30 + typedef Graph::EdgeIt EdgeIt;
2.31 +
2.32 + Graph g;
2.33 + Node s, t;
2.34 + Graph::EdgeMap<int> cap(g);
2.35 + std::ifstream ins(in.c_str());
2.36 + //readDimacsMaxFlow(ins, g, s, t, cap);
2.37 + readDimacs(ins, g, cap, s, t);
2.38 +
2.39 + Timer ts;
2.40 + Graph::EdgeMap<int> flow(g); //0 flow
2.41 + MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
2.42 + max_flow_test(g, s, t, cap, flow/*, true*/);
2.43 +
2.44 + std::cout << "SageGraph ..." << std::endl;
2.45 +
2.46 + {
2.47 + std::cout << "preflow ..." << std::endl;
2.48 + ts.reset();
2.49 + max_flow_test.run();
2.50 + std::cout << "elapsed time: " << ts << std::endl;
2.51 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.52 + }
2.53 +
2.54 + {
2.55 + std::cout << "physical blocking flow augmentation ..." << std::endl;
2.56 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
2.57 + ts.reset();
2.58 + int i=0;
2.59 + while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
2.60 + std::cout << "elapsed time: " << ts << std::endl;
2.61 + std::cout << "number of augmentation phases: " << i << std::endl;
2.62 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.63 + }
2.64 +
2.65 +// {
2.66 +// std::cout << "faster physical blocking flow augmentation ..." << std::endl;
2.67 +// FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
2.68 +// ts.reset();
2.69 +// int i=0;
2.70 +// while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
2.71 +// std::cout << "elapsed time: " << ts << std::endl;
2.72 +// std::cout << "number of augmentation phases: " << i << std::endl;
2.73 +// std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.74 +// }
2.75 +
2.76 + {
2.77 + std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
2.78 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
2.79 + ts.reset();
2.80 + int i=0;
2.81 + while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
2.82 + std::cout << "elapsed time: " << ts << std::endl;
2.83 + std::cout << "number of augmentation phases: " << i << std::endl;
2.84 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.85 + }
2.86 +
2.87 + {
2.88 + std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
2.89 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
2.90 + ts.reset();
2.91 + int i=0;
2.92 + while (max_flow_test.augmentOnShortestPath()) { ++i; }
2.93 + std::cout << "elapsed time: " << ts << std::endl;
2.94 + std::cout << "number of augmentation phases: " << i << std::endl;
2.95 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.96 + }
2.97 + }
2.98 +
2.99 + {
2.100 + typedef SmartGraph Graph;
2.101 + typedef Graph::Node Node;
2.102 + typedef Graph::EdgeIt EdgeIt;
2.103 +
2.104 + Graph g;
2.105 + Node s, t;
2.106 + Graph::EdgeMap<int> cap(g);
2.107 + std::ifstream ins(in.c_str());
2.108 + //readDimacsMaxFlow(ins, g, s, t, cap);
2.109 + readDimacs(ins, g, cap, s, t);
2.110 +
2.111 + Timer ts;
2.112 + Graph::EdgeMap<int> flow(g); //0 flow
2.113 + MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
2.114 + max_flow_test(g, s, t, cap, flow/*, true*/);
2.115 + // MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
2.116 + // max_flow_test(g, s, t, cap, flow);
2.117 +
2.118 + std::cout << "SmartGraph ..." << std::endl;
2.119 +
2.120 + {
2.121 + std::cout << "preflow ..." << std::endl;
2.122 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
2.123 + ts.reset();
2.124 + max_flow_test.run();
2.125 + std::cout << "elapsed time: " << ts << std::endl;
2.126 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.127 + }
2.128 +
2.129 + {
2.130 + std::cout << "physical blocking flow augmentation ..." << std::endl;
2.131 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
2.132 + ts.reset();
2.133 + int i=0;
2.134 + while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
2.135 + std::cout << "elapsed time: " << ts << std::endl;
2.136 + std::cout << "number of augmentation phases: " << i << std::endl;
2.137 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.138 + }
2.139 +
2.140 +// {
2.141 +// std::cout << "faster physical blocking flow augmentation ..." << std::endl;
2.142 +// FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
2.143 +// ts.reset();
2.144 +// int i=0;
2.145 +// while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
2.146 +// std::cout << "elapsed time: " << ts << std::endl;
2.147 +// std::cout << "number of augmentation phases: " << i << std::endl;
2.148 +// std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.149 +// }
2.150 +
2.151 + {
2.152 + std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
2.153 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
2.154 + ts.reset();
2.155 + int i=0;
2.156 + while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
2.157 + std::cout << "elapsed time: " << ts << std::endl;
2.158 + std::cout << "number of augmentation phases: " << i << std::endl;
2.159 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.160 + }
2.161 +
2.162 + {
2.163 + std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
2.164 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
2.165 + ts.reset();
2.166 + int i=0;
2.167 + while (max_flow_test.augmentOnShortestPath()) { ++i; }
2.168 + std::cout << "elapsed time: " << ts << std::endl;
2.169 + std::cout << "number of augmentation phases: " << i << std::endl;
2.170 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.171 + }
2.172 + }
2.173 +
2.174 + {
2.175 + typedef ListGraph Graph;
2.176 + typedef Graph::Node Node;
2.177 + typedef Graph::EdgeIt EdgeIt;
2.178 +
2.179 + Graph g;
2.180 + Node s, t;
2.181 + Graph::EdgeMap<int> cap(g);
2.182 + std::ifstream ins(in.c_str());
2.183 + //readDimacsMaxFlow(ins, g, s, t, cap);
2.184 + readDimacs(ins, g, cap, s, t);
2.185 +
2.186 + Timer ts;
2.187 + Graph::EdgeMap<int> flow(g); //0 flow
2.188 + MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
2.189 + max_flow_test(g, s, t, cap, flow/*, true*/);
2.190 + // MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
2.191 + // max_flow_test(g, s, t, cap, flow);
2.192 +
2.193 + std::cout << "ListGraph ..." << std::endl;
2.194 +
2.195 + {
2.196 + std::cout << "preflow ..." << std::endl;
2.197 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
2.198 + ts.reset();
2.199 + max_flow_test.run();
2.200 + std::cout << "elapsed time: " << ts << std::endl;
2.201 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.202 + }
2.203 +
2.204 + {
2.205 + std::cout << "physical blocking flow augmentation ..." << std::endl;
2.206 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
2.207 + ts.reset();
2.208 + int i=0;
2.209 + while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
2.210 + std::cout << "elapsed time: " << ts << std::endl;
2.211 + std::cout << "number of augmentation phases: " << i << std::endl;
2.212 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.213 + }
2.214 +
2.215 +// {
2.216 +// std::cout << "faster physical blocking flow augmentation ..." << std::endl;
2.217 +// FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
2.218 +// ts.reset();
2.219 +// int i=0;
2.220 +// while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
2.221 +// std::cout << "elapsed time: " << ts << std::endl;
2.222 +// std::cout << "number of augmentation phases: " << i << std::endl;
2.223 +// std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.224 +// }
2.225 +
2.226 + {
2.227 + std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
2.228 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
2.229 + ts.reset();
2.230 + int i=0;
2.231 + while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
2.232 + std::cout << "elapsed time: " << ts << std::endl;
2.233 + std::cout << "number of augmentation phases: " << i << std::endl;
2.234 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.235 + }
2.236 +
2.237 + {
2.238 + std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
2.239 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
2.240 + ts.reset();
2.241 + int i=0;
2.242 + while (max_flow_test.augmentOnShortestPath()) { ++i; }
2.243 + std::cout << "elapsed time: " << ts << std::endl;
2.244 + std::cout << "number of augmentation phases: " << i << std::endl;
2.245 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.246 + }
2.247 + }
2.248 +
2.249 +
2.250 +
2.251 +
2.252 + return 0;
2.253 +}
3.1 --- a/src/work/marci/makefile Fri May 14 18:28:57 2004 +0000
3.2 +++ b/src/work/marci/makefile Fri May 14 18:33:17 2004 +0000
3.3 @@ -4,7 +4,7 @@
3.4 INCLUDEDIRS ?= -I../.. -I.. -I../{marci,jacint,alpar,klao,akos,athos} -I$(BOOSTROOT)
3.5
3.6 LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
3.7 -BINARIES = max_flow_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try bipartite_matching_try_3 top_sort_test max_flow_1
3.8 +BINARIES = max_flow_demo iterator_bfs_demo macro_test lg_vs_sg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try bipartite_matching_try_3 top_sort_test max_flow_1
3.9 #gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
3.10
3.11 include ../makefile