graph/distributed/distributed_graph_utility.hpp

0001 // Copyright (C) 2005-2006 The Trustees of Indiana University.
0002 // Use, modification and distribution is subject to the Boost Software
0003 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0004 // http://www.boost.org/LICENSE_1_0.txt)
0005
0006 //  Authors: Peter Gottschling
0007 //           Douglas Gregor
0008 //           Andrew Lumsdaine
0009
0010 #include <boost/graph/iteration_macros.hpp>
0011 #include <boost/property_map/parallel/global_index_map.hpp>
0012
0013 #ifndef BOOST_GRAPH_DISTRIBUTED_GRAPH_UTILITY_INCLUDE
0014 #define BOOST_GRAPH_DISTRIBUTED_GRAPH_UTILITY_INCLUDE
0015
0016 #ifndef BOOST_GRAPH_USE_MPI
0017 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
0018 #endif
0019
0020 namespace boost { namespace graph {
0021
0022   template <class Property, class Graph>
0023   void property_on_inedges(Property p, const Graph& g)
0024   {
0025     BGL_FORALL_VERTICES_T(u, g, Graph)
0026       BGL_FORALL_INEDGES_T(u, e, g, Graph)
0027       request(p, e);
0028     synchronize(p);
0029   }
0030
0031   // For reverse graphs
0032   template <class Property, class Graph>
0033   void property_on_outedges(Property p, const Graph& g)
0034   {
0035     BGL_FORALL_VERTICES_T(u, g, Graph)
0036       BGL_FORALL_OUTEDGES_T(u, e, g, Graph)
0037         request(p, e);
0038     synchronize(p);
0039   }
0040
0041   template <class Property, class Graph>
0042   void property_on_successors(Property p, const Graph& g)
0043   {
0044     BGL_FORALL_VERTICES_T(u, g, Graph)
0045       BGL_FORALL_OUTEDGES_T(u, e, g, Graph)
0046         request(p, target(e, g));
0047     synchronize(p);
0048   }
0049
0050   template <class Property, class Graph>
0051   void property_on_predecessors(Property p, const Graph& g)
0052   {
0053     BGL_FORALL_VERTICES_T(u, g, Graph)
0054       BGL_FORALL_INEDGES_T(u, e, g, Graph)
0055         request(p, source(e, g));
0056     synchronize(p);
0057   }
0058
0059   // Like successors and predecessors but saves one synchronize (and a call)
0060   template <class Property, class Graph>
0061   void property_on_adjacents(Property p, const Graph& g)
0062   {
0063     BGL_FORALL_VERTICES_T(u, g, Graph) {
0064       BGL_FORALL_OUTEDGES_T(u, e, g, Graph)
0065         request(p, target(e, g));
0066       BGL_FORALL_INEDGES_T(u, e, g, Graph)
0067         request(p, source(e, g));
0068     }
0069     synchronize(p);
0070   }
0071
0072   template <class PropertyIn, class PropertyOut, class Graph>
0073   void copy_vertex_property(PropertyIn p_in, PropertyOut p_out, Graph& g)
0074   {
0075     BGL_FORALL_VERTICES_T(u, g, Graph)
0076       put(p_out, u, get(p_in, g));
0077   }
0078
0079   template <class PropertyIn, class PropertyOut, class Graph>
0080   void copy_edge_property(PropertyIn p_in, PropertyOut p_out, Graph& g)
0081   {
0082     BGL_FORALL_EDGES_T(e, g, Graph)
0083       put(p_out, e, get(p_in, g));
0084   }
0085
0086
0087   namespace distributed {
0088
0089     // Define global_index<Graph>  global(graph);
0090     // Then global(v) returns global index of v
0091     template <typename Graph>
0092     struct global_index
0093     {
0094       typedef typename property_map<Graph, vertex_index_t>::const_type
0095       VertexIndexMap;
0096       typedef typename property_map<Graph, vertex_global_t>::const_type
0097       VertexGlobalMap;
0098
0099       explicit global_index(Graph const& g)
0100         : global_index_map(process_group(g), num_vertices(g), get(vertex_index, g),
0101                            get(vertex_global, g)) {}
0102
0103       int operator() (typename graph_traits<Graph>::vertex_descriptor v)
0104       { return get(global_index_map, v); }
0105
0106     protected:
0107       boost::parallel::global_index_map<VertexIndexMap, VertexGlobalMap>
0108       global_index_map;
0109     };
0110
0111     template<typename T>
0112     struct additive_reducer {
0113       BOOST_STATIC_CONSTANT(bool, non_default_resolver = true);
0114
0115       template<typename K>
0116       T operator()(const K&) const { return T(0); }
0117
0118       template<typename K>
0119       T operator()(const K&, const T& local, const T& remote) const { return local + remote; }
0120     };
0121
0122     template <typename T>
0123     struct choose_min_reducer {
0124       BOOST_STATIC_CONSTANT(bool, non_default_resolver = true);
0125
0126       template<typename K>
0127       T operator()(const K&) const { return (std::numeric_limits<T>::max)(); }
0128
0129       template<typename K>
0130       T operator()(const K&, const T& x, const T& y) const
0131       { return x < y ? x : y; }
0132     };
0133
0134     // To use a property map syntactically like a function
0135     template <typename PropertyMap>
0136     struct property_map_reader
0137     {
0138       explicit property_map_reader(PropertyMap pm) : pm(pm) {}
0139
0140       template <typename T>
0141       typename PropertyMap::value_type
0142       operator() (const T& v)
0143       {
0144         return get(pm, v);
0145       }
0146     private:
0147       PropertyMap pm;
0148     };
0149
0150   } // namespace distributed
0151
0152 }} // namespace boost::graph
0153
0154 #endif // BOOST_GRAPH_DISTRIBUTED_GRAPH_UTILITY_INCLUDE