Chris@16: // (C) Copyright 2007 Andrew Sutton
Chris@16: //
Chris@16: // Use, modification and distribution are subject to the
Chris@16: // Boost Software License, Version 1.0 (See accompanying file
Chris@16: // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_DETAIL_GEODESIC_HPP
Chris@16: #define BOOST_GRAPH_DETAIL_GEODESIC_HPP
Chris@16: 
Chris@16: #include <functional>
Chris@16: #include <boost/config.hpp>
Chris@16: #include <boost/graph/graph_concepts.hpp>
Chris@16: #include <boost/graph/numeric_values.hpp>
Chris@16: #include <boost/concept/assert.hpp>
Chris@16: 
Chris@16: // TODO: Should this really be in detail?
Chris@16: 
Chris@16: namespace boost
Chris@16: {
Chris@16: // This is a very good discussion on centrality measures. While I can't
Chris@16: // say that this has been the motivating factor for the design and
Chris@16: // implementation of ths centrality framework, it does provide a single
Chris@16: // point of reference for defining things like degree and closeness
Chris@16: // centrality. Plus, the bibliography seems fairly complete.
Chris@16: //
Chris@16: //     @article{citeulike:1144245,
Chris@16: //         author = {Borgatti, Stephen  P. and Everett, Martin  G.},
Chris@16: //         citeulike-article-id = {1144245},
Chris@16: //         doi = {10.1016/j.socnet.2005.11.005},
Chris@16: //         journal = {Social Networks},
Chris@16: //         month = {October},
Chris@16: //         number = {4},
Chris@16: //         pages = {466--484},
Chris@16: //         priority = {0},
Chris@16: //         title = {A Graph-theoretic perspective on centrality},
Chris@16: //         url = {http://dx.doi.org/10.1016/j.socnet.2005.11.005},
Chris@16: //             volume = {28},
Chris@16: //             year = {2006}
Chris@16: //         }
Chris@16: //     }
Chris@16: 
Chris@16: namespace detail {
Chris@16:     // Note that this assumes T == property_traits<DistanceMap>::value_type
Chris@16:     // and that the args and return of combine are also T.
Chris@16:     template <typename Graph,
Chris@16:                 typename DistanceMap,
Chris@16:                 typename Combinator,
Chris@16:                 typename Distance>
Chris@16:     inline Distance
Chris@16:     combine_distances(const Graph& g,
Chris@16:                         DistanceMap dist,
Chris@16:                         Combinator combine,
Chris@16:                         Distance init)
Chris@16:     {
Chris@16:         BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> ));
Chris@16:         typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
Chris@16:         typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
Chris@16:         BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<DistanceMap,Vertex> ));
Chris@16:         BOOST_CONCEPT_ASSERT(( NumericValueConcept<Distance> ));
Chris@16:         typedef numeric_values<Distance> DistanceNumbers;
Chris@16:         BOOST_CONCEPT_ASSERT(( AdaptableBinaryFunction<Combinator,Distance,Distance,Distance> ));
Chris@16: 
Chris@16:         // If there's ever an infinite distance, then we simply return
Chris@16:         // infinity. Note that this /will/ include the a non-zero
Chris@16:         // distance-to-self in the combined values. However, this is usually
Chris@16:         // zero, so it shouldn't be too problematic.
Chris@16:         Distance ret = init;
Chris@16:         VertexIterator i, end;
Chris@16:         for(boost::tie(i, end) = vertices(g); i != end; ++i) {
Chris@16:             Vertex v = *i;
Chris@16:             if(get(dist, v) != DistanceNumbers::infinity()) {
Chris@16:                 ret = combine(ret, get(dist, v));
Chris@16:             }
Chris@16:             else {
Chris@16:                 ret = DistanceNumbers::infinity();
Chris@16:                 break;
Chris@16:             }
Chris@16:         }
Chris@16:         return ret;
Chris@16:     }
Chris@16: 
Chris@16:     // Similar to std::plus<T>, but maximizes parameters
Chris@16:     // rather than adding them.
Chris@16:     template <typename T>
Chris@16:     struct maximize : public std::binary_function<T, T, T>
Chris@16:     {
Chris@16:         T operator ()(T x, T y) const
Chris@16:         { BOOST_USING_STD_MAX(); return max BOOST_PREVENT_MACRO_SUBSTITUTION (x, y); }
Chris@16:     };
Chris@16: 
Chris@16:     // Another helper, like maximize() to help abstract functional
Chris@16:     // concepts. This is trivially instantiated for builtin numeric
Chris@16:     // types, but should be specialized for those types that have
Chris@16:     // discrete notions of reciprocals.
Chris@16:     template <typename T>
Chris@16:     struct reciprocal : public std::unary_function<T, T>
Chris@16:     {
Chris@16:         typedef std::unary_function<T, T> function_type;
Chris@16:         typedef typename function_type::result_type result_type;
Chris@16:         typedef typename function_type::argument_type argument_type;
Chris@16:         T operator ()(T t)
Chris@16:         { return T(1) / t; }
Chris@16:     };
Chris@16: } /* namespace detail */
Chris@16: 
Chris@16: // This type defines the basic facilities used for computing values
Chris@16: // based on the geodesic distances between vertices. Examples include
Chris@16: // closeness centrality and mean geodesic distance.
Chris@16: template <typename Graph, typename DistanceType, typename ResultType>
Chris@16: struct geodesic_measure
Chris@16: {
Chris@16:     typedef DistanceType distance_type;
Chris@16:     typedef ResultType result_type;
Chris@16:     typedef typename graph_traits<Graph>::vertices_size_type size_type;
Chris@16: 
Chris@16:     typedef numeric_values<distance_type> distance_values;
Chris@16:     typedef numeric_values<result_type> result_values;
Chris@16: 
Chris@16:     static inline distance_type infinite_distance()
Chris@16:     { return distance_values::infinity(); }
Chris@16: 
Chris@16:     static inline result_type infinite_result()
Chris@16:     { return result_values::infinity(); }
Chris@16: 
Chris@16:     static inline result_type zero_result()
Chris@16:     { return result_values::zero(); }
Chris@16: };
Chris@16: 
Chris@16: } /* namespace boost */
Chris@16: 
Chris@16: #endif