File: core_numbers.hpp

package info (click to toggle)
boost1.62 1.62.0+dfsg-4
  • links: PTS, VCS
  • area: main
  • in suites: stretch
  • size: 686,420 kB
  • sloc: cpp: 2,609,004; xml: 972,558; ansic: 53,674; python: 32,437; sh: 8,829; asm: 3,071; cs: 2,121; makefile: 964; perl: 859; yacc: 472; php: 132; ruby: 94; f90: 55; sql: 13; csh: 6
file content (351 lines) | stat: -rw-r--r-- 14,232 bytes parent folder | download | duplicates (13)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
//
//=======================================================================
// Copyright 2007 Stanford University
// Authors: David Gleich
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
//
#ifndef BOOST_GRAPH_CORE_NUMBERS_HPP
#define BOOST_GRAPH_CORE_NUMBERS_HPP

#include <boost/graph/detail/d_ary_heap.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/iterator/reverse_iterator.hpp>
#include <boost/concept/assert.hpp>

/*
 * core_numbers
 *
 * Requirement: IncidenceGraph
 */

// History
//
// 30 July 2007
// Added visitors to the implementation
//
// 8 February 2008
// Fixed headers and missing typename

namespace boost {

    // A linear time O(m) algorithm to compute the indegree core number
    // of a graph for unweighted graphs.
    //
    // and a O((n+m) log n) algorithm to compute the in-edge-weight core
    // numbers of a weighted graph.
    //
    // The linear algorithm comes from:
    // Vladimir Batagelj and Matjaz Zaversnik, "An O(m) Algorithm for Cores
    // Decomposition of Networks."  Sept. 1 2002.

    template <typename Visitor, typename Graph>
    struct CoreNumbersVisitorConcept {
        void constraints()
        {
            BOOST_CONCEPT_ASSERT(( CopyConstructibleConcept<Visitor> ));
            vis.examine_vertex(u,g);
            vis.finish_vertex(u,g);
            vis.examine_edge(e,g);
        }
        Visitor vis;
        Graph g;
        typename graph_traits<Graph>::vertex_descriptor u;
        typename graph_traits<Graph>::edge_descriptor e;
    };

    template <class Visitors = null_visitor>
    class core_numbers_visitor : public bfs_visitor<Visitors> {
        public:
        core_numbers_visitor() {}
        core_numbers_visitor(Visitors vis)
            : bfs_visitor<Visitors>(vis) {}

        private:
        template <class Vertex, class Graph>
        void initialize_vertex(Vertex, Graph&) {}

        template <class Vertex, class Graph>
        void discover_vertex(Vertex , Graph&) {}

        template <class Vertex, class Graph>
        void gray_target(Vertex, Graph&) {}

        template <class Vertex, class Graph>
        void black_target(Vertex, Graph&) {}

        template <class Edge, class Graph>
        void tree_edge(Edge, Graph&) {}

        template <class Edge, class Graph>
        void non_tree_edge(Edge, Graph&) {}
    };

    template <class Visitors>
    core_numbers_visitor<Visitors> make_core_numbers_visitor(Visitors vis)
    { return core_numbers_visitor<Visitors>(vis); }

    typedef core_numbers_visitor<> default_core_numbers_visitor;

    namespace detail {

        // implement a constant_property_map to simplify compute_in_degree
        // for the weighted and unweighted case
        // this is based on dummy property map
        template <typename ValueType>
        class constant_value_property_map
          : public boost::put_get_helper<ValueType,
              constant_value_property_map<ValueType>  >
        {
        public:
            typedef void key_type;
            typedef ValueType value_type;
            typedef const ValueType& reference;
            typedef boost::readable_property_map_tag category;
            inline constant_value_property_map(ValueType cc) : c(cc) { }
            inline constant_value_property_map(const constant_value_property_map<ValueType>& x)
              : c(x.c) { }
            template <class Vertex>
            inline reference operator[](Vertex) const { return c; }
        protected:
            ValueType c;
        };


        // the core numbers start as the indegree or inweight.  This function
        // will initialize these values
        template <typename Graph, typename CoreMap, typename EdgeWeightMap>
        void compute_in_degree_map(Graph& g, CoreMap d, EdgeWeightMap wm)
        {
            typename graph_traits<Graph>::vertex_iterator vi,vi_end;
            typename graph_traits<Graph>::out_edge_iterator ei,ei_end;
            for (boost::tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
                put(d,*vi,0);
            }
            for (boost::tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
                for (boost::tie(ei,ei_end) = out_edges(*vi,g); ei!=ei_end; ++ei) {
                    put(d,target(*ei,g),get(d,target(*ei,g))+get(wm,*ei));
                }
            }
        }

