ceph/src/boost/libs/graph_parallel/doc/vertex_list_adaptor.rst

   1 .. Copyright (C) 2004-2008 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)
   5
   6 ================================
   7 |Logo| Vertex List Graph Adaptor
   8 ================================
   9
  10 ::
  11
  12   template<typename Graph, typename GlobalIndexMap>
  13   class vertex_list_adaptor
  14   {
  15   public:
  16     vertex_list_adaptor(const Graph& g,
  17                         const GlobalIndexMap& index_map = GlobalIndexMap());
  18   };
  19
  20   template<typename Graph, typename GlobalIndexMap>
  21   vertex_list_adaptor<Graph, GlobalIndexMap>
  22   make_vertex_list_adaptor(const Graph& g, const GlobalIndexMap& index_map);
  23
  24   template<typename Graph>
  25   vertex_list_adaptor<Graph, *unspecified*>
  26   make_vertex_list_adaptor(const Graph& g);
  27
  28
  29 The vertex list graph adaptor adapts any model of `Distributed Vertex List
  30 Graph`_ in a `Vertex List Graph`_. In the former type of graph, the
  31 set of vertices is distributed across the process group, so no
  32 process has access to all vertices. In the latter type of graph,
  33 however, every process has access to every vertex in the graph. This
  34 is required by some distributed algorithms, such as the
  35 implementations of `Minimum spanning tree`_ algorithms.
  36
  37 .. contents::
  38
  39 Where Defined
  40 -------------
  41 <``boost/graph/distributed/vertex_list_adaptor.hpp``>
  42
  43
  44 Class template ``vertex_list_adaptor``
  45 --------------------------------------
  46
  47 The ``vertex_list_adaptor`` class template takes a `Distributed
  48 Vertex List Graph`_ and a mapping from vertex descriptors to global
  49 vertex indices, which must be in the range *[0, n)*, where *n* is the
  50 number of vertices in the entire graph. The mapping is a `Readable
  51 Property Map`_ whose key type is a vertex descriptor.
  52
  53 The vertex list adaptor stores only a reference to the underlying
  54 graph, forwarding all operations not related to the vertex list on to
  55 the underlying graph. For instance, if the underlying graph models
  56 `Adjacency Graph`_, then the adaptor will also model `Adjacency
  57 Graph`_. Note, however, that no modifications to the underlying graph
  58 can occur through the vertex list adaptor. Modifications made to the
  59 underlying graph directly will be reflected in the vertex list
  60 adaptor, but modifications that add or remove vertices invalidate the
  61 vertex list adaptor. Additionally, the vertex list adaptor provides
  62 access to the global index map via the ``vertex_index`` property.
  63
  64 On construction, the vertex list adaptor performs an all-gather
  65 operation to create a list of all vertices in the graph within each
  66 process. It is this list that is accessed via *vertices* and the
  67 length of this list that is accessed via *num_vertices*. Due to the
  68 all-gather operation, the creation of this adaptor is a collective
  69 operation.
  70
  71 Function templates ``make_vertex_list_adaptor``
  72 -----------------------------------------------
  73
  74 These function templates construct a vertex list adaptor from a graph
  75 and, optionally, a property map that maps vertices to global index
  76 numbers.
  77
  78 Parameters
  79 ~~~~~~~~~~
  80
  81 IN: ``Graph& g``
  82   The graph type must be a model of `Distributed Vertex List Graph`_.
  83
  84 IN: ``GlobalIndexMap index_map``
  85   A `Distributed property map`_ whose type must model `Readable
  86   property map`_ that maps from vertices to a global index. If
  87   provided, this map must be initialized prior to be passed to the
  88   vertex list adaptor.
  89
  90   **Default:** A property map of unspecified type constructed from a
  91   distributed ``iterator_property_map`` that uses the
  92   ``vertex_index`` property map of the underlying graph and a vector
  93   of ``vertices_size_type``.
  94
  95 Complexity
  96 ~~~~~~~~~~
  97 These operations require *O(n)* time, where *n* is the number of
  98 vertices in the graph, and *O(n)* communication per node in the BSP model.
  99
 100 -----------------------------------------------------------------------------
 101
 102 Copyright (C) 2004 The Trustees of Indiana University.
 103
 104 Authors: Douglas Gregor and Andrew Lumsdaine
 105
 106 .. |Logo| image:: pbgl-logo.png
 107             :align: middle
 108             :alt: Parallel BGL
 109             :target: http://www.osl.iu.edu/research/pbgl
 110
 111 .. _Kruskal's algorithm: http://www.boost.org/libs/graph/doc/kruskal_min_spanning_tree.html
 112 .. _Vertex list graph: http://www.boost.org/libs/graph/doc/VertexListGraph.html
 113 .. _Adjacency graph: http://www.boost.org/libs/graph/doc/AdjacencyGraph.html
 114 .. _distributed adjacency list: distributed_adjacency_list.html
 115 .. _Minimum spanning tree: dehne_gotz_min_spanning_tree.html
 116 .. _Distributed Vertex List Graph: DistributedVertexListGraph.html
 117 .. _Distributed property map: distributed_property_map.html
 118 .. _Readable Property Map: http://www.boost.org/libs/property_map/ReadablePropertyMap.html
 119 .. _Read/Write Property Map: http://www.boost.org/libs/property_map/ReadWritePropertyMap.html
 120
 121