|
jacint@131
|
1 |
#include <iostream>
|
|
jacint@131
|
2 |
#include <fstream>
|
|
jacint@131
|
3 |
|
|
jacint@131
|
4 |
#include <j_graph.h>
|
|
jacint@131
|
5 |
#include <dimacs_jgraph.hh>
|
|
jacint@131
|
6 |
#include <preflow_jgraph.h>
|
|
jacint@131
|
7 |
#include <time_measure.h>
|
|
jacint@131
|
8 |
|
|
jacint@131
|
9 |
using namespace hugo;
|
|
jacint@131
|
10 |
|
|
jacint@131
|
11 |
// Use a DIMACS max flow file as stdin.
|
|
jacint@131
|
12 |
// read_dimacs_demo < dimacs_max_flow_file
|
|
jacint@131
|
13 |
int main(int, char **) {
|
|
jacint@131
|
14 |
typedef JGraph::TrivNodeIt TrivNodeIt;
|
|
jacint@131
|
15 |
typedef JGraph::EdgeIt EdgeIt;
|
|
jacint@131
|
16 |
|
|
jacint@131
|
17 |
JGraph G;
|
|
jacint@131
|
18 |
TrivNodeIt s, t;
|
|
jacint@131
|
19 |
JGraph::EdgeMap<int> cap(G);
|
|
jacint@131
|
20 |
readDimacsMaxFlow(std::cin, G, s, t, cap);
|
|
jacint@131
|
21 |
|
|
jacint@131
|
22 |
std::cout << "preflow demo jacint ..." << std::endl;
|
|
jacint@131
|
23 |
|
|
jacint@131
|
24 |
double mintime=1000000;
|
|
jacint@131
|
25 |
|
|
jacint@131
|
26 |
for ( int i=1; i!=11; ++i ) {
|
|
jacint@131
|
27 |
double pre_time=currTime();
|
|
jacint@131
|
28 |
preflow<JGraph, int> max_flow_test(G, s, t, cap);
|
|
jacint@131
|
29 |
double post_time=currTime();
|
|
jacint@131
|
30 |
if ( mintime > post_time-pre_time ) mintime = post_time-pre_time;
|
|
jacint@131
|
31 |
}
|
|
jacint@131
|
32 |
|
|
jacint@131
|
33 |
double pre_time=currTime();
|
|
jacint@131
|
34 |
preflow<JGraph, int> max_flow_test(G, s, t, cap);
|
|
jacint@131
|
35 |
double post_time=currTime();
|
|
jacint@131
|
36 |
|
|
jacint@131
|
37 |
JGraph::NodeMap<bool> cut(G);
|
|
jacint@131
|
38 |
max_flow_test.minCut(cut);
|
|
jacint@131
|
39 |
int min_cut_value=0;
|
|
jacint@131
|
40 |
for(EdgeIt e=G.firstEdge(); e; G.next(e)) {
|
|
jacint@131
|
41 |
if (cut.get(G.tail(e)) && !cut.get(G.head(e))) min_cut_value+=cap.get(e);
|
|
jacint@131
|
42 |
}
|
|
jacint@131
|
43 |
|
|
jacint@131
|
44 |
JGraph::NodeMap<bool> cut1(G);
|
|
jacint@131
|
45 |
max_flow_test.minMinCut(cut1);
|
|
jacint@131
|
46 |
int min_min_cut_value=0;
|
|
jacint@131
|
47 |
for(EdgeIt e=G.firstEdge(); e; G.next(e)) {
|
|
jacint@131
|
48 |
if (cut.get(G.tail(e)) && !cut.get(G.head(e)))
|
|
jacint@131
|
49 |
min_min_cut_value+=cap.get(e);
|
|
jacint@131
|
50 |
}
|
|
jacint@131
|
51 |
|
|
jacint@131
|
52 |
JGraph::NodeMap<bool> cut2(G);
|
|
jacint@131
|
53 |
max_flow_test.maxMinCut(cut2);
|
|
jacint@131
|
54 |
int max_min_cut_value=0;
|
|
jacint@131
|
55 |
for(EdgeIt e=G.firstEdge(); e; G.next(e)) {
|
|
jacint@131
|
56 |
if (cut2.get(G.tail(e)) && !cut2.get(G.head(e)))
|
|
jacint@131
|
57 |
max_min_cut_value+=cap.get(e);
|
|
jacint@131
|
58 |
}
|
|
jacint@131
|
59 |
|
|
jacint@131
|
60 |
std::cout << "min time of 10 runs: " << mintime << " sec"<< std::endl;
|
|
jacint@131
|
61 |
std::cout << "phase 0: " << max_flow_test.time-pre_time
|
|
jacint@131
|
62 |
<< " sec"<< std::endl;
|
|
jacint@131
|
63 |
std::cout << "phase 1: " << post_time-max_flow_test.time
|
|
jacint@131
|
64 |
<< " sec"<< std::endl;
|
|
jacint@131
|
65 |
std::cout << "flow value: "<< max_flow_test.maxFlow() << std::endl;
|
|
jacint@131
|
66 |
std::cout << "min cut value: "<< min_cut_value << std::endl;
|
|
jacint@131
|
67 |
std::cout << "min min cut value: "<< min_min_cut_value << std::endl;
|
|
jacint@131
|
68 |
std::cout << "max min cut value: "<< max_min_cut_value <<
|
|
jacint@131
|
69 |
std::endl<< std::endl;
|
|
jacint@131
|
70 |
|
|
jacint@131
|
71 |
return 0;
|
|
jacint@131
|
72 |
}
|