2 //=======================================================================
3 // Copyright 2012 Fernando Vilas
4 // 2010 Daniel Trebbien
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 //=======================================================================
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
16 #ifndef BOOST_GRAPH_MAXIMUM_ADJACENCY_SEARCH_H
17 #define BOOST_GRAPH_MAXIMUM_ADJACENCY_SEARCH_H
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.
24 * The algorithm runs as follows:
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
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>
52 template <class Visitor, class Graph>
53 struct MASVisitorConcept {
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);
63 typename boost::graph_traits<Graph>::vertex_descriptor u;
64 typename boost::graph_traits<Graph>::edge_descriptor e;
67 template <class Visitors = null_visitor>
71 mas_visitor(Visitors vis) : m_vis(vis) { }
73 template <class Vertex, class Graph>
75 initialize_vertex(Vertex u, Graph& g)
77 invoke_visitors(m_vis, u, g, ::boost::on_initialize_vertex());
80 template <class Vertex, class Graph>
82 start_vertex(Vertex u, Graph& g)
84 invoke_visitors(m_vis, u, g, ::boost::on_start_vertex());
87 template <class Edge, class Graph>
89 examine_edge(Edge e, Graph& g)
91 invoke_visitors(m_vis, e, g, ::boost::on_examine_edge());
94 template <class Vertex, class Graph>
96 finish_vertex(Vertex u, Graph& g)
98 invoke_visitors(m_vis, u, g, ::boost::on_finish_vertex());
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)
109 template <class Visitors>
110 mas_visitor<Visitors>
111 make_mas_visitor(Visitors vis) {
112 return mas_visitor<Visitors>(vis);
114 typedef mas_visitor<> default_mas_visitor;
117 template <class Graph, class WeightMap, class MASVisitor, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue>
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;
123 std::set<vertex_descriptor> assignedVertices;
125 // initialize `assignments` (all vertices are initially
126 // assigned to themselves)
127 BGL_FORALL_VERTICES_T(v, g, Graph) {
128 put(assignments, v, v);
131 typename KeyedUpdatablePriorityQueue::key_map keys = pq.keys();
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);
141 BOOST_ASSERT(pq.size() >= 2);
143 // Give the starting vertex high priority
144 put(keys, start, get(keys, start) + num_vertices(g) + 1);
147 // start traversing the graph
148 //vertex_descriptor s, t;
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);
155 BGL_FORALL_OUTEDGES_T(u, e, g, Graph) { // foreach (u, v) \in E do
156 vis.examine_edge(e, g);
158 const vertex_descriptor v = get(assignments, target(e, g));
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))
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;
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);
174 const vertex_descriptor v = get(assignments, target(e, g));
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))
183 vis.finish_vertex(u, g);
186 } // end namespace detail
188 template <class Graph, class WeightMap, class MASVisitor, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue>
190 maximum_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>));
204 vertices_size_type n = num_vertices(g);
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.");
210 detail::maximum_adjacency_search(g, weights,
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,
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;
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;
232 default_pq_gen_type pq_gen(choose_param(get_param(params, boost::distance_zero_t()), weight_type(0)));
234 typename boost::result_of<default_pq_gen_type(const Graph&, const ArgPack&)>::type pq = pq_gen(g, params);
236 boost::maximum_adjacency_search
239 params [ _visitor | make_mas_visitor(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)],
248 struct mas_dispatch<boost::param_not_found> {
249 typedef void result_type;
251 template <typename Graph, typename ArgPack>
252 static result_type apply(const Graph& g,
253 const ArgPack& params,
256 using namespace boost::graph::keywords;
257 typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
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;
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;
265 default_pq_gen_type pq_gen(choose_param(get_param(params, boost::distance_zero_t()), weight_type(0)));
267 typename boost::result_of<default_pq_gen_type(const Graph&, const ArgPack&)>::type pq = pq_gen(g, params);
269 boost::maximum_adjacency_search
272 params [ _visitor | make_mas_visitor(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)],
279 } // end namespace detail
280 } // end namespace graph
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>
286 maximum_adjacency_search (const Graph& g,
287 const bgl_named_params<P,T,R>& params) {
289 typedef bgl_named_params<P, T, R> params_type;
290 BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params)
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));
299 template <typename Graph>
300 struct maximum_adjacency_search_impl {
301 typedef void result_type;
303 template <typename ArgPack>
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));
311 } // end namespace detail
312 BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(maximum_adjacency_search,1,5)
313 } // end namespace graph
315 } // end namespace boost
317 #include <boost/graph/iteration_macros_undef.hpp>
319 #endif // BOOST_GRAPH_MAXIMUM_ADJACENCY_SEARCH_H