/usr/include/boost/graph/clustering_coefficient.hpp is in libboost1.46-dev 1.46.1-7ubuntu3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 | // (C) Copyright 2007-2009 Andrew Sutton
//
// 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_CLUSTERING_COEFFICIENT_HPP
#define BOOST_GRAPH_CLUSTERING_COEFFICIENT_HPP
#include <boost/utility.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/graph_concepts.hpp>
#include <boost/graph/lookup_edge.hpp>
namespace boost
{
namespace detail
{
template <class Graph>
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);
}
template <class Graph>
inline typename graph_traits<Graph>::degree_size_type
possible_edges(const Graph& g, size_t k, undirected_tag)
{
// dirty little trick...
return possible_edges(g, k, directed_tag()) / 2;
}
// This template matches directedS and bidirectionalS.
template <class Graph>
inline typename graph_traits<Graph>::degree_size_type
count_edges(const Graph& g,
typename graph_traits<Graph>::vertex_descriptor u,
typename graph_traits<Graph>::vertex_descriptor v,
directed_tag)
{
function_requires< AdjacencyMatrixConcept<Graph> >();
return (lookup_edge(u, v, g).second ? 1 : 0) +
(lookup_edge(v, u, g).second ? 1 : 0);
}
// This template matches undirectedS
template <class Graph>
inline typename graph_traits<Graph>::degree_size_type
count_edges(const Graph& g,
typename graph_traits<Graph>::vertex_descriptor u,
typename graph_traits<Graph>::vertex_descriptor v,
undirected_tag)
{
function_requires< AdjacencyMatrixConcept<Graph> >();
return lookup_edge(u, v, g).second ? 1 : 0;
}
}
template <typename Graph, typename Vertex>
inline typename graph_traits<Graph>::degree_size_type
num_paths_through_vertex(const Graph& g, Vertex v)
{
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;
boost::tie(i, end) = adjacent_vertices(v, g);
std::size_t k = std::distance(i, end);
return detail::possible_edges(g, k, Directed());
}
template <typename Graph, typename Vertex>
inline typename graph_traits<Graph>::degree_size_type
num_triangles_on_vertex(const Graph& g, Vertex v)
{
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(boost::tie(i, end) = adjacent_vertices(v, g); i != end; ++i) {
for(j = boost::next(i); j != end; ++j) {
count += detail::count_edges(g, *i, *j, Directed());
}
}
return count;
} /* namespace detail */
template <typename T, typename Graph, typename Vertex>
inline T
clustering_coefficient(const Graph& g, Vertex v)
{
T zero(0);
T routes = T(num_paths_through_vertex(g, v));
return (routes > zero) ?
T(num_triangles_on_vertex(g, v)) / routes : zero;
}
template <typename Graph, typename Vertex>
inline double
clustering_coefficient(const Graph& g, Vertex v)
{ return clustering_coefficient<double>(g, v); }
template <typename Graph, typename ClusteringMap>
inline typename property_traits<ClusteringMap>::value_type
all_clustering_coefficients(const Graph& g, ClusteringMap cm)
{
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(boost::tie(i, end) = vertices(g); i != end; ++i) {
Coefficient cc = clustering_coefficient<Coefficient>(g, *i);
put(cm, *i, cc);
sum += cc;
}
return sum / Coefficient(num_vertices(g));
}
template <typename Graph, typename ClusteringMap>
inline typename property_traits<ClusteringMap>::value_type
mean_clustering_coefficient(const Graph& g, ClusteringMap cm)
{
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(boost::tie(i, end) = vertices(g); i != end; ++i) {
cc += get(cm, *i);
}
return cc / Coefficient(num_vertices(g));
}
} /* namespace boost */
#endif
|