|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2007-08-11 11:53:34
Author: asutton
Date: 2007-08-11 11:53:31 EDT (Sat, 11 Aug 2007)
New Revision: 38601
URL: http://svn.boost.org/trac/boost/changeset/38601
Log:
Rewrote the property matrix stuff so that it's now a property map
over a matrix - specialized read only property map that is.
Propogated matrix changes to relevant files
Started addding new graph concepts for explicit concept checking.
Added concept checking code to degree and closeness centrality.
Text files modified:
sandbox/SOC/2007/graphs/boost/graph/closeness_centrality.hpp | 55 ++++++++++++++++++++++++++++--------
sandbox/SOC/2007/graphs/boost/graph/constant_property_map.hpp | 20 ++++++------
sandbox/SOC/2007/graphs/boost/graph/container_property_map.hpp | 59 ++-------------------------------------
sandbox/SOC/2007/graphs/boost/graph/degree_centrality.hpp | 26 ++++++++++------
sandbox/SOC/2007/graphs/boost/graph/eccentricity.hpp | 7 ++--
sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp | 59 ++++++++++++++++-----------------------
sandbox/SOC/2007/graphs/boost/graph/geodesic_distance.hpp | 9 ++---
sandbox/SOC/2007/graphs/boost/graph/new_graph_concepts.hpp | 29 +++++++++++++++++++
8 files changed, 132 insertions(+), 132 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-11 11:53:31 EDT (Sat, 11 Aug 2007)
@@ -14,19 +14,22 @@
{
template <
typename Graph,
- typename DistanceNumbers,
- typename ResultNumbers,
- typename Reciprocal = detail::reciprocal<typename ResultNumbers::value_type>
+ typename DistanceType,
+ typename ResultType,
+ typename Reciprocal = detail::reciprocal<ResultType>
>
struct closeness_measure
- : public geodesic_measure<Graph, DistanceNumbers, ResultNumbers>
+ : public geodesic_measure<Graph, DistanceType, ResultType>
{
- typedef geodesic_measure< Graph, DistanceNumbers, ResultNumbers> base_type;
+ 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&)
{
+ function_requires< NumericValueConcept<DistanceType> >();
+ function_requires< NumericValueConcept<ResultType> >();
+ function_requires< AdaptableUnaryFunctionConcept<Reciprocal,ResultType,ResultType> >();
Reciprocal r;
return
(d == base_type::infinite_distance()) ?
@@ -80,10 +83,19 @@
Measure measure,
Combinator combine)
{
+ function_requires< VertexListGraphConcept<Graph> >();
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ function_requires< ReadablePropertyMapConcept<DistanceMap,Vertex> >();
typedef typename property_traits<DistanceMap>::value_type Distance;
- typedef numeric_values<Distance> DistanceValues;
- Distance n = detail::combine_distances(g, dist, combine, DistanceValues());
- return measure(n, num_vertices(g));
+ function_requires< NumericValueConcept<Distance> >();
+ function_requires< DistanceMeasureConcept<Measure,Graph> >();
+
+ // NOTE: we could further reduce the requirements on this function
+ // by removing the call to num_vertices() and passing that as a
+ // parameter.
+
+ Distance n = detail::combine_distances(g, dist, combine, Distance(0));
+ return measure(n, g);
}
template <typename Graph,
@@ -94,7 +106,11 @@
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>());
}
@@ -122,12 +138,20 @@
CentralityMap cent,
Measure measure)
{
- typedef typename property_matrix_traits<DistanceMatrix>::value_type Distance;
- typedef typename exterior_vertex_property<Graph, Distance>::map_type DistanceMap;
+ function_requires< VertexListGraphConcept<Graph> >();
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ function_requires< ReadablePropertyMapConcept<DistanceMatrix,Vertex> >();
+ typedef typename property_traits<DistanceMatrix>::value_type DistanceMap;
+ function_requires< ReadablePropertyMapConcept<DistanceMap,Vertex> >();
+ function_requires< WritablePropertyMapConcept<CentralityMap,Vertex> >();
+ typedef typename property_traits<DistanceMap>::value_type Distance;
+ typedef typename property_traits<CentralityMap>::value_type Centrality;
typename graph_traits<Graph>::vertex_iterator i, end;
for(tie(i, end) = vertices(g); i != end; ++i) {
- cent[*i] = vertex_closeness_centrality(g, DistanceMap(dist[*i]), measure);
+ DistanceMap dm = get(dist, *i);
+ Centrality c = vertex_closeness_centrality(g, dm, measure);
+ put(cent, *i, c);
}
}
@@ -139,9 +163,14 @@
const DistanceMatrix& dist,
CentralityMap cent)
{
- typedef typename property_matrix_traits<DistanceMatrix>::value_type Distance;
- typedef typename exterior_vertex_property<Graph, Distance>::map_type DistanceMap;
+ function_requires< GraphConcept<Graph> >();
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ function_requires< ReadablePropertyMapConcept<DistanceMatrix,Vertex> >();
+ typedef typename property_traits<DistanceMatrix>::value_type DistanceMap;
+ function_requires< ReadablePropertyMapConcept<DistanceMap,Vertex> >();
+ 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()));
}
}
Modified: sandbox/SOC/2007/graphs/boost/graph/constant_property_map.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/constant_property_map.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/constant_property_map.hpp 2007-08-11 11:53:31 EDT (Sat, 11 Aug 2007)
@@ -18,15 +18,15 @@
// The key is pretty much anything it doesn't matter. The
// value has to be default and copy constructible.
- template <typename Key, typename Type>
+ template <typename Key, typename Value>
struct constant_property_map
: public boost::put_get_helper<
- const Type&,
- constant_property_map<Key, Type> >
+ const Value&,
+ constant_property_map<Key, Value> >
{
typedef Key key_type;
- typedef Type value_type;
- typedef const Type& reference;
+ typedef Value value_type;
+ typedef const Value& reference;
typedef boost::readable_property_map_tag category;
constant_property_map()
@@ -44,14 +44,14 @@
inline reference operator [](const key_type& v) const
{ return m_value; }
- Type m_value;
+ value_type m_value;
};
- template <typename Key, typename Type>
- inline constant_property_map<Key, Type>
- make_constant_property(const Type& value)
+ template <typename Key, typename Value>
+ inline constant_property_map<Key, Value>
+ make_constant_property(const Value& value)
{
- return constant_property_map<Key, Type>(value);
+ return constant_property_map<Key, Value>(value);
}
}
Modified: sandbox/SOC/2007/graphs/boost/graph/container_property_map.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/container_property_map.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/container_property_map.hpp 2007-08-11 11:53:31 EDT (Sat, 11 Aug 2007)
@@ -7,69 +7,16 @@
#ifndef BOOST_GRAPH_CONTAINER_PROPERTY_MAP_HXX
#define BOOST_GRAPH_CONTAINER_PROPERTY_MAP_HXX
+#include <boost/graph/detail/index.hpp>
#include <boost/property_map.hpp>
-#include <boost/graph/graph_traits.hpp>
namespace boost
{
-
- namespace detail
- {
- template <typename Graph>
- struct vertex_indexer
- {
- typedef vertex_index_t index_type;
- typedef typename property_map<Graph, vertex_index_t>::type map_type;
- typedef typename property_map<Graph, vertex_index_t>::const_type const_map_type;
- typedef typename property_traits<map_type>::value_type value_type;
- typedef typename graph_traits<Graph>::vertex_descriptor key_type;
-
- static const_map_type index_map(const Graph& g)
- { return get(vertex_index, g); }
-
- static map_type index_map(Graph& g)
- { return get(vertex_index, g); }
-
- static value_type index(key_type k, const Graph& g)
- { return get(vertex_index, g, k); }
- };
-
- template <typename Graph>
- struct edge_indexer
- {
- typedef edge_index_t index_type;
- typedef typename property_map<Graph, edge_index_t>::type map_type;
- typedef typename property_map<Graph, edge_index_t>::const_type const_map_type;
- typedef typename property_traits<map_type>::value_type value_type;
- typedef typename graph_traits<Graph>::edge_descriptor key_type;
-
- static const_map_type index_map(const Graph& g)
- { return get(edge_index, g); }
-
- static map_type index_map(Graph& g)
- { return get(edge_index, g); }
-
- static value_type index(key_type k, const Graph& g)
- { return get(edge_index, g, k); }
- };
-
- template <typename Graph, typename Key>
- struct choose_indexer
- {
- typedef typename mpl::if_<
- is_same<Key, typename graph_traits<Graph>::vertex_descriptor>,
- vertex_indexer<Graph>,
- edge_indexer<Graph>
- >::type indexer_type;
- typedef typename indexer_type::index_type index_type;
- };
- }
-
// This is an adapter built over the iterator property map with
// more useful uniform construction semantics. Specifically, this
// requires the container rather than the iterator and the graph
// rather than the optional index map.
- template <typename Graph, typename Container, typename Key>
+ template <typename Graph, typename Key, typename Container>
struct container_property_map
: public boost::put_get_helper<
typename iterator_property_map<
@@ -79,7 +26,7 @@
typename detail::choose_indexer<Graph, Key>::index_type
>::type
>::reference,
- container_property_map<Graph, Container, Key>
+ container_property_map<Graph, Key, Container>
>
{
typedef typename detail::choose_indexer<Graph, Key>::indexer_type indexer_type;
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-11 11:53:31 EDT (Sat, 11 Aug 2007)
@@ -14,8 +14,6 @@
template <typename Graph>
struct degree_centrality_measure
{
- BOOST_CLASS_REQUIRE(Graph, boost, IncidenceGraphConcept);
-
typedef typename graph_traits<Graph>::degree_size_type degree_type;
typedef typename graph_traits<Graph>::vertex_descriptor vertex_type;
};
@@ -24,14 +22,15 @@
struct influence_measure
: public degree_centrality_measure<Graph>
{
- BOOST_CLASS_REQUIRE(Graph, boost, IncidenceGraphConcept);
-
typedef degree_centrality_measure<Graph> base_type;
typedef typename base_type::degree_type degree_type;
typedef typename base_type::vertex_type vertex_type;
inline degree_type operator ()(vertex_type v, const Graph& g)
- { return out_degree(v, g); }
+ {
+ function_requires< IncidenceGraphConcept<Graph> >();
+ return out_degree(v, g);
+ }
};
template <typename Graph>
@@ -44,14 +43,15 @@
struct prestige_measure
: public degree_centrality_measure<Graph>
{
- BOOST_CLASS_REQUIRE(Graph, boost, BidirectionalGraphConcept);
-
typedef degree_centrality_measure<Graph> base_type;
typedef typename base_type::degree_type degree_type;
typedef typename base_type::vertex_type vertex_type;
inline degree_type operator ()(vertex_type v, const Graph& g)
- { return in_degree(v, g); }
+ {
+ function_requires< BidirectionalGraphConcept<Graph> >();
+ return in_degree(v, g);
+ }
};
template <typename Graph>
@@ -86,9 +86,15 @@
Measure measure)
{
function_requires< VertexListGraphConcept<Graph> >();
- typename graph_traits<Graph>::vertex_iterator i, end;
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
+ function_requires< WritablePropertyMapConcept<CentralityMap,Vertex> >();
+ typedef typename property_traits<CentralityMap>::value_type Centrality;
+
+ VertexIterator i, end;
for(tie(i, end) = vertices(g); i != end; ++i) {
- put(cent, *i, vertex_degree_centrality(g, *i, measure));
+ Centrality c = vertex_degree_centrality(g, *i, measure);
+ put(cent, *i, c);
}
}
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-11 11:53:31 EDT (Sat, 11 Aug 2007)
@@ -21,7 +21,7 @@
{
typedef typename property_traits<DistanceMap>::value_type Distance;
return detail::combine_distances(g, dist, combine,
- numeric_values<Distance>());
+ Distance(0));
}
template <typename Graph, typename DistanceMap>
@@ -36,8 +36,9 @@
inline void
eccentricity(const Graph& g, const DistanceMatrix& dist, EccentricityMap ecc)
{
- typedef typename property_matrix_traits<DistanceMatrix>::value_type Distance;
- typedef typename exterior_vertex_property<Graph, Distance>::map_type DistanceMap;
+ typedef typename property_traits<DistanceMatrix>::value_type DistanceMap;
+ typedef typename property_traits<DistanceMap>::value_type Distance;
+
typename graph_traits<Graph>::vertex_iterator i, end;
for(tie(i, end) = vertices(g); i != end; ++i) {
ecc[*i] = vertex_eccentricity(g, DistanceMap(dist[*i]));
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-11 11:53:31 EDT (Sat, 11 Aug 2007)
@@ -8,8 +8,8 @@
#define BOOST_GRAPH_EXTERIOR_PROPERTY_HPP
#include <vector>
-#include <boost/utility.hpp>
#include <boost/graph/container_property_map.hpp>
+#include <boost/graph/matrix_property_map.hpp>
namespace boost
{
@@ -18,34 +18,32 @@
// The vector matrix provides a little abstraction over vector
// types that makes matrices easier to work with. Note that it's
// non-copyable, meaning you should be passing it by value.
- template <typename Graph, typename Key, typename Value>
+ template <typename Value>
struct vector_matrix
{
- typedef std::size_t size_type;
- typedef Key key_type;
- typedef Value value_type;
-
- typedef std::vector<value_type> container_type;
+ typedef std::vector<Value> container_type;
typedef std::vector<container_type> matrix_type;
- typedef container_property_map<Graph, container_type, Key> map_type;
- typedef typename map_type::indexer_type indexer_type;
+
+ typedef container_type value_type;
+ typedef container_type& reference;
+ typedef const container_type const_reference;
+ typedef container_type* pointer;
+ typedef typename matrix_type::size_type size_type;
// Instantiate the matrix over n elements (creates an nxn matrix).
// The graph has to be passed in order to ensure the index maps
// are constructed correctly when returning indexible elements.
- inline vector_matrix(size_type n, const Graph& g)
+ inline vector_matrix(size_type n)
: m_matrix(n, container_type(n))
- , m_graph(g)
{ }
- inline map_type operator [](key_type k)
- { return map_type(m_matrix[indexer_type::index(k, m_graph)], m_graph); }
+ inline reference operator [](size_type n)
+ { return m_matrix[n]; }
- inline map_type operator [](key_type k) const
- { return map_type(m_matrix[indexer_type::index(k, m_graph)], m_graph); }
+ inline const_reference operator [](size_type n) const
+ { return m_matrix[n]; }
- mutable matrix_type m_matrix;
- const Graph& m_graph;
+ matrix_type m_matrix;
};
}
@@ -54,9 +52,12 @@
{
typedef Key key_type;
typedef Value value_type;
+
typedef std::vector<Value> container_type;
- typedef detail::vector_matrix<Graph, Key, Value> matrix_type;
- typedef container_property_map<Graph, container_type, Key> map_type;
+ typedef container_property_map<Graph, Key, container_type> map_type;
+
+ typedef detail::vector_matrix<Value> matrix_type;
+ typedef matrix_property_map<Graph, Key, matrix_type> matrix_map_type;
private:
exterior_property() { }
@@ -74,8 +75,9 @@
typedef typename property_type::key_type key_type;
typedef typename property_type::value_type value_type;
typedef typename property_type::container_type container_type;
- typedef typename property_type::matrix_type matrix_type;
typedef typename property_type::map_type map_type;
+ typedef typename property_type::matrix_type matrix_type;
+ typedef typename property_type::matrix_map_type matrix_map_type;
};
template <typename Graph, typename Value>
@@ -89,22 +91,9 @@
typedef typename property_type::key_type key_type;
typedef typename property_type::value_type value_type;
typedef typename property_type::container_type container_type;
- typedef typename property_type::matrix_type matrix_type;
typedef typename property_type::map_type map_type;
- };
-
-
- // TODO: Rewrite a property matrix in terms of a property map (i.e., the
- // matrix is separate from map). map of maps.
-
- template <typename Matrix>
- struct property_matrix_traits
- {
- typedef typename Matrix::matrix_type matrix_type;
- typedef typename Matrix::container_type container_type;
- typedef typename Matrix::value_type value_type;
- typedef typename Matrix::key_type key_type;
- typedef typename Matrix::map_type map_type;
+ typedef typename property_type::matrix_type matrix_type;
+ typedef typename property_type::matrix_map_type matrix_map_type;
};
}
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-11 11:53:31 EDT (Sat, 11 Aug 2007)
@@ -110,8 +110,7 @@
{
typedef typename Measure::distance_type Distance;
typedef typename Measure::distance_values DistanceValues;
- Distance n = detail::combine_distances(g, dist, combine,
- DistanceValues());
+ Distance n = detail::combine_distances(g, dist, combine, Distance(0));
return measure(n, g);
}
@@ -166,8 +165,8 @@
const 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<DistanceMatrix>::value_type DistanceMap;
+ typedef typename property_traits<DistanceMap>::value_type Distance;
typedef typename property_traits<GeodesicMap>::value_type Result;
mean_geodesic(g, dist, geo,
measure_mean_geodesic<Result>(g, DistanceMap()));
@@ -179,7 +178,7 @@
graph_mean_geodesic(const Graph& g, GeodesicMap geo, Measure measure)
{
typedef typename Measure::result_type T;
- T sum = detail::combine_distances(g, geo, std::plus<T>(), numeric_values<T>());
+ T sum = detail::combine_distances(g, geo, std::plus<T>(), T(0));
return measure(sum, g);
}
Modified: sandbox/SOC/2007/graphs/boost/graph/new_graph_concepts.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/new_graph_concepts.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/new_graph_concepts.hpp 2007-08-11 11:53:31 EDT (Sat, 11 Aug 2007)
@@ -7,7 +7,9 @@
#ifndef BOOST_GRAPH_NEW_GRAPH_CONCEPTS_HXX
#define BOOST_GRAPH_NEW_GRAPH_CONCEPTS_HXX
+#include <boost/property_map.hpp>
#include <boost/graph/graph_concepts.hpp>
+#include <boost/graph/numeric_values.hpp>
#include <boost/concept/detail/concept_def.hpp>
namespace boost
@@ -19,6 +21,17 @@
namespace concepts
{
+ BOOST_concept(NumericValue,(Numeric))
+ {
+ BOOST_CONCEPT_USAGE(NumericValue)
+ {
+ function_requires< DefaultConstructible<Numeric> >();
+ function_requires< CopyConstructible<Numeric> >();
+ numeric_values<Numeric>::zero();
+ numeric_values<Numeric>::infinity();
+ }
+ };
+
BOOST_concept(DegreeMeasure,(Measure)(Graph))
{
BOOST_CONCEPT_USAGE(DegreeMeasure)
@@ -32,8 +45,24 @@
Measure m;
Graph g;
};
+
+ BOOST_concept(DistanceMeasure,(Measure)(Graph))
+ {
+ BOOST_CONCEPT_USAGE(DistanceMeasure)
+ {
+ typedef typename Measure::distance_type Distance;
+ typedef typename Measure::result_type Result;
+ Result r = m(Distance(), g);
+ ignore_unused_variable_warning(r);
+ }
+ private:
+ Measure m;
+ Graph g;
+ };
}
+ using boost::concepts::NumericValueConcept;
+ using boost::concepts::DistanceMeasureConcept;
using boost::concepts::DegreeMeasureConcept;
}
#include <boost/concept/detail/concept_undef.hpp>
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