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