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

From: asutton_at_[hidden]
Date: 2007-08-01 09:47:12

Author: asutton
Date: 2007-08-01 09:47:04 EDT (Wed, 01 Aug 2007)
New Revision: 38333
URL: http://svn.boost.org/trac/boost/changeset/38333

Log:
Renamed combine_distance to geodesic
Added some bib information to detail/geodesic
Moved various helper functors to detail/geodesic
Completely rewrote degree distributions (to centrality)
Completely rewrote all of the distance stuff
Made geodesic distance much more generic

Added:
   sandbox/SOC/2007/graphs/boost/graph/detail/geodesic.hpp
      - copied, changed from r7589, /sandbox/SOC/2007/graphs/boost/graph/detail/combine_distances.hpp
   sandbox/SOC/2007/graphs/boost/graph/geodesic_distance.hpp   (contents, props changed)
Removed:
   sandbox/SOC/2007/graphs/boost/graph/detail/combine_distances.hpp
Text files modified: 
   sandbox/SOC/2007/graphs/boost/graph/closeness_centrality.hpp |   324 +++++++-------------------------------- 
   sandbox/SOC/2007/graphs/boost/graph/degree_centrality.hpp    |   238 ----------------------------            
   sandbox/SOC/2007/graphs/boost/graph/detail/geodesic.hpp      |    65 +++++++                                 
   sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp    |    10 +                                       
   4 files changed, 143 insertions(+), 494 deletions(-)

Modified: sandbox/SOC/2007/graphs/boost/graph/closeness_centrality.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/closeness_centrality.hpp	(original)
+++ sandbox/SOC/2007/graphs/boost/graph/closeness_centrality.hpp	2007-08-01 09:47:04 EDT (Wed, 01 Aug 2007)
@@ -5,190 +5,80 @@
 // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
 
 #ifndef BOOST_GRAPH_CLOSENESS_CENTRALITY_HPP
-#define BOOST_GRAPH_CLISENESS_CENTRALITY_HPP
+#define BOOST_GRAPH_CLOSENESS_CENTRALITY_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/detail/geodesic.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>
+    template <
+            typename Graph,
+            typename DistanceNumbers,
+            typename ResultNumbers,
+            typename Reciprocal = detail::reciprocal<typename ResultNumbers::value_type>
+        >
+    struct closeness_measure
+        : public geodesic_measure<Graph, DistanceNumbers, ResultNumbers>
     {
-        typedef closeness_centrality_measure<
-                Graph, DistanceNumbers, ResultNumbers
-            > base_type;
+        typedef geodesic_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)
+        result_type operator ()(distance_type d, const Graph&)
         {
-            typedef result_type T;
+            Reciprocal r;
             return
                 (d == base_type::infinite_distance()) ?
-                    base_type::zero_result() : T(n) / T(d);
+                    base_type::zero_result() : r(result_type(d));
         }
     };
 
     template <typename Graph, typename DistanceMap>
-    inline inverse_geodesic_measure<Graph, typename property_traits<DistanceMap>::value_type, float>
-    measure_inverse_geodesic(const Graph&, DistanceMap)
+    inline closeness_measure<
+            Graph,
+            typename property_traits<DistanceMap>::value_type,
+            float,
+            detail::reciprocal<float> >
+    measure_closeness(const Graph&, DistanceMap)
     {
-        return inverse_geodesic_measure<Graph, typename property_traits<DistanceMap>::value_type, float>();
+        typedef typename property_traits<DistanceMap>::value_type Distance;
+        return closeness_measure<Graph, Distance, float, detail::reciprocal<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>
+    inline closeness_measure<
+            Graph,
+            typename property_traits<DistanceMap>::value_type,
+            T,
+            detail::reciprocal<T> >
     measure_closeness(const Graph&, DistanceMap)
     {
-        return closeness_measure<Graph, typename property_traits<DistanceMap>::value_type, float>();
+        typedef typename property_traits<DistanceMap>::value_type Distance;
+        return closeness_measure<Graph, Distance, T, detail::reciprocal<T> >();
     }
 
-    template <typename T, typename Graph, typename DistanceMap>
-    inline closeness_measure<Graph, typename property_traits<DistanceMap>::value_type, T>
+    template <typename T, typename Graph, typename DistanceMap, typename Reciprocal>
+    inline closeness_measure<
+            Graph,
+            typename property_traits<DistanceMap>::value_type,
+            T,
+            Reciprocal>
     measure_closeness(const Graph&, DistanceMap)
     {
-        return closeness_measure<Graph, typename property_traits<DistanceMap>::value_type, T>();
+        typedef typename property_traits<DistanceMap>::value_type Distance;
+        return closeness_measure<Graph, Distance, T, Reciprocal>();
     }
 
-
     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)
