← Back to branch summary

~ubuntu-branches/ubuntu/precise/deal.ii/precise

« back to all changes in this revision

Viewing changes to contrib/boost/include/boost/graph/betweenness_centrality.hpp

  • Committer: Bazaar Package Importer
  • Author(s): Adam C. Powell, IV
  • Date: 2009-05-08 23:13:50 UTC
  • Revision ID: james.westby@ubuntu.com-20090508231350-rrh1ltgi0tifabwc
Tags: upstream-6.2.0
Import upstream version 6.2.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
contrib/boost/include/boost/graph/betweenness_centrality.hpp
 
1
// Copyright 2004 The Trustees of Indiana University.
 
2
 
 
3
// Distributed under the Boost Software License, Version 1.0.
 
4
// (See accompanying file LICENSE_1_0.txt or copy at
 
5
// http://www.boost.org/LICENSE_1_0.txt)
 
6
 
 
7
//  Authors: Douglas Gregor
 
8
//           Andrew Lumsdaine
 
9
#ifndef BOOST_GRAPH_BRANDES_BETWEENNESS_CENTRALITY_HPP
 
10
#define BOOST_GRAPH_BRANDES_BETWEENNESS_CENTRALITY_HPP
 
11
 
 
12
#include <stack>
 
13
#include <vector>
 
14
#include <boost/graph/dijkstra_shortest_paths.hpp>
 
15
#include <boost/graph/breadth_first_search.hpp>
 
16
#include <boost/graph/relax.hpp>
 
17
#include <boost/graph/graph_traits.hpp>
 
18
#include <boost/tuple/tuple.hpp>
 
19
#include <boost/type_traits/is_convertible.hpp>
 
20
#include <boost/type_traits/is_same.hpp>
 
21
#include <boost/mpl/if.hpp>
 
22
#include <boost/property_map.hpp>
 
23
#include <boost/graph/named_function_params.hpp>
 
24
#include <algorithm>
 
