1.1 --- a/src/work/marci/lg_vs_sg.cc Thu Apr 15 20:19:26 2004 +0000
1.2 +++ b/src/work/marci/lg_vs_sg.cc Thu Apr 15 20:50:03 2004 +0000
1.3 @@ -7,8 +7,9 @@
1.4 #include <smart_graph.h>
1.5 #include <dimacs.h>
1.6 #include <edmonds_karp.h>
1.7 +#include <preflow.h>
1.8 #include <time_measure.h>
1.9 -#include <graph_wrapper.h>
1.10 +#include <for_each_macros.h>
1.11
1.12 using namespace hugo;
1.13
1.14 @@ -31,50 +32,62 @@
1.15 std::ifstream ins(in.c_str());
1.16 readDimacsMaxFlow(ins, G, s, t, cap);
1.17
1.18 + Timer ts;
1.19 + Graph::EdgeMap<int> flow(G); //0 flow
1.20 + Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.21 + pre_flow_test(G, s, t, cap, flow);
1.22 + MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.23 + max_flow_test(G, s, t, cap, flow);
1.24 +
1.25 + std::cout << "ListGraph ..." << std::endl;
1.26 +
1.27 {
1.28 - std::cout << "ListGraph..." << std::endl;
1.29 - std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
1.30 - Graph::EdgeMap<int> flow(G); //0 flow
1.31 + std::cout << "preflow ..." << std::endl;
1.32 + ts.reset();
1.33 + pre_flow_test.run();
1.34 + std::cout << "elapsed time: " << ts << std::endl;
1.35 + std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
1.36 + }
1.37
1.38 - Timer ts;
1.39 + {
1.40 + std::cout << "physical blocking flow augmentation ..." << std::endl;
1.41 + FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
1.42 ts.reset();
1.43 -
1.44 - MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
1.45 int i=0;
1.46 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
1.47 -
1.48 std::cout << "elapsed time: " << ts << std::endl;
1.49 std::cout << "number of augmentation phases: " << i << std::endl;
1.50 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.51 }
1.52
1.53 {
1.54 - std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
1.55 - Graph::EdgeMap<int> flow(G); //0 flow
1.56 -
1.57 - Timer ts;
1.58 + std::cout << "faster physical blocking flow augmentation ..." << std::endl;
1.59 + FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
1.60 ts.reset();
1.61 -
1.62 - MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
1.63 int i=0;
1.64 - while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
1.65 -
1.66 + while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
1.67 std::cout << "elapsed time: " << ts << std::endl;
1.68 std::cout << "number of augmentation phases: " << i << std::endl;
1.69 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.70 }
1.71
1.72 {
1.73 - std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
1.74 - Graph::EdgeMap<int> flow(G); //0 flow
1.75 + std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
1.76 + FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
1.77 + ts.reset();
1.78 + int i=0;
1.79 + while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
1.80 + std::cout << "elapsed time: " << ts << std::endl;
1.81 + std::cout << "number of augmentation phases: " << i << std::endl;
1.82 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.83 + }
1.84
1.85 - Timer ts;
1.86 + {
1.87 + std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
1.88 + FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
1.89 ts.reset();
1.90 -
1.91 - MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
1.92 int i=0;
1.93 while (max_flow_test.augmentOnShortestPath()) { ++i; }
1.94 -
1.95 std::cout << "elapsed time: " << ts << std::endl;
1.96 std::cout << "number of augmentation phases: " << i << std::endl;
1.97 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.98 @@ -93,55 +106,71 @@
1.99 std::ifstream ins(in.c_str());
1.100 readDimacsMaxFlow(ins, G, s, t, cap);
1.101
1.102 + Timer ts;
1.103 + Graph::EdgeMap<int> flow(G); //0 flow
1.104 + Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.105 + pre_flow_test(G, s, t, cap, flow);
1.106 + MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.107 + max_flow_test(G, s, t, cap, flow);
1.108 +
1.109 + std::cout << "SmatrGraph ..." << std::endl;
1.110 +
1.111 {
1.112 - std::cout << "SmartGraph..." << std::endl;
1.113 - std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
1.114 - Graph::EdgeMap<int> flow(G); //0 flow
1.115 + std::cout << "preflow ..." << std::endl;
1.116 + FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
1.117 + ts.reset();
1.118 + pre_flow_test.run();
1.119 + std::cout << "elapsed time: " << ts << std::endl;
1.120 + std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
1.121 + }
1.122
1.123 - Timer ts;
1.124 + {
1.125 + std::cout << "physical blocking flow augmentation ..." << std::endl;
1.126 + FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
1.127 ts.reset();
1.128 -
1.129 - MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
1.130 int i=0;
1.131 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
1.132 -
1.133 std::cout << "elapsed time: " << ts << std::endl;
1.134 std::cout << "number of augmentation phases: " << i << std::endl;
1.135 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.136 }
1.137
1.138 {
1.139 - std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
1.140 - Graph::EdgeMap<int> flow(G); //0 flow
1.141 -
1.142 - Timer ts;
1.143 + std::cout << "faster physical blocking flow augmentation ..." << std::endl;
1.144 + FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
1.145 ts.reset();
1.146 -
1.147 - MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
1.148 int i=0;
1.149 - while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
1.150 -
1.151 + while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
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 - std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
1.159 - Graph::EdgeMap<int> flow(G); //0 flow
1.160 + std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
1.161 + FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
1.162 + ts.reset();
1.163 + int i=0;
1.164 + while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
1.165 + std::cout << "elapsed time: " << ts << std::endl;
1.166 + std::cout << "number of augmentation phases: " << i << std::endl;
1.167 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.168 + }
1.169
1.170 - Timer ts;
1.171 + {
1.172 + std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
1.173 + FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
1.174 ts.reset();
1.175 -
1.176 - MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
1.177 int i=0;
1.178 while (max_flow_test.augmentOnShortestPath()) { ++i; }
1.179 -
1.180 std::cout << "elapsed time: " << ts << std::endl;
1.181 std::cout << "number of augmentation phases: " << i << std::endl;
1.182 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.183 }
1.184 }
1.185
1.186 +
1.187 +
1.188 +
1.189 return 0;
1.190 }