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