]>
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 | { | |
f67539c2 TL |
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) | |
7c673cae | 20 | { |
f67539c2 TL |
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; | |
7c673cae FG |
25 | |
26 | return detail::combine_distances(g, dist, combine, Distance(0)); | |
27 | } | |
28 | ||
f67539c2 TL |
29 | template < typename Graph, typename DistanceMap > |
30 | inline typename property_traits< DistanceMap >::value_type eccentricity( | |
31 | const Graph& g, DistanceMap dist) | |
7c673cae | 32 | { |
f67539c2 TL |
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; | |
7c673cae | 37 | |
f67539c2 | 38 | return eccentricity(g, dist, detail::maximize< Distance >()); |
7c673cae FG |
39 | } |
40 | ||
f67539c2 TL |
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) | |
7c673cae | 46 | { |
f67539c2 TL |
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; | |
7c673cae FG |
57 | BOOST_USING_STD_MIN(); |
58 | BOOST_USING_STD_MAX(); | |
f67539c2 TL |
59 | |
60 | Eccentricity r = numeric_values< Eccentricity >::infinity(), | |
61 | d = numeric_values< Eccentricity >::zero(); | |
7c673cae FG |
62 | VertexIterator i, end; |
63 | boost::tie(i, end) = vertices(g); | |
f67539c2 TL |
64 | for (boost::tie(i, end) = vertices(g); i != end; ++i) |
65 | { | |
7c673cae FG |
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 | |
f67539c2 TL |
71 | r = min BOOST_PREVENT_MACRO_SUBSTITUTION(r, e); |
72 | d = max BOOST_PREVENT_MACRO_SUBSTITUTION(d, e); | |
7c673cae FG |
73 | } |
74 | return std::make_pair(r, d); | |
75 | } | |
76 | ||
f67539c2 TL |
77 | template < typename Graph, typename EccentricityMap > |
78 | inline std::pair< typename property_traits< EccentricityMap >::value_type, | |
79 | typename property_traits< EccentricityMap >::value_type > | |
7c673cae FG |
80 | radius_and_diameter(const Graph& g, EccentricityMap ecc) |
81 | { | |
f67539c2 TL |
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; | |
7c673cae FG |
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); | |
f67539c2 TL |
96 | for (i = boost::next(i); i != end; ++i) |
97 | { | |
7c673cae | 98 | Eccentricity cur = get(ecc, *i); |
f67539c2 TL |
99 | radius = min BOOST_PREVENT_MACRO_SUBSTITUTION(radius, cur); |
100 | diameter = max BOOST_PREVENT_MACRO_SUBSTITUTION(diameter, cur); | |
7c673cae FG |
101 | } |
102 | return std::make_pair(radius, diameter); | |
103 | } | |
104 | ||
f67539c2 TL |
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 | } | |
7c673cae | 111 | |
f67539c2 TL |
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 | } | |
7c673cae FG |
118 | |
119 | } /* namespace boost */ | |
120 | ||
121 | #endif |