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