From: asutton_at_[hidden]
Date: 2007-08-01 13:45:47
Author: asutton
Date: 2007-08-01 13:45:46 EDT (Wed, 01 Aug 2007)
New Revision: 38340
URL: http://svn.boost.org/trac/boost/changeset/38340
Log:
Tidying things up a bit
Text files modified:
sandbox/SOC/2007/graphs/boost/graph/clique.hpp | 2
sandbox/SOC/2007/graphs/boost/graph/closeness_centrality.hpp | 8 +-
sandbox/SOC/2007/graphs/boost/graph/cycle.hpp | 26 ++++++----
sandbox/SOC/2007/graphs/boost/graph/degree_centrality.hpp | 37 +++++----------
sandbox/SOC/2007/graphs/boost/graph/eccentricity.hpp | 69 +++++++++--------------------
sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp | 8 +++
sandbox/SOC/2007/graphs/boost/graph/geodesic_distance.hpp | 93 ++++++++++++++-------------------------
7 files changed, 95 insertions(+), 148 deletions(-)
Modified: sandbox/SOC/2007/graphs/boost/graph/clique.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/clique.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/clique.hpp 2007-08-01 13:45:46 EDT (Wed, 01 Aug 2007)
@@ -206,7 +206,7 @@
template <typename Graph, typename Visitor>
inline void
- bron_kerbosch_visit_cliques(const Graph& g, Visitor vis)
+ bron_kerbosch_all_cliques(const Graph& g, Visitor vis)
{
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
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 13:45:46 EDT (Wed, 01 Aug 2007)
@@ -119,8 +119,8 @@
typename Measure>
inline void
closeness_centrality(const Graph& g,
- DistanceMatrix& dist,
- CentralityMap& cent,
+ const DistanceMatrix& dist,
+ CentralityMap cent,
Measure measure)
{
typedef typename property_matrix_traits<DistanceMatrix>::value_type Distance;
@@ -136,8 +136,8 @@
typename CentralityMap>
inline void
closeness_centrality(const Graph& g,
- DistanceMatrix& dist,
- CentralityMap& cent)
+ const DistanceMatrix& dist,
+ CentralityMap cent)
{
typedef typename property_matrix_traits<DistanceMatrix>::value_type Distance;
typedef typename exterior_vertex_property<Graph, Distance>::map_type DistanceMap;
Modified: sandbox/SOC/2007/graphs/boost/graph/cycle.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/cycle.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/cycle.hpp 2007-08-01 13:45:46 EDT (Wed, 01 Aug 2007)
@@ -243,11 +243,11 @@
template <typename Graph, typename Visitor>
inline void
- visit_cycles_at_vertex(const Graph& g,
- typename graph_traits<Graph>::vertex_descriptor v,
- Visitor vis,
- std::size_t maxlen,
- std::size_t minlen)
+ all_cycles_at_vertex(const Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor v,
+ Visitor vis,
+ std::size_t maxlen,
+ std::size_t minlen)
{
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
typedef typename graph_traits<Graph>::edge_descriptor Edge;
@@ -294,18 +294,24 @@
template <typename Graph, typename Visitor>
inline void
- tiernan_visit_cycles(const Graph& g,
- Visitor vis,
- std::size_t maxlen = std::numeric_limits<std::size_t>::max(),
- std::size_t minlen = 2)
+ tiernan_all_cycles(const Graph& g, Visitor vis,
+ std::size_t maxlen,
+ std::size_t minlen)
{
typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
VertexIterator i, end;
for(tie(i, end) = vertices(g); i != end; ++i) {
- detail::visit_cycles_at_vertex(g, *i, vis, maxlen, minlen);
+ detail::all_cycles_at_vertex(g, *i, vis, maxlen, minlen);
}
}
+
+ template <typename Graph, typename Visitor>
+ inline void
+ tiernan_all_cycles(const Graph& g, Visitor vis)
+ {
+ tiernan_all_cycles(g, vis, 2, std::numeric_limits<std::size_t>::max());
+ }
}
#endif
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 13:45:46 EDT (Wed, 01 Aug 2007)
@@ -12,7 +12,7 @@
template <typename Graph>
struct degree_centrality_measure
{
- typedef typename graph_traits<Graph>::degree_size_type value_type;
+ typedef typename graph_traits<Graph>::degree_size_type degree_type;
typedef typename graph_traits<Graph>::vertex_descriptor vertex_type;
};
@@ -21,25 +21,12 @@
: public degree_centrality_measure<Graph>
{
typedef degree_centrality_measure<Graph> base_type;
- typedef typename base_type::value_type value_type;
+ typedef typename base_type::degree_type degree_type;
typedef typename base_type::vertex_type vertex_type;
- inline value_type operator ()(const Graph& g, vertex_type v)
- {
- 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_tag)
- {
- return degree(v, g);
- }
-
- inline value_type
- get_degree(const Graph& g, vertex_type v, directed_tag)
+ inline degree_type operator ()(vertex_type v, const Graph& g)
{
+ // This defaults to degree() for undirected graphs
return out_degree(v, g);
}
};
@@ -53,12 +40,12 @@
template <typename Graph, typename Measure>
- inline typename graph_traits<Graph>::degree_size_type
+ inline typename Measure::degree_type
vertex_degree_centrality(const Graph& g,
typename graph_traits<Graph>::vertex_descriptor v,
Measure measure)
{
- return measure(g, v);
+ return measure(v, g);
}
template <typename Graph>
@@ -72,9 +59,10 @@
template <typename Graph, typename CentralityMap, typename Measure>
- void degree_centrality(const Graph& g,
- CentralityMap cent,
- Measure measure)
+ inline void
+ degree_centrality(const Graph& g,
+ CentralityMap cent,
+ Measure measure)
{
typename graph_traits<Graph>::vertex_iterator i, end;
for(tie(i, end) = vertices(g); i != end; ++i) {
@@ -83,12 +71,11 @@
}
template <typename Graph, typename CentralityMap>
- void degree_centrality(const Graph& g,
- CentralityMap cent)
+ inline void degree_centrality(const Graph& g,
+ CentralityMap cent)
{
degree_centrality(g, cent, measure_basic_degree_centrality(g));
}
-
}
#endif
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-01 13:45:46 EDT (Wed, 01 Aug 2007)
@@ -7,67 +7,42 @@
#ifndef BOOST_GRAPH_ECCENTRICITY_HPP
#define BOOST_GRAPH_ECCENTRICITY_HPP
-#include <boost/graph/detail/combine_distances.hpp>
+#include <boost/graph/detail/geodesic.hpp>
namespace boost
{
- template <
- typename Graph,
- typename DistanceMap,
- typename Combinator>
+ template <typename Graph,
+ typename DistanceMap,
+ typename Combinator>
inline typename property_traits<DistanceMap>::value_type
- eccentricity(const Graph& g,
- dist,
- Combinator combine,
- typename property_traits<DistanceMap>::value_type zero = T(),
- typename property_traits<DistanceMap>::value_type inf = std::numeric_limits<T>::max())
+ vertex_eccentricity(const Graph& g,
+ DistanceMap dist,
+ Combinator combine)
{
- return detail::combine_distances(g, dist, combine, zero, inf);
+ typedef typename property_traits<DistanceMap>::value_type Distance;
+ return detail::combine_distances(g, dist, combine,
+ numeric_values<Distance>());
}
template <typename Graph, typename DistanceMap>
- inline T
- eccentricity(const Graph& g, DistanceMap dist)
- {
- return eccentricity<T>(g, dist, std::plus<T>());
- }
-
- template <typename Graph, typename DistanceMap>
- inline double
- mean_geodesic(const Graph& g, DistanceMap dist)
- {
- return mean_geodesic<double>(g, dist);
- }
-
-
- template <typename Graph, typename DistanceMap>
inline typename property_traits<DistanceMap>::value_type
- eccentricity(const Graph& g,
- DistanceMap dist)
+ vertex_eccentricity(const Graph& g, DistanceMap dist)
{
- typename property_traits<DistanceMap>::value_type ret(0);
- typename graph_traits<Graph>::vertex_iterator i, end;
- for(tie(i, end) = vertices(g); i != end; ++i) {
- ret = std::max(ret, dist[*i]);
- }
- return ret;
+ typedef typename property_traits<DistanceMap>::value_type Distance;
+ return vertex_eccentricity(g, dist, detail::maximize<Distance>());
}
- // The computation of eccentricities, radius and diameter are all
- // closely related. Basically, these computations can be run at
- // the same time - compute eccentricities of all vertices, and
- // the radius and diameter of the graph.
-
template <typename Graph, typename DistanceMatrix, typename EccentricityMap>
- void
- eccentricities(const Graph& g, DistanceMatrix& dist, EccentricityMap ecc)
+ inline void
+ eccentricity(const Graph& g, const DistanceMatrix& dist, EccentricityMap ecc)
{
- typename graph_traits<Graph>::vertex_iterator i, j, end;
+ typedef typename property_matrix_traits<DistanceMatrix>::value_type Distance;
+ typedef typename exterior_vertex_property<Graph, Distance>::map_type DistanceMap;
+ typename graph_traits<Graph>::vertex_iterator i, end;
for(tie(i, end) = vertices(g); i != end; ++i) {
- // compute the max eccentricity "in-place"
- typename property_traits<EccentricityMap>::value_type& ei = ecc[*i];
- for(j = vertices(g).first; j != end; ++j) {
- ei = std::max(ei, dist[*i][*j]);
- }
+ ecc[*i] = vertex_eccentricity(g, DistanceMap(dist[*i]));
}
}
+}
+
+#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 13:45:46 EDT (Wed, 01 Aug 2007)
@@ -121,7 +121,10 @@
inline typename matrix_type::reference operator [](key_type k)
{ return m_matrix[k]; }
- matrix_type m_matrix;
+ inline typename matrix_type::reference operator [](key_type k) const
+ { return m_matrix[k]; }
+
+ mutable matrix_type m_matrix;
};
// There's a strange side-effect using the []'s of a hashtable in
@@ -155,6 +158,9 @@
inline typename matrix_type::mapped_type& operator [](key_type k)
{ return m_matrix[k]; }
+ inline typename matrix_type::mapped_type& operator [](key_type k) const
+ { return m_matrix[k]; }
+
mutable matrix_type m_matrix;
};
}
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-01 13:45:46 EDT (Wed, 01 Aug 2007)
@@ -20,14 +20,14 @@
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)
+ result_type operator ()(distance_type d, const Graph& g)
{
typedef result_type T;
return
(d == base_type::infinite_distance()) ?
- base_type::infinite_result() : T(d) / T(n);
+ base_type::infinite_result() :
+ T(d) / T(num_vertices(g));
}
};
@@ -46,19 +46,23 @@
}
- template <typename Graph, typename DistanceType, typename ResultType>
+ // 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.
+ template <typename Graph, typename DistanceType>
struct mean_graph_distance_measure
- : public geodesic_measure<Graph, DistanceType, ResultType>
+ : public geodesic_measure<Graph, DistanceType, DistanceType>
{
- typedef geodesic_measure<Graph, DistanceType, ResultType> base_type;
+ typedef geodesic_measure<Graph, DistanceType, DistanceType> 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)
+ inline result_type operator ()(distance_type d, const Graph& g)
{
typename graph_traits<Graph>::directed_category cat;
- return this->average(d, n, cat);
+ return this->average(d, num_vertices(g), cat);
}
private:
@@ -86,16 +90,13 @@
}
};
- 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>
+ 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>();
+ }
template <typename Graph,
typename DistanceMap,
@@ -111,7 +112,7 @@
typedef typename Measure::distance_values DistanceValues;
Distance n = detail::combine_distances(g, dist, combine,
DistanceValues());
- return measure(n, num_vertices(g));
+ return measure(n, g);
}
template <typename Graph,
@@ -147,11 +148,10 @@
typename Measure>
inline void
mean_geodesic(const Graph& g,
- DistanceMatrix& dist,
- GeodesicMap& geo,
+ const 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);
@@ -163,8 +163,8 @@
typename GeodesicMap>
inline void
mean_geodesic(const Graph& g,
- DistanceMatrix& dist,
- GeodesicMap& geo)
+ const DistanceMatrix& dist,
+ GeodesicMap geo)
{
typedef typename property_matrix_traits<DistanceMatrix>::value_type Distance;
typedef typename exterior_vertex_property<Graph, Distance>::map_type DistanceMap;
@@ -173,48 +173,21 @@
measure_mean_geodesic<Result>(g, DistanceMap()));
}
- template <typename Graph,
- typename DistanceMatrix,
- typename Measure>
+
+ template <typename Graph, typename GeodesicMap, typename Measure>
inline typename Measure::result_type
- graph_mean_geodesic(const Graph& g,
- DistanceMatrix& dist,
- Measure measure)
+ graph_mean_geodesic(const Graph& g, GeodesicMap geo, 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));
+ T sum = detail::combine_distances(g, geo, std::plus<T>(), numeric_values<T>());
+ return measure(sum, 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)
+ template <typename Graph, typename GeodesicMap>
+ inline typename property_traits<GeodesicMap>::value_type
+ graph_mean_geodesic(const Graph& g, GeodesicMap geo)
{
- return graph_mean_geodesic<float>(g, dist);
+ return graph_mean_geodesic(g, geo, measure_graph_mean_geodesic(g, geo));
}
}