123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137 |
- // 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
|