path: root/boost/graph/core_numbers.hpp

//
//=======================================================================
// Copyright 2007 Stanford University
// Authors: David Gleich
//
// Distributed under 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)
//=======================================================================
//
#ifndef BOOST_GRAPH_CORE_NUMBERS_HPP
#define BOOST_GRAPH_CORE_NUMBERS_HPP

#include <boost/pending/mutable_queue.hpp>
#include <boost/pending/indirect_cmp.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/iterator/reverse_iterator.hpp>
#include <boost/concept/assert.hpp>

/*
 * core_numbers
 *
 * Requirement: IncidenceGraph
 */

// History
//
// 30 July 2007
// Added visitors to the implementation
//
// 8 February 2008
// Fixed headers and missing typename

namespace boost {

    // A linear time O(m) algorithm to compute the indegree core number
    // of a graph for unweighted graphs.
    //
    // and a O((n+m) log n) algorithm to compute the in-edge-weight core
    // numbers of a weighted graph.
    //
    // The linear algorithm comes from:
    // Vladimir Batagelj and Matjaz Zaversnik, "An O(m) Algorithm for Cores
    // Decomposition of Networks."  Sept. 1 2002.

    template <typename Visitor, typename Graph>
    struct CoreNumbersVisitorConcept {
        void constraints()
        {
            BOOST_CONCEPT_ASSERT(( CopyConstructibleConcept<Visitor> ));
            vis.examine_vertex(u,g);
            vis.finish_vertex(u,g);
            vis.examine_edge(e,g);
        }
        Visitor vis;
        Graph g;
        typename graph_traits<Graph>::vertex_descriptor u;
        typename graph_traits<Graph>::edge_descriptor e;
    };

    template <class Visitors = null_visitor>
    class core_numbers_visitor : public bfs_visitor<Visitors> {
        public:
        core_numbers_visitor() {}
        core_numbers_visitor(Visitors vis)
            : bfs_visitor<Visitors>(vis) {}

        private:
        template <class Vertex, class Graph>
        void initialize_vertex(Vertex, Graph&) {}

        template <class Vertex, class Graph>
        void discover_vertex(Vertex , Graph&) {}

        template <class Vertex, class Graph>
        void gray_target(Vertex, Graph&) {}

        template <class Vertex, class Graph>
        void black_target(Vertex, Graph&) {}

        template <class Edge, class Graph>
        void tree_edge(Edge, Graph&) {}

        template <class Edge, class Graph>
        void non_tree_edge(Edge, Graph&) {}
    };

    template <class Visitors>
    core_numbers_visitor<Visitors> make_core_numbers_visitor(Visitors vis)
    { return core_numbers_visitor<Visitors>(vis); }

    typedef core_numbers_visitor<> default_core_numbers_visitor;

    namespace detail {

        // implement a constant_property_map to simplify compute_in_degree
        // for the weighted and unweighted case
        // this is based on dummy property map
        template <typename ValueType>
        class constant_value_property_map
          : public boost::put_get_helper<ValueType,
              constant_value_property_map<ValueType>  >
        {
        public:
            typedef void key_type;
            typedef ValueType value_type;
            typedef const ValueType& reference;
            typedef boost::readable_property_map_tag category;
            inline constant_value_property_map(ValueType cc) : c(cc) { }
            inline constant_value_property_map(const constant_value_property_map<ValueType>& x)
              : c(x.c) { }
            template <class Vertex>
            inline reference operator[](Vertex) const { return c; }
        protected:
            ValueType c;
        };


        // the core numbers start as the indegree or inweight.  This function
        // will initialize these values
        template <typename Graph, typename CoreMap, typename EdgeWeightMap>
        void compute_in_degree_map(Graph& g, CoreMap d, EdgeWeightMap wm)
        {
            typename graph_traits<Graph>::vertex_iterator vi,vi_end;
            typename graph_traits<Graph>::out_edge_iterator ei,ei_end;
            for (boost::tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
                put(d,*vi,0);
            }
            for (boost::tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
                for (boost::tie(ei,ei_end) = out_edges(*vi,g); ei!=ei_end; ++ei) {
                    put(d,target(*ei,g),get(d,target(*ei,g))+get(wm,*ei));
                }
            }
        }

