boost/graph/clustering_coefficient.hpp

0001 // (C) Copyright 2007-2009 Andrew Sutton
0002 //
0003 // Use, modification and distribution are subject to the
0004 // Boost Software License, Version 1.0 (See accompanying file
0005 // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
0006
0007 #ifndef BOOST_GRAPH_CLUSTERING_COEFFICIENT_HPP
0008 #define BOOST_GRAPH_CLUSTERING_COEFFICIENT_HPP
0009
0010 #include <boost/next_prior.hpp>
0011 #include <boost/graph/graph_traits.hpp>
0012 #include <boost/graph/graph_concepts.hpp>
0013 #include <boost/graph/lookup_edge.hpp>
0014 #include <boost/concept/assert.hpp>
0015
0016 namespace boost
0017 {
0018 namespace detail
0019 {
0020     template < class Graph >
0021     inline typename graph_traits< Graph >::degree_size_type possible_edges(
0022         const Graph& g, std::size_t k, directed_tag)
0023     {
0024         BOOST_CONCEPT_ASSERT((GraphConcept< Graph >));
0025         typedef typename graph_traits< Graph >::degree_size_type T;
0026         return T(k) * (T(k) - 1);
0027     }
0028
0029     template < class Graph >
0030     inline typename graph_traits< Graph >::degree_size_type possible_edges(
0031         const Graph& g, size_t k, undirected_tag)
0032     {
0033         // dirty little trick...
0034         return possible_edges(g, k, directed_tag()) / 2;
0035     }
0036
0037     // This template matches directedS and bidirectionalS.
0038     template < class Graph >
0039     inline typename graph_traits< Graph >::degree_size_type count_edges(
0040         const Graph& g, typename graph_traits< Graph >::vertex_descriptor u,
0041         typename graph_traits< Graph >::vertex_descriptor v, directed_tag)
0042
0043     {
0044         BOOST_CONCEPT_ASSERT((AdjacencyMatrixConcept< Graph >));
0045         return (lookup_edge(u, v, g).second ? 1 : 0)
0046             + (lookup_edge(v, u, g).second ? 1 : 0);
0047     }
0048
0049     // This template matches undirectedS
0050     template < class Graph >
0051     inline typename graph_traits< Graph >::degree_size_type count_edges(
0052         const Graph& g, typename graph_traits< Graph >::vertex_descriptor u,
0053         typename graph_traits< Graph >::vertex_descriptor v, undirected_tag)
0054     {
0055         BOOST_CONCEPT_ASSERT((AdjacencyMatrixConcept< Graph >));
0056         return lookup_edge(u, v, g).second ? 1 : 0;
0057     }
0058 }
0059
0060 template < typename Graph, typename Vertex >
0061 inline typename graph_traits< Graph >::degree_size_type
0062 num_paths_through_vertex(const Graph& g, Vertex v)
0063 {
0064     BOOST_CONCEPT_ASSERT((AdjacencyGraphConcept< Graph >));
0065     typedef typename graph_traits< Graph >::directed_category Directed;
0066     typedef
0067         typename graph_traits< Graph >::adjacency_iterator AdjacencyIterator;
0068
0069     // TODO: There should actually be a set of neighborhood functions
0070     // for things like this (num_neighbors() would be great).
0071
0072     AdjacencyIterator i, end;
0073     boost::tie(i, end) = adjacent_vertices(v, g);
0074     std::size_t k = std::distance(i, end);
0075     return detail::possible_edges(g, k, Directed());
0076 }
0077
0078 template < typename Graph, typename Vertex >
0079 inline typename graph_traits< Graph >::degree_size_type num_triangles_on_vertex(
0080     const Graph& g, Vertex v)
0081 {
0082     BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< Graph >));
0083     BOOST_CONCEPT_ASSERT((AdjacencyGraphConcept< Graph >));
0084     typedef typename graph_traits< Graph >::degree_size_type Degree;
0085     typedef typename graph_traits< Graph >::directed_category Directed;
0086     typedef
0087         typename graph_traits< Graph >::adjacency_iterator AdjacencyIterator;
0088
0089     // TODO: I might be able to reduce the requirement from adjacency graph
0090     // to incidence graph by using out edges.
0091
0092     Degree count(0);
0093     AdjacencyIterator i, j, end;
0094     for (boost::tie(i, end) = adjacent_vertices(v, g); i != end; ++i)
0095     {
0096         for (j = boost::next(i); j != end; ++j)
0097         {
0098             count += detail::count_edges(g, *i, *j, Directed());
0099         }
0100     }
0101     return count;
0102 } /* namespace detail */
0103
0104 template < typename T, typename Graph, typename Vertex >
0105 inline T clustering_coefficient(const Graph& g, Vertex v)
0106 {
0107     T zero(0);
0108     T routes = T(num_paths_through_vertex(g, v));
0109     return (routes > zero) ? T(num_triangles_on_vertex(g, v)) / routes : zero;
0110 }
0111
0112 template < typename Graph, typename Vertex >
0113 inline double clustering_coefficient(const Graph& g, Vertex v)
0114 {
0115     return clustering_coefficient< double >(g, v);
0116 }
0117
0118 template < typename Graph, typename ClusteringMap >
0119 inline typename property_traits< ClusteringMap >::value_type
0120 all_clustering_coefficients(const Graph& g, ClusteringMap cm)
0121 {
0122     BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >));
0123     typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0124     typedef typename graph_traits< Graph >::vertex_iterator VertexIterator;
0125     BOOST_CONCEPT_ASSERT((WritablePropertyMapConcept< ClusteringMap, Vertex >));
0126     typedef typename property_traits< ClusteringMap >::value_type Coefficient;
0127
0128     Coefficient sum(0);
0129     VertexIterator i, end;
0130     for (boost::tie(i, end) = vertices(g); i != end; ++i)
0131     {
0132         Coefficient cc = clustering_coefficient< Coefficient >(g, *i);
0133         put(cm, *i, cc);
0134         sum += cc;
0135     }
0136     return sum / Coefficient(num_vertices(g));
0137 }
0138
0139 template < typename Graph, typename ClusteringMap >
0140 inline typename property_traits< ClusteringMap >::value_type
0141 mean_clustering_coefficient(const Graph& g, ClusteringMap cm)
0142 {
0143     BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >));
0144     typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0145     typedef typename graph_traits< Graph >::vertex_iterator VertexIterator;
0146     BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept< ClusteringMap, Vertex >));
0147     typedef typename property_traits< ClusteringMap >::value_type Coefficient;
0148
0149     Coefficient cc(0);
0150     VertexIterator i, end;
0151     for (boost::tie(i, end) = vertices(g); i != end; ++i)
0152     {
0153         cc += get(cm, *i);
0154     }
0155     return cc / Coefficient(num_vertices(g));
0156 }
0157
0158 } /* namespace boost */
0159
0160 #endif