1.1 --- a/src/work/jacint/preflow.cc Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,264 +0,0 @@
1.4 -#include <iostream>
1.5 -
1.6 -#include <smart_graph.h>
1.7 -#include <dimacs.h>
1.8 -#include <preflow.h>
1.9 -#include <time_measure.h>
1.10 -
1.11 -using namespace lemon;
1.12 -
1.13 -int main(int, char **) {
1.14 -
1.15 - typedef SmartGraph Graph;
1.16 -
1.17 - typedef Graph::Node Node;
1.18 - typedef Graph::EdgeIt EdgeIt;
1.19 -
1.20 - Graph G;
1.21 - Node s, t;
1.22 - Graph::EdgeMap<int> cap(G);
1.23 - readDimacsMaxFlow(std::cin, G, s, t, cap);
1.24 - Timer ts;
1.25 - bool error=false;
1.26 -
1.27 - std::cout <<
1.28 - "\n Testing preflow.h on a graph with " <<
1.29 - G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
1.30 - << std::endl;
1.31 -
1.32 -
1.33 - Graph::EdgeMap<int> flow(G,0);
1.34 - Preflow<Graph, int> preflow_test(G, s, t, cap, flow);
1.35 - std::cout << "\nCalling run() (flow must be constant zero)..."<<std::endl;
1.36 - ts.reset();
1.37 - preflow_test.run();
1.38 - std::cout << "Elapsed time: " << ts << std::endl;
1.39 -
1.40 - Graph::NodeMap<bool> mincut(G);
1.41 - preflow_test.minMinCut(mincut);
1.42 - int min_min_cut_value=0;
1.43 - Graph::NodeMap<bool> cut(G);
1.44 - preflow_test.minCut(cut);
1.45 - int min_cut_value=0;
1.46 - Graph::NodeMap<bool> maxcut(G);
1.47 - preflow_test.maxMinCut(maxcut);
1.48 - int max_min_cut_value=0;
1.49 - EdgeIt e;
1.50 - for(G.first(e); G.valid(e); G.next(e)) {
1.51 - int c=cap[e];
1.52 - if (mincut[G.source(e)] && !mincut[G.target(e)]) min_min_cut_value+=c;
1.53 - if (cut[G.source(e)] && !cut[G.target(e)]) min_cut_value+=c;
1.54 - if (maxcut[G.source(e)] && !maxcut[G.target(e)]) max_min_cut_value+=c;
1.55 - }
1.56 -
1.57 - std::cout << "\nChecking the result: " <<std::endl;
1.58 - std::cout << "Flow value: "<< preflow_test.flowValue() << std::endl;
1.59 - std::cout << "Min cut value: "<< min_cut_value << std::endl;
1.60 - std::cout << "Min min cut value: "<< min_min_cut_value << std::endl;
1.61 - std::cout << "Max min cut value: "<< max_min_cut_value <<
1.62 - std::endl;
1.63 -
1.64 - if ( preflow_test.flowValue() == min_cut_value &&
1.65 - min_cut_value == min_min_cut_value &&
1.66 - min_min_cut_value == max_min_cut_value )
1.67 - std::cout << "They are equal. " <<std::endl;
1.68 - else {
1.69 - std::cout << "ERROR! They are not equal! " <<std::endl;
1.70 - error=true;
1.71 - }
1.72 -
1.73 -
1.74 -
1.75 - Preflow<Graph, int> preflow_test2(G, s, t, cap, flow);
1.76 - std::cout << "\n\nCalling preflow(GEN_FLOW) with the given maximum flow..."<<std::endl;
1.77 - ts.reset();
1.78 - preflow_test2.preflow(preflow_test2.GEN_FLOW);
1.79 - std::cout << "Elapsed time: " << ts << std::endl;
1.80 -
1.81 - Graph::NodeMap<bool> mincut2(G);
1.82 - preflow_test.minMinCut(mincut2);
1.83 - int min_min_cut2_value=0;
1.84 - Graph::NodeMap<bool> cut2(G);
1.85 - preflow_test.minCut(cut2);
1.86 - int min_cut2_value=0;
1.87 - Graph::NodeMap<bool> maxcut2(G);
1.88 - preflow_test.maxMinCut(maxcut2);
1.89 - int max_min_cut2_value=0;
1.90 - for(G.first(e); G.valid(e); G.next(e)) {
1.91 - int c=cap[e];
1.92 - if (mincut2[G.source(e)] && !mincut2[G.target(e)]) min_min_cut2_value+=c;
1.93 - if (cut2[G.source(e)] && !cut2[G.target(e)]) min_cut2_value+=c;
1.94 - if (maxcut2[G.source(e)] && !maxcut2[G.target(e)]) max_min_cut2_value+=c;
1.95 - }
1.96 -
1.97 - std::cout << "\nThe given flow value is "
1.98 - << preflow_test2.flowValue();
1.99 -
1.100 - if ( preflow_test2.flowValue() == min_cut2_value &&
1.101 - min_cut2_value == min_min_cut2_value &&
1.102 - min_min_cut2_value == max_min_cut2_value )
1.103 - std::cout <<", which is equal to all three min cut values."
1.104 - <<std::endl;
1.105 - else {
1.106 - std::cout << "ERROR! It is not equal to all three min cut values! "
1.107 - <<std::endl;
1.108 - error=true;
1.109 - }
1.110 -
1.111 -
1.112 -
1.113 -
1.114 - Graph::EdgeMap<int> flow3(G,0);
1.115 - Preflow<Graph, int> preflow_test3(G, s, t, cap, flow3);
1.116 - std::cout << "\n\nCalling preflowPhase0(PREFLOW) on the constant zero flow..."<<std::endl;
1.117 - ts.reset();
1.118 - preflow_test3.preflowPhase0(preflow_test3.PREFLOW);
1.119 - std::cout << "Elapsed time: " << ts << std::endl;
1.120 - Graph::NodeMap<bool> actcut3(G);
1.121 - std::cout << "\nCalling actMinCut()..."<<std::endl;
1.122 - preflow_test3.actMinCut(actcut3);
1.123 - std::cout << "Calling preflowPhase1() on the given flow..."<<std::endl;
1.124 - ts.reset();
1.125 - preflow_test3.preflowPhase1();
1.126 - std::cout << "Elapsed time: " << ts << std::endl;
1.127 -
1.128 - int act_min_cut3_value=0;
1.129 -
1.130 - Graph::NodeMap<bool> mincut3(G);
1.131 - preflow_test.minMinCut(mincut3);
1.132 - int min_min_cut3_value=0;
1.133 -
1.134 - Graph::NodeMap<bool> cut3(G);
1.135 - preflow_test.minCut(cut3);
1.136 - int min_cut3_value=0;
1.137 -
1.138 - Graph::NodeMap<bool> maxcut3(G);
1.139 - preflow_test.maxMinCut(maxcut3);
1.140 - int max_min_cut3_value=0;
1.141 -
1.142 - for(G.first(e); G.valid(e); G.next(e)) {
1.143 - int c=cap[e];
1.144 - if (mincut3[G.source(e)] && !mincut3[G.target(e)]) min_min_cut3_value+=c;
1.145 - if (cut3[G.source(e)] && !cut3[G.target(e)]) min_cut3_value+=c;
1.146 - if (maxcut3[G.source(e)] && !maxcut3[G.target(e)]) max_min_cut3_value+=c;
1.147 - if (actcut3[G.source(e)] && !actcut3[G.target(e)]) act_min_cut3_value+=c;
1.148 - }
1.149 -
1.150 - std::cout << "\nThe min cut value given by actMinCut() after phase 0 is "<<
1.151 - act_min_cut3_value;
1.152 -
1.153 - if ( preflow_test3.flowValue() == min_cut3_value &&
1.154 - min_cut3_value == min_min_cut3_value &&
1.155 - min_min_cut3_value == max_min_cut3_value &&
1.156 - max_min_cut3_value == act_min_cut3_value ) {
1.157 - std::cout <<
1.158 - ", which is equal to the given flow value and to all three min cut values after phase 1."
1.159 - <<std::endl;
1.160 - }
1.161 - else {
1.162 - std::cout <<
1.163 - "ERROR! It is not equal to the given flow value and to all three min cut values after phase 1! "
1.164 - <<std::endl;
1.165 - error=true;
1.166 - }
1.167 -
1.168 -
1.169 -
1.170 -
1.171 -
1.172 - Graph::EdgeMap<int> flow4(G,0);
1.173 - Preflow<Graph, int> preflow_test4(G, s, t, cap, flow4);
1.174 - std::cout <<
1.175 - "\n\nCalling preflow(PREFLOW) with the constant 0 flow, the result is f..."
1.176 - <<std::endl;
1.177 - preflow_test4.preflow(preflow_test4.PREFLOW);
1.178 -
1.179 - std::cout << "Swapping the source and the target, "<<std::endl;
1.180 - std::cout << "by calling resetSource(t) and resetTarget(s)..."
1.181 - <<std::endl;
1.182 - preflow_test4.resetSource(t);
1.183 - preflow_test4.resetTarget(s);
1.184 -
1.185 - std::cout <<
1.186 - "Calling preflow(PREFLOW) to find a maximum t-s flow starting with flow f..."
1.187 - <<std::endl;
1.188 - preflow_test4.preflow(preflow_test4.PREFLOW);
1.189 -
1.190 - Graph::NodeMap<bool> mincut4(G);
1.191 - preflow_test4.minMinCut(mincut4);
1.192 - int min_min_cut4_value=0;
1.193 - Graph::NodeMap<bool> cut4(G);
1.194 - preflow_test4.minCut(cut4);
1.195 - int min_cut4_value=0;
1.196 - Graph::NodeMap<bool> maxcut4(G);
1.197 - preflow_test4.maxMinCut(maxcut4);
1.198 - int max_min_cut4_value=0;
1.199 - for(G.first(e); G.valid(e); G.next(e)) {
1.200 - int c=cap[e];
1.201 - if (mincut4[G.source(e)] && !mincut4[G.target(e)]) min_min_cut4_value+=c;
1.202 - if (cut4[G.source(e)] && !cut4[G.target(e)]) min_cut4_value+=c;
1.203 - if (maxcut4[G.source(e)] && !maxcut4[G.target(e)]) max_min_cut4_value+=c;
1.204 - }
1.205 -
1.206 - std::cout << "\nThe given flow value is "
1.207 - << preflow_test4.flowValue();
1.208 -
1.209 - if ( preflow_test4.flowValue() == min_cut4_value &&
1.210 - min_cut4_value == min_min_cut4_value &&
1.211 - min_min_cut4_value == max_min_cut4_value )
1.212 - std::cout <<", which is equal to all three min cut values."
1.213 - <<std::endl;
1.214 - else {
1.215 - std::cout << "ERROR! It is not equal to all three min cut values! "
1.216 - <<std::endl;
1.217 - error=true;
1.218 - }
1.219 -
1.220 -
1.221 -
1.222 -
1.223 - Graph::EdgeMap<int> flow5(G,0);
1.224 - std::cout << "Resetting the stored flow to constant zero, by calling resetFlow..."
1.225 - <<std::endl;
1.226 - preflow_test4.resetFlow(flow5);
1.227 - std::cout <<
1.228 - "Calling preflow(GEN_FLOW) to find a maximum t-s flow "<<std::endl;
1.229 - std::cout <<
1.230 - "starting with this constant zero flow..." <<std::endl;
1.231 - preflow_test4.preflow(preflow_test4.GEN_FLOW);
1.232 -
1.233 - Graph::NodeMap<bool> mincut5(G);
1.234 - preflow_test4.minMinCut(mincut5);
1.235 - int min_min_cut5_value=0;
1.236 - Graph::NodeMap<bool> cut5(G);
1.237 - preflow_test4.minCut(cut5);
1.238 - int min_cut5_value=0;
1.239 - Graph::NodeMap<bool> maxcut5(G);
1.240 - preflow_test4.maxMinCut(maxcut5);
1.241 - int max_min_cut5_value=0;
1.242 - for(G.first(e); G.valid(e); G.next(e)) {
1.243 - int c=cap[e];
1.244 - if (mincut5[G.source(e)] && !mincut5[G.target(e)]) min_min_cut5_value+=c;
1.245 - if (cut5[G.source(e)] && !cut5[G.target(e)]) min_cut5_value+=c;
1.246 - if (maxcut5[G.source(e)] && !maxcut5[G.target(e)]) max_min_cut5_value+=c;
1.247 - }
1.248 -
1.249 - std::cout << "\nThe given flow value is "
1.250 - << preflow_test4.flowValue();
1.251 -
1.252 - if ( preflow_test4.flowValue() == min_cut5_value &&
1.253 - min_cut5_value == min_min_cut5_value &&
1.254 - min_min_cut5_value == max_min_cut5_value )
1.255 - std::cout <<", which is equal to all three min cut values."
1.256 - <<std::endl<<std::endl;
1.257 - else {
1.258 - std::cout << "ERROR! It is not equal to all three min cut values! "
1.259 - <<std::endl;
1.260 - error=true;
1.261 - }
1.262 -
1.263 - if (error) std::cout <<"\nThere was some error in the results!\n"<<std::endl;
1.264 - else std::cout <<"\nThere was no error in the results.\n"<<std::endl;
1.265 -
1.266 - return 0;
1.267 -}