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>;
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:
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.
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.
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.
<boost/graph/distributed/adjacency_list.hpp>
Since the distributed adjacency list closely follows the non-distributed adjacency_list, this reference documentation only describes where the two implementations differ.
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(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 construct 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.
void swap(adjacency_list& x)
TODO: Not yet implemented.
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.
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.
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.
std::pair<edge_descriptor, bool>
add_edge(vertex_descriptor u, vertex_descriptor v,
adjacency_list& g);
Adds edge (u,v) to the graph and returns the edge descriptor for the new 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 vertex u must be stored in the executing process.
std::pair<edge_descriptor, bool>
add_edge(vertex_descriptor u, vertex_descriptor 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. Also 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.
vertex_descriptor add_vertex(const VertexProperties& p, adjacency_list& g);
Adds a vertex to the graph with the specified properties. Returns the vertex descriptor for the new vertex. The vertex will be stored in the local process.
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.
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.
Authors: Douglas Gregor and Andrew Lumsdaine