boost/graph/breadth_first_search.hpp

0001 //
0002 //=======================================================================
0003 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
0004 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
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 #ifndef BOOST_GRAPH_BREADTH_FIRST_SEARCH_HPP
0012 #define BOOST_GRAPH_BREADTH_FIRST_SEARCH_HPP
0013
0014 /*
0015   Breadth First Search Algorithm (Cormen, Leiserson, and Rivest p. 470)
0016 */
0017 #include <boost/config.hpp>
0018 #include <vector>
0019 #include <boost/pending/queue.hpp>
0020 #include <boost/graph/graph_traits.hpp>
0021 #include <boost/graph/graph_concepts.hpp>
0022 #include <boost/graph/visitors.hpp>
0023 #include <boost/graph/named_function_params.hpp>
0024 #include <boost/graph/overloading.hpp>
0025 #include <boost/graph/graph_concepts.hpp>
0026 #include <boost/graph/two_bit_color_map.hpp>
0027 #include <boost/graph/detail/mpi_include.hpp>
0028 #include <boost/concept/assert.hpp>
0029
0030 #include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/concepts.hpp>)
0031
0032 namespace boost
0033 {
0034
0035 template < class Visitor, class Graph > struct BFSVisitorConcept
0036 {
0037     void constraints()
0038     {
0039         BOOST_CONCEPT_ASSERT((CopyConstructibleConcept< Visitor >));
0040         vis.initialize_vertex(u, g);
0041         vis.discover_vertex(u, g);
0042         vis.examine_vertex(u, g);
0043         vis.examine_edge(e, g);
0044         vis.tree_edge(e, g);
0045         vis.non_tree_edge(e, g);
0046         vis.gray_target(e, g);
0047         vis.black_target(e, g);
0048         vis.finish_vertex(u, g);
0049     }
0050     Visitor vis;
0051     Graph g;
0052     typename graph_traits< Graph >::vertex_descriptor u;
0053     typename graph_traits< Graph >::edge_descriptor e;
0054 };
0055
0056 // Multiple-source version
0057 template < class IncidenceGraph, class Buffer, class BFSVisitor, class ColorMap,
0058     class SourceIterator >
0059 void breadth_first_visit(const IncidenceGraph& g, SourceIterator sources_begin,
0060     SourceIterator sources_end, Buffer& Q, BFSVisitor vis, ColorMap color)
0061 {
0062     BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< IncidenceGraph >));
0063     typedef graph_traits< IncidenceGraph > GTraits;
0064     typedef typename GTraits::vertex_descriptor Vertex;
0065     BOOST_CONCEPT_ASSERT((BFSVisitorConcept< BFSVisitor, IncidenceGraph >));
0066     BOOST_CONCEPT_ASSERT((ReadWritePropertyMapConcept< ColorMap, Vertex >));
0067     typedef typename property_traits< ColorMap >::value_type ColorValue;
0068     typedef color_traits< ColorValue > Color;
0069     typename GTraits::out_edge_iterator ei, ei_end;
0070
0071     for (; sources_begin != sources_end; ++sources_begin)
0072     {
0073         Vertex s = *sources_begin;
0074         put(color, s, Color::gray());
0075         vis.discover_vertex(s, g);
0076         Q.push(s);
0077     }
0078     while (!Q.empty())
0079     {
0080         Vertex u = Q.top();
0081         Q.pop();
0082         vis.examine_vertex(u, g);
0083         for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei)
0084         {
0085             Vertex v = target(*ei, g);
0086             vis.examine_edge(*ei, g);
0087             ColorValue v_color = get(color, v);
0088             if (v_color == Color::white())
0089             {
0090                 vis.tree_edge(*ei, g);
0091                 put(color, v, Color::gray());
0092                 vis.discover_vertex(v, g);
0093                 Q.push(v);
0094             }
0095             else
0096             {
0097                 vis.non_tree_edge(*ei, g);
0098                 if (v_color == Color::gray())
0099                     vis.gray_target(*ei, g);
0100                 else
0101                     vis.black_target(*ei, g);
0102             }
0103         } // end for
0104         put(color, u, Color::black());
0105         vis.finish_vertex(u, g);
0106     } // end while
0107 } // breadth_first_visit
0108
0109 // Single-source version
0110 template < class IncidenceGraph, class Buffer, class BFSVisitor,
0111     class ColorMap >
0112 void breadth_first_visit(const IncidenceGraph& g,
0113     typename graph_traits< IncidenceGraph >::vertex_descriptor s, Buffer& Q,
0114     BFSVisitor vis, ColorMap color)
0115 {
0116     typename graph_traits< IncidenceGraph >::vertex_descriptor sources[1]
0117         = { s };
0118     breadth_first_visit(g, sources, sources + 1, Q, vis, color);
0119 }
0120
0121 template < class VertexListGraph, class SourceIterator, class Buffer,
0122     class BFSVisitor, class ColorMap >
0123 void breadth_first_search(const VertexListGraph& g,
0124     SourceIterator sources_begin, SourceIterator sources_end, Buffer& Q,
0125     BFSVisitor vis, ColorMap color)
0126 {
0127     // Initialization
0128     typedef typename property_traits< ColorMap >::value_type ColorValue;
0129     typedef color_traits< ColorValue > Color;
0130     typename boost::graph_traits< VertexListGraph >::vertex_iterator i, i_end;
0131     for (boost::tie(i, i_end) = vertices(g); i != i_end; ++i)
0132     {
0133         vis.initialize_vertex(*i, g);
0134         put(color, *i, Color::white());
0135     }
0136     breadth_first_visit(g, sources_begin, sources_end, Q, vis, color);
0137 }
0138
0139 template < class VertexListGraph, class Buffer, class BFSVisitor,
0140     class ColorMap >
0141 void breadth_first_search(const VertexListGraph& g,
0142     typename graph_traits< VertexListGraph >::vertex_descriptor s, Buffer& Q,
0143     BFSVisitor vis, ColorMap color)
0144 {
0145     typename graph_traits< VertexListGraph >::vertex_descriptor sources[1]
0146         = { s };
0147     breadth_first_search(g, sources, sources + 1, Q, vis, color);
0148 }
0149
0150 namespace graph
0151 {
0152     struct bfs_visitor_event_not_overridden
0153     {
0154     };
0155 }
0156
0157 template < class Visitors = null_visitor > class bfs_visitor
0158 {
0159 public:
0160     bfs_visitor() {}
0161     bfs_visitor(Visitors vis) : m_vis(vis) {}
0162
0163     template < class Vertex, class Graph >
0164     graph::bfs_visitor_event_not_overridden initialize_vertex(
0165         Vertex u, Graph& g)
0166     {
0167         invoke_visitors(m_vis, u, g, ::boost::on_initialize_vertex());
0168         return graph::bfs_visitor_event_not_overridden();
0169     }
0170
0171     template < class Vertex, class Graph >
0172     graph::bfs_visitor_event_not_overridden discover_vertex(Vertex u, Graph& g)
0173     {
0174         invoke_visitors(m_vis, u, g, ::boost::on_discover_vertex());
0175         return graph::bfs_visitor_event_not_overridden();
0176     }
0177
0178     template < class Vertex, class Graph >
0179     graph::bfs_visitor_event_not_overridden examine_vertex(Vertex u, Graph& g)
0180     {
0181         invoke_visitors(m_vis, u, g, ::boost::on_examine_vertex());
0182         return graph::bfs_visitor_event_not_overridden();
0183     }
0184
0185     template < class Edge, class Graph >
0186     graph::bfs_visitor_event_not_overridden examine_edge(Edge e, Graph& g)
0187     {
0188         invoke_visitors(m_vis, e, g, ::boost::on_examine_edge());
0189         return graph::bfs_visitor_event_not_overridden();
0190     }
0191
0192     template < class Edge, class Graph >
0193     graph::bfs_visitor_event_not_overridden tree_edge(Edge e, Graph& g)
0194     {
0195         invoke_visitors(m_vis, e, g, ::boost::on_tree_edge());
0196         return graph::bfs_visitor_event_not_overridden();
0197     }
0198
0199     template < class Edge, class Graph >
0200     graph::bfs_visitor_event_not_overridden non_tree_edge(Edge e, Graph& g)
0201     {
0202         invoke_visitors(m_vis, e, g, ::boost::on_non_tree_edge());
0203         return graph::bfs_visitor_event_not_overridden();
0204     }
0205
0206     template < class Edge, class Graph >
0207     graph::bfs_visitor_event_not_overridden gray_target(Edge e, Graph& g)
0208     {
0209         invoke_visitors(m_vis, e, g, ::boost::on_gray_target());
0210         return graph::bfs_visitor_event_not_overridden();
0211     }
0212
0213     template < class Edge, class Graph >
0214     graph::bfs_visitor_event_not_overridden black_target(Edge e, Graph& g)
0215     {
0216         invoke_visitors(m_vis, e, g, ::boost::on_black_target());
0217         return graph::bfs_visitor_event_not_overridden();
0218     }
0219
0220     template < class Vertex, class Graph >
0221     graph::bfs_visitor_event_not_overridden finish_vertex(Vertex u, Graph& g)
0222     {
0223         invoke_visitors(m_vis, u, g, ::boost::on_finish_vertex());
0224         return graph::bfs_visitor_event_not_overridden();
0225     }
0226
0227     BOOST_GRAPH_EVENT_STUB(on_initialize_vertex, bfs)
0228     BOOST_GRAPH_EVENT_STUB(on_discover_vertex, bfs)
0229     BOOST_GRAPH_EVENT_STUB(on_examine_vertex, bfs)
0230     BOOST_GRAPH_EVENT_STUB(on_examine_edge, bfs)
0231     BOOST_GRAPH_EVENT_STUB(on_tree_edge, bfs)
0232     BOOST_GRAPH_EVENT_STUB(on_non_tree_edge, bfs)
0233     BOOST_GRAPH_EVENT_STUB(on_gray_target, bfs)
0234     BOOST_GRAPH_EVENT_STUB(on_black_target, bfs)
0235     BOOST_GRAPH_EVENT_STUB(on_finish_vertex, bfs)
0236
0237 protected:
0238     Visitors m_vis;
0239 };
0240 template < class Visitors >
0241 bfs_visitor< Visitors > make_bfs_visitor(Visitors vis)
0242 {
0243     return bfs_visitor< Visitors >(vis);
0244 }
0245 typedef bfs_visitor<> default_bfs_visitor;
0246
0247 namespace detail
0248 {
0249
0250     template < class VertexListGraph, class ColorMap, class BFSVisitor, class P,
0251         class T, class R >
0252     void bfs_helper(VertexListGraph& g,
0253         typename graph_traits< VertexListGraph >::vertex_descriptor s,
0254         ColorMap color, BFSVisitor vis,
0255         const bgl_named_params< P, T, R >& params, boost::mpl::false_)
0256     {
0257         typedef graph_traits< VertexListGraph > Traits;
0258         // Buffer default
0259         typedef typename Traits::vertex_descriptor Vertex;
0260         typedef boost::queue< Vertex > queue_t;
0261         queue_t Q;
0262         breadth_first_search(g, s,
0263             choose_param(get_param(params, buffer_param_t()), boost::ref(Q))
0264                 .get(),
0265             vis, color);
0266     }
0267
0268 #ifdef BOOST_GRAPH_USE_MPI
0269     template < class DistributedGraph, class ColorMap, class BFSVisitor,
0270         class P, class T, class R >
0271     void bfs_helper(DistributedGraph& g,
0272         typename graph_traits< DistributedGraph >::vertex_descriptor s,
0273         ColorMap color, BFSVisitor vis,
0274         const bgl_named_params< P, T, R >& params, boost::mpl::true_);
0275 #endif // BOOST_GRAPH_USE_MPI
0276
0277     //-------------------------------------------------------------------------
0278     // Choose between default color and color parameters. Using
0279     // function dispatching so that we don't require vertex index if
0280     // the color default is not being used.
0281
0282     template < class ColorMap > struct bfs_dispatch
0283     {
0284         template < class VertexListGraph, class P, class T, class R >
0285         static void apply(VertexListGraph& g,
0286             typename graph_traits< VertexListGraph >::vertex_descriptor s,
0287             const bgl_named_params< P, T, R >& params, ColorMap color)
0288         {
0289             bfs_helper(g, s, color,
0290                 choose_param(get_param(params, graph_visitor),
0291                     make_bfs_visitor(null_visitor())),
0292                 params,
0293                 boost::mpl::bool_<
0294                     boost::is_base_and_derived< distributed_graph_tag,
0295                         typename graph_traits<
0296                             VertexListGraph >::traversal_category >::value >());
0297         }
0298     };
0299
0300     template <> struct bfs_dispatch< param_not_found >
0301     {
0302         template < class VertexListGraph, class P, class T, class R >
0303         static void apply(VertexListGraph& g,
0304             typename graph_traits< VertexListGraph >::vertex_descriptor s,
0305             const bgl_named_params< P, T, R >& params, param_not_found)
0306         {
0307             null_visitor null_vis;
0308
0309             bfs_helper(g, s,
0310                 make_two_bit_color_map(num_vertices(g),
0311                     choose_const_pmap(
0312                         get_param(params, vertex_index), g, vertex_index)),
0313                 choose_param(get_param(params, graph_visitor),
0314                     make_bfs_visitor(null_vis)),
0315                 params,
0316                 boost::mpl::bool_<
0317                     boost::is_base_and_derived< distributed_graph_tag,
0318                         typename graph_traits<
0319                             VertexListGraph >::traversal_category >::value >());
0320         }
0321     };
0322
0323 } // namespace detail
0324
0325 #if 1
0326 // Named Parameter Variant
0327 template < class VertexListGraph, class P, class T, class R >
0328 void breadth_first_search(const VertexListGraph& g,
0329     typename graph_traits< VertexListGraph >::vertex_descriptor s,
0330     const bgl_named_params< P, T, R >& params)
0331 {
0332     // The graph is passed by *const* reference so that graph adaptors
0333     // (temporaries) can be passed into this function. However, the
0334     // graph is not really const since we may write to property maps
0335     // of the graph.
0336     VertexListGraph& ng = const_cast< VertexListGraph& >(g);
0337     typedef typename get_param_type< vertex_color_t,
0338         bgl_named_params< P, T, R > >::type C;
0339     detail::bfs_dispatch< C >::apply(
0340         ng, s, params, get_param(params, vertex_color));
0341 }
0342 #endif
0343
0344 // This version does not initialize colors, user has to.
0345
0346 template < class IncidenceGraph, class P, class T, class R >
0347 void breadth_first_visit(const IncidenceGraph& g,
0348     typename graph_traits< IncidenceGraph >::vertex_descriptor s,
0349     const bgl_named_params< P, T, R >& params)
0350 {
0351     // The graph is passed by *const* reference so that graph adaptors
0352     // (temporaries) can be passed into this function. However, the
0353     // graph is not really const since we may write to property maps
0354     // of the graph.
0355     IncidenceGraph& ng = const_cast< IncidenceGraph& >(g);
0356
0357     typedef graph_traits< IncidenceGraph > Traits;
0358     // Buffer default
0359     typedef typename Traits::vertex_descriptor vertex_descriptor;
0360     typedef boost::queue< vertex_descriptor > queue_t;
0361     queue_t Q;
0362
0363     breadth_first_visit(ng, s,
0364         choose_param(get_param(params, buffer_param_t()), boost::ref(Q)).get(),
0365         choose_param(
0366             get_param(params, graph_visitor), make_bfs_visitor(null_visitor())),
0367         choose_pmap(get_param(params, vertex_color), ng, vertex_color));
0368 }
0369
0370 namespace graph
0371 {
0372     namespace detail
0373     {
0374         template < typename Graph, typename Source >
0375         struct breadth_first_search_impl
0376         {
0377             typedef void result_type;
0378             template < typename ArgPack >
0379             void operator()(
0380                 const Graph& g, const Source& source, const ArgPack& arg_pack)
0381             {
0382                 using namespace boost::graph::keywords;
0383                 typename boost::graph_traits< Graph >::vertex_descriptor
0384                     sources[1]
0385                     = { source };
0386                 boost::queue<
0387                     typename boost::graph_traits< Graph >::vertex_descriptor >
0388                     Q;
0389                 boost::breadth_first_search(g, &sources[0], &sources[1],
0390                     boost::unwrap_ref(arg_pack[_buffer | boost::ref(Q)]),
0391                     arg_pack[_visitor | make_bfs_visitor(null_visitor())],
0392                     boost::detail::make_color_map_from_arg_pack(g, arg_pack));
0393             }
0394         };
0395     }
0396     BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(breadth_first_search, 2, 4)
0397 }
0398
0399 #if 0
0400   // Named Parameter Variant
0401   BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(breadth_first_search, 2)
0402 #endif
0403
0404 } // namespace boost
0405
0406 #include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/breadth_first_search.hpp>)
0407
0408 #endif // BOOST_GRAPH_BREADTH_FIRST_SEARCH_HPP