1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/jacint/preflow.cc Sat Feb 21 21:01:22 2004 +0000
1.3 @@ -0,0 +1,66 @@
1.4 +#include <iostream>
1.5 +#include <fstream>
1.6 +
1.7 +#include <list_graph.hh>
1.8 +#include <dimacs.hh>
1.9 +#include <preflow.h>
1.10 +#include <time_measure.h>
1.11 +
1.12 +using namespace hugo;
1.13 +
1.14 +// Use a DIMACS max flow file as stdin.
1.15 +// read_dimacs_demo < dimacs_max_flow_file
1.16 +int main(int, char **) {
1.17 + typedef ListGraph::NodeIt NodeIt;
1.18 + typedef ListGraph::EachEdgeIt EachEdgeIt;
1.19 +
1.20 + ListGraph G;
1.21 + NodeIt s, t;
1.22 + ListGraph::EdgeMap<int> cap(G);
1.23 + readDimacsMaxFlow(std::cin, G, s, t, cap);
1.24 +
1.25 + std::cout << "preflow demo ..." << std::endl;
1.26 +
1.27 + double mintime=1000000;
1.28 +
1.29 + for ( int i=1; i!=11; ++i ) {
1.30 + double pre_time=currTime();
1.31 + preflow<ListGraph, int> max_flow_test(G, s, t, cap);
1.32 + double post_time=currTime();
1.33 + if ( mintime > post_time-pre_time ) mintime = post_time-pre_time;
1.34 + }
1.35 +
1.36 + preflow<ListGraph, int> max_flow_test(G, s, t, cap);
1.37 +
1.38 + ListGraph::NodeMap<bool> cut(G);
1.39 + max_flow_test.minCut(cut);
1.40 + int min_cut_value=0;
1.41 + for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
1.42 + if (cut.get(G.tail(e)) && !cut.get(G.head(e))) min_cut_value+=cap.get(e);
1.43 + }
1.44 +
1.45 + ListGraph::NodeMap<bool> cut1(G);
1.46 + max_flow_test.minMinCut(cut1);
1.47 + int min_min_cut_value=0;
1.48 + for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
1.49 + if (cut.get(G.tail(e)) && !cut.get(G.head(e)))
1.50 + min_min_cut_value+=cap.get(e);
1.51 + }
1.52 +
1.53 + ListGraph::NodeMap<bool> cut2(G);
1.54 + max_flow_test.maxMinCut(cut2);
1.55 + int max_min_cut_value=0;
1.56 + for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
1.57 + if (cut2.get(G.tail(e)) && !cut2.get(G.head(e)))
1.58 + max_min_cut_value+=cap.get(e);
1.59 + }
1.60 +
1.61 + std::cout << "min time of 10 runs: " << mintime << " sec"<< std::endl;
1.62 + std::cout << "flow value: "<< max_flow_test.maxFlow() << std::endl;
1.63 + std::cout << "min cut value: "<< min_cut_value << std::endl;
1.64 + std::cout << "min min cut value: "<< min_min_cut_value << std::endl;
1.65 + std::cout << "max min cut value: "<< max_min_cut_value <<
1.66 + std::endl<< std::endl;
1.67 +
1.68 + return 0;
1.69 +}