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 #include <cassert>
7 #include <cstddef>
8 #include <cstdlib>
9 #include <iostream>
10 #include <boost/graph/adjacency_list.hpp>
11 #include <boost/graph/graph_traits.hpp>
12 #include <boost/graph/one_bit_color_map.hpp>
13 #include <boost/graph/stoer_wagner_min_cut.hpp>
14 #include <boost/property_map/property_map.hpp>
15 #include <boost/typeof/typeof.hpp>
16
17 struct edge_t
18 {
19 unsigned long first;
20 unsigned long second;
21 };
22
23 // A graphic of the min-cut is available at
24 // <http://www.boost.org/doc/libs/release/libs/graph/doc/stoer_wagner_imgs/stoer_wagner.cpp.gif>
main()25 int main()
26 {
27 using namespace std;
28
29 typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS,
30 boost::no_property, boost::property< boost::edge_weight_t, int > >
31 undirected_graph;
32 typedef boost::property_map< undirected_graph, boost::edge_weight_t >::type
33 weight_map_type;
34 typedef boost::property_traits< weight_map_type >::value_type weight_type;
35
36 // define the 16 edges of the graph. {3, 4} means an undirected edge between
37 // vertices 3 and 4.
38 edge_t edges[] = { { 3, 4 }, { 3, 6 }, { 3, 5 }, { 0, 4 }, { 0, 1 },
39 { 0, 6 }, { 0, 7 }, { 0, 5 }, { 0, 2 }, { 4, 1 }, { 1, 6 }, { 1, 5 },
40 { 6, 7 }, { 7, 5 }, { 5, 2 }, { 3, 4 } };
41
42 // for each of the 16 edges, define the associated edge weight. ws[i] is the
43 // weight for the edge that is described by edges[i].
44 weight_type ws[] = { 0, 3, 1, 3, 1, 2, 6, 1, 8, 1, 1, 80, 2, 1, 1, 4 };
45
46 // construct the graph object. 8 is the number of vertices, which are
47 // numbered from 0 through 7, and 16 is the number of edges.
48 undirected_graph g(edges, edges + 16, ws, 8, 16);
49
50 // define a property map, `parities`, that will store a boolean value for
51 // each vertex. Vertices that have the same parity after
52 // `stoer_wagner_min_cut` runs are on the same side of the min-cut.
53 BOOST_AUTO(parities,
54 boost::make_one_bit_color_map(
55 num_vertices(g), get(boost::vertex_index, g)));
56
57 // run the Stoer-Wagner algorithm to obtain the min-cut weight. `parities`
58 // is also filled in.
59 int w = boost::stoer_wagner_min_cut(
60 g, get(boost::edge_weight, g), boost::parity_map(parities));
61
62 cout << "The min-cut weight of G is " << w << ".\n" << endl;
63 assert(w == 7);
64
65 cout << "One set of vertices consists of:" << endl;
66 size_t i;
67 for (i = 0; i < num_vertices(g); ++i)
68 {
69 if (get(parities, i))
70 cout << i << endl;
71 }
72 cout << endl;
73
74 cout << "The other set of vertices consists of:" << endl;
75 for (i = 0; i < num_vertices(g); ++i)
76 {
77 if (!get(parities, i))
78 cout << i << endl;
79 }
80 cout << endl;
81
82 return EXIT_SUCCESS;
83 }
84
