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 | 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 | |
201 | namespace 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) |
233 | namespace 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 | |