        // the version for weighted graphs is a little different
        template <typename Graph, typename CoreMap,
            typename EdgeWeightMap, typename MutableQueue,
            typename Visitor>
        typename property_traits<CoreMap>::value_type
        core_numbers_impl(Graph& g, CoreMap c, EdgeWeightMap wm,
            MutableQueue& Q, Visitor vis)
        {
            typename property_traits<CoreMap>::value_type v_cn = 0;
            typedef typename graph_traits<Graph>::vertex_descriptor vertex;
            while (!Q.empty())
            {
                // remove v from the Q, and then decrease the core numbers
                // of its successors
                vertex v = Q.top();
                vis.examine_vertex(v,g);
                Q.pop();
                v_cn = get(c,v);
                typename graph_traits<Graph>::out_edge_iterator oi,oi_end;
                for (boost::tie(oi,oi_end) = out_edges(v,g); oi!=oi_end; ++oi) {
                    vis.examine_edge(*oi,g);
                    vertex u = target(*oi,g);
                    // if c[u] > c[v], then u is still in the graph,
                    if (get(c,u) > v_cn) {
                        // remove the edge
                        put(c,u,get(c,u)-get(wm,*oi));
                        if (Q.contains(u))
                          Q.update(u);
                    }
                }
                vis.finish_vertex(v,g);
            }
            return (v_cn);
        }

        template <typename Graph, typename CoreMap, typename EdgeWeightMap,
            typename IndexMap, typename CoreNumVisitor>
        typename property_traits<CoreMap>::value_type
        core_numbers_dispatch(Graph&g, CoreMap c, EdgeWeightMap wm,
            IndexMap im, CoreNumVisitor vis)
        {
            typedef typename property_traits<CoreMap>::value_type D;
            typedef std::less<D> Cmp;
            // build the mutable queue
            typedef typename graph_traits<Graph>::vertex_descriptor vertex;
            std::vector<std::size_t> index_in_heap_data(num_vertices(g));
            typedef iterator_property_map<std::vector<std::size_t>::iterator, IndexMap>
              index_in_heap_map_type;
            index_in_heap_map_type index_in_heap_map(index_in_heap_data.begin(), im);
            typedef d_ary_heap_indirect<vertex, 4, index_in_heap_map_type, CoreMap, Cmp> MutableQueue;
            MutableQueue Q(c, index_in_heap_map, Cmp());
            typename graph_traits<Graph>::vertex_iterator vi,vi_end;
            for (boost::tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
                Q.push(*vi);
            }
            return core_numbers_impl(g, c, wm, Q, vis);
        }

