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