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/test/unit_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
init_unit_test_suite(int argc,char * argv[])38 boost::unit_test::test_suite* init_unit_test_suite(int argc, char* argv[])
39 {
40 if (argc != 2)
41 {
42 std::cerr << "Usage: " << argv[0] << " path-to-libs-graph-test"
43 << std::endl;
44 throw boost::unit_test::framework::setup_error(
45 "Invalid command line arguments");
46 }
47 test_dir = argv[1];
48 return 0;
49 }
50
51 struct edge_t
52 {
53 unsigned long first;
54 unsigned long second;
55 };
56
57 // the example from Stoer & Wagner (1997)
BOOST_AUTO_TEST_CASE(test0)58 BOOST_AUTO_TEST_CASE(test0)
59 {
60 edge_t edges[] = { { 0, 1 }, { 1, 2 }, { 2, 3 }, { 0, 4 }, { 1, 4 },
61 { 1, 5 }, { 2, 6 }, { 3, 6 }, { 3, 7 }, { 4, 5 }, { 5, 6 }, { 6, 7 } };
62 weight_type ws[] = { 2, 3, 4, 3, 2, 2, 2, 2, 2, 3, 1, 3 };
63 undirected_graph g(edges, edges + 12, ws, 8, 12);
64
65 weight_map_type weights = get(boost::edge_weight, g);
66 std::map< int, bool > parity;
67 boost::associative_property_map< std::map< int, bool > > parities(parity);
68 int w
69 = boost::stoer_wagner_min_cut(g, weights, boost::parity_map(parities));
70 BOOST_CHECK_EQUAL(w, 4);
71 const bool parity0 = get(parities, 0);
72 BOOST_CHECK_EQUAL(parity0, get(parities, 1));
73 BOOST_CHECK_EQUAL(parity0, get(parities, 4));
74 BOOST_CHECK_EQUAL(parity0, get(parities, 5));
75 const bool parity2 = get(parities, 2);
76 BOOST_CHECK_NE(parity0, parity2);
77 BOOST_CHECK_EQUAL(parity2, get(parities, 3));
78 BOOST_CHECK_EQUAL(parity2, get(parities, 6));
79 BOOST_CHECK_EQUAL(parity2, get(parities, 7));
80 }
81
BOOST_AUTO_TEST_CASE(test1)82 BOOST_AUTO_TEST_CASE(test1)
83 {
84 { // if only one vertex, can't run `boost::stoer_wagner_min_cut`
85 undirected_graph g;
86 add_vertex(g);
87
88 BOOST_CHECK_THROW(
89 boost::stoer_wagner_min_cut(g, get(boost::edge_weight, g)),
90 boost::bad_graph);
91 }
92 { // three vertices with one multi-edge
93 typedef boost::graph_traits< undirected_graph >::vertex_descriptor
94 vertex_descriptor;
95
96 edge_t edges[] = { { 0, 1 }, { 1, 2 }, { 1, 2 }, { 2, 0 } };
97 weight_type ws[] = { 3, 1, 1, 1 };
98 undirected_graph g(edges, edges + 4, ws, 3, 4);
99
100 weight_map_type weights = get(boost::edge_weight, g);
101 std::map< int, bool > parity;
102 boost::associative_property_map< std::map< int, bool > > parities(
103 parity);
104 std::map< vertex_descriptor, vertex_descriptor > assignment;
105 boost::associative_property_map<
106 std::map< vertex_descriptor, vertex_descriptor > >
107 assignments(assignment);
108 int w = boost::stoer_wagner_min_cut(g, weights,
109 boost::parity_map(parities).vertex_assignment_map(assignments));
110 BOOST_CHECK_EQUAL(w, 3);
111 const bool parity2 = get(parities, 2), parity0 = get(parities, 0);
112 BOOST_CHECK_NE(parity2, parity0);
113 BOOST_CHECK_EQUAL(parity0, get(parities, 1));
114 }
115 }
116
117 // example by Daniel Trebbien
BOOST_AUTO_TEST_CASE(test2)118 BOOST_AUTO_TEST_CASE(test2)
119 {
120 edge_t edges[] = { { 5, 2 }, { 0, 6 }, { 5, 6 }, { 3, 1 }, { 0, 1 },
121 { 6, 3 }, { 4, 6 }, { 2, 4 }, { 5, 3 } };
122 weight_type ws[] = { 1, 3, 4, 6, 4, 1, 2, 5, 2 };
123 undirected_graph g(edges, edges + 9, ws, 7, 9);
124
125 std::map< int, bool > parity;
126 boost::associative_property_map< std::map< int, bool > > parities(parity);
127 int w = boost::stoer_wagner_min_cut(
128 g, get(boost::edge_weight, g), boost::parity_map(parities));
129 BOOST_CHECK_EQUAL(w, 3);
130 const bool parity2 = get(parities, 2);
131 BOOST_CHECK_EQUAL(parity2, get(parities, 4));
132 const bool parity5 = get(parities, 5);
133 BOOST_CHECK_NE(parity2, parity5);
134 BOOST_CHECK_EQUAL(parity5, get(parities, 3));
135 BOOST_CHECK_EQUAL(parity5, get(parities, 6));
136 BOOST_CHECK_EQUAL(parity5, get(parities, 1));
137 BOOST_CHECK_EQUAL(parity5, get(parities, 0));
138 }
139
140 // example by Daniel Trebbien
BOOST_AUTO_TEST_CASE(test3)141 BOOST_AUTO_TEST_CASE(test3)
142 {
143 edge_t edges[] = { { 3, 4 }, { 3, 6 }, { 3, 5 }, { 0, 4 }, { 0, 1 },
144 { 0, 6 }, { 0, 7 }, { 0, 5 }, { 0, 2 }, { 4, 1 }, { 1, 6 }, { 1, 5 },
145 { 6, 7 }, { 7, 5 }, { 5, 2 }, { 3, 4 } };
146 weight_type ws[] = { 0, 3, 1, 3, 1, 2, 6, 1, 8, 1, 1, 80, 2, 1, 1, 4 };
147 undirected_graph g(edges, edges + 16, ws, 8, 16);
148
149 weight_map_type weights = get(boost::edge_weight, g);
150 std::map< int, bool > parity;
151 boost::associative_property_map< std::map< int, bool > > parities(parity);
152 int w
153 = boost::stoer_wagner_min_cut(g, weights, boost::parity_map(parities));
154 BOOST_CHECK_EQUAL(w, 7);
155 const bool parity1 = get(parities, 1);
156 BOOST_CHECK_EQUAL(parity1, get(parities, 5));
157 const bool parity0 = get(parities, 0);
158 BOOST_CHECK_NE(parity1, parity0);
159 BOOST_CHECK_EQUAL(parity0, get(parities, 2));
160 BOOST_CHECK_EQUAL(parity0, get(parities, 3));
161 BOOST_CHECK_EQUAL(parity0, get(parities, 4));
162 BOOST_CHECK_EQUAL(parity0, get(parities, 6));
163 BOOST_CHECK_EQUAL(parity0, get(parities, 7));
164 }
165
BOOST_AUTO_TEST_CASE(test4)166 BOOST_AUTO_TEST_CASE(test4)
167 {
168 typedef boost::graph_traits<
169 undirected_unweighted_graph >::vertex_descriptor vertex_descriptor;
170 typedef boost::graph_traits< undirected_unweighted_graph >::edge_descriptor
171 edge_descriptor;
172
173 edge_t edges[] = { { 0, 1 }, { 1, 2 }, { 2, 3 }, { 0, 4 }, { 1, 4 },
174 { 1, 5 }, { 2, 6 }, { 3, 6 }, { 3, 7 }, { 4, 5 }, { 5, 6 }, { 6, 7 },
175 { 0, 4 }, { 6, 7 } };
176 undirected_unweighted_graph g(edges, edges + 14, 8);
177
178 std::map< vertex_descriptor, bool > parity;
179 boost::associative_property_map< std::map< vertex_descriptor, bool > >
180 parities(parity);
181 std::map< vertex_descriptor, vertex_descriptor > assignment;
182 boost::associative_property_map<
183 std::map< vertex_descriptor, vertex_descriptor > >
184 assignments(assignment);
185 int w = boost::stoer_wagner_min_cut(g,
186 boost::make_constant_property< edge_descriptor >(weight_type(1)),
187 boost::vertex_assignment_map(assignments).parity_map(parities));
188 BOOST_CHECK_EQUAL(w, 2);
189 const bool parity0 = get(parities, 0);
190 BOOST_CHECK_EQUAL(parity0, get(parities, 1));
191 BOOST_CHECK_EQUAL(parity0, get(parities, 4));
192 BOOST_CHECK_EQUAL(parity0, get(parities, 5));
193 const bool parity2 = get(parities, 2);
194 BOOST_CHECK_NE(parity0, parity2);
195 BOOST_CHECK_EQUAL(parity2, get(parities, 3));
196 BOOST_CHECK_EQUAL(parity2, get(parities, 6));
197 BOOST_CHECK_EQUAL(parity2, get(parities, 7));
198 }
199
200 // The input for the `test_prgen` family of tests comes from a program, named
201 // `prgen`, that comes with a package of min-cut solvers by Chandra Chekuri,
202 // Andrew Goldberg, David Karger, Matthew Levine, and Cliff Stein. `prgen` was
203 // used to generate input graphs and the solvers were used to verify the return
204 // value of `boost::stoer_wagner_min_cut` on the input graphs.
205 //
206 // http://www.columbia.edu/~cs2035/code.html
207 //
208 // Note that it is somewhat more difficult to verify the parities because
209 // "`prgen` graphs" often have several min-cuts. This is why only the cut
210 // weight of the min-cut is verified.
211
212 // 3 min-cuts
BOOST_AUTO_TEST_CASE(test_prgen_20_70_2)213 BOOST_AUTO_TEST_CASE(test_prgen_20_70_2)
214 {
215 typedef boost::graph_traits< undirected_graph >::vertex_descriptor
216 vertex_descriptor;
217
218 std::ifstream ifs(
219 (test_dir + "/prgen_input_graphs/prgen_20_70_2.net").c_str());
220 undirected_graph g;
221 boost::read_dimacs_min_cut(
222 g, get(boost::edge_weight, g), boost::dummy_property_map(), ifs);
223
224 std::map< vertex_descriptor, std::size_t > component;
225 boost::associative_property_map<
226 std::map< vertex_descriptor, std::size_t > >
227 components(component);
228 BOOST_CHECK_EQUAL(boost::connected_components(g, components),
229 1U); // verify the connectedness assumption
230
231 typedef boost::shared_array_property_map< weight_type,
232 boost::property_map< undirected_graph,
233 boost::vertex_index_t >::const_type >
234 distances_type;
235 distances_type distances = boost::make_shared_array_property_map(
236 num_vertices(g), weight_type(0), get(boost::vertex_index, g));
237 typedef std::vector< vertex_descriptor >::size_type index_in_heap_type;
238 typedef boost::shared_array_property_map< index_in_heap_type,
239 boost::property_map< undirected_graph,
240 boost::vertex_index_t >::const_type >
241 indicesInHeap_type;
242 indicesInHeap_type indicesInHeap = boost::make_shared_array_property_map(
243 num_vertices(g), index_in_heap_type(-1), get(boost::vertex_index, g));
244 boost::d_ary_heap_indirect< vertex_descriptor, 22, indicesInHeap_type,
245 distances_type, std::greater< weight_type > >
246 pq(distances, indicesInHeap);
247
248 int w = boost::stoer_wagner_min_cut(
249 g, get(boost::edge_weight, g), boost::max_priority_queue(pq));
250 BOOST_CHECK_EQUAL(w, 3407);
251 }
252
253 // 7 min-cuts
BOOST_AUTO_TEST_CASE(test_prgen_50_40_2)254 BOOST_AUTO_TEST_CASE(test_prgen_50_40_2)
255 {
256 typedef boost::graph_traits< undirected_graph >::vertex_descriptor
257 vertex_descriptor;
258
259 std::ifstream ifs(
260 (test_dir + "/prgen_input_graphs/prgen_50_40_2.net").c_str());
261 undirected_graph g;
262 boost::read_dimacs_min_cut(
263 g, get(boost::edge_weight, g), boost::dummy_property_map(), ifs);
264
265 std::map< vertex_descriptor, std::size_t > component;
266 boost::associative_property_map<
267 std::map< vertex_descriptor, std::size_t > >
268 components(component);
269 BOOST_CHECK_EQUAL(boost::connected_components(g, components),
270 1U); // verify the connectedness assumption
271
272 int w = boost::stoer_wagner_min_cut(g, get(boost::edge_weight, g));
273 BOOST_CHECK_EQUAL(w, 10056);
274 }
275
276 // 6 min-cuts
BOOST_AUTO_TEST_CASE(test_prgen_50_70_2)277 BOOST_AUTO_TEST_CASE(test_prgen_50_70_2)
278 {
279 typedef boost::graph_traits< undirected_graph >::vertex_descriptor
280 vertex_descriptor;
281
282 std::ifstream ifs(
283 (test_dir + "/prgen_input_graphs/prgen_50_70_2.net").c_str());
284 undirected_graph g;
285 boost::read_dimacs_min_cut(
286 g, get(boost::edge_weight, g), boost::dummy_property_map(), ifs);
287
288 std::map< vertex_descriptor, std::size_t > component;
289 boost::associative_property_map<
290 std::map< vertex_descriptor, std::size_t > >
291 components(component);
292 BOOST_CHECK_EQUAL(boost::connected_components(g, components),
293 1U); // verify the connectedness assumption
294
295 int w = boost::stoer_wagner_min_cut(g, get(boost::edge_weight, g));
296 BOOST_CHECK_EQUAL(w, 21755);
297 }
298