Chris@16: // (C) Copyright 2007-2009 Andrew Sutton
Chris@16: //
Chris@16: // Use, modification and distribution are subject to the
Chris@16: // Boost Software License, Version 1.0 (See accompanying file
Chris@16: // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_CLUSTERING_COEFFICIENT_HPP
Chris@16: #define BOOST_GRAPH_CLUSTERING_COEFFICIENT_HPP
Chris@16: 
Chris@16: #include <boost/next_prior.hpp>
Chris@16: #include <boost/graph/graph_traits.hpp>
Chris@16: #include <boost/graph/graph_concepts.hpp>
Chris@16: #include <boost/graph/lookup_edge.hpp>
Chris@16: #include <boost/concept/assert.hpp>
Chris@16: 
Chris@16: namespace boost
Chris@16: {
Chris@16: namespace detail
Chris@16: {
Chris@16:     template <class Graph>
Chris@16:     inline typename graph_traits<Graph>::degree_size_type
Chris@16:     possible_edges(const Graph& g, std::size_t k, directed_tag)
Chris@16:     {
Chris@16:         BOOST_CONCEPT_ASSERT(( GraphConcept<Graph> ));
Chris@16:         typedef typename graph_traits<Graph>::degree_size_type T;
Chris@16:         return T(k) * (T(k) - 1);
Chris@16:     }
Chris@16: 
Chris@16:     template <class Graph>
Chris@16:     inline typename graph_traits<Graph>::degree_size_type
Chris@16:     possible_edges(const Graph& g, size_t k, undirected_tag)
Chris@16:     {
Chris@16:         // dirty little trick...
Chris@16:         return possible_edges(g, k, directed_tag()) / 2;
Chris@16:     }
Chris@16: 
Chris@16:     // This template matches directedS and bidirectionalS.
Chris@16:     template <class Graph>
Chris@16:     inline typename graph_traits<Graph>::degree_size_type
Chris@16:     count_edges(const Graph& g,
Chris@16:                 typename graph_traits<Graph>::vertex_descriptor u,
Chris@16:                 typename graph_traits<Graph>::vertex_descriptor v,
Chris@16:                 directed_tag)
Chris@16: 
Chris@16:     {
Chris@16:         BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept<Graph> ));
Chris@16:         return (lookup_edge(u, v, g).second ? 1 : 0) +
Chris@16:                 (lookup_edge(v, u, g).second ? 1 : 0);
Chris@16:     }
Chris@16: 
Chris@16:     // This template matches undirectedS
Chris@16:     template <class Graph>
Chris@16:     inline typename graph_traits<Graph>::degree_size_type
Chris@16:     count_edges(const Graph& g,
Chris@16:                 typename graph_traits<Graph>::vertex_descriptor u,
Chris@16:                 typename graph_traits<Graph>::vertex_descriptor v,
Chris@16:                 undirected_tag)
Chris@16:     {
Chris@16:         BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept<Graph> ));
Chris@16:         return lookup_edge(u, v, g).second ? 1 : 0;
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: template <typename Graph, typename Vertex>
Chris@16: inline typename graph_traits<Graph>::degree_size_type
Chris@16: num_paths_through_vertex(const Graph& g, Vertex v)
Chris@16: {
Chris@16:     BOOST_CONCEPT_ASSERT(( AdjacencyGraphConcept<Graph> ));
Chris@16:     typedef typename graph_traits<Graph>::directed_category Directed;
Chris@16:     typedef typename graph_traits<Graph>::adjacency_iterator AdjacencyIterator;
Chris@16: 
Chris@16:     // TODO: There should actually be a set of neighborhood functions
Chris@16:     // for things like this (num_neighbors() would be great).
Chris@16: 
Chris@16:     AdjacencyIterator i, end;
Chris@16:     boost::tie(i, end) = adjacent_vertices(v, g);
Chris@16:     std::size_t k = std::distance(i, end);
Chris@16:     return detail::possible_edges(g, k, Directed());
Chris@16: }
Chris@16: 
Chris@16: template <typename Graph, typename Vertex>
Chris@16: inline typename graph_traits<Graph>::degree_size_type
Chris@16: num_triangles_on_vertex(const Graph& g, Vertex v)
Chris@16: {
Chris@16:     BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<Graph> ));
Chris@16:     BOOST_CONCEPT_ASSERT(( AdjacencyGraphConcept<Graph> ));
Chris@16:     typedef typename graph_traits<Graph>::degree_size_type Degree;
Chris@16:     typedef typename graph_traits<Graph>::directed_category Directed;
Chris@16:     typedef typename graph_traits<Graph>::adjacency_iterator AdjacencyIterator;
Chris@16: 
Chris@16:     // TODO: I might be able to reduce the requirement from adjacency graph
Chris@16:     // to incidence graph by using out edges.
Chris@16: 
Chris@16:     Degree count(0);
Chris@16:     AdjacencyIterator i, j, end;
Chris@16:     for(boost::tie(i, end) = adjacent_vertices(v, g); i != end; ++i) {
Chris@16:         for(j = boost::next(i); j != end; ++j) {
Chris@16:             count += detail::count_edges(g, *i, *j, Directed());
Chris@16:         }
Chris@16:     }
Chris@16:     return count;
Chris@16: } /* namespace detail */
Chris@16: 
Chris@16: template <typename T, typename Graph, typename Vertex>
Chris@16: inline T
Chris@16: clustering_coefficient(const Graph& g, Vertex v)
Chris@16: {
Chris@16:     T zero(0);
Chris@16:     T routes = T(num_paths_through_vertex(g, v));
Chris@16:     return (routes > zero) ?
Chris@16:         T(num_triangles_on_vertex(g, v)) / routes : zero;
Chris@16: }
Chris@16: 
Chris@16: template <typename Graph, typename Vertex>
Chris@16: inline double
Chris@16: clustering_coefficient(const Graph& g, Vertex v)
Chris@16: { return clustering_coefficient<double>(g, v); }
Chris@16: 
Chris@16: template <typename Graph, typename ClusteringMap>
Chris@16: inline typename property_traits<ClusteringMap>::value_type
Chris@16: all_clustering_coefficients(const Graph& g, ClusteringMap cm)
Chris@16: {
Chris@16:     BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> ));
Chris@16:     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
Chris@16:     typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
Chris@16:     BOOST_CONCEPT_ASSERT(( WritablePropertyMapConcept<ClusteringMap,Vertex> ));
Chris@16:     typedef typename property_traits<ClusteringMap>::value_type Coefficient;
Chris@16: 
Chris@16:     Coefficient sum(0);
Chris@16:     VertexIterator i, end;
Chris@16:     for(boost::tie(i, end) = vertices(g); i != end; ++i) {
Chris@16:         Coefficient cc = clustering_coefficient<Coefficient>(g, *i);
Chris@16:         put(cm, *i, cc);
Chris@16:         sum += cc;
Chris@16:     }
Chris@16:     return sum / Coefficient(num_vertices(g));
Chris@16: }
Chris@16: 
Chris@16: template <typename Graph, typename ClusteringMap>
Chris@16: inline typename property_traits<ClusteringMap>::value_type
Chris@16: mean_clustering_coefficient(const Graph& g, ClusteringMap cm)
Chris@16: {
Chris@16:     BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> ));
Chris@16:     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
Chris@16:     typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
Chris@16:     BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<ClusteringMap,Vertex> ));
Chris@16:     typedef typename property_traits<ClusteringMap>::value_type Coefficient;
Chris@16: 
Chris@16:     Coefficient cc(0);
Chris@16:     VertexIterator i, end;
Chris@16:     for(boost::tie(i, end) = vertices(g); i != end; ++i) {
Chris@16:         cc += get(cm, *i);
Chris@16:     }
Chris@16:     return cc / Coefficient(num_vertices(g));
Chris@16: }
Chris@16: 
Chris@16: } /* namespace boost */
Chris@16: 
Chris@16: #endif