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