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
51namespace boost {
52 template <class Visitor, class Graph>
53 struct MASVisitorConcept {
54 void constraints() {
55 boost::function_requires< boost::CopyConstructibleConcept<Visitor> >();
56 vis.initialize_vertex(u, g);
57 vis.start_vertex(u, g);
58 vis.examine_edge(e, g);
59 vis.finish_vertex(u, g);
60 }
61 Visitor vis;
62 Graph g;
63 typename boost::graph_traits<Graph>::vertex_descriptor u;
64 typename boost::graph_traits<Graph>::edge_descriptor e;
65 };
66
67 template <class Visitors = null_visitor>
68 class mas_visitor {
69 public:
70 mas_visitor() { }
71 mas_visitor(Visitors vis) : m_vis(vis) { }
72
73 template <class Vertex, class Graph>
74 void
75 initialize_vertex(Vertex u, Graph& g)
76 {
77 invoke_visitors(m_vis, u, g, ::boost::on_initialize_vertex());
78 }
79
80 template <class Vertex, class Graph>
81 void
82 start_vertex(Vertex u, Graph& g)
83 {
84 invoke_visitors(m_vis, u, g, ::boost::on_start_vertex());
85 }
86
87 template <class Edge, class Graph>
88 void
89 examine_edge(Edge e, Graph& g)
90 {
91 invoke_visitors(m_vis, e, g, ::boost::on_examine_edge());
92 }
93
94 template <class Vertex, class Graph>
95 void
96 finish_vertex(Vertex u, Graph& g)
97 {
98 invoke_visitors(m_vis, u, g, ::boost::on_finish_vertex());
99 }
100
101 BOOST_GRAPH_EVENT_STUB(on_initialize_vertex,mas)
102 BOOST_GRAPH_EVENT_STUB(on_start_vertex,mas)
103 BOOST_GRAPH_EVENT_STUB(on_examine_edge,mas)
104 BOOST_GRAPH_EVENT_STUB(on_finish_vertex,mas)
105
106 protected:
107 Visitors m_vis;
108 };
109 template <class Visitors>
110 mas_visitor<Visitors>
111 make_mas_visitor(Visitors vis) {
112 return mas_visitor<Visitors>(vis);
113 }
114 typedef mas_visitor<> default_mas_visitor;
115
116 namespace detail {
117 template <class Graph, class WeightMap, class MASVisitor, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue>
118 void
119 maximum_adjacency_search(const Graph& g, WeightMap weights, MASVisitor vis, const typename boost::graph_traits<Graph>::vertex_descriptor start, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue pq) {
120 typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
121 typedef typename boost::property_traits<WeightMap>::value_type weight_type;
122
123 std::set<vertex_descriptor> assignedVertices;
124
125 // initialize `assignments` (all vertices are initially
126 // assigned to themselves)
127 BGL_FORALL_VERTICES_T(v, g, Graph) {
128 put(assignments, v, v);
129 }
130
131 typename KeyedUpdatablePriorityQueue::key_map keys = pq.keys();
132
133 // set number of visited neighbors for all vertices to 0
134 BGL_FORALL_VERTICES_T(v, g, Graph) {
135 if (v == get(assignments, v)) { // foreach u \in V do
136 put(keys, v, weight_type(0)); vis.initialize_vertex(v, g);
137
138 pq.push(v);
139 }
140 }
141 BOOST_ASSERT(pq.size() >= 2);
142
143 // Give the starting vertex high priority
144 put(keys, start, get(keys, start) + num_vertices(g) + 1);
145 pq.update(start);
146
147 // start traversing the graph
148 //vertex_descriptor s, t;
149 weight_type w;
150 while (!pq.empty()) { // while PQ \neq {} do
151 const vertex_descriptor u = pq.top(); // u = extractmax(PQ)
152 w = get(keys, u); vis.start_vertex(u, g);
153 pq.pop(); // vis.start_vertex(u, g);
154
155 BGL_FORALL_OUTEDGES_T(u, e, g, Graph) { // foreach (u, v) \in E do
156 vis.examine_edge(e, g);
157
158 const vertex_descriptor v = get(assignments, target(e, g));
159
160 if (pq.contains(v)) { // if v \in PQ then
161 put(keys, v, get(keys, v) + get(weights, e)); // increasekey(PQ, v, wA(v) + w(u, v))
162 pq.update(v);
163 }
164 }
165
166 typename std::set<vertex_descriptor>::const_iterator assignedVertexIt, assignedVertexEnd = assignedVertices.end();
167 for (assignedVertexIt = assignedVertices.begin(); assignedVertexIt != assignedVertexEnd; ++assignedVertexIt) {
168 const vertex_descriptor uPrime = *assignedVertexIt;
169
170 if (get(assignments, uPrime) == u) {
171 BGL_FORALL_OUTEDGES_T(uPrime, e, g, Graph) { // foreach (u, v) \in E do
172 vis.examine_edge(e, g);
173
174 const vertex_descriptor v = get(assignments, target(e, g));
175
176 if (pq.contains(v)) { // if v \in PQ then
177 put(keys, v, get(keys, v) + get(weights, e)); // increasekey(PQ, v, wA(v) + w(u, v))
178 pq.update(v);
179 }
180 }
181 }
182 }
183 vis.finish_vertex(u, g);
184 }
185 }
186 } // end namespace detail
187
188 template <class Graph, class WeightMap, class MASVisitor, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue>
189 void
190maximum_adjacency_search(const Graph& g, WeightMap weights, MASVisitor vis, const typename boost::graph_traits<Graph>::vertex_descriptor start, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue pq) {
191 BOOST_CONCEPT_ASSERT((boost::IncidenceGraphConcept<Graph>));
192 BOOST_CONCEPT_ASSERT((boost::VertexListGraphConcept<Graph>));
193 typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
194 typedef typename boost::graph_traits<Graph>::vertices_size_type vertices_size_type;
195 typedef typename boost::graph_traits<Graph>::edge_descriptor edge_descriptor;
196 BOOST_CONCEPT_ASSERT((boost::Convertible<typename boost::graph_traits<Graph>::directed_category, boost::undirected_tag>));
197 BOOST_CONCEPT_ASSERT((boost::ReadablePropertyMapConcept<WeightMap, edge_descriptor>));
198 // typedef typename boost::property_traits<WeightMap>::value_type weight_type;
199 boost::function_requires< MASVisitorConcept<MASVisitor, Graph> >();
200 BOOST_CONCEPT_ASSERT((boost::ReadWritePropertyMapConcept<VertexAssignmentMap, vertex_descriptor>));
201 BOOST_CONCEPT_ASSERT((boost::Convertible<vertex_descriptor, typename boost::property_traits<VertexAssignmentMap>::value_type>));
202 BOOST_CONCEPT_ASSERT((boost::KeyedUpdatableQueueConcept<KeyedUpdatablePriorityQueue>));
203
204 vertices_size_type n = num_vertices(g);
205 if (n < 2)
206 throw boost::bad_graph("the input graph must have at least two vertices.");
207 else if (!pq.empty())
208 throw std::invalid_argument("the max-priority queue must be empty initially.");
209
210 detail::maximum_adjacency_search(g, weights,
211 vis, start,
212 assignments, pq);
213 }
214
215 namespace graph {
216 namespace detail {
217 template <typename WeightMap>
218 struct mas_dispatch {
219 typedef void result_type;
220 template <typename Graph, typename ArgPack>
221 static result_type apply(const Graph& g,
222 //const bgl_named_params<P,T,R>& params,
223 const ArgPack& params,
224 WeightMap w) {
225
226 using namespace boost::graph::keywords;
227 typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
228 typedef typename WeightMap::value_type weight_type;
229
230 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> > default_pq_gen_type;
231
232 default_pq_gen_type pq_gen(choose_param(get_param(params, boost::distance_zero_t()), weight_type(0)));
233
234 typename boost::result_of<default_pq_gen_type(const Graph&, const ArgPack&)>::type pq = pq_gen(g, params);
235
236 boost::maximum_adjacency_search
237 (g,
238 w,
239 params [ _visitor | make_mas_visitor(vis: null_visitor())],
240 params [ _root_vertex | *vertices(g).first],
241 params [ _vertex_assignment_map | boost::detail::make_property_map_from_arg_pack_gen<boost::graph::keywords::tag::vertex_assignment_map, vertex_descriptor>(vertex_descriptor())(g, params)],
242 pq
243 );
244 }
245 };
246
247 template <>
248 struct mas_dispatch<boost::param_not_found> {
249 typedef void result_type;
250
251 template <typename Graph, typename ArgPack>
252 static result_type apply(const Graph& g,
253 const ArgPack& params,
254 param_not_found) {
255
256 using namespace boost::graph::keywords;
257 typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
258
259 // get edge_weight_t as the weight type
260 typedef typename boost::property_map<Graph, edge_weight_t> WeightMap;
261 typedef typename WeightMap::value_type weight_type;
262
263 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> > default_pq_gen_type;
264
265 default_pq_gen_type pq_gen(choose_param(get_param(params, boost::distance_zero_t()), weight_type(0)));
266
267 typename boost::result_of<default_pq_gen_type(const Graph&, const ArgPack&)>::type pq = pq_gen(g, params);
268
269 boost::maximum_adjacency_search
270 (g,
271 get(edge_weight, g),
272 params [ _visitor | make_mas_visitor(vis: null_visitor())],
273 params [ _root_vertex | *vertices(g).first],
274 params [ _vertex_assignment_map | boost::detail::make_property_map_from_arg_pack_gen<boost::graph::keywords::tag::vertex_assignment_map, vertex_descriptor>(vertex_descriptor())(g, params)],
275 pq
276 );
277 }
278 };
279 } // end namespace detail
280 } // end namespace graph
281
282 // Named parameter interface
283 //BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(maximum_adjacency_search, 1)
284 template <typename Graph, typename P, typename T, typename R>
285 void
286 maximum_adjacency_search (const Graph& g,
287 const bgl_named_params<P,T,R>& params) {
288
289 typedef bgl_named_params<P, T, R> params_type;
290 BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params)
291
292 // do the dispatch based on WeightMap
293 typedef typename get_param_type<edge_weight_t, bgl_named_params<P,T,R> >::type W;
294 graph::detail::mas_dispatch<W>::apply(g, arg_pack, get_param(params, edge_weight));
295 }
296
297 namespace graph {
298 namespace detail {
299 template <typename Graph>
300 struct maximum_adjacency_search_impl {
301 typedef void result_type;
302
303 template <typename ArgPack>
304 void
305 operator() (const Graph& g, const ArgPack& arg_pack) const {
306 // call the function that does the dispatching
307 typedef typename get_param_type<edge_weight_t, ArgPack >::type W;
308 graph::detail::mas_dispatch<W>::apply(g, arg_pack, get_param(arg_pack, edge_weight));
309 }
310 };
311 } // end namespace detail
312 BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(maximum_adjacency_search,1,5)
313 } // end namespace graph
314
315} // end namespace boost
316
317#include <boost/graph/iteration_macros_undef.hpp>
318
319#endif // BOOST_GRAPH_MAXIMUM_ADJACENCY_SEARCH_H
320

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