From: asutton_at_[hidden]
Date: 2007-08-10 12:20:55
Author: asutton
Date: 2007-08-10 12:20:54 EDT (Fri, 10 Aug 2007)
New Revision: 38574
URL: http://svn.boost.org/trac/boost/changeset/38574
Log:
Added new graph concepts header
Implemented concept checking for degree centrality
Added:
sandbox/SOC/2007/graphs/boost/graph/new_graph_concepts.hpp (contents, props changed)
Text files modified:
sandbox/SOC/2007/graphs/boost/graph/container_property_map.hpp | 2
sandbox/SOC/2007/graphs/boost/graph/degree_centrality.hpp | 56 +++++++++++++++++++++++++++------------
sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp | 5 +++
3 files changed, 45 insertions(+), 18 deletions(-)
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-10 12:20:54 EDT (Fri, 10 Aug 2007)
@@ -50,7 +50,7 @@
{ return get(edge_index, g); }
static value_type index(key_type k, const Graph& g)
- { return get(vertex_index, g, k); }
+ { return get(edge_index, g, k); }
};
template <typename Graph, typename Key>
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-10 12:20:54 EDT (Fri, 10 Aug 2007)
@@ -7,54 +7,75 @@
#ifndef BOOST_GRAPH_DEGREE_CENTRALITY_HXX
#define BOOST_GRAPH_DEGREE_CENTRALITY_HXX
+#include <boost/graph/new_graph_concepts.hpp>
+
namespace boost
{
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;
};
template <typename Graph>
- struct basic_degree_centrality
+ 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)
- {
- // This defaults to degree() for undirected graphs
- return out_degree(v, g);
- }
+ { return out_degree(v, g); }
};
template <typename Graph>
- inline basic_degree_centrality<Graph>
- measure_basic_degree_centrality(const Graph&)
+ inline influence_measure<Graph>
+ measure_influence(const Graph&)
+ { return influence_measure<Graph>(); }
+
+
+ template <typename Graph>
+ struct prestige_measure
+ : public degree_centrality_measure<Graph>
{
- return basic_degree_centrality<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); }
+ };
- template <typename Graph, typename Measure>
+ template <typename Graph>
+ inline prestige_measure<Graph>
+ measure_prestige(const Graph&)
+ { return prestige_measure<Graph>(); }
+
+
+ template <typename Graph, typename Vertex, typename Measure>
inline typename Measure::degree_type
vertex_degree_centrality(const Graph& g,
- typename graph_traits<Graph>::vertex_descriptor v,
+ Vertex v,
Measure measure)
{
+ function_requires< DegreeMeasureConcept<Measure, Graph> >();
return measure(v, g);
}
- template <typename Graph>
+ template <typename Graph, typename Vertex>
inline typename graph_traits<Graph>::degree_size_type
vertex_degree_centrality(const Graph& g,
- typename graph_traits<Graph>::vertex_descriptor v)
+ Vertex v)
{
- return vertex_degree_centrality(g, v,
- measure_basic_degree_centrality(g));
+ return vertex_degree_centrality(g, v, measure_influence(g));
}
@@ -64,9 +85,10 @@
CentralityMap cent,
Measure measure)
{
+ function_requires< VertexListGraphConcept<Graph> >();
typename graph_traits<Graph>::vertex_iterator i, end;
for(tie(i, end) = vertices(g); i != end; ++i) {
- cent[*i] = vertex_degree_centrality(g, *i, measure);
+ put(cent, *i, vertex_degree_centrality(g, *i, measure));
}
}
@@ -74,7 +96,7 @@
inline void degree_centrality(const Graph& g,
CentralityMap cent)
{
- degree_centrality(g, cent, measure_basic_degree_centrality(g));
+ degree_centrality(g, cent, measure_influence(g));
}
}
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-10 12:20:54 EDT (Fri, 10 Aug 2007)
@@ -93,6 +93,10 @@
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
{
@@ -100,6 +104,7 @@
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;
};
}
Added: sandbox/SOC/2007/graphs/boost/graph/new_graph_concepts.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/boost/graph/new_graph_concepts.hpp 2007-08-10 12:20:54 EDT (Fri, 10 Aug 2007)
@@ -0,0 +1,43 @@
+// (C) Copyright Andrew Sutton 2007
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GRAPH_NEW_GRAPH_CONCEPTS_HXX
+#define BOOST_GRAPH_NEW_GRAPH_CONCEPTS_HXX
+
+#include <boost/graph/graph_concepts.hpp>
+
+#include <boost/concept/detail/concept_def.hpp>
+namespace boost
+{
+ // The DegreeMeasure is its own concept because it does, in a way
+ // specialize the semantics of an AdaptableBinaryFunction. Specifically,
+ // it is templated over a single type - a graph and derives its result
+ // and argument types from that graph.
+
+ namespace concepts
+ {
+ BOOST_concept(DegreeMeasure,(Measure)(Graph))
+ {
+ BOOST_CONCEPT_USAGE(DegreeMeasure)
+ {
+ typedef typename Measure::degree_type Degree;
+ typedef typename Measure::vertex_type Vertex;
+ Degree d = m(Vertex(), g);
+ ignore_unused_variable_warning(d);
+ }
+ private:
+ Measure m;
+ Graph g;
+ };
+ }
+
+ using boost::concepts::DegreeMeasureConcept;
+}
+#include <boost/concept/detail/concept_undef.hpp>
+
+#endif
+
+