+    vertex_closeness_centrality(const Graph& g,
+                                DistanceMap dist,
+                                Measure measure,
+                                Combinator combine)
     {
         typedef typename Measure::distance_type Distance;
         typedef typename Measure::distance_values DistanceValues;
@@ -197,151 +87,63 @@
         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)
+    vertex_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));
+        return vertex_closeness_centrality(g, dist, measure, std::plus<Distance>());
     }
 
     template <typename Graph, typename DistanceMap>
     inline float
-    closeness(const Graph& g, DistanceMap dist)
+    vertex_closeness_centrality(const Graph& g, DistanceMap dist)
     {
-        return closeness_centrality(g, dist, measure_closeness(g, dist));
+        return vertex_closeness_centrality(g, dist, measure_closeness(g, dist));
     }
 
     template <typename T, typename Graph, typename DistanceMap>
     inline T
-    closeness(const Graph& g, DistanceMap dist)
+    vertex_closeness_centrality(const Graph& g, DistanceMap dist)
     {
-        return closeness_centrality(g, dist, measure_closeness<T>(g, dist));
+        return vertex_closeness_centrality(g, dist, measure_closeness<T>(g, dist));
     }
 
     template <typename Graph,
               typename DistanceMatrix,
-              typename ClosenessMap,
+              typename CentralityMap,
               typename Measure>
     inline void
-    all_closeness_centralities(const Graph& g,
-                               DistanceMatrix& matrix,
-                               ClosenessMap& close,
-                               Measure measure)
+    closeness_centrality(const Graph& g,
+                         DistanceMatrix& dist,
+                         CentralityMap& cent,
+                         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);
+            cent[*i] = vertex_closeness_centrality(g, dist[*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>
+              typename CentralityMap>
     inline void
-    all_closenesses(const Graph& g,
-                    DistanceMatrix& matrix,
-                    ClosenessMap& close)
+    closeness_centrality(const Graph& g,
+                         DistanceMatrix& dist,
+                         CentralityMap& cent)
     {
         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));
+        typedef typename exterior_vertex_property<Graph, Distance>::map_type DistanceMap;
+        typedef typename property_traits<CentralityMap>::value_type Result;
+        closeness_centrality(g, dist, cent,
+                             measure_closeness<Result>(g, DistanceMap()));
     }
 }
 

Modified: sandbox/SOC/2007/graphs/boost/graph/degree_centrality.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/degree_centrality.hpp	(original)
+++ sandbox/SOC/2007/graphs/boost/graph/degree_centrality.hpp	2007-08-01 09:47:04 EDT (Wed, 01 Aug 2007)
@@ -12,8 +12,8 @@
     template <typename Graph>
     struct degree_centrality_measure
     {
-        typedef graph_traits<Graph>::degree_size_type value_type;
-        typedef graph_traits<Graph>::vertex_descriptor vertex_type;
+        typedef typename graph_traits<Graph>::degree_size_type value_type;
+        typedef typename graph_traits<Graph>::vertex_descriptor vertex_type;
     };
 
     template <typename Graph>
@@ -22,22 +22,23 @@
     {
         typedef degree_centrality_measure<Graph> base_type;
         typedef typename base_type::value_type value_type;
-        typedef typename base_type::vertex_descriptor vertex_type;
+        typedef typename base_type::vertex_type vertex_type;
 
         inline value_type operator ()(const Graph& g, vertex_type v)
         {
-            return  get_degree(g, v, typename Graph::directed_category());
+            typename graph_traits<Graph>::directed_category cat;
+            return this->get_degree(g, v, cat);
         }
 
     private:
         inline value_type
-        get_degree(const Graph& g, vertex_type v, undirected_graph_tag)
+        get_degree(const Graph& g, vertex_type v, undirected_tag)
         {
             return degree(v, g);
         }
 
         inline value_type
-        get_degree(const Graph& g, vertex_type v, directed_graph_tag)
+        get_degree(const Graph& g, vertex_type v, directed_tag)
         {
             return out_degree(v, g);
         }
@@ -77,7 +78,7 @@
     {
         typename graph_traits<Graph>::vertex_iterator i, end;
         for(tie(i, end) = vertices(g); i != end; ++i) {
-            cent[*i] = vertex_centrality(g, *i, measure);
+            cent[*i] = vertex_degree_centrality(g, *i, measure);
         }
     }
 
@@ -88,229 +89,6 @@
         degree_centrality(g, cent, measure_basic_degree_centrality(g));
     }
 
