[Boost-commit] svn:boost r7589 - in sandbox/SOC/2007/graphs/boost/graph: . detail

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