/usr/include/boost/graph/graph_stats.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 | // Copyright 2005 The Trustees of Indiana University.
// Use, modification and distribution is subject to the Boost Software
// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
// Authors: Alex Breuer
// Andrew Lumsdaine
#ifndef BOOST_GRAPH_GRAPH_STATS_HPP
#define BOOST_GRAPH_GRAPH_STATS_HPP
#include <map>
#include <list>
#include <boost/graph/iteration_macros.hpp>
#include <boost/assert.hpp>
namespace boost { namespace graph {
template<typename Graph>
struct sort_edge_by_origin {
public:
typedef typename graph_traits<Graph>::edge_descriptor edge_type;
explicit sort_edge_by_origin( Graph& g ) : g(g) {}
inline bool operator()( edge_type a, edge_type b ) {
return source( a, g ) == source( b, g ) ? target( a, g ) < target( b, g ) :
source( a, g ) < source( b, g );
}
private:
Graph& g;
};
template<typename Graph>
struct equal_edge {
public:
typedef typename graph_traits<Graph>::edge_descriptor edge_type;
explicit equal_edge( Graph& g ) : g(g) {}
inline bool operator()( edge_type a, edge_type b ) {
return source( a, g ) == source( b, g ) &&
target( a, g ) == target( b, g );
}
private:
Graph& g;
};
template<typename Graph>
unsigned long num_dup_edges( Graph& g ) {
typedef typename graph_traits<Graph>::edge_iterator e_iterator_type;
typedef typename graph_traits<Graph>::edge_descriptor edge_type;
std::list<edge_type> all_edges;
BGL_FORALL_EDGES_T( e, g, Graph ) {
all_edges.push_back( e );
}
sort_edge_by_origin<Graph> cmp1( g );
all_edges.sort( cmp1 );
equal_edge<Graph> cmp2( g );
all_edges.unique( cmp2 );
return num_edges( g ) - all_edges.size();
}
template<typename Graph>
std::map<unsigned long, unsigned long> dup_edge_dist( Graph& g ) {
std::map<unsigned long, unsigned long> dist;
typedef typename graph_traits<Graph>::adjacency_iterator a_iterator_type;
typedef typename graph_traits<Graph>::vertex_descriptor vertex_type;
BGL_FORALL_VERTICES_T( v, g, Graph ) {
std::list<vertex_type> front_neighbors;
a_iterator_type a_iter, a_end;
for( boost::tie( a_iter, a_end ) = adjacent_vertices( v, g );
a_iter != a_end; ++a_iter ) {
front_neighbors.push_back( *a_iter );
}
front_neighbors.sort();
front_neighbors.unique();
dist[out_degree( v, g ) - front_neighbors.size()] += 1;
}
return dist;
}
template<typename Graph>
std::map<unsigned long, unsigned long> degree_dist( Graph& g ) {
std::map<unsigned long, unsigned long> dist;
typedef typename graph_traits<Graph>::adjacency_iterator a_iterator_type;
typedef typename graph_traits<Graph>::vertex_descriptor vertex_type;
BGL_FORALL_VERTICES_T( v, g, Graph ) {
dist[out_degree( v, g )] += 1;
}
return dist;
}
template<typename Graph>
std::map<unsigned long, double> weight_degree_dist( Graph& g ) {
std::map<unsigned long, double> dist, n;
typedef typename graph_traits<Graph>::adjacency_iterator a_iterator_type;
typedef typename graph_traits<Graph>::vertex_descriptor vertex_type;
typedef typename property_map<Graph, edge_weight_t>::const_type edge_map_type;
typedef typename property_traits<edge_map_type>::value_type
edge_weight_type;
typename property_map<Graph, edge_weight_t>::type em = get( edge_weight, g );
BGL_FORALL_VERTICES_T( v, g, Graph ) {
edge_weight_type tmp = 0;
BGL_FORALL_OUTEDGES_T( v, e, g, Graph ) {
tmp += em[e];
}
n[out_degree( v, g )] += 1.;
dist[out_degree( v, g )] += tmp;
}
for( std::map<unsigned long, double>::iterator iter = dist.begin();
iter != dist.end(); ++iter ) {
BOOST_ASSERT( n[iter->first] != 0 );
dist[iter->first] /= n[iter->first];
}
return dist;
}
}}
#endif
|