        // the version for weighted graphs is a little different
        template <typename Graph, typename CoreMap,
            typename EdgeWeightMap, typename MutableQueue,
            typename Visitor>
        typename property_traits<CoreMap>::value_type
        core_numbers_impl(Graph& g, CoreMap c, EdgeWeightMap wm,
            MutableQueue& Q, Visitor vis)
        {
            typename property_traits<CoreMap>::value_type v_cn = 0;
            typedef typename graph_traits<Graph>::vertex_descriptor vertex;
            while (!Q.empty())
            {
                // remove v from the Q, and then decrease the core numbers
                // of its successors
                vertex v = Q.top();
                vis.examine_vertex(v,g);
                Q.pop();
                v_cn = get(c,v);
                typename graph_traits<Graph>::out_edge_iterator oi,oi_end;
                for (boost::tie(oi,oi_end) = out_edges(v,g); oi!=oi_end; ++oi) {
                    vis.examine_edge(*oi,g);
                    vertex u = target(*oi,g);
                    // if c[u] > c[v], then u is still in the graph,
                    if (get(c,u) > v_cn) {
                        // remove the edge
                        put(c,u,get(c,u)-get(wm,*oi));
                        Q.update(u);
                    }
                }
                vis.finish_vertex(v,g);
            }
            return (v_cn);
        }

        template <typename Graph, typename CoreMap, typename EdgeWeightMap,
            typename IndexMap, typename CoreNumVisitor>
        typename property_traits<CoreMap>::value_type
        core_numbers_dispatch(Graph&g, CoreMap c, EdgeWeightMap wm,
            IndexMap im, CoreNumVisitor vis)
        {
            typedef typename property_traits<CoreMap>::value_type D;
            typedef std::less<D> Cmp;
            typedef indirect_cmp<CoreMap,Cmp > IndirectCmp;
            IndirectCmp icmp(c, Cmp());
            // build the mutable queue
            typedef typename graph_traits<Graph>::vertex_descriptor vertex;
            typedef mutable_queue<vertex, std::vector<vertex>, IndirectCmp,
                IndexMap> MutableQueue;
            MutableQueue Q(num_vertices(g), icmp, im);
            typename graph_traits<Graph>::vertex_iterator vi,vi_end;
            for (boost::tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
                Q.push(*vi);
            }
            return core_numbers_impl(g, c, wm, Q, vis);
        }

        // the version for the unweighted case
        // for this functions CoreMap must be initialized
        // with the in degree of each vertex
        template <typename Graph, typename CoreMap, typename PositionMap,
            typename Visitor>
        typename property_traits<CoreMap>::value_type
        core_numbers_impl(Graph& g, CoreMap c, PositionMap pos, Visitor vis)
        {
            typedef typename graph_traits<Graph>::vertices_size_type size_type;
            typedef typename graph_traits<Graph>::degree_size_type degree_type;
            typedef typename graph_traits<Graph>::vertex_descriptor vertex;
            typename graph_traits<Graph>::vertex_iterator vi,vi_end;

            // store the vertex core numbers
            typename property_traits<CoreMap>::value_type v_cn = 0;

            // compute the maximum degree (degrees are in the coremap)
            typename graph_traits<Graph>::degree_size_type max_deg = 0;
            for (boost::tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
                max_deg = (std::max<typename graph_traits<Graph>::degree_size_type>)(max_deg, get(c,*vi));
            }

            // store the vertices in bins by their degree
            // allocate two extra locations to ease boundary cases
            std::vector<size_type> bin(max_deg+2);
            for (boost::tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
                ++bin[get(c,*vi)];
            }

            // this loop sets bin[d] to the starting position of vertices
            // with degree d in the vert array for the bucket sort
            size_type cur_pos = 0;
            for (degree_type cur_deg = 0; cur_deg < max_deg+2; ++cur_deg) {
                degree_type tmp = bin[cur_deg];
                bin[cur_deg] = cur_pos;
                cur_pos += tmp;
            }

            // perform the bucket sort with pos and vert so that
            // pos[0] is the vertex of smallest degree
            std::vector<vertex> vert(num_vertices(g));
            for (boost::tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
                vertex v=*vi;
                size_type p=bin[get(c,v)];
                put(pos,v,p);
                vert[p]=v;
                ++bin[get(c,v)];
            }
            // we ``abused'' bin while placing the vertices, now,
            // we need to restore it
            std::copy(boost::make_reverse_iterator(bin.end()-2),
                boost::make_reverse_iterator(bin.begin()),
                boost::make_reverse_iterator(bin.end()-1));
            // now simulate removing the vertices
            for (size_type i=0; i < num_vertices(g); ++i) {
                vertex v = vert[i];
                vis.examine_vertex(v,g);
                v_cn = get(c,v);
                typename graph_traits<Graph>::out_edge_iterator oi,oi_end;
                for (boost::tie(oi,oi_end) = out_edges(v,g); oi!=oi_end; ++oi) {
                    vis.examine_edge(*oi,g);
                    vertex u = target(*oi,g);
                    // if c[u] > c[v], then u is still in the graph,
                    if (get(c,u) > v_cn) {
                        degree_type deg_u = get(c,u);
                        degree_type pos_u = get(pos,u);
                        // w is the first vertex with the same degree as u
                        // (this is the resort operation!)
                        degree_type pos_w = bin[deg_u];
                        vertex w = vert[pos_w];
                        if (u!=v) {
                            // swap u and w
                            put(pos,u,pos_w);
                            put(pos,w,pos_u);
                            vert[pos_w] = u;
                            vert[pos_u] = w;
                        }
                        // now, the vertices array is sorted assuming
                        // we perform the following step
                        // start the set of vertices with degree of u
                        // one into the future (this now points at vertex
                        // w which we swapped with u).
                        ++bin[deg_u];
                        // we are removing v from the graph, so u's degree
                        // decreases
                        put(c,u,get(c,u)-1);
                    }
                }
                vis.finish_vertex(v,g);
            }
            return v_cn;
        }

    } // namespace detail

