// Copyright 2004 The Trustees of Indiana University. | |
// Use, modification and distribution is subject to the Boost Software | |
// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
// http://www.boost.org/LICENSE_1_0.txt) | |
// Authors: Douglas Gregor | |
// Andrew Lumsdaine | |
#ifndef BOOST_GRAPH_PARALLEL_BFS_HPP | |
#define BOOST_GRAPH_PARALLEL_BFS_HPP | |
#ifndef BOOST_GRAPH_USE_MPI | |
#error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included" | |
#endif | |
#include <boost/graph/breadth_first_search.hpp> | |
#include <boost/graph/overloading.hpp> | |
#include <boost/graph/distributed/concepts.hpp> | |
#include <boost/graph/distributed/detail/filtered_queue.hpp> | |
#include <boost/graph/distributed/queue.hpp> | |
#include <boost/dynamic_bitset.hpp> | |
#include <boost/pending/queue.hpp> | |
#include <boost/graph/parallel/properties.hpp> | |
#include <boost/graph/parallel/container_traits.hpp> | |
namespace boost { | |
namespace detail { | |
/** @brief A unary predicate that decides when to push into a | |
* breadth-first search queue. | |
* | |
* This predicate stores a color map that is used to determine | |
* when to push. If it is provided with a key for which the color | |
* is white, it darkens the color to gray and returns true (so | |
* that the value will be pushed appropriately); if the color is | |
* not white, it returns false so that the vertex will be | |
* ignored. | |
*/ | |
template<typename ColorMap> | |
struct darken_and_push | |
{ | |
typedef typename property_traits<ColorMap>::key_type argument_type; | |
typedef bool result_type; | |
explicit darken_and_push(const ColorMap& color) : color(color) { } | |
bool operator()(const argument_type& value) const | |
{ | |
typedef color_traits<typename property_traits<ColorMap>::value_type> | |
Color; | |
if (get(color, value) == Color::white()) { | |
put(color, value, Color::gray()); | |
return true; | |
} else { | |
return false; | |
} | |
} | |
ColorMap color; | |
}; | |
template<typename IndexMap> | |
struct has_not_been_seen | |
{ | |
typedef bool result_type; | |
has_not_been_seen() { } | |
has_not_been_seen(std::size_t n, IndexMap index_map) | |
: seen(n), index_map(index_map) {} | |
template<typename Key> | |
result_type operator()(Key key) | |
{ | |
bool result = seen[get(index_map, key)]; | |
seen[get(index_map, key)] = true; | |
return !result; | |
} | |
void swap(has_not_been_seen& other) | |
{ | |
using std::swap; | |
swap(seen, other.seen); | |
swap(index_map, other.index_map); | |
} | |
private: | |
dynamic_bitset<> seen; | |
IndexMap index_map; | |
}; | |
template<typename IndexMap> | |
inline void | |
swap(has_not_been_seen<IndexMap>& x, has_not_been_seen<IndexMap>& y) | |
{ | |
x.swap(y); | |
} | |
template <class DistributedGraph, class ColorMap, class BFSVisitor, | |
class BufferRef, class VertexIndexMap> | |
inline void | |
parallel_bfs_helper | |
(DistributedGraph& g, | |
typename graph_traits<DistributedGraph>::vertex_descriptor s, | |
ColorMap color, | |
BFSVisitor vis, | |
BufferRef Q, | |
VertexIndexMap) | |
{ | |
set_property_map_role(vertex_color, color); | |
color.set_consistency_model(0); | |
breadth_first_search(g, s, Q.ref, vis, color); | |
} | |
template <class DistributedGraph, class ColorMap, class BFSVisitor, | |
class VertexIndexMap> | |
void parallel_bfs_helper | |
(DistributedGraph& g, | |
typename graph_traits<DistributedGraph>::vertex_descriptor s, | |
ColorMap color, | |
BFSVisitor vis, | |
error_property_not_found, | |
VertexIndexMap vertex_index) | |
{ | |
using boost::graph::parallel::process_group; | |
typedef graph_traits<DistributedGraph> Traits; | |
typedef typename Traits::vertex_descriptor Vertex; | |
typedef typename boost::graph::parallel::process_group_type<DistributedGraph>::type | |
process_group_type; | |
set_property_map_role(vertex_color, color); | |
color.set_consistency_model(0); | |
// Buffer default | |
typedef typename property_map<DistributedGraph, vertex_owner_t> | |
::const_type vertex_owner_map; | |
typedef boost::graph::distributed::distributed_queue< | |
process_group_type, vertex_owner_map, queue<Vertex>, | |
detail::darken_and_push<ColorMap> > queue_t; | |
queue_t Q(process_group(g), | |
get(vertex_owner, g), | |
detail::darken_and_push<ColorMap>(color)); | |
breadth_first_search(g, s, Q, vis, color); | |
} | |
template <class DistributedGraph, class ColorMap, class BFSVisitor, | |
class P, class T, class R> | |
void bfs_helper | |
(DistributedGraph& g, | |
typename graph_traits<DistributedGraph>::vertex_descriptor s, | |
ColorMap color, | |
BFSVisitor vis, | |
const bgl_named_params<P, T, R>& params, | |
BOOST_GRAPH_ENABLE_IF_MODELS(DistributedGraph, distributed_graph_tag, | |
void)*) | |
{ | |
parallel_bfs_helper | |
(g, s, color, vis, get_param(params, buffer_param_t()), | |
choose_const_pmap(get_param(params, vertex_index), g, vertex_index)); | |
} | |
} | |
} | |
#endif // BOOST_GRAPH_PARALLEL_BFS_HPP |