ceph/src/boost/libs/graph/include/boost/graph/clustering_coefficient.hpp

   1 // (C) Copyright 2007-2009 Andrew Sutton
   2 //
   3 // Use, modification and distribution are subject to the
   4 // Boost Software License, Version 1.0 (See accompanying file
   5 // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
   6
   7 #ifndef BOOST_GRAPH_CLUSTERING_COEFFICIENT_HPP
   8 #define BOOST_GRAPH_CLUSTERING_COEFFICIENT_HPP
   9
  10 #include <boost/next_prior.hpp>
  11 #include <boost/graph/graph_traits.hpp>
  12 #include <boost/graph/graph_concepts.hpp>
  13 #include <boost/graph/lookup_edge.hpp>
  14 #include <boost/concept/assert.hpp>
  15
  16 namespace boost
  17 {
  18 namespace detail
  19 {
  20     template <class Graph>
  21     inline typename graph_traits<Graph>::degree_size_type
  22     possible_edges(const Graph& g, std::size_t k, directed_tag)
  23     {
  24         BOOST_CONCEPT_ASSERT(( GraphConcept<Graph> ));
  25         typedef typename graph_traits<Graph>::degree_size_type T;
  26         return T(k) * (T(k) - 1);
  27     }
  28
  29     template <class Graph>
  30     inline typename graph_traits<Graph>::degree_size_type
  31     possible_edges(const Graph& g, size_t k, undirected_tag)
  32     {
  33         // dirty little trick...
  34         return possible_edges(g, k, directed_tag()) / 2;
  35     }
  36
  37     // This template matches directedS and bidirectionalS.
  38     template <class Graph>
  39     inline typename graph_traits<Graph>::degree_size_type
  40     count_edges(const Graph& g,
  41                 typename graph_traits<Graph>::vertex_descriptor u,
  42                 typename graph_traits<Graph>::vertex_descriptor v,
  43                 directed_tag)
  44
  45     {
  46         BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept<Graph> ));
  47         return (lookup_edge(u, v, g).second ? 1 : 0) +
  48                 (lookup_edge(v, u, g).second ? 1 : 0);
  49     }
  50
  51     // This template matches undirectedS
  52     template <class Graph>
  53     inline typename graph_traits<Graph>::degree_size_type
  54     count_edges(const Graph& g,
  55                 typename graph_traits<Graph>::vertex_descriptor u,
  56                 typename graph_traits<Graph>::vertex_descriptor v,
  57                 undirected_tag)
  58     {
  59         BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept<Graph> ));
  60         return lookup_edge(u, v, g).second ? 1 : 0;
  61     }
  62 }
  63
  64 template <typename Graph, typename Vertex>
  65 inline typename graph_traits<Graph>::degree_size_type
  66 num_paths_through_vertex(const Graph& g, Vertex v)
  67 {
  68     BOOST_CONCEPT_ASSERT(( AdjacencyGraphConcept<Graph> ));
  69     typedef typename graph_traits<Graph>::directed_category Directed;
  70     typedef typename graph_traits<Graph>::adjacency_iterator AdjacencyIterator;
  71
  72     // TODO: There should actually be a set of neighborhood functions
  73     // for things like this (num_neighbors() would be great).
  74
  75     AdjacencyIterator i, end;
  76     boost::tie(i, end) = adjacent_vertices(v, g);
  77     std::size_t k = std::distance(i, end);
  78     return detail::possible_edges(g, k, Directed());
  79 }
  80
  81 template <typename Graph, typename Vertex>
  82 inline typename graph_traits<Graph>::degree_size_type
  83 num_triangles_on_vertex(const Graph& g, Vertex v)
  84 {
  85     BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<Graph> ));
  86     BOOST_CONCEPT_ASSERT(( AdjacencyGraphConcept<Graph> ));
  87     typedef typename graph_traits<Graph>::degree_size_type Degree;
  88     typedef typename graph_traits<Graph>::directed_category Directed;
  89     typedef typename graph_traits<Graph>::adjacency_iterator AdjacencyIterator;
  90
  91     // TODO: I might be able to reduce the requirement from adjacency graph
  92     // to incidence graph by using out edges.
  93
  94     Degree count(0);
  95     AdjacencyIterator i, j, end;
  96     for(boost::tie(i, end) = adjacent_vertices(v, g); i != end; ++i) {
  97         for(j = boost::next(i); j != end; ++j) {
  98             count += detail::count_edges(g, *i, *j, Directed());
  99         }
 100     }
 101     return count;
 102 } /* namespace detail */
 103
 104 template <typename T, typename Graph, typename Vertex>
 105 inline T
 106 clustering_coefficient(const Graph& g, Vertex v)
 107 {
 108     T zero(0);
 109     T routes = T(num_paths_through_vertex(g, v));
 110     return (routes > zero) ?
 111         T(num_triangles_on_vertex(g, v)) / routes : zero;
 112 }
 113
 114 template <typename Graph, typename Vertex>
 115 inline double
 116 clustering_coefficient(const Graph& g, Vertex v)
 117 { return clustering_coefficient<double>(g, v); }
 118
 119 template <typename Graph, typename ClusteringMap>
 120 inline typename property_traits<ClusteringMap>::value_type
 121 all_clustering_coefficients(const Graph& g, ClusteringMap cm)
 122 {
 123     BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> ));
 124     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
 125     typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
 126     BOOST_CONCEPT_ASSERT(( WritablePropertyMapConcept<ClusteringMap,Vertex> ));
 127     typedef typename property_traits<ClusteringMap>::value_type Coefficient;
 128
 129     Coefficient sum(0);
 130     VertexIterator i, end;
 131     for(boost::tie(i, end) = vertices(g); i != end; ++i) {
 132         Coefficient cc = clustering_coefficient<Coefficient>(g, *i);
 133         put(cm, *i, cc);
 134         sum += cc;
 135     }
 136     return sum / Coefficient(num_vertices(g));
 137 }
 138
 139 template <typename Graph, typename ClusteringMap>
 140 inline typename property_traits<ClusteringMap>::value_type
 141 mean_clustering_coefficient(const Graph& g, ClusteringMap cm)
 142 {
 143     BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> ));
 144     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
 145     typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
 146     BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<ClusteringMap,Vertex> ));
 147     typedef typename property_traits<ClusteringMap>::value_type Coefficient;
 148
 149     Coefficient cc(0);
 150     VertexIterator i, end;
 151     for(boost::tie(i, end) = vertices(g); i != end; ++i) {
 152         cc += get(cm, *i);
 153     }
 154     return cc / Coefficient(num_vertices(g));
 155 }
 156
 157 } /* namespace boost */
 158
 159 #endif