1 //
2 //=======================================================================
3 // Copyright 2007 Stanford University
4 // Authors: David Gleich
5 //
6 // Distributed under the Boost Software License, Version 1.0. (See
7 // accompanying file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
9 //=======================================================================
10 //
11 #ifndef BOOST_GRAPH_CORE_NUMBERS_HPP
12 #define BOOST_GRAPH_CORE_NUMBERS_HPP
13 
14 #include <boost/graph/detail/d_ary_heap.hpp>
15 #include <boost/graph/breadth_first_search.hpp>
16 #include <boost/iterator/reverse_iterator.hpp>
17 #include <boost/concept/assert.hpp>
18 
19 /*
20  * core_numbers
21  *
22  * Requirement: IncidenceGraph
23  */
24 
25 // History
26 //
27 // 30 July 2007
28 // Added visitors to the implementation
29 //
30 // 8 February 2008
31 // Fixed headers and missing typename
32 
33 namespace boost {
34 
35     // A linear time O(m) algorithm to compute the indegree core number
36     // of a graph for unweighted graphs.
37     //
38     // and a O((n+m) log n) algorithm to compute the in-edge-weight core
39     // numbers of a weighted graph.
40     //
41     // The linear algorithm comes from:
42     // Vladimir Batagelj and Matjaz Zaversnik, "An O(m) Algorithm for Cores
43     // Decomposition of Networks."  Sept. 1 2002.
44 
45     template <typename Visitor, typename Graph>
46     struct CoreNumbersVisitorConcept {
constraintsboost::CoreNumbersVisitorConcept47         void constraints()
48         {
49             BOOST_CONCEPT_ASSERT(( CopyConstructibleConcept<Visitor> ));
50             vis.examine_vertex(u,g);
51             vis.finish_vertex(u,g);
52             vis.examine_edge(e,g);
53         }
54         Visitor vis;
55         Graph g;
56         typename graph_traits<Graph>::vertex_descriptor u;
57         typename graph_traits<Graph>::edge_descriptor e;
58     };
59 
60     template <class Visitors = null_visitor>
61     class core_numbers_visitor : public bfs_visitor<Visitors> {
62         public:
core_numbers_visitor()63         core_numbers_visitor() {}
core_numbers_visitor(Visitors vis)64         core_numbers_visitor(Visitors vis)
65             : bfs_visitor<Visitors>(vis) {}
66 
67         private:
68         template <class Vertex, class Graph>
initialize_vertex(Vertex,Graph &)69         void initialize_vertex(Vertex, Graph&) {}
70 
71         template <class Vertex, class Graph>
discover_vertex(Vertex,Graph &)72         void discover_vertex(Vertex , Graph&) {}
73 
74         template <class Vertex, class Graph>
gray_target(Vertex,Graph &)75         void gray_target(Vertex, Graph&) {}
76 
77         template <class Vertex, class Graph>
black_target(Vertex,Graph &)78         void black_target(Vertex, Graph&) {}
79 
80         template <class Edge, class Graph>
tree_edge(Edge,Graph &)81         void tree_edge(Edge, Graph&) {}
82 
83         template <class Edge, class Graph>
non_tree_edge(Edge,Graph &)84         void non_tree_edge(Edge, Graph&) {}
85     };
86 
87     template <class Visitors>
make_core_numbers_visitor(Visitors vis)88     core_numbers_visitor<Visitors> make_core_numbers_visitor(Visitors vis)
89     { return core_numbers_visitor<Visitors>(vis); }
90 
91     typedef core_numbers_visitor<> default_core_numbers_visitor;
92 
93     namespace detail {
94 
95         // implement a constant_property_map to simplify compute_in_degree
96         // for the weighted and unweighted case
97         // this is based on dummy property map
98         template <typename ValueType>
99         class constant_value_property_map
100           : public boost::put_get_helper<ValueType,
101               constant_value_property_map<ValueType>  >
102         {
103         public:
104             typedef void key_type;
105             typedef ValueType value_type;
106             typedef const ValueType& reference;
107             typedef boost::readable_property_map_tag category;
constant_value_property_map(ValueType cc)108             inline constant_value_property_map(ValueType cc) : c(cc) { }
constant_value_property_map(const constant_value_property_map<ValueType> & x)109             inline constant_value_property_map(const constant_value_property_map<ValueType>& x)
110               : c(x.c) { }
111             template <class Vertex>
operator [](Vertex) const112             inline reference operator[](Vertex) const { return c; }
113         protected:
114             ValueType c;
115         };
116 
117 
118         // the core numbers start as the indegree or inweight.  This function
119         // will initialize these values
120         template <typename Graph, typename CoreMap, typename EdgeWeightMap>
compute_in_degree_map(Graph & g,CoreMap d,EdgeWeightMap wm)121         void compute_in_degree_map(Graph& g, CoreMap d, EdgeWeightMap wm)
122         {
123             typename graph_traits<Graph>::vertex_iterator vi,vi_end;
124             typename graph_traits<Graph>::out_edge_iterator ei,ei_end;
125             for (boost::tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
126                 put(d,*vi,0);
127             }
128             for (boost::tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
129                 for (boost::tie(ei,ei_end) = out_edges(*vi,g); ei!=ei_end; ++ei) {
130                     put(d,target(*ei,g),get(d,target(*ei,g))+get(wm,*ei));
131                 }
132             }
133         }
134 
135         // the version for weighted graphs is a little different
136         template <typename Graph, typename CoreMap,
137             typename EdgeWeightMap, typename MutableQueue,
138             typename Visitor>
139         typename property_traits<CoreMap>::value_type
core_numbers_impl(Graph & g,CoreMap c,EdgeWeightMap wm,MutableQueue & Q,Visitor vis)140         core_numbers_impl(Graph& g, CoreMap c, EdgeWeightMap wm,
141             MutableQueue& Q, Visitor vis)
142         {
143             typename property_traits<CoreMap>::value_type v_cn = 0;
144             typedef typename graph_traits<Graph>::vertex_descriptor vertex;
145             while (!Q.empty())
146             {
147                 // remove v from the Q, and then decrease the core numbers
148                 // of its successors
149                 vertex v = Q.top();
150                 vis.examine_vertex(v,g);
151                 Q.pop();
152                 v_cn = get(c,v);
153                 typename graph_traits<Graph>::out_edge_iterator oi,oi_end;
154                 for (boost::tie(oi,oi_end) = out_edges(v,g); oi!=oi_end; ++oi) {
155                     vis.examine_edge(*oi,g);
156                     vertex u = target(*oi,g);
157                     // if c[u] > c[v], then u is still in the graph,
158                     if (get(c,u) > v_cn) {
159                         // remove the edge
160                         put(c,u,get(c,u)-get(wm,*oi));
161                         if (Q.contains(u))
162                           Q.update(u);
163                     }
164                 }
165                 vis.finish_vertex(v,g);
166             }
167             return (v_cn);
168         }
169 
170         template <typename Graph, typename CoreMap, typename EdgeWeightMap,
171             typename IndexMap, typename CoreNumVisitor>
172         typename property_traits<CoreMap>::value_type
core_numbers_dispatch(Graph & g,CoreMap c,EdgeWeightMap wm,IndexMap im,CoreNumVisitor vis)173         core_numbers_dispatch(Graph&g, CoreMap c, EdgeWeightMap wm,
174             IndexMap im, CoreNumVisitor vis)
175         {
176             typedef typename property_traits<CoreMap>::value_type D;
177             typedef std::less<D> Cmp;
178             // build the mutable queue
179             typedef typename graph_traits<Graph>::vertex_descriptor vertex;
180             std::vector<std::size_t> index_in_heap_data(num_vertices(g));
181             typedef iterator_property_map<std::vector<std::size_t>::iterator, IndexMap>
182               index_in_heap_map_type;
183             index_in_heap_map_type index_in_heap_map(index_in_heap_data.begin(), im);
184             typedef d_ary_heap_indirect<vertex, 4, index_in_heap_map_type, CoreMap, Cmp> MutableQueue;
185             MutableQueue Q(c, index_in_heap_map, Cmp());
186             typename graph_traits<Graph>::vertex_iterator vi,vi_end;
187             for (boost::tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
188                 Q.push(*vi);
189             }
190             return core_numbers_impl(g, c, wm, Q, vis);
191         }
192 
193         // the version for the unweighted case
194         // for this functions CoreMap must be initialized
195         // with the in degree of each vertex
196         template <typename Graph, typename CoreMap, typename PositionMap,
197             typename Visitor>
198         typename property_traits<CoreMap>::value_type
core_numbers_impl(Graph & g,CoreMap c,PositionMap pos,Visitor vis)199         core_numbers_impl(Graph& g, CoreMap c, PositionMap pos, Visitor vis)
200         {
201             typedef typename graph_traits<Graph>::vertices_size_type size_type;
202             typedef typename graph_traits<Graph>::degree_size_type degree_type;
203             typedef typename graph_traits<Graph>::vertex_descriptor vertex;
204             typename graph_traits<Graph>::vertex_iterator vi,vi_end;
205 
206             // store the vertex core numbers
207             typename property_traits<CoreMap>::value_type v_cn = 0;
208 
209             // compute the maximum degree (degrees are in the coremap)
210             typename graph_traits<Graph>::degree_size_type max_deg = 0;
211             for (boost::tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
212                 max_deg = (std::max<typename graph_traits<Graph>::degree_size_type>)(max_deg, get(c,*vi));
213             }
214 
215             // store the vertices in bins by their degree
216             // allocate two extra locations to ease boundary cases
217             std::vector<size_type> bin(max_deg+2);
218             for (boost::tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
219                 ++bin[get(c,*vi)];
220             }
221 
222             // this loop sets bin[d] to the starting position of vertices
223             // with degree d in the vert array for the bucket sort
224             size_type cur_pos = 0;
225             for (degree_type cur_deg = 0; cur_deg < max_deg+2; ++cur_deg) {
226                 degree_type tmp = bin[cur_deg];
227                 bin[cur_deg] = cur_pos;
228                 cur_pos += tmp;
229             }
230 
231             // perform the bucket sort with pos and vert so that
232             // pos[0] is the vertex of smallest degree
233             std::vector<vertex> vert(num_vertices(g));
234             for (boost::tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
235                 vertex v=*vi;
236                 size_type p=bin[get(c,v)];
237                 put(pos,v,p);
238                 vert[p]=v;
239                 ++bin[get(c,v)];
240             }
241             // we ``abused'' bin while placing the vertices, now,
242             // we need to restore it
243             std::copy(boost::make_reverse_iterator(bin.end()-2),
244                 boost::make_reverse_iterator(bin.begin()),
245                 boost::make_reverse_iterator(bin.end()-1));
246             // now simulate removing the vertices
247             for (size_type i=0; i < num_vertices(g); ++i) {
248                 vertex v = vert[i];
249                 vis.examine_vertex(v,g);
250                 v_cn = get(c,v);
251                 typename graph_traits<Graph>::out_edge_iterator oi,oi_end;
252                 for (boost::tie(oi,oi_end) = out_edges(v,g); oi!=oi_end; ++oi) {
253                     vis.examine_edge(*oi,g);
254                     vertex u = target(*oi,g);
255                     // if c[u] > c[v], then u is still in the graph,
256                     if (get(c,u) > v_cn) {
257                         degree_type deg_u = get(c,u);
258                         degree_type pos_u = get(pos,u);
259                         // w is the first vertex with the same degree as u
260                         // (this is the resort operation!)
261                         degree_type pos_w = bin[deg_u];
262                         vertex w = vert[pos_w];
263                         if (u!=v) {
264                             // swap u and w
265                             put(pos,u,pos_w);
266                             put(pos,w,pos_u);
267                             vert[pos_w] = u;
268                             vert[pos_u] = w;
269                         }
270                         // now, the vertices array is sorted assuming
271                         // we perform the following step
272                         // start the set of vertices with degree of u
273                         // one into the future (this now points at vertex
274                         // w which we swapped with u).
275                         ++bin[deg_u];
276                         // we are removing v from the graph, so u's degree
277                         // decreases
278                         put(c,u,get(c,u)-1);
279                     }
280                 }
281                 vis.finish_vertex(v,g);
282             }
283             return v_cn;
284         }
285 
286     } // namespace detail
287 
288     // non-named parameter version for the unweighted case
289     template <typename Graph, typename CoreMap, typename CoreNumVisitor>
290     typename property_traits<CoreMap>::value_type
core_numbers(Graph & g,CoreMap c,CoreNumVisitor vis)291     core_numbers(Graph& g, CoreMap c, CoreNumVisitor vis)
292     {
293         typedef typename graph_traits<Graph>::vertices_size_type size_type;
294         detail::compute_in_degree_map(g,c,
295             detail::constant_value_property_map<
296                 typename property_traits<CoreMap>::value_type>(1) );
297         return detail::core_numbers_impl(g,c,
298             make_iterator_property_map(
299                 std::vector<size_type>(num_vertices(g)).begin(),get(vertex_index, g)),
300             vis
301         );
302     }
303 
304     // non-named paramter version for the unweighted case
305     template <typename Graph, typename CoreMap>
306     typename property_traits<CoreMap>::value_type
core_numbers(Graph & g,CoreMap c)307     core_numbers(Graph& g, CoreMap c)
308     {
309         return core_numbers(g, c, make_core_numbers_visitor(null_visitor()));
310     }
311 
312     // non-named parameter version for the weighted case
313     template <typename Graph, typename CoreMap, typename EdgeWeightMap,
314         typename VertexIndexMap, typename CoreNumVisitor>
315     typename property_traits<CoreMap>::value_type
core_numbers(Graph & g,CoreMap c,EdgeWeightMap wm,VertexIndexMap vim,CoreNumVisitor vis)316     core_numbers(Graph& g, CoreMap c, EdgeWeightMap wm, VertexIndexMap vim,
317         CoreNumVisitor vis)
318     {
319         detail::compute_in_degree_map(g,c,wm);
320         return detail::core_numbers_dispatch(g,c,wm,vim,vis);
321     }
322 
323     // non-named parameter version for the weighted case
324 //    template <typename Graph, typename CoreMap, typename EdgeWeightMap>
325 //    typename property_traits<CoreMap>::value_type
326 //    core_numbers(Graph& g, CoreMap c, EdgeWeightMap wm)
327 //    {
328 //        typedef typename graph_traits<Graph>::vertices_size_type size_type;
329 //        detail::compute_in_degree_map(g,c,wm);
330 //        return detail::core_numbers_dispatch(g,c,wm,get(vertex_index,g),
331 //            make_core_numbers_visitor(null_visitor()));
332 //    }
333 
334     template <typename Graph, typename CoreMap>
335     typename property_traits<CoreMap>::value_type
weighted_core_numbers(Graph & g,CoreMap c)336     weighted_core_numbers(Graph& g, CoreMap c)
337     {
338         return weighted_core_numbers(
339             g,c, make_core_numbers_visitor(null_visitor())
340         );
341     }
342 
343     template <typename Graph, typename CoreMap, typename CoreNumVisitor>
344     typename property_traits<CoreMap>::value_type
weighted_core_numbers(Graph & g,CoreMap c,CoreNumVisitor vis)345     weighted_core_numbers(Graph& g, CoreMap c, CoreNumVisitor vis)
346     { return core_numbers(g,c,get(edge_weight,g),get(vertex_index,g),vis); }
347 
348 } // namespace boost
349 
350 #endif // BOOST_GRAPH_CORE_NUMBERS_HPP
351 
352