boost/graph/maximum_adjacency_search.hpp

0001 //
0002 //=======================================================================
0003 // Copyright 2012 Fernando Vilas
0004 //           2010 Daniel Trebbien
0005 //
0006 // Distributed under the Boost Software License, Version 1.0. (See
0007 // accompanying file LICENSE_1_0.txt or copy at
0008 // http://www.boost.org/LICENSE_1_0.txt)
0009 //=======================================================================
0010 //
0011
0012 // The maximum adjacency search algorithm was originally part of the
0013 // Stoer-Wagner min cut implementation by Daniel Trebbien. It has been
0014 // broken out into its own file to be a public search algorithm, with
0015 // visitor concepts.
0016 #ifndef BOOST_GRAPH_MAXIMUM_ADJACENCY_SEARCH_H
0017 #define BOOST_GRAPH_MAXIMUM_ADJACENCY_SEARCH_H
0018
0019 /**
0020  * This is an implementation of the maximum adjacency search on an
0021  * undirected graph. It allows a visitor object to perform some
0022  * operation on each vertex as that vertex is visited.
0023  *
0024  * The algorithm runs as follows:
0025  *
0026  * Initialize all nodes to be unvisited (reach count = 0)
0027  *   and call vis.initialize_vertex
0028  * For i = number of nodes in graph downto 1
0029  *   Select the unvisited node with the highest reach count
0030  *     The user provides the starting node to break the first tie,
0031  *     but future ties are broken arbitrarily
0032  *   Visit the node by calling vis.start_vertex
0033  *   Increment the reach count for all unvisited neighbors
0034  *     and call vis.examine_edge for each of these edges
0035  *   Mark the node as visited and call vis.finish_vertex
0036  *
0037  */
0038
0039 #include <boost/concept_check.hpp>
0040 #include <boost/concept/assert.hpp>
0041 #include <boost/graph/buffer_concepts.hpp>
0042 #include <boost/graph/exception.hpp>
0043 #include <boost/graph/graph_concepts.hpp>
0044 #include <boost/graph/iteration_macros.hpp>
0045 #include <boost/graph/named_function_params.hpp>
0046 #include <boost/graph/visitors.hpp>
0047 #include <boost/tuple/tuple.hpp>
0048
0049 #include <set>
0050
0051 namespace boost
0052 {
0053 template < class Visitor, class Graph > struct MASVisitorConcept
0054 {
0055     void constraints()
0056     {
0057         boost::function_requires<
0058             boost::CopyConstructibleConcept< Visitor > >();
0059         vis.initialize_vertex(u, g);
0060         vis.start_vertex(u, g);
0061         vis.examine_edge(e, g);
0062         vis.finish_vertex(u, g);
0063     }
0064     Visitor vis;
0065     Graph g;
0066     typename boost::graph_traits< Graph >::vertex_descriptor u;
0067     typename boost::graph_traits< Graph >::edge_descriptor e;
0068 };
0069
0070 template < class Visitors = null_visitor > class mas_visitor
0071 {
0072 public:
0073     mas_visitor() {}
0074     mas_visitor(Visitors vis) : m_vis(vis) {}
0075
0076     template < class Vertex, class Graph >
0077     void initialize_vertex(Vertex u, Graph& g)
0078     {
0079         invoke_visitors(m_vis, u, g, ::boost::on_initialize_vertex());
0080     }
0081
0082     template < class Vertex, class Graph > void start_vertex(Vertex u, Graph& g)
0083     {
0084         invoke_visitors(m_vis, u, g, ::boost::on_start_vertex());
0085     }
0086
0087     template < class Edge, class Graph > void examine_edge(Edge e, Graph& g)
0088     {
0089         invoke_visitors(m_vis, e, g, ::boost::on_examine_edge());
0090     }
0091
0092     template < class Vertex, class Graph >
0093     void finish_vertex(Vertex u, Graph& g)
0094     {
0095         invoke_visitors(m_vis, u, g, ::boost::on_finish_vertex());
0096     }
0097
0098     BOOST_GRAPH_EVENT_STUB(on_initialize_vertex, mas)
0099     BOOST_GRAPH_EVENT_STUB(on_start_vertex, mas)
0100     BOOST_GRAPH_EVENT_STUB(on_examine_edge, mas)
0101     BOOST_GRAPH_EVENT_STUB(on_finish_vertex, mas)
0102
0103 protected:
0104     Visitors m_vis;
0105 };
0106 template < class Visitors >
0107 mas_visitor< Visitors > make_mas_visitor(Visitors vis)
0108 {
0109     return mas_visitor< Visitors >(vis);
0110 }
0111 typedef mas_visitor<> default_mas_visitor;
0112
0113 namespace detail
0114 {
0115     template < class Graph, class WeightMap, class MASVisitor,
0116         class VertexAssignmentMap, class KeyedUpdatablePriorityQueue >
0117     void maximum_adjacency_search(const Graph& g, WeightMap weights,
0118         MASVisitor vis,
0119         const typename boost::graph_traits< Graph >::vertex_descriptor start,
0120         VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue pq)
0121     {
0122         typedef typename boost::graph_traits< Graph >::vertex_descriptor
0123             vertex_descriptor;
0124         typedef typename boost::property_traits< WeightMap >::value_type
0125             weight_type;
0126
0127         std::set< vertex_descriptor > assignedVertices;
0128
0129         // initialize `assignments` (all vertices are initially
0130         // assigned to themselves)
0131         BGL_FORALL_VERTICES_T(v, g, Graph) { put(assignments, v, v); }
0132
0133         typename KeyedUpdatablePriorityQueue::key_map keys = pq.keys();
0134
0135         // set number of visited neighbors for all vertices to 0
0136         BGL_FORALL_VERTICES_T(v, g, Graph)
0137         {
0138             if (v == get(assignments, v))
0139             { // foreach u \in V do
0140                 put(keys, v, weight_type(0));
0141                 vis.initialize_vertex(v, g);
0142
0143                 pq.push(v);
0144             }
0145         }
0146         BOOST_ASSERT(pq.size() >= 2);
0147
0148         // Give the starting vertex high priority
0149         put(keys, start, get(keys, start) + num_vertices(g) + 1);
0150         pq.update(start);
0151
0152         // start traversing the graph
0153         // vertex_descriptor s, t;
0154         // weight_type w;
0155         while (!pq.empty())
0156         { // while PQ \neq {} do
0157             const vertex_descriptor u = pq.top(); // u = extractmax(PQ)
0158             /* weight_type w = */ get(keys, u);
0159             vis.start_vertex(u, g);
0160             pq.pop(); //            vis.start_vertex(u, g);
0161
0162             BGL_FORALL_OUTEDGES_T(u, e, g, Graph)
0163             { // foreach (u, v) \in E do
0164                 vis.examine_edge(e, g);
0165
0166                 const vertex_descriptor v = get(assignments, target(e, g));
0167
0168                 if (pq.contains(v))
0169                 { // if v \in PQ then
0170                     put(keys, v,
0171                         get(keys, v)
0172                             + get(weights,
0173                                 e)); // increasekey(PQ, v, wA(v) + w(u, v))
0174                     pq.update(v);
0175                 }
0176             }
0177
0178             typename std::set< vertex_descriptor >::const_iterator
0179                 assignedVertexIt,
0180                 assignedVertexEnd = assignedVertices.end();
0181             for (assignedVertexIt = assignedVertices.begin();
0182                  assignedVertexIt != assignedVertexEnd; ++assignedVertexIt)
0183             {
0184                 const vertex_descriptor uPrime = *assignedVertexIt;
0185
0186                 if (get(assignments, uPrime) == u)
0187                 {
0188                     BGL_FORALL_OUTEDGES_T(uPrime, e, g, Graph)
0189                     { // foreach (u, v) \in E do
0190                         vis.examine_edge(e, g);
0191
0192                         const vertex_descriptor v
0193                             = get(assignments, target(e, g));
0194
0195                         if (pq.contains(v))
0196                         { // if v \in PQ then
0197                             put(keys, v,
0198                                 get(keys, v)
0199                                     + get(weights, e)); // increasekey(PQ, v,
0200                                                         // wA(v) + w(u, v))
0201                             pq.update(v);
0202                         }
0203                     }
0204                 }
0205             }
0206             vis.finish_vertex(u, g);
0207         }
0208     }
0209 } // end namespace detail
0210
0211 template < class Graph, class WeightMap, class MASVisitor,
0212     class VertexAssignmentMap, class KeyedUpdatablePriorityQueue >
0213 void maximum_adjacency_search(const Graph& g, WeightMap weights, MASVisitor vis,
0214     const typename boost::graph_traits< Graph >::vertex_descriptor start,
0215     VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue pq)
0216 {
0217     BOOST_CONCEPT_ASSERT((boost::IncidenceGraphConcept< Graph >));
0218     BOOST_CONCEPT_ASSERT((boost::VertexListGraphConcept< Graph >));
0219     typedef typename boost::graph_traits< Graph >::vertex_descriptor
0220         vertex_descriptor;
0221     typedef typename boost::graph_traits< Graph >::vertices_size_type
0222         vertices_size_type;
0223     typedef
0224         typename boost::graph_traits< Graph >::edge_descriptor edge_descriptor;
0225     BOOST_CONCEPT_ASSERT((boost::Convertible<
0226         typename boost::graph_traits< Graph >::directed_category,
0227         boost::undirected_tag >));
0228     BOOST_CONCEPT_ASSERT(
0229         (boost::ReadablePropertyMapConcept< WeightMap, edge_descriptor >));
0230     // typedef typename boost::property_traits<WeightMap>::value_type
0231     // weight_type;
0232     boost::function_requires< MASVisitorConcept< MASVisitor, Graph > >();
0233     BOOST_CONCEPT_ASSERT(
0234         (boost::ReadWritePropertyMapConcept< VertexAssignmentMap,
0235             vertex_descriptor >));
0236     BOOST_CONCEPT_ASSERT((boost::Convertible< vertex_descriptor,
0237         typename boost::property_traits< VertexAssignmentMap >::value_type >));
0238     BOOST_CONCEPT_ASSERT(
0239         (boost::KeyedUpdatableQueueConcept< KeyedUpdatablePriorityQueue >));
0240
0241     vertices_size_type n = num_vertices(g);
0242     if (n < 2)
0243         throw boost::bad_graph(
0244             "the input graph must have at least two vertices.");
0245     else if (!pq.empty())
0246         throw std::invalid_argument(
0247             "the max-priority queue must be empty initially.");
0248
0249     detail::maximum_adjacency_search(g, weights, vis, start, assignments, pq);
0250 }
0251
0252 namespace graph
0253 {
0254     namespace detail
0255     {
0256         template < typename WeightMap > struct mas_dispatch
0257         {
0258             typedef void result_type;
0259             template < typename Graph, typename ArgPack >
0260             static result_type apply(const Graph& g,
0261                 // const bgl_named_params<P,T,R>& params,
0262                 const ArgPack& params, WeightMap w)
0263             {
0264
0265                 using namespace boost::graph::keywords;
0266                 typedef typename boost::graph_traits< Graph >::vertex_descriptor
0267                     vertex_descriptor;
0268                 typedef typename WeightMap::value_type weight_type;
0269
0270                 typedef boost::detail::make_priority_queue_from_arg_pack_gen<
0271                     boost::graph::keywords::tag::max_priority_queue,
0272                     weight_type, vertex_descriptor,
0273                     std::greater< weight_type > >
0274                     default_pq_gen_type;
0275
0276                 default_pq_gen_type pq_gen(
0277                     choose_param(get_param(params, boost::distance_zero_t()),
0278                         weight_type(0)));
0279
0280                 typename boost::result_of< default_pq_gen_type(
0281                     const Graph&, const ArgPack&) >::type pq
0282                     = pq_gen(g, params);
0283
0284                 boost::null_visitor null_vis;
0285                 boost::mas_visitor< boost::null_visitor > default_visitor(
0286                     null_vis);
0287                 vertex_descriptor v = vertex_descriptor();
0288                 boost::detail::make_property_map_from_arg_pack_gen<
0289                     boost::graph::keywords::tag::vertex_assignment_map,
0290                     vertex_descriptor >
0291                     map_gen(v);
0292                 typename boost::detail::map_maker< Graph, ArgPack,
0293                     boost::graph::keywords::tag::vertex_assignment_map,
0294                     vertex_descriptor >::map_type default_map
0295                     = map_gen(g, params);
0296                 boost::maximum_adjacency_search(g, w,
0297                     params[_visitor | default_visitor],
0298                     params[_root_vertex | *vertices(g).first],
0299                     params[_vertex_assignment_map | default_map], pq);
0300             }
0301         };
0302
0303         template <> struct mas_dispatch< boost::param_not_found >
0304         {
0305             typedef void result_type;
0306
0307             template < typename Graph, typename ArgPack >
0308             static result_type apply(
0309                 const Graph& g, const ArgPack& params, param_not_found)
0310             {
0311
0312                 using namespace boost::graph::keywords;
0313                 typedef typename boost::graph_traits< Graph >::vertex_descriptor
0314                     vertex_descriptor;
0315
0316                 // get edge_weight_t as the weight type
0317                 typedef typename boost::property_map< Graph, edge_weight_t >
0318                     WeightMap;
0319                 typedef typename WeightMap::value_type weight_type;
0320
0321                 typedef boost::detail::make_priority_queue_from_arg_pack_gen<
0322                     boost::graph::keywords::tag::max_priority_queue,
0323                     weight_type, vertex_descriptor,
0324                     std::greater< weight_type > >
0325                     default_pq_gen_type;
0326
0327                 default_pq_gen_type pq_gen(
0328                     choose_param(get_param(params, boost::distance_zero_t()),
0329                         weight_type(0)));
0330
0331                 typename boost::result_of< default_pq_gen_type(
0332                     const Graph&, const ArgPack&) >::type pq
0333                     = pq_gen(g, params);
0334
0335                 boost::null_visitor null_vis;
0336                 boost::mas_visitor< boost::null_visitor > default_visitor(
0337                     null_vis);
0338                 vertex_descriptor v = vertex_descriptor();
0339                 boost::detail::make_property_map_from_arg_pack_gen<
0340                     boost::graph::keywords::tag::vertex_assignment_map,
0341                     vertex_descriptor >
0342                     map_gen(v);
0343                 typename boost::detail::map_maker< Graph, ArgPack,
0344                     boost::graph::keywords::tag::vertex_assignment_map,
0345                     vertex_descriptor >::map_type default_map
0346                     = map_gen(g, params);
0347                 boost::maximum_adjacency_search(g, get(edge_weight, g),
0348                     params[_visitor | default_visitor],
0349                     params[_root_vertex | *vertices(g).first],
0350                     params[_vertex_assignment_map | default_map], pq);
0351             }
0352         };
0353     } // end namespace detail
0354 } // end namespace graph
0355
0356 // Named parameter interface
0357 // BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(maximum_adjacency_search, 1)
0358 template < typename Graph, typename P, typename T, typename R >
0359 void maximum_adjacency_search(
0360     const Graph& g, const bgl_named_params< P, T, R >& params)
0361 {
0362
0363     typedef bgl_named_params< P, T, R > params_type;
0364     BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params)
0365
0366     // do the dispatch based on WeightMap
0367     typedef typename get_param_type< edge_weight_t,
0368         bgl_named_params< P, T, R > >::type W;
0369     graph::detail::mas_dispatch< W >::apply(
0370         g, arg_pack, get_param(params, edge_weight));
0371 }
0372
0373 namespace graph
0374 {
0375     namespace detail
0376     {
0377         template < typename Graph > struct maximum_adjacency_search_impl
0378         {
0379             typedef void result_type;
0380
0381             template < typename ArgPack >
0382             void operator()(const Graph& g, const ArgPack& arg_pack) const
0383             {
0384                 // call the function that does the dispatching
0385                 typedef
0386                     typename get_param_type< edge_weight_t, ArgPack >::type W;
0387                 graph::detail::mas_dispatch< W >::apply(
0388                     g, arg_pack, get_param(arg_pack, edge_weight));
0389             }
0390         };
0391     } // end namespace detail
0392     BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(maximum_adjacency_search, 1, 5)
0393 } // end namespace graph
0394
0395 } // end namespace boost
0396
0397 #include <boost/graph/iteration_macros_undef.hpp>
0398
0399 #endif // BOOST_GRAPH_MAXIMUM_ADJACENCY_SEARCH_H