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 combine_distances(const Graph & g,DistanceMap dist,Combinator combine,Distance init)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 { operator ()boost::detail::maximize87 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; operator ()boost::detail::reciprocal101 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 infinite_distanceboost::geodesic_measure119 static inline distance_type infinite_distance() 120 { return distance_values::infinity(); } 121 infinite_resultboost::geodesic_measure122 static inline result_type infinite_result() 123 { return result_values::infinity(); } 124 zero_resultboost::geodesic_measure125 static inline result_type zero_result() 126 { return result_values::zero(); } 127 }; 128 129 } /* namespace boost */ 130 131 #endif 132