[ceph.git] / ceph / src / boost / libs / graph_parallel / doc / DistributedVertexListGraph.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| Concept Distributed Vertex List Graph
============================================

.. contents::

Description
-----------

A Distributed Vertex List Graph is a graph whose vertices are
distributed across multiple processes or address spaces. The
``vertices`` and ``num_vertices`` functions retain the same
signatures as in the `Vertex List Graph`_ concept, but return only
the local set (and size of the local set) of vertices. 

Notation
--------

G
  A type that models the Distributed Vertex List Graph concept.

g
  An object of type ``G``.

Refinement of
-------------

  - `Graph`_

Associated types
----------------

+----------------+---------------------------------------+---------------------------------+
|Vertex          |``graph_traits<G>::vertex_descriptor`` |Must model the                   |
|descriptor type |                                       |`Global Descriptor`_ concept.    |
+----------------+---------------------------------------+---------------------------------+
|Vertex iterator |``graph_traits<G>::vertex_iterator``   |Iterates over vertices stored    |
|type            |                                       |locally. The value type must be  |
|                |                                       |``vertex_descriptor``.           |
+----------------+---------------------------------------+---------------------------------+
|Vertices size   |``graph_traits<G>::vertices_size_type``|The unsigned integral type used  |
|type            |                                       |to store the number of vertices  |
|                |                                       |in the local subgraph.           |
+----------------+---------------------------------------+---------------------------------+

Valid Expressions
-----------------

+----------------+---------------------+----------------------+-------------------------------------+
|Name            |Expression           |Type                  |Semantics                            |
+================+=====================+======================+=====================================+
|Local vertex set|``vertices(g)``      |``std::pair<``        |Returns an iterator range            |
|                |                     |``vertex_iterator,``  |providing access to the local        |
|                |                     |``vertex_iterator>``  |vertices in the graph.               |
+----------------+---------------------+----------------------+-------------------------------------+
|Number of local |``num_vertices(g)``  |``vertices_size_type``|Returns the number of vertices       |
|vertices.       |                     |                      |stored locally in the graph.         |
+----------------+---------------------+----------------------+-------------------------------------+


Models
------

  - `Distributed adjacency list`_

-----------------------------------------------------------------------------

Copyright (C) 2005 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

.. _Graph: http://www.boost.org/libs/graph/doc/Graph.html
.. _Vertex List Graph: http://www.boost.org/libs/graph/doc/VertexListGraph.html
.. _Distributed Graph: DistributedGraph.html
.. _Global descriptor: GlobalDescriptor.html
.. _Distributed adjacency list: distributed_adjacency_list.html
Commit	Line	Data
7c673cae FG	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\| Concept Distributed Vertex List Graph
	8	============================================
	9
	10	.. contents::
	11
	12	Description
	13	-----------
	14
	15	A Distributed Vertex List Graph is a graph whose vertices are
	16	distributed across multiple processes or address spaces. The
	17	``vertices`` and ``num_vertices`` functions retain the same
	18	signatures as in the `Vertex List Graph`_ concept, but return only
	19	the local set (and size of the local set) of vertices.
	20
	21	Notation
	22	--------
	23
	24	G
	25	A type that models the Distributed Vertex List Graph concept.
	26
	27	g
	28	An object of type ``G``.
	29
	30	Refinement of
	31	-------------
	32
	33	- `Graph`_
	34
	35	Associated types
	36	----------------
	37
	38	+----------------+---------------------------------------+---------------------------------+
	39	\|Vertex \|``graph_traits<G>::vertex_descriptor`` \|Must model the \|
	40	\|descriptor type \| \|`Global Descriptor`_ concept. \|
	41	+----------------+---------------------------------------+---------------------------------+
	42	\|Vertex iterator \|``graph_traits<G>::vertex_iterator`` \|Iterates over vertices stored \|
	43	\|type \| \|locally. The value type must be \|
	44	\| \| \|``vertex_descriptor``. \|
	45	+----------------+---------------------------------------+---------------------------------+
	46	\|Vertices size \|``graph_traits<G>::vertices_size_type``\|The unsigned integral type used \|
	47	\|type \| \|to store the number of vertices \|
	48	\| \| \|in the local subgraph. \|
	49	+----------------+---------------------------------------+---------------------------------+
	50
	51	Valid Expressions
	52	-----------------
	53
	54	+----------------+---------------------+----------------------+-------------------------------------+
	55	\|Name \|Expression \|Type \|Semantics \|
	56	+================+=====================+======================+=====================================+
	57	\|Local vertex set\|``vertices(g)`` \|``std::pair<`` \|Returns an iterator range \|
	58	\| \| \|``vertex_iterator,`` \|providing access to the local \|
	59	\| \| \|``vertex_iterator>`` \|vertices in the graph. \|
	60	+----------------+---------------------+----------------------+-------------------------------------+
	61	\|Number of local \|``num_vertices(g)`` \|``vertices_size_type``\|Returns the number of vertices \|
	62	\|vertices. \| \| \|stored locally in the graph. \|
	63	+----------------+---------------------+----------------------+-------------------------------------+
	64
65
66	Models
67	------
68
69	- `Distributed adjacency list`_
70
71	-----------------------------------------------------------------------------
72
73	Copyright (C) 2005 The Trustees of Indiana University.
74
75	Authors: Douglas Gregor and Andrew Lumsdaine
76
77	.. \|Logo\| image:: pbgl-logo.png
78	:align: middle
79	:alt: Parallel BGL
80	:target: http://www.osl.iu.edu/research/pbgl
81
82	.. _Graph: http://www.boost.org/libs/graph/doc/Graph.html
83	.. _Vertex List Graph: http://www.boost.org/libs/graph/doc/VertexListGraph.html
84	.. _Distributed Graph: DistributedGraph.html
85	.. _Global descriptor: GlobalDescriptor.html
86	.. _Distributed adjacency list: distributed_adjacency_list.html