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
15 namespace boost
16 {
17 template < typename Graph, typename DistanceMap, typename Combinator >
eccentricity(const Graph & g,DistanceMap dist,Combinator combine)18 inline 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
29 template < typename Graph, typename DistanceMap >
eccentricity(const Graph & g,DistanceMap dist)30 inline 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
41 template < typename Graph, typename DistanceMatrix, typename EccentricityMap >
42 inline std::pair< typename property_traits< EccentricityMap >::value_type,
43 typename property_traits< EccentricityMap >::value_type >
all_eccentricities(const Graph & g,const DistanceMatrix & dist,EccentricityMap ecc)44 all_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
77 template < typename Graph, typename EccentricityMap >
78 inline std::pair< typename property_traits< EccentricityMap >::value_type,
79 typename property_traits< EccentricityMap >::value_type >
radius_and_diameter(const Graph & g,EccentricityMap ecc)80 radius_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
105 template < typename Graph, typename EccentricityMap >
radius(const Graph & g,EccentricityMap ecc)106 inline typename property_traits< EccentricityMap >::value_type radius(
107 const Graph& g, EccentricityMap ecc)
108 {
109 return radius_and_diameter(g, ecc).first;
110 }
111
112 template < typename Graph, typename EccentricityMap >
diameter(const Graph & g,EccentricityMap ecc)113 inline 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