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