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#ifndef BOOST_GRAPH_STOER_WAGNER_MIN_CUT_HPP
7#define BOOST_GRAPH_STOER_WAGNER_MIN_CUT_HPP 1
8
9#include <boost/assert.hpp>
10#include <set>
11#include <vector>
12#include <boost/concept_check.hpp>
13#include <boost/concept/assert.hpp>
14#include <boost/graph/adjacency_list.hpp>
15#include <boost/graph/buffer_concepts.hpp>
16#include <boost/graph/exception.hpp>
17#include <boost/graph/graph_traits.hpp>
18#include <boost/graph/maximum_adjacency_search.hpp>
19#include <boost/graph/named_function_params.hpp>
20#include <boost/graph/one_bit_color_map.hpp>
21#include <boost/graph/detail/d_ary_heap.hpp>
22#include <boost/property_map/property_map.hpp>
23#include <boost/tuple/tuple.hpp>
24#include <boost/utility/result_of.hpp>
25#include <boost/graph/iteration_macros.hpp>
26
27namespace boost {
28
29 namespace detail {
30 template < typename ParityMap, typename WeightMap, typename IndexMap >
31 class mas_min_cut_visitor : public boost::default_mas_visitor {
32 typedef one_bit_color_map <IndexMap> InternalParityMap;
33 typedef typename boost::property_traits<WeightMap>::value_type weight_type;
34 public:
35 template < typename Graph >
36 mas_min_cut_visitor(const Graph& g,
37 ParityMap parity,
38 weight_type& cutweight,
39 const WeightMap& weight_map,
40 IndexMap index_map)
41 : m_bestParity(parity),
42 m_parity(make_one_bit_color_map(num_vertices(g), index_map)),
43 m_bestWeight(cutweight),
44 m_cutweight(0),
45 m_visited(0),
46 m_weightMap(weight_map)
47 {
48 // set here since the init list sets the reference
49 m_bestWeight = (std::numeric_limits<weight_type>::max)();
50 }
51
52 template < typename Vertex, typename Graph >
53 void initialize_vertex(Vertex u, const Graph & g)
54 {
55 typedef typename boost::property_traits<ParityMap>::value_type parity_type;
56 typedef typename boost::property_traits<InternalParityMap>::value_type internal_parity_type;
57
58 put(m_parity, u, internal_parity_type(0));
59 put(m_bestParity, u, parity_type(0));
60 }
61
62 template < typename Edge, typename Graph >
63 void examine_edge(Edge e, const Graph & g)
64 {
65 weight_type w = get(m_weightMap, e);
66
67 // if the target of e is already marked then decrease cutweight
68 // otherwise, increase it
69 if (get(m_parity, boost::target(e, g))) {
70 m_cutweight -= w;
71 } else {
72 m_cutweight += w;
73 }
74 }
75
76 template < typename Vertex, typename Graph >
77 void finish_vertex(Vertex u, const Graph & g)
78 {
79 typedef typename boost::property_traits<InternalParityMap>::value_type internal_parity_type;
80
81 ++m_visited;
82 put(m_parity, u, internal_parity_type(1));
83
84 if (m_cutweight < m_bestWeight && m_visited < num_vertices(g)) {
85 m_bestWeight = m_cutweight;
86 BGL_FORALL_VERTICES_T(i, g, Graph) {
87 put(m_bestParity,i, get(m_parity,i));
88 }
89 }
90 }
91
92 inline void clear() {
93 m_bestWeight = (std::numeric_limits<weight_type>::max)();
94 m_visited = 0;
95 m_cutweight = 0;
96 }
97
98 private:
99 ParityMap m_bestParity;
100 InternalParityMap m_parity;
101 weight_type& m_bestWeight;
102 weight_type m_cutweight;
103 unsigned m_visited;
104 const WeightMap& m_weightMap;
105 };
106
107 /**
108 * \brief Computes a min-cut of the input graph
109 *
110 * Computes a min-cut of the input graph using the Stoer-Wagner algorithm.
111 *
112 * \pre \p g is a connected, undirected graph
113 * \pre <code>pq.empty()</code>
114 * \param[in] g the input graph
115 * \param[in] weights a readable property map from each edge to its weight (a non-negative value)
116 * \param[out] parities a writable property map from each vertex to a bool type object for
117 * distinguishing the two vertex sets of the min-cut
118 * \param[out] assignments a read/write property map from each vertex to a \c vertex_descriptor object. This
119 * map serves as work space, and no particular meaning should be derived from property values
120 * after completion of the algorithm.
121 * \param[out] pq a keyed, updatable max-priority queue
122 * \returns the cut weight of the min-cut
123 * \see http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.114.6687&rep=rep1&type=pdf
124 * \see http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.31.614&rep=rep1&type=pdf
125 *
126 * \author Daniel Trebbien
127 * \date 2010-09-11
128 */
129 template <class UndirectedGraph, class WeightMap, class ParityMap, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue, class IndexMap>
130 typename boost::property_traits<WeightMap>::value_type
131 stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights, ParityMap parities, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue& pq, IndexMap index_map) {
132 typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_descriptor;
133 typedef typename boost::property_traits<WeightMap>::value_type weight_type;
134
135 typename graph_traits<UndirectedGraph>::vertex_iterator u_iter, u_end;
136
137 weight_type bestW = (std::numeric_limits<weight_type>::max)();
138 weight_type bestThisTime = (std::numeric_limits<weight_type>::max)();
139 vertex_descriptor bestStart = boost::graph_traits<UndirectedGraph>::null_vertex();
140
141 detail::mas_min_cut_visitor<ParityMap, WeightMap, IndexMap>
142 vis(g, parities, bestThisTime, weights, index_map);
143
144 // for each node in the graph,
145 for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) {
146 // run the MAS and find the min cut
147 vis.clear();
148 boost::maximum_adjacency_search(g,
149 boost::weight_map(weights).
150 visitor(vis).
151 root_vertex(*u_iter).
152 vertex_assignment_map(assignments).
153 max_priority_queue(pq));
154 if (bestThisTime < bestW) {
155 bestW = bestThisTime;
156 bestStart = *u_iter;
157 }
158 }
159
160 // Run one more time, starting from the best start location, to
161 // ensure the visitor has the best values.
162 vis.clear();
163 boost::maximum_adjacency_search(g,
164 boost::vertex_assignment_map(assignments).
165 weight_map(weights).
166 visitor(vis).
167 root_vertex(bestStart).
168 max_priority_queue(pq));
169
170 return bestW;
171 }
172 } // end `namespace detail` within `namespace boost`
173
174 template <class UndirectedGraph, class WeightMap, class ParityMap, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue, class IndexMap>
175 typename boost::property_traits<WeightMap>::value_type
176 stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights, ParityMap parities, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue& pq, IndexMap index_map) {
177 BOOST_CONCEPT_ASSERT((boost::IncidenceGraphConcept<UndirectedGraph>));
178 BOOST_CONCEPT_ASSERT((boost::VertexListGraphConcept<UndirectedGraph>));
179 typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_descriptor;
180 typedef typename boost::graph_traits<UndirectedGraph>::vertices_size_type vertices_size_type;
181 typedef typename boost::graph_traits<UndirectedGraph>::edge_descriptor edge_descriptor;
182 BOOST_CONCEPT_ASSERT((boost::Convertible<typename boost::graph_traits<UndirectedGraph>::directed_category, boost::undirected_tag>));
183 BOOST_CONCEPT_ASSERT((boost::ReadablePropertyMapConcept<WeightMap, edge_descriptor>));
184 // typedef typename boost::property_traits<WeightMap>::value_type weight_type;
185 BOOST_CONCEPT_ASSERT((boost::WritablePropertyMapConcept<ParityMap, vertex_descriptor>));
186 // typedef typename boost::property_traits<ParityMap>::value_type parity_type;
187 BOOST_CONCEPT_ASSERT((boost::ReadWritePropertyMapConcept<VertexAssignmentMap, vertex_descriptor>));
188 BOOST_CONCEPT_ASSERT((boost::Convertible<vertex_descriptor, typename boost::property_traits<VertexAssignmentMap>::value_type>));
189 BOOST_CONCEPT_ASSERT((boost::KeyedUpdatableQueueConcept<KeyedUpdatablePriorityQueue>));
190
191 vertices_size_type n = num_vertices(g);
192 if (n < 2)
193 throw boost::bad_graph("the input graph must have at least two vertices.");
194 else if (!pq.empty())
195 throw std::invalid_argument("the max-priority queue must be empty initially.");
196
197 return detail::stoer_wagner_min_cut(g, weights,
198 parities, assignments, pq, index_map);
199 }
200
201namespace graph {
202 namespace detail {
203 template <class UndirectedGraph, class WeightMap>
204 struct stoer_wagner_min_cut_impl {
205 typedef typename boost::property_traits<WeightMap>::value_type result_type;
206 template <typename ArgPack>
207 result_type operator() (const UndirectedGraph& g, WeightMap weights, const ArgPack& arg_pack) const {
208 using namespace boost::graph::keywords;
209 typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_descriptor;
210 typedef typename boost::property_traits<WeightMap>::value_type weight_type;
211
212 typedef boost::detail::make_priority_queue_from_arg_pack_gen<boost::graph::keywords::tag::max_priority_queue, weight_type, vertex_descriptor, std::greater<weight_type> > gen_type;
213
214 gen_type gen(choose_param(get_param(arg_pack, boost::distance_zero_t()), weight_type(0)));
215
216 typename boost::result_of<gen_type(const UndirectedGraph&, const ArgPack&)>::type pq = gen(g, arg_pack);
217
218 return boost::stoer_wagner_min_cut(g,
219 weights,
220 arg_pack [_parity_map | boost::dummy_property_map()],
221 boost::detail::make_property_map_from_arg_pack_gen<tag::vertex_assignment_map, vertex_descriptor>(vertex_descriptor())(g, arg_pack),
222 pq,
223 boost::detail::override_const_property(arg_pack, _vertex_index_map, g, vertex_index)
224 );
225 }
226 };
227 }
228 BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(stoer_wagner_min_cut,2,4)
229}
230
231 // Named parameter interface
232 BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(stoer_wagner_min_cut, 2)
233namespace graph {
234 // version without IndexMap kept for backwards compatibility
235 // (but requires vertex_index_t to be defined in the graph)
236 // Place after the macro to avoid compilation errors
237 template <class UndirectedGraph, class WeightMap, class ParityMap, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue>
238 typename boost::property_traits<WeightMap>::value_type
239 stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights, ParityMap parities, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue& pq) {
240
241 return stoer_wagner_min_cut(g, weights,
242 parities, assignments, pq,
243 get(vertex_index, g));
244 }
245} // end `namespace graph`
246} // end `namespace boost`
247
248#include <boost/graph/iteration_macros_undef.hpp>
249
250#endif // !BOOST_GRAPH_STOER_WAGNER_MIN_CUT_HPP
251

source code of boost/boost/graph/stoer_wagner_min_cut.hpp