[Boost-commit] svn:boost r51100 - in trunk: boost/graph libs/graph/test

Subject: [Boost-commit] svn:boost r51100 - in trunk: boost/graph libs/graph/test
From: asutton_at_[hidden]
Date: 2009-02-08 10:40:34

Author: asutton
Date: 2009-02-08 10:40:33 EST (Sun, 08 Feb 2009)
New Revision: 51100
URL: http://svn.boost.org/trac/boost/changeset/51100

Log:
Importing geodesic distance module from SOC.

Added:
   trunk/boost/graph/geodesic_distance.hpp   (contents, props changed)
      - copied, changed from r51086, /sandbox/SOC/2007/graphs/boost/graph/geodesic_distance.hpp
   trunk/libs/graph/test/mean_geodesic.cpp   (contents, props changed)
      - copied, changed from r51086, /sandbox/SOC/2007/graphs/libs/graph/test/runtime/mean_geodesic.cpp
Text files modified: 
   trunk/boost/graph/geodesic_distance.hpp |   347 +++++++++++++++++++-------------------- 
   trunk/libs/graph/test/Jamfile.v2        |     1                                         
   trunk/libs/graph/test/mean_geodesic.cpp |    35 +--                                     
   3 files changed, 189 insertions(+), 194 deletions(-)

Copied: trunk/boost/graph/geodesic_distance.hpp (from r51086, /sandbox/SOC/2007/graphs/boost/graph/geodesic_distance.hpp)
==============================================================================
--- /sandbox/SOC/2007/graphs/boost/graph/geodesic_distance.hpp	(original)
+++ trunk/boost/graph/geodesic_distance.hpp	2009-02-08 10:40:33 EST (Sun, 08 Feb 2009)
@@ -12,204 +12,199 @@
 
 namespace boost
 {
-    template <typename Graph,
-              typename DistanceType,
-              typename ResultType,
-              typename Divides = std::divides<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;
-
-        result_type operator ()(distance_type d, const Graph& g)
-        {
-            function_requires< VertexListGraphConcept<Graph> >();
-            function_requires< NumericValueConcept<DistanceType> >();
-            function_requires< NumericValueConcept<ResultType> >();
-            function_requires< AdaptableBinaryFunctionConcept<Divides,ResultType,ResultType,ResultType> >();
-
-            return
-                (d == base_type::infinite_distance()) ?
-                    base_type::infinite_result() :
-                    div(result_type(d), result_type(num_vertices(g) - 1));
-        }
-        Divides div;
-    };
-
-    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 Graph,
+          typename DistanceType,
+          typename ResultType,
+          typename Divides = std::divides<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;
 
-    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)
+    result_type operator ()(distance_type d, const Graph& g)
     {
-        return mean_geodesic_measure<Graph, typename property_traits<DistanceMap>::value_type, T>();
-    }
+        function_requires< VertexListGraphConcept<Graph> >();
+        function_requires< NumericValueConcept<DistanceType> >();
+        function_requires< NumericValueConcept<ResultType> >();
+        function_requires< AdaptableBinaryFunctionConcept<Divides,ResultType,ResultType,ResultType> >();
+
+        return (d == base_type::infinite_distance())
+            ? base_type::infinite_result()
+            : div(result_type(d), result_type(num_vertices(g) - 1));
+    }
+    Divides div;
+};
+
+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>();
+}
 
