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 > |
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 > |
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 > |
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 > |
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 > |
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 > |
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 | |