1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/jacint/preflow_res_comp.cc Fri Apr 23 21:26:32 2004 +0000
1.3 @@ -0,0 +1,125 @@
1.4 +/*
1.5 +The only difference between preflow.h and preflow_res.h is that the latter
1.6 +uses the ResGraphWrapper, while the first does not. (Bfs is implemented by
1.7 +hand in both.) This test program runs Preflow and PreflowRes on the same
1.8 +graph, tests the result of these implementations and writes the running time
1.9 +of them. */
1.10 +#include <iostream>
1.11 +
1.12 +#include <smart_graph.h>
1.13 +#include <dimacs.h>
1.14 +#include <preflow.h>
1.15 +#include <preflow_res.h>
1.16 +#include <time_measure.h>
1.17 +
1.18 +using namespace hugo;
1.19 +
1.20 +int main(int, char **) {
1.21 +
1.22 + typedef SmartGraph Graph;
1.23 +
1.24 + typedef Graph::Node Node;
1.25 + typedef Graph::EdgeIt EdgeIt;
1.26 +
1.27 + Graph G;
1.28 + Node s, t;
1.29 + Graph::EdgeMap<int> cap(G);
1.30 + readDimacsMaxFlow(std::cin, G, s, t, cap);
1.31 + Timer ts;
1.32 +
1.33 + std::cout <<
1.34 + "\n In which way are we faster: using ResGraphWrapper or not?"
1.35 + <<std::endl;
1.36 + std::cout <<
1.37 + "\n Running preflow.h on a graph with " <<
1.38 + G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
1.39 + << std::endl<<std::endl;
1.40 +
1.41 +
1.42 +
1.43 + Graph::EdgeMap<int> flow(G,0);
1.44 + Preflow<Graph, int> max_flow_test(G, s, t, cap, flow, 1);
1.45 + ts.reset();
1.46 + max_flow_test.run();
1.47 + std::cout << "Elapsed time NOT using the ResGraphWrapper: " << std::endl
1.48 + <<ts << std::endl;
1.49 +
1.50 + Graph::NodeMap<bool> mincut(G);
1.51 + max_flow_test.minMinCut(mincut);
1.52 + int min_min_cut_value=0;
1.53 + EdgeIt e;
1.54 + for(G.first(e); G.valid(e); G.next(e)) {
1.55 + if (mincut[G.tail(e)] && !mincut[G.head(e)]) min_min_cut_value+=cap[e];
1.56 + }
1.57 +
1.58 + Graph::NodeMap<bool> cut(G);
1.59 + max_flow_test.minCut(cut);
1.60 + int min_cut_value=0;
1.61 + for(G.first(e); G.valid(e); G.next(e)) {
1.62 + if (cut[G.tail(e)] && !cut[G.head(e)])
1.63 + min_cut_value+=cap[e];
1.64 + }
1.65 +
1.66 + Graph::NodeMap<bool> maxcut(G);
1.67 + max_flow_test.maxMinCut(maxcut);
1.68 + int max_min_cut_value=0;
1.69 + for(G.first(e); G.valid(e); G.next(e)) {
1.70 + if (maxcut[G.tail(e)] && !maxcut[G.head(e)])
1.71 + max_min_cut_value+=cap[e];
1.72 + }
1.73 +
1.74 + std::cout << "\n Checking the result: " <<std::endl;
1.75 + std::cout << "Flow value: "<< max_flow_test.flowValue() << std::endl;
1.76 + std::cout << "Min cut value: "<< min_cut_value << std::endl;
1.77 + std::cout << "Min min cut value: "<< min_min_cut_value << std::endl;
1.78 + std::cout << "Max min cut value: "<< max_min_cut_value <<
1.79 + std::endl;
1.80 +
1.81 + if ( max_flow_test.flowValue() == min_cut_value &&
1.82 + min_cut_value == min_min_cut_value &&
1.83 + min_min_cut_value == max_min_cut_value )
1.84 + std::cout << "They are equal! " <<std::endl<< std::endl<<"\n";
1.85 +
1.86 + Graph::EdgeMap<int> flow2(G,0);
1.87 + PreflowRes<Graph, int> max_flow_test2(G, s, t, cap, flow2, 1);
1.88 + ts.reset();
1.89 + max_flow_test2.run();
1.90 + std::cout << "Elapsed time using the ResGraphWrapper: " << std::endl
1.91 + << ts << std::endl;
1.92 +
1.93 + Graph::NodeMap<bool> mincut2(G);
1.94 + max_flow_test2.minMinCut(mincut2);
1.95 + int min_min_cut_value2=0;
1.96 + for(G.first(e); G.valid(e); G.next(e)) {
1.97 + if (mincut2[G.tail(e)] && !mincut2[G.head(e)]) min_min_cut_value2+=cap[e];
1.98 + }
1.99 +
1.100 + Graph::NodeMap<bool> cut2(G);
1.101 + max_flow_test2.minCut(cut2);
1.102 + int min_cut_value2=0;
1.103 + for(G.first(e); G.valid(e); G.next(e)) {
1.104 + if (cut2[G.tail(e)] && !cut2[G.head(e)])
1.105 + min_cut_value2+=cap[e];
1.106 + }
1.107 +
1.108 + Graph::NodeMap<bool> maxcut2(G);
1.109 + max_flow_test2.maxMinCut(maxcut2);
1.110 + int max_min_cut_value2=0;
1.111 + for(G.first(e); G.valid(e); G.next(e)) {
1.112 + if (maxcut2[G.tail(e)] && !maxcut2[G.head(e)])
1.113 + max_min_cut_value2+=cap[e];
1.114 + }
1.115 +
1.116 + std::cout << "\n Checking the result: " <<std::endl;
1.117 + std::cout << "Flow value: "<< max_flow_test2.flowValue() << std::endl;
1.118 + std::cout << "Min cut value: "<< min_cut_value2 << std::endl;
1.119 + std::cout << "Min min cut value: "<< min_min_cut_value2 << std::endl;
1.120 + std::cout << "Max min cut value: "<< max_min_cut_value2 <<
1.121 + std::endl;
1.122 + if ( max_flow_test.flowValue() == min_cut_value &&
1.123 + min_cut_value == min_min_cut_value &&
1.124 + min_min_cut_value == max_min_cut_value )
1.125 + std::cout << "They are equal! " <<std::endl<<"/n";
1.126 +
1.127 + return 0;
1.128 +}