-    // Helper functions for computing degree distributions, histograms. Note
-    // that when passed a not_given argumemt, all of these operations are
-    // no-ops. The effect is that the actual computations shouldn't add hidden
-    // constants at run-time.
-    namespace detail
-    {
-        template <typename Dist, typename Graph>
-        inline void
-        max_degree(Dist&,
-                   typename graph_traits<Graph>::degree_size_type& m,
-                   typename graph_traits<Graph>::vertex_descriptor v,
-                   const Graph& g)
-        { m = max(m, degree(v, g)); }
-
-        template <typename Graph>
-        inline void
-        max_degree(not_given,
-                   typename graph_traits<Graph>::degree_size_type&,
-                   typename graph_traits<Graph>::vertex_descriptor,
-                   const Graph&)
-        {}
-
-
-        template <typename Dist, typename Graph>
-        inline void
-        max_out_degree(Dist&,
-                       typename graph_traits<Graph>::degree_size_type& m,
-                       typename graph_traits<Graph>::vertex_descriptor v,
-                       const Graph& g)
-        { m = max(m, out_degree(v, g)); }
-
-        template <typename Graph>
-        inline void
-        max_out_degree(not_given,
-                       typename graph_traits<Graph>::degree_size_type&,
-                       typename graph_traits<Graph>::vertex_descriptor,
-                       const Graph&)
-        {}
-
-
-        template <typename Dist, typename Graph>
-        inline void
-        max_in_degree(Dist&,
-                      typename graph_traits<Graph>::degree_size_type& m,
-                      typename graph_traits<Graph>::vertex_descriptor v,
-                      const Graph& g)
-        { m = max(m, in_degree(v, g)); }
-
-        template <typename Graph>
-        inline void
-        max_in_degree(not_given,
-                      typename graph_traits<Graph>::degree_size_type&,
-                      typename graph_traits<Graph>::vertex_descriptor,
-                      const Graph&)
-        { }
-
-
-        template <typename Dist>
-        inline void resize_distribution(Dist& d, size_t n)
-        { d.resize(n); }
-
-        inline void resize_distribution(not_given, size_t n)
-        { }
-
-
-        template <typename Hist, typename Graph>
-        inline void observe_degree(Hist& d,
-                                   typename graph_traits<Graph>::vertex_descriptor v,
-                                   const Graph& g)
-        { d[degree(v, g)] += 1; }
-
-        template <typename Graph>
-        inline void observe_degree(not_given,
-                                   typename graph_traits<Graph>::vertex_descriptor v,
-                                   const Graph& g)
-        { }
-
-
-        template <typename Hist, typename Graph>
-        inline void observe_out_degree(Hist& d,
-                                       typename graph_traits<Graph>::vertex_descriptor v,
-                                       const Graph& g)
-        { d[out_degree(v, g)] += 1; }
-
-        template <typename Graph>
-        inline void observe_out_degree(not_given,
-                                       typename graph_traits<Graph>::vertex_descriptor v,
-                                       const Graph& g)
-        { }
-
-
-        template <typename Dist, typename Graph>
-        inline void observe_in_degree(Dist& d,
-                                      typename graph_traits<Graph>::vertex_descriptor v,
-                                      const Graph& g)
-        { d[in_degree(v, g)] += 1; }
-
-        template <typename Graph>
-        inline void observe_in_degree(not_given,
-                                      typename graph_traits<Graph>::vertex_descriptor v,
-                                      const Graph& g)
-        { }
-
-
-        template <typename Hist, typename Graph>
-        inline void record_degree(Hist& h,
-                                  typename graph_traits<Graph>::vertex_descriptor v,
-                                  const Graph& g)
-        { h[degree(v, g)].push_back(v); }
-
-        template <typename Graph>
-        inline void record_degree(not_given,
-                                  typename graph_traits<Graph>::vertex_descriptor v,
-                                  const Graph& g)
-        { }
-
-
-        template <typename Hist, typename Graph>
-        inline void record_out_degree(Hist& h,
-                                      typename graph_traits<Graph>::vertex_descriptor v,
-                                      const Graph& g)
-        { h[out_degree(v, g)].push_back(v); }
-
-        template <typename Graph>
-        inline void record_out_degree(not_given,
-                                      typename graph_traits<Graph>::vertex_descriptor v,
-                                      const Graph& g)
-        { }
-
-
-        template <typename Hist, typename Graph>
-        inline void record_in_degree(Hist& h,
-                                     typename graph_traits<Graph>::vertex_descriptor v,
-                                     const Graph& g)
-        { h[in_degree(v, g)].push_back(v); }
-
-        template <typename Graph>
-        inline void record_in_degree(not_given,
-                                     typename graph_traits<Graph>::vertex_descriptor v,
-                                     const Graph& g)
-        { }
-    }
-
-    // A helper function for initializing distributions and histograms
-    BOOST_PARAMETER_FUNCTION(
-        (void), initialize_distribution, tag,
-        (required (graph, *))
-        (optional
-            (out(distribution), *, not_given())
-            (out(out_distribution), *, not_given())
-            (out(in_distribution), *, not_given()))
-        )
-    {
-        typename graph_traits<graph_type>::vertex_iterator i, end;
-
-        // part 1: find the max observable degrees for the graph so we
-        // only have to resize once. note that this relaxes requirements on
-        // the distribution type - it just needs to be resizable.
-        size_t max_d = 0, max_od = 0, max_id = 0;
-        for(tie(i, end) = vertices(graph); i != end; ++i) {
-            typename graph_type::vertex_descriptor v = *i;
-            detail::max_degree(distribution, max_d, v, graph);
-            detail::max_out_degree(out_distribution, max_od, v, graph);
-            detail::max_in_degree(in_distribution, max_id, v, graph);
-        }
-        detail::resize_distribution(distribution, max_d + 1);
-        detail::resize_distribution(out_distribution, max_od + 1);
-        detail::resize_distribution(in_distribution, max_id + 1);
-    }
-
-    // the actual degree_distribution function
-    BOOST_PARAMETER_FUNCTION(
-        (void), degree_distribution, tag,
-        (required (graph, *))
-        (optional
-            (out(distribution), *, not_given())
-            (out(out_distribution), *, not_given())
-            (out(in_distribution), *, not_given()))
-        )
-    {
-        typename graph_traits<graph_type>::vertex_iterator i, end;
-
-        // part 1: initialize distributions
-        initialize_distribution(graph,
-            _distribution = distribution,
-            _out_distribution = out_distribution,
-            _in_distribution = in_distribution);
-
-        // part 2: record observed distributions
-        for(tie(i, end) = vertices(graph); i != end; ++i) {
-            typename graph_type::vertex_descriptor v = *i;
-            detail::observe_degree(distribution, v, graph);
-            detail::observe_out_degree(out_distribution, v, graph);
-            detail::observe_in_degree(in_distribution, v, graph);
-        }
-    }
-
-    // the actual degree_histogram function
-    BOOST_PARAMETER_FUNCTION(
-        (void), degree_histogram, tag,
-        (required (graph, *))
-        (optional
-            (out(histogram), *, not_given())
-            (out(out_histogram), *, not_given())
-            (out(in_histogram), *, not_given()))
-        )
-    {
-        typename graph_traits<graph_type>::vertex_iterator i, end;
-
-        // part 1: initialize distributions
-        initialize_distribution(graph,
-            _distribution = histogram,
-            _out_distribution = out_histogram,
-            _in_distribution = in_histogram);
-
-        // part 2: record observed distributions
-        for(tie(i, end) = vertices(graph); i != end; ++i) {
-            typename graph_type::vertex_descriptor v = *i;
-            detail::record_degree(histogram, v, graph);
-            detail::record_out_degree(out_histogram, v, graph);
-            detail::record_in_degree(in_histogram, v, graph);
-        }
-    }
 }
 
 #endif

