1 // Copyright 2004 The Trustees of Indiana University.
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)
7 // Authors: Douglas Gregor
9 #ifndef BOOST_GRAPH_PARALLEL_BFS_HPP
10 #define BOOST_GRAPH_PARALLEL_BFS_HPP
12 #ifndef BOOST_GRAPH_USE_MPI
13 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
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>
28 /** @brief A unary predicate that decides when to push into a
29 * breadth-first search queue.
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
38 template<typename ColorMap>
39 struct darken_and_push
41 typedef typename property_traits<ColorMap>::key_type argument_type;
42 typedef bool result_type;
44 explicit darken_and_push(const ColorMap& color) : color(color) { }
46 bool operator()(const argument_type& value) const
48 typedef color_traits<typename property_traits<ColorMap>::value_type>
50 if (get(color, value) == Color::white()) {
51 put(color, value, Color::gray());
61 template<typename IndexMap>
62 struct has_not_been_seen
64 typedef bool result_type;
66 has_not_been_seen() { }
68 has_not_been_seen(std::size_t n, IndexMap index_map)
69 : seen(n), index_map(index_map) {}
71 template<typename Key>
72 result_type operator()(Key key)
74 bool result = seen[get(index_map, key)];
75 seen[get(index_map, key)] = true;
79 void swap(has_not_been_seen& other)
82 swap(seen, other.seen);
83 swap(index_map, other.index_map);
87 dynamic_bitset<> seen;
91 template<typename IndexMap>
93 swap(has_not_been_seen<IndexMap>& x, has_not_been_seen<IndexMap>& y)
98 template <class DistributedGraph, class ColorMap, class BFSVisitor,
99 class BufferRef, class VertexIndexMap>
102 (DistributedGraph& g,
103 typename graph_traits<DistributedGraph>::vertex_descriptor s,
109 set_property_map_role(vertex_color, color);
110 color.set_consistency_model(0);
111 breadth_first_search(g, s, Q.ref, vis, color);
114 template <class DistributedGraph, class ColorMap, class BFSVisitor,
115 class VertexIndexMap>
116 void parallel_bfs_helper
117 (DistributedGraph& g,
118 typename graph_traits<DistributedGraph>::vertex_descriptor s,
121 boost::param_not_found,
122 VertexIndexMap vertex_index)
124 using boost::graph::parallel::process_group;
126 typedef graph_traits<DistributedGraph> Traits;
127 typedef typename Traits::vertex_descriptor Vertex;
128 typedef typename boost::graph::parallel::process_group_type<DistributedGraph>::type
131 set_property_map_role(vertex_color, color);
132 color.set_consistency_model(0);
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);
146 template <class DistributedGraph, class ColorMap, class BFSVisitor,
147 class P, class T, class R>
149 (DistributedGraph& g,
150 typename graph_traits<DistributedGraph>::vertex_descriptor s,
153 const bgl_named_params<P, T, R>& params,
157 (g, s, color, vis, get_param(params, buffer_param_t()),
158 choose_const_pmap(get_param(params, vertex_index), g, vertex_index));
163 #endif // BOOST_GRAPH_PARALLEL_BFS_HPP