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)
6 =============================================
7 |Logo| Non-Distributed Betweenness Centrality
8 =============================================
12 // named parameter versions
13 template<typename ProcessGroup, typename Graph, typename Param, typename Tag, typename Rest>
15 non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg, const Graph& g,
16 const bgl_named_params<Param,Tag,Rest>& params);
18 template<typename ProcessGroup, typename Graph, typename CentralityMap,
21 non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg, const Graph& g,
22 CentralityMap centrality, Buffer sources);
24 template<typename ProcessGroup, typename Graph, typename CentralityMap,
25 typename EdgeCentralityMap, typename Buffer>
27 non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg, const Graph& g,
28 CentralityMap centrality,
29 EdgeCentralityMap edge_centrality_map,
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,
38 non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg,
40 CentralityMap centrality,
41 EdgeCentralityMap edge_centrality_map,
44 DependencyMap dependency,
45 PathCountMap path_count,
46 VertexIndexMap vertex_index,
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>
54 non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg,
56 CentralityMap centrality,
57 EdgeCentralityMap edge_centrality_map,
60 DependencyMap dependency,
61 PathCountMap path_count,
62 VertexIndexMap vertex_index,
67 template<typename Graph, typename CentralityMap>
68 typename property_traits<CentralityMap>::value_type
69 central_point_dominance(const Graph& g, CentralityMap centrality);
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.
88 <``boost/graph/distributed/betweenness_centrality.hpp``>
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.
98 IN: ``const Graph& g``
99 The graph type must be a model of the `Incidence Graph`_ concept.
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.
107 **Default**: A ``dummy_property_map``.
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.
115 **Default**: A ``dummy_property_map``.
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.
123 **Default**: An ``iterator_property_map`` created from a
124 ``std::vector`` of ``std::vector`` of the graph's edge descriptor
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.
132 **Default**: An ``iterator_property_map`` created from a
133 ``std::vector`` of the value type of the ``CentralityMap``.
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.
140 **Default**: An ``iterator_property_map`` created from a
141 ``std::vector`` of the value type of the ``CentralityMap``.
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.
148 **Default**: An ``iterator_property_map`` created from a
149 ``std::vector`` of the graph's degree size type.
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))*.
157 **Default**: ``get(vertex_index, g)``
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.
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
171 **Default**: An empty ``boost::queue`` of int.
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)*.
181 Algorithm Description
182 ---------------------
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
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
201 Either weighted or unweighted betweenness centrality is calculated
202 depending on whether a ``WeightMap`` is passed.
204 -----------------------------------------------------------------------------
206 Copyright (C) 2009 The Trustees of Indiana University.
208 Authors: Nick Edmonds and Andrew Lumsdaine
210 .. |Logo| image:: pbgl-logo.png
213 :target: http://www.osl.iu.edu/research/pbgl
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