]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
71 | The ``non_distributed_betweenness_centrality()`` function computes the | |
72 | betweenness centrality of the vertices and edges in a graph. The name | |
73 | is somewhat confusing, the graph ``g`` is not a distributed graph, | |
74 | however the algorithm does run in parallel. Rather than parallelizing | |
75 | the individual shortest paths calculations that are required by | |
76 | betweenness centrality, this variant of the algorithm performs the | |
77 | shortest paths calculations in parallel with each process in ``pg`` | |
78 | calculating the shortest path from a different set of source vertices | |
79 | using the BGL's implementation of `Dijkstra shortest paths`_. Each | |
80 | process accumulates into it's local centrality map and once all the | |
81 | shortest paths calculations are performed a reduction is performed to | |
82 | combine the centrality from all the processes. | |
83 | ||
84 | .. contents:: | |
85 | ||
86 | Where Defined | |
87 | ------------- | |
88 | <``boost/graph/distributed/betweenness_centrality.hpp``> | |
89 | ||
90 | Parameters | |
91 | ---------- | |
92 | ||
93 | IN: ``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 | ||
98 | IN: ``const Graph& g`` | |
99 | The graph type must be a model of the `Incidence Graph`_ concept. | |
100 | ||
101 | IN: ``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 | ||
109 | IN: ``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 | ||
117 | IN: ``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 | ||
127 | IN: ``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 | ||
135 | IN: ``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 | ||
143 | IN: ``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 | ||
151 | IN: ``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 | ||
159 | IN: ``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 | ||
164 | IN: ``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 | ||
173 | Complexity | |
174 | ---------- | |
175 | ||
176 | Each of the shortest paths calculations is *O(V log V)* and each of | |
177 | them may be run in parallel (one per process in ``pg``). The | |
178 | reduction phase to calculate the total centrality at the end of the | |
179 | shortest paths phase is *O(V log V)*. | |
180 | ||
181 | Algorithm Description | |
182 | --------------------- | |
183 | ||
184 | The algorithm uses a non-distributed (sequential) graph, as well as | |
185 | non-distributed property maps. Each process contains a separate copy | |
186 | of the sequential graph ``g``. In order for the algorithm to be | |
187 | correct, these copies of ``g`` must be identical. The ``sources`` | |
188 | buffer contains the vertices to use as the source of single source | |
189 | shortest paths calculations when approximating betweenness centrality | |
190 | using a subset of the vertices in the graph. If ``sources`` is empty | |
191 | then a complete betweenness centrality calculation is performed using | |
192 | all vertices. | |
193 | ||
194 | In the sequential phase of the algorithm each process computes | |
195 | shortest paths from a subset of the vertices in the graph using the | |
196 | Brandes shortest paths methods from the BGL's betweenness centrality | |
197 | implementation. In the parallel phase of the algorithm a reduction is | |
198 | performed to sum the values computed by each process for all vertices | |
199 | in the graph. | |
200 | ||
201 | Either weighted or unweighted betweenness centrality is calculated | |
202 | depending on whether a ``WeightMap`` is passed. | |
203 | ||
204 | ----------------------------------------------------------------------------- | |
205 | ||
206 | Copyright (C) 2009 The Trustees of Indiana University. | |
207 | ||
208 | Authors: 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 |