graph/parallel/properties.hpp

0001 // Copyright 2004 The Trustees of Indiana University.
0002
0003 // Use, modification and distribution is subject to the Boost Software
0004 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006
0007 //  Authors: Douglas Gregor
0008 //           Andrew Lumsdaine
0009
0010 #ifndef BOOST_GRAPH_PARALLEL_PROPERTIES_HPP
0011 #define BOOST_GRAPH_PARALLEL_PROPERTIES_HPP
0012
0013 #ifndef BOOST_GRAPH_USE_MPI
0014 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
0015 #endif
0016
0017 #include <boost/graph/properties.hpp>
0018 #include <boost/property_map/parallel/distributed_property_map.hpp>
0019
0020 namespace boost {
0021   /***************************************************************************
0022    * Property map reduction operations
0023    ***************************************************************************/
0024   /**
0025    * Metafunction that produces a reduction operation for the given
0026    * property. The default behavior merely forwards to @ref
0027    * basic_reduce, but it is expected that this class template will be
0028    * specified for important properties.
0029    */
0030   template<typename Property>
0031   struct property_reduce
0032   {
0033     template<typename Value>
0034     class apply : public parallel::basic_reduce<Value> {};
0035   };
0036
0037   /**
0038    * Reduction of vertex colors can only darken, not lighten, the
0039    * color. Black cannot turn black, grey can only turn black, and
0040    * white can be changed to either color. The default color is white.
0041    */
0042   template<>
0043   struct property_reduce<vertex_color_t>
0044   {
0045     template<typename Color>
0046     class apply
0047     {
0048       typedef color_traits<Color> traits;
0049
0050     public:
0051       BOOST_STATIC_CONSTANT(bool, non_default_resolver = true);
0052
0053       template<typename Key>
0054       Color operator()(const Key&) const { return traits::white(); }
0055
0056       template<typename Key>
0057       Color operator()(const Key&, Color local, Color remote) const {
0058         if (local == traits::white()) return remote;
0059         else if (remote == traits::black()) return remote;
0060         else return local;
0061       }
0062     };
0063   };
0064
0065   /**
0066    * Reduction of a distance always takes the shorter distance. The
0067    * default distance value is the maximum value for the data type.
0068    */
0069   template<>
0070   struct property_reduce<vertex_distance_t>
0071   {
0072     template<typename T>
0073     class apply
0074     {
0075     public:
0076       BOOST_STATIC_CONSTANT(bool, non_default_resolver = true);
0077
0078       template<typename Key>
0079       T operator()(const Key&) const { return (std::numeric_limits<T>::max)(); }
0080
0081       template<typename Key>
0082       T operator()(const Key&, T x, T y) const { return x < y? x : y; }
0083     };
0084   };
0085
0086   template<>
0087   struct property_reduce<vertex_predecessor_t>
0088   {
0089     template<typename T>
0090     class apply
0091     {
0092     public:
0093       BOOST_STATIC_CONSTANT(bool, non_default_resolver = true);
0094
0095       template<typename Key>
0096       T operator()(Key key) const { return key; }
0097       template<typename Key>
0098       T operator()(Key key, T, T y) const { return y; }
0099     };
0100   };
0101
0102   template<typename Property, typename PropertyMap>
0103   inline void set_property_map_role(Property p, PropertyMap pm)
0104   {
0105     typedef typename property_traits<PropertyMap>::value_type value_type;
0106     typedef property_reduce<Property> property_red;
0107     typedef typename property_red::template apply<value_type> reduce;
0108
0109     pm.set_reduce(reduce());
0110   }
0111
0112 } // end namespace boost
0113 #endif // BOOST_GRAPH_PARALLEL_PROPERTIES_HPP