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