boost/graph/geodesic_distance.hpp

0001 // (C) Copyright Andrew Sutton 2007
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_GEODESIC_DISTANCE_HPP
0008 #define BOOST_GRAPH_GEODESIC_DISTANCE_HPP
0009
0010 #include <boost/graph/detail/geodesic.hpp>
0011 #include <boost/graph/exterior_property.hpp>
0012 #include <boost/concept/assert.hpp>
0013
0014 namespace boost
0015 {
0016 template < typename Graph, typename DistanceType, typename ResultType,
0017     typename Divides = std::divides< ResultType > >
0018 struct mean_geodesic_measure
0019 : public geodesic_measure< Graph, DistanceType, ResultType >
0020 {
0021     typedef geodesic_measure< Graph, DistanceType, ResultType > base_type;
0022     typedef typename base_type::distance_type distance_type;
0023     typedef typename base_type::result_type result_type;
0024
0025     result_type operator()(distance_type d, const Graph& g)
0026     {
0027         BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >));
0028         BOOST_CONCEPT_ASSERT((NumericValueConcept< DistanceType >));
0029         BOOST_CONCEPT_ASSERT((NumericValueConcept< ResultType >));
0030 //      NOTE: Disabled until this concept assert is fixed in Boost.ConceptCheck.
0031 //         BOOST_CONCEPT_ASSERT((AdaptableBinaryFunctionConcept< Divides,
0032 //             ResultType, ResultType, ResultType >));
0033
0034         return (d == base_type::infinite_distance())
0035             ? base_type::infinite_result()
0036             : div(result_type(d), result_type(num_vertices(g) - 1));
0037     }
0038     Divides div;
0039 };
0040
0041 template < typename Graph, typename DistanceMap >
0042 inline mean_geodesic_measure< Graph,
0043     typename property_traits< DistanceMap >::value_type, double >
0044 measure_mean_geodesic(const Graph&, DistanceMap)
0045 {
0046     return mean_geodesic_measure< Graph,
0047         typename property_traits< DistanceMap >::value_type, double >();
0048 }
0049
0050 template < typename T, typename Graph, typename DistanceMap >
0051 inline mean_geodesic_measure< Graph,
0052     typename property_traits< DistanceMap >::value_type, T >
0053 measure_mean_geodesic(const Graph&, DistanceMap)
0054 {
0055     return mean_geodesic_measure< Graph,
0056         typename property_traits< DistanceMap >::value_type, T >();
0057 }
0058
0059 // This is a little different because it's expected that the result type
0060 // should (must?) be the same as the distance type. There's a type of
0061 // transitivity in this thinking... If the average of distances has type
0062 // X then the average of x's should also be type X. Is there a case where this
0063 // is not true?
0064 //
0065 // This type is a little under-genericized... It needs generic parameters
0066 // for addition and division.
0067 template < typename Graph, typename DistanceType >
0068 struct mean_graph_distance_measure
0069 : public geodesic_measure< Graph, DistanceType, DistanceType >
0070 {
0071     typedef geodesic_measure< Graph, DistanceType, DistanceType > base_type;
0072     typedef typename base_type::distance_type distance_type;
0073     typedef typename base_type::result_type result_type;
0074
0075     inline result_type operator()(distance_type d, const Graph& g)
0076     {
0077         BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >));
0078         BOOST_CONCEPT_ASSERT((NumericValueConcept< DistanceType >));
0079
0080         if (d == base_type::infinite_distance())
0081         {
0082             return base_type::infinite_result();
0083         }
0084         else
0085         {
0086             return d / result_type(num_vertices(g));
0087         }
0088     }
0089 };
0090
0091 template < typename Graph, typename DistanceMap >
0092 inline mean_graph_distance_measure< Graph,
0093     typename property_traits< DistanceMap >::value_type >
0094 measure_graph_mean_geodesic(const Graph&, DistanceMap)
0095 {
0096     typedef typename property_traits< DistanceMap >::value_type T;
0097     return mean_graph_distance_measure< Graph, T >();
0098 }
0099
0100 template < typename Graph, typename DistanceMap, typename Measure,
0101     typename Combinator >
0102 inline typename Measure::result_type mean_geodesic(
0103     const Graph& g, DistanceMap dist, Measure measure, Combinator combine)
0104 {
0105     BOOST_CONCEPT_ASSERT((DistanceMeasureConcept< Measure, Graph >));
0106     typedef typename Measure::distance_type Distance;
0107
0108     Distance n = detail::combine_distances(g, dist, combine, Distance(0));
0109     return measure(n, g);
0110 }
0111
0112 template < typename Graph, typename DistanceMap, typename Measure >
0113 inline typename Measure::result_type mean_geodesic(
0114     const Graph& g, DistanceMap dist, Measure measure)
0115 {
0116     BOOST_CONCEPT_ASSERT((DistanceMeasureConcept< Measure, Graph >));
0117     typedef typename Measure::distance_type Distance;
0118
0119     return mean_geodesic(g, dist, measure, std::plus< Distance >());
0120 }
0121
0122 template < typename Graph, typename DistanceMap >
0123 inline double mean_geodesic(const Graph& g, DistanceMap dist)
0124 {
0125     return mean_geodesic(g, dist, measure_mean_geodesic(g, dist));
0126 }
0127
0128 template < typename T, typename Graph, typename DistanceMap >
0129 inline T mean_geodesic(const Graph& g, DistanceMap dist)
0130 {
0131     return mean_geodesic(g, dist, measure_mean_geodesic< T >(g, dist));
0132 }
0133
0134 template < typename Graph, typename DistanceMatrixMap, typename GeodesicMap,
0135     typename Measure >
0136 inline typename property_traits< GeodesicMap >::value_type all_mean_geodesics(
0137     const Graph& g, DistanceMatrixMap dist, GeodesicMap geo, Measure measure)
0138 {
0139     BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >));
0140     typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0141     typedef typename graph_traits< Graph >::vertex_iterator VertexIterator;
0142     BOOST_CONCEPT_ASSERT(
0143         (ReadablePropertyMapConcept< DistanceMatrixMap, Vertex >));
0144     typedef
0145         typename property_traits< DistanceMatrixMap >::value_type DistanceMap;
0146     BOOST_CONCEPT_ASSERT((DistanceMeasureConcept< Measure, Graph >));
0147     typedef typename Measure::result_type Result;
0148     BOOST_CONCEPT_ASSERT((WritablePropertyMapConcept< GeodesicMap, Vertex >));
0149     BOOST_CONCEPT_ASSERT((NumericValueConcept< Result >));
0150
0151     // NOTE: We could compute the mean geodesic here by performing additional
0152     // computations (i.e., adding and dividing). However, I don't really feel
0153     // like fully genericizing the entire operation yet so I'm not going to.
0154
0155     Result inf = numeric_values< Result >::infinity();
0156     Result sum = numeric_values< Result >::zero();
0157     VertexIterator i, end;
0158     for (boost::tie(i, end) = vertices(g); i != end; ++i)
0159     {
0160         DistanceMap dm = get(dist, *i);
0161         Result r = mean_geodesic(g, dm, measure);
0162         put(geo, *i, r);
0163
0164         // compute the sum along with geodesics
0165         if (r == inf)
0166         {
0167             sum = inf;
0168         }
0169         else if (sum != inf)
0170         {
0171             sum += r;
0172         }
0173     }
0174
0175     // return the average of averages.
0176     return sum / Result(num_vertices(g));
0177 }
0178
0179 template < typename Graph, typename DistanceMatrixMap, typename GeodesicMap >
0180 inline typename property_traits< GeodesicMap >::value_type all_mean_geodesics(
0181     const Graph& g, DistanceMatrixMap dist, GeodesicMap geo)
0182 {
0183     BOOST_CONCEPT_ASSERT((GraphConcept< Graph >));
0184     typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0185     BOOST_CONCEPT_ASSERT(
0186         (ReadablePropertyMapConcept< DistanceMatrixMap, Vertex >));
0187     typedef
0188         typename property_traits< DistanceMatrixMap >::value_type DistanceMap;
0189     BOOST_CONCEPT_ASSERT((WritablePropertyMapConcept< GeodesicMap, Vertex >));
0190     typedef typename property_traits< GeodesicMap >::value_type Result;
0191
0192     return all_mean_geodesics(
0193         g, dist, geo, measure_mean_geodesic< Result >(g, DistanceMap()));
0194 }
0195
0196 template < typename Graph, typename GeodesicMap, typename Measure >
0197 inline typename Measure::result_type small_world_distance(
0198     const Graph& g, GeodesicMap geo, Measure measure)
0199 {
0200     BOOST_CONCEPT_ASSERT((DistanceMeasureConcept< Measure, Graph >));
0201     typedef typename Measure::result_type Result;
0202
0203     Result sum
0204         = detail::combine_distances(g, geo, std::plus< Result >(), Result(0));
0205     return measure(sum, g);
0206 }
0207
0208 template < typename Graph, typename GeodesicMap >
0209 inline typename property_traits< GeodesicMap >::value_type small_world_distance(
0210     const Graph& g, GeodesicMap geo)
0211 {
0212     return small_world_distance(g, geo, measure_graph_mean_geodesic(g, geo));
0213 }
0214
0215 }
0216
0217 #endif