25
 
 
26
namespace boost {
 
27
 
 
28
namespace detail { namespace graph {
 
29
 
 
30
  /**
 
31
   * Customized visitor passed to Dijkstra's algorithm by Brandes'
 
32
   * betweenness centrality algorithm. This visitor is responsible for
 
33
   * keeping track of the order in which vertices are discovered, the
 
34
   * predecessors on the shortest path(s) to a vertex, and the number
 
35
   * of shortest paths.
 
36
   */
 
37
  template<typename Graph, typename WeightMap, typename IncomingMap,
 
38
           typename DistanceMap, typename PathCountMap>
 
39
  struct brandes_dijkstra_visitor : public bfs_visitor<>
 
40
  {
 
41
    typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
 
42
    typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
 
43
 
 
44
    brandes_dijkstra_visitor(std::stack<vertex_descriptor>& ordered_vertices,
 
45
                             WeightMap weight,
 
46
                             IncomingMap incoming,
 
47
                             DistanceMap distance,
 
48
                             PathCountMap path_count)
 
49
      : ordered_vertices(ordered_vertices), weight(weight), 
 
50
        incoming(incoming), distance(distance),
 
51
        path_count(path_count)
 
52
    { }
 
53
 
 
54
    /**
 
55
     * Whenever an edge e = (v, w) is relaxed, the incoming edge list
 
56
     * for w is set to {(v, w)} and the shortest path count of w is set to
 
57
     * the number of paths that reach {v}.
 
58
     */
 
59
    void edge_relaxed(edge_descriptor e, const Graph& g) 
 
60
    { 
 
61
      vertex_descriptor v = source(e, g), w = target(e, g);
 
62
      incoming[w].clear();
 
63
      incoming[w].push_back(e);
 
64
      put(path_count, w, get(path_count, v));
 
65
    }
 
66
 
 
67
    /**
 
68
     * If an edge e = (v, w) was not relaxed, it may still be the case
 
69
     * that we've found more equally-short paths, so include {(v, w)} in the
 
70
     * incoming edges of w and add all of the shortest paths to v to the
 
71
     * shortest path count of w.
 
72
     */
 
73
    void edge_not_relaxed(edge_descriptor e, const Graph& g) 
 
74
    {
 
75
      typedef typename property_traits<WeightMap>::value_type weight_type;
 
76
      typedef typename property_traits<DistanceMap>::value_type distance_type;
 
77
      vertex_descriptor v = source(e, g), w = target(e, g);
 
78
      distance_type d_v = get(distance, v), d_w = get(distance, w);
 
79
      weight_type w_e = get(weight, e);
 
80
 
 
81
      closed_plus<distance_type> combine;
 
82
      if (d_w == combine(d_v, w_e)) {
 
83
        put(path_count, w, get(path_count, w) + get(path_count, v));
 
84
        incoming[w].push_back(e);
 
85
      }
 
86
    }
 
87
 
 
88
    /// Keep track of vertices as they are reached
 
89
    void examine_vertex(vertex_descriptor w, const Graph&) 
 
90
    { 
 
91
      ordered_vertices.push(w);
 
92
    }
 
93
 
 
94
  private:
 
95
    std::stack<vertex_descriptor>& ordered_vertices;
 
96
    WeightMap weight;
 
97
    IncomingMap incoming;
 
98
    DistanceMap distance;
 
99
    PathCountMap path_count;
 
100
  };
 
101
 
 
102
  /**
 
103
   * Function object that calls Dijkstra's shortest paths algorithm
 
104
   * using the Dijkstra visitor for the Brandes betweenness centrality
 
105
   * algorithm.
 
106
   */
 
107
  template<typename WeightMap>
 
108
  struct brandes_dijkstra_shortest_paths
 
109
  {
 
110
    brandes_dijkstra_shortest_paths(WeightMap weight_map) 
 
111
      : weight_map(weight_map) { }
 
112
 
 
113
    template<typename Graph, typename IncomingMap, typename DistanceMap, 
 
114
             typename PathCountMap, typename VertexIndexMap>
 
115
    void 
 
116
    operator()(Graph& g, 
 
117
               typename graph_traits<Graph>::vertex_descriptor s,
 
118
               std::stack<typename graph_traits<Graph>::vertex_descriptor>& ov,
 
119
               IncomingMap incoming,
 
120
               DistanceMap distance,
 
121
               PathCountMap path_count,
 
122
               VertexIndexMap vertex_index)
 
123
    {
 
124
      typedef brandes_dijkstra_visitor<Graph, WeightMap, IncomingMap, 
 
125
                                       DistanceMap, PathCountMap> visitor_type;
 
126
      visitor_type visitor(ov, weight_map, incoming, distance, path_count);
 
127
 
 
128
      dijkstra_shortest_paths(g, s, 
 
129
                              boost::weight_map(weight_map)
 
130
                              .vertex_index_map(vertex_index)
 
131
                              .distance_map(distance)
 
132
                              .visitor(visitor));
 
133
    }
 
134
 
 
135
  private:
 
136
    WeightMap weight_map;
 
137
  };
 
138
 
 
139
  /**
 
140
   * Function object that invokes breadth-first search for the
 
141
   * unweighted form of the Brandes betweenness centrality algorithm.
 
142
   */
 
143
  struct brandes_unweighted_shortest_paths
 
144
  {
 
145
    /**
 
146
     * Customized visitor passed to breadth-first search, which
 
147
     * records predecessor and the number of shortest paths to each
 
148
     * vertex.
 
149
     */
 
150
    template<typename Graph, typename IncomingMap, typename DistanceMap, 
 
151
             typename PathCountMap>
 
152
    struct visitor_type : public bfs_visitor<>
 
153
    {
 
154
      typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
 
155
      typedef typename graph_traits<Graph>::vertex_descriptor 
 
156
        vertex_descriptor;
 
157
      
 
158
      visitor_type(IncomingMap incoming, DistanceMap distance, 
 
159
                   PathCountMap path_count, 
 
160
                   std::stack<vertex_descriptor>& ordered_vertices)
 
161
        : incoming(incoming), distance(distance), 
 
162
          path_count(path_count), ordered_vertices(ordered_vertices) { }
 
163
 
 
164
      /// Keep track of vertices as they are reached
 
165
      void examine_vertex(vertex_descriptor v, Graph&)
 
166
      {
 
167
        ordered_vertices.push(v);
 
168
      }
 
169
 
 
170
      /**
 
171
       * Whenever an edge e = (v, w) is labelled a tree edge, the
 
172
       * incoming edge list for w is set to {(v, w)} and the shortest
 
173
       * path count of w is set to the number of paths that reach {v}.
 
174
       */
 
175
      void tree_edge(edge_descriptor e, Graph& g)
 
176
      {
 
177
        vertex_descriptor v = source(e, g);
 
178
        vertex_descriptor w = target(e, g);
 
179
        put(distance, w, get(distance, v) + 1);
 
180
        
 
181
        put(path_count, w, get(path_count, v));
 
182
        incoming[w].push_back(e);
 
183
      }
 
184
 
 
185
      /**
 
186
       * If an edge e = (v, w) is not a tree edge, it may still be the
 
187
       * case that we've found more equally-short paths, so include (v, w)
 
188
       * in the incoming edge list of w and add all of the shortest
 
189
       * paths to v to the shortest path count of w.
 
190
       */
 
191
      void non_tree_edge(edge_descriptor e, Graph& g)
 
192
      {
 
193
        vertex_descriptor v = source(e, g);
 
194
        vertex_descriptor w = target(e, g);
 
195
        if (get(distance, w) == get(distance, v) + 1) {
 
196
          put(path_count, w, get(path_count, w) + get(path_count, v));
 
197
          incoming[w].push_back(e);
 
198
        }
 
199
      }
 
200
 
 
201
    private:
 
202
      IncomingMap incoming;
 
203
      DistanceMap distance;
 
204
      PathCountMap path_count;
 
205
      std::stack<vertex_descriptor>& ordered_vertices;
 
206
    };
 
207
 
 
208
    template<typename Graph, typename IncomingMap, typename DistanceMap, 
 
209
             typename PathCountMap, typename VertexIndexMap>
 
210
    void 
 
211
    operator()(Graph& g, 
 
212
               typename graph_traits<Graph>::vertex_descriptor s,
 
213
               std::stack<typename graph_traits<Graph>::vertex_descriptor>& ov,
 
214
               IncomingMap incoming,
 
215
               DistanceMap distance,
 
216
               PathCountMap path_count,
 
217
               VertexIndexMap vertex_index)
 
218
    {
 
219
      typedef typename graph_traits<Graph>::vertex_descriptor
 
220
        vertex_descriptor;
 
221
 
 
222
      visitor_type<Graph, IncomingMap, DistanceMap, PathCountMap>
 
223
        visitor(incoming, distance, path_count, ov);
 
224
      
 
225
      std::vector<default_color_type> 
 
226
        colors(num_vertices(g), color_traits<default_color_type>::white());
 
227
      boost::queue<vertex_descriptor> Q;
 
228
      breadth_first_visit(g, s, Q, visitor, 
 
229
                          make_iterator_property_map(colors.begin(), 
 
230
                                                     vertex_index));
 
231
    }
 
232
  };
 
233
 
 
234
  // When the edge centrality map is a dummy property map, no
 
235
  // initialization is needed.
 
236
  template<typename Iter>
 
237
  inline void 
 
238
  init_centrality_map(std::pair<Iter, Iter>, dummy_property_map) { }
 
239
 
 
240
  // When we have a real edge centrality map, initialize all of the
 
241
  // centralities to zero.
 
242
  template<typename Iter, typename Centrality>
 
243
  void 
 
244
  init_centrality_map(std::pair<Iter, Iter> keys, Centrality centrality_map)
 
245
  {
 
246
    typedef typename property_traits<Centrality>::value_type 
 
247
      centrality_type;
 
248
    while (keys.first != keys.second) {
 
249
      put(centrality_map, *keys.first, centrality_type(0));
 
250
      ++keys.first;
 
251
    }
 
252
  }
 
253
 
 
254
  // When the edge centrality map is a dummy property map, no update
 
255
  // is performed.
 
256
  template<typename Key, typename T>
 
257
  inline void 
 
258
  update_centrality(dummy_property_map, const Key&, const T&) { }
 
259
 
 
260
  // When we have a real edge centrality map, add the value to the map
 
261
  template<typename CentralityMap, typename Key, typename T>
 
262
  inline void 
 
263
  update_centrality(CentralityMap centrality_map, Key k, const T& x)
 
264
  { put(centrality_map, k, get(centrality_map, k) + x); }
 
265
 
 
266
  template<typename Iter>
 
267
  inline void 
 
268
  divide_centrality_by_two(std::pair<Iter, Iter>, dummy_property_map) {}
 
269
 
 
270
  template<typename Iter, typename CentralityMap>
 
271
  inline void
 
272
  divide_centrality_by_two(std::pair<Iter, Iter> keys, 
 
273
                           CentralityMap centrality_map)
 
274
  {
 
275
    typename property_traits<CentralityMap>::value_type two(2);
 
276
    while (keys.first != keys.second) {
 
277
      put(centrality_map, *keys.first, get(centrality_map, *keys.first) / two);
 
278
      ++keys.first;
 
279
    }
 
280
  }
 
281
 
 
282
  template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
 
283
           typename IncomingMap, typename DistanceMap, 
 
284
           typename DependencyMap, typename PathCountMap,
 
285
           typename VertexIndexMap, typename ShortestPaths>
 
286
  void 
 
287
  brandes_betweenness_centrality_impl(const Graph& g, 
 
288
                                      CentralityMap centrality,     // C_B
 
289
                                      EdgeCentralityMap edge_centrality_map,
 
290
                                      IncomingMap incoming, // P
 
291
                                      DistanceMap distance,         // d
 
292
                                      DependencyMap dependency,     // delta
 
293
                                      PathCountMap path_count,      // sigma
 
294
                                      VertexIndexMap vertex_index,
 
295
                                      ShortestPaths shortest_paths)
 
296
  {
 
297
    typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
 
298
    typedef typename graph_traits<Graph>::edge_iterator edge_iterator;
 
299
    typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
 
300
 
 
301
    // Initialize centrality
 
302
    init_centrality_map(vertices(g), centrality);
 
303
    init_centrality_map(edges(g), edge_centrality_map);
 
304
 
 
305
    std::stack<vertex_descriptor> ordered_vertices;
 
306
    vertex_iterator s, s_end;
 
307
    for (tie(s, s_end) = vertices(g); s != s_end; ++s) {
 
308
      // Initialize for this iteration
 
309
      vertex_iterator w, w_end;
 
310
      for (tie(w, w_end) = vertices(g); w != w_end; ++w) {
 
311
        incoming[*w].clear();
 
312
        put(path_count, *w, 0);
 
313
        put(dependency, *w, 0);
 
314
      }
 
315
      put(path_count, *s, 1);
 
316
      
 
317
      // Execute the shortest paths algorithm. This will be either
 
318
      // Dijkstra's algorithm or a customized breadth-first search,
 
319
      // depending on whether the graph is weighted or unweighted.
 
320
      shortest_paths(g, *s, ordered_vertices, incoming, distance,
 
321
                     path_count, vertex_index);
 
322
      
 
323
      while (!ordered_vertices.empty()) {
 
324
        vertex_descriptor w = ordered_vertices.top();
 
325
        ordered_vertices.pop();
 
326
        
 
327
        typedef typename property_traits<IncomingMap>::value_type
 
328
          incoming_type;
 
329
        typedef typename incoming_type::iterator incoming_iterator;
 
330
        typedef typename property_traits<DependencyMap>::value_type 
 
331
          dependency_type;
 
332
        
 
333
        for (incoming_iterator vw = incoming[w].begin();
 
334
             vw != incoming[w].end(); ++vw) {
 
335
          vertex_descriptor v = source(*vw, g);
 
336
          dependency_type factor = dependency_type(get(path_count, v))
 
337
            / dependency_type(get(path_count, w));
 
338
          factor *= (dependency_type(1) + get(dependency, w));
 
339
          put(dependency, v, get(dependency, v) + factor);
 
340
          update_centrality(edge_centrality_map, *vw, factor);
 
341
        }
 
342
        
 
343
        if (w != *s) {
 
344
          update_centrality(centrality, w, get(dependency, w));
 
345
        }
 
346
      }
 
347
    }
 
348
 
 
349
    typedef typename graph_traits<Graph>::directed_category directed_category;
 
350
    const bool is_undirected = 
 
351
      is_convertible<directed_category*, undirected_tag*>::value;
 
352
    if (is_undirected) {
 
353
      divide_centrality_by_two(vertices(g), centrality);
 
354
      divide_centrality_by_two(edges(g), edge_centrality_map);
 
355
    }
 
356
  }
 
357
 
 
358
} } // end namespace detail::graph
 
359
 
 
360
template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
 
361
         typename IncomingMap, typename DistanceMap, 
 
362
         typename DependencyMap, typename PathCountMap, 
 
363
         typename VertexIndexMap>
 
364
void 
 
365
brandes_betweenness_centrality(const Graph& g, 
 
366
                               CentralityMap centrality,     // C_B
 
367
                               EdgeCentralityMap edge_centrality_map,
 
368
                               IncomingMap incoming, // P
 
369
                               DistanceMap distance,         // d
 
370
                               DependencyMap dependency,     // delta
 
371
                               PathCountMap path_count,      // sigma
 
372
                               VertexIndexMap vertex_index)
 
373
{
 
374
  detail::graph::brandes_unweighted_shortest_paths shortest_paths;
 
375
 
 
376
  detail::graph::brandes_betweenness_centrality_impl(g, centrality, 
 
377
                                                     edge_centrality_map,
 
378
                                                     incoming, distance,
 
379
                                                     dependency, path_count,
 
380
                                                     vertex_index, 
 
381
                                                     shortest_paths);
 
382
}
 
383
 
 
384
template<typename Graph, typename CentralityMap, typename EdgeCentralityMap, 
 
385
         typename IncomingMap, typename DistanceMap, 
 
386
         typename DependencyMap, typename PathCountMap, 
 
387
         typename VertexIndexMap, typename WeightMap>    
 
388
void 
 
389
brandes_betweenness_centrality(const Graph& g, 
 
390
                               CentralityMap centrality,     // C_B
 
391
                               EdgeCentralityMap edge_centrality_map,
 
392
                               IncomingMap incoming, // P
 
393
                               DistanceMap distance,         // d
 
394
                               DependencyMap dependency,     // delta
 
395
                               PathCountMap path_count,      // sigma
 
396
                               VertexIndexMap vertex_index,
 
397
                               WeightMap weight_map)
 
398
{
 
399
  detail::graph::brandes_dijkstra_shortest_paths<WeightMap>
 
400
    shortest_paths(weight_map);
 
401
 
 
402
  detail::graph::brandes_betweenness_centrality_impl(g, centrality, 
 
403
                                                     edge_centrality_map,
 
404
                                                     incoming, distance,
 
405
                                                     dependency, path_count,
 
406
                                                     vertex_index, 
 
407
                                                     shortest_paths);
 
408
}
 
409
 
 
410
namespace detail { namespace graph {
 
411
  template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
 
412
           typename WeightMap, typename VertexIndexMap>
 
413
  void 
 
414
  brandes_betweenness_centrality_dispatch2(const Graph& g,
 
415
                                           CentralityMap centrality,
 
416
                                           EdgeCentralityMap edge_centrality_map,
 
417
                                           WeightMap weight_map,
 
418
                                           VertexIndexMap vertex_index)
 
419
  {
 
420
    typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
 
421
    typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
 
422
    typedef typename mpl::if_c<(is_same<CentralityMap, 
 
423
                                        dummy_property_map>::value),
 
424
                                         EdgeCentralityMap, 
 
425
                               CentralityMap>::type a_centrality_map;
 
426
    typedef typename property_traits<a_centrality_map>::value_type 
 
427
      centrality_type;
 
428
 
 
429
    typename graph_traits<Graph>::vertices_size_type V = num_vertices(g);
 
430
    
 
431
    std::vector<std::vector<edge_descriptor> > incoming(V);
 
432
    std::vector<centrality_type> distance(V);
 
433
    std::vector<centrality_type> dependency(V);
 
434
    std::vector<unsigned long long> path_count(V);
 
435
 
 
436
    brandes_betweenness_centrality(
 
437
      g, centrality, edge_centrality_map,
 
438
      make_iterator_property_map(incoming.begin(), vertex_index),
 
439
      make_iterator_property_map(distance.begin(), vertex_index),
 
440
      make_iterator_property_map(dependency.begin(), vertex_index),
 
441
      make_iterator_property_map(path_count.begin(), vertex_index),
 
442
      vertex_index,
 
443
      weight_map);
 
444
  }
 
445
  
 
446
 
 
447
  template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
 
448
           typename VertexIndexMap>
 
449
  void 
 
450
  brandes_betweenness_centrality_dispatch2(const Graph& g,
 
451
                                           CentralityMap centrality,
 
452
                                           EdgeCentralityMap edge_centrality_map,
 
453
                                           VertexIndexMap vertex_index)
 
454
  {
 
455
    typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
 
456
    typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
 
457
    typedef typename mpl::if_c<(is_same<CentralityMap, 
 
458
                                        dummy_property_map>::value),
 
459
                                         EdgeCentralityMap, 
 
460
                               CentralityMap>::type a_centrality_map;
 
461
    typedef typename property_traits<a_centrality_map>::value_type 
 
462
      centrality_type;
 
463
 
 
464
    typename graph_traits<Graph>::vertices_size_type V = num_vertices(g);
 
465
    
 
466
    std::vector<std::vector<edge_descriptor> > incoming(V);
 
467
    std::vector<centrality_type> distance(V);
 
468
    std::vector<centrality_type> dependency(V);
 
469
    std::vector<unsigned long long> path_count(V);
 
470
 
 
471
    brandes_betweenness_centrality(
 
472
      g, centrality, edge_centrality_map,
 
473
      make_iterator_property_map(incoming.begin(), vertex_index),
 
474
      make_iterator_property_map(distance.begin(), vertex_index),
 
475
      make_iterator_property_map(dependency.begin(), vertex_index),
 
476
      make_iterator_property_map(path_count.begin(), vertex_index),
 
477
      vertex_index);
 
478
  }
 
479
 
 
480
  template<typename WeightMap>
 
481
  struct brandes_betweenness_centrality_dispatch1
 
482
  {
 
483
    template<typename Graph, typename CentralityMap, 
 
484
             typename EdgeCentralityMap, typename VertexIndexMap>
 
485
    static void 
 
486
    run(const Graph& g, CentralityMap centrality, 
 
487
        EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index,
 
488
        WeightMap weight_map)
 
489
    {
 
490
      brandes_betweenness_centrality_dispatch2(g, centrality, edge_centrality_map,
 
491
                                               weight_map, vertex_index);
 
492
    }
 
493
  };
 
494
 
 
495
  template<>
 
496
  struct brandes_betweenness_centrality_dispatch1<error_property_not_found>
 
497
  {
 
498
    template<typename Graph, typename CentralityMap, 
 
499
             typename EdgeCentralityMap, typename VertexIndexMap>
 
500
    static void 
 
501
    run(const Graph& g, CentralityMap centrality, 
 
502
        EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index,
 
503
        error_property_not_found)
 
504
    {
 
505
      brandes_betweenness_centrality_dispatch2(g, centrality, edge_centrality_map,
 
506
                                               vertex_index);
 
507
    }
 
508
  };
 
509
 
 
510
} } // end namespace detail::graph
 
511
 
 
512
template<typename Graph, typename Param, typename Tag, typename Rest>
 
513
void 
 
514
brandes_betweenness_centrality(const Graph& g, 
 
515
                               const bgl_named_params<Param,Tag,Rest>& params)
 
516
{
 
517
  typedef bgl_named_params<Param,Tag,Rest> named_params;
 
518
 
 
519
  typedef typename property_value<named_params, edge_weight_t>::type ew;
 
520
  detail::graph::brandes_betweenness_centrality_dispatch1<ew>::run(
 
521
    g, 
 
522
    choose_param(get_param(params, vertex_centrality), 
 
523
                 dummy_property_map()),
 
524
    choose_param(get_param(params, edge_centrality), 
 
525
                 dummy_property_map()),
 
526
    choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
 
527
    get_param(params, edge_weight));
 
528
}
 
529
 
 
530
template<typename Graph, typename CentralityMap>
 
531
void 
 
532
brandes_betweenness_centrality(const Graph& g, CentralityMap centrality)
 
533
{
 
534
  detail::graph::brandes_betweenness_centrality_dispatch2(
 
535
    g, centrality, dummy_property_map(), get(vertex_index, g));
 
536
}
 
537
 
 
538
template<typename Graph, typename CentralityMap, typename EdgeCentralityMap>
 
539
void 
 
540
brandes_betweenness_centrality(const Graph& g, CentralityMap centrality,
 
541
                               EdgeCentralityMap edge_centrality_map)
 
542
{
 
543
  detail::graph::brandes_betweenness_centrality_dispatch2(
 
544
    g, centrality, edge_centrality_map, get(vertex_index, g));
 
545
}
 
546
 
 
547
/**
 
548
 * Converts "absolute" betweenness centrality (as computed by the
 
549
 * brandes_betweenness_centrality algorithm) in the centrality map
 
550
 * into "relative" centrality. The result is placed back into the
 
551
 * given centrality map.
 
552
 */
 
553
template<typename Graph, typename CentralityMap>
 
554
void 
 
555
relative_betweenness_centrality(const Graph& g, CentralityMap centrality)
 
556
{
 
557
  typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
 
558
  typedef typename property_traits<CentralityMap>::value_type centrality_type;
 
559
 
 
560
  typename graph_traits<Graph>::vertices_size_type n = num_vertices(g);
 
561
  centrality_type factor = centrality_type(2)/centrality_type(n*n - 3*n + 2);
 
562
  vertex_iterator v, v_end;
 
563
  for (tie(v, v_end) = vertices(g); v != v_end; ++v) {
 
564
    put(centrality, *v, factor * get(centrality, *v));
 
565
  }
 
566
}
 
567
 
 
568
// Compute the central point dominance of a graph.
 
569
template<typename Graph, typename CentralityMap>
 
570
typename property_traits<CentralityMap>::value_type
 
571
central_point_dominance(const Graph& g, CentralityMap centrality)
 
572
{
 
573
  using std::max;
 
574
 
 
575
  typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
 
576
  typedef typename property_traits<CentralityMap>::value_type centrality_type;
 
577
 
 
578
  typename graph_traits<Graph>::vertices_size_type n = num_vertices(g);
 
579
 
 
580
  // Find max centrality
 
581
  centrality_type max_centrality(0);
 
582
  vertex_iterator v, v_end;
 
583
  for (tie(v, v_end) = vertices(g); v != v_end; ++v) {
 
584
    max_centrality = (max)(max_centrality, get(centrality, *v));
 
585
  }
 
586
 
 
587
  // Compute central point dominance
 
588
  centrality_type sum(0);
 
589
  for (tie(v, v_end) = vertices(g); v != v_end; ++v) {
 
590
    sum += (max_centrality - get(centrality, *v));
 
591
  }
 
592
  return sum/(n-1);
 
593
}
 
594
 
 
595
} // end namespace boost
 
596
 
 
597
#endif // BOOST_GRAPH_BRANDES_BETWEENNESS_CENTRALITY_HPP