ceph/src/boost/libs/graph_parallel/include/boost/graph/distributed/distributed_graph_utility.hpp

   1 // Copyright (C) 2005-2006 The Trustees of Indiana University.
   2 // Use, modification and distribution is subject to the Boost Software
   3 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   4 // http://www.boost.org/LICENSE_1_0.txt)
   5
   6 //  Authors: Peter Gottschling
   7 //           Douglas Gregor
   8 //           Andrew Lumsdaine
   9
  10 #include <boost/graph/iteration_macros.hpp>
  11 #include <boost/property_map/parallel/global_index_map.hpp>
  12
  13 #ifndef BOOST_GRAPH_DISTRIBUTED_GRAPH_UTILITY_INCLUDE
  14 #define BOOST_GRAPH_DISTRIBUTED_GRAPH_UTILITY_INCLUDE
  15
  16 #ifndef BOOST_GRAPH_USE_MPI
  17 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
  18 #endif
  19
  20 namespace boost { namespace graph {
  21
  22   template <class Property, class Graph>
  23   void property_on_inedges(Property p, const Graph& g)
  24   {
  25     BGL_FORALL_VERTICES_T(u, g, Graph)
  26       BGL_FORALL_INEDGES_T(u, e, g, Graph)
  27       request(p, e);
  28     synchronize(p);
  29   }
  30
  31   // For reverse graphs
  32   template <class Property, class Graph>
  33   void property_on_outedges(Property p, const Graph& g)
  34   {
  35     BGL_FORALL_VERTICES_T(u, g, Graph)
  36       BGL_FORALL_OUTEDGES_T(u, e, g, Graph)
  37         request(p, e);
  38     synchronize(p);
  39   }
  40
  41   template <class Property, class Graph>
  42   void property_on_successors(Property p, const Graph& g)
  43   {
  44     BGL_FORALL_VERTICES_T(u, g, Graph)
  45       BGL_FORALL_OUTEDGES_T(u, e, g, Graph)
  46         request(p, target(e, g));
  47     synchronize(p);
  48   }
  49
  50   template <class Property, class Graph>
  51   void property_on_predecessors(Property p, const Graph& g)
  52   {
  53     BGL_FORALL_VERTICES_T(u, g, Graph)
  54       BGL_FORALL_INEDGES_T(u, e, g, Graph)
  55         request(p, source(e, g));
  56     synchronize(p);
  57   }
  58
  59   // Like successors and predecessors but saves one synchronize (and a call)
  60   template <class Property, class Graph>
  61   void property_on_adjacents(Property p, const Graph& g)
  62   {
  63     BGL_FORALL_VERTICES_T(u, g, Graph) {
  64       BGL_FORALL_OUTEDGES_T(u, e, g, Graph)
  65         request(p, target(e, g));
  66       BGL_FORALL_INEDGES_T(u, e, g, Graph)
  67         request(p, source(e, g));
  68     }
  69     synchronize(p);
  70   }
  71
  72   template <class PropertyIn, class PropertyOut, class Graph>
  73   void copy_vertex_property(PropertyIn p_in, PropertyOut p_out, Graph& g)
  74   {
  75     BGL_FORALL_VERTICES_T(u, g, Graph)
  76       put(p_out, u, get(p_in, g));
  77   }
  78
  79   template <class PropertyIn, class PropertyOut, class Graph>
  80   void copy_edge_property(PropertyIn p_in, PropertyOut p_out, Graph& g)
  81   {
  82     BGL_FORALL_EDGES_T(e, g, Graph)
  83       put(p_out, e, get(p_in, g));
  84   }
  85
  86
  87   namespace distributed {
  88
  89     // Define global_index<Graph>  global(graph);
  90     // Then global(v) returns global index of v
  91     template <typename Graph>
  92     struct global_index
  93     {
  94       typedef typename property_map<Graph, vertex_index_t>::const_type
  95       VertexIndexMap;
  96       typedef typename property_map<Graph, vertex_global_t>::const_type
  97       VertexGlobalMap;
  98
  99       explicit global_index(Graph const& g)
 100         : global_index_map(process_group(g), num_vertices(g), get(vertex_index, g),
 101                            get(vertex_global, g)) {}
 102
 103       int operator() (typename graph_traits<Graph>::vertex_descriptor v)
 104       { return get(global_index_map, v); }
 105
 106     protected:
 107       boost::parallel::global_index_map<VertexIndexMap, VertexGlobalMap>
 108       global_index_map;
 109     };
 110
 111     template<typename T>
 112     struct additive_reducer {
 113       BOOST_STATIC_CONSTANT(bool, non_default_resolver = true);
 114
 115       template<typename K>
 116       T operator()(const K&) const { return T(0); }
 117
 118       template<typename K>
 119       T operator()(const K&, const T& local, const T& remote) const { return local + remote; }
 120     };
 121
 122     template <typename T>
 123     struct choose_min_reducer {
 124       BOOST_STATIC_CONSTANT(bool, non_default_resolver = true);
 125
 126       template<typename K>
 127       T operator()(const K&) const { return (std::numeric_limits<T>::max)(); }
 128
 129       template<typename K>
 130       T operator()(const K&, const T& x, const T& y) const
 131       { return x < y ? x : y; }
 132     };
 133
 134     // To use a property map syntactically like a function
 135     template <typename PropertyMap>
 136     struct property_map_reader
 137     {
 138       explicit property_map_reader(PropertyMap pm) : pm(pm) {}
 139
 140       template <typename T>
 141       typename PropertyMap::value_type
 142       operator() (const T& v)
 143       {
 144         return get(pm, v);
 145       }
 146     private:
 147       PropertyMap pm;
 148     };
 149
 150   } // namespace distributed
 151
 152 }} // namespace boost::graph
 153
 154 #endif // BOOST_GRAPH_DISTRIBUTED_GRAPH_UTILITY_INCLUDE