122 lines
4.7 KiB
ReStructuredText
122 lines
4.7 KiB
ReStructuredText
.. Copyright (C) 2004-2008 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| Vertex List Graph Adaptor
|
|
================================
|
|
|
|
::
|
|
|
|
template<typename Graph, typename GlobalIndexMap>
|
|
class vertex_list_adaptor
|
|
{
|
|
public:
|
|
vertex_list_adaptor(const Graph& g,
|
|
const GlobalIndexMap& index_map = GlobalIndexMap());
|
|
};
|
|
|
|
template<typename Graph, typename GlobalIndexMap>
|
|
vertex_list_adaptor<Graph, GlobalIndexMap>
|
|
make_vertex_list_adaptor(const Graph& g, const GlobalIndexMap& index_map);
|
|
|
|
template<typename Graph>
|
|
vertex_list_adaptor<Graph, *unspecified*>
|
|
make_vertex_list_adaptor(const Graph& g);
|
|
|
|
|
|
The vertex list graph adaptor adapts any model of `Distributed Vertex List
|
|
Graph`_ in a `Vertex List Graph`_. In the former type of graph, the
|
|
set of vertices is distributed across the process group, so no
|
|
process has access to all vertices. In the latter type of graph,
|
|
however, every process has access to every vertex in the graph. This
|
|
is required by some distributed algorithms, such as the
|
|
implementations of `Minimum spanning tree`_ algorithms.
|
|
|
|
.. contents::
|
|
|
|
Where Defined
|
|
-------------
|
|
<``boost/graph/distributed/vertex_list_adaptor.hpp``>
|
|
|
|
|
|
Class template ``vertex_list_adaptor``
|
|
--------------------------------------
|
|
|
|
The ``vertex_list_adaptor`` class template takes a `Distributed
|
|
Vertex List Graph`_ and a mapping from vertex descriptors to global
|
|
vertex indices, which must be in the range *[0, n)*, where *n* is the
|
|
number of vertices in the entire graph. The mapping is a `Readable
|
|
Property Map`_ whose key type is a vertex descriptor.
|
|
|
|
The vertex list adaptor stores only a reference to the underlying
|
|
graph, forwarding all operations not related to the vertex list on to
|
|
the underlying graph. For instance, if the underlying graph models
|
|
`Adjacency Graph`_, then the adaptor will also model `Adjacency
|
|
Graph`_. Note, however, that no modifications to the underlying graph
|
|
can occur through the vertex list adaptor. Modifications made to the
|
|
underlying graph directly will be reflected in the vertex list
|
|
adaptor, but modifications that add or remove vertices invalidate the
|
|
vertex list adaptor. Additionally, the vertex list adaptor provides
|
|
access to the global index map via the ``vertex_index`` property.
|
|
|
|
On construction, the vertex list adaptor performs an all-gather
|
|
operation to create a list of all vertices in the graph within each
|
|
process. It is this list that is accessed via *vertices* and the
|
|
length of this list that is accessed via *num_vertices*. Due to the
|
|
all-gather operation, the creation of this adaptor is a collective
|
|
operation.
|
|
|
|
Function templates ``make_vertex_list_adaptor``
|
|
-----------------------------------------------
|
|
|
|
These function templates construct a vertex list adaptor from a graph
|
|
and, optionally, a property map that maps vertices to global index
|
|
numbers.
|
|
|
|
Parameters
|
|
~~~~~~~~~~
|
|
|
|
IN: ``Graph& g``
|
|
The graph type must be a model of `Distributed Vertex List Graph`_.
|
|
|
|
IN: ``GlobalIndexMap index_map``
|
|
A `Distributed property map`_ whose type must model `Readable
|
|
property map`_ that maps from vertices to a global index. If
|
|
provided, this map must be initialized prior to be passed to the
|
|
vertex list adaptor.
|
|
|
|
**Default:** A property map of unspecified type constructed from a
|
|
distributed ``iterator_property_map`` that uses the
|
|
``vertex_index`` property map of the underlying graph and a vector
|
|
of ``vertices_size_type``.
|
|
|
|
Complexity
|
|
~~~~~~~~~~
|
|
These operations require *O(n)* time, where *n* is the number of
|
|
vertices in the graph, and *O(n)* communication per node in the BSP model.
|
|
|
|
-----------------------------------------------------------------------------
|
|
|
|
Copyright (C) 2004 The Trustees of Indiana University.
|
|
|
|
Authors: Douglas Gregor and Andrew Lumsdaine
|
|
|
|
.. |Logo| image:: pbgl-logo.png
|
|
:align: middle
|
|
:alt: Parallel BGL
|
|
:target: http://www.osl.iu.edu/research/pbgl
|
|
|
|
.. _Kruskal's algorithm: http://www.boost.org/libs/graph/doc/kruskal_min_spanning_tree.html
|
|
.. _Vertex list graph: http://www.boost.org/libs/graph/doc/VertexListGraph.html
|
|
.. _Adjacency graph: http://www.boost.org/libs/graph/doc/AdjacencyGraph.html
|
|
.. _distributed adjacency list: distributed_adjacency_list.html
|
|
.. _Minimum spanning tree: dehne_gotz_min_spanning_tree.html
|
|
.. _Distributed Vertex List Graph: DistributedVertexListGraph.html
|
|
.. _Distributed property map: distributed_property_map.html
|
|
.. _Readable Property Map: http://www.boost.org/libs/property_map/ReadablePropertyMap.html
|
|
.. _Read/Write Property Map: http://www.boost.org/libs/property_map/ReadWritePropertyMap.html
|
|
|
|
|