1 /* |
|
2 The only difference between preflow.h and preflow_res.h is that the latter |
|
3 uses the ResGraphWrapper, while the first does not. (Bfs is implemented by |
|
4 hand in both.) This test program runs Preflow and PreflowRes on the same |
|
5 graph, tests the result of these implementations and writes the running time |
|
6 of them. */ |
|
7 #include <iostream> |
|
8 |
|
9 #include <smart_graph.h> |
|
10 #include <dimacs.h> |
|
11 #include <preflow_excess.h> |
|
12 #include <time_measure.h> |
|
13 |
|
14 using namespace lemon; |
|
15 |
|
16 int main(int, char **) { |
|
17 |
|
18 typedef SmartGraph Graph; |
|
19 |
|
20 typedef Graph::Node Node; |
|
21 typedef Graph::EdgeIt EdgeIt; |
|
22 |
|
23 Graph G; |
|
24 Node s, t; |
|
25 Graph::EdgeMap<int> cap(G); |
|
26 readDimacsMaxFlow(std::cin, G, s, t, cap); |
|
27 Timer ts; |
|
28 |
|
29 std::cout << |
|
30 "\n Are we slower?" |
|
31 <<std::endl; |
|
32 std::cout << |
|
33 "\n Running preflow.h on a graph with " << |
|
34 G.nodeNum() << " nodes and " << G.edgeNum() << " edges..." |
|
35 << std::endl<<std::endl; |
|
36 |
|
37 |
|
38 |
|
39 |
|
40 |
|
41 |
|
42 |
|
43 Graph::EdgeMap<int> flow(G,0); |
|
44 Preflow<Graph, int> max_flow_test(G, s, t, cap, flow, 0 , 0); |
|
45 ts.reset(); |
|
46 max_flow_test.run(); |
|
47 std::cout << "Elapsed time from a preflow: " << std::endl |
|
48 <<ts << std::endl; |
|
49 |
|
50 Graph::NodeMap<bool> mincut(G); |
|
51 max_flow_test.minMinCut(mincut); |
|
52 int min_min_cut_value=0; |
|
53 EdgeIt e; |
|
54 for(G.first(e); G.valid(e); G.next(e)) { |
|
55 if (mincut[G.source(e)] && !mincut[G.target(e)]) min_min_cut_value+=cap[e]; |
|
56 } |
|
57 |
|
58 Graph::NodeMap<bool> cut(G); |
|
59 max_flow_test.minCut(cut); |
|
60 int min_cut_value=0; |
|
61 for(G.first(e); G.valid(e); G.next(e)) { |
|
62 if (cut[G.source(e)] && !cut[G.target(e)]) |
|
63 min_cut_value+=cap[e]; |
|
64 } |
|
65 |
|
66 Graph::NodeMap<bool> maxcut(G); |
|
67 max_flow_test.maxMinCut(maxcut); |
|
68 int max_min_cut_value=0; |
|
69 for(G.first(e); G.valid(e); G.next(e)) { |
|
70 if (maxcut[G.source(e)] && !maxcut[G.target(e)]) |
|
71 max_min_cut_value+=cap[e]; |
|
72 } |
|
73 |
|
74 std::cout << "\n Checking the result: " <<std::endl; |
|
75 std::cout << "Flow value: "<< max_flow_test.flowValue() << std::endl; |
|
76 std::cout << "Min cut value: "<< min_cut_value << std::endl; |
|
77 std::cout << "Min min cut value: "<< min_min_cut_value << std::endl; |
|
78 std::cout << "Max min cut value: "<< max_min_cut_value << |
|
79 std::endl; |
|
80 |
|
81 if ( max_flow_test.flowValue() == min_cut_value && |
|
82 min_cut_value == min_min_cut_value && |
|
83 min_min_cut_value == max_min_cut_value ) |
|
84 std::cout << "They are equal! " <<std::endl<< std::endl<<"\n"; |
|
85 |
|
86 |
|
87 |
|
88 |
|
89 |
|
90 |
|
91 Graph::EdgeMap<int> flow2(G,0); |
|
92 Preflow<Graph, int> max_flow_test2(G, s, t, cap, flow2, 0 , 1); |
|
93 ts.reset(); |
|
94 max_flow_test2.run(); |
|
95 std::cout << "Elapsed time from a flow: " << std::endl |
|
96 << ts << std::endl; |
|
97 |
|
98 Graph::NodeMap<bool> mincut2(G); |
|
99 max_flow_test2.minMinCut(mincut2); |
|
100 int min_min_cut_value2=0; |
|
101 for(G.first(e); G.valid(e); G.next(e)) { |
|
102 if (mincut2[G.source(e)] && !mincut2[G.target(e)]) min_min_cut_value2+=cap[e]; |
|
103 } |
|
104 |
|
105 Graph::NodeMap<bool> cut2(G); |
|
106 max_flow_test2.minCut(cut2); |
|
107 int min_cut_value2=0; |
|
108 for(G.first(e); G.valid(e); G.next(e)) { |
|
109 if (cut2[G.source(e)] && !cut2[G.target(e)]) |
|
110 min_cut_value2+=cap[e]; |
|
111 } |
|
112 |
|
113 Graph::NodeMap<bool> maxcut2(G); |
|
114 max_flow_test2.maxMinCut(maxcut2); |
|
115 int max_min_cut_value2=0; |
|
116 for(G.first(e); G.valid(e); G.next(e)) { |
|
117 if (maxcut2[G.source(e)] && !maxcut2[G.target(e)]) |
|
118 max_min_cut_value2+=cap[e]; |
|
119 } |
|
120 |
|
121 std::cout << "\n Checking the result: " <<std::endl; |
|
122 std::cout << "Flow value: "<< max_flow_test2.flowValue() << std::endl; |
|
123 std::cout << "Min cut value: "<< min_cut_value2 << std::endl; |
|
124 std::cout << "Min min cut value: "<< min_min_cut_value2 << std::endl; |
|
125 std::cout << "Max min cut value: "<< max_min_cut_value2 << |
|
126 std::endl; |
|
127 if ( max_flow_test.flowValue() == min_cut_value && |
|
128 min_cut_value == min_min_cut_value && |
|
129 min_min_cut_value == max_min_cut_value ) |
|
130 std::cout << "They are equal! " <<std::endl; |
|
131 |
|
132 |
|
133 |
|
134 |
|
135 |
|
136 Graph::EdgeMap<int> flow3(G,0); |
|
137 Preflow<Graph, int> max_flow_test3(G, s, t, cap, flow3, 1 , 1); |
|
138 ts.reset(); |
|
139 max_flow_test3.run(); |
|
140 std::cout << "Elapsed time from a const zero flow: " << std::endl |
|
141 <<ts << std::endl; |
|
142 |
|
143 Graph::NodeMap<bool> mincut3(G); |
|
144 max_flow_test3.minMinCut(mincut3); |
|
145 int min_min_cut_value3=0; |
|
146 for(G.first(e); G.valid(e); G.next(e)) { |
|
147 if (mincut3[G.source(e)] && !mincut3[G.target(e)]) min_min_cut_value3+=cap[e]; |
|
148 } |
|
149 |
|
150 Graph::NodeMap<bool> cut3(G); |
|
151 max_flow_test3.minCut(cut3); |
|
152 int min_cut_value3=0; |
|
153 for(G.first(e); G.valid(e); G.next(e)) { |
|
154 if (cut3[G.source(e)] && !cut3[G.target(e)]) |
|
155 min_cut_value3+=cap[e]; |
|
156 } |
|
157 |
|
158 Graph::NodeMap<bool> maxcut3(G); |
|
159 max_flow_test3.maxMinCut(maxcut3); |
|
160 int max_min_cut_value3=0; |
|
161 for(G.first(e); G.valid(e); G.next(e)) { |
|
162 if (maxcut3[G.source(e)] && !maxcut3[G.target(e)]) |
|
163 max_min_cut_value3+=cap[e]; |
|
164 } |
|
165 |
|
166 std::cout << "\n Checking the result: " <<std::endl; |
|
167 std::cout << "Flow value: "<< max_flow_test3.flowValue() << std::endl; |
|
168 std::cout << "Min cut value: "<< min_cut_value3 << std::endl; |
|
169 std::cout << "Min min cut value: "<< min_min_cut_value3 << std::endl; |
|
170 std::cout << "Max min cut value: "<< max_min_cut_value3 << |
|
171 std::endl; |
|
172 |
|
173 if ( max_flow_test3.flowValue() == min_cut_value3 && |
|
174 min_cut_value3 == min_min_cut_value3 && |
|
175 min_min_cut_value3 == max_min_cut_value3 ) |
|
176 std::cout << "They are equal! " <<std::endl<< std::endl<<"\n"; |
|
177 |
|
178 return 0; |
|
179 } |
|