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