Chris@16: // (C) Copyright 2007-2009 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_ECCENTRICITY_HPP
Chris@16: #define BOOST_GRAPH_ECCENTRICITY_HPP
Chris@16: 
Chris@16: #include <boost/next_prior.hpp>
Chris@16: #include <boost/config.hpp>
Chris@16: #include <boost/graph/detail/geodesic.hpp>
Chris@16: #include <boost/concept/assert.hpp>
Chris@16: 
Chris@16: namespace boost
Chris@16: {
Chris@16: template <typename Graph,
Chris@16:             typename DistanceMap,
Chris@16:             typename Combinator>
Chris@16: inline typename property_traits<DistanceMap>::value_type
Chris@16: eccentricity(const Graph& g, DistanceMap dist, Combinator combine)
Chris@16: {
Chris@16:     BOOST_CONCEPT_ASSERT(( GraphConcept<Graph> ));
Chris@16:     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
Chris@16:     BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<DistanceMap,Vertex> ));
Chris@16:     typedef typename property_traits<DistanceMap>::value_type Distance;
Chris@16: 
Chris@16:     return detail::combine_distances(g, dist, combine, Distance(0));
Chris@16: }
Chris@16: 
Chris@16: template <typename Graph, typename DistanceMap>
Chris@16: inline typename property_traits<DistanceMap>::value_type
Chris@16: eccentricity(const Graph& g, DistanceMap dist)
Chris@16: {
Chris@16:     BOOST_CONCEPT_ASSERT(( GraphConcept<Graph> ));
Chris@16:     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
Chris@16:     BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<DistanceMap,Vertex> ));
Chris@16:     typedef typename property_traits<DistanceMap>::value_type Distance;
Chris@16: 
Chris@16:     return eccentricity(g, dist, detail::maximize<Distance>());
Chris@16: }
Chris@16: 
Chris@16: template <typename Graph, typename DistanceMatrix, typename EccentricityMap>
Chris@16: inline std::pair<typename property_traits<EccentricityMap>::value_type,
Chris@16:                     typename property_traits<EccentricityMap>::value_type>
Chris@16: all_eccentricities(const Graph& g, const DistanceMatrix& dist, EccentricityMap ecc)
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<DistanceMatrix,Vertex> ));
Chris@16:     typedef typename property_traits<DistanceMatrix>::value_type DistanceMap;
Chris@16:     BOOST_CONCEPT_ASSERT(( WritablePropertyMapConcept<EccentricityMap,Vertex> ));
Chris@16:     typedef typename property_traits<EccentricityMap>::value_type Eccentricity;
Chris@16:     BOOST_USING_STD_MIN();
Chris@16:     BOOST_USING_STD_MAX();
Chris@16:     
Chris@16:     Eccentricity
Chris@16:             r = numeric_values<Eccentricity>::infinity(),
Chris@16:             d = numeric_values<Eccentricity>::zero();
Chris@16:     VertexIterator i, end;
Chris@16:     boost::tie(i, end) = vertices(g);
Chris@16:     for(boost::tie(i, end) = vertices(g); i != end; ++i) {
Chris@16:         DistanceMap dm = get(dist, *i);
Chris@16:         Eccentricity e = eccentricity(g, dm);
Chris@16:         put(ecc, *i, e);
Chris@16: 
Chris@16:         // track the radius and diameter at the same time
Chris@16:         r = min BOOST_PREVENT_MACRO_SUBSTITUTION (r, e);
Chris@16:         d = max BOOST_PREVENT_MACRO_SUBSTITUTION (d, e);
Chris@16:     }
Chris@16:     return std::make_pair(r, d);
Chris@16: }
Chris@16: 
Chris@16: template <typename Graph, typename EccentricityMap>
Chris@16: inline std::pair<typename property_traits<EccentricityMap>::value_type,
Chris@16:                     typename property_traits<EccentricityMap>::value_type>
Chris@16: radius_and_diameter(const Graph& g, EccentricityMap ecc)
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<EccentricityMap, Vertex> ));
Chris@16:     typedef typename property_traits<EccentricityMap>::value_type Eccentricity;
Chris@16:     BOOST_USING_STD_MIN();
Chris@16:     BOOST_USING_STD_MAX();
Chris@16: 
Chris@16:     VertexIterator i, end;
Chris@16:     boost::tie(i, end) = vertices(g);
Chris@16:     Eccentricity radius = get(ecc, *i);
Chris@16:     Eccentricity diameter = get(ecc, *i);
Chris@16:     for(i = boost::next(i); i != end; ++i) {
Chris@16:         Eccentricity cur = get(ecc, *i);
Chris@16:         radius = min BOOST_PREVENT_MACRO_SUBSTITUTION (radius, cur);
Chris@16:         diameter = max BOOST_PREVENT_MACRO_SUBSTITUTION (diameter, cur);
Chris@16:     }
Chris@16:     return std::make_pair(radius, diameter);
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: template <typename Graph, typename EccentricityMap>
Chris@16: inline typename property_traits<EccentricityMap>::value_type
Chris@16: radius(const Graph& g, EccentricityMap ecc)
Chris@16: { return radius_and_diameter(g, ecc).first; }
Chris@16: 
Chris@16: 
Chris@16: template <typename Graph, typename EccentricityMap>
Chris@16: inline typename property_traits<EccentricityMap>::value_type
Chris@16: diameter(const Graph& g, EccentricityMap ecc)
Chris@16: { return radius_and_diameter(g, ecc).second; }
Chris@16: 
Chris@16: } /* namespace boost */
Chris@16: 
Chris@16: #endif