From: asutton_at_[hidden]
Date: 2007-08-15 08:39:05
Author: asutton
Date: 2007-08-15 08:39:04 EDT (Wed, 15 Aug 2007)
New Revision: 38674
URL: http://svn.boost.org/trac/boost/changeset/38674
Log:
Moved diameter, radius to eccentricity header
Added a radius_and_diameter() function
concept checking in all eccentricity-related functions
Removed:
sandbox/SOC/2007/graphs/boost/graph/diameter.hpp
sandbox/SOC/2007/graphs/boost/graph/radius.hpp
Text files modified:
sandbox/SOC/2007/graphs/boost/graph/detail/geodesic.hpp | 11 +++-
sandbox/SOC/2007/graphs/boost/graph/eccentricity.hpp | 91 +++++++++++++++++++++++++++++++++++++--
sandbox/SOC/2007/graphs/boost/graph/geodesic_distance.hpp | 26 ----------
3 files changed, 95 insertions(+), 33 deletions(-)
Modified: sandbox/SOC/2007/graphs/boost/graph/detail/geodesic.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/detail/geodesic.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/detail/geodesic.hpp 2007-08-15 08:39:04 EDT (Wed, 15 Aug 2007)
@@ -58,13 +58,16 @@
typedef numeric_values<Distance> DistanceNumbers;
function_requires< AdaptableBinaryFunction<Combinator,Distance,Distance,Distance> >();
- // If there's ever an infinite distance, then we simply
- // return infinity.
+ // If there's ever an infinite distance, then we simply return
+ // infinity. Note that this /will/ include the a non-zero
+ // distance-to-self in the combined values. However, this is usually
+ // zero, so it shouldn't be too problematic.
Distance ret = init;
VertexIterator i, end;
for(tie(i, end) = vertices(g); i != end; ++i) {
- if(get(dist, *i) != DistanceNumbers::infinity()) {
- ret = combine(ret, get(dist, *i));
+ Vertex v = *i;
+ if(get(dist, v) != DistanceNumbers::infinity()) {
+ ret = combine(ret, get(dist, v));
}
else {
ret = DistanceNumbers::infinity();
Deleted: sandbox/SOC/2007/graphs/boost/graph/diameter.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/diameter.hpp 2007-08-15 08:39:04 EDT (Wed, 15 Aug 2007)
+++ (empty file)
@@ -1,26 +0,0 @@
-// (C) Copyright Andrew Sutton 2007
-//
-// 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_DIAMETER_HPP
-#define BOOST_GRAPH_DIAMETER_HPP
-
-namespace boost
-{
- template <typename Graph, typename EccentricityMap>
- inline typename property_traits<EccentricityMap>::value_type
- graph_diameter(const Graph& g, EccentricityMap ecc)
- {
- typedef typename property_traits<EccentricityMap>::value_type T;
- typename graph_traits<Graph>::vertex_iterator i, end;
- T ret = ecc[*vertices(g).first];
- for(tie(i, end) = vertices(g); i != end; ++i) {
- ret = std::max(ret, ecc[*i]);
- }
- return ret;
- }
-}
-
-#endif
Modified: sandbox/SOC/2007/graphs/boost/graph/eccentricity.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/eccentricity.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/eccentricity.hpp 2007-08-15 08:39:04 EDT (Wed, 15 Aug 2007)
@@ -7,6 +7,7 @@
#ifndef BOOST_GRAPH_ECCENTRICITY_HPP
#define BOOST_GRAPH_ECCENTRICITY_HPP
+#include <boost/utility.hpp>
#include <boost/graph/detail/geodesic.hpp>
namespace boost
@@ -19,16 +20,23 @@
DistanceMap dist,
Combinator combine)
{
+ function_requires< GraphConcept<Graph> >();
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ function_requires< ReadablePropertyMapConcept<DistanceMap,Vertex> >();
typedef typename property_traits<DistanceMap>::value_type Distance;
- return detail::combine_distances(g, dist, combine,
- Distance(0));
+
+ return detail::combine_distances(g, dist, combine, Distance(0));
}
template <typename Graph, typename DistanceMap>
inline typename property_traits<DistanceMap>::value_type
vertex_eccentricity(const Graph& g, DistanceMap dist)
{
+ function_requires< GraphConcept<Graph> >();
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ function_requires< ReadablePropertyMapConcept<DistanceMap,Vertex> >();
typedef typename property_traits<DistanceMap>::value_type Distance;
+
return vertex_eccentricity(g, dist, detail::maximize<Distance>());
}
@@ -36,13 +44,86 @@
inline void
eccentricity(const Graph& g, const DistanceMatrix& dist, EccentricityMap ecc)
{
+ function_requires< VertexListGraphConcept<Graph> >();
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
+ function_requires< ReadablePropertyMapConcept<DistanceMatrix,Vertex> >();
typedef typename property_traits<DistanceMatrix>::value_type DistanceMap;
- typedef typename property_traits<DistanceMap>::value_type Distance;
+ function_requires< WritablePropertyMapConcept<EccentricityMap,Vertex> >();
+ typedef typename property_traits<EccentricityMap>::value_type Eccentricity;
- typename graph_traits<Graph>::vertex_iterator i, end;
+ VertexIterator i, end;
for(tie(i, end) = vertices(g); i != end; ++i) {
- ecc[*i] = vertex_eccentricity(g, DistanceMap(dist[*i]));
+ DistanceMap dm = get(dist, *i);
+ Eccentricity e = vertex_eccentricity(g, dm);
+ put(ecc, *i, e);
+ }
+ }
+
+
+ template <typename Graph, typename EccentricityMap>
+ inline typename property_traits<EccentricityMap>::value_type
+ graph_radius(const Graph& g, EccentricityMap ecc)
+ {
+ function_requires< VertexListGraphConcept<Graph> >();
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
+ function_requires< ReadablePropertyMapConcept<EccentricityMap, Vertex> >();
+ typedef typename property_traits<EccentricityMap>::value_type Eccentricity;
+
+ VertexIterator i, end;
+ tie(i, end) = vertices(g);
+ Eccentricity ret = get(ecc, *i);
+ for(i = next(i); i != end; ++i) {
+ Eccentricity cur = get(ecc, *i);
+ ret = std::min(ret, cur);
+ }
+ return ret;
+ }
+
+
+ template <typename Graph, typename EccentricityMap>
+ inline typename property_traits<EccentricityMap>::value_type
+ graph_diameter(const Graph& g, EccentricityMap ecc)
+ {
+ function_requires< VertexListGraphConcept<Graph> >();
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
+ function_requires< ReadablePropertyMapConcept<EccentricityMap, Vertex> >();
+ typedef typename property_traits<EccentricityMap>::value_type Eccentricity;
+
+ VertexIterator i, end;
+ tie(i, end) = vertices(g);
+ Eccentricity ret = get(ecc, *i);
+ for(i = next(i); i != end; ++i) {
+ Eccentricity cur = get(ecc, *i);
+ ret = std::max(ret, cur);
+ }
+ return ret;
+ }
+
+
+ template <typename Graph, typename EccentricityMap>
+ inline std::pair<typename property_traits<EccentricityMap>::value_type,
+ typename property_traits<EccentricityMap>::value_type>
+ graph_radius_and_diameter(const Graph& g, EccentricityMap ecc)
+ {
+ function_requires< VertexListGraphConcept<Graph> >();
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
+ function_requires< ReadablePropertyMapConcept<EccentricityMap, Vertex> >();
+ typedef typename property_traits<EccentricityMap>::value_type Eccentricity;
+
+ VertexIterator i, end;
+ tie(i, end) = vertices(g);
+ Eccentricity radius = get(ecc, *i);
+ Eccentricity diameter = get(ecc, *i);
+ for(i = next(i); i != end; ++i) {
+ Eccentricity cur = get(ecc, *i);
+ radius = std::min(radius, cur);
+ diameter = std::max(diameter, cur);
}
+ return std::make_pair(radius, diameter);
}
}
Modified: sandbox/SOC/2007/graphs/boost/graph/geodesic_distance.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/geodesic_distance.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/geodesic_distance.hpp 2007-08-15 08:39:04 EDT (Wed, 15 Aug 2007)
@@ -34,7 +34,7 @@
return
(d == base_type::infinite_distance()) ?
base_type::infinite_result() :
- div(result_type(d), result_type(num_vertices(g)));
+ div(result_type(d), result_type(num_vertices(g) - 1));
}
Divides div;
};
@@ -53,7 +53,6 @@
return mean_geodesic_measure<Graph, typename property_traits<DistanceMap>::value_type, T>();
}
-
// This is a little different because it's expected that the result type
// should (must?) be the same as the distance type. There's a type of
// transitivity in this thinking... If the average of distances has type
@@ -68,38 +67,17 @@
typedef geodesic_measure<Graph, DistanceType, DistanceType> base_type;
typedef typename base_type::distance_type distance_type;
typedef typename base_type::result_type result_type;
- typedef typename base_type::size_type size_type;
inline result_type operator ()(distance_type d, const Graph& g)
{
function_requires< VertexListGraphConcept<Graph> >();
- typename graph_traits<Graph>::directed_category cat;
function_requires< NumericValueConcept<DistanceType> >();
- return this->average(d, num_vertices(g), cat);
- }
-
- private:
- inline result_type
- average(distance_type d, size_type n, undirected_tag)
- {
- if(d == base_type::infinite_distance()) {
- return base_type::infinite_result();
- }
- else {
- result_type f = (result_type(n) + 1) / result_type(2);
- return d / f;
- }
- }
-
- inline result_type
- average(distance_type d, size_type n, directed_tag)
- {
if(d == base_type::infinite_distance()) {
return base_type::infinite_result();
}
else {
- return result_type(d) / result_type(n);
+ return d / result_type(num_vertices(g));
}
}
};
Deleted: sandbox/SOC/2007/graphs/boost/graph/radius.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/radius.hpp 2007-08-15 08:39:04 EDT (Wed, 15 Aug 2007)
+++ (empty file)
@@ -1,26 +0,0 @@
-// (C) Copyright Andrew Sutton 2007
-//
-// 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_RADIUS_HPP
-#define BOOST_GRAPH_RADIUS_HPP
-
-namespace boost
-{
- template <typename Graph, typename EccentricityMap>
- inline typename property_traits<EccentricityMap>::value_type
- graph_radius(const Graph& g, EccentricityMap ecc)
- {
- typedef typename property_traits<EccentricityMap>::value_type T;
- typename graph_traits<Graph>::vertex_iterator i, end;
- T ret = ecc[*vertices(g).first];
- for(tie(i, end) = vertices(g); i != end; ++i) {
- ret = std::min(ret, ecc[*i]);
- }
- return ret;
- }
-}
-
-#endif