40 Graph::NodeMap<bool> mincut(G); |
40 Graph::NodeMap<bool> mincut(G); |
41 max_flow_test_no_stack.minMinCut(mincut); |
41 max_flow_test_no_stack.minMinCut(mincut); |
42 int min_min_cut_value=0; |
42 int min_min_cut_value=0; |
43 EdgeIt e; |
43 EdgeIt e; |
44 for(G.first(e); G.valid(e); G.next(e)) { |
44 for(G.first(e); G.valid(e); G.next(e)) { |
45 if (mincut[G.tail(e)] && !mincut[G.head(e)]) min_min_cut_value+=cap[e]; |
45 if (mincut[G.source(e)] && !mincut[G.target(e)]) min_min_cut_value+=cap[e]; |
46 } |
46 } |
47 |
47 |
48 Graph::NodeMap<bool> cut(G); |
48 Graph::NodeMap<bool> cut(G); |
49 max_flow_test_no_stack.minCut(cut); |
49 max_flow_test_no_stack.minCut(cut); |
50 int min_cut_value=0; |
50 int min_cut_value=0; |
51 for(G.first(e); G.valid(e); G.next(e)) { |
51 for(G.first(e); G.valid(e); G.next(e)) { |
52 if (cut[G.tail(e)] && !cut[G.head(e)]) |
52 if (cut[G.source(e)] && !cut[G.target(e)]) |
53 min_cut_value+=cap[e]; |
53 min_cut_value+=cap[e]; |
54 } |
54 } |
55 |
55 |
56 Graph::NodeMap<bool> maxcut(G); |
56 Graph::NodeMap<bool> maxcut(G); |
57 max_flow_test_no_stack.maxMinCut(maxcut); |
57 max_flow_test_no_stack.maxMinCut(maxcut); |
58 int max_min_cut_value=0; |
58 int max_min_cut_value=0; |
59 for(G.first(e); G.valid(e); G.next(e)) { |
59 for(G.first(e); G.valid(e); G.next(e)) { |
60 if (maxcut[G.tail(e)] && !maxcut[G.head(e)]) |
60 if (maxcut[G.source(e)] && !maxcut[G.target(e)]) |
61 max_min_cut_value+=cap[e]; |
61 max_min_cut_value+=cap[e]; |
62 } |
62 } |
63 |
63 |
64 std::cout << "\n Checking the result without stack: " <<std::endl; |
64 std::cout << "\n Checking the result without stack: " <<std::endl; |
65 std::cout << "Flow value: "<< max_flow_test_no_stack.flowValue() << std::endl; |
65 std::cout << "Flow value: "<< max_flow_test_no_stack.flowValue() << std::endl; |
86 |
86 |
87 Graph::NodeMap<bool> mincut2(G); |
87 Graph::NodeMap<bool> mincut2(G); |
88 max_flow_test.minMinCut(mincut2); |
88 max_flow_test.minMinCut(mincut2); |
89 int min_min_cut_value2=0; |
89 int min_min_cut_value2=0; |
90 for(G.first(e); G.valid(e); G.next(e)) { |
90 for(G.first(e); G.valid(e); G.next(e)) { |
91 if (mincut2[G.tail(e)] && !mincut2[G.head(e)]) min_min_cut_value2+=cap[e]; |
91 if (mincut2[G.source(e)] && !mincut2[G.target(e)]) min_min_cut_value2+=cap[e]; |
92 } |
92 } |
93 |
93 |
94 Graph::NodeMap<bool> cut2(G); |
94 Graph::NodeMap<bool> cut2(G); |
95 max_flow_test.minCut(cut2); |
95 max_flow_test.minCut(cut2); |
96 int min_cut_value2=0; |
96 int min_cut_value2=0; |
97 for(G.first(e); G.valid(e); G.next(e)) { |
97 for(G.first(e); G.valid(e); G.next(e)) { |
98 if (cut2[G.tail(e)] && !cut2[G.head(e)]) |
98 if (cut2[G.source(e)] && !cut2[G.target(e)]) |
99 min_cut_value2+=cap[e]; |
99 min_cut_value2+=cap[e]; |
100 } |
100 } |
101 |
101 |
102 Graph::NodeMap<bool> maxcut2(G); |
102 Graph::NodeMap<bool> maxcut2(G); |
103 max_flow_test.maxMinCut(maxcut2); |
103 max_flow_test.maxMinCut(maxcut2); |
104 int max_min_cut_value2=0; |
104 int max_min_cut_value2=0; |
105 for(G.first(e); G.valid(e); G.next(e)) { |
105 for(G.first(e); G.valid(e); G.next(e)) { |
106 if (maxcut2[G.tail(e)] && !maxcut2[G.head(e)]) |
106 if (maxcut2[G.source(e)] && !maxcut2[G.target(e)]) |
107 max_min_cut_value2+=cap[e]; |
107 max_min_cut_value2+=cap[e]; |
108 } |
108 } |
109 |
109 |
110 std::cout << "\n Checking the result: " <<std::endl; |
110 std::cout << "\n Checking the result: " <<std::endl; |
111 std::cout << "Flow value: "<< max_flow_test.flowValue() << std::endl; |
111 std::cout << "Flow value: "<< max_flow_test.flowValue() << std::endl; |
125 |
125 |
126 Graph::NodeMap<bool> mincut3(G); |
126 Graph::NodeMap<bool> mincut3(G); |
127 max_flow_test3.minMinCut(mincut3); |
127 max_flow_test3.minMinCut(mincut3); |
128 int min_min_cut_value3=0; |
128 int min_min_cut_value3=0; |
129 for(G.first(e); G.valid(e); G.next(e)) { |
129 for(G.first(e); G.valid(e); G.next(e)) { |
130 if (mincut3[G.tail(e)] && !mincut3[G.head(e)]) min_min_cut_value3+=cap[e]; |
130 if (mincut3[G.source(e)] && !mincut3[G.target(e)]) min_min_cut_value3+=cap[e]; |
131 } |
131 } |
132 |
132 |
133 Graph::NodeMap<bool> cut3(G); |
133 Graph::NodeMap<bool> cut3(G); |
134 max_flow_test3.minCut(cut3); |
134 max_flow_test3.minCut(cut3); |
135 int min_cut_value3=0; |
135 int min_cut_value3=0; |
136 for(G.first(e); G.valid(e); G.next(e)) { |
136 for(G.first(e); G.valid(e); G.next(e)) { |
137 if (cut3[G.tail(e)] && !cut3[G.head(e)]) |
137 if (cut3[G.source(e)] && !cut3[G.target(e)]) |
138 min_cut_value3+=cap[e]; |
138 min_cut_value3+=cap[e]; |
139 } |
139 } |
140 |
140 |
141 Graph::NodeMap<bool> maxcut3(G); |
141 Graph::NodeMap<bool> maxcut3(G); |
142 max_flow_test3.maxMinCut(maxcut3); |
142 max_flow_test3.maxMinCut(maxcut3); |
143 int max_min_cut_value3=0; |
143 int max_min_cut_value3=0; |
144 for(G.first(e); G.valid(e); G.next(e)) { |
144 for(G.first(e); G.valid(e); G.next(e)) { |
145 if (maxcut3[G.tail(e)] && !maxcut3[G.head(e)]) |
145 if (maxcut3[G.source(e)] && !maxcut3[G.target(e)]) |
146 max_min_cut_value3+=cap[e]; |
146 max_min_cut_value3+=cap[e]; |
147 } |
147 } |
148 |
148 |
149 std::cout << "\n Checking the result: " <<std::endl; |
149 std::cout << "\n Checking the result: " <<std::endl; |
150 std::cout << "Flow value: "<< max_flow_test3.flowValue() << std::endl; |
150 std::cout << "Flow value: "<< max_flow_test3.flowValue() << std::endl; |