-    // 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
-    // X then the average of x's should also be type X.
-    //
-    // This type is a little under-genericized... It needs generic parameters
-    // for addition and division.
-    template <typename Graph, typename DistanceType>
-    struct mean_graph_distance_measure
-        : public geodesic_measure<Graph, DistanceType, DistanceType>
-    {
-        typedef geodesic_measure<Graph, DistanceType, DistanceType> base_type;
-        typedef typename base_type::distance_type distance_type;
-        typedef typename base_type::result_type result_type;
-
-        inline result_type operator ()(distance_type d, const Graph& g)
-        {
-            function_requires< VertexListGraphConcept<Graph> >();
-            function_requires< NumericValueConcept<DistanceType> >();
-
-            if(d == base_type::infinite_distance()) {
-                return base_type::infinite_result();
-            }
-            else {
-                return d / result_type(num_vertices(g));
-            }
-        }
-    };
+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 DistanceMap>
-    inline mean_graph_distance_measure<Graph, typename property_traits<DistanceMap>::value_type>
-    measure_graph_mean_geodesic(const Graph& g, DistanceMap dist)
-    {
-        typedef typename property_traits<DistanceMap>::value_type T;
-        return mean_graph_distance_measure<Graph, 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
+// X then the average of x's should also be type X. Is there a case where this
+// is not true?
+//
+// This type is a little under-genericized... It needs generic parameters
+// for addition and division.
+template <typename Graph, typename DistanceType>
+struct mean_graph_distance_measure
+    : public geodesic_measure<Graph, DistanceType, DistanceType>
+{
+    typedef geodesic_measure<Graph, DistanceType, DistanceType> base_type;
+    typedef typename base_type::distance_type distance_type;
+    typedef typename base_type::result_type result_type;
 
-    template <typename Graph,
-              typename DistanceMap,
-              typename Measure,
-              typename Combinator>
-    inline typename Measure::result_type
-    mean_geodesic(const Graph& g,
-                  DistanceMap dist,
-                  Measure measure,
-                  Combinator combine)
+    inline result_type operator ()(distance_type d, const Graph& g)
     {
-        function_requires< DistanceMeasureConcept<Measure,Graph> >();
-        typedef typename Measure::distance_type Distance;
+        function_requires< VertexListGraphConcept<Graph> >();
+        function_requires< NumericValueConcept<DistanceType> >();
 
-        Distance n = detail::combine_distances(g, dist, combine, Distance(0));
-        return measure(n, g);
+        if(d == base_type::infinite_distance()) {
+            return base_type::infinite_result();
+        }
+        else {
+            return d / result_type(num_vertices(g));
+        }
     }
+};
 
-    template <typename Graph,
-              typename DistanceMap,
-              typename Measure>
-    inline typename Measure::result_type
-    mean_geodesic(const Graph& g, DistanceMap dist, Measure measure)
-    {
-        function_requires< DistanceMeasureConcept<Measure,Graph> >();
-        typedef typename Measure::distance_type Distance;
+template <typename Graph, typename DistanceMap>
+inline mean_graph_distance_measure<Graph, typename property_traits<DistanceMap>::value_type>
+measure_graph_mean_geodesic(const Graph& g, DistanceMap dist)
+{
+    typedef typename property_traits<DistanceMap>::value_type T;
+    return mean_graph_distance_measure<Graph, T>();
+}
 
-        return mean_geodesic(g, dist, measure, std::plus<Distance>());
-    }
+template <typename Graph,
+          typename DistanceMap,
+          typename Measure,
+          typename Combinator>
+inline typename Measure::result_type
+mean_geodesic(const Graph& g,
+                DistanceMap dist,
+                Measure measure,
+                Combinator combine)
+{
+    function_requires< DistanceMeasureConcept<Measure,Graph> >();
+    typedef typename Measure::distance_type Distance;
 
-    template <typename Graph, typename DistanceMap>
-    inline float
-    mean_geodesic(const Graph& g, DistanceMap dist)
-    {
-        return mean_geodesic(g, dist, measure_mean_geodesic(g, dist));
-    }
+    Distance n = detail::combine_distances(g, dist, combine, Distance(0));
+    return measure(n, g);
+}
 
-    template <typename T, typename Graph, typename DistanceMap>
-    inline T
-    mean_geodesic(const Graph& g, DistanceMap dist)
-    {
-        return mean_geodesic(g, dist, measure_mean_geodesic<T>(g, dist));
-    }
+template <typename Graph,
+            typename DistanceMap,
+            typename Measure>
+inline typename Measure::result_type
+mean_geodesic(const Graph& g, DistanceMap dist, Measure measure)
+{
+    function_requires< DistanceMeasureConcept<Measure,Graph> >();
+    typedef typename Measure::distance_type Distance;
 
+    return mean_geodesic(g, dist, measure, std::plus<Distance>());
+}
 
-    template <typename Graph,
-              typename DistanceMatrixMap,
-              typename GeodesicMap,
-              typename Measure>
-    inline typename property_traits<GeodesicMap>::value_type
-    all_mean_geodesics(const Graph& g,
-                       DistanceMatrixMap dist,
-                       GeodesicMap geo,
-                       Measure measure)
-    {
-        function_requires< VertexListGraphConcept<Graph> >();
-        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
-        typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
-        function_requires< ReadablePropertyMapConcept<DistanceMatrixMap,Vertex> >();
-        typedef typename property_traits<DistanceMatrixMap>::value_type DistanceMap;
-        function_requires< DistanceMeasureConcept<Measure,Graph> >();
-        typedef typename Measure::result_type Result;
-        function_requires< WritablePropertyMapConcept<GeodesicMap,Vertex> >();
-        function_requires< NumericValueConcept<Result> >();
-
-        // NOTE: We could compute the mean geodesic here by performing additional
-        // computations (i.e., adding and dividing). However, I don't really feel
-        // like fully genericizing the entire operation yet so I'm not going to.
-
-        Result inf = numeric_values<Result>::infinity();
-        Result sum = numeric_values<Result>::zero();
-        VertexIterator i, end;
-        for(tie(i, end) = vertices(g); i != end; ++i) {
-            DistanceMap dm = get(dist, *i);
-            Result r = mean_geodesic(g, dm, measure);
-            put(geo, *i, r);
-
-            // compute the sum along with geodesics
-            if(r == inf) {
-                sum = inf;
-            }
-            else if(sum != inf) {
-                sum += r;
-            }
+template <typename Graph, typename DistanceMap>
+inline float
+mean_geodesic(const Graph& g, DistanceMap dist)
+{ return mean_geodesic(g, dist, measure_mean_geodesic(g, dist)); }
+
+template <typename T, typename Graph, typename DistanceMap>
+inline T
+mean_geodesic(const Graph& g, DistanceMap dist)
+{ return mean_geodesic(g, dist, measure_mean_geodesic<T>(g, dist)); }
+
+
+template <typename Graph,
+            typename DistanceMatrixMap,
+            typename GeodesicMap,
+            typename Measure>
+inline typename property_traits<GeodesicMap>::value_type
+all_mean_geodesics(const Graph& g,
+                    DistanceMatrixMap dist,
+                    GeodesicMap geo,
+                    Measure measure)
+{
+    function_requires< VertexListGraphConcept<Graph> >();
+    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+    typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
+    function_requires< ReadablePropertyMapConcept<DistanceMatrixMap,Vertex> >();
+    typedef typename property_traits<DistanceMatrixMap>::value_type DistanceMap;
+    function_requires< DistanceMeasureConcept<Measure,Graph> >();
+    typedef typename Measure::result_type Result;
+    function_requires< WritablePropertyMapConcept<GeodesicMap,Vertex> >();
+    function_requires< NumericValueConcept<Result> >();
+
+    // NOTE: We could compute the mean geodesic here by performing additional
+    // computations (i.e., adding and dividing). However, I don't really feel
+    // like fully genericizing the entire operation yet so I'm not going to.
+
+    Result inf = numeric_values<Result>::infinity();
+    Result sum = numeric_values<Result>::zero();
+    VertexIterator i, end;
+    for(tie(i, end) = vertices(g); i != end; ++i) {
+        DistanceMap dm = get(dist, *i);
+        Result r = mean_geodesic(g, dm, measure);
+        put(geo, *i, r);
+
+        // compute the sum along with geodesics
+        if(r == inf) {
+            sum = inf;
+        }
+        else if(sum != inf) {
+            sum += r;
         }
-
-        // return the average of averages.
-        return sum / Result(num_vertices(g));
     }
 
-    template <typename Graph, typename DistanceMatrixMap, typename GeodesicMap>
-    inline typename property_traits<GeodesicMap>::value_type
-    all_mean_geodesics(const Graph& g, DistanceMatrixMap dist, GeodesicMap geo)
-    {
-        function_requires< GraphConcept<Graph> >();
-        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
-        function_requires< ReadablePropertyMapConcept<DistanceMatrixMap,Vertex> >();
-        typedef typename property_traits<DistanceMatrixMap>::value_type DistanceMap;
-        function_requires< WritablePropertyMapConcept<GeodesicMap,Vertex> >();
-        typedef typename property_traits<GeodesicMap>::value_type Result;
+    // return the average of averages.
+    return sum / Result(num_vertices(g));
+}
 
-        return all_mean_geodesics(g, dist, geo, measure_mean_geodesic<Result>(g, DistanceMap()));
-    }
+template <typename Graph, typename DistanceMatrixMap, typename GeodesicMap>
+inline typename property_traits<GeodesicMap>::value_type
+all_mean_geodesics(const Graph& g, DistanceMatrixMap dist, GeodesicMap geo)
+{
+    function_requires< GraphConcept<Graph> >();
+    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+    function_requires< ReadablePropertyMapConcept<DistanceMatrixMap,Vertex> >();
+    typedef typename property_traits<DistanceMatrixMap>::value_type DistanceMap;
+    function_requires< WritablePropertyMapConcept<GeodesicMap,Vertex> >();
+    typedef typename property_traits<GeodesicMap>::value_type Result;
 
+    return all_mean_geodesics(g, dist, geo, measure_mean_geodesic<Result>(g, DistanceMap()));
+}
 
-    template <typename Graph, typename GeodesicMap, typename Measure>
-    inline typename Measure::result_type
-    small_world_distance(const Graph& g, GeodesicMap geo, Measure measure)
-    {
-        function_requires< DistanceMeasureConcept<Measure,Graph> >();
-        typedef typename Measure::result_type Result;
 
-        Result sum = detail::combine_distances(g, geo, std::plus<Result>(), Result(0));
-        return measure(sum, g);
-    }
+template <typename Graph, typename GeodesicMap, typename Measure>
+inline typename Measure::result_type
+small_world_distance(const Graph& g, GeodesicMap geo, Measure measure)
+{
+    function_requires< DistanceMeasureConcept<Measure,Graph> >();
+    typedef typename Measure::result_type Result;
+
+    Result sum = detail::combine_distances(g, geo, std::plus<Result>(), Result(0));
+    return measure(sum, g);
+}
+
+template <typename Graph, typename GeodesicMap>
+inline typename property_traits<GeodesicMap>::value_type
+small_world_distance(const Graph& g, GeodesicMap geo)
+{ return small_world_distance(g, geo, measure_graph_mean_geodesic(g, geo)); }
 
-    template <typename Graph, typename GeodesicMap>
-    inline typename property_traits<GeodesicMap>::value_type
-    small_world_distance(const Graph& g, GeodesicMap geo)
-    {
-        return small_world_distance(g, geo, measure_graph_mean_geodesic(g, geo));
-    }
 }
 
 #endif

Modified: trunk/libs/graph/test/Jamfile.v2
==============================================================================
--- trunk/libs/graph/test/Jamfile.v2	(original)
+++ trunk/libs/graph/test/Jamfile.v2	2009-02-08 10:40:33 EST (Sun, 08 Feb 2009)
@@ -102,6 +102,7 @@
     [ run tiernan_all_cycles.cpp ]
     [ run closeness_centrality.cpp ]
     [ run degree_centrality.cpp ]
+    [ run mean_geodesic.cpp ]
 
     $(optional_tests)
     ;

Copied: trunk/libs/graph/test/mean_geodesic.cpp (from r51086, /sandbox/SOC/2007/graphs/libs/graph/test/runtime/mean_geodesic.cpp)
==============================================================================
--- /sandbox/SOC/2007/graphs/libs/graph/test/runtime/mean_geodesic.cpp	(original)
+++ trunk/libs/graph/test/mean_geodesic.cpp	2009-02-08 10:40:33 EST (Sun, 08 Feb 2009)
@@ -1,4 +1,4 @@
-// (C) Copyright Andrew Sutton 2007
+// (C) Copyright 2007-2009 Andrew Sutton
 //
 // Use, modification and distribution are subject to the
 // Boost Software License, Version 1.0 (See accompanying file
@@ -9,7 +9,7 @@
 #include <boost/graph/undirected_graph.hpp>
 #include <boost/graph/directed_graph.hpp>
 #include <boost/graph/exterior_property.hpp>
-#include <boost/graph/constant_property_map.hpp>
+#include <boost/graph/property_maps/constant_property_map.hpp>
 
 #include <boost/graph/floyd_warshall_shortest.hpp>
 #include <boost/graph/geodesic_distance.hpp>
@@ -29,8 +29,7 @@
 };
 
 template <typename Graph>
-void build_graph(Graph& g,
-                 typename vertex_vector<Graph>::type& v)
+void build_graph(Graph& g, typename vertex_vector<Graph>::type& v)
 {
     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
 
@@ -54,7 +53,7 @@
     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
     typedef typename graph_traits<Graph>::edge_descriptor Edge;
 
-    typedef exterior_vertex_property<Graph, float> CentralityProperty;
+    typedef exterior_vertex_property<Graph, double> CentralityProperty;
     typedef typename CentralityProperty::container_type CentralityContainer;
     typedef typename CentralityProperty::map_type CentralityMap;
 
@@ -77,15 +76,15 @@
     WeightMap wm(1);
 
     floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
-    float geo1 = all_mean_geodesics(g, dm, cm);
-    float geo2 = small_world_distance(g, cm);
+    double geo1 = all_mean_geodesics(g, dm, cm);
+    double geo2 = small_world_distance(g, cm);
 
-    BOOST_ASSERT(cm[v[0]] == float(5)/4);
-    BOOST_ASSERT(cm[v[1]] == float(7)/4);
-    BOOST_ASSERT(cm[v[2]] == float(7)/4);
-    BOOST_ASSERT(cm[v[3]] == float(9)/4);
-    BOOST_ASSERT(cm[v[4]] == float(6)/4);
-    BOOST_ASSERT(geo1 == float(34)/20);
+    BOOST_ASSERT(cm[v[0]] == double(5)/4);
+    BOOST_ASSERT(cm[v[1]] == double(7)/4);
+    BOOST_ASSERT(cm[v[2]] == double(7)/4);
+    BOOST_ASSERT(cm[v[3]] == double(9)/4);
+    BOOST_ASSERT(cm[v[4]] == double(6)/4);
+    BOOST_ASSERT(geo1 == double(34)/20);
     BOOST_ASSERT(geo1 == geo2);
 }
 
@@ -95,7 +94,7 @@
     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
     typedef typename graph_traits<Graph>::edge_descriptor Edge;
 
-    typedef exterior_vertex_property<Graph, float> CentralityProperty;
+    typedef exterior_vertex_property<Graph, double> CentralityProperty;
     typedef typename CentralityProperty::container_type CentralityContainer;
     typedef typename CentralityProperty::map_type CentralityMap;
 
@@ -118,14 +117,14 @@
     WeightMap wm(1);
 
     floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
-    float geo1 = all_mean_geodesics(g, dm, cm);
-    float geo2 = small_world_distance(g, cm);
+    double geo1 = all_mean_geodesics(g, dm, cm);
+    double geo2 = small_world_distance(g, cm);
 
-    float inf = numeric_values<float>::infinity();
+    double inf = numeric_values<double>::infinity();
     BOOST_ASSERT(cm[v[0]] == inf);
     BOOST_ASSERT(cm[v[1]] == inf);
     BOOST_ASSERT(cm[v[2]] == inf);
-    BOOST_ASSERT(cm[v[3]] == float(10)/4);
+    BOOST_ASSERT(cm[v[3]] == double(10)/4);
     BOOST_ASSERT(cm[v[4]] == inf);
     BOOST_ASSERT(geo1 == inf);
     BOOST_ASSERT(geo1 == geo2);