boost/graph/graph_stats.hpp

0001 // Copyright 2005 The Trustees of Indiana University.
0002
0003 // Use, modification and distribution is subject to the Boost Software
0004 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006
0007 //  Authors: Alex Breuer
0008 //           Andrew Lumsdaine
0009 #ifndef BOOST_GRAPH_GRAPH_STATS_HPP
0010 #define BOOST_GRAPH_GRAPH_STATS_HPP
0011
0012 #include <map>
0013 #include <list>
0014 #include <boost/graph/graph_traits.hpp>
0015 #include <boost/graph/iteration_macros.hpp>
0016 #include <boost/graph/properties.hpp>
0017 #include <boost/assert.hpp>
0018
0019 namespace boost
0020 {
0021 namespace graph
0022 {
0023
0024     template < typename Graph > struct sort_edge_by_origin
0025     {
0026     public:
0027         typedef typename graph_traits< Graph >::edge_descriptor edge_type;
0028
0029         explicit sort_edge_by_origin(Graph& g) : g(g) {}
0030
0031         inline bool operator()(edge_type a, edge_type b)
0032         {
0033             return source(a, g) == source(b, g) ? target(a, g) < target(b, g)
0034                                                 : source(a, g) < source(b, g);
0035         }
0036
0037     private:
0038         Graph& g;
0039     };
0040
0041     template < typename Graph > struct equal_edge
0042     {
0043     public:
0044         typedef typename graph_traits< Graph >::edge_descriptor edge_type;
0045
0046         explicit equal_edge(Graph& g) : g(g) {}
0047
0048         inline bool operator()(edge_type a, edge_type b)
0049         {
0050             return source(a, g) == source(b, g) && target(a, g) == target(b, g);
0051         }
0052
0053     private:
0054         Graph& g;
0055     };
0056
0057     template < typename Graph > unsigned long num_dup_edges(Graph& g)
0058     {
0059         typedef typename graph_traits< Graph >::edge_iterator e_iterator_type;
0060         typedef typename graph_traits< Graph >::edge_descriptor edge_type;
0061
0062         std::list< edge_type > all_edges;
0063
0064         BGL_FORALL_EDGES_T(e, g, Graph) { all_edges.push_back(e); }
0065
0066         sort_edge_by_origin< Graph > cmp1(g);
0067         all_edges.sort(cmp1);
0068         equal_edge< Graph > cmp2(g);
0069         all_edges.unique(cmp2);
0070
0071         return num_edges(g) - all_edges.size();
0072     }
0073
0074     template < typename Graph >
0075     std::map< unsigned long, unsigned long > dup_edge_dist(Graph& g)
0076     {
0077         std::map< unsigned long, unsigned long > dist;
0078         typedef
0079             typename graph_traits< Graph >::adjacency_iterator a_iterator_type;
0080         typedef typename graph_traits< Graph >::vertex_descriptor vertex_type;
0081
0082         BGL_FORALL_VERTICES_T(v, g, Graph)
0083         {
0084             std::list< vertex_type > front_neighbors;
0085             a_iterator_type a_iter, a_end;
0086             for (boost::tie(a_iter, a_end) = adjacent_vertices(v, g);
0087                  a_iter != a_end; ++a_iter)
0088             {
0089                 front_neighbors.push_back(*a_iter);
0090             }
0091
0092             front_neighbors.sort();
0093             front_neighbors.unique();
0094             dist[out_degree(v, g) - front_neighbors.size()] += 1;
0095         }
0096         return dist;
0097     }
0098
0099     template < typename Graph >
0100     std::map< unsigned long, unsigned long > degree_dist(Graph& g)
0101     {
0102         std::map< unsigned long, unsigned long > dist;
0103         typedef
0104             typename graph_traits< Graph >::adjacency_iterator a_iterator_type;
0105         typedef typename graph_traits< Graph >::vertex_descriptor vertex_type;
0106
0107         BGL_FORALL_VERTICES_T(v, g, Graph) { dist[out_degree(v, g)] += 1; }
0108
0109         return dist;
0110     }
0111
0112     template < typename Graph >
0113     std::map< unsigned long, double > weight_degree_dist(Graph& g)
0114     {
0115         std::map< unsigned long, double > dist, n;
0116         typedef
0117             typename graph_traits< Graph >::adjacency_iterator a_iterator_type;
0118         typedef typename graph_traits< Graph >::vertex_descriptor vertex_type;
0119         typedef typename property_map< Graph, edge_weight_t >::const_type
0120             edge_map_type;
0121         typedef typename property_traits< edge_map_type >::value_type
0122             edge_weight_type;
0123
0124         typename property_map< Graph, edge_weight_t >::type em
0125             = get(edge_weight, g);
0126
0127         BGL_FORALL_VERTICES_T(v, g, Graph)
0128         {
0129             edge_weight_type tmp = 0;
0130             BGL_FORALL_OUTEDGES_T(v, e, g, Graph) { tmp += em[e]; }
0131             n[out_degree(v, g)] += 1.;
0132             dist[out_degree(v, g)] += tmp;
0133         }
0134
0135         for (std::map< unsigned long, double >::iterator iter = dist.begin();
0136              iter != dist.end(); ++iter)
0137         {
0138             BOOST_ASSERT(n[iter->first] != 0);
0139             dist[iter->first] /= n[iter->first];
0140         }
0141
0142         return dist;
0143     }
0144
0145 }
0146 }
0147
0148 #endif