1 //
2 //=======================================================================
3 // Copyright 2012 Fernando Vilas
4 // 2010 Daniel Trebbien
5 //
6 // Distributed under the Boost Software License, Version 1.0. (See
7 // accompanying file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
9 //=======================================================================
10 //
11
12 // The maximum adjacency search algorithm was originally part of the
13 // Stoer-Wagner min cut implementation by Daniel Trebbien. It has been
14 // broken out into its own file to be a public search algorithm, with
15 // visitor concepts.
16 #ifndef BOOST_GRAPH_MAXIMUM_ADJACENCY_SEARCH_H
17 #define BOOST_GRAPH_MAXIMUM_ADJACENCY_SEARCH_H
18
19 /**
20 * This is an implementation of the maximum adjacency search on an
21 * undirected graph. It allows a visitor object to perform some
22 * operation on each vertex as that vertex is visited.
23 *
24 * The algorithm runs as follows:
25 *
26 * Initialize all nodes to be unvisited (reach count = 0)
27 * and call vis.initialize_vertex
28 * For i = number of nodes in graph downto 1
29 * Select the unvisited node with the highest reach count
30 * The user provides the starting node to break the first tie,
31 * but future ties are broken arbitrarily
32 * Visit the node by calling vis.start_vertex
33 * Increment the reach count for all unvisited neighbors
34 * and call vis.examine_edge for each of these edges
35 * Mark the node as visited and call vis.finish_vertex
36 *
37 */
38
39 #include <boost/concept_check.hpp>
40 #include <boost/concept/assert.hpp>
41 #include <boost/graph/buffer_concepts.hpp>
42 #include <boost/graph/exception.hpp>
43 #include <boost/graph/graph_concepts.hpp>
44 #include <boost/graph/iteration_macros.hpp>
45 #include <boost/graph/named_function_params.hpp>
46 #include <boost/graph/visitors.hpp>
47 #include <boost/tuple/tuple.hpp>
48
49 #include <set>
50
51 namespace boost
52 {
53 template < class Visitor, class Graph > struct MASVisitorConcept
54 {
constraintsboost::MASVisitorConcept55 void constraints()
56 {
57 boost::function_requires<
58 boost::CopyConstructibleConcept< Visitor > >();
59 vis.initialize_vertex(u, g);
60 vis.start_vertex(u, g);
61 vis.examine_edge(e, g);
62 vis.finish_vertex(u, g);
63 }
64 Visitor vis;
65 Graph g;
66 typename boost::graph_traits< Graph >::vertex_descriptor u;
67 typename boost::graph_traits< Graph >::edge_descriptor e;
68 };
69
70 template < class Visitors = null_visitor > class mas_visitor
71 {
72 public:
mas_visitor()73 mas_visitor() {}
mas_visitor(Visitors vis)74 mas_visitor(Visitors vis) : m_vis(vis) {}
75
76 template < class Vertex, class Graph >
initialize_vertex(Vertex u,Graph & g)77 void initialize_vertex(Vertex u, Graph& g)
78 {
79 invoke_visitors(m_vis, u, g, ::boost::on_initialize_vertex());
80 }
81
start_vertex(Vertex u,Graph & g)82 template < class Vertex, class Graph > void start_vertex(Vertex u, Graph& g)
83 {
84 invoke_visitors(m_vis, u, g, ::boost::on_start_vertex());
85 }
86
examine_edge(Edge e,Graph & g)87 template < class Edge, class Graph > void examine_edge(Edge e, Graph& g)
88 {
89 invoke_visitors(m_vis, e, g, ::boost::on_examine_edge());
90 }
91
92 template < class Vertex, class Graph >
finish_vertex(Vertex u,Graph & g)93 void finish_vertex(Vertex u, Graph& g)
94 {
95 invoke_visitors(m_vis, u, g, ::boost::on_finish_vertex());
96 }
97
98 BOOST_GRAPH_EVENT_STUB(on_initialize_vertex, mas)
99 BOOST_GRAPH_EVENT_STUB(on_start_vertex, mas)
100 BOOST_GRAPH_EVENT_STUB(on_examine_edge, mas)
101 BOOST_GRAPH_EVENT_STUB(on_finish_vertex, mas)
102
103 protected:
104 Visitors m_vis;
105 };
106 template < class Visitors >
make_mas_visitor(Visitors vis)107 mas_visitor< Visitors > make_mas_visitor(Visitors vis)
108 {
109 return mas_visitor< Visitors >(vis);
110 }
111 typedef mas_visitor<> default_mas_visitor;
112
113 namespace detail
114 {
115 template < class Graph, class WeightMap, class MASVisitor,
116 class VertexAssignmentMap, class KeyedUpdatablePriorityQueue >
maximum_adjacency_search(const Graph & g,WeightMap weights,MASVisitor vis,const typename boost::graph_traits<Graph>::vertex_descriptor start,VertexAssignmentMap assignments,KeyedUpdatablePriorityQueue pq)117 void maximum_adjacency_search(const Graph& g, WeightMap weights,
118 MASVisitor vis,
119 const typename boost::graph_traits< Graph >::vertex_descriptor start,
120 VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue pq)
121 {
122 typedef typename boost::graph_traits< Graph >::vertex_descriptor
123 vertex_descriptor;
124 typedef typename boost::property_traits< WeightMap >::value_type
125 weight_type;
126
127 std::set< vertex_descriptor > assignedVertices;
128
129 // initialize `assignments` (all vertices are initially
130 // assigned to themselves)
131 BGL_FORALL_VERTICES_T(v, g, Graph) { put(assignments, v, v); }
132
133 typename KeyedUpdatablePriorityQueue::key_map keys = pq.keys();
134
135 // set number of visited neighbors for all vertices to 0
136 BGL_FORALL_VERTICES_T(v, g, Graph)
137 {
138 if (v == get(assignments, v))
139 { // foreach u \in V do
140 put(keys, v, weight_type(0));
141 vis.initialize_vertex(v, g);
142
143 pq.push(v);
144 }
145 }
146 BOOST_ASSERT(pq.size() >= 2);
147
148 // Give the starting vertex high priority
149 put(keys, start, get(keys, start) + num_vertices(g) + 1);
150 pq.update(start);
151
152 // start traversing the graph
153 // vertex_descriptor s, t;
154 // weight_type w;
155 while (!pq.empty())
156 { // while PQ \neq {} do
157 const vertex_descriptor u = pq.top(); // u = extractmax(PQ)
158 /* weight_type w = */ get(keys, u);
159 vis.start_vertex(u, g);
160 pq.pop(); // vis.start_vertex(u, g);
161
162 BGL_FORALL_OUTEDGES_T(u, e, g, Graph)
163 { // foreach (u, v) \in E do
164 vis.examine_edge(e, g);
165
166 const vertex_descriptor v = get(assignments, target(e, g));
167
168 if (pq.contains(v))
169 { // if v \in PQ then
170 put(keys, v,
171 get(keys, v)
172 + get(weights,
173 e)); // increasekey(PQ, v, wA(v) + w(u, v))
174 pq.update(v);
175 }
176 }
177
178 typename std::set< vertex_descriptor >::const_iterator
179 assignedVertexIt,
180 assignedVertexEnd = assignedVertices.end();
181 for (assignedVertexIt = assignedVertices.begin();
182 assignedVertexIt != assignedVertexEnd; ++assignedVertexIt)
183 {
184 const vertex_descriptor uPrime = *assignedVertexIt;
185
186 if (get(assignments, uPrime) == u)
187 {
188 BGL_FORALL_OUTEDGES_T(uPrime, e, g, Graph)
189 { // foreach (u, v) \in E do
190 vis.examine_edge(e, g);
191
192 const vertex_descriptor v
193 = get(assignments, target(e, g));
194
195 if (pq.contains(v))
196 { // if v \in PQ then
197 put(keys, v,
198 get(keys, v)
199 + get(weights, e)); // increasekey(PQ, v,
200 // wA(v) + w(u, v))
201 pq.update(v);
202 }
203 }
204 }
205 }
206 vis.finish_vertex(u, g);
207 }
208 }
209 } // end namespace detail
210
211 template < class Graph, class WeightMap, class MASVisitor,
212 class VertexAssignmentMap, class KeyedUpdatablePriorityQueue >
maximum_adjacency_search(const Graph & g,WeightMap weights,MASVisitor vis,const typename boost::graph_traits<Graph>::vertex_descriptor start,VertexAssignmentMap assignments,KeyedUpdatablePriorityQueue pq)213 void maximum_adjacency_search(const Graph& g, WeightMap weights, MASVisitor vis,
214 const typename boost::graph_traits< Graph >::vertex_descriptor start,
215 VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue pq)
216 {
217 BOOST_CONCEPT_ASSERT((boost::IncidenceGraphConcept< Graph >));
218 BOOST_CONCEPT_ASSERT((boost::VertexListGraphConcept< Graph >));
219 typedef typename boost::graph_traits< Graph >::vertex_descriptor
220 vertex_descriptor;
221 typedef typename boost::graph_traits< Graph >::vertices_size_type
222 vertices_size_type;
223 typedef
224 typename boost::graph_traits< Graph >::edge_descriptor edge_descriptor;
225 BOOST_CONCEPT_ASSERT((boost::Convertible<
226 typename boost::graph_traits< Graph >::directed_category,
227 boost::undirected_tag >));
228 BOOST_CONCEPT_ASSERT(
229 (boost::ReadablePropertyMapConcept< WeightMap, edge_descriptor >));
230 // typedef typename boost::property_traits<WeightMap>::value_type
231 // weight_type;
232 boost::function_requires< MASVisitorConcept< MASVisitor, Graph > >();
233 BOOST_CONCEPT_ASSERT(
234 (boost::ReadWritePropertyMapConcept< VertexAssignmentMap,
235 vertex_descriptor >));
236 BOOST_CONCEPT_ASSERT((boost::Convertible< vertex_descriptor,
237 typename boost::property_traits< VertexAssignmentMap >::value_type >));
238 BOOST_CONCEPT_ASSERT(
239 (boost::KeyedUpdatableQueueConcept< KeyedUpdatablePriorityQueue >));
240
241 vertices_size_type n = num_vertices(g);
242 if (n < 2)
243 throw boost::bad_graph(
244 "the input graph must have at least two vertices.");
245 else if (!pq.empty())
246 throw std::invalid_argument(
247 "the max-priority queue must be empty initially.");
248
249 detail::maximum_adjacency_search(g, weights, vis, start, assignments, pq);
250 }
251
252 namespace graph
253 {
254 namespace detail
255 {
256 template < typename WeightMap > struct mas_dispatch
257 {
258 typedef void result_type;
259 template < typename Graph, typename ArgPack >
applyboost::graph::detail::mas_dispatch260 static result_type apply(const Graph& g,
261 // const bgl_named_params<P,T,R>& params,
262 const ArgPack& params, WeightMap w)
263 {
264
265 using namespace boost::graph::keywords;
266 typedef typename boost::graph_traits< Graph >::vertex_descriptor
267 vertex_descriptor;
268 typedef typename WeightMap::value_type weight_type;
269
270 typedef boost::detail::make_priority_queue_from_arg_pack_gen<
271 boost::graph::keywords::tag::max_priority_queue,
272 weight_type, vertex_descriptor,
273 std::greater< weight_type > >
274 default_pq_gen_type;
275
276 default_pq_gen_type pq_gen(
277 choose_param(get_param(params, boost::distance_zero_t()),
278 weight_type(0)));
279
280 typename boost::result_of< default_pq_gen_type(
281 const Graph&, const ArgPack&) >::type pq
282 = pq_gen(g, params);
283
284 boost::null_visitor null_vis;
285 boost::mas_visitor< boost::null_visitor > default_visitor(
286 null_vis);
287 vertex_descriptor v = vertex_descriptor();
288 boost::detail::make_property_map_from_arg_pack_gen<
289 boost::graph::keywords::tag::vertex_assignment_map,
290 vertex_descriptor >
291 map_gen(v);
292 typename boost::detail::map_maker< Graph, ArgPack,
293 boost::graph::keywords::tag::vertex_assignment_map,
294 vertex_descriptor >::map_type default_map
295 = map_gen(g, params);
296 boost::maximum_adjacency_search(g, w,
297 params[_visitor | default_visitor],
298 params[_root_vertex | *vertices(g).first],
299 params[_vertex_assignment_map | default_map], pq);
300 }
301 };
302
303 template <> struct mas_dispatch< boost::param_not_found >
304 {
305 typedef void result_type;
306
307 template < typename Graph, typename ArgPack >
applyboost::graph::detail::mas_dispatch308 static result_type apply(
309 const Graph& g, const ArgPack& params, param_not_found)
310 {
311
312 using namespace boost::graph::keywords;
313 typedef typename boost::graph_traits< Graph >::vertex_descriptor
314 vertex_descriptor;
315
316 // get edge_weight_t as the weight type
317 typedef typename boost::property_map< Graph, edge_weight_t >
318 WeightMap;
319 typedef typename WeightMap::value_type weight_type;
320
321 typedef boost::detail::make_priority_queue_from_arg_pack_gen<
322 boost::graph::keywords::tag::max_priority_queue,
323 weight_type, vertex_descriptor,
324 std::greater< weight_type > >
325 default_pq_gen_type;
326
327 default_pq_gen_type pq_gen(
328 choose_param(get_param(params, boost::distance_zero_t()),
329 weight_type(0)));
330
331 typename boost::result_of< default_pq_gen_type(
332 const Graph&, const ArgPack&) >::type pq
333 = pq_gen(g, params);
334
335 boost::null_visitor null_vis;
336 boost::mas_visitor< boost::null_visitor > default_visitor(
337 null_vis);
338 vertex_descriptor v = vertex_descriptor();
339 boost::detail::make_property_map_from_arg_pack_gen<
340 boost::graph::keywords::tag::vertex_assignment_map,
341 vertex_descriptor >
342 map_gen(v);
343 typename boost::detail::map_maker< Graph, ArgPack,
344 boost::graph::keywords::tag::vertex_assignment_map,
345 vertex_descriptor >::map_type default_map
346 = map_gen(g, params);
347 boost::maximum_adjacency_search(g, get(edge_weight, g),
348 params[_visitor | default_visitor],
349 params[_root_vertex | *vertices(g).first],
350 params[_vertex_assignment_map | default_map], pq);
351 }
352 };
353 } // end namespace detail
354 } // end namespace graph
355
356 // Named parameter interface
357 // BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(maximum_adjacency_search, 1)
358 template < typename Graph, typename P, typename T, typename R >
maximum_adjacency_search(const Graph & g,const bgl_named_params<P,T,R> & params)359 void maximum_adjacency_search(
360 const Graph& g, const bgl_named_params< P, T, R >& params)
361 {
362
363 typedef bgl_named_params< P, T, R > params_type;
364 BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params)
365
366 // do the dispatch based on WeightMap
367 typedef typename get_param_type< edge_weight_t,
368 bgl_named_params< P, T, R > >::type W;
369 graph::detail::mas_dispatch< W >::apply(
370 g, arg_pack, get_param(params, edge_weight));
371 }
372
373 namespace graph
374 {
375 namespace detail
376 {
377 template < typename Graph > struct maximum_adjacency_search_impl
378 {
379 typedef void result_type;
380
381 template < typename ArgPack >
operator ()boost::graph::detail::maximum_adjacency_search_impl382 void operator()(const Graph& g, const ArgPack& arg_pack) const
383 {
384 // call the function that does the dispatching
385 typedef
386 typename get_param_type< edge_weight_t, ArgPack >::type W;
387 graph::detail::mas_dispatch< W >::apply(
388 g, arg_pack, get_param(arg_pack, edge_weight));
389 }
390 };
391 } // end namespace detail
392 BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(maximum_adjacency_search, 1, 5)
393 } // end namespace graph
394
395 } // end namespace boost
396
397 #include <boost/graph/iteration_macros_undef.hpp>
398
399 #endif // BOOST_GRAPH_MAXIMUM_ADJACENCY_SEARCH_H
400