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