graph/distributed/breadth_first_search.hpp

0001 // Copyright 2004 The Trustees of Indiana University.
0002
0003 // Use, modification and distribution is subject to the Boost Software
0004 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006
0007 //  Authors: Douglas Gregor
0008 //           Andrew Lumsdaine
0009 #ifndef BOOST_GRAPH_PARALLEL_BFS_HPP
0010 #define BOOST_GRAPH_PARALLEL_BFS_HPP
0011
0012 #ifndef BOOST_GRAPH_USE_MPI
0013 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
0014 #endif
0015
0016 #include <boost/graph/breadth_first_search.hpp>
0017 #include <boost/graph/overloading.hpp>
0018 #include <boost/graph/distributed/concepts.hpp>
0019 #include <boost/graph/distributed/detail/filtered_queue.hpp>
0020 #include <boost/graph/distributed/queue.hpp>
0021 #include <boost/dynamic_bitset.hpp>
0022 #include <boost/pending/queue.hpp>
0023 #include <boost/graph/parallel/properties.hpp>
0024 #include <boost/graph/parallel/container_traits.hpp>
0025
0026 namespace boost {
0027   namespace detail {
0028     /** @brief A unary predicate that decides when to push into a
0029      *         breadth-first search queue.
0030      *
0031      *  This predicate stores a color map that is used to determine
0032      *  when to push. If it is provided with a key for which the color
0033      *  is white, it darkens the color to gray and returns true (so
0034      *  that the value will be pushed appropriately); if the color is
0035      *  not white, it returns false so that the vertex will be
0036      *  ignored.
0037      */
0038     template<typename ColorMap>
0039     struct darken_and_push
0040     {
0041       typedef typename property_traits<ColorMap>::key_type argument_type;
0042       typedef bool result_type;
0043
0044       explicit darken_and_push(const ColorMap& color) : color(color) { }
0045
0046       bool operator()(const argument_type& value) const
0047       {
0048         typedef color_traits<typename property_traits<ColorMap>::value_type>
0049           Color;
0050         if (get(color, value) == Color::white()) {
0051           put(color, value, Color::gray());
0052           return true;
0053         } else {
0054           return false;
0055         }
0056       }
0057
0058       ColorMap color;
0059     };
0060
0061     template<typename IndexMap>
0062     struct has_not_been_seen
0063     {
0064       typedef bool result_type;
0065
0066       has_not_been_seen() { }
0067
0068       has_not_been_seen(std::size_t n, IndexMap index_map)
0069         : seen(n), index_map(index_map) {}
0070
0071       template<typename Key>
0072       result_type operator()(Key key)
0073       {
0074         bool result = seen[get(index_map, key)];
0075         seen[get(index_map, key)] = true;
0076         return !result;
0077       }
0078
0079       void swap(has_not_been_seen& other)
0080       {
0081         using std::swap;
0082         swap(seen, other.seen);
0083         swap(index_map, other.index_map);
0084       }
0085
0086     private:
0087       dynamic_bitset<> seen;
0088       IndexMap index_map;
0089     };
0090
0091     template<typename IndexMap>
0092     inline void
0093     swap(has_not_been_seen<IndexMap>& x, has_not_been_seen<IndexMap>& y)
0094     {
0095       x.swap(y);
0096     }
0097
0098     template <class DistributedGraph, class ColorMap, class BFSVisitor,
0099               class BufferRef, class VertexIndexMap>
0100     inline void
0101     parallel_bfs_helper
0102       (DistributedGraph& g,
0103        typename graph_traits<DistributedGraph>::vertex_descriptor s,
0104        ColorMap color,
0105        BFSVisitor vis,
0106        BufferRef Q,
0107        VertexIndexMap)
0108     {
0109       set_property_map_role(vertex_color, color);
0110       color.set_consistency_model(0);
0111       breadth_first_search(g, s, Q.ref, vis, color);
0112     }
0113
0114     template <class DistributedGraph, class ColorMap, class BFSVisitor,
0115               class VertexIndexMap>
0116     void parallel_bfs_helper
0117       (DistributedGraph& g,
0118        typename graph_traits<DistributedGraph>::vertex_descriptor s,
0119        ColorMap color,
0120        BFSVisitor vis,
0121        boost::param_not_found,
0122        VertexIndexMap vertex_index)
0123     {
0124       using boost::graph::parallel::process_group;
0125
0126       typedef graph_traits<DistributedGraph> Traits;
0127       typedef typename Traits::vertex_descriptor Vertex;
0128       typedef typename boost::graph::parallel::process_group_type<DistributedGraph>::type
0129         process_group_type;
0130
0131       set_property_map_role(vertex_color, color);
0132       color.set_consistency_model(0);
0133
0134       // Buffer default
0135       typedef typename property_map<DistributedGraph, vertex_owner_t>
0136         ::const_type vertex_owner_map;
0137       typedef boost::graph::distributed::distributed_queue<
0138                 process_group_type, vertex_owner_map, queue<Vertex>,
0139                 detail::darken_and_push<ColorMap> > queue_t;
0140       queue_t Q(process_group(g),
0141                 get(vertex_owner, g),
0142                 detail::darken_and_push<ColorMap>(color));
0143       breadth_first_search(g, s, Q, vis, color);
0144     }
0145
0146     template <class DistributedGraph, class ColorMap, class BFSVisitor,
0147               class P, class T, class R>
0148     void bfs_helper
0149       (DistributedGraph& g,
0150        typename graph_traits<DistributedGraph>::vertex_descriptor s,
0151        ColorMap color,
0152        BFSVisitor vis,
0153        const bgl_named_params<P, T, R>& params,
0154        boost::mpl::true_)
0155         {
0156             parallel_bfs_helper
0157         (g, s, color, vis, get_param(params, buffer_param_t()),
0158          choose_const_pmap(get_param(params, vertex_index),  g, vertex_index));
0159         }
0160   }
0161 }
0162
0163 #endif // BOOST_GRAPH_PARALLEL_BFS_HPP