1 | // Copyright Daniel Trebbien 2010. |
2 | // Distributed under the Boost Software License, Version 1.0. |
3 | // (See accompanying file LICENSE_1_0.txt or the copy at |
4 | // http://www.boost.org/LICENSE_1_0.txt) |
5 | |
6 | #if defined(_MSC_VER) && !defined(_CRT_SECURE_NO_WARNINGS) |
7 | #define _CRT_SECURE_NO_WARNINGS |
8 | #endif |
9 | |
10 | #include <fstream> |
11 | #include <iostream> |
12 | #include <map> |
13 | #include <vector> |
14 | #include <string> |
15 | #include <boost/graph/adjacency_list.hpp> |
16 | #include <boost/graph/connected_components.hpp> |
17 | #include <boost/graph/exception.hpp> |
18 | #include <boost/graph/graph_traits.hpp> |
19 | #include <boost/graph/read_dimacs.hpp> |
20 | #include <boost/graph/stoer_wagner_min_cut.hpp> |
21 | #include <boost/graph/property_maps/constant_property_map.hpp> |
22 | #include <boost/property_map/property_map.hpp> |
23 | #include <boost/core/lightweight_test.hpp> |
24 | #include <boost/tuple/tuple.hpp> |
25 | |
26 | typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS, |
27 | boost::no_property, boost::property< boost::edge_weight_t, int > > |
28 | undirected_graph; |
29 | typedef boost::property_map< undirected_graph, boost::edge_weight_t >::type |
30 | weight_map_type; |
31 | typedef boost::property_traits< weight_map_type >::value_type weight_type; |
32 | |
33 | typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS > |
34 | undirected_unweighted_graph; |
35 | |
36 | std::string test_dir; |
37 | |
38 | struct edge_t |
39 | { |
40 | unsigned long first; |
41 | unsigned long second; |
42 | }; |
43 | |
44 | // the example from Stoer & Wagner (1997) |
45 | void test0() |
46 | { |
47 | edge_t edges[] = { { .first: 0, .second: 1 }, { .first: 1, .second: 2 }, { .first: 2, .second: 3 }, { .first: 0, .second: 4 }, { .first: 1, .second: 4 }, |
48 | { .first: 1, .second: 5 }, { .first: 2, .second: 6 }, { .first: 3, .second: 6 }, { .first: 3, .second: 7 }, { .first: 4, .second: 5 }, { .first: 5, .second: 6 }, { .first: 6, .second: 7 } }; |
49 | weight_type ws[] = { 2, 3, 4, 3, 2, 2, 2, 2, 2, 3, 1, 3 }; |
50 | undirected_graph g(edges, edges + 12, ws, 8, 12); |
51 | |
52 | weight_map_type weights = get(p: boost::edge_weight, g); |
53 | std::map< int, bool > parity; |
54 | boost::associative_property_map< std::map< int, bool > > parities(parity); |
55 | int w |
56 | = boost::stoer_wagner_min_cut(param0: g, param1: weights, old_style_params: boost::parity_map(p: parities)); |
57 | BOOST_TEST_EQ(w, 4); |
58 | const bool parity0 = get(pa: parities, k: 0); |
59 | BOOST_TEST_EQ(parity0, get(parities, 1)); |
60 | BOOST_TEST_EQ(parity0, get(parities, 4)); |
61 | BOOST_TEST_EQ(parity0, get(parities, 5)); |
62 | const bool parity2 = get(pa: parities, k: 2); |
63 | BOOST_TEST_NE(parity0, parity2); |
64 | BOOST_TEST_EQ(parity2, get(parities, 3)); |
65 | BOOST_TEST_EQ(parity2, get(parities, 6)); |
66 | BOOST_TEST_EQ(parity2, get(parities, 7)); |
67 | } |
68 | |
69 | void test1() |
70 | { |
71 | { // if only one vertex, can't run `boost::stoer_wagner_min_cut` |
72 | undirected_graph g; |
73 | add_vertex(g_&: g); |
74 | |
75 | BOOST_TEST_THROWS( |
76 | boost::stoer_wagner_min_cut(g, get(boost::edge_weight, g)), |
77 | boost::bad_graph); |
78 | } |
79 | { // three vertices with one multi-edge |
80 | typedef boost::graph_traits< undirected_graph >::vertex_descriptor |
81 | vertex_descriptor; |
82 | |
83 | edge_t edges[] = { { .first: 0, .second: 1 }, { .first: 1, .second: 2 }, { .first: 1, .second: 2 }, { .first: 2, .second: 0 } }; |
84 | weight_type ws[] = { 3, 1, 1, 1 }; |
85 | undirected_graph g(edges, edges + 4, ws, 3, 4); |
86 | |
87 | weight_map_type weights = get(p: boost::edge_weight, g); |
88 | std::map< int, bool > parity; |
89 | boost::associative_property_map< std::map< int, bool > > parities( |
90 | parity); |
91 | std::map< vertex_descriptor, vertex_descriptor > assignment; |
92 | boost::associative_property_map< |
93 | std::map< vertex_descriptor, vertex_descriptor > > |
94 | assignments(assignment); |
95 | int w = boost::stoer_wagner_min_cut(param0: g, param1: weights, |
96 | old_style_params: boost::parity_map(p: parities).vertex_assignment_map(p: assignments)); |
97 | BOOST_TEST_EQ(w, 3); |
98 | const bool parity2 = get(pa: parities, k: 2), parity0 = get(pa: parities, k: 0); |
99 | BOOST_TEST_NE(parity2, parity0); |
100 | BOOST_TEST_EQ(parity0, get(parities, 1)); |
101 | } |
102 | } |
103 | |
104 | // example by Daniel Trebbien |
105 | void test2() |
106 | { |
107 | edge_t edges[] = { { .first: 5, .second: 2 }, { .first: 0, .second: 6 }, { .first: 5, .second: 6 }, { .first: 3, .second: 1 }, { .first: 0, .second: 1 }, |
108 | { .first: 6, .second: 3 }, { .first: 4, .second: 6 }, { .first: 2, .second: 4 }, { .first: 5, .second: 3 } }; |
109 | weight_type ws[] = { 1, 3, 4, 6, 4, 1, 2, 5, 2 }; |
110 | undirected_graph g(edges, edges + 9, ws, 7, 9); |
111 | |
112 | std::map< int, bool > parity; |
113 | boost::associative_property_map< std::map< int, bool > > parities(parity); |
114 | int w = boost::stoer_wagner_min_cut( |
115 | param0: g, param1: get(p: boost::edge_weight, g), old_style_params: boost::parity_map(p: parities)); |
116 | BOOST_TEST_EQ(w, 3); |
117 | const bool parity2 = get(pa: parities, k: 2); |
118 | BOOST_TEST_EQ(parity2, get(parities, 4)); |
119 | const bool parity5 = get(pa: parities, k: 5); |
120 | BOOST_TEST_NE(parity2, parity5); |
121 | BOOST_TEST_EQ(parity5, get(parities, 3)); |
122 | BOOST_TEST_EQ(parity5, get(parities, 6)); |
123 | BOOST_TEST_EQ(parity5, get(parities, 1)); |
124 | BOOST_TEST_EQ(parity5, get(parities, 0)); |
125 | } |
126 | |
127 | // example by Daniel Trebbien |
128 | void test3() |
129 | { |
130 | edge_t edges[] = { { .first: 3, .second: 4 }, { .first: 3, .second: 6 }, { .first: 3, .second: 5 }, { .first: 0, .second: 4 }, { .first: 0, .second: 1 }, |
131 | { .first: 0, .second: 6 }, { .first: 0, .second: 7 }, { .first: 0, .second: 5 }, { .first: 0, .second: 2 }, { .first: 4, .second: 1 }, { .first: 1, .second: 6 }, { .first: 1, .second: 5 }, |
132 | { .first: 6, .second: 7 }, { .first: 7, .second: 5 }, { .first: 5, .second: 2 }, { .first: 3, .second: 4 } }; |
133 | weight_type ws[] = { 0, 3, 1, 3, 1, 2, 6, 1, 8, 1, 1, 80, 2, 1, 1, 4 }; |
134 | undirected_graph g(edges, edges + 16, ws, 8, 16); |
135 | |
136 | weight_map_type weights = get(p: boost::edge_weight, g); |
137 | std::map< int, bool > parity; |
138 | boost::associative_property_map< std::map< int, bool > > parities(parity); |
139 | int w |
140 | = boost::stoer_wagner_min_cut(param0: g, param1: weights, old_style_params: boost::parity_map(p: parities)); |
141 | BOOST_TEST_EQ(w, 7); |
142 | const bool parity1 = get(pa: parities, k: 1); |
143 | BOOST_TEST_EQ(parity1, get(parities, 5)); |
144 | const bool parity0 = get(pa: parities, k: 0); |
145 | BOOST_TEST_NE(parity1, parity0); |
146 | BOOST_TEST_EQ(parity0, get(parities, 2)); |
147 | BOOST_TEST_EQ(parity0, get(parities, 3)); |
148 | BOOST_TEST_EQ(parity0, get(parities, 4)); |
149 | BOOST_TEST_EQ(parity0, get(parities, 6)); |
150 | BOOST_TEST_EQ(parity0, get(parities, 7)); |
151 | } |
152 | |
153 | void test4() |
154 | { |
155 | typedef boost::graph_traits< |
156 | undirected_unweighted_graph >::vertex_descriptor vertex_descriptor; |
157 | typedef boost::graph_traits< undirected_unweighted_graph >::edge_descriptor |
158 | edge_descriptor; |
159 | |
160 | edge_t edges[] = { { .first: 0, .second: 1 }, { .first: 1, .second: 2 }, { .first: 2, .second: 3 }, { .first: 0, .second: 4 }, { .first: 1, .second: 4 }, |
161 | { .first: 1, .second: 5 }, { .first: 2, .second: 6 }, { .first: 3, .second: 6 }, { .first: 3, .second: 7 }, { .first: 4, .second: 5 }, { .first: 5, .second: 6 }, { .first: 6, .second: 7 }, |
162 | { .first: 0, .second: 4 }, { .first: 6, .second: 7 } }; |
163 | undirected_unweighted_graph g(edges, edges + 14, 8); |
164 | |
165 | std::map< vertex_descriptor, bool > parity; |
166 | boost::associative_property_map< std::map< vertex_descriptor, bool > > |
167 | parities(parity); |
168 | std::map< vertex_descriptor, vertex_descriptor > assignment; |
169 | boost::associative_property_map< |
170 | std::map< vertex_descriptor, vertex_descriptor > > |
171 | assignments(assignment); |
172 | int w = boost::stoer_wagner_min_cut(param0: g, |
173 | param1: boost::make_constant_property< edge_descriptor >(value: weight_type(1)), |
174 | old_style_params: boost::vertex_assignment_map(p: assignments).parity_map(p: parities)); |
175 | BOOST_TEST_EQ(w, 2); |
176 | const bool parity0 = get(pa: parities, k: 0); |
177 | BOOST_TEST_EQ(parity0, get(parities, 1)); |
178 | BOOST_TEST_EQ(parity0, get(parities, 4)); |
179 | BOOST_TEST_EQ(parity0, get(parities, 5)); |
180 | const bool parity2 = get(pa: parities, k: 2); |
181 | BOOST_TEST_NE(parity0, parity2); |
182 | BOOST_TEST_EQ(parity2, get(parities, 3)); |
183 | BOOST_TEST_EQ(parity2, get(parities, 6)); |
184 | BOOST_TEST_EQ(parity2, get(parities, 7)); |
185 | } |
186 | |
187 | // Non regression test for github.com/boostorg/graph/issues/286 |
188 | void test5() |
189 | { |
190 | edge_t edges[] = { { .first: 0, .second: 1 }, { .first: 0, .second: 2 }, { .first: 0, .second: 3 }, { .first: 1, .second: 2 }, { .first: 1, .second: 3 }, |
191 | { .first: 2, .second: 3 }, { .first: 4, .second: 5 }, { .first: 4, .second: 6 }, { .first: 4, .second: 7 }, { .first: 5, .second: 6 }, { .first: 5, .second: 7 }, { .first: 6, .second: 7 }, |
192 | { .first: 0, .second: 4 } }; |
193 | weight_type ws[] = { 3, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 2, 6 }; |
194 | undirected_graph g(edges, edges + 13, ws, 8, 13); |
195 | |
196 | weight_map_type weights = get(p: boost::edge_weight, g); |
197 | std::map< int, bool > parity; |
198 | boost::associative_property_map< std::map< int, bool > > parities(parity); |
199 | int w |
200 | = boost::stoer_wagner_min_cut(param0: g, param1: weights, old_style_params: boost::parity_map(p: parities)); |
201 | BOOST_TEST_EQ(w, 6); |
202 | const bool parity0 = get(pa: parities, k: 0); |
203 | BOOST_TEST_EQ(parity0, get(parities, 1)); |
204 | BOOST_TEST_EQ(parity0, get(parities, 2)); |
205 | BOOST_TEST_EQ(parity0, get(parities, 3)); |
206 | const bool parity4 = get(pa: parities, k: 4); |
207 | BOOST_TEST_NE(parity0, parity4); |
208 | BOOST_TEST_EQ(parity4, get(parities, 5)); |
209 | BOOST_TEST_EQ(parity4, get(parities, 6)); |
210 | BOOST_TEST_EQ(parity4, get(parities, 7)); |
211 | } |
212 | |
213 | // The input for the `test_prgen` family of tests comes from a program, named |
214 | // `prgen`, that comes with a package of min-cut solvers by Chandra Chekuri, |
215 | // Andrew Goldberg, David Karger, Matthew Levine, and Cliff Stein. `prgen` was |
216 | // used to generate input graphs and the solvers were used to verify the return |
217 | // value of `boost::stoer_wagner_min_cut` on the input graphs. |
218 | // |
219 | // http://www.columbia.edu/~cs2035/code.html |
220 | // |
221 | // Note that it is somewhat more difficult to verify the parities because |
222 | // "`prgen` graphs" often have several min-cuts. This is why only the cut |
223 | // weight of the min-cut is verified. |
224 | |
225 | // 3 min-cuts |
226 | void test_prgen_20_70_2() |
227 | { |
228 | typedef boost::graph_traits< undirected_graph >::vertex_descriptor |
229 | vertex_descriptor; |
230 | |
231 | std::ifstream ifs( |
232 | (test_dir + "/prgen_input_graphs/prgen_20_70_2.net" ).c_str()); |
233 | undirected_graph g; |
234 | boost::read_dimacs_min_cut( |
235 | g, capacity: get(p: boost::edge_weight, g), reverse_edge: boost::dummy_property_map(), in&: ifs); |
236 | |
237 | std::map< vertex_descriptor, std::size_t > component; |
238 | boost::associative_property_map< |
239 | std::map< vertex_descriptor, std::size_t > > |
240 | components(component); |
241 | BOOST_TEST_EQ(boost::connected_components(g, components), |
242 | 1U); // verify the connectedness assumption |
243 | |
244 | typedef boost::shared_array_property_map< weight_type, |
245 | boost::property_map< undirected_graph, |
246 | boost::vertex_index_t >::const_type > |
247 | distances_type; |
248 | distances_type distances = boost::make_shared_array_property_map( |
249 | n: num_vertices(g_: g), weight_type(0), index: get(p: boost::vertex_index, g)); |
250 | typedef std::vector< vertex_descriptor >::size_type index_in_heap_type; |
251 | typedef boost::shared_array_property_map< index_in_heap_type, |
252 | boost::property_map< undirected_graph, |
253 | boost::vertex_index_t >::const_type > |
254 | indicesInHeap_type; |
255 | indicesInHeap_type indicesInHeap = boost::make_shared_array_property_map( |
256 | n: num_vertices(g_: g), index_in_heap_type(-1), index: get(p: boost::vertex_index, g)); |
257 | boost::d_ary_heap_indirect< vertex_descriptor, 22, indicesInHeap_type, |
258 | distances_type, std::greater< weight_type > > |
259 | pq(distances, indicesInHeap); |
260 | |
261 | int w = boost::stoer_wagner_min_cut( |
262 | param0: g, param1: get(p: boost::edge_weight, g), old_style_params: boost::max_priority_queue(p&: pq)); |
263 | BOOST_TEST_EQ(w, 3407); |
264 | } |
265 | |
266 | // 7 min-cuts |
267 | void test_prgen_50_40_2() |
268 | { |
269 | typedef boost::graph_traits< undirected_graph >::vertex_descriptor |
270 | vertex_descriptor; |
271 | |
272 | std::ifstream ifs( |
273 | (test_dir + "/prgen_input_graphs/prgen_50_40_2.net" ).c_str()); |
274 | undirected_graph g; |
275 | boost::read_dimacs_min_cut( |
276 | g, capacity: get(p: boost::edge_weight, g), reverse_edge: boost::dummy_property_map(), in&: ifs); |
277 | |
278 | std::map< vertex_descriptor, std::size_t > component; |
279 | boost::associative_property_map< |
280 | std::map< vertex_descriptor, std::size_t > > |
281 | components(component); |
282 | BOOST_TEST_EQ(boost::connected_components(g, components), |
283 | 1U); // verify the connectedness assumption |
284 | |
285 | int w = boost::stoer_wagner_min_cut(param0: g, param1: get(p: boost::edge_weight, g)); |
286 | BOOST_TEST_EQ(w, 10056); |
287 | } |
288 | |
289 | // 6 min-cuts |
290 | void test_prgen_50_70_2() |
291 | { |
292 | typedef boost::graph_traits< undirected_graph >::vertex_descriptor |
293 | vertex_descriptor; |
294 | |
295 | std::ifstream ifs( |
296 | (test_dir + "/prgen_input_graphs/prgen_50_70_2.net" ).c_str()); |
297 | undirected_graph g; |
298 | boost::read_dimacs_min_cut( |
299 | g, capacity: get(p: boost::edge_weight, g), reverse_edge: boost::dummy_property_map(), in&: ifs); |
300 | |
301 | std::map< vertex_descriptor, std::size_t > component; |
302 | boost::associative_property_map< |
303 | std::map< vertex_descriptor, std::size_t > > |
304 | components(component); |
305 | BOOST_TEST_EQ(boost::connected_components(g, components), |
306 | 1U); // verify the connectedness assumption |
307 | |
308 | int w = boost::stoer_wagner_min_cut(param0: g, param1: get(p: boost::edge_weight, g)); |
309 | BOOST_TEST_EQ(w, 21755); |
310 | } |
311 | |
312 | int main(int argc, char* argv[]) |
313 | { |
314 | if (BOOST_TEST(argc == 2)) |
315 | { |
316 | test_dir = argv[1]; |
317 | test0(); |
318 | test1(); |
319 | test2(); |
320 | test3(); |
321 | test4(); |
322 | test5(); |
323 | test_prgen_20_70_2(); |
324 | test_prgen_50_70_2(); |
325 | } |
326 | return boost::report_errors(); |
327 | } |
328 | |