1.. Copyright (C) 2004-2009 The Trustees of Indiana University. 2 Use, modification and distribution is subject to the Boost Software 3 License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 4 http://www.boost.org/LICENSE_1_0.txt) 5 6============================================= 7|Logo| Non-Distributed Betweenness Centrality 8============================================= 9 10:: 11 12 // named parameter versions 13 template<typename ProcessGroup, typename Graph, typename Param, typename Tag, typename Rest> 14 void 15 non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg, const Graph& g, 16 const bgl_named_params<Param,Tag,Rest>& params); 17 18 template<typename ProcessGroup, typename Graph, typename CentralityMap, 19 typename Buffer> 20 void 21 non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg, const Graph& g, 22 CentralityMap centrality, Buffer sources); 23 24 template<typename ProcessGroup, typename Graph, typename CentralityMap, 25 typename EdgeCentralityMap, typename Buffer> 26 void 27 non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg, const Graph& g, 28 CentralityMap centrality, 29 EdgeCentralityMap edge_centrality_map, 30 Buffer sources); 31 32 // non-named parameter versions 33 template<typename ProcessGroup, typename Graph, typename CentralityMap, 34 typename EdgeCentralityMap, typename IncomingMap, typename DistanceMap, 35 typename DependencyMap, typename PathCountMap, typename VertexIndexMap, 36 typename Buffer> 37 void 38 non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg, 39 const Graph& g, 40 CentralityMap centrality, 41 EdgeCentralityMap edge_centrality_map, 42 IncomingMap incoming, 43 DistanceMap distance, 44 DependencyMap dependency, 45 PathCountMap path_count, 46 VertexIndexMap vertex_index, 47 Buffer sources); 48 49 template<typename ProcessGroup, typename Graph, typename CentralityMap, 50 typename EdgeCentralityMap, typename IncomingMap, typename DistanceMap, 51 typename DependencyMap, typename PathCountMap, typename VertexIndexMap, 52 typename WeightMap, typename Buffer> 53 void 54 non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg, 55 const Graph& g, 56 CentralityMap centrality, 57 EdgeCentralityMap edge_centrality_map, 58 IncomingMap incoming, 59 DistanceMap distance, 60 DependencyMap dependency, 61 PathCountMap path_count, 62 VertexIndexMap vertex_index, 63 WeightMap weight_map, 64 Buffer sources); 65 66 // helper functions 67 template<typename Graph, typename CentralityMap> 68 typename property_traits<CentralityMap>::value_type 69 central_point_dominance(const Graph& g, CentralityMap centrality); 70 71The ``non_distributed_betweenness_centrality()`` function computes the 72betweenness centrality of the vertices and edges in a graph. The name 73is somewhat confusing, the graph ``g`` is not a distributed graph, 74however the algorithm does run in parallel. Rather than parallelizing 75the individual shortest paths calculations that are required by 76betweenness centrality, this variant of the algorithm performs the 77shortest paths calculations in parallel with each process in ``pg`` 78calculating the shortest path from a different set of source vertices 79using the BGL's implementation of `Dijkstra shortest paths`_. Each 80process accumulates into it's local centrality map and once all the 81shortest paths calculations are performed a reduction is performed to 82combine the centrality from all the processes. 83 84.. contents:: 85 86Where Defined 87------------- 88<``boost/graph/distributed/betweenness_centrality.hpp``> 89 90Parameters 91---------- 92 93IN: ``const ProcessGroup& pg`` 94 The process group over which the the processes involved in 95 betweenness centrality communicate. The process group type must 96 model the `Process Group`_ concept. 97 98IN: ``const Graph& g`` 99 The graph type must be a model of the `Incidence Graph`_ concept. 100 101IN: ``CentralityMap centrality`` 102 A centrality map may be supplied to the algorithm, if one is not 103 supplied a ``dummy_property_map`` will be used and no vertex 104 centrality information will be recorded. The key type of the 105 ``CentralityMap`` must be the graph's vertex descriptor type. 106 107 **Default**: A ``dummy_property_map``. 108 109IN: ``EdgeCentralityMap edge_centrality_map`` 110 An edge centrality map may be supplied to the algorithm, if one is 111 not supplied a ``dummy_property_map`` will be used and no edge 112 centrality information will be recorded. The key type of the 113 ``EdgeCentralityMap`` must be the graph's vertex descriptor type. 114 115 **Default**: A ``dummy_property_map``. 116 117IN: ``IncomingMap incoming`` 118 The incoming map contains the incoming edges to a vertex that are 119 part of shortest paths to that vertex. Its key type must be the 120 graph's vertex descriptor type and its value type must be the 121 graph's edge descriptor type. 122 123 **Default**: An ``iterator_property_map`` created from a 124 ``std::vector`` of ``std::vector`` of the graph's edge descriptor 125 type. 126 127IN: ``DistanceMap distance`` 128 The distance map records the distance to vertices during the 129 shortest paths portion of the algorithm. Its key type must be the 130 graph's vertex descriptor type. 131 132 **Default**: An ``iterator_property_map`` created from a 133 ``std::vector`` of the value type of the ``CentralityMap``. 134 135IN: ``DependencyMap dependency`` 136 The dependency map records the dependency of each vertex during the 137 centrality calculation portion of the algorithm. Its key type must 138 be the graph's vertex descriptor type. 139 140 **Default**: An ``iterator_property_map`` created from a 141 ``std::vector`` of the value type of the ``CentralityMap``. 142 143IN: ``PathCountMap path_count`` 144 The path count map records the number of shortest paths each vertex 145 is on during the centrality calculation portion of the algorithm. 146 Its key type must be the graph's vertex descriptor type. 147 148 **Default**: An ``iterator_property_map`` created from a 149 ``std::vector`` of the graph's degree size type. 150 151IN: ``VertexIndexMap vertex_index`` 152 A model of `Readable Property Map`_ whose key type is the vertex 153 descriptor type of the graph ``g`` and whose value type is an 154 integral type. The property map should map from vertices to their 155 (local) indices in the range *[0, num_vertices(g))*. 156 157 **Default**: ``get(vertex_index, g)`` 158 159IN: ``WeightMap weight_map`` 160 A model of `Readable Property Map`_ whose key type is the edge 161 descriptor type of the graph ``g``. If not supplied the betweenness 162 centrality calculation will be unweighted. 163 164IN: ``Buffer sources`` 165 A model of Buffer_ containing the starting vertices for the 166 algorithm. If ``sources`` is empty a complete betweenness 167 centrality calculation using all vertices in ``g`` will be 168 performed. The value type of the Buffer must be the graph's vertex 169 descriptor type. 170 171 **Default**: An empty ``boost::queue`` of int. 172 173Complexity 174---------- 175 176Each of the shortest paths calculations is *O(V log V)* and each of 177them may be run in parallel (one per process in ``pg``). The 178reduction phase to calculate the total centrality at the end of the 179shortest paths phase is *O(V log V)*. 180 181Algorithm Description 182--------------------- 183 184The algorithm uses a non-distributed (sequential) graph, as well as 185non-distributed property maps. Each process contains a separate copy 186of the sequential graph ``g``. In order for the algorithm to be 187correct, these copies of ``g`` must be identical. The ``sources`` 188buffer contains the vertices to use as the source of single source 189shortest paths calculations when approximating betweenness centrality 190using a subset of the vertices in the graph. If ``sources`` is empty 191then a complete betweenness centrality calculation is performed using 192all vertices. 193 194In the sequential phase of the algorithm each process computes 195shortest paths from a subset of the vertices in the graph using the 196Brandes shortest paths methods from the BGL's betweenness centrality 197implementation. In the parallel phase of the algorithm a reduction is 198performed to sum the values computed by each process for all vertices 199in the graph. 200 201Either weighted or unweighted betweenness centrality is calculated 202depending on whether a ``WeightMap`` is passed. 203 204----------------------------------------------------------------------------- 205 206Copyright (C) 2009 The Trustees of Indiana University. 207 208Authors: Nick Edmonds and Andrew Lumsdaine 209 210.. |Logo| image:: pbgl-logo.png 211 :align: middle 212 :alt: Parallel BGL 213 :target: http://www.osl.iu.edu/research/pbgl 214 215.. _Process Group: process_group.html 216.. _Buffer: http://www.boost.org/libs/graph/doc/Buffer.html 217.. _Dijkstra shortest paths: http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html 218.. _Readable Property Map: http://www.boost.org/libs/property_map/ReadablePropertyMap.html 219.. _Incidence Graph: http://www.boost.org/libs/graph/doc/IncidenceGraph.html 220