Deleted: sandbox/SOC/2007/graphs/boost/graph/detail/combine_distances.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/detail/combine_distances.hpp	2007-08-01 09:47:04 EDT (Wed, 01 Aug 2007)
+++ (empty file)
@@ -1,55 +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_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

Copied: sandbox/SOC/2007/graphs/boost/graph/detail/geodesic.hpp (from r7589, /sandbox/SOC/2007/graphs/boost/graph/detail/combine_distances.hpp)
==============================================================================
--- /sandbox/SOC/2007/graphs/boost/graph/detail/combine_distances.hpp	(original)
+++ sandbox/SOC/2007/graphs/boost/graph/detail/geodesic.hpp	2007-08-01 09:47:04 EDT (Wed, 01 Aug 2007)
@@ -4,13 +4,38 @@
 // 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
+#ifndef BOOST_GRAPH_DETAIL_GEODESIC_HPP
+#define BOOST_GRAPH_DETAIL_GEODESIC_HPP
 
 #include <functional>
+#include <boost/graph/numeric_values.hpp>
 
 namespace boost
 {
+    // This is a very good discussion on centrality measures. While I can't
+    // say that this has been the motivating factor for the design and
+    // implementation of ths centrality framework, it does provide a single
+    // point of reference for defining things like degree and closeness
+    // centrality. Plus, the bibliography seems fairly complete.
+    //
+    //     @article{citeulike:1144245,
+    //         author = {Borgatti, Stephen  P.  and Everett, Martin  G. },
+    //         citeulike-article-id = {1144245},
+    //         doi = {10.1016/j.socnet.2005.11.005},
+    //         journal = {Social Networks},
+    //         keywords = {2006 centrality complex_network graph-theory social sociality social_network},
+    //         month = {October},
+    //         number = {4},
+    //         pages = {466--484},
+    //         priority = {0},
+    //         title = {A Graph-theoretic perspective on centrality},
+    //         url = {http://dx.doi.org/10.1016/j.socnet.2005.11.005},
+    //             volume = {28},
+    //             year = {2006}
+    //         }
+    //     }
+
+
     namespace detail
     {
         // Note that this assumes T == property_traits<DistanceMap>::value_type
@@ -50,6 +75,42 @@
             T operator ()(T x, T y) const
             { return std::max(x, y); }
         };
+
+        // Another helper, like maximize() to help abstract functional
+        // concepts. This is trivially instantiated for builtin numeric
+        // types, but should be specialized for those types that have
+        // discrete notions of reciprocals.
+        template <typename T>
+                struct reciprocal : public std::unary_function<T, T>
+        {
+            T operator ()(T t)
+            { return T(1) / t; }
+        };
     }
