bump version to 12.2.2-pve1

[ceph.git] / ceph / src / boost / libs / graph_parallel / doc / distributed_adjacency_list.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| Distributed Adjacency List
=================================

.. contents::

Introduction
------------

The distributed adjacency list implements a graph data structure using
an adjacency list representation. Its interface and behavior are
roughly equivalent to the Boost Graph Library's adjacency_list_
class template. However, the distributed adjacency list partitions the
vertices of the graph across several processes (which need not share
an address space). Edges outgoing from any vertex stored by a process
are also stored on that process, except in the case of undirected
graphs, where either the source or the target may store the edge.

::

  template<typename OutEdgeListS, typename ProcessGroup, typename VertexListS,
           typename DirectedS, typename VertexProperty, typename EdgeProperty, 
           typename GraphProperty, typename EdgeListS>
  class adjacency_list<OutEdgeListS, 
                       distributedS<ProcessGroup, VertexListS>,
                       DirectedS, VertexProperty,
                       EdgeProperty, GraphProperty, EdgeListS>;

Defining a Distributed Adjacency List
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
To create a distributed adjacency list, first determine the
representation of the graph in a single address space using these
guidelines_. Next, replace the vertex list selector (``VertexListS``)
with an instantiation of distributedS_, which includes:

- Selecting a `process group`_ type that represents the various
  coordinating processes that will store the distributed graph. For
  example, the `MPI process group`_.

- A selector indicating how the vertex lists in each process will be
  stored. Only the ``vecS`` and ``listS`` selectors are well-supported
  at this time.


The following ``typedef`` defines a distributed adjacency list
containing directed edges. The vertices in the graph will be
distributed over several processes, using the MPI process group
for communication. In each process, the vertices and outgoing edges
will be stored in STL vectors. There are no properties attached to the
vertices or edges of the graph.

::

  using namespace boost;
  typedef adjacency_list<vecS, 
                         distributedS<parallel::mpi::bsp_process_group, vecS>,
                         directedS> 
    Graph;


Distributed Vertex and Edge Properties
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Vertex and edge properties for distributed graphs mirror their
counterparts for non-distributed graphs. With a distributed graph,
however, vertex and edge properties are stored only in the process
that owns the vertex or edge. 

The most direct way to attach properties to a distributed graph is to
create a structure that will be attached to each of the vertices and
edges of the graph. For example, if we wish to model a simplistic map
of the United States interstate highway system, we might state that
the vertices of the graph are cities and the edges are highways, then
define the information that we maintain for each city and highway:

::

  struct City {
    City() { }
    City(const std::string& name, const std::string& mayor = "Unknown", int population = 0)
      : name(name), mayor(mayor), population(population) { }

    std::string name;
    std::string mayor;
    int population;

    // Serialization support is required!
    template<typename Archiver>
    void serialize(Archiver& ar, const unsigned int /*version*/) {
      ar & name & mayor & population;
    }
  };

  struct Highway {
    Highway() { }
    Highway(const std::string& name, int lanes, int miles_per_hour, int length) 
      : name(name), lanes(lanes), miles_per_hour(miles_per_hour), length(length) { }

    std::string name;
    int lanes;
    int miles_per_hour;
    int length;

    // Serialization support is required!
    template<typename Archiver>
    void serialize(Archiver& ar, const unsigned int /*version*/) {
      ar & name & lanes & miles_per_hour & length;
    }
  };


To create a distributed graph for a road map, we supply ``City`` and
``Highway`` as the fourth and fifth parameters to ``adjacency_list``,
respectively:

::

  typedef adjacency_list<vecS, 
                         distributedS<parallel::mpi::bsp_process_group, vecS>,
                         directedS,
                         City, Highway> 
    RoadMap;


Property maps for internal properties retain their behavior with
distributed graphs via `distributed property maps`_, which automate
communication among processes so that ``put`` and ``get`` operations
may be applied to non-local vertices and edges. However, for
distributed adjacency lists that store vertices in a vector
(``VertexListS`` is ``vecS``), the automatic ``vertex_index``
property map restricts the domain of ``put`` and ``get`` operations
to vertices local to the process executing the operation. For example,
we can create a property map that accesses the length of each highway
as follows:

::

  RoadMap map; // distributed graph instance

  typedef property_map<RoadMap, int Highway::*>::type 
    road_length = get(&Highway::length, map);


