1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/jacint/preflow.cc Tue Apr 27 22:59:15 2004 +0000
1.3 @@ -0,0 +1,239 @@
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 hugo;
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 +
1.26 + std::cout <<
1.27 + "\n Testing preflow.h on a graph with " <<
1.28 + G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
1.29 + << std::endl;
1.30 +
1.31 +
1.32 + Graph::EdgeMap<int> flow(G,0);
1.33 + Preflow<Graph, int> preflow_test(G, s, t, cap, flow);
1.34 + std::cout << "\nCalling run() (flow must be constant zero)..."<<std::endl;
1.35 + ts.reset();
1.36 + preflow_test.run();
1.37 + std::cout << "Elapsed time: " << ts << std::endl;
1.38 +
1.39 + Graph::NodeMap<bool> mincut(G);
1.40 + preflow_test.minMinCut(mincut);
1.41 + int min_min_cut_value=0;
1.42 + Graph::NodeMap<bool> cut(G);
1.43 + preflow_test.minCut(cut);
1.44 + int min_cut_value=0;
1.45 + Graph::NodeMap<bool> maxcut(G);
1.46 + preflow_test.maxMinCut(maxcut);
1.47 + int max_min_cut_value=0;
1.48 + EdgeIt e;
1.49 + for(G.first(e); G.valid(e); G.next(e)) {
1.50 + int c=cap[e];
1.51 + if (mincut[G.tail(e)] && !mincut[G.head(e)]) min_min_cut_value+=c;
1.52 + if (cut[G.tail(e)] && !cut[G.head(e)]) min_cut_value+=c;
1.53 + if (maxcut[G.tail(e)] && !maxcut[G.head(e)]) max_min_cut_value+=c;
1.54 + }
1.55 +
1.56 + std::cout << "\nChecking the result: " <<std::endl;
1.57 + std::cout << "Flow value: "<< preflow_test.flowValue() << std::endl;
1.58 + std::cout << "Min cut value: "<< min_cut_value << std::endl;
1.59 + std::cout << "Min min cut value: "<< min_min_cut_value << std::endl;
1.60 + std::cout << "Max min cut value: "<< max_min_cut_value <<
1.61 + std::endl;
1.62 +
1.63 + if ( preflow_test.flowValue() == min_cut_value &&
1.64 + min_cut_value == min_min_cut_value &&
1.65 + min_min_cut_value == max_min_cut_value )
1.66 + std::cout << "They are equal. " <<std::endl;
1.67 +
1.68 +
1.69 +
1.70 +
1.71 +
1.72 + Preflow<Graph, int> preflow_test2(G, s, t, cap, flow);
1.73 + std::cout << "\n\nCalling preflow(GEN_FLOW) with the given maximum flow..."<<std::endl;
1.74 + ts.reset();
1.75 + preflow_test2.preflow(preflow_test2.GEN_FLOW);
1.76 + std::cout << "Elapsed time: " << ts << std::endl;
1.77 +
1.78 + Graph::NodeMap<bool> mincut2(G);
1.79 + preflow_test.minMinCut(mincut2);
1.80 + int min_min_cut2_value=0;
1.81 + Graph::NodeMap<bool> cut2(G);
1.82 + preflow_test.minCut(cut2);
1.83 + int min_cut2_value=0;
1.84 + Graph::NodeMap<bool> maxcut2(G);
1.85 + preflow_test.maxMinCut(maxcut2);
1.86 + int max_min_cut2_value=0;
1.87 + for(G.first(e); G.valid(e); G.next(e)) {
1.88 + int c=cap[e];
1.89 + if (mincut2[G.tail(e)] && !mincut2[G.head(e)]) min_min_cut2_value+=c;
1.90 + if (cut2[G.tail(e)] && !cut2[G.head(e)]) min_cut2_value+=c;
1.91 + if (maxcut2[G.tail(e)] && !maxcut2[G.head(e)]) max_min_cut2_value+=c;
1.92 + }
1.93 +
1.94 + std::cout << "\nThe given flow value is "
1.95 + << preflow_test2.flowValue();
1.96 +
1.97 + if ( preflow_test2.flowValue() == min_cut2_value &&
1.98 + min_cut2_value == min_min_cut2_value &&
1.99 + min_min_cut2_value == max_min_cut2_value )
1.100 + std::cout <<", which is equal to all three min cut values."
1.101 + <<std::endl;
1.102 +
1.103 +
1.104 +
1.105 +
1.106 +
1.107 + Graph::EdgeMap<int> flow3(G,0);
1.108 + Preflow<Graph, int> preflow_test3(G, s, t, cap, flow3);
1.109 + std::cout << "\n\nCalling preflowPhase0(PREFLOW) on the constant zero flow..."<<std::endl;
1.110 + ts.reset();
1.111 + preflow_test3.preflowPhase0(preflow_test3.PREFLOW);
1.112 + std::cout << "Elapsed time: " << ts << std::endl;
1.113 + Graph::NodeMap<bool> actcut3(G);
1.114 + std::cout << "\nCalling actMinCut()..."<<std::endl;
1.115 + preflow_test3.actMinCut(actcut3);
1.116 + std::cout << "Calling preflowPhase1() on the given flow..."<<std::endl;
1.117 + ts.reset();
1.118 + preflow_test3.preflowPhase1();
1.119 + std::cout << "Elapsed time: " << ts << std::endl;
1.120 +
1.121 + int act_min_cut3_value=0;
1.122 +
1.123 + Graph::NodeMap<bool> mincut3(G);
1.124 + preflow_test.minMinCut(mincut3);
1.125 + int min_min_cut3_value=0;
1.126 +
1.127 + Graph::NodeMap<bool> cut3(G);
1.128 + preflow_test.minCut(cut3);
1.129 + int min_cut3_value=0;
1.130 +
1.131 + Graph::NodeMap<bool> maxcut3(G);
1.132 + preflow_test.maxMinCut(maxcut3);
1.133 + int max_min_cut3_value=0;
1.134 +
1.135 + for(G.first(e); G.valid(e); G.next(e)) {
1.136 + int c=cap[e];
1.137 + if (mincut3[G.tail(e)] && !mincut3[G.head(e)]) min_min_cut3_value+=c;
1.138 + if (cut3[G.tail(e)] && !cut3[G.head(e)]) min_cut3_value+=c;
1.139 + if (maxcut3[G.tail(e)] && !maxcut3[G.head(e)]) max_min_cut3_value+=c;
1.140 + if (actcut3[G.tail(e)] && !actcut3[G.head(e)]) act_min_cut3_value+=c;
1.141 + }
1.142 +
1.143 + std::cout << "\nThe min cut value given by actMinCut() after phase 0 is "<<
1.144 + act_min_cut3_value;
1.145 +
1.146 + if ( preflow_test3.flowValue() == min_cut3_value &&
1.147 + min_cut3_value == min_min_cut3_value &&
1.148 + min_min_cut3_value == max_min_cut3_value &&
1.149 + max_min_cut3_value == act_min_cut3_value ) {
1.150 + std::cout <<
1.151 + ", which is equal to the given flow value and to all three min cut values after phase 1."
1.152 + <<std::endl;
1.153 + }
1.154 +
1.155 +
1.156 +
1.157 +
1.158 +
1.159 + Graph::EdgeMap<int> flow4(G,0);
1.160 + Preflow<Graph, int> preflow_test4(G, s, t, cap, flow4);
1.161 + std::cout <<
1.162 + "\n\nCalling preflow(PREFLOW) with the constant 0 flow, the result is f..."
1.163 + <<std::endl;
1.164 + preflow_test4.preflow(preflow_test4.PREFLOW);
1.165 +
1.166 + std::cout << "Swapping the source and the target, "<<std::endl;
1.167 + std::cout << "by calling resetSource(t) and resetTarget(s)..."
1.168 + <<std::endl;
1.169 + preflow_test4.resetSource(t);
1.170 + preflow_test4.resetTarget(s);
1.171 +
1.172 + std::cout <<
1.173 + "Calling preflow(PREFLOW) to find a maximum t-s flow starting with flow f..."
1.174 + <<std::endl;
1.175 + preflow_test4.preflow(preflow_test4.PREFLOW);
1.176 +
1.177 + Graph::NodeMap<bool> mincut4(G);
1.178 + preflow_test4.minMinCut(mincut4);
1.179 + int min_min_cut4_value=0;
1.180 + Graph::NodeMap<bool> cut4(G);
1.181 + preflow_test4.minCut(cut4);
1.182 + int min_cut4_value=0;
1.183 + Graph::NodeMap<bool> maxcut4(G);
1.184 + preflow_test4.maxMinCut(maxcut4);
1.185 + int max_min_cut4_value=0;
1.186 + for(G.first(e); G.valid(e); G.next(e)) {
1.187 + int c=cap[e];
1.188 + if (mincut4[G.tail(e)] && !mincut4[G.head(e)]) min_min_cut4_value+=c;
1.189 + if (cut4[G.tail(e)] && !cut4[G.head(e)]) min_cut4_value+=c;
1.190 + if (maxcut4[G.tail(e)] && !maxcut4[G.head(e)]) max_min_cut4_value+=c;
1.191 + }
1.192 +
1.193 + std::cout << "\nThe given flow value is "
1.194 + << preflow_test4.flowValue();
1.195 +
1.196 + if ( preflow_test4.flowValue() == min_cut4_value &&
1.197 + min_cut4_value == min_min_cut4_value &&
1.198 + min_min_cut4_value == max_min_cut4_value )
1.199 + std::cout <<", which is equal to all three min cut values."
1.200 + <<std::endl;
1.201 +
1.202 +
1.203 +
1.204 +
1.205 + Graph::EdgeMap<int> flow5(G,0);
1.206 + std::cout << "Resetting the stored flow to constant zero, by calling resetFlow..."
1.207 + <<std::endl;
1.208 + preflow_test4.resetFlow(flow5);
1.209 + std::cout <<
1.210 + "Calling preflow(GEN_FLOW) to find a maximum t-s flow "<<std::endl;
1.211 + std::cout <<
1.212 + "starting with this constant zero flow..." <<std::endl;
1.213 + preflow_test4.preflow(preflow_test4.GEN_FLOW);
1.214 +
1.215 + Graph::NodeMap<bool> mincut5(G);
1.216 + preflow_test4.minMinCut(mincut5);
1.217 + int min_min_cut5_value=0;
1.218 + Graph::NodeMap<bool> cut5(G);
1.219 + preflow_test4.minCut(cut5);
1.220 + int min_cut5_value=0;
1.221 + Graph::NodeMap<bool> maxcut5(G);
1.222 + preflow_test4.maxMinCut(maxcut5);
1.223 + int max_min_cut5_value=0;
1.224 + for(G.first(e); G.valid(e); G.next(e)) {
1.225 + int c=cap[e];
1.226 + if (mincut5[G.tail(e)] && !mincut5[G.head(e)]) min_min_cut5_value+=c;
1.227 + if (cut5[G.tail(e)] && !cut5[G.head(e)]) min_cut5_value+=c;
1.228 + if (maxcut5[G.tail(e)] && !maxcut5[G.head(e)]) max_min_cut5_value+=c;
1.229 + }
1.230 +
1.231 + std::cout << "\nThe given flow value is "
1.232 + << preflow_test4.flowValue();
1.233 +
1.234 + if ( preflow_test4.flowValue() == min_cut5_value &&
1.235 + min_cut5_value == min_min_cut5_value &&
1.236 + min_min_cut5_value == max_min_cut5_value )
1.237 + std::cout <<", which is equal to all three min cut values."
1.238 + <<std::endl<<std::endl;
1.239 +
1.240 +
1.241 + return 0;
1.242 +}