123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219 |
- .. Copyright (C) 2004-2009 The Trustees of Indiana University.
- Use, modification and distribution is subject to the Boost Software
- License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
- http://www.boost.org/LICENSE_1_0.txt)
- =============================================
- |Logo| Non-Distributed Betweenness Centrality
- =============================================
- ::
- // named parameter versions
- template<typename ProcessGroup, typename Graph, typename Param, typename Tag, typename Rest>
- void
- non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg, const Graph& g,
- const bgl_named_params<Param,Tag,Rest>& params);
- template<typename ProcessGroup, typename Graph, typename CentralityMap,
- typename Buffer>
- void
- non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg, const Graph& g,
- CentralityMap centrality, Buffer sources);
- template<typename ProcessGroup, typename Graph, typename CentralityMap,
- typename EdgeCentralityMap, typename Buffer>
- void
- non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg, const Graph& g,
- CentralityMap centrality,
- EdgeCentralityMap edge_centrality_map,
- Buffer sources);
- // non-named parameter versions
- template<typename ProcessGroup, typename Graph, typename CentralityMap,
- typename EdgeCentralityMap, typename IncomingMap, typename DistanceMap,
- typename DependencyMap, typename PathCountMap, typename VertexIndexMap,
- typename Buffer>
- void
- non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg,
- const Graph& g,
- CentralityMap centrality,
- EdgeCentralityMap edge_centrality_map,
- IncomingMap incoming,
- DistanceMap distance,
- DependencyMap dependency,
- PathCountMap path_count,
- VertexIndexMap vertex_index,
- Buffer sources);
- template<typename ProcessGroup, typename Graph, typename CentralityMap,
- typename EdgeCentralityMap, typename IncomingMap, typename DistanceMap,
- typename DependencyMap, typename PathCountMap, typename VertexIndexMap,
- typename WeightMap, typename Buffer>
- void
- non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg,
- const Graph& g,
- CentralityMap centrality,
- EdgeCentralityMap edge_centrality_map,
- IncomingMap incoming,
- DistanceMap distance,
- DependencyMap dependency,
- PathCountMap path_count,
- VertexIndexMap vertex_index,
- WeightMap weight_map,
- Buffer sources);
- // helper functions
- template<typename Graph, typename CentralityMap>
- typename property_traits<CentralityMap>::value_type
- central_point_dominance(const Graph& g, CentralityMap centrality);
- The ``non_distributed_betweenness_centrality()`` function computes the
- betweenness centrality of the vertices and edges in a graph. The name
- is somewhat confusing, the graph ``g`` is not a distributed graph,
- however the algorithm does run in parallel. Rather than parallelizing
- the individual shortest paths calculations that are required by
- betweenness centrality, this variant of the algorithm performs the
- shortest paths calculations in parallel with each process in ``pg``
- calculating the shortest path from a different set of source vertices
- using the BGL's implementation of `Dijkstra shortest paths`_. Each
- process accumulates into it's local centrality map and once all the
- shortest paths calculations are performed a reduction is performed to
- combine the centrality from all the processes.
- .. contents::
- Where Defined
- -------------
- <``boost/graph/distributed/betweenness_centrality.hpp``>
- Parameters
- ----------
- IN: ``const ProcessGroup& pg``
- The process group over which the the processes involved in
- betweenness centrality communicate. The process group type must
- model the `Process Group`_ concept.
- IN: ``const Graph& g``
- The graph type must be a model of the `Incidence Graph`_ concept.
- IN: ``CentralityMap centrality``
- A centrality map may be supplied to the algorithm, if one is not
- supplied a ``dummy_property_map`` will be used and no vertex
- centrality information will be recorded. The key type of the
- ``CentralityMap`` must be the graph's vertex descriptor type.
- **Default**: A ``dummy_property_map``.
- IN: ``EdgeCentralityMap edge_centrality_map``
- An edge centrality map may be supplied to the algorithm, if one is
- not supplied a ``dummy_property_map`` will be used and no edge
- centrality information will be recorded. The key type of the
- ``EdgeCentralityMap`` must be the graph's vertex descriptor type.
- **Default**: A ``dummy_property_map``.
- IN: ``IncomingMap incoming``
- The incoming map contains the incoming edges to a vertex that are
- part of shortest paths to that vertex. Its key type must be the
- graph's vertex descriptor type and its value type must be the
- graph's edge descriptor type.
- **Default**: An ``iterator_property_map`` created from a
- ``std::vector`` of ``std::vector`` of the graph's edge descriptor
- type.
- IN: ``DistanceMap distance``
- The distance map records the distance to vertices during the
- shortest paths portion of the algorithm. Its key type must be the
- graph's vertex descriptor type.
- **Default**: An ``iterator_property_map`` created from a
- ``std::vector`` of the value type of the ``CentralityMap``.
- IN: ``DependencyMap dependency``
- The dependency map records the dependency of each vertex during the
- centrality calculation portion of the algorithm. Its key type must
- be the graph's vertex descriptor type.
- **Default**: An ``iterator_property_map`` created from a
- ``std::vector`` of the value type of the ``CentralityMap``.
- IN: ``PathCountMap path_count``
- The path count map records the number of shortest paths each vertex
- is on during the centrality calculation portion of the algorithm.
- Its key type must be the graph's vertex descriptor type.
- **Default**: An ``iterator_property_map`` created from a
- ``std::vector`` of the graph's degree size type.
- IN: ``VertexIndexMap vertex_index``
- A model of `Readable Property Map`_ whose key type is the vertex
- descriptor type of the graph ``g`` and whose value type is an
- integral type. The property map should map from vertices to their
- (local) indices in the range *[0, num_vertices(g))*.
- **Default**: ``get(vertex_index, g)``
- IN: ``WeightMap weight_map``
- A model of `Readable Property Map`_ whose key type is the edge
- descriptor type of the graph ``g``. If not supplied the betweenness
- centrality calculation will be unweighted.
- IN: ``Buffer sources``
- A model of Buffer_ containing the starting vertices for the
- algorithm. If ``sources`` is empty a complete betweenness
- centrality calculation using all vertices in ``g`` will be
- performed. The value type of the Buffer must be the graph's vertex
- descriptor type.
- **Default**: An empty ``boost::queue`` of int.
- Complexity
- ----------
- Each of the shortest paths calculations is *O(V log V)* and each of
- them may be run in parallel (one per process in ``pg``). The
- reduction phase to calculate the total centrality at the end of the
- shortest paths phase is *O(V log V)*.
- Algorithm Description
- ---------------------
- The algorithm uses a non-distributed (sequential) graph, as well as
- non-distributed property maps. Each process contains a separate copy
- of the sequential graph ``g``. In order for the algorithm to be
- correct, these copies of ``g`` must be identical. The ``sources``
- buffer contains the vertices to use as the source of single source
- shortest paths calculations when approximating betweenness centrality
- using a subset of the vertices in the graph. If ``sources`` is empty
- then a complete betweenness centrality calculation is performed using
- all vertices.
- In the sequential phase of the algorithm each process computes
- shortest paths from a subset of the vertices in the graph using the
- Brandes shortest paths methods from the BGL's betweenness centrality
- implementation. In the parallel phase of the algorithm a reduction is
- performed to sum the values computed by each process for all vertices
- in the graph.
- Either weighted or unweighted betweenness centrality is calculated
- depending on whether a ``WeightMap`` is passed.
- -----------------------------------------------------------------------------
- Copyright (C) 2009 The Trustees of Indiana University.
- Authors: Nick Edmonds and Andrew Lumsdaine
- .. |Logo| image:: pbgl-logo.png
- :align: middle
- :alt: Parallel BGL
- :target: http://www.osl.iu.edu/research/pbgl
- .. _Process Group: process_group.html
- .. _Buffer: http://www.boost.org/libs/graph/doc/Buffer.html
- .. _Dijkstra shortest paths: http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html
- .. _Readable Property Map: http://www.boost.org/libs/property_map/ReadablePropertyMap.html
- .. _Incidence Graph: http://www.boost.org/libs/graph/doc/IncidenceGraph.html
|