ceph/src/boost/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 = {https://doi.org/10.1016/j.socnet.2005.11.005},
  37 //             volume = {28},
  38 //             year = {2006}
  39 //         }
  40 //     }
  41
  42 namespace detail
  43 {
  44     // Note that this assumes T == property_traits<DistanceMap>::value_type
  45     // and that the args and return of combine are also T.
  46     template < typename Graph, typename DistanceMap, typename Combinator,
  47         typename Distance >
  48     inline Distance combine_distances(
  49         const Graph& g, DistanceMap dist, Combinator combine, Distance init)
  50     {
  51         BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >));
  52         typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
  53         typedef typename graph_traits< Graph >::vertex_iterator VertexIterator;
  54         BOOST_CONCEPT_ASSERT(
  55             (ReadablePropertyMapConcept< DistanceMap, Vertex >));
  56         BOOST_CONCEPT_ASSERT((NumericValueConcept< Distance >));
  57         typedef numeric_values< Distance > DistanceNumbers;
  58 //      NOTE: Disabled until this concept assert is fixed in Boost.ConceptCheck.
  59 //         BOOST_CONCEPT_ASSERT((AdaptableBinaryFunction< Combinator, Distance,
  60 //             Distance, Distance >));
  61
  62         // If there's ever an infinite distance, then we simply return
  63         // infinity. Note that this /will/ include the a non-zero
  64         // distance-to-self in the combined values. However, this is usually
  65         // zero, so it shouldn't be too problematic.
  66         Distance ret = init;
  67         VertexIterator i, end;
  68         for (boost::tie(i, end) = vertices(g); i != end; ++i)
  69         {
  70             Vertex v = *i;
  71             if (get(dist, v) != DistanceNumbers::infinity())
  72             {
  73                 ret = combine(ret, get(dist, v));
  74             }
  75             else
  76             {
  77                 ret = DistanceNumbers::infinity();
  78                 break;
  79             }
  80         }
  81         return ret;
  82     }
  83
  84     // Similar to std::plus<T>, but maximizes parameters
  85     // rather than adding them.
  86     template < typename T > struct maximize
  87     {
  88         typedef T result_type;
  89         typedef T first_argument_type;
  90         typedef T second_argument_type;
  91         T operator()(T x, T y) const
  92         {
  93             BOOST_USING_STD_MAX();
  94             return max BOOST_PREVENT_MACRO_SUBSTITUTION(x, y);
  95         }
  96     };
  97
  98     // Another helper, like maximize() to help abstract functional
  99     // concepts. This is trivially instantiated for builtin numeric
 100     // types, but should be specialized for those types that have
 101     // discrete notions of reciprocals.
 102     template < typename T > struct reciprocal
 103     {
 104         typedef T result_type;
 105         typedef T argument_type;
 106         T operator()(T t) { return T(1) / t; }
 107     };
 108 } /* namespace detail */
 109
 110 // This type defines the basic facilities used for computing values
 111 // based on the geodesic distances between vertices. Examples include
 112 // closeness centrality and mean geodesic distance.
 113 template < typename Graph, typename DistanceType, typename ResultType >
 114 struct geodesic_measure
 115 {
 116     typedef DistanceType distance_type;
 117     typedef ResultType result_type;
 118     typedef typename graph_traits< Graph >::vertices_size_type size_type;
 119
 120     typedef numeric_values< distance_type > distance_values;
 121     typedef numeric_values< result_type > result_values;
 122
 123     static inline distance_type infinite_distance()
 124     {
 125         return distance_values::infinity();
 126     }
 127
 128     static inline result_type infinite_result()
 129     {
 130         return result_values::infinity();
 131     }
 132
 133     static inline result_type zero_result() { return result_values::zero(); }
 134 };
 135
 136 } /* namespace boost */
 137
 138 #endif