1 // Copyright 2004 The Trustees of Indiana University. 2 3 // Use, modification and distribution is subject to the Boost Software 4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 5 // http://www.boost.org/LICENSE_1_0.txt) 6 7 // Authors: Douglas Gregor 8 // Andrew Lumsdaine 9 #ifndef BOOST_GRAPH_PARALLEL_BFS_HPP 10 #define BOOST_GRAPH_PARALLEL_BFS_HPP 11 12 #ifndef BOOST_GRAPH_USE_MPI 13 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included" 14 #endif 15 16 #include <boost/graph/breadth_first_search.hpp> 17 #include <boost/graph/overloading.hpp> 18 #include <boost/graph/distributed/concepts.hpp> 19 #include <boost/graph/distributed/detail/filtered_queue.hpp> 20 #include <boost/graph/distributed/queue.hpp> 21 #include <boost/dynamic_bitset.hpp> 22 #include <boost/pending/queue.hpp> 23 #include <boost/graph/parallel/properties.hpp> 24 #include <boost/graph/parallel/container_traits.hpp> 25 26 namespace boost { 27 namespace detail { 28 /** @brief A unary predicate that decides when to push into a 29 * breadth-first search queue. 30 * 31 * This predicate stores a color map that is used to determine 32 * when to push. If it is provided with a key for which the color 33 * is white, it darkens the color to gray and returns true (so 34 * that the value will be pushed appropriately); if the color is 35 * not white, it returns false so that the vertex will be 36 * ignored. 37 */ 38 template<typename ColorMap> 39 struct darken_and_push 40 { 41 typedef typename property_traits<ColorMap>::key_type argument_type; 42 typedef bool result_type; 43 darken_and_pushboost::detail::darken_and_push44 explicit darken_and_push(const ColorMap& color) : color(color) { } 45 operator ()boost::detail::darken_and_push46 bool operator()(const argument_type& value) const 47 { 48 typedef color_traits<typename property_traits<ColorMap>::value_type> 49 Color; 50 if (get(color, value) == Color::white()) { 51 put(color, value, Color::gray()); 52 return true; 53 } else { 54 return false; 55 } 56 } 57 58 ColorMap color; 59 }; 60 61 template<typename IndexMap> 62 struct has_not_been_seen 63 { 64 typedef bool result_type; 65 has_not_been_seenboost::detail::has_not_been_seen66 has_not_been_seen() { } 67 has_not_been_seenboost::detail::has_not_been_seen68 has_not_been_seen(std::size_t n, IndexMap index_map) 69 : seen(n), index_map(index_map) {} 70 71 template<typename Key> operator ()boost::detail::has_not_been_seen72 result_type operator()(Key key) 73 { 74 bool result = seen[get(index_map, key)]; 75 seen[get(index_map, key)] = true; 76 return !result; 77 } 78 swapboost::detail::has_not_been_seen79 void swap(has_not_been_seen& other) 80 { 81 using std::swap; 82 swap(seen, other.seen); 83 swap(index_map, other.index_map); 84 } 85 86 private: 87 dynamic_bitset<> seen; 88 IndexMap index_map; 89 }; 90 91 template<typename IndexMap> 92 inline void swap(has_not_been_seen<IndexMap> & x,has_not_been_seen<IndexMap> & y)93 swap(has_not_been_seen<IndexMap>& x, has_not_been_seen<IndexMap>& y) 94 { 95 x.swap(y); 96 } 97 98 template <class DistributedGraph, class ColorMap, class BFSVisitor, 99 class BufferRef, class VertexIndexMap> 100 inline void parallel_bfs_helper(DistributedGraph & g,typename graph_traits<DistributedGraph>::vertex_descriptor s,ColorMap color,BFSVisitor vis,BufferRef Q,VertexIndexMap)101 parallel_bfs_helper 102 (DistributedGraph& g, 103 typename graph_traits<DistributedGraph>::vertex_descriptor s, 104 ColorMap color, 105 BFSVisitor vis, 106 BufferRef Q, 107 VertexIndexMap) 108 { 109 set_property_map_role(vertex_color, color); 110 color.set_consistency_model(0); 111 breadth_first_search(g, s, Q.ref, vis, color); 112 } 113 114 template <class DistributedGraph, class ColorMap, class BFSVisitor, 115 class VertexIndexMap> parallel_bfs_helper(DistributedGraph & g,typename graph_traits<DistributedGraph>::vertex_descriptor s,ColorMap color,BFSVisitor vis,boost::param_not_found,VertexIndexMap vertex_index)116 void parallel_bfs_helper 117 (DistributedGraph& g, 118 typename graph_traits<DistributedGraph>::vertex_descriptor s, 119 ColorMap color, 120 BFSVisitor vis, 121 boost::param_not_found, 122 VertexIndexMap vertex_index) 123 { 124 using boost::graph::parallel::process_group; 125 126 typedef graph_traits<DistributedGraph> Traits; 127 typedef typename Traits::vertex_descriptor Vertex; 128 typedef typename boost::graph::parallel::process_group_type<DistributedGraph>::type 129 process_group_type; 130 131 set_property_map_role(vertex_color, color); 132 color.set_consistency_model(0); 133 134 // Buffer default 135 typedef typename property_map<DistributedGraph, vertex_owner_t> 136 ::const_type vertex_owner_map; 137 typedef boost::graph::distributed::distributed_queue< 138 process_group_type, vertex_owner_map, queue<Vertex>, 139 detail::darken_and_push<ColorMap> > queue_t; 140 queue_t Q(process_group(g), 141 get(vertex_owner, g), 142 detail::darken_and_push<ColorMap>(color)); 143 breadth_first_search(g, s, Q, vis, color); 144 } 145 146 template <class DistributedGraph, class ColorMap, class BFSVisitor, 147 class P, class T, class R> bfs_helper(DistributedGraph & g,typename graph_traits<DistributedGraph>::vertex_descriptor s,ColorMap color,BFSVisitor vis,const bgl_named_params<P,T,R> & params,boost::mpl::true_)148 void bfs_helper 149 (DistributedGraph& g, 150 typename graph_traits<DistributedGraph>::vertex_descriptor s, 151 ColorMap color, 152 BFSVisitor vis, 153 const bgl_named_params<P, T, R>& params, 154 boost::mpl::true_) 155 { 156 parallel_bfs_helper 157 (g, s, color, vis, get_param(params, buffer_param_t()), 158 choose_const_pmap(get_param(params, vertex_index), g, vertex_index)); 159 } 160 } 161 } 162 163 #endif // BOOST_GRAPH_PARALLEL_BFS_HPP 164