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
33namespace 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 {
47 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:
63 core_numbers_visitor() {}
64 core_numbers_visitor(Visitors vis)
65 : bfs_visitor<Visitors>(vis) {}
66
67 private:
68 template <class Vertex, class Graph>
69 void initialize_vertex(Vertex, Graph&) {}
70
71 template <class Vertex, class Graph>
72 void discover_vertex(Vertex , Graph&) {}
73
74 template <class Vertex, class Graph>
75 void gray_target(Vertex, Graph&) {}
76
77 template <class Vertex, class Graph>
78 void black_target(Vertex, Graph&) {}
79
80 template <class Edge, class Graph>
81 void tree_edge(Edge, Graph&) {}
82
83 template <class Edge, class Graph>
84 void non_tree_edge(Edge, Graph&) {}
85 };
86
87 template <class Visitors>
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;
108 inline constant_value_property_map(ValueType cc) : c(cc) { }
109 inline constant_value_property_map(const constant_value_property_map<ValueType>& x)
110 : c(x.c) { }
111 template <class Vertex>
112 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>
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
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
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
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
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
307 core_numbers(Graph& g, CoreMap c)
308 {
309 return core_numbers(g, c, make_core_numbers_visitor(vis: 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
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
336 weighted_core_numbers(Graph& g, CoreMap c)
337 {
338 return weighted_core_numbers(
339 g,c, make_core_numbers_visitor(vis: null_visitor())
340 );
341 }
342
343 template <typename Graph, typename CoreMap, typename CoreNumVisitor>
344 typename property_traits<CoreMap>::value_type
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

source code of boost/boost/graph/core_numbers.hpp