bump version to 12.2.2-pve1

[ceph.git] / ceph / src / boost / libs / graph_parallel / doc / vertex_list_adaptor.rst

.. 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