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 > combine_distances(const Graph & g,DistanceMap dist,Combinator combine,Distance init)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 BOOST_CONCEPT_ASSERT((AdaptableBinaryFunction< Combinator, Distance, 59 Distance, Distance >)); 60 61 // If there's ever an infinite distance, then we simply return 62 // infinity. Note that this /will/ include the a non-zero 63 // distance-to-self in the combined values. However, this is usually 64 // zero, so it shouldn't be too problematic. 65 Distance ret = init; 66 VertexIterator i, end; 67 for (boost::tie(i, end) = vertices(g); i != end; ++i) 68 { 69 Vertex v = *i; 70 if (get(dist, v) != DistanceNumbers::infinity()) 71 { 72 ret = combine(ret, get(dist, v)); 73 } 74 else 75 { 76 ret = DistanceNumbers::infinity(); 77 break; 78 } 79 } 80 return ret; 81 } 82 83 // Similar to std::plus<T>, but maximizes parameters 84 // rather than adding them. 85 template < typename T > struct maximize 86 { 87 typedef T result_type; 88 typedef T first_argument_type; 89 typedef T second_argument_type; operator ()boost::detail::maximize90 T operator()(T x, T y) const 91 { 92 BOOST_USING_STD_MAX(); 93 return max BOOST_PREVENT_MACRO_SUBSTITUTION(x, y); 94 } 95 }; 96 97 // Another helper, like maximize() to help abstract functional 98 // concepts. This is trivially instantiated for builtin numeric 99 // types, but should be specialized for those types that have 100 // discrete notions of reciprocals. 101 template < typename T > struct reciprocal 102 { 103 typedef T result_type; 104 typedef T argument_type; operator ()boost::detail::reciprocal105 T operator()(T t) { return T(1) / t; } 106 }; 107 } /* namespace detail */ 108 109 // This type defines the basic facilities used for computing values 110 // based on the geodesic distances between vertices. Examples include 111 // closeness centrality and mean geodesic distance. 112 template < typename Graph, typename DistanceType, typename ResultType > 113 struct geodesic_measure 114 { 115 typedef DistanceType distance_type; 116 typedef ResultType result_type; 117 typedef typename graph_traits< Graph >::vertices_size_type size_type; 118 119 typedef numeric_values< distance_type > distance_values; 120 typedef numeric_values< result_type > result_values; 121 infinite_distanceboost::geodesic_measure122 static inline distance_type infinite_distance() 123 { 124 return distance_values::infinity(); 125 } 126 infinite_resultboost::geodesic_measure127 static inline result_type infinite_result() 128 { 129 return result_values::infinity(); 130 } 131 zero_resultboost::geodesic_measure132 static inline result_type zero_result() { return result_values::zero(); } 133 }; 134 135 } /* namespace boost */ 136 137 #endif 138