]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |