]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
24 | explicit sort_edge_by_origin( Graph& g ) : g(g) {} | |
25 | ||
26 | 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 | ||
40 | explicit equal_edge( Graph& g ) : g(g) {} | |
41 | ||
42 | 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> | |
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> | |
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> | |
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> | |
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 |