1 // Copyright 2005 The Trustees of Indiana University.
2
3 // Use, modification and distribution is subject to the Boost Software
4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
5 // http://www.boost.org/LICENSE_1_0.txt)
6
7 // Authors: Alex Breuer
8 // Andrew Lumsdaine
9 #ifndef BOOST_GRAPH_GRAPH_STATS_HPP
10 #define BOOST_GRAPH_GRAPH_STATS_HPP
11
12 #include <map>
13 #include <list>
14 #include <boost/graph/iteration_macros.hpp>
15 #include <boost/assert.hpp>
16
17 namespace boost { namespace graph {
18
19 template<typename Graph>
20 struct sort_edge_by_origin {
21 public:
22 typedef typename graph_traits<Graph>::edge_descriptor edge_type;
23
sort_edge_by_originboost::graph::sort_edge_by_origin24 explicit sort_edge_by_origin( Graph& g ) : g(g) {}
25
operator ()boost::graph::sort_edge_by_origin26 inline bool operator()( edge_type a, edge_type b ) {
27 return source( a, g ) == source( b, g ) ? target( a, g ) < target( b, g ) :
28 source( a, g ) < source( b, g );
29 }
30
31 private:
32 Graph& g;
33 };
34
35 template<typename Graph>
36 struct equal_edge {
37 public:
38 typedef typename graph_traits<Graph>::edge_descriptor edge_type;
39
equal_edgeboost::graph::equal_edge40 explicit equal_edge( Graph& g ) : g(g) {}
41
operator ()boost::graph::equal_edge42 inline bool operator()( edge_type a, edge_type b ) {
43 return source( a, g ) == source( b, g ) &&
44 target( a, g ) == target( b, g );
45 }
46
47 private:
48 Graph& g;
49 };
50
51 template<typename Graph>
num_dup_edges(Graph & g)52 unsigned long num_dup_edges( Graph& g ) {
53 typedef typename graph_traits<Graph>::edge_iterator e_iterator_type;
54 typedef typename graph_traits<Graph>::edge_descriptor edge_type;
55
56 std::list<edge_type> all_edges;
57
58 BGL_FORALL_EDGES_T( e, g, Graph ) {
59 all_edges.push_back( e );
60 }
61
62 sort_edge_by_origin<Graph> cmp1( g );
63 all_edges.sort( cmp1 );
64 equal_edge<Graph> cmp2( g );
65 all_edges.unique( cmp2 );
66
67 return num_edges( g ) - all_edges.size();
68 }
69
70
71 template<typename Graph>
dup_edge_dist(Graph & g)72 std::map<unsigned long, unsigned long> dup_edge_dist( Graph& g ) {
73 std::map<unsigned long, unsigned long> dist;
74 typedef typename graph_traits<Graph>::adjacency_iterator a_iterator_type;
75 typedef typename graph_traits<Graph>::vertex_descriptor vertex_type;
76
77
78 BGL_FORALL_VERTICES_T( v, g, Graph ) {
79 std::list<vertex_type> front_neighbors;
80 a_iterator_type a_iter, a_end;
81 for( boost::tie( a_iter, a_end ) = adjacent_vertices( v, g );
82 a_iter != a_end; ++a_iter ) {
83 front_neighbors.push_back( *a_iter );
84 }
85
86 front_neighbors.sort();
87 front_neighbors.unique();
88 dist[out_degree( v, g ) - front_neighbors.size()] += 1;
89 }
90 return dist;
91 }
92
93 template<typename Graph>
degree_dist(Graph & g)94 std::map<unsigned long, unsigned long> degree_dist( Graph& g ) {
95 std::map<unsigned long, unsigned long> dist;
96 typedef typename graph_traits<Graph>::adjacency_iterator a_iterator_type;
97 typedef typename graph_traits<Graph>::vertex_descriptor vertex_type;
98
99 BGL_FORALL_VERTICES_T( v, g, Graph ) {
100 dist[out_degree( v, g )] += 1;
101 }
102
103 return dist;
104 }
105
106 template<typename Graph>
weight_degree_dist(Graph & g)107 std::map<unsigned long, double> weight_degree_dist( Graph& g ) {
108 std::map<unsigned long, double> dist, n;
109 typedef typename graph_traits<Graph>::adjacency_iterator a_iterator_type;
110 typedef typename graph_traits<Graph>::vertex_descriptor vertex_type;
111 typedef typename property_map<Graph, edge_weight_t>::const_type edge_map_type;
112 typedef typename property_traits<edge_map_type>::value_type
113 edge_weight_type;
114
115 typename property_map<Graph, edge_weight_t>::type em = get( edge_weight, g );
116
117 BGL_FORALL_VERTICES_T( v, g, Graph ) {
118 edge_weight_type tmp = 0;
119 BGL_FORALL_OUTEDGES_T( v, e, g, Graph ) {
120 tmp += em[e];
121 }
122 n[out_degree( v, g )] += 1.;
123 dist[out_degree( v, g )] += tmp;
124 }
125
126 for( std::map<unsigned long, double>::iterator iter = dist.begin();
127 iter != dist.end(); ++iter ) {
128 BOOST_ASSERT( n[iter->first] != 0 );
129 dist[iter->first] /= n[iter->first];
130 }
131
132 return dist;
133 }
134
135 }}
136
137 #endif
138