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/iteration_macros.hpp>
0015 #include <boost/assert.hpp>
0016
0017 namespace boost
0018 {
0019 namespace graph
0020 {
0021
0022     template < typename Graph > struct sort_edge_by_origin
0023     {
0024     public:
0025         typedef typename graph_traits< Graph >::edge_descriptor edge_type;
0026
0027         explicit sort_edge_by_origin(Graph& g) : g(g) {}
0028
0029         inline bool operator()(edge_type a, edge_type b)
0030         {
0031             return source(a, g) == source(b, g) ? target(a, g) < target(b, g)
0032                                                 : source(a, g) < source(b, g);
0033         }
0034
0035     private:
0036         Graph& g;
0037     };
0038
0039     template < typename Graph > struct equal_edge
0040     {
0041     public:
0042         typedef typename graph_traits< Graph >::edge_descriptor edge_type;
0043
0044         explicit equal_edge(Graph& g) : g(g) {}
0045
0046         inline bool operator()(edge_type a, edge_type b)
0047         {
0048             return source(a, g) == source(b, g) && target(a, g) == target(b, g);
0049         }
0050
0051     private:
0052         Graph& g;
0053     };
0054
0055     template < typename Graph > unsigned long num_dup_edges(Graph& g)
0056     {
0057         typedef typename graph_traits< Graph >::edge_iterator e_iterator_type;
0058         typedef typename graph_traits< Graph >::edge_descriptor edge_type;
0059
0060         std::list< edge_type > all_edges;
0061
0062         BGL_FORALL_EDGES_T(e, g, Graph) { all_edges.push_back(e); }
0063
0064         sort_edge_by_origin< Graph > cmp1(g);
0065         all_edges.sort(cmp1);
0066         equal_edge< Graph > cmp2(g);
0067         all_edges.unique(cmp2);
0068
0069         return num_edges(g) - all_edges.size();
0070     }
0071
0072     template < typename Graph >
0073     std::map< unsigned long, unsigned long > dup_edge_dist(Graph& g)
0074     {
0075         std::map< unsigned long, unsigned long > dist;
0076         typedef
0077             typename graph_traits< Graph >::adjacency_iterator a_iterator_type;
0078         typedef typename graph_traits< Graph >::vertex_descriptor vertex_type;
0079
0080         BGL_FORALL_VERTICES_T(v, g, Graph)
0081         {
0082             std::list< vertex_type > front_neighbors;
0083             a_iterator_type a_iter, a_end;
0084             for (boost::tie(a_iter, a_end) = adjacent_vertices(v, g);
0085                  a_iter != a_end; ++a_iter)
0086             {
0087                 front_neighbors.push_back(*a_iter);
0088             }
0089
0090             front_neighbors.sort();
0091             front_neighbors.unique();
0092             dist[out_degree(v, g) - front_neighbors.size()] += 1;
0093         }
0094         return dist;
0095     }
0096
0097     template < typename Graph >
0098     std::map< unsigned long, unsigned long > degree_dist(Graph& g)
0099     {
0100         std::map< unsigned long, unsigned long > dist;
0101         typedef
0102             typename graph_traits< Graph >::adjacency_iterator a_iterator_type;
0103         typedef typename graph_traits< Graph >::vertex_descriptor vertex_type;
0104
0105         BGL_FORALL_VERTICES_T(v, g, Graph) { dist[out_degree(v, g)] += 1; }
0106
0107         return dist;
0108     }
0109
0110     template < typename Graph >
0111     std::map< unsigned long, double > weight_degree_dist(Graph& g)
0112     {
0113         std::map< unsigned long, double > dist, n;
0114         typedef
0115             typename graph_traits< Graph >::adjacency_iterator a_iterator_type;
0116         typedef typename graph_traits< Graph >::vertex_descriptor vertex_type;
0117         typedef typename property_map< Graph, edge_weight_t >::const_type
0118             edge_map_type;
0119         typedef typename property_traits< edge_map_type >::value_type
0120             edge_weight_type;
0121
0122         typename property_map< Graph, edge_weight_t >::type em
0123             = get(edge_weight, g);
0124
0125         BGL_FORALL_VERTICES_T(v, g, Graph)
0126         {
0127             edge_weight_type tmp = 0;
0128             BGL_FORALL_OUTEDGES_T(v, e, g, Graph) { tmp += em[e]; }
0129             n[out_degree(v, g)] += 1.;
0130             dist[out_degree(v, g)] += tmp;
0131         }
0132
0133         for (std::map< unsigned long, double >::iterator iter = dist.begin();
0134              iter != dist.end(); ++iter)
0135         {
0136             BOOST_ASSERT(n[iter->first] != 0);
0137             dist[iter->first] /= n[iter->first];
0138         }
0139
0140         return dist;
0141     }
0142
0143 }
0144 }
0145
0146 #endif