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 10 #ifndef BOOST_GRAPH_PARALLEL_PROPERTIES_HPP 11 #define BOOST_GRAPH_PARALLEL_PROPERTIES_HPP 12 13 #ifndef BOOST_GRAPH_USE_MPI 14 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included" 15 #endif 16 17 #include <boost/graph/properties.hpp> 18 #include <boost/property_map/parallel/distributed_property_map.hpp> 19 20 namespace boost { 21 /*************************************************************************** 22 * Property map reduction operations 23 ***************************************************************************/ 24 /** 25 * Metafunction that produces a reduction operation for the given 26 * property. The default behavior merely forwards to @ref 27 * basic_reduce, but it is expected that this class template will be 28 * specified for important properties. 29 */ 30 template<typename Property> 31 struct property_reduce 32 { 33 template<typename Value> 34 class apply : public parallel::basic_reduce<Value> {}; 35 }; 36 37 /** 38 * Reduction of vertex colors can only darken, not lighten, the 39 * color. Black cannot turn black, grey can only turn black, and 40 * white can be changed to either color. The default color is white. 41 */ 42 template<> 43 struct property_reduce<vertex_color_t> 44 { 45 template<typename Color> 46 class apply 47 { 48 typedef color_traits<Color> traits; 49 50 public: 51 BOOST_STATIC_CONSTANT(bool, non_default_resolver = true); 52 53 template<typename Key> operator ()(const Key &) const54 Color operator()(const Key&) const { return traits::white(); } 55 56 template<typename Key> operator ()(const Key &,Color local,Color remote) const57 Color operator()(const Key&, Color local, Color remote) const { 58 if (local == traits::white()) return remote; 59 else if (remote == traits::black()) return remote; 60 else return local; 61 } 62 }; 63 }; 64 65 /** 66 * Reduction of a distance always takes the shorter distance. The 67 * default distance value is the maximum value for the data type. 68 */ 69 template<> 70 struct property_reduce<vertex_distance_t> 71 { 72 template<typename T> 73 class apply 74 { 75 public: 76 BOOST_STATIC_CONSTANT(bool, non_default_resolver = true); 77 78 template<typename Key> operator ()(const Key &) const79 T operator()(const Key&) const { return (std::numeric_limits<T>::max)(); } 80 81 template<typename Key> operator ()(const Key &,T x,T y) const82 T operator()(const Key&, T x, T y) const { return x < y? x : y; } 83 }; 84 }; 85 86 template<> 87 struct property_reduce<vertex_predecessor_t> 88 { 89 template<typename T> 90 class apply 91 { 92 public: 93 BOOST_STATIC_CONSTANT(bool, non_default_resolver = true); 94 95 template<typename Key> operator ()(Key key) const96 T operator()(Key key) const { return key; } 97 template<typename Key> operator ()(Key key,T,T y) const98 T operator()(Key key, T, T y) const { return y; } 99 }; 100 }; 101 102 template<typename Property, typename PropertyMap> set_property_map_role(Property p,PropertyMap pm)103 inline void set_property_map_role(Property p, PropertyMap pm) 104 { 105 typedef typename property_traits<PropertyMap>::value_type value_type; 106 typedef property_reduce<Property> property_red; 107 typedef typename property_red::template apply<value_type> reduce; 108 109 pm.set_reduce(reduce()); 110 } 111 112 } // end namespace boost 113 #endif // BOOST_GRAPH_PARALLEL_PROPERTIES_HPP 114