graph/detail/geodesic.hpp

0001 // (C) Copyright 2007 Andrew Sutton
0002 //
0003 // Use, modification and distribution are subject to the
0004 // Boost Software License, Version 1.0 (See accompanying file
0005 // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
0006
0007 #ifndef BOOST_GRAPH_DETAIL_GEODESIC_HPP
0008 #define BOOST_GRAPH_DETAIL_GEODESIC_HPP
0009
0010 #include <functional>
0011 #include <boost/config.hpp>
0012 #include <boost/graph/graph_concepts.hpp>
0013 #include <boost/graph/numeric_values.hpp>
0014 #include <boost/concept/assert.hpp>
0015
0016 // TODO: Should this really be in detail?
0017
0018 namespace boost
0019 {
0020 // This is a very good discussion on centrality measures. While I can't
0021 // say that this has been the motivating factor for the design and
0022 // implementation of ths centrality framework, it does provide a single
0023 // point of reference for defining things like degree and closeness
0024 // centrality. Plus, the bibliography seems fairly complete.
0025 //
0026 //     @article{citeulike:1144245,
0027 //         author = {Borgatti, Stephen  P. and Everett, Martin  G.},
0028 //         citeulike-article-id = {1144245},
0029 //         doi = {10.1016/j.socnet.2005.11.005},
0030 //         journal = {Social Networks},
0031 //         month = {October},
0032 //         number = {4},
0033 //         pages = {466--484},
0034 //         priority = {0},
0035 //         title = {A Graph-theoretic perspective on centrality},
0036 //         url = {https://doi.org/10.1016/j.socnet.2005.11.005},
0037 //             volume = {28},
0038 //             year = {2006}
0039 //         }
0040 //     }
0041
0042 namespace detail
0043 {
0044     // Note that this assumes T == property_traits<DistanceMap>::value_type
0045     // and that the args and return of combine are also T.
0046     template < typename Graph, typename DistanceMap, typename Combinator,
0047         typename Distance >
0048     inline Distance combine_distances(
0049         const Graph& g, DistanceMap dist, Combinator combine, Distance init)
0050     {
0051         BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >));
0052         typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0053         typedef typename graph_traits< Graph >::vertex_iterator VertexIterator;
0054         BOOST_CONCEPT_ASSERT(
0055             (ReadablePropertyMapConcept< DistanceMap, Vertex >));
0056         BOOST_CONCEPT_ASSERT((NumericValueConcept< Distance >));
0057         typedef numeric_values< Distance > DistanceNumbers;
0058 //      NOTE: Disabled until this concept assert is fixed in Boost.ConceptCheck.
0059 //         BOOST_CONCEPT_ASSERT((AdaptableBinaryFunction< Combinator, Distance,
0060 //             Distance, Distance >));
0061
0062         // If there's ever an infinite distance, then we simply return
0063         // infinity. Note that this /will/ include the a non-zero
0064         // distance-to-self in the combined values. However, this is usually
0065         // zero, so it shouldn't be too problematic.
0066         Distance ret = init;
0067         VertexIterator i, end;
0068         for (boost::tie(i, end) = vertices(g); i != end; ++i)
0069         {
0070             Vertex v = *i;
0071             if (get(dist, v) != DistanceNumbers::infinity())
0072             {
0073                 ret = combine(ret, get(dist, v));
0074             }
0075             else
0076             {
0077                 ret = DistanceNumbers::infinity();
0078                 break;
0079             }
0080         }
0081         return ret;
0082     }
0083
0084     // Similar to std::plus<T>, but maximizes parameters
0085     // rather than adding them.
0086     template < typename T > struct maximize
0087     {
0088         typedef T result_type;
0089         typedef T first_argument_type;
0090         typedef T second_argument_type;
0091         T operator()(T x, T y) const
0092         {
0093             BOOST_USING_STD_MAX();
0094             return max BOOST_PREVENT_MACRO_SUBSTITUTION(x, y);
0095         }
0096     };
0097
0098     // Another helper, like maximize() to help abstract functional
0099     // concepts. This is trivially instantiated for builtin numeric
0100     // types, but should be specialized for those types that have
0101     // discrete notions of reciprocals.
0102     template < typename T > struct reciprocal
0103     {
0104         typedef T result_type;
0105         typedef T argument_type;
0106         T operator()(T t) { return T(1) / t; }
0107     };
0108 } /* namespace detail */
0109
0110 // This type defines the basic facilities used for computing values
0111 // based on the geodesic distances between vertices. Examples include
0112 // closeness centrality and mean geodesic distance.
0113 template < typename Graph, typename DistanceType, typename ResultType >
0114 struct geodesic_measure
0115 {
0116     typedef DistanceType distance_type;
0117     typedef ResultType result_type;
0118     typedef typename graph_traits< Graph >::vertices_size_type size_type;
0119
0120     typedef numeric_values< distance_type > distance_values;
0121     typedef numeric_values< result_type > result_values;
0122
0123     static inline distance_type infinite_distance()
0124     {
0125         return distance_values::infinity();
0126     }
0127
0128     static inline result_type infinite_result()
0129     {
0130         return result_values::infinity();
0131     }
0132
0133     static inline result_type zero_result() { return result_values::zero(); }
0134 };
0135
0136 } /* namespace boost */
0137
0138 #endif