Imported Upstream version 1.49.0upstream/1.49.0

1 files changed, 164 insertions, 0 deletions

diff --git a/boost/graph/distributed/breadth_first_search.hpp b/boost/graph/distributed/breadth_first_search.hpp
new file mode 100644
index 0000000000..c987585f5f
--- /dev/null
+++ b/boost/graph/distributed/breadth_first_search.hpp
@@ -0,0 +1,164 @@
+// 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