From: asutton_at_[hidden]
Date: 2007-07-30 08:31:11
Author: asutton
Date: 2007-07-30 08:31:11 EDT (Mon, 30 Jul 2007)
New Revision: 7589
URL: http://svn.boost.org/trac/boost/changeset/7589
Log:
Renamed geodesic file to closeness centrality
Finished implementing all distance/closeenss measures
Added property_matrix_traits to exterior property header
Added some missing files that support closeness centrality
Added:
sandbox/SOC/2007/graphs/boost/graph/closeness_centrality.hpp (contents, props changed)
sandbox/SOC/2007/graphs/boost/graph/detail/combine_distances.hpp (contents, props changed)
sandbox/SOC/2007/graphs/boost/graph/eccentricity.hpp (contents, props changed)
sandbox/SOC/2007/graphs/boost/graph/numeric_values.hpp (contents, props changed)
Text files modified:
sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp | 12 +++++++++++-
1 files changed, 11 insertions(+), 1 deletions(-)
Added: sandbox/SOC/2007/graphs/boost/graph/closeness_centrality.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/boost/graph/closeness_centrality.hpp 2007-07-30 08:31:11 EDT (Mon, 30 Jul 2007)
@@ -0,0 +1,348 @@
+// (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_GEODESIC_HPP
+#define BOOST_GRAPH_GEODESIC_HPP
+
+#include <limits>
+
+#include <boost/graph/named_parameters.hpp>
+#include <boost/graph/numeric_values.hpp>
+#include <boost/graph/detail/combine_distances.hpp>
+#include <boost/graph/exterior_property.hpp>
+
+namespace boost
+{
+ template <typename Graph,
+ typename DistanceType,
+ typename ResultType>
+ struct closeness_centrality_measure
+ {
+ typedef DistanceType distance_type;
+ typedef ResultType result_type;
+ typedef typename graph_traits<Graph>::vertices_size_type size_type;
+
+ typedef numeric_values<distance_type> distance_values;
+ typedef numeric_values<result_type> result_values;
+
+ static inline distance_type infinite_distance()
+ { return distance_values::infinity(); }
+
+ static inline result_type infinite_result()
+ { return result_values::infinity(); }
+
+ static inline result_type zero_result()
+ { return result_values::zero(); }
+ };
+
+ template <typename Graph,
+ typename DistanceNumbers,
+ typename ResultNumbers>
+ struct total_geodesic_measure
+ : public closeness_centrality_measure<Graph, DistanceNumbers, ResultNumbers>
+ {
+ typedef closeness_centrality_measure<
+ Graph, DistanceNumbers, ResultNumbers
+ > 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;
+
+ result_type operator ()(distance_type d, size_type n)
+ { return d; }
+ };
+
+ template <typename Graph, typename DistanceMap>
+ inline total_geodesic_measure<Graph, typename property_traits<DistanceMap>::value_type, float>
+ measure_total_geodesic(const Graph&, DistanceMap)
+ {
+ return total_geodesic_measure<Graph, typename property_traits<DistanceMap>::value_type, float>();
+ }
+
+ template <typename T, typename Graph, typename DistanceMap>
+ inline total_geodesic_measure<Graph, typename property_traits<DistanceMap>::value_type, T>
+ measure_total_geodesic(const Graph&, DistanceMap)
+ {
+ return total_geodesic_measure<Graph, typename property_traits<DistanceMap>::value_type, T>();
+ }
+
+ template <typename Graph,
+ typename DistanceNumbers,
+ typename ResultNumbers>
+ struct mean_geodesic_measure
+ : public closeness_centrality_measure<Graph, DistanceNumbers, ResultNumbers>
+ {
+ typedef closeness_centrality_measure<
+ Graph, DistanceNumbers, ResultNumbers
+ > 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;
+
+ result_type operator ()(distance_type d, size_type n)
+ {
+ typedef result_type T;
+ return
+ (d == base_type::infinite_distance()) ?
+ base_type::infinite_result() : T(d) / T(n);
+ }
+ };
+
+ template <typename Graph, typename DistanceMap>
+ inline mean_geodesic_measure<Graph, typename property_traits<DistanceMap>::value_type, float>
+ measure_mean_geodesic(const Graph&, DistanceMap)
+ {
+ return mean_geodesic_measure<Graph, typename property_traits<DistanceMap>::value_type, float>();
+ }
+
+ template <typename T, typename Graph, typename DistanceMap>
+ inline mean_geodesic_measure<Graph, typename property_traits<DistanceMap>::value_type, T>
+ measure_mean_geodesic(const Graph&, DistanceMap)
+ {
+ return mean_geodesic_measure<Graph, typename property_traits<DistanceMap>::value_type, T>();
+ }
+
+
+ template <typename Graph,
+ typename DistanceNumbers,
+ typename ResultNumbers>
+ struct inverse_geodesic_measure
+ : public closeness_centrality_measure<Graph, DistanceNumbers, ResultNumbers>
+ {
+ typedef closeness_centrality_measure<
+ Graph, DistanceNumbers, ResultNumbers
+ > 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;
+
+ result_type operator ()(distance_type d, size_type n)
+ {
+ typedef result_type T;
+ return
+ (d == base_type::infinite_distance()) ?
+ base_type::zero_result() : T(n) / T(d);
+ }
+ };
+
+ template <typename Graph, typename DistanceMap>
+ inline inverse_geodesic_measure<Graph, typename property_traits<DistanceMap>::value_type, float>
+ measure_inverse_geodesic(const Graph&, DistanceMap)
+ {
+ return inverse_geodesic_measure<Graph, typename property_traits<DistanceMap>::value_type, float>();
+ }
+
+ template <typename T, typename Graph, typename DistanceMap>
+ inline inverse_geodesic_measure<Graph, typename property_traits<DistanceMap>::value_type, T>
+ measure_inverse_geodesic(const Graph&, DistanceMap)
+ {
+ return inverse_geodesic_measure<Graph, typename property_traits<DistanceMap>::value_type, T>();
+ }
+
+
+ template <typename Graph,
+ typename DistanceNumbers,
+ typename ResultNumbers>
+ struct closeness_measure
+ : public closeness_centrality_measure<Graph, DistanceNumbers, ResultNumbers>
+ {
+ typedef closeness_centrality_measure<
+ Graph, DistanceNumbers, ResultNumbers
+ > 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;
+
+ result_type operator ()(distance_type d, size_type n)
+ {
+ typedef result_type T;
+ return
+ (d == base_type::infinite_distance()) ?
+ base_type::zero_result() : T(1) / T(d);
+ }
+ };
+
+ template <typename Graph, typename DistanceMap>
+ inline closeness_measure<Graph, typename property_traits<DistanceMap>::value_type, float>
+ measure_closeness(const Graph&, DistanceMap)
+ {
+ return closeness_measure<Graph, typename property_traits<DistanceMap>::value_type, float>();
+ }
+
+ template <typename T, typename Graph, typename DistanceMap>
+ inline closeness_measure<Graph, typename property_traits<DistanceMap>::value_type, T>
+ measure_closeness(const Graph&, DistanceMap)
+ {
+ return closeness_measure<Graph, typename property_traits<DistanceMap>::value_type, T>();
+ }
+
+
+ template <typename Graph,
+ typename DistanceMap,
+ typename Measure,
+ typename Combinator>
+ inline typename Measure::result_type
+ closeness_centrality(const Graph& g,
+ DistanceMap dist,
+ Measure measure,
+ Combinator combine)
+ {
+ typedef typename Measure::distance_type Distance;
+ typedef typename Measure::distance_values DistanceValues;
+ Distance n = detail::combine_distances(g, dist, combine,
+ DistanceValues());
+ return measure(n, num_vertices(g));
+ }
+
+
+ template <typename Graph,
+ typename DistanceMap,
+ typename Measure>
+ inline typename Measure::result_type
+ closeness_centrality(const Graph& g,
+ DistanceMap dist,
+ Measure measure)
+ {
+ typedef typename Measure::distance_type Distance;
+ return closeness_centrality(g, dist, measure, std::plus<Distance>());
+ }
+
+ template <typename Graph, typename DistanceMap>
+ inline float
+ total_geodesic_distance(const Graph& g, DistanceMap dist)
+ {
+ return closeness_centrality(g, dist, measure_total_geodesic(g, dist));
+ }
+
+ template <typename T, typename Graph, typename DistanceMap>
+ inline T
+ total_geodesic_distance(const Graph& g, DistanceMap dist)
+ {
+ return closeness_centrality(g, dist, measure_total_geodesic<T>(g, dist));
+ }
+
+ template <typename Graph, typename DistanceMap>
+ inline float
+ mean_geodesic_distance(const Graph& g, DistanceMap dist)
+ {
+ return closeness_centrality(g, dist, measure_mean_geodesic(g, dist));
+ }
+
+ template <typename T, typename Graph, typename DistanceMap>
+ inline T
+ mean_geodesic_distance(const Graph& g, DistanceMap dist)
+ {
+ return closeness_centrality(g, dist, measure_mean_geodesic<T>(g, dist));
+ }
+
+ template <typename Graph, typename DistanceMap>
+ inline float
+ inverse_geodesic_distance(const Graph& g, DistanceMap dist)
+ {
+ return closeness_centrality(g, dist, measure_inverse_geodesic(g, dist));
+ }
+
+ template <typename T, typename Graph, typename DistanceMap>
+ inline T
+ inverse_geodesic_distance(const Graph& g, DistanceMap dist)
+ {
+ return closeness_centrality(g, dist, measure_inverse_geodesic<T>(g, dist));
+ }
+
+ template <typename Graph, typename DistanceMap>
+ inline float
+ closeness(const Graph& g, DistanceMap dist)
+ {
+ return closeness_centrality(g, dist, measure_closeness(g, dist));
+ }
+
+ template <typename T, typename Graph, typename DistanceMap>
+ inline T
+ closeness(const Graph& g, DistanceMap dist)
+ {
+ return closeness_centrality(g, dist, measure_closeness<T>(g, dist));
+ }
+
+ template <typename Graph,
+ typename DistanceMatrix,
+ typename ClosenessMap,
+ typename Measure>
+ inline void
+ all_closeness_centralities(const Graph& g,
+ DistanceMatrix& matrix,
+ ClosenessMap& close,
+ Measure measure)
+ {
+ typedef typename property_matrix_traits<DistanceMatrix>::value_type Distance;
+
+ typename graph_traits<Graph>::vertex_iterator i, end;
+ for(tie(i, end) = vertices(g); i != end; ++i) {
+ close[*i] = closeness_centrality(g, matrix[*i], measure);
+ }
+ }
+
+ template <typename Graph,
+ typename DistanceMatrix,
+ typename ClosenessMap>
+ inline void
+ all_total_geodesic_distances(const Graph& g,
+ DistanceMatrix& matrix,
+ ClosenessMap& close)
+ {
+ typedef typename property_matrix_traits<DistanceMatrix>::value_type Distance;
+ typedef typename property_traits<ClosenessMap>::value_type Result;
+
+ all_closeness_centralities(g, matrix, close,
+ measure_total_geodesic<Result>(g, close));
+ }
+
+ template <typename Graph,
+ typename DistanceMatrix,
+ typename ClosenessMap>
+ inline void
+ all_mean_geodesic_distances(const Graph& g,
+ DistanceMatrix& matrix,
+ ClosenessMap& close)
+ {
+ typedef typename property_matrix_traits<DistanceMatrix>::value_type Distance;
+ typedef typename property_traits<ClosenessMap>::value_type Result;
+
+ all_closeness_centralities(g, matrix, close,
+ measure_mean_geodesic<Result>(g, close));
+ }
+
+ template <typename Graph,
+ typename DistanceMatrix,
+ typename ClosenessMap>
+ inline void
+ all_inverse_geodesic_distances(const Graph& g,
+ DistanceMatrix& matrix,
+ ClosenessMap& close)
+ {
+ typedef typename property_matrix_traits<DistanceMatrix>::value_type Distance;
+ typedef typename property_traits<ClosenessMap>::value_type Result;
+
+ all_closeness_centralities(g, matrix, close,
+ measure_inverse_geodesic<Result>(g, close));
+ }
+
+ template <typename Graph,
+ typename DistanceMatrix,
+ typename ClosenessMap>
+ inline void
+ all_closenesses(const Graph& g,
+ DistanceMatrix& matrix,
+ ClosenessMap& close)
+ {
+ typedef typename property_matrix_traits<DistanceMatrix>::value_type Distance;
+ typedef typename property_traits<ClosenessMap>::value_type Result;
+
+ all_closeness_centralities(g, matrix, close,
+ measure_closeness<Result>(g, close));
+ }
+}
+
+#endif
Added: sandbox/SOC/2007/graphs/boost/graph/detail/combine_distances.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/boost/graph/detail/combine_distances.hpp 2007-07-30 08:31:11 EDT (Mon, 30 Jul 2007)
@@ -0,0 +1,55 @@
+// (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_DETAIL_COMBINE_DISTANCES_GRAPH_HPP
+#define BOOST_GRAPH_DETAIL_COMBINE_DISTANCES_GRAPH_HPP
+
+#include <functional>
+
+namespace boost
+{
+ namespace detail
+ {
+ // Note that this assumes T == property_traits<DistanceMap>::value_type
+ // and that the args and return of combine are also T.
+ template <typename Graph,
+ typename DistanceMap,
+ typename Combinator,
+ typename DistanceNumbers>
+ inline typename DistanceNumbers::value_type
+ combine_distances(const Graph& g,
+ DistanceMap dist,
+ Combinator combine,
+ DistanceNumbers distnum)
+ {
+ // If there's ever an infinite distance, then we simply
+ // return infinity.
+ typename DistanceNumbers::value_type ret(DistanceNumbers::zero());
+ typename graph_traits<Graph>::vertex_iterator i, end;
+ for(tie(i, end) = vertices(g); i != end; ++i) {
+ if(dist[*i] != DistanceNumbers::infinity()) {
+ ret = combine(ret, dist[*i]);
+ }
+ else {
+ ret = DistanceNumbers::infinity();
+ break;
+ }
+ }
+ return ret;
+ }
+
+
+ // Similar to std::plus<T>, but maximizes parameters
+ // rather than adding them.
+ template <typename T>
+ struct maximize : public std::binary_function<T, T, T>
+ {
+ T operator ()(T x, T y) const
+ { return std::max(x, y); }
+ };
+ }
+}
+#endif
Added: sandbox/SOC/2007/graphs/boost/graph/eccentricity.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/boost/graph/eccentricity.hpp 2007-07-30 08:31:11 EDT (Mon, 30 Jul 2007)
@@ -0,0 +1,73 @@
+// (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_ECCENTRICITY_HPP
+#define BOOST_GRAPH_ECCENTRICITY_HPP
+
+#include <boost/graph/detail/combine_distances.hpp>
+
+namespace boost
+{
+ template <
+ typename Graph,
+ typename DistanceMap,
+ typename Combinator>
+ inline typename property_traits<DistanceMap>::value_type
+ eccentricity(const Graph& g,
+ dist,
+ Combinator combine,
+ typename property_traits<DistanceMap>::value_type zero = T(),
+ typename property_traits<DistanceMap>::value_type inf = std::numeric_limits<T>::max())
+ {
+ return detail::combine_distances(g, dist, combine, zero, inf);
+ }
+
+ template <typename Graph, typename DistanceMap>
+ inline T
+ eccentricity(const Graph& g, DistanceMap dist)
+ {
+ return eccentricity<T>(g, dist, std::plus<T>());
+ }
+
+ template <typename Graph, typename DistanceMap>
+ inline double
+ mean_geodesic(const Graph& g, DistanceMap dist)
+ {
+ return mean_geodesic<double>(g, dist);
+ }
+
+
+ template <typename Graph, typename DistanceMap>
+ inline typename property_traits<DistanceMap>::value_type
+ eccentricity(const Graph& g,
+ DistanceMap dist)
+ {
+ typename property_traits<DistanceMap>::value_type ret(0);
+ typename graph_traits<Graph>::vertex_iterator i, end;
+ for(tie(i, end) = vertices(g); i != end; ++i) {
+ ret = std::max(ret, dist[*i]);
+ }
+ return ret;
+ }
+
+ // The computation of eccentricities, radius and diameter are all
+ // closely related. Basically, these computations can be run at
+ // the same time - compute eccentricities of all vertices, and
+ // the radius and diameter of the graph.
+
+ template <typename Graph, typename DistanceMatrix, typename EccentricityMap>
+ void
+ eccentricities(const Graph& g, DistanceMatrix& dist, EccentricityMap ecc)
+ {
+ typename graph_traits<Graph>::vertex_iterator i, j, end;
+ for(tie(i, end) = vertices(g); i != end; ++i) {
+ // compute the max eccentricity "in-place"
+ typename property_traits<EccentricityMap>::value_type& ei = ecc[*i];
+ for(j = vertices(g).first; j != end; ++j) {
+ ei = std::max(ei, dist[*i][*j]);
+ }
+ }
+ }
Modified: sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp 2007-07-30 08:31:11 EDT (Mon, 30 Jul 2007)
@@ -130,8 +130,8 @@
{
typedef typename graph_traits<Graph>::vertices_size_type size_type;
typedef typename graph_traits<Graph>::vertex_descriptor key_type;
- typedef Value value_type;
+ typedef Value value_type;
typedef std::tr1::unordered_map<key_type, value_type> container_type;
typedef std::tr1::unordered_map<key_type, container_type> matrix_type;
@@ -189,6 +189,7 @@
typedef detail::hash_property_map_adapter<Graph, container_type> map_type;
};
+
template <typename Graph, typename Value>
struct exterior_vertex_property
{
@@ -205,6 +206,15 @@
typedef typename traits_type::matrix_type matrix_type;
typedef typename traits_type::map_type map_type;
};
+
+ template <typename Matrix>
+ struct property_matrix_traits
+ {
+ typedef typename Matrix::matrix_type matrix_type;
+ typedef typename Matrix::container_type container_type;
+ typedef typename Matrix::value_type value_type;
+ typedef typename Matrix::key_type key_type;
+ };
}
#endif
Added: sandbox/SOC/2007/graphs/boost/graph/numeric_values.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/boost/graph/numeric_values.hpp 2007-07-30 08:31:11 EDT (Mon, 30 Jul 2007)
@@ -0,0 +1,34 @@
+// (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_NUMERIC_VALUES_HPP
+#define BOOST_GRAPH_NUMERIC_VALUES_HPP
+
+#include <limits>
+
+namespace boost
+{
+
+ // This generic type reports various numeric values for
+ // some type. This must be specialized for non-numeric
+ // types such that the return values have the equivalent
+ // semantics of zero and infinity. This classd essentially
+ // builds abstractions for zero and infinity out of types
+ // that don't necessarily support it.
+ template <typename T>
+ struct numeric_values
+ {
+ typedef T value_type;
+
+ static inline T zero()
+ { return T(); }
+
+ static inline T infinity()
+ { return std::numeric_limits<T>::max(); }
+ };
+}
+
+#endif