+
+    // This type defines the basic facilities used for computing values
+    // based on the geodesic distances between vertices. Examples include
+    // closeness centrality and mean geodesic distance.
+    template <typename Graph,
+              typename DistanceType,
+              typename ResultType>
+    struct geodesic_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(); }
+    };
 }
 #endif

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-08-01 09:47:04 EDT (Wed, 01 Aug 2007)
@@ -44,6 +44,10 @@
             typedef typename map_type::reference reference;
             typedef typename map_type::category category;
 
+            inline vector_property_map_adapter()
+                : m_map()
+            { }
+
             inline vector_property_map_adapter(Container& c)
                 : m_map(c.begin())
             { }
@@ -53,7 +57,7 @@
             { }
 
             inline reference operator [](const key_type& k) const
-            { return m_map[k]; }
+            { return m_map[k];  }
 
             map_type m_map;
         };
@@ -71,6 +75,10 @@
             typedef typename map_type::reference reference;
             typedef typename map_type::category category;
 
+            inline hash_property_map_adapter()
+                : m_map()
+            { }
+
             inline hash_property_map_adapter(Container& c)
                 : m_map(c)
             { }

Added: sandbox/SOC/2007/graphs/boost/graph/geodesic_distance.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/boost/graph/geodesic_distance.hpp	2007-08-01 09:47:04 EDT (Wed, 01 Aug 2007)
@@ -0,0 +1,221 @@
+// (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_DISTANCE_HPP
+#define BOOST_GRAPH_GEODESIC_DISTANCE_HPP
+
+#include <boost/graph/detail/geodesic.hpp>
+#include <boost/graph/exterior_property.hpp>
+
+namespace boost
+{
+
+    template <typename Graph, typename DistanceType, typename ResultType>
+    struct mean_geodesic_measure
+        : public geodesic_measure<Graph, DistanceType, ResultType>
+    {
+        typedef geodesic_measure<Graph, DistanceType, ResultType> 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 DistanceType, typename ResultType>
+    struct mean_graph_distance_measure
+        : public geodesic_measure<Graph, DistanceType, ResultType>
+    {
+        typedef geodesic_measure<Graph, DistanceType, ResultType> 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, size_type n)
+        {
+            typename graph_traits<Graph>::directed_category cat;
+            return this->average(d, n, 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);
+            }
+        }
+    };
+
+    template <typename Distance, typename Result, typename Graph>
+    inline mean_graph_distance_measure<Graph, Distance, Result>
+    measure_mean_graph_distance(const Graph& g)
+    { return mean_graph_distance_measure<Graph, Distance, Result>(); }
+
+    template <typename T, typename Graph, typename DistanceMap>
+    inline mean_graph_distance_measure<Graph, typename property_traits<DistanceMap>::value_type, T>
+    measure_mean_graph_distance(const Graph& g, DistanceMap dist)
+    { return mean_graph_distance_measure<Graph, typename property_traits<DistanceMap>::value_type, T>(); }
+
+
+    template <typename Graph,
+              typename DistanceMap,
+              typename Measure,
+              typename Combinator>
+    inline typename Measure::result_type
+    vertex_mean_geodesic(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
+    vertex_mean_geodesic(const Graph& g,
+                         DistanceMap dist,
+                         Measure measure)
+    {
+        typedef typename Measure::distance_type Distance;
+        return vertex_mean_geodesic(g, dist, measure, std::plus<Distance>());
+    }
+
+    template <typename Graph, typename DistanceMap>
+    inline float
+    vertex_mean_geodesic(const Graph& g, DistanceMap dist)
+    {
+        return vertex_mean_geodesic(g, dist, measure_mean_geodesic(g, dist));
+    }
+
+    template <typename T, typename Graph, typename DistanceMap>
+    inline T
+    vertex_mean_geodesic(const Graph& g, DistanceMap dist)
+    {
+        return vertex_mean_geodesic(g, dist, measure_mean_geodesic<T>(g, dist));
+    }
+
+
+    template <typename Graph,
+              typename DistanceMatrix,
+              typename GeodesicMap,
+              typename Measure>
+    inline void
+    mean_geodesic(const Graph& g,
+                  DistanceMatrix& dist,
+                  GeodesicMap& geo,
+                  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) {
+            geo[*i] = vertex_mean_geodesic(g, dist[*i], measure);
+        }
+    }
+
+    template <typename Graph,
+              typename DistanceMatrix,
+              typename GeodesicMap>
+    inline void
+    mean_geodesic(const Graph& g,
+                  DistanceMatrix& dist,
+                  GeodesicMap& geo)
+    {
+        typedef typename property_matrix_traits<DistanceMatrix>::value_type Distance;
+        typedef typename exterior_vertex_property<Graph, Distance>::map_type DistanceMap;
+        typedef typename property_traits<GeodesicMap>::value_type Result;
+        mean_geodesic(g, dist, geo,
+                      measure_mean_geodesic<Result>(g, DistanceMap()));
+    }
+
+    template <typename Graph,
+              typename DistanceMatrix,
+              typename Measure>
+    inline typename Measure::result_type
+    graph_mean_geodesic(const Graph& g,
+                        DistanceMatrix& dist,
+                        Measure measure)
+    {
+        typedef typename Measure::result_type T;
+        typedef typename property_matrix_traits<DistanceMatrix>::value_type Distance;
+        typedef typename exterior_vertex_property<Graph, Distance>::map_type DistanceMap;
+        typedef typename exterior_vertex_property<Graph, T>::container_type GeoContainer;
+        typedef typename exterior_vertex_property<Graph, T>::map_type GeoMap;
+
+        // get all mean geos
+        GeoContainer geodesics(num_vertices(g));
+        GeoMap geo(geodesics);
+        mean_geodesic(g, dist, geo,
+                      measure_mean_geodesic(g, DistanceMap()));
+
+        // re-combine these as new distances
+        T sum = detail::combine_distances(g, geo,
+                                          std::plus<T>(),
+                                          numeric_values<T>());
+        return measure(sum, num_vertices(g));
+    }
+
+    template <typename T, typename Graph, typename DistanceMatrix>
+    inline T
+    graph_mean_geodesic(const Graph& g,
+                        DistanceMatrix& dist)
+    {
+        return
+            graph_mean_geodesic(g, dist, measure_mean_graph_distance<T, T>(g));
+    }
+
+    template <typename Graph, typename DistanceMatrix>
+    inline float
+    graph_mean_geodesic(const Graph& g,
+                        DistanceMatrix& dist)
+    {
+        return graph_mean_geodesic<float>(g, dist);
+    }
+}
+
+#endif