50 Graph::NodeMap<bool> mincut(G); |
50 Graph::NodeMap<bool> mincut(G); |
51 max_flow_test.minMinCut(mincut); |
51 max_flow_test.minMinCut(mincut); |
52 int min_min_cut_value=0; |
52 int min_min_cut_value=0; |
53 EdgeIt e; |
53 EdgeIt e; |
54 for(G.first(e); G.valid(e); G.next(e)) { |
54 for(G.first(e); G.valid(e); G.next(e)) { |
55 if (mincut[G.tail(e)] && !mincut[G.head(e)]) min_min_cut_value+=cap[e]; |
55 if (mincut[G.source(e)] && !mincut[G.target(e)]) min_min_cut_value+=cap[e]; |
56 } |
56 } |
57 |
57 |
58 Graph::NodeMap<bool> cut(G); |
58 Graph::NodeMap<bool> cut(G); |
59 max_flow_test.minCut(cut); |
59 max_flow_test.minCut(cut); |
60 int min_cut_value=0; |
60 int min_cut_value=0; |
61 for(G.first(e); G.valid(e); G.next(e)) { |
61 for(G.first(e); G.valid(e); G.next(e)) { |
62 if (cut[G.tail(e)] && !cut[G.head(e)]) |
62 if (cut[G.source(e)] && !cut[G.target(e)]) |
63 min_cut_value+=cap[e]; |
63 min_cut_value+=cap[e]; |
64 } |
64 } |
65 |
65 |
66 Graph::NodeMap<bool> maxcut(G); |
66 Graph::NodeMap<bool> maxcut(G); |
67 max_flow_test.maxMinCut(maxcut); |
67 max_flow_test.maxMinCut(maxcut); |
68 int max_min_cut_value=0; |
68 int max_min_cut_value=0; |
69 for(G.first(e); G.valid(e); G.next(e)) { |
69 for(G.first(e); G.valid(e); G.next(e)) { |
70 if (maxcut[G.tail(e)] && !maxcut[G.head(e)]) |
70 if (maxcut[G.source(e)] && !maxcut[G.target(e)]) |
71 max_min_cut_value+=cap[e]; |
71 max_min_cut_value+=cap[e]; |
72 } |
72 } |
73 |
73 |
74 std::cout << "\n Checking the result: " <<std::endl; |
74 std::cout << "\n Checking the result: " <<std::endl; |
75 std::cout << "Flow value: "<< max_flow_test.flowValue() << std::endl; |
75 std::cout << "Flow value: "<< max_flow_test.flowValue() << std::endl; |
97 |
97 |
98 Graph::NodeMap<bool> mincut2(G); |
98 Graph::NodeMap<bool> mincut2(G); |
99 max_flow_test2.minMinCut(mincut2); |
99 max_flow_test2.minMinCut(mincut2); |
100 int min_min_cut_value2=0; |
100 int min_min_cut_value2=0; |
101 for(G.first(e); G.valid(e); G.next(e)) { |
101 for(G.first(e); G.valid(e); G.next(e)) { |
102 if (mincut2[G.tail(e)] && !mincut2[G.head(e)]) min_min_cut_value2+=cap[e]; |
102 if (mincut2[G.source(e)] && !mincut2[G.target(e)]) min_min_cut_value2+=cap[e]; |
103 } |
103 } |
104 |
104 |
105 Graph::NodeMap<bool> cut2(G); |
105 Graph::NodeMap<bool> cut2(G); |
106 max_flow_test2.minCut(cut2); |
106 max_flow_test2.minCut(cut2); |
107 int min_cut_value2=0; |
107 int min_cut_value2=0; |
108 for(G.first(e); G.valid(e); G.next(e)) { |
108 for(G.first(e); G.valid(e); G.next(e)) { |
109 if (cut2[G.tail(e)] && !cut2[G.head(e)]) |
109 if (cut2[G.source(e)] && !cut2[G.target(e)]) |
110 min_cut_value2+=cap[e]; |
110 min_cut_value2+=cap[e]; |
111 } |
111 } |
112 |
112 |
113 Graph::NodeMap<bool> maxcut2(G); |
113 Graph::NodeMap<bool> maxcut2(G); |
114 max_flow_test2.maxMinCut(maxcut2); |
114 max_flow_test2.maxMinCut(maxcut2); |
115 int max_min_cut_value2=0; |
115 int max_min_cut_value2=0; |
116 for(G.first(e); G.valid(e); G.next(e)) { |
116 for(G.first(e); G.valid(e); G.next(e)) { |
117 if (maxcut2[G.tail(e)] && !maxcut2[G.head(e)]) |
117 if (maxcut2[G.source(e)] && !maxcut2[G.target(e)]) |
118 max_min_cut_value2+=cap[e]; |
118 max_min_cut_value2+=cap[e]; |
119 } |
119 } |
120 |
120 |
121 std::cout << "\n Checking the result: " <<std::endl; |
121 std::cout << "\n Checking the result: " <<std::endl; |
122 std::cout << "Flow value: "<< max_flow_test2.flowValue() << std::endl; |
122 std::cout << "Flow value: "<< max_flow_test2.flowValue() << std::endl; |
142 |
142 |
143 Graph::NodeMap<bool> mincut3(G); |
143 Graph::NodeMap<bool> mincut3(G); |
144 max_flow_test3.minMinCut(mincut3); |
144 max_flow_test3.minMinCut(mincut3); |
145 int min_min_cut_value3=0; |
145 int min_min_cut_value3=0; |
146 for(G.first(e); G.valid(e); G.next(e)) { |
146 for(G.first(e); G.valid(e); G.next(e)) { |
147 if (mincut3[G.tail(e)] && !mincut3[G.head(e)]) min_min_cut_value3+=cap[e]; |
147 if (mincut3[G.source(e)] && !mincut3[G.target(e)]) min_min_cut_value3+=cap[e]; |
148 } |
148 } |
149 |
149 |
150 Graph::NodeMap<bool> cut3(G); |
150 Graph::NodeMap<bool> cut3(G); |
151 max_flow_test3.minCut(cut3); |
151 max_flow_test3.minCut(cut3); |
152 int min_cut_value3=0; |
152 int min_cut_value3=0; |
153 for(G.first(e); G.valid(e); G.next(e)) { |
153 for(G.first(e); G.valid(e); G.next(e)) { |
154 if (cut3[G.tail(e)] && !cut3[G.head(e)]) |
154 if (cut3[G.source(e)] && !cut3[G.target(e)]) |
155 min_cut_value3+=cap[e]; |
155 min_cut_value3+=cap[e]; |
156 } |
156 } |
157 |
157 |
158 Graph::NodeMap<bool> maxcut3(G); |
158 Graph::NodeMap<bool> maxcut3(G); |
159 max_flow_test3.maxMinCut(maxcut3); |
159 max_flow_test3.maxMinCut(maxcut3); |
160 int max_min_cut_value3=0; |
160 int max_min_cut_value3=0; |
161 for(G.first(e); G.valid(e); G.next(e)) { |
161 for(G.first(e); G.valid(e); G.next(e)) { |
162 if (maxcut3[G.tail(e)] && !maxcut3[G.head(e)]) |
162 if (maxcut3[G.source(e)] && !maxcut3[G.target(e)]) |
163 max_min_cut_value3+=cap[e]; |
163 max_min_cut_value3+=cap[e]; |
164 } |
164 } |
165 |
165 |
166 std::cout << "\n Checking the result: " <<std::endl; |
166 std::cout << "\n Checking the result: " <<std::endl; |
167 std::cout << "Flow value: "<< max_flow_test3.flowValue() << std::endl; |
167 std::cout << "Flow value: "<< max_flow_test3.flowValue() << std::endl; |