ceph/src/boost/libs/graph_parallel/include/boost/graph/parallel/properties.hpp

   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>
  54       Color operator()(const Key&) const { return traits::white(); }
  55
  56       template<typename Key>
  57       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>
  79       T operator()(const Key&) const { return (std::numeric_limits<T>::max)(); }
  80
  81       template<typename Key>
  82       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>
  96       T operator()(Key key) const { return key; }
  97       template<typename Key>
  98       T operator()(Key key, T, T y) const { return y; }
  99     };
 100   };
 101
 102   template<typename Property, typename PropertyMap>
 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