|
| enum | {
msg_add_vertex_with_property = 0,
msg_add_vertex_with_property_and_reply,
msg_add_vertex_reply,
msg_add_edge,
msg_add_edge_with_property,
msg_add_edge_with_reply,
msg_add_edge_with_property_and_reply,
msg_add_edge_reply,
msg_nonlocal_edge,
msg_remove_edge,
msg_num_relocated
} |
| | The set of messages that can be transmitted and received by a distributed adjacency list. More...
|
| |
typedef
config_type::in_edge_list_type | in_edge_list_type |
| | The container type that will store incoming edges for a bidirectional graph. More...
|
| |
| typedef config_type::inherited | inherited |
| | The type of the underlying adjacency list implementation. More...
|
| |
typedef
inherited::vertex_property_type | base_vertex_property_type |
| | The type of properties stored in the local subgraph Bidirectional graphs have an extra vertex property to store the incoming edges. More...
|
| |
| typedef config_type::graph_type | graph_type |
| | The type of the distributed adjacency list (this type) More...
|
| |
typedef
traits_type::local_vertex_descriptor | local_vertex_descriptor |
| | Expose graph components and graph category. More...
|
| |
typedef
traits_type::local_edge_descriptor | local_edge_descriptor |
| |
typedef
traits_type::vertex_descriptor | vertex_descriptor |
| |
typedef
traits_type::edge_descriptor | edge_descriptor |
| |
typedef
traits_type::directed_category | directed_category |
| |
typedef
inherited::edge_parallel_category | edge_parallel_category |
| |
| typedef inherited::graph_tag | graph_tag |
| |
typedef boost::mpl::if_
< is_same< DirectedS,
directedS >
, directed_distributed_adj_list_tag,
typename boost::mpl::if_
< is_same< DirectedS,
bidirectionalS >
, bidirectional_distributed_adj_list_tag,
undirected_distributed_adj_list_tag >
::type >::type | traversal_category |
| | Determine the graph traversal category. More...
|
| |
| typedef inherited::degree_size_type | degree_size_type |
| |
typedef
inherited::vertices_size_type | vertices_size_type |
| |
| typedef inherited::edges_size_type | edges_size_type |
| |
| typedef VertexProperty | vertex_property_type |
| |
| typedef EdgeProperty | edge_property_type |
| |
typedef
inherited::graph_property_type | graph_property_type |
| |
| typedef inherited::vertex_bundled | vertex_bundled |
| |
| typedef inherited::edge_bundled | edge_bundled |
| |
| typedef inherited::graph_bundled | graph_bundled |
| |
typedef container_gen
< edge_list_selector,
edge_descriptor >::type | local_edge_list_type |
| |
typedef transform_iterator
< typename
vertex_descriptor::generator,
typename
inherited::vertex_iterator > | vertex_iterator |
| | Iterator over the (local) vertices of the graph. More...
|
| |
typedef
edge_descriptor::template
out_generator< adjacency_list > | out_edge_generator |
| | Helper for out_edge_iterator. More...
|
| |
typedef transform_iterator
< out_edge_generator, typename
inherited::out_edge_iterator > | out_edge_iterator |
| | Iterator over the outgoing edges of a vertex. More...
|
| |
typedef
edge_descriptor::template
in_generator< adjacency_list > | in_edge_generator |
| | Helper for in_edge_iterator. More...
|
| |
typedef transform_iterator
< in_edge_generator,
base_in_edge_iterator > | in_edge_iterator |
| | Iterator over the incoming edges of a vertex. More...
|
| |
typedef
boost::adjacency_iterator
< adjacency_list,
vertex_descriptor,
out_edge_iterator, typename
detail::iterator_traits
< base_out_edge_iterator >
::difference_type > | adjacency_iterator |
| | Iterator over the neighbors of a vertex. More...
|
| |
typedef boost::mpl::if_
< is_same< DirectedS,
undirectedS >
, undirected_edge_iterator,
transform_iterator
< out_edge_generator,
base_edge_iterator > >::type | edge_iterator |
| | Iterator over the (local) edges in a graph. More...
|
| |
typedef
graph::distributed::maybe_named_graph
< graph_type,
vertex_descriptor,
edge_descriptor, config_type > | named_graph_mixin |
| | The type of the mixin for named vertices. More...
|
| |
| typedef ProcessGroup | process_group_type |
| | Process group used for communication. More...
|
| |
typedef
process_group_type::process_id_type | process_id_type |
| | How to refer to a process. More...
|
| |
| typedef DirectedS | directed_selector |
| | Whether this graph is directed, undirected, or bidirectional. More...
|
| |
typedef
graph::distributed::select_distribution
< InDistribution,
VertexProperty,
vertices_size_type,
ProcessGroup >::default_type | default_distribution_type |
| | default_distribution_type is the type of the distribution used if the user didn't specify an explicit one More...
|
| |
typedef
graph::distributed::select_distribution
< InDistribution,
VertexProperty,
vertices_size_type,
ProcessGroup >::type | base_distribution_type |
| | distribution_type is the type of the distribution instance stored in the maybe_named_graph base class More...
|
| |
typedef
graph::distributed::shuffled_distribution
< base_distribution_type > | distribution_type |
| |
typedef
detail::parallel::msg_add_edge_data
< vertex_descriptor,
local_vertex_descriptor > | msg_add_edge_data |
| |
typedef
detail::parallel::msg_add_edge_with_property_data
< vertex_descriptor,
local_vertex_descriptor,
edge_property_type > | msg_add_edge_with_property_data |
| |
typedef
boost::detail::parallel::msg_nonlocal_edge_data
< edge_property_type,
local_edge_descriptor > | msg_nonlocal_edge_data |
| |
typedef
boost::detail::parallel::msg_remove_edge_data
< edge_descriptor > | msg_remove_edge_data |
| |
| enum | message_kind |
| | Messages passed within the distributed named graph. More...
|
| |
typedef internal_vertex_name
< vertex_property_type >::type | extract_name_type |
| | The type used to extract names from the property structure. More...
|
| |
typedef remove_cv< typename
remove_reference< typename
extract_name_type::result_type >
::type >::type | vertex_name_type |
| | The type used to name vertices in the graph. More...
|
| |
| typedef named_graph | named_graph_type |
| | a reference to this class, which is used for disambiguation of the More...
|
| |
|
| | BOOST_STATIC_ASSERT ((is_same< edge_parallel_category, allow_parallel_edge_tag >::value)) |
| |
| | adjacency_list (const ProcessGroup &pg=ProcessGroup()) |
| |
| | adjacency_list (const ProcessGroup &pg, const base_distribution_type &distribution) |
| |
| | adjacency_list (const GraphProperty &g, const ProcessGroup &pg=ProcessGroup()) |
| |
| | adjacency_list (vertices_size_type n, const GraphProperty &p, const ProcessGroup &pg, const base_distribution_type &distribution) |
| |
| | adjacency_list (vertices_size_type n, const ProcessGroup &pg, const base_distribution_type &distribution) |
| |
| | adjacency_list (vertices_size_type n, const GraphProperty &p, const ProcessGroup &pg=ProcessGroup()) |
| |
| | adjacency_list (vertices_size_type n, const ProcessGroup &pg=ProcessGroup()) |
| |
| 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 &pg, const base_distribution_type &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 &pg, const base_distribution_type &distribution, const GraphProperty &p=GraphProperty()) |
| |
| | ~adjacency_list () |
| |
| void | clear () |
| |
| void | swap (adjacency_list &other) |
| |
| inherited & | base () |
| |
| const inherited & | base () const |
| |
| processor_id_type | processor () const |
| |
| process_group_type | process_group () const |
| |
| local_edge_list_type & | local_edges () |
| |
| const local_edge_list_type & | local_edges () const |
| |
| template<typename VertexProcessorMap > |
| void | redistribute (VertexProcessorMap vertex_to_processor) |
| |
| vertex_bundled & | operator[] (vertex_descriptor v) |
| |
| const vertex_bundled & | operator[] (vertex_descriptor v) const |
| |
| edge_bundled & | operator[] (edge_descriptor e) |
| |
| const edge_bundled & | operator[] (edge_descriptor e) const |
| |
| graph_bundled & | operator[] (graph_bundle_t) |
| |
| graph_bundled const & | operator[] (graph_bundle_t) const |
| |
| template<typename OStreamConstructibleArchive > |
| void | save (std::string const &filename) const |
| |
| template<typename IStreamConstructibleArchive > |
| void | load (std::string const &filename) |
| |
| base_vertex_property_type | build_vertex_property (const vertex_property_type &p) |
| |
| base_vertex_property_type | build_vertex_property (const vertex_property_type &p, directedS) |
| |
| base_vertex_property_type | build_vertex_property (const vertex_property_type &p, bidirectionalS) |
| |
| base_vertex_property_type | build_vertex_property (const vertex_property_type &p, undirectedS) |
| |
| base_edge_property_type | build_edge_property (const edge_property_type &p) |
| |
| base_edge_property_type | build_edge_property (const edge_property_type &p, directedS) |
| |
| base_edge_property_type | build_edge_property (const edge_property_type &p, bidirectionalS) |
| |
| base_edge_property_type | build_edge_property (const edge_property_type &p, undirectedS) |
| |
| edge_property_type | split_edge_property (const base_edge_property_type &p) |
| |
| edge_property_type | split_edge_property (const base_edge_property_type &p, directedS) |
| |
| edge_property_type | split_edge_property (const base_edge_property_type &p, bidirectionalS) |
| |
| edge_property_type | split_edge_property (const base_edge_property_type &p, undirectedS) |
| |
| void | send_remove_edge_request (edge_descriptor e) |
| |
| void | setup_triggers () |
| | Process incoming messages. More...
|
| |
| void | handle_add_vertex_with_property (int source, int tag, const vertex_property_type &, trigger_receive_context) |
| |
| local_vertex_descriptor | handle_add_vertex_with_property_and_reply (int source, int tag, const vertex_property_type &, trigger_receive_context) |
| |
| void | handle_add_edge (int source, int tag, const msg_add_edge_data &data, trigger_receive_context) |
| |
boost::parallel::detail::untracked_pair
< edge_descriptor, bool > | handle_add_edge_with_reply (int source, int tag, const msg_add_edge_data &data, trigger_receive_context) |
| |
| void | handle_add_edge_with_property (int source, int tag, const msg_add_edge_with_property_data &, trigger_receive_context) |
| |
boost::parallel::detail::untracked_pair
< edge_descriptor, bool > | handle_add_edge_with_property_and_reply (int source, int tag, const msg_add_edge_with_property_data &, trigger_receive_context) |
| |
| void | handle_nonlocal_edge (int source, int tag, const msg_nonlocal_edge_data &data, trigger_receive_context) |
| |
| void | handle_remove_edge (int source, int tag, const msg_remove_edge_data &data, trigger_receive_context) |
| |
| void | remove_local_edge_from_list (vertex_descriptor, vertex_descriptor, directedS) |
| |
| void | remove_local_edge_from_list (vertex_descriptor, vertex_descriptor, bidirectionalS) |
| |
| void | remove_local_edge_from_list (vertex_descriptor src, vertex_descriptor tgt, undirectedS) |
| |
| distribution_type & | distribution () |
| |
| const distribution_type & | distribution () const |
| |
adjacency_list< OutEdgeListS,
distributedS< ProcessGroup,
InVertexListS, InDistribution >
, DirectedS, VertexProperty,
EdgeProperty, GraphProperty,
EdgeListS > & | derived () |
| | Retrieve the derived instance. More...
|
| |
const adjacency_list
< OutEdgeListS, distributedS
< ProcessGroup, InVertexListS,
InDistribution >, DirectedS,
VertexProperty, EdgeProperty,
GraphProperty, EdgeListS > & | derived () const |
| |
| process_group_type & | process_group () |
| | Retrieve the process group. More...
|
| |
| distribution_type & | named_distribution () |
| |
| const distribution_type & | named_distribution () const |
| |
| void | added_vertex (adjacency_list_traits< OutEdgeListS, distributedS< ProcessGroup, InVertexListS, InDistribution >, DirectedS >::vertex_descriptor) |
| | Notify the named_graph that we have added the given vertex. More...
|
| |
| void | removing_vertex (adjacency_list_traits< OutEdgeListS, distributedS< ProcessGroup, InVertexListS, InDistribution >, DirectedS >::vertex_descriptor, VertexIterStability) |
| | Notify the named_graph that we are removing the given vertex. More...
|
| |
| void | clearing_graph () |
| | Notify the named_graph that we are clearing the graph. More...
|
| |
| process_id_type | owner_by_property (const vertex_property_type &) |
| | Retrieve the owner of a given vertex based on the properties associated with that vertex. More...
|
| |
|
| void | add_remote_edge (const msg_nonlocal_edge_data &, processor_id_type, directedS) |
| | Add an edge (locally) that was received from another processor. More...
|
| |
| void | add_remote_edge (const msg_nonlocal_edge_data &data, processor_id_type other_proc, bidirectionalS) |
| | This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts. More...
|
| |
| void | add_remote_edge (const msg_nonlocal_edge_data &data, processor_id_type other_proc, undirectedS) |
| | This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts. More...
|
| |
| void | remove_local_edge (const msg_remove_edge_data &, processor_id_type, directedS) |
| |
| void | remove_local_edge (const msg_remove_edge_data &data, processor_id_type other_proc, bidirectionalS) |
| |
| void | remove_local_edge (const msg_remove_edge_data &data, processor_id_type other_proc, undirectedS) |
| |
| void | handle_add_vertex_name (int source, int tag, const vertex_name_type &msg, trigger_receive_context) |
| |
| vertex_descriptor | handle_add_vertex_name_with_reply (int source, int tag, const vertex_name_type &msg, trigger_receive_context) |
| |
boost::parallel::detail::untracked_pair
< vertex_descriptor, bool > | handle_find_vertex (int source, int tag, const vertex_name_type &msg, trigger_receive_context) |
| |
| void | handle_add_edge (int source, int tag, const boost::parallel::detail::untracked_pair< U, V > &msg, trigger_receive_context) |
| |
boost::parallel::detail::untracked_pair
< edge_descriptor, bool > | handle_add_edge_with_reply (int source, int tag, const boost::parallel::detail::untracked_pair< U, V > &msg, trigger_receive_context) |
| |
| void | handle_add_edge_with_property (int source, int tag, const pair_with_property< U, V, edge_property_type > &msg, trigger_receive_context) |
| |
boost::parallel::detail::untracked_pair
< edge_descriptor, bool > | handle_add_edge_with_reply_and_property (int source, int tag, const pair_with_property< U, V, edge_property_type > &msg, trigger_receive_context) |
| |
template<typename OutEdgeListS, typename ProcessGroup, typename InVertexListS, typename InDistribution, typename DirectedS, typename VertexProperty, typename EdgeProperty, typename GraphProperty, typename EdgeListS>
class boost::adjacency_list< OutEdgeListS, distributedS< ProcessGroup, InVertexListS, InDistribution >, DirectedS, VertexProperty, EdgeProperty, GraphProperty, EdgeListS >
A distributed adjacency list.
This class template partial specialization defines a distributed (or "partitioned") adjacency list graph. The distributed adjacency list is similar to the standard Boost Graph Library adjacency list, which stores a list of vertices and for each verted the list of edges outgoing from the vertex (and, in some cases, also the edges incoming to the vertex). The distributed adjacency list differs in that it partitions the graph into several subgraphs that are then divided among different processors (or nodes within a cluster). The distributed adjacency list attempts to maintain a high degree of compatibility with the standard, non-distributed adjacency list.
The graph is partitioned by vertex, with each processor storing all of the required information for a particular subset of the vertices, including vertex properties, outgoing edges, and (for bidirectional graphs) incoming edges. This information is accessible only on the processor that owns the vertex: for instance, if processor 0 owns vertex v, no other processor can directly access the properties of v or enumerate its outgoing edges.
Edges in a graph may be entirely local (connecting two local vertices), but more often it is the case that edges are non-local, meaning that the two vertices they connect reside in different processes. Edge properties are stored with the originating vertex for directed and bidirectional graphs, and are therefore only accessible from the processor that owns the originating vertex. Other processors may query the source and target of the edge, but cannot access its properties. This is particularly interesting when accessing the incoming edges of a bidirectional graph, which are not guaranteed to be stored on the processor that is able to perform the iteration. For undirected graphs the situation is more complicated, since no vertex clearly owns the edges: the list of edges incident to a vertex may contain a mix of local and non-local edges.
The distributed adjacency list is able to model several of the existing Graph concepts. It models the Graph concept because it exposes vertex and edge descriptors in the normal way; these descriptors model the GlobalDescriptor concept (because they have an owner and a local descriptor), and as such the distributed adjacency list models the DistributedGraph concept. The adjacency list also models the IncidenceGraph and AdjacencyGraph concepts, although this is only true so long as the domain of the valid expression arguments are restricted to vertices and edges stored locally. Likewise, bidirectional and undirected distributed adjacency lists model the BidirectionalGraph concept (vertex and edge domains must be respectived) and the distributed adjacency list models the MutableGraph concept (vertices and edges can only be added or removed locally). T he distributed adjacency list does not, however, model the VertexListGraph or EdgeListGraph concepts, because we can not efficiently enumerate all vertices or edges in the graph. Instead, the local subsets of vertices and edges can be enumerated (with the same syntax): the distributed adjacency list therefore models the DistributedVertexListGraph and DistributedEdgeListGraph concepts, because concurrent iteration over all of the vertices or edges stored on each processor will visit each vertex or edge.
The distributed adjacency list is distinguished from the non-distributed version by the vertex list descriptor, which will be distributedS<ProcessGroup,VertexListS>. Here, the VertexListS type plays the same role as the VertexListS type in the non-distributed adjacency list: it allows one to select the data structure that will be used to store the local vertices. The ProcessGroup type, on the other hand, is unique to distributed data structures: it is the type that abstracts a group of cooperating processes, and it used for process identification, communication, and synchronization, among other things. Different process group types represent different communication mediums (e.g., MPI, PVM, TCP) or different models of communication (LogP, CGM, BSP, synchronous, etc.). This distributed adjacency list assumes a model based on non-blocking sends.
Distribution of vertices across different processors is accomplished in two different ways. When initially constructing the graph, the user may provide a distribution object (that models the Distribution concept), which will determine the distribution of vertices to each process. Additionally, the add_vertex and add_edge operations add vertices or edges stored on the local processor. For add_edge, this is accomplished by requiring that the source vertex of the new edge be local to the process executing add_edge.
Internal properties of a distributed adjacency list are accessible in the same manner as internal properties for a non-distributed adjacency list for local vertices or edges. Access to properties for remote vertices or edges occurs with the same syntax, but involve communication with the owner of the information: for more information, refer to class template distributed_property_map, which manages distributed property maps. Note that the distributed property maps created for internal properties determine their reduction operation via the metafunction property_reduce, which for the vast majority of uses is correct behavior.
Communication among the processes coordinating on a particular distributed graph relies on non-blocking message passing along with synchronization. Local portions of the distributed graph may be modified concurrently, including the introduction of non-local edges, but prior to accessing the graph it is recommended that the synchronize free function be invoked on the graph to clear up any pending interprocess communication and modifications. All processes will then be released from the synchronization barrier concurrently.
- Todo:
- Determine precisely what we should do with nonlocal edges in undirected graphs. Our parallelization of certain algorithms relies on the ability to access edge property maps immediately (e.g., edge_weight_t), so it may be necessary to duplicate the edge properties in both processes (but then we need some form of coherence protocol).
- Todo:
- What does the user do if
property_reduce doesn't do the right thing?
1.8.8