Chris@16: //
Chris@16: //=======================================================================
Chris@16: // Copyright 2007 Stanford University
Chris@16: // Authors: David Gleich
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //=======================================================================
Chris@16: //
Chris@16: #ifndef BOOST_GRAPH_CORE_NUMBERS_HPP
Chris@16: #define BOOST_GRAPH_CORE_NUMBERS_HPP
Chris@16: 
Chris@16: #include <boost/graph/detail/d_ary_heap.hpp>
Chris@16: #include <boost/graph/breadth_first_search.hpp>
Chris@16: #include <boost/iterator/reverse_iterator.hpp>
Chris@16: #include <boost/concept/assert.hpp>
Chris@16: 
Chris@16: /*
Chris@16:  * core_numbers
Chris@16:  *
Chris@16:  * Requirement: IncidenceGraph
Chris@16:  */
Chris@16: 
Chris@16: // History
Chris@16: //
Chris@16: // 30 July 2007
Chris@16: // Added visitors to the implementation
Chris@16: //
Chris@16: // 8 February 2008
Chris@16: // Fixed headers and missing typename
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16:     // A linear time O(m) algorithm to compute the indegree core number
Chris@16:     // of a graph for unweighted graphs.
Chris@16:     //
Chris@16:     // and a O((n+m) log n) algorithm to compute the in-edge-weight core
Chris@16:     // numbers of a weighted graph.
Chris@16:     //
Chris@16:     // The linear algorithm comes from:
Chris@16:     // Vladimir Batagelj and Matjaz Zaversnik, "An O(m) Algorithm for Cores
Chris@16:     // Decomposition of Networks."  Sept. 1 2002.
Chris@16: 
Chris@16:     template <typename Visitor, typename Graph>
Chris@16:     struct CoreNumbersVisitorConcept {
Chris@16:         void constraints()
Chris@16:         {
Chris@16:             BOOST_CONCEPT_ASSERT(( CopyConstructibleConcept<Visitor> ));
Chris@16:             vis.examine_vertex(u,g);
Chris@16:             vis.finish_vertex(u,g);
Chris@16:             vis.examine_edge(e,g);
Chris@16:         }
Chris@16:         Visitor vis;
Chris@16:         Graph g;
Chris@16:         typename graph_traits<Graph>::vertex_descriptor u;
Chris@16:         typename graph_traits<Graph>::edge_descriptor e;
Chris@16:     };
Chris@16: 
Chris@16:     template <class Visitors = null_visitor>
Chris@16:     class core_numbers_visitor : public bfs_visitor<Visitors> {
Chris@16:         public:
Chris@16:         core_numbers_visitor() {}
Chris@16:         core_numbers_visitor(Visitors vis)
Chris@16:             : bfs_visitor<Visitors>(vis) {}
Chris@16: 
Chris@16:         private:
Chris@16:         template <class Vertex, class Graph>
Chris@16:         void initialize_vertex(Vertex, Graph&) {}
Chris@16: 
Chris@16:         template <class Vertex, class Graph>
Chris@16:         void discover_vertex(Vertex , Graph&) {}
Chris@16: 
Chris@16:         template <class Vertex, class Graph>
Chris@16:         void gray_target(Vertex, Graph&) {}
Chris@16: 
Chris@16:         template <class Vertex, class Graph>
Chris@16:         void black_target(Vertex, Graph&) {}
Chris@16: 
Chris@16:         template <class Edge, class Graph>
Chris@16:         void tree_edge(Edge, Graph&) {}
Chris@16: 
Chris@16:         template <class Edge, class Graph>
Chris@16:         void non_tree_edge(Edge, Graph&) {}
Chris@16:     };
Chris@16: 
Chris@16:     template <class Visitors>
Chris@16:     core_numbers_visitor<Visitors> make_core_numbers_visitor(Visitors vis)
Chris@16:     { return core_numbers_visitor<Visitors>(vis); }
Chris@16: 
Chris@16:     typedef core_numbers_visitor<> default_core_numbers_visitor;
Chris@16: 
Chris@16:     namespace detail {
Chris@16: 
Chris@16:         // implement a constant_property_map to simplify compute_in_degree
Chris@16:         // for the weighted and unweighted case
Chris@16:         // this is based on dummy property map
Chris@16:         template <typename ValueType>
Chris@16:         class constant_value_property_map
Chris@16:           : public boost::put_get_helper<ValueType,
Chris@16:               constant_value_property_map<ValueType>  >
Chris@16:         {
Chris@16:         public:
Chris@16:             typedef void key_type;
Chris@16:             typedef ValueType value_type;
Chris@16:             typedef const ValueType& reference;
Chris@16:             typedef boost::readable_property_map_tag category;
Chris@16:             inline constant_value_property_map(ValueType cc) : c(cc) { }
Chris@16:             inline constant_value_property_map(const constant_value_property_map<ValueType>& x)
Chris@16:               : c(x.c) { }
Chris@16:             template <class Vertex>
Chris@16:             inline reference operator[](Vertex) const { return c; }
Chris@16:         protected:
Chris@16:             ValueType c;
Chris@16:         };
Chris@16: 
Chris@16: 
Chris@16:         // the core numbers start as the indegree or inweight.  This function
Chris@16:         // will initialize these values
Chris@16:         template <typename Graph, typename CoreMap, typename EdgeWeightMap>
Chris@16:         void compute_in_degree_map(Graph& g, CoreMap d, EdgeWeightMap wm)
Chris@16:         {
Chris@16:             typename graph_traits<Graph>::vertex_iterator vi,vi_end;
Chris@16:             typename graph_traits<Graph>::out_edge_iterator ei,ei_end;
Chris@16:             for (boost::tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
Chris@16:                 put(d,*vi,0);
Chris@16:             }
Chris@16:             for (boost::tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
Chris@16:                 for (boost::tie(ei,ei_end) = out_edges(*vi,g); ei!=ei_end; ++ei) {
Chris@16:                     put(d,target(*ei,g),get(d,target(*ei,g))+get(wm,*ei));
Chris@16:                 }
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:         // the version for weighted graphs is a little different
Chris@16:         template <typename Graph, typename CoreMap,
Chris@16:             typename EdgeWeightMap, typename MutableQueue,
Chris@16:             typename Visitor>
Chris@16:         typename property_traits<CoreMap>::value_type
Chris@16:         core_numbers_impl(Graph& g, CoreMap c, EdgeWeightMap wm,
Chris@16:             MutableQueue& Q, Visitor vis)
Chris@16:         {
Chris@16:             typename property_traits<CoreMap>::value_type v_cn = 0;
Chris@16:             typedef typename graph_traits<Graph>::vertex_descriptor vertex;
Chris@16:             while (!Q.empty())
Chris@16:             {
Chris@16:                 // remove v from the Q, and then decrease the core numbers
Chris@16:                 // of its successors
Chris@16:                 vertex v = Q.top();
Chris@16:                 vis.examine_vertex(v,g);
Chris@16:                 Q.pop();
Chris@16:                 v_cn = get(c,v);
Chris@16:                 typename graph_traits<Graph>::out_edge_iterator oi,oi_end;
Chris@16:                 for (boost::tie(oi,oi_end) = out_edges(v,g); oi!=oi_end; ++oi) {
Chris@16:                     vis.examine_edge(*oi,g);
Chris@16:                     vertex u = target(*oi,g);
Chris@16:                     // if c[u] > c[v], then u is still in the graph,
Chris@16:                     if (get(c,u) > v_cn) {
Chris@16:                         // remove the edge
Chris@16:                         put(c,u,get(c,u)-get(wm,*oi));
Chris@16:                         if (Q.contains(u))
Chris@16:                           Q.update(u);
Chris@16:                     }
Chris@16:                 }
Chris@16:                 vis.finish_vertex(v,g);
Chris@16:             }
Chris@16:             return (v_cn);
Chris@16:         }
Chris@16: 
Chris@16:         template <typename Graph, typename CoreMap, typename EdgeWeightMap,
Chris@16:             typename IndexMap, typename CoreNumVisitor>
Chris@16:         typename property_traits<CoreMap>::value_type
Chris@16:         core_numbers_dispatch(Graph&g, CoreMap c, EdgeWeightMap wm,
Chris@16:             IndexMap im, CoreNumVisitor vis)
Chris@16:         {
Chris@16:             typedef typename property_traits<CoreMap>::value_type D;
Chris@16:             typedef std::less<D> Cmp;
Chris@16:             // build the mutable queue
Chris@16:             typedef typename graph_traits<Graph>::vertex_descriptor vertex;
Chris@16:             std::vector<std::size_t> index_in_heap_data(num_vertices(g));
Chris@16:             typedef iterator_property_map<std::vector<std::size_t>::iterator, IndexMap>
Chris@16:               index_in_heap_map_type;
Chris@16:             index_in_heap_map_type index_in_heap_map(index_in_heap_data.begin(), im);
Chris@16:             typedef d_ary_heap_indirect<vertex, 4, index_in_heap_map_type, CoreMap, Cmp> MutableQueue;
Chris@16:             MutableQueue Q(c, index_in_heap_map, Cmp());
Chris@16:             typename graph_traits<Graph>::vertex_iterator vi,vi_end;
Chris@16:             for (boost::tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
Chris@16:                 Q.push(*vi);
Chris@16:             }
Chris@16:             return core_numbers_impl(g, c, wm, Q, vis);
Chris@16:         }
Chris@16: 
Chris@16:         // the version for the unweighted case
Chris@16:         // for this functions CoreMap must be initialized
Chris@16:         // with the in degree of each vertex
Chris@16:         template <typename Graph, typename CoreMap, typename PositionMap,
Chris@16:             typename Visitor>
Chris@16:         typename property_traits<CoreMap>::value_type
Chris@16:         core_numbers_impl(Graph& g, CoreMap c, PositionMap pos, Visitor vis)
Chris@16:         {
Chris@16:             typedef typename graph_traits<Graph>::vertices_size_type size_type;
Chris@16:             typedef typename graph_traits<Graph>::degree_size_type degree_type;
Chris@16:             typedef typename graph_traits<Graph>::vertex_descriptor vertex;
Chris@16:             typename graph_traits<Graph>::vertex_iterator vi,vi_end;
Chris@16: 
Chris@16:             // store the vertex core numbers
Chris@16:             typename property_traits<CoreMap>::value_type v_cn = 0;
Chris@16: 
Chris@16:             // compute the maximum degree (degrees are in the coremap)
Chris@16:             typename graph_traits<Graph>::degree_size_type max_deg = 0;
Chris@16:             for (boost::tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
Chris@16:                 max_deg = (std::max<typename graph_traits<Graph>::degree_size_type>)(max_deg, get(c,*vi));
Chris@16:             }
Chris@16: 
Chris@16:             // store the vertices in bins by their degree
Chris@16:             // allocate two extra locations to ease boundary cases
Chris@16:             std::vector<size_type> bin(max_deg+2);
Chris@16:             for (boost::tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
Chris@16:                 ++bin[get(c,*vi)];
Chris@16:             }
Chris@16: 
Chris@16:             // this loop sets bin[d] to the starting position of vertices
Chris@16:             // with degree d in the vert array for the bucket sort
Chris@16:             size_type cur_pos = 0;
Chris@16:             for (degree_type cur_deg = 0; cur_deg < max_deg+2; ++cur_deg) {
Chris@16:                 degree_type tmp = bin[cur_deg];
Chris@16:                 bin[cur_deg] = cur_pos;
Chris@16:                 cur_pos += tmp;
Chris@16:             }
Chris@16: 
Chris@16:             // perform the bucket sort with pos and vert so that
Chris@16:             // pos[0] is the vertex of smallest degree
Chris@16:             std::vector<vertex> vert(num_vertices(g));
Chris@16:             for (boost::tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
Chris@16:                 vertex v=*vi;
Chris@16:                 size_type p=bin[get(c,v)];
Chris@16:                 put(pos,v,p);
Chris@16:                 vert[p]=v;
Chris@16:                 ++bin[get(c,v)];
Chris@16:             }
Chris@16:             // we ``abused'' bin while placing the vertices, now,
Chris@16:             // we need to restore it
Chris@16:             std::copy(boost::make_reverse_iterator(bin.end()-2),
Chris@16:                 boost::make_reverse_iterator(bin.begin()),
Chris@16:                 boost::make_reverse_iterator(bin.end()-1));
Chris@16:             // now simulate removing the vertices
Chris@16:             for (size_type i=0; i < num_vertices(g); ++i) {
Chris@16:                 vertex v = vert[i];
Chris@16:                 vis.examine_vertex(v,g);
Chris@16:                 v_cn = get(c,v);
Chris@16:                 typename graph_traits<Graph>::out_edge_iterator oi,oi_end;
Chris@16:                 for (boost::tie(oi,oi_end) = out_edges(v,g); oi!=oi_end; ++oi) {
Chris@16:                     vis.examine_edge(*oi,g);
Chris@16:                     vertex u = target(*oi,g);
Chris@16:                     // if c[u] > c[v], then u is still in the graph,
Chris@16:                     if (get(c,u) > v_cn) {
Chris@16:                         degree_type deg_u = get(c,u);
Chris@16:                         degree_type pos_u = get(pos,u);
Chris@16:                         // w is the first vertex with the same degree as u
Chris@16:                         // (this is the resort operation!)
Chris@16:                         degree_type pos_w = bin[deg_u];
Chris@16:                         vertex w = vert[pos_w];
Chris@16:                         if (u!=v) {
Chris@16:                             // swap u and w
Chris@16:                             put(pos,u,pos_w);
Chris@16:                             put(pos,w,pos_u);
Chris@16:                             vert[pos_w] = u;
Chris@16:                             vert[pos_u] = w;
Chris@16:                         }
Chris@16:                         // now, the vertices array is sorted assuming
Chris@16:                         // we perform the following step
Chris@16:                         // start the set of vertices with degree of u
Chris@16:                         // one into the future (this now points at vertex
Chris@16:                         // w which we swapped with u).
Chris@16:                         ++bin[deg_u];
Chris@16:                         // we are removing v from the graph, so u's degree
Chris@16:                         // decreases
Chris@16:                         put(c,u,get(c,u)-1);
Chris@16:                     }
Chris@16:                 }
Chris@16:                 vis.finish_vertex(v,g);
Chris@16:             }
Chris@16:             return v_cn;
Chris@16:         }
Chris@16: 
Chris@16:     } // namespace detail
Chris@16: 
Chris@16:     // non-named parameter version for the unweighted case
Chris@16:     template <typename Graph, typename CoreMap, typename CoreNumVisitor>
Chris@16:     typename property_traits<CoreMap>::value_type
Chris@16:     core_numbers(Graph& g, CoreMap c, CoreNumVisitor vis)
Chris@16:     {
Chris@16:         typedef typename graph_traits<Graph>::vertices_size_type size_type;
Chris@16:         detail::compute_in_degree_map(g,c,
Chris@16:             detail::constant_value_property_map<
Chris@16:                 typename property_traits<CoreMap>::value_type>(1) );
Chris@16:         return detail::core_numbers_impl(g,c,
Chris@16:             make_iterator_property_map(
Chris@16:                 std::vector<size_type>(num_vertices(g)).begin(),get(vertex_index, g)),
Chris@16:             vis
Chris@16:         );
Chris@16:     }
Chris@16: 
Chris@16:     // non-named paramter version for the unweighted case
Chris@16:     template <typename Graph, typename CoreMap>
Chris@16:     typename property_traits<CoreMap>::value_type
Chris@16:     core_numbers(Graph& g, CoreMap c)
Chris@16:     {
Chris@16:         return core_numbers(g, c, make_core_numbers_visitor(null_visitor()));
Chris@16:     }
Chris@16: 
Chris@16:     // non-named parameter version for the weighted case
Chris@16:     template <typename Graph, typename CoreMap, typename EdgeWeightMap,
Chris@16:         typename VertexIndexMap, typename CoreNumVisitor>
Chris@16:     typename property_traits<CoreMap>::value_type
Chris@16:     core_numbers(Graph& g, CoreMap c, EdgeWeightMap wm, VertexIndexMap vim,
Chris@16:         CoreNumVisitor vis)
Chris@16:     {
Chris@16:         detail::compute_in_degree_map(g,c,wm);
Chris@16:         return detail::core_numbers_dispatch(g,c,wm,vim,vis);
Chris@16:     }
Chris@16: 
Chris@16:     // non-named parameter version for the weighted case
Chris@16: //    template <typename Graph, typename CoreMap, typename EdgeWeightMap>
Chris@16: //    typename property_traits<CoreMap>::value_type
Chris@16: //    core_numbers(Graph& g, CoreMap c, EdgeWeightMap wm)
Chris@16: //    {
Chris@16: //        typedef typename graph_traits<Graph>::vertices_size_type size_type;
Chris@16: //        detail::compute_in_degree_map(g,c,wm);
Chris@16: //        return detail::core_numbers_dispatch(g,c,wm,get(vertex_index,g),
Chris@16: //            make_core_numbers_visitor(null_visitor()));
Chris@16: //    }
Chris@16: 
Chris@16:     template <typename Graph, typename CoreMap>
Chris@16:     typename property_traits<CoreMap>::value_type
Chris@16:     weighted_core_numbers(Graph& g, CoreMap c)
Chris@16:     {
Chris@16:         return weighted_core_numbers(
Chris@16:             g,c, make_core_numbers_visitor(null_visitor())
Chris@16:         );
Chris@16:     }
Chris@16: 
Chris@16:     template <typename Graph, typename CoreMap, typename CoreNumVisitor>
Chris@16:     typename property_traits<CoreMap>::value_type
Chris@16:     weighted_core_numbers(Graph& g, CoreMap c, CoreNumVisitor vis)
Chris@16:     { return core_numbers(g,c,get(edge_weight,g),get(vertex_index,g),vis); }
Chris@16: 
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #endif // BOOST_GRAPH_CORE_NUMBERS_HPP
Chris@16: