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
26typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS,
27 boost::no_property, boost::property< boost::edge_weight_t, int > >
28 undirected_graph;
29typedef boost::property_map< undirected_graph, boost::edge_weight_t >::type
30 weight_map_type;
31typedef boost::property_traits< weight_map_type >::value_type weight_type;
32
33typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS >
34 undirected_unweighted_graph;
35
36std::string test_dir;
37
38struct edge_t
39{
40 unsigned long first;
41 unsigned long second;
42};
43
44// the example from Stoer & Wagner (1997)
45void 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
69void 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
105void 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
128void 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
153void 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
188void 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
226void 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
267void 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
290void 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
312int 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

source code of boost/libs/graph/test/stoer_wagner_test.cpp