boost/graph/eccentricity.hpp

0001 // (C) Copyright 2007-2009 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_ECCENTRICITY_HPP
0008 #define BOOST_GRAPH_ECCENTRICITY_HPP
0009
0010 #include <boost/next_prior.hpp>
0011 #include <boost/config.hpp>
0012 #include <boost/graph/detail/geodesic.hpp>
0013 #include <boost/concept/assert.hpp>
0014
0015 namespace boost
0016 {
0017 template < typename Graph, typename DistanceMap, typename Combinator >
0018 inline typename property_traits< DistanceMap >::value_type eccentricity(
0019     const Graph& g, DistanceMap dist, Combinator combine)
0020 {
0021     BOOST_CONCEPT_ASSERT((GraphConcept< Graph >));
0022     typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0023     BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept< DistanceMap, Vertex >));
0024     typedef typename property_traits< DistanceMap >::value_type Distance;
0025
0026     return detail::combine_distances(g, dist, combine, Distance(0));
0027 }
0028
0029 template < typename Graph, typename DistanceMap >
0030 inline typename property_traits< DistanceMap >::value_type eccentricity(
0031     const Graph& g, DistanceMap dist)
0032 {
0033     BOOST_CONCEPT_ASSERT((GraphConcept< Graph >));
0034     typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0035     BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept< DistanceMap, Vertex >));
0036     typedef typename property_traits< DistanceMap >::value_type Distance;
0037
0038     return eccentricity(g, dist, detail::maximize< Distance >());
0039 }
0040
0041 template < typename Graph, typename DistanceMatrix, typename EccentricityMap >
0042 inline std::pair< typename property_traits< EccentricityMap >::value_type,
0043     typename property_traits< EccentricityMap >::value_type >
0044 all_eccentricities(
0045     const Graph& g, const DistanceMatrix& dist, EccentricityMap ecc)
0046 {
0047     BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >));
0048     typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0049     typedef typename graph_traits< Graph >::vertex_iterator VertexIterator;
0050     BOOST_CONCEPT_ASSERT(
0051         (ReadablePropertyMapConcept< DistanceMatrix, Vertex >));
0052     typedef typename property_traits< DistanceMatrix >::value_type DistanceMap;
0053     BOOST_CONCEPT_ASSERT(
0054         (WritablePropertyMapConcept< EccentricityMap, Vertex >));
0055     typedef
0056         typename property_traits< EccentricityMap >::value_type Eccentricity;
0057     BOOST_USING_STD_MIN();
0058     BOOST_USING_STD_MAX();
0059
0060     Eccentricity r = numeric_values< Eccentricity >::infinity(),
0061                  d = numeric_values< Eccentricity >::zero();
0062     VertexIterator i, end;
0063     boost::tie(i, end) = vertices(g);
0064     for (boost::tie(i, end) = vertices(g); i != end; ++i)
0065     {
0066         DistanceMap dm = get(dist, *i);
0067         Eccentricity e = eccentricity(g, dm);
0068         put(ecc, *i, e);
0069
0070         // track the radius and diameter at the same time
0071         r = min BOOST_PREVENT_MACRO_SUBSTITUTION(r, e);
0072         d = max BOOST_PREVENT_MACRO_SUBSTITUTION(d, e);
0073     }
0074     return std::make_pair(r, d);
0075 }
0076
0077 template < typename Graph, typename EccentricityMap >
0078 inline std::pair< typename property_traits< EccentricityMap >::value_type,
0079     typename property_traits< EccentricityMap >::value_type >
0080 radius_and_diameter(const Graph& g, EccentricityMap ecc)
0081 {
0082     BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >));
0083     typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0084     typedef typename graph_traits< Graph >::vertex_iterator VertexIterator;
0085     BOOST_CONCEPT_ASSERT(
0086         (ReadablePropertyMapConcept< EccentricityMap, Vertex >));
0087     typedef
0088         typename property_traits< EccentricityMap >::value_type Eccentricity;
0089     BOOST_USING_STD_MIN();
0090     BOOST_USING_STD_MAX();
0091
0092     VertexIterator i, end;
0093     boost::tie(i, end) = vertices(g);
0094     Eccentricity radius = get(ecc, *i);
0095     Eccentricity diameter = get(ecc, *i);
0096     for (i = boost::next(i); i != end; ++i)
0097     {
0098         Eccentricity cur = get(ecc, *i);
0099         radius = min BOOST_PREVENT_MACRO_SUBSTITUTION(radius, cur);
0100         diameter = max BOOST_PREVENT_MACRO_SUBSTITUTION(diameter, cur);
0101     }
0102     return std::make_pair(radius, diameter);
0103 }
0104
0105 template < typename Graph, typename EccentricityMap >
0106 inline typename property_traits< EccentricityMap >::value_type radius(
0107     const Graph& g, EccentricityMap ecc)
0108 {
0109     return radius_and_diameter(g, ecc).first;
0110 }
0111
0112 template < typename Graph, typename EccentricityMap >
0113 inline typename property_traits< EccentricityMap >::value_type diameter(
0114     const Graph& g, EccentricityMap ecc)
0115 {
0116     return radius_and_diameter(g, ecc).second;
0117 }
0118
0119 } /* namespace boost */
0120
0121 #endif