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

From: asutton_at_[hidden]
Date: 2007-08-22 11:09:39

Author: asutton
Date: 2007-08-22 11:09:38 EDT (Wed, 22 Aug 2007)
New Revision: 38851
URL: http://svn.boost.org/trac/boost/changeset/38851

Log:
Concept checking clustering coef

Text files modified: 
   sandbox/SOC/2007/graphs/boost/graph/clustering_coefficient.hpp |    93 +++++++++++++++++++++++++-------------- 
   1 files changed, 59 insertions(+), 34 deletions(-)

Modified: sandbox/SOC/2007/graphs/boost/graph/clustering_coefficient.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/clustering_coefficient.hpp	(original)
+++ sandbox/SOC/2007/graphs/boost/graph/clustering_coefficient.hpp	2007-08-22 11:09:38 EDT (Wed, 22 Aug 2007)
@@ -9,6 +9,7 @@
 
 #include <boost/utility.hpp>
 #include <boost/graph/graph_traits.hpp>
+#include <boost/graph/new_graph_concepts.hpp>
 
 namespace boost
 {
@@ -18,6 +19,7 @@
         inline typename graph_traits<Graph>::degree_size_type
         possible_edges(const Graph& g, std::size_t k, directed_tag)
         {
+            function_requires< GraphConcept<Graph> >();
             typedef typename graph_traits<Graph>::degree_size_type T;
             return T(k) * (T(k) - 1);
         }
@@ -39,6 +41,7 @@
                     directed_tag)
 
         {
+            function_requires< AdjacencyMatrixConcept<Graph> >();
             return (edge(u, v, g).second ? 1 : 0) +
                    (edge(v, u, g).second ? 1 : 0);
         }
@@ -51,32 +54,46 @@
                     typename Graph::vertex_descriptor v,
                     undirected_tag)
         {
+            function_requires< AdjacencyMatrixConcept<Graph> >();
             return edge(u, v, g).second ? 1 : 0;
         }
     }
 
     template <typename Graph, typename Vertex>
     inline typename graph_traits<Graph>::degree_size_type
-    vertex_num_routes(const Graph& g, Vertex v)
+    num_paths_through_vertex(const Graph& g, Vertex v)
     {
-        typename graph_traits<Graph>::directed_category cat;
-        typename graph_traits<Graph>::adjacency_iterator i, end;
+        function_requires< AdjacencyGraphConcept<Graph> >();
+        typedef typename graph_traits<Graph>::directed_category Directed;
+        typedef typename graph_traits<Graph>::adjacency_iterator AdjacencyIterator;
+
+        // TODO: There should actually be a set of neighborhood functions
+        // for things like this (num_neighbors() would be great).
+
+        AdjacencyIterator i, end;
         tie(i, end) = adjacent_vertices(v, g);
         std::size_t k = std::distance(i, end);
-        return detail::possible_edges(g, k, cat);
+        return detail::possible_edges(g, k, Directed());
     }
 
     template <typename Graph, typename Vertex>
     inline typename graph_traits<Graph>::degree_size_type
-    vertex_num_triangles(const Graph& g, Vertex v)
+    num_triangles_on_vertex(const Graph& g, Vertex v)
     {
-        typedef typename graph_traits<Graph>::degree_size_type T;
-        T count = 0;
-        typename graph_traits<Graph>::directed_category cat;
-        typename graph_traits<Graph>::adjacency_iterator i, j, end;
+        function_requires< IncidenceGraphConcept<Graph> >();
+        function_requires< AdjacencyGraphConcept<Graph> >();
+        typedef typename graph_traits<Graph>::degree_size_type Degree;
+        typedef typename graph_traits<Graph>::directed_category Directed;
+        typedef typename graph_traits<Graph>::adjacency_iterator AdjacencyIterator;
+
+        // TODO: I might be able to reduce the requirement from adjacency graph
+        // to incidence graph by using out edges.
+
+        Degree count(0);
+        AdjacencyIterator i, j, end;
         for(tie(i, end) = adjacent_vertices(v, g); i != end; ++i) {
             for(j = next(i); j != end; ++j) {
-                count += detail::count_edges(g, *i, *j, cat);
+                count += detail::count_edges(g, *i, *j, Directed());
             }
         }
         return count;
@@ -84,49 +101,57 @@
 
     template <typename T, typename Graph, typename Vertex>
     inline T
-    vertex_clustering_coefficient(const Graph& g, Vertex v)
+    clustering_coefficient(const Graph& g, Vertex v)
     {
         T zero(0);
-        T routes = T(vertex_num_routes(g, v));
+        T routes = T(num_paths_through_vertex(g, v));
         return (routes > zero) ?
-            T(vertex_num_triangles(g, v)) / routes : zero;
+            T(num_triangles_on_vertex(g, v)) / routes : zero;
     }
 
     template <typename Graph, typename Vertex>
     inline float
-    vertex_clustering_coefficient(const Graph& g, Vertex v)
+    clustering_coefficient(const Graph& g, Vertex v)
     {
-        return vertex_clustering_coefficient<float>(g, v);
+        return clustering_coefficient<float>(g, v);
     }
 
     template <typename Graph, typename ClusteringMap>
-    inline void
-    clustering_coefficient(const Graph& g, ClusteringMap cluster)
+    inline typename property_traits<ClusteringMap>::value_type
+    all_clustering_coefficients(const Graph& g, ClusteringMap cm)
     {
-        typedef typename property_traits<ClusteringMap>::value_type T;
-        typename graph_traits<Graph>::vertex_iterator i, end;
+        function_requires< VertexListGraphConcept<Graph> >();
+        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+        typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
+        function_requires< WritablePropertyMapConcept<ClusteringMap,Vertex> >();
+        typedef typename property_traits<ClusteringMap>::value_type Coefficient;
+
+        Coefficient sum(0);
+        VertexIterator i, end;
         for(tie(i, end) = vertices(g); i != end; ++i) {
-            cluster[*i] = vertex_clustering_coefficient<T>(g, *i);
+            Coefficient cc = clustering_coefficient<Coefficient>(g, *i);
+            put(cm, *i, cc);
+            sum += cc;
         }
+        return sum / Coefficient(num_vertices(g));
     }
 
-    template <typename T, typename Graph>
-    inline T
-    graph_clustering_coefficient(const Graph& g)
+    template <typename Graph, typename ClusteringMap>
+    inline typename property_traits<ClusteringMap>::value_type
+    mean_clustering_coefficient(const Graph& g, ClusteringMap cm)
     {
-        T cc(0);
-        typename graph_traits<Graph>::vertex_iterator i, end;
+        function_requires< VertexListGraphConcept<Graph> >();
+        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+        typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
+        function_requires< ReadablePropertyMapConcept<ClusteringMap,Vertex> >();
+        typedef typename property_traits<ClusteringMap>::value_type Coefficient;
+
+        Coefficient cc(0);
+        VertexIterator i, end;
         for(tie(i, end) = vertices(g); i != end; ++i) {
-            cc += vertex_clustering_coefficient<T>(g, *i);
+            cc += get(cm, *i);
         }
-        return cc / T(num_vertices(g));
-    }
-
-    template <typename Graph>
-    inline float
-    graph_clustering_coefficient(const Graph& g)
-    {
-        return graph_clustering_coefficient<float>(g);
+        return cc / Coefficient(num_vertices(g));
     }
 }