Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / betweenness_centrality.hpp
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
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>::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
514 template<typename Graph, typename Param, typename Tag, typename Rest>
515 void 
516 brandes_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
532 template<typename Graph, typename CentralityMap>
533 void 
534 brandes_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
540 template<typename Graph, typename CentralityMap, typename EdgeCentralityMap>
541 void 
542 brandes_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  */
555 template<typename Graph, typename CentralityMap>
556 void 
557 relative_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.
571 template<typename Graph, typename CentralityMap>
572 typename property_traits<CentralityMap>::value_type
573 central_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