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