Boost logo

Boost-Commit :

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
+
+


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