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