[Boost-commit] svn:boost r38574 - sandbox/SOC/2007/graphs/boost/graph

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