1 #include <iostream> |
|
2 |
|
3 #include <smart_graph.h> |
|
4 #include <dimacs.h> |
|
5 #include <preflow.h> |
|
6 #include <time_measure.h> |
|
7 |
|
8 using namespace lemon; |
|
9 |
|
10 int main(int, char **) { |
|
11 |
|
12 typedef SmartGraph Graph; |
|
13 |
|
14 typedef Graph::Node Node; |
|
15 typedef Graph::EdgeIt EdgeIt; |
|
16 |
|
17 Graph G; |
|
18 Node s, t; |
|
19 Graph::EdgeMap<int> cap(G); |
|
20 readDimacsMaxFlow(std::cin, G, s, t, cap); |
|
21 Timer ts; |
|
22 bool error=false; |
|
23 |
|
24 std::cout << |
|
25 "\n Testing preflow.h on a graph with " << |
|
26 G.nodeNum() << " nodes and " << G.edgeNum() << " edges..." |
|
27 << std::endl; |
|
28 |
|
29 |
|
30 Graph::EdgeMap<int> flow(G,0); |
|
31 Preflow<Graph, int> preflow_test(G, s, t, cap, flow); |
|
32 std::cout << "\nCalling run() (flow must be constant zero)..."<<std::endl; |
|
33 ts.reset(); |
|
34 preflow_test.run(); |
|
35 std::cout << "Elapsed time: " << ts << std::endl; |
|
36 |
|
37 Graph::NodeMap<bool> mincut(G); |
|
38 preflow_test.minMinCut(mincut); |
|
39 int min_min_cut_value=0; |
|
40 Graph::NodeMap<bool> cut(G); |
|
41 preflow_test.minCut(cut); |
|
42 int min_cut_value=0; |
|
43 Graph::NodeMap<bool> maxcut(G); |
|
44 preflow_test.maxMinCut(maxcut); |
|
45 int max_min_cut_value=0; |
|
46 EdgeIt e; |
|
47 for(G.first(e); G.valid(e); G.next(e)) { |
|
48 int c=cap[e]; |
|
49 if (mincut[G.source(e)] && !mincut[G.target(e)]) min_min_cut_value+=c; |
|
50 if (cut[G.source(e)] && !cut[G.target(e)]) min_cut_value+=c; |
|
51 if (maxcut[G.source(e)] && !maxcut[G.target(e)]) max_min_cut_value+=c; |
|
52 } |
|
53 |
|
54 std::cout << "\nChecking the result: " <<std::endl; |
|
55 std::cout << "Flow value: "<< preflow_test.flowValue() << std::endl; |
|
56 std::cout << "Min cut value: "<< min_cut_value << std::endl; |
|
57 std::cout << "Min min cut value: "<< min_min_cut_value << std::endl; |
|
58 std::cout << "Max min cut value: "<< max_min_cut_value << |
|
59 std::endl; |
|
60 |
|
61 if ( preflow_test.flowValue() == min_cut_value && |
|
62 min_cut_value == min_min_cut_value && |
|
63 min_min_cut_value == max_min_cut_value ) |
|
64 std::cout << "They are equal. " <<std::endl; |
|
65 else { |
|
66 std::cout << "ERROR! They are not equal! " <<std::endl; |
|
67 error=true; |
|
68 } |
|
69 |
|
70 |
|
71 |
|
72 Preflow<Graph, int> preflow_test2(G, s, t, cap, flow); |
|
73 std::cout << "\n\nCalling preflow(GEN_FLOW) with the given maximum flow..."<<std::endl; |
|
74 ts.reset(); |
|
75 preflow_test2.preflow(preflow_test2.GEN_FLOW); |
|
76 std::cout << "Elapsed time: " << ts << std::endl; |
|
77 |
|
78 Graph::NodeMap<bool> mincut2(G); |
|
79 preflow_test.minMinCut(mincut2); |
|
80 int min_min_cut2_value=0; |
|
81 Graph::NodeMap<bool> cut2(G); |
|
82 preflow_test.minCut(cut2); |
|
83 int min_cut2_value=0; |
|
84 Graph::NodeMap<bool> maxcut2(G); |
|
85 preflow_test.maxMinCut(maxcut2); |
|
86 int max_min_cut2_value=0; |
|
87 for(G.first(e); G.valid(e); G.next(e)) { |
|
88 int c=cap[e]; |
|
89 if (mincut2[G.source(e)] && !mincut2[G.target(e)]) min_min_cut2_value+=c; |
|
90 if (cut2[G.source(e)] && !cut2[G.target(e)]) min_cut2_value+=c; |
|
91 if (maxcut2[G.source(e)] && !maxcut2[G.target(e)]) max_min_cut2_value+=c; |
|
92 } |
|
93 |
|
94 std::cout << "\nThe given flow value is " |
|
95 << preflow_test2.flowValue(); |
|
96 |
|
97 if ( preflow_test2.flowValue() == min_cut2_value && |
|
98 min_cut2_value == min_min_cut2_value && |
|
99 min_min_cut2_value == max_min_cut2_value ) |
|
100 std::cout <<", which is equal to all three min cut values." |
|
101 <<std::endl; |
|
102 else { |
|
103 std::cout << "ERROR! It is not equal to all three min cut values! " |
|
104 <<std::endl; |
|
105 error=true; |
|
106 } |
|
107 |
|
108 |
|
109 |
|
110 |
|
111 Graph::EdgeMap<int> flow3(G,0); |
|
112 Preflow<Graph, int> preflow_test3(G, s, t, cap, flow3); |
|
113 std::cout << "\n\nCalling preflowPhase0(PREFLOW) on the constant zero flow..."<<std::endl; |
|
114 ts.reset(); |
|
115 preflow_test3.preflowPhase0(preflow_test3.PREFLOW); |
|
116 std::cout << "Elapsed time: " << ts << std::endl; |
|
117 Graph::NodeMap<bool> actcut3(G); |
|
118 std::cout << "\nCalling actMinCut()..."<<std::endl; |
|
119 preflow_test3.actMinCut(actcut3); |
|
120 std::cout << "Calling preflowPhase1() on the given flow..."<<std::endl; |
|
121 ts.reset(); |
|
122 preflow_test3.preflowPhase1(); |
|
123 std::cout << "Elapsed time: " << ts << std::endl; |
|
124 |
|
125 int act_min_cut3_value=0; |
|
126 |
|
127 Graph::NodeMap<bool> mincut3(G); |
|
128 preflow_test.minMinCut(mincut3); |
|
129 int min_min_cut3_value=0; |
|
130 |
|
131 Graph::NodeMap<bool> cut3(G); |
|
132 preflow_test.minCut(cut3); |
|
133 int min_cut3_value=0; |
|
134 |
|
135 Graph::NodeMap<bool> maxcut3(G); |
|
136 preflow_test.maxMinCut(maxcut3); |
|
137 int max_min_cut3_value=0; |
|
138 |
|
139 for(G.first(e); G.valid(e); G.next(e)) { |
|
140 int c=cap[e]; |
|
141 if (mincut3[G.source(e)] && !mincut3[G.target(e)]) min_min_cut3_value+=c; |
|
142 if (cut3[G.source(e)] && !cut3[G.target(e)]) min_cut3_value+=c; |
|
143 if (maxcut3[G.source(e)] && !maxcut3[G.target(e)]) max_min_cut3_value+=c; |
|
144 if (actcut3[G.source(e)] && !actcut3[G.target(e)]) act_min_cut3_value+=c; |
|
145 } |
|
146 |
|
147 std::cout << "\nThe min cut value given by actMinCut() after phase 0 is "<< |
|
148 act_min_cut3_value; |
|
149 |
|
150 if ( preflow_test3.flowValue() == min_cut3_value && |
|
151 min_cut3_value == min_min_cut3_value && |
|
152 min_min_cut3_value == max_min_cut3_value && |
|
153 max_min_cut3_value == act_min_cut3_value ) { |
|
154 std::cout << |
|
155 ", which is equal to the given flow value and to all three min cut values after phase 1." |
|
156 <<std::endl; |
|
157 } |
|
158 else { |
|
159 std::cout << |
|
160 "ERROR! It is not equal to the given flow value and to all three min cut values after phase 1! " |
|
161 <<std::endl; |
|
162 error=true; |
|
163 } |
|
164 |
|
165 |
|
166 |
|
167 |
|
168 |
|
169 Graph::EdgeMap<int> flow4(G,0); |
|
170 Preflow<Graph, int> preflow_test4(G, s, t, cap, flow4); |
|
171 std::cout << |
|
172 "\n\nCalling preflow(PREFLOW) with the constant 0 flow, the result is f..." |
|
173 <<std::endl; |
|
174 preflow_test4.preflow(preflow_test4.PREFLOW); |
|
175 |
|
176 std::cout << "Swapping the source and the target, "<<std::endl; |
|
177 std::cout << "by calling resetSource(t) and resetTarget(s)..." |
|
178 <<std::endl; |
|
179 preflow_test4.resetSource(t); |
|
180 preflow_test4.resetTarget(s); |
|
181 |
|
182 std::cout << |
|
183 "Calling preflow(PREFLOW) to find a maximum t-s flow starting with flow f..." |
|
184 <<std::endl; |
|
185 preflow_test4.preflow(preflow_test4.PREFLOW); |
|
186 |
|
187 Graph::NodeMap<bool> mincut4(G); |
|
188 preflow_test4.minMinCut(mincut4); |
|
189 int min_min_cut4_value=0; |
|
190 Graph::NodeMap<bool> cut4(G); |
|
191 preflow_test4.minCut(cut4); |
|
192 int min_cut4_value=0; |
|
193 Graph::NodeMap<bool> maxcut4(G); |
|
194 preflow_test4.maxMinCut(maxcut4); |
|
195 int max_min_cut4_value=0; |
|
196 for(G.first(e); G.valid(e); G.next(e)) { |
|
197 int c=cap[e]; |
|
198 if (mincut4[G.source(e)] && !mincut4[G.target(e)]) min_min_cut4_value+=c; |
|
199 if (cut4[G.source(e)] && !cut4[G.target(e)]) min_cut4_value+=c; |
|
200 if (maxcut4[G.source(e)] && !maxcut4[G.target(e)]) max_min_cut4_value+=c; |
|
201 } |
|
202 |
|
203 std::cout << "\nThe given flow value is " |
|
204 << preflow_test4.flowValue(); |
|
205 |
|
206 if ( preflow_test4.flowValue() == min_cut4_value && |
|
207 min_cut4_value == min_min_cut4_value && |
|
208 min_min_cut4_value == max_min_cut4_value ) |
|
209 std::cout <<", which is equal to all three min cut values." |
|
210 <<std::endl; |
|
211 else { |
|
212 std::cout << "ERROR! It is not equal to all three min cut values! " |
|
213 <<std::endl; |
|
214 error=true; |
|
215 } |
|
216 |
|
217 |
|
218 |
|
219 |
|
220 Graph::EdgeMap<int> flow5(G,0); |
|
221 std::cout << "Resetting the stored flow to constant zero, by calling resetFlow..." |
|
222 <<std::endl; |
|
223 preflow_test4.resetFlow(flow5); |
|
224 std::cout << |
|
225 "Calling preflow(GEN_FLOW) to find a maximum t-s flow "<<std::endl; |
|
226 std::cout << |
|
227 "starting with this constant zero flow..." <<std::endl; |
|
228 preflow_test4.preflow(preflow_test4.GEN_FLOW); |
|
229 |
|
230 Graph::NodeMap<bool> mincut5(G); |
|
231 preflow_test4.minMinCut(mincut5); |
|
232 int min_min_cut5_value=0; |
|
233 Graph::NodeMap<bool> cut5(G); |
|
234 preflow_test4.minCut(cut5); |
|
235 int min_cut5_value=0; |
|
236 Graph::NodeMap<bool> maxcut5(G); |
|
237 preflow_test4.maxMinCut(maxcut5); |
|
238 int max_min_cut5_value=0; |
|
239 for(G.first(e); G.valid(e); G.next(e)) { |
|
240 int c=cap[e]; |
|
241 if (mincut5[G.source(e)] && !mincut5[G.target(e)]) min_min_cut5_value+=c; |
|
242 if (cut5[G.source(e)] && !cut5[G.target(e)]) min_cut5_value+=c; |
|
243 if (maxcut5[G.source(e)] && !maxcut5[G.target(e)]) max_min_cut5_value+=c; |
|
244 } |
|
245 |
|
246 std::cout << "\nThe given flow value is " |
|
247 << preflow_test4.flowValue(); |
|
248 |
|
249 if ( preflow_test4.flowValue() == min_cut5_value && |
|
250 min_cut5_value == min_min_cut5_value && |
|
251 min_min_cut5_value == max_min_cut5_value ) |
|
252 std::cout <<", which is equal to all three min cut values." |
|
253 <<std::endl<<std::endl; |
|
254 else { |
|
255 std::cout << "ERROR! It is not equal to all three min cut values! " |
|
256 <<std::endl; |
|
257 error=true; |
|
258 } |
|
259 |
|
260 if (error) std::cout <<"\nThere was some error in the results!\n"<<std::endl; |
|
261 else std::cout <<"\nThere was no error in the results.\n"<<std::endl; |
|
262 |
|
263 return 0; |
|
264 } |
|