← Back to branch summary

~dgleich/matlab-bgl/master

« back to all changes in this revision

Viewing changes to libmbgl/yasmic/boost_mod/core_numbers.hpp

  • Committer: David Gleich
  • Date: 2008-09-29 22:06:39 UTC
  • mfrom: (1.1.19 work)
  • Revision ID: dgleich@stanford.edu-20080929220639-4ic8mxd20lu81dla
Incorporated misc. fixes and graph layout algorithms.

Show diffs side-by-side

added added

removed removed

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