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