source: NonGTP/Boost/boost/graph/betweenness_centrality.hpp @ 857

Revision 857, 23.8 KB checked in by igarcia, 19 years ago (diff)
Line 
1// Copyright 2004 The Trustees of Indiana University.
2
3// Use, modification and distribution is subject to the Boost Software
4// License, Version 1.0. (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
26namespace boost {
27
28namespace 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
360template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
361         typename IncomingMap, typename DistanceMap,
362         typename DependencyMap, typename PathCountMap,
363         typename VertexIndexMap>
364void
365brandes_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
384template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
385         typename IncomingMap, typename DistanceMap,
386         typename DependencyMap, typename PathCountMap,
387         typename VertexIndexMap, typename WeightMap>   
388void
389brandes_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
410namespace 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>::degree_size_type degree_size_type;
421    typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
422    typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
423    typedef typename mpl::if_c<(is_same<CentralityMap,
424                                        dummy_property_map>::value),
425                                         EdgeCentralityMap,
426                               CentralityMap>::type a_centrality_map;
427    typedef typename property_traits<a_centrality_map>::value_type
428      centrality_type;
429
430    typename graph_traits<Graph>::vertices_size_type V = num_vertices(g);
431   
432    std::vector<std::vector<edge_descriptor> > incoming(V);
433    std::vector<centrality_type> distance(V);
434    std::vector<centrality_type> dependency(V);
435    std::vector<degree_size_type> path_count(V);
436
437    brandes_betweenness_centrality(
438      g, centrality, edge_centrality_map,
439      make_iterator_property_map(incoming.begin(), vertex_index),
440      make_iterator_property_map(distance.begin(), vertex_index),
441      make_iterator_property_map(dependency.begin(), vertex_index),
442      make_iterator_property_map(path_count.begin(), vertex_index),
443      vertex_index,
444      weight_map);
445  }
446 
447
448  template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
449           typename VertexIndexMap>
450  void
451  brandes_betweenness_centrality_dispatch2(const Graph& g,
452                                           CentralityMap centrality,
453                                           EdgeCentralityMap edge_centrality_map,
454                                           VertexIndexMap vertex_index)
455  {
456    typedef typename graph_traits<Graph>::degree_size_type degree_size_type;
457    typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
458    typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
459    typedef typename mpl::if_c<(is_same<CentralityMap,
460                                        dummy_property_map>::value),
461                                         EdgeCentralityMap,
462                               CentralityMap>::type a_centrality_map;
463    typedef typename property_traits<a_centrality_map>::value_type
464      centrality_type;
465
466    typename graph_traits<Graph>::vertices_size_type V = num_vertices(g);
467   
468    std::vector<std::vector<edge_descriptor> > incoming(V);
469    std::vector<centrality_type> distance(V);
470    std::vector<centrality_type> dependency(V);
471    std::vector<degree_size_type> path_count(V);
472
473    brandes_betweenness_centrality(
474      g, centrality, edge_centrality_map,
475      make_iterator_property_map(incoming.begin(), vertex_index),
476      make_iterator_property_map(distance.begin(), vertex_index),
477      make_iterator_property_map(dependency.begin(), vertex_index),
478      make_iterator_property_map(path_count.begin(), vertex_index),
479      vertex_index);
480  }
481
482  template<typename WeightMap>
483  struct brandes_betweenness_centrality_dispatch1
484  {
485    template<typename Graph, typename CentralityMap,
486             typename EdgeCentralityMap, typename VertexIndexMap>
487    static void
488    run(const Graph& g, CentralityMap centrality,
489        EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index,
490        WeightMap weight_map)
491    {
492      brandes_betweenness_centrality_dispatch2(g, centrality, edge_centrality_map,
493                                               weight_map, vertex_index);
494    }
495  };
496
497  template<>
498  struct brandes_betweenness_centrality_dispatch1<error_property_not_found>
499  {
500    template<typename Graph, typename CentralityMap,
501             typename EdgeCentralityMap, typename VertexIndexMap>
502    static void
503    run(const Graph& g, CentralityMap centrality,
504        EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index,
505        error_property_not_found)
506    {
507      brandes_betweenness_centrality_dispatch2(g, centrality, edge_centrality_map,
508                                               vertex_index);
509    }
510  };
511
512} } // end namespace detail::graph
513
514template<typename Graph, typename Param, typename Tag, typename Rest>
515void
516brandes_betweenness_centrality(const Graph& g,
517                               const bgl_named_params<Param,Tag,Rest>& params)
518{
519  typedef bgl_named_params<Param,Tag,Rest> named_params;
520
521  typedef typename property_value<named_params, edge_weight_t>::type ew;
522  detail::graph::brandes_betweenness_centrality_dispatch1<ew>::run(
523    g,
524    choose_param(get_param(params, vertex_centrality),
525                 dummy_property_map()),
526    choose_param(get_param(params, edge_centrality),
527                 dummy_property_map()),
528    choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
529    get_param(params, edge_weight));
530}
531
532template<typename Graph, typename CentralityMap>
533void
534brandes_betweenness_centrality(const Graph& g, CentralityMap centrality)
535{
536  detail::graph::brandes_betweenness_centrality_dispatch2(
537    g, centrality, dummy_property_map(), get(vertex_index, g));
538}
539
540template<typename Graph, typename CentralityMap, typename EdgeCentralityMap>
541void
542brandes_betweenness_centrality(const Graph& g, CentralityMap centrality,
543                               EdgeCentralityMap edge_centrality_map)
544{
545  detail::graph::brandes_betweenness_centrality_dispatch2(
546    g, centrality, edge_centrality_map, get(vertex_index, g));
547}
548
549/**
550 * Converts "absolute" betweenness centrality (as computed by the
551 * brandes_betweenness_centrality algorithm) in the centrality map
552 * into "relative" centrality. The result is placed back into the
553 * given centrality map.
554 */
555template<typename Graph, typename CentralityMap>
556void
557relative_betweenness_centrality(const Graph& g, CentralityMap centrality)
558{
559  typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
560  typedef typename property_traits<CentralityMap>::value_type centrality_type;
561
562  typename graph_traits<Graph>::vertices_size_type n = num_vertices(g);
563  centrality_type factor = centrality_type(2)/centrality_type(n*n - 3*n + 2);
564  vertex_iterator v, v_end;
565  for (tie(v, v_end) = vertices(g); v != v_end; ++v) {
566    put(centrality, *v, factor * get(centrality, *v));
567  }
568}
569
570// Compute the central point dominance of a graph.
571template<typename Graph, typename CentralityMap>
572typename property_traits<CentralityMap>::value_type
573central_point_dominance(const Graph& g, CentralityMap centrality)
574{
575  using std::max;
576
577  typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
578  typedef typename property_traits<CentralityMap>::value_type centrality_type;
579
580  typename graph_traits<Graph>::vertices_size_type n = num_vertices(g);
581
582  // Find max centrality
583  centrality_type max_centrality(0);
584  vertex_iterator v, v_end;
585  for (tie(v, v_end) = vertices(g); v != v_end; ++v) {
586    max_centrality = (max)(max_centrality, get(centrality, *v));
587  }
588
589  // Compute central point dominance
590  centrality_type sum(0);
591  for (tie(v, v_end) = vertices(g); v != v_end; ++v) {
592    sum += (max_centrality - get(centrality, *v));
593  }
594  return sum/(n-1);
595}
596
597} // end namespace boost
598
599#endif // BOOST_GRAPH_BRANDES_BETWEENNESS_CENTRALITY_HPP
Note: See TracBrowser for help on using the repository browser.