1// (C) Copyright 2007-2009 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_ECCENTRICITY_HPP
8#define BOOST_GRAPH_ECCENTRICITY_HPP
9
10#include <boost/next_prior.hpp>
11#include <boost/config.hpp>
12#include <boost/graph/detail/geodesic.hpp>
13#include <boost/concept/assert.hpp>
14
15namespace boost
16{
17template < typename Graph, typename DistanceMap, typename Combinator >
18inline typename property_traits< DistanceMap >::value_type eccentricity(
19 const Graph& g, DistanceMap dist, Combinator combine)
20{
21 BOOST_CONCEPT_ASSERT((GraphConcept< Graph >));
22 typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
23 BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept< DistanceMap, Vertex >));
24 typedef typename property_traits< DistanceMap >::value_type Distance;
25
26 return detail::combine_distances(g, dist, combine, Distance(0));
27}
28
29template < typename Graph, typename DistanceMap >
30inline typename property_traits< DistanceMap >::value_type eccentricity(
31 const Graph& g, DistanceMap dist)
32{
33 BOOST_CONCEPT_ASSERT((GraphConcept< Graph >));
34 typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
35 BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept< DistanceMap, Vertex >));
36 typedef typename property_traits< DistanceMap >::value_type Distance;
37
38 return eccentricity(g, dist, detail::maximize< Distance >());
39}
40
41template < typename Graph, typename DistanceMatrix, typename EccentricityMap >
42inline std::pair< typename property_traits< EccentricityMap >::value_type,
43 typename property_traits< EccentricityMap >::value_type >
44all_eccentricities(
45 const Graph& g, const DistanceMatrix& dist, EccentricityMap ecc)
46{
47 BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >));
48 typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
49 typedef typename graph_traits< Graph >::vertex_iterator VertexIterator;
50 BOOST_CONCEPT_ASSERT(
51 (ReadablePropertyMapConcept< DistanceMatrix, Vertex >));
52 typedef typename property_traits< DistanceMatrix >::value_type DistanceMap;
53 BOOST_CONCEPT_ASSERT(
54 (WritablePropertyMapConcept< EccentricityMap, Vertex >));
55 typedef
56 typename property_traits< EccentricityMap >::value_type Eccentricity;
57 BOOST_USING_STD_MIN();
58 BOOST_USING_STD_MAX();
59
60 Eccentricity r = numeric_values< Eccentricity >::infinity(),
61 d = numeric_values< Eccentricity >::zero();
62 VertexIterator i, end;
63 boost::tie(i, end) = vertices(g);
64 for (boost::tie(i, end) = vertices(g); i != end; ++i)
65 {
66 DistanceMap dm = get(dist, *i);
67 Eccentricity e = eccentricity(g, dm);
68 put(ecc, *i, e);
69
70 // track the radius and diameter at the same time
71 r = min BOOST_PREVENT_MACRO_SUBSTITUTION(r, e);
72 d = max BOOST_PREVENT_MACRO_SUBSTITUTION(d, e);
73 }
74 return std::make_pair(r, d);
75}
76
77template < typename Graph, typename EccentricityMap >
78inline std::pair< typename property_traits< EccentricityMap >::value_type,
79 typename property_traits< EccentricityMap >::value_type >
80radius_and_diameter(const Graph& g, EccentricityMap ecc)
81{
82 BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >));
83 typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
84 typedef typename graph_traits< Graph >::vertex_iterator VertexIterator;
85 BOOST_CONCEPT_ASSERT(
86 (ReadablePropertyMapConcept< EccentricityMap, Vertex >));
87 typedef
88 typename property_traits< EccentricityMap >::value_type Eccentricity;
89 BOOST_USING_STD_MIN();
90 BOOST_USING_STD_MAX();
91
92 VertexIterator i, end;
93 boost::tie(i, end) = vertices(g);
94 Eccentricity radius = get(ecc, *i);
95 Eccentricity diameter = get(ecc, *i);
96 for (i = boost::next(i); i != end; ++i)
97 {
98 Eccentricity cur = get(ecc, *i);
99 radius = min BOOST_PREVENT_MACRO_SUBSTITUTION(radius, cur);
100 diameter = max BOOST_PREVENT_MACRO_SUBSTITUTION(diameter, cur);
101 }
102 return std::make_pair(radius, diameter);
103}
104
105template < typename Graph, typename EccentricityMap >
106inline typename property_traits< EccentricityMap >::value_type radius(
107 const Graph& g, EccentricityMap ecc)
108{
109 return radius_and_diameter(g, ecc).first;
110}
111
112template < typename Graph, typename EccentricityMap >
113inline typename property_traits< EccentricityMap >::value_type diameter(
114 const Graph& g, EccentricityMap ecc)
115{
116 return radius_and_diameter(g, ecc).second;
117}
118
119} /* namespace boost */
120
121#endif
122

source code of boost/libs/graph/include/boost/graph/eccentricity.hpp