Now, one can access the length of any given road based on its edge
descriptor ``e`` with the expression ``get(road_length, e)``,
regardless of which process stores the edge ``e``. 

Named Vertices
~~~~~~~~~~~~~~

The vertices of a graph typically correspond to named entities within
the application domain. In the road map example from the previous
section, the vertices in the graph represent cities. The distributed
adjacency list supports named vertices, which provides an implicit
mapping from the names of the vertices in the application domain
(e.g., the name of a city, such as "Bloomington") to the actual vertex
descriptor stored within the distributed graph (e.g., the third vertex
on processor 1). By enabling support for named vertices, one can refer
to vertices by name when manipulating the graph. For example, one can
add a highway from Indianapolis to Chicago:

::
  
  add_edge("Indianapolis", "Chicago", Highway("I-65", 4, 65, 151), map);

The distributed adjacency list will find vertices associated with the
names "Indianapolis" and "Chicago", then add an edge between these
vertices that represents I-65. The vertices may be stored on any
processor, local or remote. 

To enable named vertices, specialize the ``internal_vertex_name``
property for the structure attached to the vertices in your
graph. ``internal_vertex_name`` contains a single member, ``type``,
which is the type of a function object that accepts a vertex property
and returns the name stored within that vertex property. In the case
of our road map, the ``name`` field contains the name of each city, so
we use the ``member`` function object from the `Boost.MultiIndex`_
library to extract the name, e.g.,

::

  namespace boost { namespace graph { 

  template<>
  struct internal_vertex_name<City>
  {
    typedef multi_index::member<City, std::string, &City::name> type;
  };
  
  } }


That's it! One can now refer to vertices by name when interacting with
the distributed adjacency list.

What happens when one uses the name of a vertex that does not exist?
For example, in our ``add_edge`` call above, what happens if the
vertex named "Indianapolis" has not yet been added to the graph? By
default, the distributed adjacency list will throw an exception if a
named vertex does not yet exist. However, one can customize this
behavior by specifying a function object that constructs an instance
of the vertex property (e.g., ``City``) from just the name of the
vertex. This customization occurs via the
``internal_vertex_constructor`` trait. For example, using the
``vertex_from_name`` template (provided with the Parallel BGL), we can
state that a ``City`` can be constructed directly from the name of the
city using its second constructor:

::

  namespace boost { namespace graph {

  template<>
  struct internal_vertex_constructor<City>
  {
    typedef vertex_from_name<City> type;
  };

  } }

Now, one can add edges by vertex name freely, without worrying about
the explicit addition of vertices. The ``mayor`` and ``population``
fields will have default values, but the graph structure will be
correct. 

Building a Distributed Graph
~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Once you have determined the layout of your graph type, including the
specific data structures and properties, it is time to construct an
instance of the graph by adding the appropriate vertices and
edges. Construction of distributed graphs can be slightly more
complicated than construction of normal, non-distributed graph data
structures, because one must account for both the distribution of the
vertices and edges and the multiple processes executing
concurrently. There are three main ways to construct distributed
graphs:

1. *Sequence constructors*: if your data can easily be generated by a
pair of iterators that produce (source, target) pairs, you can use the
sequence constructors to build the distributed graph in parallel. This
method is often preferred when creating benchmarks, because random
graph generators like the sorted_erdos_renyi_iterator_ create the
appropriate input sequence. Note that one must provide the same input
iterator sequence on all processes. This method has the advantage that
the sequential graph-building code is identical to the parallel
graph-building code. An example constructing a random graph this way:

  ::

    typedef boost::sorted_erdos_renyi_iterator<boost::minstd_rand, Graph> ERIter;
    boost::minstd_rand gen;
    unsigned long n = 1000000; // 1M vertices
    Graph g(ERIter(gen, n, 0.00005), ERIter(), n);

2. *Adding edges by vertex number*: if you are able to map your
vertices into values in the random [0, *n*), where *n* is the number
of vertices in the distributed graph. Use this method rather than the
sequence constructors when your algorithm cannot easily be moved into
input iterators, or if you can't replicate the input sequence. For
example, you might be reading the graph from an input file:

  ::

    Graph g(n); // initialize with the total number of vertices, n
    if (process_id(g.process_group()) == 0) {
      // Only process 0 loads the graph, which is distributed automatically
      int source, target;
      for (std::cin >> source >> target)
        add_edge(vertex(source, g), vertex(target, g), g);
    }

    // All processes synchronize at this point, then the graph is complete
    synchronize(g.process_group());