        // the version for the unweighted case
        // for this functions CoreMap must be initialized
        // with the in degree of each vertex
        template <typename Graph, typename CoreMap, typename PositionMap,
            typename Visitor>
        typename property_traits<CoreMap>::value_type
        core_numbers_impl(Graph& g, CoreMap c, PositionMap pos, Visitor vis)
        {
            typedef typename graph_traits<Graph>::vertices_size_type size_type;
            typedef typename graph_traits<Graph>::degree_size_type degree_type;
            typedef typename graph_traits<Graph>::vertex_descriptor vertex;
            typename graph_traits<Graph>::vertex_iterator vi,vi_end;

            // store the vertex core numbers
            typename property_traits<CoreMap>::value_type v_cn = 0;

            // compute the maximum degree (degrees are in the coremap)
            typename graph_traits<Graph>::degree_size_type max_deg = 0;
            for (boost::tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
                max_deg = (std::max<typename graph_traits<Graph>::degree_size_type>)(max_deg, get(c,*vi));
            }

            // store the vertices in bins by their degree
            // allocate two extra locations to ease boundary cases
            std::vector<size_type> bin(max_deg+2);
            for (boost::tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
                ++bin[get(c,*vi)];
            }

            // this loop sets bin[d] to the starting position of vertices
            // with degree d in the vert array for the bucket sort
            size_type cur_pos = 0;
            for (degree_type cur_deg = 0; cur_deg < max_deg+2; ++cur_deg) {
                degree_type tmp = bin[cur_deg];
                bin[cur_deg] = cur_pos;
                cur_pos += tmp;
            }

            // perform the bucket sort with pos and vert so that
            // pos[0] is the vertex of smallest degree
            std::vector<vertex> vert(num_vertices(g));
            for (boost::tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
                vertex v=*vi;
                size_type p=bin[get(c,v)];
                put(pos,v,p);
                vert[p]=v;
                ++bin[get(c,v)];
            }
            // we ``abused'' bin while placing the vertices, now,
            // we need to restore it
            std::copy(boost::make_reverse_iterator(bin.end()-2),
                boost::make_reverse_iterator(bin.begin()),
                boost::make_reverse_iterator(bin.end()-1));
            // now simulate removing the vertices
            for (size_type i=0; i < num_vertices(g); ++i) {
                vertex v = vert[i];
                vis.examine_vertex(v,g);
                v_cn = get(c,v);
                typename graph_traits<Graph>::out_edge_iterator oi,oi_end;
                for (boost::tie(oi,oi_end) = out_edges(v,g); oi!=oi_end; ++oi) {
                    vis.examine_edge(*oi,g);
                    vertex u = target(*oi,g);
                    // if c[u] > c[v], then u is still in the graph,
                    if (get(c,u) > v_cn) {
                        degree_type deg_u = get(c,u);
                        degree_type pos_u = get(pos,u);
                        // w is the first vertex with the same degree as u
                        // (this is the resort operation!)
                        degree_type pos_w = bin[deg_u];
                        vertex w = vert[pos_w];
                        if (u!=v) {
                            // swap u and w
                            put(pos,u,pos_w);
                            put(pos,w,pos_u);
                            vert[pos_w] = u;
                            vert[pos_u] = w;
                        }
                        // now, the vertices array is sorted assuming
                        // we perform the following step
                        // start the set of vertices with degree of u
                        // one into the future (this now points at vertex
                        // w which we swapped with u).
                        ++bin[deg_u];
                        // we are removing v from the graph, so u's degree
                        // decreases
                        put(c,u,get(c,u)-1);
                    }
                }
                vis.finish_vertex(v,g);
            }
            return v_cn;
        }

    } // namespace detail

    // non-named parameter version for the unweighted case
    template <typename Graph, typename CoreMap, typename CoreNumVisitor>
    typename property_traits<CoreMap>::value_type
    core_numbers(Graph& g, CoreMap c, CoreNumVisitor vis)
    {
        typedef typename graph_traits<Graph>::vertices_size_type size_type;
        detail::compute_in_degree_map(g,c,
            detail::constant_value_property_map<
                typename property_traits<CoreMap>::value_type>(1) );
        return detail::core_numbers_impl(g,c,
            make_iterator_property_map(
                std::vector<size_type>(num_vertices(g)).begin(),get(vertex_index, g)),
            vis
        );
    }

    // non-named paramter version for the unweighted case
    template <typename Graph, typename CoreMap>
    typename property_traits<CoreMap>::value_type
    core_numbers(Graph& g, CoreMap c)
    {
        return core_numbers(g, c, make_core_numbers_visitor(null_visitor()));
    }

    // non-named parameter version for the weighted case
    template <typename Graph, typename CoreMap, typename EdgeWeightMap,
        typename VertexIndexMap, typename CoreNumVisitor>
    typename property_traits<CoreMap>::value_type
    core_numbers(Graph& g, CoreMap c, EdgeWeightMap wm, VertexIndexMap vim,
        CoreNumVisitor vis)
    {
        detail::compute_in_degree_map(g,c,wm);
        return detail::core_numbers_dispatch(g,c,wm,vim,vis);
    }

    // non-named parameter version for the weighted case
//    template <typename Graph, typename CoreMap, typename EdgeWeightMap>
//    typename property_traits<CoreMap>::value_type
//    core_numbers(Graph& g, CoreMap c, EdgeWeightMap wm)
//    {
//        typedef typename graph_traits<Graph>::vertices_size_type size_type;
//        detail::compute_in_degree_map(g,c,wm);
//        return detail::core_numbers_dispatch(g,c,wm,get(vertex_index,g),
//            make_core_numbers_visitor(null_visitor()));
//    }

    template <typename Graph, typename CoreMap>
    typename property_traits<CoreMap>::value_type
    weighted_core_numbers(Graph& g, CoreMap c)
    {
        return weighted_core_numbers(
            g,c, make_core_numbers_visitor(null_visitor())
        );
    }

    template <typename Graph, typename CoreMap, typename CoreNumVisitor>
    typename property_traits<CoreMap>::value_type
    weighted_core_numbers(Graph& g, CoreMap c, CoreNumVisitor vis)
    { return core_numbers(g,c,get(edge_weight,g),get(vertex_index,g),vis); }

} // namespace boost

#endif // BOOST_GRAPH_CORE_NUMBERS_HPP