boost/graph/core_numbers.hpp

0001 //
0002 //=======================================================================
0003 // Copyright 2007 Stanford University
0004 // Authors: David Gleich
0005 //
0006 // Distributed under the Boost Software License, Version 1.0. (See
0007 // accompanying file LICENSE_1_0.txt or copy at
0008 // http://www.boost.org/LICENSE_1_0.txt)
0009 //=======================================================================
0010 //
0011 #ifndef BOOST_GRAPH_CORE_NUMBERS_HPP
0012 #define BOOST_GRAPH_CORE_NUMBERS_HPP
0013
0014 #include <boost/graph/detail/d_ary_heap.hpp>
0015 #include <boost/graph/breadth_first_search.hpp>
0016 #include <boost/iterator/reverse_iterator.hpp>
0017 #include <boost/concept/assert.hpp>
0018
0019 /*
0020  * core_numbers
0021  *
0022  * Requirement: IncidenceGraph
0023  */
0024
0025 // History
0026 //
0027 // 30 July 2007
0028 // Added visitors to the implementation
0029 //
0030 // 8 February 2008
0031 // Fixed headers and missing typename
0032
0033 namespace boost
0034 {
0035
0036 // A linear time O(m) algorithm to compute the indegree core number
0037 // of a graph for unweighted graphs.
0038 //
0039 // and a O((n+m) log n) algorithm to compute the in-edge-weight core
0040 // numbers of a weighted graph.
0041 //
0042 // The linear algorithm comes from:
0043 // Vladimir Batagelj and Matjaz Zaversnik, "An O(m) Algorithm for Cores
0044 // Decomposition of Networks."  Sept. 1 2002.
0045
0046 template < typename Visitor, typename Graph > struct CoreNumbersVisitorConcept
0047 {
0048     void constraints()
0049     {
0050         BOOST_CONCEPT_ASSERT((CopyConstructibleConcept< Visitor >));
0051         vis.examine_vertex(u, g);
0052         vis.finish_vertex(u, g);
0053         vis.examine_edge(e, g);
0054     }
0055     Visitor vis;
0056     Graph g;
0057     typename graph_traits< Graph >::vertex_descriptor u;
0058     typename graph_traits< Graph >::edge_descriptor e;
0059 };
0060
0061 template < class Visitors = null_visitor >
0062 class core_numbers_visitor : public bfs_visitor< Visitors >
0063 {
0064 public:
0065     core_numbers_visitor() {}
0066     core_numbers_visitor(Visitors vis) : bfs_visitor< Visitors >(vis) {}
0067
0068 private:
0069     template < class Vertex, class Graph >
0070     void initialize_vertex(Vertex, Graph&)
0071     {
0072     }
0073
0074     template < class Vertex, class Graph > void discover_vertex(Vertex, Graph&)
0075     {
0076     }
0077
0078     template < class Vertex, class Graph > void gray_target(Vertex, Graph&) {}
0079
0080     template < class Vertex, class Graph > void black_target(Vertex, Graph&) {}
0081
0082     template < class Edge, class Graph > void tree_edge(Edge, Graph&) {}
0083
0084     template < class Edge, class Graph > void non_tree_edge(Edge, Graph&) {}
0085 };
0086
0087 template < class Visitors >
0088 core_numbers_visitor< Visitors > make_core_numbers_visitor(Visitors vis)
0089 {
0090     return core_numbers_visitor< Visitors >(vis);
0091 }
0092
0093 typedef core_numbers_visitor<> default_core_numbers_visitor;
0094
0095 namespace detail
0096 {
0097
0098     // implement a constant_property_map to simplify compute_in_degree
0099     // for the weighted and unweighted case
0100     // this is based on dummy property map
0101     template < typename ValueType >
0102     class constant_value_property_map
0103     : public boost::put_get_helper< ValueType,
0104           constant_value_property_map< ValueType > >
0105     {
0106     public:
0107         typedef void key_type;
0108         typedef ValueType value_type;
0109         typedef const ValueType& reference;
0110         typedef boost::readable_property_map_tag category;
0111         inline constant_value_property_map(ValueType cc) : c(cc) {}
0112         inline constant_value_property_map(
0113             const constant_value_property_map< ValueType >& x)
0114         : c(x.c)
0115         {
0116         }
0117         template < class Vertex > inline reference operator[](Vertex) const
0118         {
0119             return c;
0120         }
0121
0122     protected:
0123         ValueType c;
0124     };
0125
0126     // the core numbers start as the indegree or inweight.  This function
0127     // will initialize these values
0128     template < typename Graph, typename CoreMap, typename EdgeWeightMap >
0129     void compute_in_degree_map(Graph& g, CoreMap d, EdgeWeightMap wm)
0130     {
0131         typename graph_traits< Graph >::vertex_iterator vi, vi_end;
0132         typename graph_traits< Graph >::out_edge_iterator ei, ei_end;
0133         for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
0134         {
0135             put(d, *vi, 0);
0136         }
0137         for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
0138         {
0139             for (boost::tie(ei, ei_end) = out_edges(*vi, g); ei != ei_end; ++ei)
0140             {
0141                 put(d, target(*ei, g), get(d, target(*ei, g)) + get(wm, *ei));
0142             }
0143         }
0144     }
0145
0146     // the version for weighted graphs is a little different
0147     template < typename Graph, typename CoreMap, typename EdgeWeightMap,
0148         typename MutableQueue, typename Visitor >
0149     typename property_traits< CoreMap >::value_type core_numbers_impl(
0150         Graph& g, CoreMap c, EdgeWeightMap wm, MutableQueue& Q, Visitor vis)
0151     {
0152         typename property_traits< CoreMap >::value_type v_cn = 0;
0153         typedef typename graph_traits< Graph >::vertex_descriptor vertex;
0154         while (!Q.empty())
0155         {
0156             // remove v from the Q, and then decrease the core numbers
0157             // of its successors
0158             vertex v = Q.top();
0159             vis.examine_vertex(v, g);
0160             Q.pop();
0161             v_cn = get(c, v);
0162             typename graph_traits< Graph >::out_edge_iterator oi, oi_end;
0163             for (boost::tie(oi, oi_end) = out_edges(v, g); oi != oi_end; ++oi)
0164             {
0165                 vis.examine_edge(*oi, g);
0166                 vertex u = target(*oi, g);
0167                 // if c[u] > c[v], then u is still in the graph,
0168                 if (get(c, u) > v_cn)
0169                 {
0170                     // remove the edge
0171                     put(c, u, get(c, u) - get(wm, *oi));
0172                     if (Q.contains(u))
0173                         Q.update(u);
0174                 }
0175             }
0176             vis.finish_vertex(v, g);
0177         }
0178         return (v_cn);
0179     }
0180
0181     template < typename Graph, typename CoreMap, typename EdgeWeightMap,
0182         typename IndexMap, typename CoreNumVisitor >
0183     typename property_traits< CoreMap >::value_type core_numbers_dispatch(
0184         Graph& g, CoreMap c, EdgeWeightMap wm, IndexMap im, CoreNumVisitor vis)
0185     {
0186         typedef typename property_traits< CoreMap >::value_type D;
0187         typedef std::less< D > Cmp;
0188         // build the mutable queue
0189         typedef typename graph_traits< Graph >::vertex_descriptor vertex;
0190         std::vector< std::size_t > index_in_heap_data(num_vertices(g));
0191         typedef iterator_property_map< std::vector< std::size_t >::iterator,
0192             IndexMap >
0193             index_in_heap_map_type;
0194         index_in_heap_map_type index_in_heap_map(
0195             index_in_heap_data.begin(), im);
0196         typedef d_ary_heap_indirect< vertex, 4, index_in_heap_map_type, CoreMap,
0197             Cmp >
0198             MutableQueue;
0199         MutableQueue Q(c, index_in_heap_map, Cmp());
0200         typename graph_traits< Graph >::vertex_iterator vi, vi_end;
0201         for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
0202         {
0203             Q.push(*vi);
0204         }
0205         return core_numbers_impl(g, c, wm, Q, vis);
0206     }
0207
0208     // the version for the unweighted case
0209     // for this functions CoreMap must be initialized
0210     // with the in degree of each vertex
0211     template < typename Graph, typename CoreMap, typename PositionMap,
0212         typename Visitor >
0213     typename property_traits< CoreMap >::value_type core_numbers_impl(
0214         Graph& g, CoreMap c, PositionMap pos, Visitor vis)
0215     {
0216         typedef typename graph_traits< Graph >::vertices_size_type size_type;
0217         typedef typename graph_traits< Graph >::degree_size_type degree_type;
0218         typedef typename graph_traits< Graph >::vertex_descriptor vertex;
0219         typename graph_traits< Graph >::vertex_iterator vi, vi_end;
0220
0221         // store the vertex core numbers
0222         typename property_traits< CoreMap >::value_type v_cn = 0;
0223
0224         // compute the maximum degree (degrees are in the coremap)
0225         typename graph_traits< Graph >::degree_size_type max_deg = 0;
0226         for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
0227         {
0228             max_deg = (std::max<
0229                 typename graph_traits< Graph >::degree_size_type >)(max_deg,
0230                 get(c, *vi));
0231         }
0232
0233         // store the vertices in bins by their degree
0234         // allocate two extra locations to ease boundary cases
0235         std::vector< size_type > bin(max_deg + 2);
0236         for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
0237         {
0238             ++bin[get(c, *vi)];
0239         }
0240
0241         // this loop sets bin[d] to the starting position of vertices
0242         // with degree d in the vert array for the bucket sort
0243         size_type cur_pos = 0;
0244         for (degree_type cur_deg = 0; cur_deg < max_deg + 2; ++cur_deg)
0245         {
0246             degree_type tmp = bin[cur_deg];
0247             bin[cur_deg] = cur_pos;
0248             cur_pos += tmp;
0249         }
0250
0251         // perform the bucket sort with pos and vert so that
0252         // pos[0] is the vertex of smallest degree
0253         std::vector< vertex > vert(num_vertices(g));
0254         for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
0255         {
0256             vertex v = *vi;
0257             size_type p = bin[get(c, v)];
0258             put(pos, v, p);
0259             vert[p] = v;
0260             ++bin[get(c, v)];
0261         }
0262         // we ``abused'' bin while placing the vertices, now,
0263         // we need to restore it
0264         std::copy(boost::make_reverse_iterator(bin.end() - 2),
0265             boost::make_reverse_iterator(bin.begin()),
0266             boost::make_reverse_iterator(bin.end() - 1));
0267         // now simulate removing the vertices
0268         for (size_type i = 0; i < num_vertices(g); ++i)
0269         {
0270             vertex v = vert[i];
0271             vis.examine_vertex(v, g);
0272             v_cn = get(c, v);
0273             typename graph_traits< Graph >::out_edge_iterator oi, oi_end;
0274             for (boost::tie(oi, oi_end) = out_edges(v, g); oi != oi_end; ++oi)
0275             {
0276                 vis.examine_edge(*oi, g);
0277                 vertex u = target(*oi, g);
0278                 // if c[u] > c[v], then u is still in the graph,
0279                 if (get(c, u) > v_cn)
0280                 {
0281                     degree_type deg_u = get(c, u);
0282                     degree_type pos_u = get(pos, u);
0283                     // w is the first vertex with the same degree as u
0284                     // (this is the resort operation!)
0285                     degree_type pos_w = bin[deg_u];
0286                     vertex w = vert[pos_w];
0287                     if (u != v)
0288                     {
0289                         // swap u and w
0290                         put(pos, u, pos_w);
0291                         put(pos, w, pos_u);
0292                         vert[pos_w] = u;
0293                         vert[pos_u] = w;
0294                     }
0295                     // now, the vertices array is sorted assuming
0296                     // we perform the following step
0297                     // start the set of vertices with degree of u
0298                     // one into the future (this now points at vertex
0299                     // w which we swapped with u).
0300                     ++bin[deg_u];
0301                     // we are removing v from the graph, so u's degree
0302                     // decreases
0303                     put(c, u, get(c, u) - 1);
0304                 }
0305             }
0306             vis.finish_vertex(v, g);
0307         }
0308         return v_cn;
0309     }
0310
0311 } // namespace detail
0312
0313 // non-named parameter version for the unweighted case
0314 template < typename Graph, typename CoreMap, typename CoreNumVisitor >
0315 typename property_traits< CoreMap >::value_type core_numbers(
0316     Graph& g, CoreMap c, CoreNumVisitor vis)
0317 {
0318     typedef typename graph_traits< Graph >::vertices_size_type size_type;
0319     detail::compute_in_degree_map(g, c,
0320         detail::constant_value_property_map<
0321             typename property_traits< CoreMap >::value_type >(1));
0322     return detail::core_numbers_impl(g, c,
0323         make_iterator_property_map(
0324             std::vector< size_type >(num_vertices(g)).begin(),
0325             get(vertex_index, g)),
0326         vis);
0327 }
0328
0329 // non-named paramter version for the unweighted case
0330 template < typename Graph, typename CoreMap >
0331 typename property_traits< CoreMap >::value_type core_numbers(
0332     Graph& g, CoreMap c)
0333 {
0334     return core_numbers(g, c, make_core_numbers_visitor(null_visitor()));
0335 }
0336
0337 // non-named parameter version for the weighted case
0338 template < typename Graph, typename CoreMap, typename EdgeWeightMap,
0339     typename VertexIndexMap, typename CoreNumVisitor >
0340 typename property_traits< CoreMap >::value_type core_numbers(Graph& g,
0341     CoreMap c, EdgeWeightMap wm, VertexIndexMap vim, CoreNumVisitor vis)
0342 {
0343     detail::compute_in_degree_map(g, c, wm);
0344     return detail::core_numbers_dispatch(g, c, wm, vim, vis);
0345 }
0346
0347 // non-named parameter version for the weighted case
0348 //    template <typename Graph, typename CoreMap, typename EdgeWeightMap>
0349 //    typename property_traits<CoreMap>::value_type
0350 //    core_numbers(Graph& g, CoreMap c, EdgeWeightMap wm)
0351 //    {
0352 //        typedef typename graph_traits<Graph>::vertices_size_type size_type;
0353 //        detail::compute_in_degree_map(g,c,wm);
0354 //        return detail::core_numbers_dispatch(g,c,wm,get(vertex_index,g),
0355 //            make_core_numbers_visitor(null_visitor()));
0356 //    }
0357
0358 template < typename Graph, typename CoreMap >
0359 typename property_traits< CoreMap >::value_type weighted_core_numbers(
0360     Graph& g, CoreMap c)
0361 {
0362     return weighted_core_numbers(
0363         g, c, make_core_numbers_visitor(null_visitor()));
0364 }
0365
0366 template < typename Graph, typename CoreMap, typename CoreNumVisitor >
0367 typename property_traits< CoreMap >::value_type weighted_core_numbers(
0368     Graph& g, CoreMap c, CoreNumVisitor vis)
0369 {
0370     return core_numbers(g, c, get(edge_weight, g), get(vertex_index, g), vis);
0371 }
0372
0373 } // namespace boost
0374
0375 #endif // BOOST_GRAPH_CORE_NUMBERS_HPP