3. *Adding edges by name*: if you are using named vertices, you can
construct your graph just by calling ``add_edge`` with the names of
the source and target vertices. Be careful to make sure that each edge
is added by only one process (it doesn't matter which process it is),
otherwise you will end up with multiple edges. For example, in the
following program we read edges from the standard input of process 0,
adding those edges by name. Vertices and edges will be created and
distributed automatically.

  ::

    Graph g;
    if (process_id(g.process_group()) == 0) {
      // Only process 0 loads the graph, which is distributed automatically
      std:string source, target;
      for(std::cin >> source >> target)
        add_edge(source, target, g);
    }

    // All processes synchronize at this point, then the graph is complete
    synchronize(g.process_group());


Graph Concepts
~~~~~~~~~~~~~~

The distributed adjacency list models the Graph_ concept, and in
particular the `Distributed Graph`_ concept. It also models the
`Incidence Graph`_ and `Adjacency Graph`_ concept, but restricts the
input domain of the operations to correspond to local vertices
only. For instance, a process may only access the outgoing edges of a
vertex if that vertex is stored in that process. Undirected and
bidirectional distributed adjacency lists model the `Bidirectional
Graph`_ concept, with the same domain restrictions. Distributed
adjacency lists also model the `Mutable Graph`_ concept (with domain
restrictions; see the Reference_ section), `Property Graph`_ concept,
and `Mutable Property Graph`_ concept.

Unlike its non-distributed counterpart, the distributed adjacency
list does **not** model the `Vertex List Graph`_ or `Edge List
Graph`_ concepts, because one cannot enumerate all vertices or edges
within a distributed graph. Instead, it models the weaker
`Distributed Vertex List Graph`_ and `Distributed Edge List Graph`_
concepts, which permit access to the local edges and vertices on each
processor. Note that if all processes within the process group over
which the graph is distributed iterator over their respective vertex
or edge lists, all vertices and edges will be covered once. 

Reference
---------
Since the distributed adjacency list closely follows the
non-distributed adjacency_list_, this reference documentation
only describes where the two implementations differ.

Where Defined
~~~~~~~~~~~~~

<boost/graph/distributed/adjacency_list.hpp>

Associated Types
~~~~~~~~~~~~~~~~

::

  adjacency_list::process_group_type

The type of the process group over which the graph will be
distributed.

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

  adjacency_list::distribution_type

The type of distribution used to partition vertices in the graph.

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

  adjacency_list::vertex_name_type

If the graph supports named vertices, this is the type used to name
vertices. Otherwise, this type is not present within the distributed
adjacency list. 


Member Functions
~~~~~~~~~~~~~~~~

::

    adjacency_list(const ProcessGroup& pg = ProcessGroup());

    adjacency_list(const GraphProperty& g, 
                   const ProcessGroup& pg = ProcessGroup());

Construct an empty distributed adjacency list with the given process
group (or default) and graph property (or default).

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

::

    adjacency_list(vertices_size_type n, const GraphProperty& p,
                   const ProcessGroup& pg, const Distribution& distribution);

    adjacency_list(vertices_size_type n, const ProcessGroup& pg,
                   const Distribution& distribution);

    adjacency_list(vertices_size_type n, const GraphProperty& p,
                   const ProcessGroup& pg = ProcessGroup());
      
    adjacency_list(vertices_size_type n, 
                   const ProcessGroup& pg = ProcessGroup());

Construct a distributed adjacency list with ``n`` vertices,
optionally providing the graph property, process group, or
distribution. The ``n`` vertices will be distributed via the given
(or default-constructed) distribution. This operation is collective,
requiring all processes with the process group to execute it
concurrently.

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

::

    template <class EdgeIterator>
    adjacency_list(EdgeIterator first, EdgeIterator last,
                   vertices_size_type n, 
                   const ProcessGroup& pg = ProcessGroup(),
                   const GraphProperty& p = GraphProperty());

    template <class EdgeIterator, class EdgePropertyIterator>
    adjacency_list(EdgeIterator first, EdgeIterator last,
                   EdgePropertyIterator ep_iter,
                   vertices_size_type n,
                   const ProcessGroup& pg = ProcessGroup(),
                   const GraphProperty& p = GraphProperty());

    template <class EdgeIterator>
    adjacency_list(EdgeIterator first, EdgeIterator last,
                   vertices_size_type n, 
                   const ProcessGroup& process_group,
                   const Distribution& distribution,
                   const GraphProperty& p = GraphProperty());

    template <class EdgeIterator, class EdgePropertyIterator>
    adjacency_list(EdgeIterator first, EdgeIterator last,
                   EdgePropertyIterator ep_iter,
                   vertices_size_type n,
                   const ProcessGroup& process_group,
                   const Distribution& distribution,
                   const GraphProperty& p = GraphProperty());

Construct a distributed adjacency list with ``n`` vertices and with
edges specified in the edge list given by the range ``[first, last)``. The
``EdgeIterator`` must be a model of InputIterator_. The value type of the
``EdgeIterator`` must be a ``std::pair``, where the type in the pair is an
integer type. The integers will correspond to vertices, and they must
all fall in the range of ``[0, n)``. When provided, ``ep_iter``
refers to an edge property list ``[ep_iter, ep_iter + m)`` contains
properties for each of the edges.

This constructor is a collective operation and must be executed
concurrently by each process with the same argument list. Most
importantly, the edge lists provided to the constructor in each process
should be equivalent. The vertices will be partitioned among the
processes according to the ``distribution``, with edges placed on the
process owning the source of the edge. Note that this behavior
permits sequential graph construction code to be parallelized
automatically, regardless of the underlying distribution. 

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

::

  void clear()

Removes all of the edges and vertices from the local graph. To
eliminate all vertices and edges from the graph, this routine must be
executed in all processes.

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

::

  process_group_type& process_group();
  const process_group_type& process_group() const;

Returns the process group over which this graph is distributed.

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

::

  distribution_type&       distribution();
  const distribution_type& distribution() const;

Returns the distribution used for initial placement of vertices.

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

::

  template<typename VertexProcessorMap>
    void redistribute(VertexProcessorMap vertex_to_processor);

Redistributes the vertices (and, therefore, the edges) of the
graph. The property map ``vertex_to_processor`` provides, for each
vertex, the process identifier indicating where the vertex should be
moved. Once this collective routine has completed, the distributed
graph will reflect the new distribution. All vertex and edge
descsriptors and internal and external property maps are invalidated
by this operation.

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

::

  template<typename OStreamConstructibleArchive>
    void save(std::string const& filename) const;

  template<typename IStreamConstructibleArchive>
    void load(std::string const& filename);

Serializes the graph to a Boost.Serialization archive. 
``OStreamConstructibleArchive`` and ``IStreamConstructibleArchive``
are models of Boost.Serialization *Archive* with the extra
requirement that they can be constructed from a ``std::ostream`` 
and ``std::istream``.
``filename`` names a directory that will hold files for
the different processes.


Non-Member Functions
~~~~~~~~~~~~~~~~~~~~

::

  std::pair<vertex_iterator, vertex_iterator>
  vertices(const adjacency_list& g);

Returns an iterator-range providing access to the vertex set of graph
``g`` stored in this process. Each of the processes that contain ``g``
will get disjoint sets of vertices.

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

::

  std::pair<edge_iterator, edge_iterator>
  edges(const adjacency_list& g);

Returns an iterator-range providing access to the edge set of graph
``g`` stored in this process.

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

::

  std::pair<adjacency_iterator, adjacency_iterator>
  adjacent_vertices(vertex_descriptor u, const adjacency_list& g);

Returns an iterator-range providing access to the vertices adjacent to
vertex ``u`` in graph ``g``. The vertex ``u`` must be local to this process.

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

::

  std::pair<out_edge_iterator, out_edge_iterator>
  out_edges(vertex_descriptor u, const adjacency_list& g);

Returns an iterator-range providing access to the out-edges of vertex
``u`` in graph ``g``. If the graph is undirected, this iterator-range
provides access to all edges incident on vertex ``u``. For both
directed and undirected graphs, for an out-edge ``e``, ``source(e, g)
== u`` and ``target(e, g) == v`` where ``v`` is a vertex adjacent to
``u``. The vertex ``u`` must be local to this process.

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

::

  std::pair<in_edge_iterator, in_edge_iterator>
  in_edges(vertex_descriptor v, const adjacency_list& g);

Returns an iterator-range providing access to the in-edges of vertex
``v`` in graph ``g``. This operation is only available if
``bidirectionalS`` was specified for the ``Directed`` template
parameter. For an in-edge ``e``, ``target(e, g) == v`` and ``source(e,
g) == u`` for some vertex ``u`` that is adjacent to ``v``, whether the
graph is directed or undirected. The vertex ``v`` must be local to
this process.

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

::

  degree_size_type
  out_degree(vertex_descriptor u, const adjacency_list& g);

Returns the number of edges leaving vertex ``u``. Vertex ``u`` must
be local to the executing process.

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

::

  degree_size_type
  in_degree(vertex_descriptor u, const adjacency_list& g);

Returns the number of edges entering vertex ``u``. This operation is
only available if ``bidirectionalS`` was specified for the
``Directed`` template parameter. Vertex ``u`` must be local to the
executing process.

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

::

  vertices_size_type
  num_vertices(const adjacency_list& g);

Returns the number of vertices in the graph ``g`` that are stored in
the executing process.

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

::

  edges_size_type
  num_edges(const adjacency_list& g);

Returns the number of edges in the graph ``g`` that are stored in the
executing process.

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

::

  vertex_descriptor
  vertex(vertices_size_type n, const adjacency_list& g);

Returns the ``n``th vertex in the graph's vertex list, according to the
distribution used to partition the graph. ``n`` must be a value
between zero and the sum of ``num_vertices(g)`` in each process (minus
one). Note that it is not necessarily the case that ``vertex(0, g) ==
*num_vertices(g).first``. This function is only guaranteed to be
accurate when no vertices have been added to or removed from the
graph after its initial construction.

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

::

  std::pair<edge_descriptor, bool>
  edge(vertex_descriptor u, vertex_descriptor v,
       const adjacency_list& g);

Returns an edge connecting vertex ``u`` to vertex ``v`` in graph
``g``. For bidirectional and undirected graphs, either vertex ``u`` or
vertex ``v`` must be local; for directed graphs, vertex ``u`` must be
local.

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

::

  std::pair<out_edge_iterator, out_edge_iterator>
  edge_range(vertex_descriptor u, vertex_descriptor v,
             const adjacency_list& g);

TODO: Not implemented.  Returns a pair of out-edge iterators that give
the range for all the parallel edges from ``u`` to ``v``. This function only
works when the ``OutEdgeList`` for the ``adjacency_list`` is a container that
sorts the out edges according to target vertex, and allows for
parallel edges. The ``multisetS`` selector chooses such a
container. Vertex ``u`` must be stored in the executing process.

Structure Modification
~~~~~~~~~~~~~~~~~~~~~~

::

  unspecified add_edge(vertex_descriptor u, vertex_descriptor v, adjacency_list& g);
  unspecified add_edge(vertex_name_type u, vertex_descriptor v, adjacency_list& g);
  unspecified add_edge(vertex_descriptor u, vertex_name_type v, adjacency_list& g);
  unspecified add_edge(vertex_name_type u, vertex_name_type v, adjacency_list& g);

Adds edge ``(u,v)`` to the graph. The return type itself is
unspecified, but the type can be copy-constructed and implicitly
converted into a ``std::pair<edge_descriptor,bool>``. The edge
descriptor describes the added (or found) edge. For graphs that do not
allow parallel edges, if the edge 
is already in the graph then a duplicate will not be added and the
``bool`` flag will be ``false``. Also, if u and v are descriptors for
the same vertex (creating a self loop) and the graph is undirected,
then the edge will not be added and the flag will be ``false``. When
the flag is ``false``, the returned edge descriptor points to the
already existing edge. 

The parameters ``u`` and ``v`` can be either vertex descriptors or, if
the graph uses named vertices, the names of vertices. If no vertex
with the given name exists, the internal vertex constructor will be
invoked to create a new vertex property and a vertex with that
property will be added to the graph implicitly. The default internal
vertex constructor throws an exception.

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

::

  unspecified add_edge(vertex_descriptor u, vertex_descriptor v, const EdgeProperties& p, adjacency_list& g);
  unspecified add_edge(vertex_name_type u, vertex_descriptor v, const EdgeProperties& p, adjacency_list& g);
  unspecified add_edge(vertex_descriptor u, vertex_name_type v, const EdgeProperties& p, adjacency_list& g);
  unspecified add_edge(vertex_name_type u, vertex_name_type v, const EdgeProperties& p, adjacency_list& g);


Adds edge ``(u,v)`` to the graph and attaches ``p`` as the value of the edge's
internal property storage. See the previous ``add_edge()`` member
function for more details.  

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

::

  void 
  remove_edge(vertex_descriptor u, vertex_descriptor v, 
              adjacency_list& g);

Removes the edge ``(u,v)`` from the graph. If the directed selector is
``bidirectionalS`` or ``undirectedS``, either the source or target
vertex of the graph must be local. If the directed selector is
``directedS``, then the source vertex must be local.

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

::

  void 
  remove_edge(edge_descriptor e, adjacency_list& g);

Removes the edge ``e`` from the graph. If the directed selector is
``bidirectionalS`` or ``undirectedS``, either the source or target
vertex of the graph must be local. If the directed selector is
``directedS``, then the source vertex must be local.

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

::

  void remove_edge(out_edge_iterator iter, adjacency_list& g);

This has the same effect as ``remove_edge(*iter, g)``. For directed
(but not bidirectional) graphs, this will be more efficient than
``remove_edge(*iter, g)``.

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

::

  template <class Predicate >
  void remove_out_edge_if(vertex_descriptor u, Predicate predicate,
                          adjacency_list& g);

Removes all out-edges of vertex ``u`` from the graph that satisfy the
predicate. That is, if the predicate returns ``true`` when applied to an
edge descriptor, then the edge is removed. The vertex ``u`` must be local.

The affect on descriptor and iterator stability is the same as that of
invoking remove_edge() on each of the removed edges.

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

::

  template <class Predicate >
  void remove_in_edge_if(vertex_descriptor v, Predicate predicate,
                         adjacency_list& g);

Removes all in-edges of vertex ``v`` from the graph that satisfy the
predicate. That is, if the predicate returns true when applied to an
edge descriptor, then the edge is removed. The vertex ``v`` must be local.

The affect on descriptor and iterator stability is the same as that of
invoking ``remove_edge()`` on each of the removed edges.

This operation is available for undirected and bidirectional
adjacency_list graphs, but not for directed.  

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

::

  template <class Predicate> 
  void remove_edge_if(Predicate predicate, adjacency_list& g);

Removes all edges from the graph that satisfy the predicate. That is,
if the predicate returns true when applied to an edge descriptor, then
the edge is removed. 

The affect on descriptor and iterator stability is the same as that
of invoking ``remove_edge()`` on each of the removed edges.

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

::

  vertex_descriptor add_vertex(adjacency_list& g);

Adds a vertex to the graph and returns the vertex descriptor for the
new vertex. The vertex will be stored in the local process. This
function is not available when using named vertices.

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

::

  unspecified add_vertex(const VertexProperties& p, adjacency_list& g);
  unspecified add_vertex(const vertex_name_type& p, adjacency_list& g);

Adds a vertex to the graph with the specified properties. If the graph
is using vertex names, the vertex will be added on whichever process
"owns" that name. Otherwise, the vertex will be stored in the local
process. Note that the second constructor will invoke the
user-customizable internal vertex constructor, which (by default)
throws an exception when it sees an unknown vertex. 

The return type is of unspecified type, but can be copy-constructed
and can be implicitly converted into a vertex descriptor.

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

::

  void clear_vertex(vertex_descriptor u, adjacency_list& g);

Removes all edges to and from vertex ``u``. The vertex still appears
in the vertex set of the graph.

The affect on descriptor and iterator stability is the same as that of
invoking ``remove_edge()`` for all of the edges that have ``u`` as the source
or target.

This operation is not applicable to directed graphs, because the
incoming edges to vertex ``u`` are not known.

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

::

  void clear_out_edges(vertex_descriptor u, adjacency_list& g);

Removes all out-edges from vertex ``u``. The vertex still appears in
the vertex set of the graph. 

The affect on descriptor and iterator stability is the same as that of
invoking ``remove_edge()`` for all of the edges that have ``u`` as the
source. 

This operation is not applicable to undirected graphs (use
``clear_vertex()`` instead).

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

::

  void clear_in_edges(vertex_descriptor u, adjacency_list& g);

Removes all in-edges from vertex ``u``. The vertex still appears in
the vertex set of the graph.

The affect on descriptor and iterator stability is the same as that of
invoking ``remove_edge()`` for all of the edges that have ``u`` as the
target. 

This operation is only applicable to bidirectional graphs.

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

::

  void remove_vertex(vertex_descriptor u, adjacency_list& g);

Remove vertex ``u`` from the vertex set of the graph. It is assumed
that there are no edges to or from vertex ``u`` when it is
removed. One way to make sure of this is to invoke ``clear_vertex()``
beforehand. The vertex ``u`` must be stored locally.

Property Map Accessors
~~~~~~~~~~~~~~~~~~~~~~

::

  template <class PropertyTag>
  property_map<adjacency_list, PropertyTag>::type
  get(PropertyTag, adjacency_list& g);

  template <class PropertyTag>
  property_map<adjacency_list, Tag>::const_type
  get(PropertyTag, const adjacency_list& g);

Returns the property map object for the vertex property specified by
``PropertyTag``. The ``PropertyTag`` must match one of the properties
specified in the graph's ``VertexProperty`` template argument. The
returned property map will be a `distributed property map`_.

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

::

  template <class PropertyTag , class X>
  typename property_traits<property_map<adjacency_list, PropertyTag>::const_type>::value_type
  get(PropertyTag, const adjacency_list& g, X x);

This returns the property value for ``x``, where ``x`` is either a vertex or
edge descriptor.  The entity referred to by descriptor ``x`` must be
stored in the local process.

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

::

  template <class PropertyTag , class X, class Value>
  void put(PropertyTag, const adjacency_list& g, X x, const Value& value);

This sets the property value for ``x`` to value. ``x`` is either a
vertex or edge descriptor. ``Value`` must be convertible to ``typename
property_traits<property_map<adjacency_list,
PropertyTag>::type>::value_type``. 

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

::

  template <class GraphProperties, class GraphPropertyTag>
  typename graph_property<adjacency_list, GraphPropertyTag>::type&
  get_property(adjacency_list& g, GraphPropertyTag);

  template <class GraphProperties, class GraphPropertyTag >
  const typename graph_property<adjacency_list, GraphPropertyTag>::type&
  get_property(const adjacency_list& g, GraphPropertyTag);

TODO: not implemented.

Return the property specified by ``GraphPropertyTag`` that is attached
to the graph object ``g``. The ``graph_property`` traits class is
defined in ``boost/graph/adjacency_list.hpp``.

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

Copyright (C) 2004 The Trustees of Indiana University.

Copyright (C) 2007 Douglas Gregor

Authors: Douglas Gregor and Andrew Lumsdaine

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

.. _adjacency_list: http://www.boost.org/libs/graph/doc/adjacency_list.html
.. _guidelines: http://www.boost.org/libs/graph/doc/using_adjacency_list.html
.. _process group: process_group.html
.. _mpi process group: process_group.html
.. _distributedS: distributedS.html
.. _Graph: http://www.boost.org/libs/graph/doc/Graph.html
.. _Distributed graph: DistributedGraph.html
.. _Incidence Graph: http://www.boost.org/libs/graph/doc/IncidenceGraph.html
.. _Adjacency Graph: http://www.boost.org/libs/graph/doc/AdjacencyGraph.html
.. _Bidirectional Graph: http://www.boost.org/libs/graph/doc/BidirectionalGraph.html
.. _Mutable Graph: http://www.boost.org/libs/graph/doc/MutableGraph.html
.. _Property Graph: http://www.boost.org/libs/graph/doc/PropertyGraph.html
.. _Mutable Property Graph: http://www.boost.org/libs/graph/doc/MutablePropertyGraph.html
.. _Vertex List Graph: http://www.boost.org/libs/graph/doc/VertexListGraph.html
.. _Edge List Graph: http://www.boost.org/libs/graph/doc/EdgeListGraph.html
.. _Distribution: concepts/Distribution.html
.. _distributed property map: distributed_property_map.html
.. _distributed property maps: distributed_property_map.html
.. _Distributed Vertex List Graph: DistributedVertexListGraph.html
.. _Distributed Edge List Graph: DistributedEdgeListGraph.html
.. _InputIterator: http://www.boost.org/doc/html/InputIterator.html
.. _member: http://www.boost.org/libs/multi_index/doc/reference/key_extraction.html#member_synopsis
.. _Boost.MultiIndex: http://www.boost.org/libs/multi_index/doc/index.html
.. _sorted_erdos_renyi_iterator: http://www.boost.org/libs/graph/doc/sorted_erdos_renyi_gen.html