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