ceph/src/boost/libs/graph/include/boost/graph/detail/geodesic.hpp

   1 // (C) Copyright 2007 Andrew Sutton
   2 //
   3 // Use, modification and distribution are subject to the
   4 // Boost Software License, Version 1.0 (See accompanying file
   5 // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
   6
   7 #ifndef BOOST_GRAPH_DETAIL_GEODESIC_HPP
   8 #define BOOST_GRAPH_DETAIL_GEODESIC_HPP
   9
  10 #include <functional>
  11 #include <boost/config.hpp>
  12 #include <boost/graph/graph_concepts.hpp>
  13 #include <boost/graph/numeric_values.hpp>
  14 #include <boost/concept/assert.hpp>
  15
  16 // TODO: Should this really be in detail?
  17
  18 namespace boost
  19 {
  20 // This is a very good discussion on centrality measures. While I can't
  21 // say that this has been the motivating factor for the design and
  22 // implementation of ths centrality framework, it does provide a single
  23 // point of reference for defining things like degree and closeness
  24 // centrality. Plus, the bibliography seems fairly complete.
  25 //
  26 //     @article{citeulike:1144245,
  27 //         author = {Borgatti, Stephen  P. and Everett, Martin  G.},
  28 //         citeulike-article-id = {1144245},
  29 //         doi = {10.1016/j.socnet.2005.11.005},
  30 //         journal = {Social Networks},
  31 //         month = {October},
  32 //         number = {4},
  33 //         pages = {466--484},
  34 //         priority = {0},
  35 //         title = {A Graph-theoretic perspective on centrality},
  36 //         url = {http://dx.doi.org/10.1016/j.socnet.2005.11.005},
  37 //             volume = {28},
  38 //             year = {2006}
  39 //         }
  40 //     }
  41
  42 namespace detail {
  43     // Note that this assumes T == property_traits<DistanceMap>::value_type
  44     // and that the args and return of combine are also T.
  45     template <typename Graph,
  46                 typename DistanceMap,
  47                 typename Combinator,
  48                 typename Distance>
  49     inline Distance
  50     combine_distances(const Graph& g,
  51                         DistanceMap dist,
  52                         Combinator combine,
  53                         Distance init)
  54     {
  55         BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> ));
  56         typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
  57         typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
  58         BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<DistanceMap,Vertex> ));
  59         BOOST_CONCEPT_ASSERT(( NumericValueConcept<Distance> ));
  60         typedef numeric_values<Distance> DistanceNumbers;
  61         BOOST_CONCEPT_ASSERT(( AdaptableBinaryFunction<Combinator,Distance,Distance,Distance> ));
  62
  63         // If there's ever an infinite distance, then we simply return
  64         // infinity. Note that this /will/ include the a non-zero
  65         // distance-to-self in the combined values. However, this is usually
  66         // zero, so it shouldn't be too problematic.
  67         Distance ret = init;
  68         VertexIterator i, end;
  69         for(boost::tie(i, end) = vertices(g); i != end; ++i) {
  70             Vertex v = *i;
  71             if(get(dist, v) != DistanceNumbers::infinity()) {
  72                 ret = combine(ret, get(dist, v));
  73             }
  74             else {
  75                 ret = DistanceNumbers::infinity();
  76                 break;
  77             }
  78         }
  79         return ret;
  80     }
  81
  82     // Similar to std::plus<T>, but maximizes parameters
  83     // rather than adding them.
  84     template <typename T>
  85     struct maximize : public std::binary_function<T, T, T>
  86     {
  87         T operator ()(T x, T y) const
  88         { BOOST_USING_STD_MAX(); return max BOOST_PREVENT_MACRO_SUBSTITUTION (x, y); }
  89     };
  90
  91     // Another helper, like maximize() to help abstract functional
  92     // concepts. This is trivially instantiated for builtin numeric
  93     // types, but should be specialized for those types that have
  94     // discrete notions of reciprocals.
  95     template <typename T>
  96     struct reciprocal : public std::unary_function<T, T>
  97     {
  98         typedef std::unary_function<T, T> function_type;
  99         typedef typename function_type::result_type result_type;
 100         typedef typename function_type::argument_type argument_type;
 101         T operator ()(T t)
 102         { return T(1) / t; }
 103     };
 104 } /* namespace detail */
 105
 106 // This type defines the basic facilities used for computing values
 107 // based on the geodesic distances between vertices. Examples include
 108 // closeness centrality and mean geodesic distance.
 109 template <typename Graph, typename DistanceType, typename ResultType>
 110 struct geodesic_measure
 111 {
 112     typedef DistanceType distance_type;
 113     typedef ResultType result_type;
 114     typedef typename graph_traits<Graph>::vertices_size_type size_type;
 115
 116     typedef numeric_values<distance_type> distance_values;
 117     typedef numeric_values<result_type> result_values;
 118
 119     static inline distance_type infinite_distance()
 120     { return distance_values::infinity(); }
 121
 122     static inline result_type infinite_result()
 123     { return result_values::infinity(); }
 124
 125     static inline result_type zero_result()
 126     { return result_values::zero(); }
 127 };
 128
 129 } /* namespace boost */
 130
 131 #endif