|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2007-08-17 15:21:25
Author: asutton
Date: 2007-08-17 15:21:24 EDT (Fri, 17 Aug 2007)
New Revision: 38749
URL: http://svn.boost.org/trac/boost/changeset/38749
Log:
Renamed almost every function in these files
Text files modified:
sandbox/SOC/2007/graphs/boost/graph/closeness_centrality.hpp | 54 ++++++++++++----------------
sandbox/SOC/2007/graphs/boost/graph/degree_centrality.hpp | 55 +++++++++++++++++++++++-------
sandbox/SOC/2007/graphs/boost/graph/eccentricity.hpp | 30 ++++++++++------
sandbox/SOC/2007/graphs/boost/graph/geodesic_distance.hpp | 73 +++++++++++++++++++++++----------------
4 files changed, 126 insertions(+), 86 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-17 15:21:24 EDT (Fri, 17 Aug 2007)
@@ -72,15 +72,13 @@
return closeness_measure<Graph, Distance, T, Reciprocal>();
}
- template <typename Graph,
- typename DistanceMap,
- typename Measure,
- typename Combinator>
+ template <typename Graph, typename DistanceMap,
+ typename Measure, typename Combinator>
inline typename Measure::result_type
- vertex_closeness_centrality(const Graph& g,
- DistanceMap dist,
- Measure measure,
- Combinator combine)
+ closeness_centrality(const Graph& g,
+ DistanceMap dist,
+ Measure measure,
+ Combinator combine)
{
function_requires< VertexListGraphConcept<Graph> >();
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
@@ -91,40 +89,34 @@
// NOTE: we could further reduce the requirements on this function
// by removing the call to num_vertices() and passing that as a
- // parameter.
+ // parameter. I don't know if its worthwhile...
Distance n = detail::combine_distances(g, dist, combine, Distance(0));
return measure(n, g);
}
- template <typename Graph,
- typename DistanceMap,
- typename Measure>
+ template <typename Graph, typename DistanceMap, typename Measure>
inline typename Measure::result_type
- vertex_closeness_centrality(const Graph& g,
- DistanceMap dist,
- Measure measure)
+ closeness_centrality(const Graph& g, DistanceMap dist, Measure measure)
{
function_requires< GraphConcept<Graph> >();
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
function_requires< ReadablePropertyMapConcept<DistanceMap,Vertex> >();
typedef typename property_traits<DistanceMap>::value_type Distance;
- return vertex_closeness_centrality(g, dist, measure, std::plus<Distance>());
+ return closeness_centrality(g, dist, measure, std::plus<Distance>());
}
template <typename Graph, typename DistanceMap>
- inline float
- vertex_closeness_centrality(const Graph& g, DistanceMap dist)
+ inline float closeness_centrality(const Graph& g, DistanceMap dist)
{
- return vertex_closeness_centrality(g, dist, measure_closeness(g, dist));
+ return closeness_centrality(g, dist, measure_closeness(g, dist));
}
template <typename T, typename Graph, typename DistanceMap>
- inline T
- vertex_closeness_centrality(const Graph& g, DistanceMap dist)
+ inline T closeness_centrality(const Graph& g, DistanceMap dist)
{
- return vertex_closeness_centrality(g, dist, measure_closeness<T>(g, dist));
+ return closeness_centrality(g, dist, measure_closeness<T>(g, dist));
}
template <typename Graph,
@@ -132,10 +124,10 @@
typename CentralityMap,
typename Measure>
inline void
- closeness_centrality(const Graph& g,
- const DistanceMatrixMap& dist,
- CentralityMap cent,
- Measure measure)
+ all_closeness_centralities(const Graph& g,
+ DistanceMatrixMap dist,
+ CentralityMap cent,
+ Measure measure)
{
function_requires< VertexListGraphConcept<Graph> >();
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
@@ -149,7 +141,7 @@
typename graph_traits<Graph>::vertex_iterator i, end;
for(tie(i, end) = vertices(g); i != end; ++i) {
DistanceMap dm = get(dist, *i);
- Centrality c = vertex_closeness_centrality(g, dm, measure);
+ Centrality c = closeness_centrality(g, dm, measure);
put(cent, *i, c);
}
}
@@ -158,9 +150,9 @@
typename DistanceMatrixMap,
typename CentralityMap>
inline void
- closeness_centrality(const Graph& g,
- const DistanceMatrixMap& dist,
- CentralityMap cent)
+ all_closeness_centralities(const Graph& g,
+ DistanceMatrixMap dist,
+ CentralityMap cent)
{
function_requires< GraphConcept<Graph> >();
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
@@ -170,7 +162,7 @@
typedef typename property_traits<DistanceMap>::value_type Distance;
typedef typename property_traits<CentralityMap>::value_type Result;
- closeness_centrality(g, dist, cent, measure_closeness<Result>(g, DistanceMap()));
+ all_closeness_centralities(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-17 15:21:24 EDT (Fri, 17 Aug 2007)
@@ -62,9 +62,7 @@
template <typename Graph, typename Vertex, typename Measure>
inline typename Measure::degree_type
- vertex_degree_centrality(const Graph& g,
- Vertex v,
- Measure measure)
+ degree_centrality(const Graph& g, Vertex v, Measure measure)
{
function_requires< DegreeMeasureConcept<Measure, Graph> >();
return measure(v, g);
@@ -72,18 +70,34 @@
template <typename Graph, typename Vertex>
inline typename graph_traits<Graph>::degree_size_type
- vertex_degree_centrality(const Graph& g,
- Vertex v)
+ degree_centrality(const Graph& g, Vertex v)
{
- return vertex_degree_centrality(g, v, measure_influence(g));
+ return degree_centrality(g, v, measure_influence(g));
+ }
+
+
+ // These are just alias functions, intended to provide a more
+ // "semantic" interface.
+
+ template <typename Graph, typename Vertex>
+ inline typename graph_traits<Graph>::degree_size_type
+ influence(const Graph& g, Vertex v)
+ {
+ return degree_centrality(g, v, measure_influence(g));
+ }
+
+
+ template <typename Graph, typename Vertex>
+ inline typename graph_traits<Graph>::degree_size_type
+ prestige(const Graph& g, Vertex v)
+ {
+ return degree_centrality(g, v, measure_prestige(g));
}
template <typename Graph, typename CentralityMap, typename Measure>
inline void
- degree_centrality(const Graph& g,
- CentralityMap cent,
- Measure measure)
+ all_degree_centralities(const Graph& g, CentralityMap cent, Measure measure)
{
function_requires< VertexListGraphConcept<Graph> >();
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
@@ -93,16 +107,31 @@
VertexIterator i, end;
for(tie(i, end) = vertices(g); i != end; ++i) {
- Centrality c = vertex_degree_centrality(g, *i, measure);
+ Centrality c = degree_centrality(g, *i, measure);
put(cent, *i, c);
}
}
template <typename Graph, typename CentralityMap>
- inline void degree_centrality(const Graph& g,
- CentralityMap cent)
+ inline void all_degree_centralities(const Graph& g, CentralityMap cent)
+ {
+ all_degree_centralities(g, cent, measure_influence(g));
+ }
+
+ // More helper functions for computing influence and prestige.
+ // I hate the names of these functions, but influence and prestige
+ // don't pluralize too well.
+
+ template <typename Graph, typename CentralityMap>
+ inline void all_influence_values(const Graph& g, CentralityMap cent)
+ {
+ all_degree_centralities(g, cent, measure_influence(g));
+ }
+
+ template <typename Graph, typename CentralityMap>
+ inline void all_prestige_values(const Graph& g, CentralityMap cent)
{
- degree_centrality(g, cent, measure_influence(g));
+ all_degree_centralities(g, cent, measure_prestige(g));
}
}
Modified: sandbox/SOC/2007/graphs/boost/graph/eccentricity.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/eccentricity.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/eccentricity.hpp 2007-08-17 15:21:24 EDT (Fri, 17 Aug 2007)
@@ -16,9 +16,7 @@
typename DistanceMap,
typename Combinator>
inline typename property_traits<DistanceMap>::value_type
- vertex_eccentricity(const Graph& g,
- DistanceMap dist,
- Combinator combine)
+ eccentricity(const Graph& g, DistanceMap dist, Combinator combine)
{
function_requires< GraphConcept<Graph> >();
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
@@ -30,19 +28,20 @@
template <typename Graph, typename DistanceMap>
inline typename property_traits<DistanceMap>::value_type
- vertex_eccentricity(const Graph& g, DistanceMap dist)
+ eccentricity(const Graph& g, DistanceMap dist)
{
function_requires< GraphConcept<Graph> >();
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
function_requires< ReadablePropertyMapConcept<DistanceMap,Vertex> >();
typedef typename property_traits<DistanceMap>::value_type Distance;
- return vertex_eccentricity(g, dist, detail::maximize<Distance>());
+ return eccentricity(g, dist, detail::maximize<Distance>());
}
template <typename Graph, typename DistanceMatrix, typename EccentricityMap>
- inline void
- eccentricity(const Graph& g, const DistanceMatrix& dist, EccentricityMap ecc)
+ inline std::pair<typename property_traits<EccentricityMap>::value_type,
+ typename property_traits<EccentricityMap>::value_type>
+ all_eccentricities(const Graph& g, const DistanceMatrix& dist, EccentricityMap ecc)
{
function_requires< VertexListGraphConcept<Graph> >();
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
@@ -52,18 +51,27 @@
function_requires< WritablePropertyMapConcept<EccentricityMap,Vertex> >();
typedef typename property_traits<EccentricityMap>::value_type Eccentricity;
+ Eccentricity
+ r = numeric_values<Eccentricity>::infinity(),
+ d = numeric_values<Eccentricity>::zero();
VertexIterator i, end;
+ tie(i, end) = vertices(g);
for(tie(i, end) = vertices(g); i != end; ++i) {
DistanceMap dm = get(dist, *i);
- Eccentricity e = vertex_eccentricity(g, dm);
+ Eccentricity e = eccentricity(g, dm);
put(ecc, *i, e);
+
+ // track the radius and diameter at the same time
+ r = std::min(r, e);
+ d = std::max(d, e);
}
+ return make_pair(r, d);
}
template <typename Graph, typename EccentricityMap>
inline typename property_traits<EccentricityMap>::value_type
- graph_radius(const Graph& g, EccentricityMap ecc)
+ radius(const Graph& g, EccentricityMap ecc)
{
function_requires< VertexListGraphConcept<Graph> >();
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
@@ -84,7 +92,7 @@
template <typename Graph, typename EccentricityMap>
inline typename property_traits<EccentricityMap>::value_type
- graph_diameter(const Graph& g, EccentricityMap ecc)
+ diameter(const Graph& g, EccentricityMap ecc)
{
function_requires< VertexListGraphConcept<Graph> >();
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
@@ -106,7 +114,7 @@
template <typename Graph, typename EccentricityMap>
inline std::pair<typename property_traits<EccentricityMap>::value_type,
typename property_traits<EccentricityMap>::value_type>
- graph_radius_diameter(const Graph& g, EccentricityMap ecc)
+ radius_diameter(const Graph& g, EccentricityMap ecc)
{
function_requires< VertexListGraphConcept<Graph> >();
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
Modified: sandbox/SOC/2007/graphs/boost/graph/geodesic_distance.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/geodesic_distance.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/geodesic_distance.hpp 2007-08-17 15:21:24 EDT (Fri, 17 Aug 2007)
@@ -12,7 +12,6 @@
namespace boost
{
-
template <typename Graph,
typename DistanceType,
typename ResultType,
@@ -95,10 +94,10 @@
typename Measure,
typename Combinator>
inline typename Measure::result_type
- vertex_mean_geodesic(const Graph& g,
- DistanceMap dist,
- Measure measure,
- Combinator combine)
+ mean_geodesic(const Graph& g,
+ DistanceMap dist,
+ Measure measure,
+ Combinator combine)
{
function_requires< DistanceMeasureConcept<Measure,Graph> >();
typedef typename Measure::distance_type Distance;
@@ -111,27 +110,26 @@
typename DistanceMap,
typename Measure>
inline typename Measure::result_type
- vertex_mean_geodesic(const Graph& g,
- DistanceMap dist,
- Measure measure)
+ mean_geodesic(const Graph& g, DistanceMap dist, Measure measure)
{
function_requires< DistanceMeasureConcept<Measure,Graph> >();
typedef typename Measure::distance_type Distance;
- return vertex_mean_geodesic(g, dist, measure, std::plus<Distance>());
+
+ return mean_geodesic(g, dist, measure, std::plus<Distance>());
}
template <typename Graph, typename DistanceMap>
inline float
- vertex_mean_geodesic(const Graph& g, DistanceMap dist)
+ mean_geodesic(const Graph& g, DistanceMap dist)
{
- return vertex_mean_geodesic(g, dist, measure_mean_geodesic(g, dist));
+ return 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)
+ mean_geodesic(const Graph& g, DistanceMap dist)
{
- return vertex_mean_geodesic(g, dist, measure_mean_geodesic<T>(g, dist));
+ return mean_geodesic(g, dist, measure_mean_geodesic<T>(g, dist));
}
@@ -139,11 +137,11 @@
typename DistanceMatrixMap,
typename GeodesicMap,
typename Measure>
- inline void
- mean_geodesic(const Graph& g,
- const DistanceMatrixMap& dist,
- GeodesicMap geo,
- Measure 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;
@@ -153,22 +151,36 @@
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 = vertex_mean_geodesic(g, dm, measure);
+ 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 void
- mean_geodesic(const Graph& g,
- const DistanceMatrixMap& dist,
- GeodesicMap geo)
+ 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;
@@ -177,14 +189,13 @@
function_requires< WritablePropertyMapConcept<GeodesicMap,Vertex> >();
typedef typename property_traits<GeodesicMap>::value_type Result;
- mean_geodesic(g, dist, geo,
- measure_mean_geodesic<Result>(g, DistanceMap()));
+ 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
- graph_mean_geodesic(const Graph& g, GeodesicMap geo, Measure measure)
+ small_world_distance(const Graph& g, GeodesicMap geo, Measure measure)
{
function_requires< DistanceMeasureConcept<Measure,Graph> >();
typedef typename Measure::result_type Result;
@@ -195,9 +206,9 @@
template <typename Graph, typename GeodesicMap>
inline typename property_traits<GeodesicMap>::value_type
- graph_mean_geodesic(const Graph& g, GeodesicMap geo)
+ small_world_distance(const Graph& g, GeodesicMap geo)
{
- return graph_mean_geodesic(g, geo, measure_graph_mean_geodesic(g, geo));
+ return small_world_distance(g, geo, measure_graph_mean_geodesic(g, geo));
}
}
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk