equal
deleted
inserted
replaced
44 preflow_test.maxMinCut(maxcut); |
44 preflow_test.maxMinCut(maxcut); |
45 int max_min_cut_value=0; |
45 int max_min_cut_value=0; |
46 EdgeIt e; |
46 EdgeIt e; |
47 for(G.first(e); G.valid(e); G.next(e)) { |
47 for(G.first(e); G.valid(e); G.next(e)) { |
48 int c=cap[e]; |
48 int c=cap[e]; |
49 if (mincut[G.tail(e)] && !mincut[G.head(e)]) min_min_cut_value+=c; |
49 if (mincut[G.source(e)] && !mincut[G.target(e)]) min_min_cut_value+=c; |
50 if (cut[G.tail(e)] && !cut[G.head(e)]) min_cut_value+=c; |
50 if (cut[G.source(e)] && !cut[G.target(e)]) min_cut_value+=c; |
51 if (maxcut[G.tail(e)] && !maxcut[G.head(e)]) max_min_cut_value+=c; |
51 if (maxcut[G.source(e)] && !maxcut[G.target(e)]) max_min_cut_value+=c; |
52 } |
52 } |
53 |
53 |
54 std::cout << "\nChecking the result: " <<std::endl; |
54 std::cout << "\nChecking the result: " <<std::endl; |
55 std::cout << "Flow value: "<< preflow_test.flowValue() << std::endl; |
55 std::cout << "Flow value: "<< preflow_test.flowValue() << std::endl; |
56 std::cout << "Min cut value: "<< min_cut_value << std::endl; |
56 std::cout << "Min cut value: "<< min_cut_value << std::endl; |
84 Graph::NodeMap<bool> maxcut2(G); |
84 Graph::NodeMap<bool> maxcut2(G); |
85 preflow_test.maxMinCut(maxcut2); |
85 preflow_test.maxMinCut(maxcut2); |
86 int max_min_cut2_value=0; |
86 int max_min_cut2_value=0; |
87 for(G.first(e); G.valid(e); G.next(e)) { |
87 for(G.first(e); G.valid(e); G.next(e)) { |
88 int c=cap[e]; |
88 int c=cap[e]; |
89 if (mincut2[G.tail(e)] && !mincut2[G.head(e)]) min_min_cut2_value+=c; |
89 if (mincut2[G.source(e)] && !mincut2[G.target(e)]) min_min_cut2_value+=c; |
90 if (cut2[G.tail(e)] && !cut2[G.head(e)]) min_cut2_value+=c; |
90 if (cut2[G.source(e)] && !cut2[G.target(e)]) min_cut2_value+=c; |
91 if (maxcut2[G.tail(e)] && !maxcut2[G.head(e)]) max_min_cut2_value+=c; |
91 if (maxcut2[G.source(e)] && !maxcut2[G.target(e)]) max_min_cut2_value+=c; |
92 } |
92 } |
93 |
93 |
94 std::cout << "\nThe given flow value is " |
94 std::cout << "\nThe given flow value is " |
95 << preflow_test2.flowValue(); |
95 << preflow_test2.flowValue(); |
96 |
96 |
136 preflow_test.maxMinCut(maxcut3); |
136 preflow_test.maxMinCut(maxcut3); |
137 int max_min_cut3_value=0; |
137 int max_min_cut3_value=0; |
138 |
138 |
139 for(G.first(e); G.valid(e); G.next(e)) { |
139 for(G.first(e); G.valid(e); G.next(e)) { |
140 int c=cap[e]; |
140 int c=cap[e]; |
141 if (mincut3[G.tail(e)] && !mincut3[G.head(e)]) min_min_cut3_value+=c; |
141 if (mincut3[G.source(e)] && !mincut3[G.target(e)]) min_min_cut3_value+=c; |
142 if (cut3[G.tail(e)] && !cut3[G.head(e)]) min_cut3_value+=c; |
142 if (cut3[G.source(e)] && !cut3[G.target(e)]) min_cut3_value+=c; |
143 if (maxcut3[G.tail(e)] && !maxcut3[G.head(e)]) max_min_cut3_value+=c; |
143 if (maxcut3[G.source(e)] && !maxcut3[G.target(e)]) max_min_cut3_value+=c; |
144 if (actcut3[G.tail(e)] && !actcut3[G.head(e)]) act_min_cut3_value+=c; |
144 if (actcut3[G.source(e)] && !actcut3[G.target(e)]) act_min_cut3_value+=c; |
145 } |
145 } |
146 |
146 |
147 std::cout << "\nThe min cut value given by actMinCut() after phase 0 is "<< |
147 std::cout << "\nThe min cut value given by actMinCut() after phase 0 is "<< |
148 act_min_cut3_value; |
148 act_min_cut3_value; |
149 |
149 |
193 Graph::NodeMap<bool> maxcut4(G); |
193 Graph::NodeMap<bool> maxcut4(G); |
194 preflow_test4.maxMinCut(maxcut4); |
194 preflow_test4.maxMinCut(maxcut4); |
195 int max_min_cut4_value=0; |
195 int max_min_cut4_value=0; |
196 for(G.first(e); G.valid(e); G.next(e)) { |
196 for(G.first(e); G.valid(e); G.next(e)) { |
197 int c=cap[e]; |
197 int c=cap[e]; |
198 if (mincut4[G.tail(e)] && !mincut4[G.head(e)]) min_min_cut4_value+=c; |
198 if (mincut4[G.source(e)] && !mincut4[G.target(e)]) min_min_cut4_value+=c; |
199 if (cut4[G.tail(e)] && !cut4[G.head(e)]) min_cut4_value+=c; |
199 if (cut4[G.source(e)] && !cut4[G.target(e)]) min_cut4_value+=c; |
200 if (maxcut4[G.tail(e)] && !maxcut4[G.head(e)]) max_min_cut4_value+=c; |
200 if (maxcut4[G.source(e)] && !maxcut4[G.target(e)]) max_min_cut4_value+=c; |
201 } |
201 } |
202 |
202 |
203 std::cout << "\nThe given flow value is " |
203 std::cout << "\nThe given flow value is " |
204 << preflow_test4.flowValue(); |
204 << preflow_test4.flowValue(); |
205 |
205 |
236 Graph::NodeMap<bool> maxcut5(G); |
236 Graph::NodeMap<bool> maxcut5(G); |
237 preflow_test4.maxMinCut(maxcut5); |
237 preflow_test4.maxMinCut(maxcut5); |
238 int max_min_cut5_value=0; |
238 int max_min_cut5_value=0; |
239 for(G.first(e); G.valid(e); G.next(e)) { |
239 for(G.first(e); G.valid(e); G.next(e)) { |
240 int c=cap[e]; |
240 int c=cap[e]; |
241 if (mincut5[G.tail(e)] && !mincut5[G.head(e)]) min_min_cut5_value+=c; |
241 if (mincut5[G.source(e)] && !mincut5[G.target(e)]) min_min_cut5_value+=c; |
242 if (cut5[G.tail(e)] && !cut5[G.head(e)]) min_cut5_value+=c; |
242 if (cut5[G.source(e)] && !cut5[G.target(e)]) min_cut5_value+=c; |
243 if (maxcut5[G.tail(e)] && !maxcut5[G.head(e)]) max_min_cut5_value+=c; |
243 if (maxcut5[G.source(e)] && !maxcut5[G.target(e)]) max_min_cut5_value+=c; |
244 } |
244 } |
245 |
245 |
246 std::cout << "\nThe given flow value is " |
246 std::cout << "\nThe given flow value is " |
247 << preflow_test4.flowValue(); |
247 << preflow_test4.flowValue(); |
248 |
248 |