ceph/src/boost/boost/graph/graph_stats.hpp

   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