ceph/src/boost/boost/graph/distributed/breadth_first_search.hpp

   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
  44       explicit darken_and_push(const ColorMap& color) : color(color) { }
  45
  46       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
  66       has_not_been_seen() { }
  67
  68       has_not_been_seen(std::size_t n, IndexMap index_map)
  69         : seen(n), index_map(index_map) {}
  70
  71       template<typename Key>
  72       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
  79       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
  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
 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>
 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>
 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