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