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);