]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 { | |
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(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(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 |