1 // Copyright 2005 The Trustees of Indiana University.
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)
7 // Authors: Alex Breuer
9 #ifndef BOOST_GRAPH_GRAPH_STATS_HPP
10 #define BOOST_GRAPH_GRAPH_STATS_HPP
14 #include <boost/graph/iteration_macros.hpp>
16 namespace boost
{ namespace graph
{
18 template<typename Graph
>
19 struct sort_edge_by_origin
{
21 typedef typename graph_traits
<Graph
>::edge_descriptor edge_type
;
23 explicit sort_edge_by_origin( Graph
& g
) : g(g
) {}
25 inline bool operator()( edge_type a
, edge_type b
) {
26 return source( a
, g
) == source( b
, g
) ? target( a
, g
) < target( b
, g
) :
27 source( a
, g
) < source( b
, g
);
34 template<typename Graph
>
37 typedef typename graph_traits
<Graph
>::edge_descriptor edge_type
;
39 explicit equal_edge( Graph
& g
) : g(g
) {}
41 inline bool operator()( edge_type a
, edge_type b
) {
42 return source( a
, g
) == source( b
, g
) &&
43 target( a
, g
) == target( b
, g
);
50 template<typename Graph
>
51 unsigned long num_dup_edges( Graph
& g
) {
52 typedef typename graph_traits
<Graph
>::edge_iterator e_iterator_type
;
53 typedef typename graph_traits
<Graph
>::edge_descriptor edge_type
;
55 std::list
<edge_type
> all_edges
;
57 BGL_FORALL_EDGES_T( e
, g
, Graph
) {
58 all_edges
.push_back( e
);
61 sort_edge_by_origin
<Graph
> cmp1( g
);
62 all_edges
.sort( cmp1
);
63 equal_edge
<Graph
> cmp2( g
);
64 all_edges
.unique( cmp2
);
66 return num_edges( g
) - all_edges
.size();
70 template<typename Graph
>
71 std::map
<unsigned long, unsigned long> dup_edge_dist( Graph
& g
) {
72 std::map
<unsigned long, unsigned long> dist
;
73 typedef typename graph_traits
<Graph
>::adjacency_iterator a_iterator_type
;
74 typedef typename graph_traits
<Graph
>::vertex_descriptor vertex_type
;
77 BGL_FORALL_VERTICES_T( v
, g
, Graph
) {
78 std::list
<vertex_type
> front_neighbors
;
79 a_iterator_type a_iter
, a_end
;
80 for( tie( a_iter
, a_end
) = adjacent_vertices( v
, g
);
81 a_iter
!= a_end
; ++a_iter
) {
82 front_neighbors
.push_back( *a_iter
);
85 front_neighbors
.sort();
86 front_neighbors
.unique();
87 dist
[out_degree( v
, g
) - front_neighbors
.size()] += 1;
92 template<typename Graph
>
93 std::map
<unsigned long, unsigned long> degree_dist( Graph
& g
) {
94 std::map
<unsigned long, unsigned long> dist
;
95 typedef typename graph_traits
<Graph
>::adjacency_iterator a_iterator_type
;
96 typedef typename graph_traits
<Graph
>::vertex_descriptor vertex_type
;
98 BGL_FORALL_VERTICES_T( v
, g
, Graph
) {
99 dist
[out_degree( v
, g
)] += 1;
105 template<typename Graph
>
106 std::map
<unsigned long, double> weight_degree_dist( Graph
& g
) {
107 std::map
<unsigned long, double> dist
, n
;
108 typedef typename graph_traits
<Graph
>::adjacency_iterator a_iterator_type
;
109 typedef typename graph_traits
<Graph
>::vertex_descriptor vertex_type
;
110 typedef typename property_map
<Graph
, edge_weight_t
>::const_type edge_map_type
;
111 typedef typename property_traits
<edge_map_type
>::value_type
114 typename property_map
<Graph
, edge_weight_t
>::type em
= get( edge_weight
, g
);
116 BGL_FORALL_VERTICES_T( v
, g
, Graph
) {
117 edge_weight_type tmp
= 0;
118 BGL_FORALL_OUTEDGES_T( v
, e
, g
, Graph
) {
121 n
[out_degree( v
, g
)] += 1.;
122 dist
[out_degree( v
, g
)] += tmp
;
125 for( std::map
<unsigned long, double>::iterator iter
= dist
.begin();
126 iter
!= dist
.end(); ++iter
) {
127 assert( n
[iter
->first
] != 0 );
128 dist
[iter
->first
] /= n
[iter
->first
];