    // non-named parameter version for the unweighted case
    template <typename Graph, typename CoreMap, typename CoreNumVisitor>
    typename property_traits<CoreMap>::value_type
    core_numbers(Graph& g, CoreMap c, CoreNumVisitor vis)
    {
        typedef typename graph_traits<Graph>::vertices_size_type size_type;
        detail::compute_in_degree_map(g,c,
            detail::constant_value_property_map<
                typename property_traits<CoreMap>::value_type>(1) );
        return detail::core_numbers_impl(g,c,
            make_iterator_property_map(
                std::vector<size_type>(num_vertices(g)).begin(),get(vertex_index, g)),
            vis
        );
    }

    // non-named paramter version for the unweighted case
    template <typename Graph, typename CoreMap>
    typename property_traits<CoreMap>::value_type
    core_numbers(Graph& g, CoreMap c)
    {
        return core_numbers(g, c, make_core_numbers_visitor(null_visitor()));
    }

    // non-named parameter version for the weighted case
    template <typename Graph, typename CoreMap, typename EdgeWeightMap,
        typename VertexIndexMap, typename CoreNumVisitor>
    typename property_traits<CoreMap>::value_type
    core_numbers(Graph& g, CoreMap c, EdgeWeightMap wm, VertexIndexMap vim,
        CoreNumVisitor vis)
    {
        typedef typename graph_traits<Graph>::vertices_size_type size_type;
        detail::compute_in_degree_map(g,c,wm);
        return detail::core_numbers_dispatch(g,c,wm,vim,vis);
    }

    // non-named parameter version for the weighted case
//    template <typename Graph, typename CoreMap, typename EdgeWeightMap>
//    typename property_traits<CoreMap>::value_type
//    core_numbers(Graph& g, CoreMap c, EdgeWeightMap wm)
//    {
//        typedef typename graph_traits<Graph>::vertices_size_type size_type;
//        detail::compute_in_degree_map(g,c,wm);
//        return detail::core_numbers_dispatch(g,c,wm,get(vertex_index,g),
//            make_core_numbers_visitor(null_visitor()));
//    }

    template <typename Graph, typename CoreMap>
    typename property_traits<CoreMap>::value_type
    weighted_core_numbers(Graph& g, CoreMap c)
    {
        return weighted_core_numbers(
            g,c, make_core_numbers_visitor(null_visitor())
        );
    }

    template <typename Graph, typename CoreMap, typename CoreNumVisitor>
    typename property_traits<CoreMap>::value_type
    weighted_core_numbers(Graph& g, CoreMap c, CoreNumVisitor vis)
    { return core_numbers(g,c,get(edge_weight,g),get(vertex_index,g),vis); }

} // namespace boost

#endif // BOOST_GRAPH_CORE_NUMBERS_HPP