/usr/include/boost/graph/distributed
Edit: /usr/include/boost/graph/distributed/adjacency_list.hpp (149777B)
// Copyright (C) 2004-2006 The Trustees of Indiana University.
// Copyright (C) 2007 Douglas Gregor
// 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)
// Authors: Douglas Gregor
// Andrew Lumsdaine
#ifndef BOOST_GRAPH_DISTRIBUTED_ADJACENCY_LIST_HPP
#define BOOST_GRAPH_DISTRIBUTED_ADJACENCY_LIST_HPP
#ifndef BOOST_GRAPH_USE_MPI
#error "Parallel BGL files should not be included unless
has been included"
#endif
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
// Callbacks
#include
// Serialization
#include
#include
#include
#include
// Named vertices
#include
#include
namespace boost {
/// The type used to store an identifier that uniquely names a processor.
// NGE: I doubt we'll be running on more than 32768 procs for the time being
typedef /*int*/ short processor_id_type;
// Tell which processor the target of an edge resides on (for
// directed graphs) or which processor the other end point of the
// edge resides on (for undirected graphs).
enum edge_target_processor_id_t { edge_target_processor_id };
BOOST_INSTALL_PROPERTY(edge, target_processor_id);
// For undirected graphs, tells whether the edge is locally owned.
enum edge_locally_owned_t { edge_locally_owned };
BOOST_INSTALL_PROPERTY(edge, locally_owned);
// For bidirectional graphs, stores the incoming edges.
enum vertex_in_edges_t { vertex_in_edges };
BOOST_INSTALL_PROPERTY(vertex, in_edges);
/// Tag class for directed, distributed adjacency list
struct directed_distributed_adj_list_tag
: public virtual distributed_graph_tag,
public virtual distributed_vertex_list_graph_tag,
public virtual distributed_edge_list_graph_tag,
public virtual incidence_graph_tag,
public virtual adjacency_graph_tag {};
/// Tag class for bidirectional, distributed adjacency list
struct bidirectional_distributed_adj_list_tag
: public virtual distributed_graph_tag,
public virtual distributed_vertex_list_graph_tag,
public virtual distributed_edge_list_graph_tag,
public virtual incidence_graph_tag,
public virtual adjacency_graph_tag,
public virtual bidirectional_graph_tag {};
/// Tag class for undirected, distributed adjacency list
struct undirected_distributed_adj_list_tag
: public virtual distributed_graph_tag,
public virtual distributed_vertex_list_graph_tag,
public virtual distributed_edge_list_graph_tag,
public virtual incidence_graph_tag,
public virtual adjacency_graph_tag,
public virtual bidirectional_graph_tag {};
namespace detail {
template
void
serialize(Archiver& ar, edge_base& e,
const unsigned int /*version*/)
{
ar & unsafe_serialize(e.m_source)
& unsafe_serialize(e.m_target);
}
template
void
serialize(Archiver& ar, edge_desc_impl& e,
const unsigned int /*version*/)
{
ar & boost::serialization::base_object >(e)
& unsafe_serialize(e.m_eproperty);
}
}
namespace detail { namespace parallel {
/**
* A distributed vertex descriptor. These descriptors contain both
* the ID of the processor that owns the vertex and a local vertex
* descriptor that identifies the particular vertex for that
* processor.
*/
template
struct global_descriptor
{
typedef LocalDescriptor local_descriptor_type;
global_descriptor() : owner(), local() { }
global_descriptor(processor_id_type owner, LocalDescriptor local)
: owner(owner), local(local) { }
processor_id_type owner;
LocalDescriptor local;
/**
* A function object that, given a processor ID, generates
* distributed vertex descriptors from local vertex
* descriptors. This function object is used by the
* vertex_iterator of the distributed adjacency list.
*/
struct generator
{
typedef global_descriptor result_type;
typedef LocalDescriptor argument_type;
generator() {}
generator(processor_id_type owner) : owner(owner) {}
result_type operator()(argument_type v) const
{ return result_type(owner, v); }
private:
processor_id_type owner;
};
template
void serialize(Archiver& ar, const unsigned int /*version*/)
{
ar & owner & unsafe_serialize(local);
}
};
/// Determine the process that owns the given descriptor
template
inline processor_id_type owner(const global_descriptor& v)
{ return v.owner; }
/// Determine the local portion of the given descriptor
template
inline LocalDescriptor local(const global_descriptor& v)
{ return v.local; }
/// Compare distributed vertex descriptors for equality
template
inline bool
operator==(const global_descriptor& u,
const global_descriptor& v)
{
return u.owner == v.owner && u.local == v.local;
}
/// Compare distributed vertex descriptors for inequality
template
inline bool
operator!=(const global_descriptor& u,
const global_descriptor& v)
{ return !(u == v); }
template
inline bool
operator<(const global_descriptor& u,
const global_descriptor& v)
{
return (u.owner) < v.owner || (u.owner == v.owner && (u.local) < v.local);
}
template
inline bool
operator<=(const global_descriptor& u,
const global_descriptor& v)
{
return u.owner <= v.owner || (u.owner == v.owner && u.local <= v.local);
}
template
inline bool
operator>(const global_descriptor& u,
const global_descriptor& v)
{
return v < u;
}
template
inline bool
operator>=(const global_descriptor& u,
const global_descriptor& v)
{
return v <= u;
}
// DPG TBD: Add <, <=, >=, > for global descriptors
/**
* A Readable Property Map that extracts a global descriptor pair
* from a global_descriptor.
*/
template
struct global_descriptor_property_map
{
typedef std::pair value_type;
typedef value_type reference;
typedef global_descriptor key_type;
typedef readable_property_map_tag category;
};
template
inline std::pair
get(global_descriptor_property_map,
global_descriptor x)
{
return std::pair(x.owner, x.local);
}
/**
* A Readable Property Map that extracts the owner of a global
* descriptor.
*/
template
struct owner_property_map
{
typedef processor_id_type value_type;
typedef value_type reference;
typedef global_descriptor key_type;
typedef readable_property_map_tag category;
};
template
inline processor_id_type
get(owner_property_map,
global_descriptor x)
{
return x.owner;
}
/**
* A Readable Property Map that extracts the local descriptor from
* a global descriptor.
*/
template
struct local_descriptor_property_map
{
typedef LocalDescriptor value_type;
typedef value_type reference;
typedef global_descriptor key_type;
typedef readable_property_map_tag category;
};
template
inline LocalDescriptor
get(local_descriptor_property_map,
global_descriptor x)
{
return x.local;
}
/**
* Stores an incoming edge for a bidirectional distributed
* adjacency list. The user does not see this type directly,
* because it is just an implementation detail.
*/
template
struct stored_in_edge
{
stored_in_edge(processor_id_type sp, Edge e)
: source_processor(sp), e(e) {}
processor_id_type source_processor;
Edge e;
};
/**
* A distributed edge descriptor. These descriptors contain the
* underlying edge descriptor, the processor IDs for both the
* source and the target of the edge, and a boolean flag that
* indicates which of the processors actually owns the edge.
*/
template
struct edge_descriptor
{
edge_descriptor(processor_id_type sp = processor_id_type(),
processor_id_type tp = processor_id_type(),
bool owns = false, Edge ld = Edge())
: source_processor(sp), target_processor(tp),
source_owns_edge(owns), local(ld) {}
processor_id_type owner() const
{
return source_owns_edge? source_processor : target_processor;
}
/// The processor that the source vertex resides on
processor_id_type source_processor;
/// The processor that the target vertex resides on
processor_id_type target_processor;
/// True when the source processor owns the edge, false when the
/// target processor owns the edge.
bool source_owns_edge;
/// The local edge descriptor.
Edge local;
/**
* Function object that generates edge descriptors for the
* out_edge_iterator of the given distributed adjacency list
* from the edge descriptors of the underlying adjacency list.
*/
template
class out_generator
{
typedef typename Graph::directed_selector directed_selector;
public:
typedef edge_descriptor result_type;
typedef Edge argument_type;
out_generator() : g(0) {}
explicit out_generator(const Graph& g) : g(&g) {}
result_type operator()(argument_type e) const
{ return map(e, directed_selector()); }
private:
result_type map(argument_type e, directedS) const
{
return result_type(g->processor(),
get(edge_target_processor_id, g->base(), e),
true, e);
}
result_type map(argument_type e, bidirectionalS) const
{
return result_type(g->processor(),
get(edge_target_processor_id, g->base(), e),
true, e);
}
result_type map(argument_type e, undirectedS) const
{
return result_type(g->processor(),
get(edge_target_processor_id, g->base(), e),
get(edge_locally_owned, g->base(), e),
e);
}
const Graph* g;
};
/**
* Function object that generates edge descriptors for the
* in_edge_iterator of the given distributed adjacency list
* from the edge descriptors of the underlying adjacency list.
*/
template
class in_generator
{
typedef typename Graph::directed_selector DirectedS;
public:
typedef typename boost::mpl::if_,
stored_in_edge,
Edge>::type argument_type;
typedef edge_descriptor result_type;
in_generator() : g(0) {}
explicit in_generator(const Graph& g) : g(&g) {}
result_type operator()(argument_type e) const
{ return map(e, DirectedS()); }
private:
/**
* For a bidirectional graph, we just generate the appropriate
* edge. No tricks.
*/
result_type map(argument_type e, bidirectionalS) const
{
return result_type(e.source_processor,
g->processor(),
true,
e.e);
}
/**
* For an undirected graph, we generate descriptors for the
* incoming edges by swapping the source/target of the
* underlying edge descriptor (a hack). The target processor
* ID on the edge is actually the source processor for this
* edge, and our processor is the target processor. If the
* edge is locally owned, then it is owned by the target (us);
* otherwise it is owned by the source.
*/
result_type map(argument_type e, undirectedS) const
{
typename Graph::local_edge_descriptor local_edge(e);
// TBD: This is a very, VERY lame hack that takes advantage
// of our knowledge of the internals of the BGL
// adjacency_list. There should be a cleaner way to handle
// this...
using std::swap;
swap(local_edge.m_source, local_edge.m_target);
return result_type(get(edge_target_processor_id, g->base(), e),
g->processor(),
!get(edge_locally_owned, g->base(), e),
local_edge);
}
const Graph* g;
};
private:
friend class boost::serialization::access;
template
void serialize(Archiver& ar, const unsigned int /*version*/)
{
ar
& source_processor
& target_processor
& source_owns_edge
& local;
}
};
/// Determine the process that owns this edge
template
inline processor_id_type
owner(const edge_descriptor& e)
{ return e.source_owns_edge? e.source_processor : e.target_processor; }
/// Determine the local descriptor for this edge.
template
inline Edge
local(const edge_descriptor& e)
{ return e.local; }
/**
* A Readable Property Map that extracts the owner and local
* descriptor of an edge descriptor.
*/
template
struct edge_global_property_map
{
typedef std::pair value_type;
typedef value_type reference;
typedef edge_descriptor key_type;
typedef readable_property_map_tag category;
};
template
inline std::pair
get(edge_global_property_map, const edge_descriptor& e)
{
typedef std::pair result_type;
return result_type(e.source_owns_edge? e.source_processor
/* target owns edge*/: e.target_processor,
e.local);
}
/**
* A Readable Property Map that extracts the owner of an edge
* descriptor.
*/
template
struct edge_owner_property_map
{
typedef processor_id_type value_type;
typedef value_type reference;
typedef edge_descriptor key_type;
typedef readable_property_map_tag category;
};
template
inline processor_id_type
get(edge_owner_property_map, const edge_descriptor& e)
{
return e.source_owns_edge? e.source_processor : e.target_processor;
}
/**
* A Readable Property Map that extracts the local descriptor from
* an edge descriptor.
*/
template
struct edge_local_property_map
{
typedef Edge value_type;
typedef value_type reference;
typedef edge_descriptor key_type;
typedef readable_property_map_tag category;
};
template
inline Edge
get(edge_local_property_map,
const edge_descriptor& e)
{
return e.local;
}
/** Compare distributed edge descriptors for equality.
*
* \todo need edge_descriptor to know if it is undirected so we
* can compare both ways.
*/
template
inline bool
operator==(const edge_descriptor& e1,
const edge_descriptor& e2)
{
return (e1.source_processor == e2.source_processor
&& e1.target_processor == e2.target_processor
&& e1.local == e2.local);
}
/// Compare distributed edge descriptors for inequality.
template
inline bool
operator!=(const edge_descriptor& e1,
const edge_descriptor& e2)
{ return !(e1 == e2); }
/**
* Configuration for the distributed adjacency list. We use this
* parameter to store all of the configuration details for the
* implementation of the distributed adjacency list, which allows us to
* get at the distribution type in the maybe_named_graph.
*/
template
struct adjacency_list_config
{
typedef typename mpl::if_,
vecS, InVertexListS>::type
VertexListS;
/// Introduce the target processor ID property for each edge
typedef property edge_property_with_id;
/// For undirected graphs, introduce the locally-owned property for edges
typedef typename boost::mpl::if_,
property,
edge_property_with_id>::type
base_edge_property_type;
/// The edge descriptor type for the local subgraph
typedef typename adjacency_list_traits::edge_descriptor
local_edge_descriptor;
/// For bidirectional graphs, the type of an incoming stored edge
typedef stored_in_edge bidir_stored_edge;
/// The container type that will store incoming edges for a
/// bidirectional graph.
typedef typename container_gen::type
in_edge_list_type;
// Bidirectional graphs have an extra vertex property to store
// the incoming edges.
typedef typename boost::mpl::if_,
property,
VertexProperty>::type
base_vertex_property_type;
// The type of the distributed adjacency list
typedef adjacency_list,
DirectedS, VertexProperty, EdgeProperty,
GraphProperty, EdgeListS>
graph_type;
// The type of the underlying adjacency list implementation
typedef adjacency_list
inherited;
typedef InDistribution in_distribution_type;
typedef typename inherited::vertices_size_type vertices_size_type;
typedef typename ::boost::graph::distributed::select_distribution<
in_distribution_type, VertexProperty, vertices_size_type,
ProcessGroup>::type
base_distribution_type;
typedef ::boost::graph::distributed::shuffled_distribution<
base_distribution_type> distribution_type;
typedef VertexProperty vertex_property_type;
typedef EdgeProperty edge_property_type;
typedef ProcessGroup process_group_type;
typedef VertexListS vertex_list_selector;
typedef OutEdgeListS out_edge_list_selector;
typedef DirectedS directed_selector;
typedef GraphProperty graph_property_type;
typedef EdgeListS edge_list_selector;
};
// Maybe initialize the indices of each vertex
template
void
maybe_initialize_vertex_indices(IteratorPair p, VertexIndexMap to_index,
read_write_property_map_tag)
{
typedef typename property_traits::value_type index_t;
index_t next_index = 0;
while (p.first != p.second)
put(to_index, *p.first++, next_index++);
}
template
inline void
maybe_initialize_vertex_indices(IteratorPair p, VertexIndexMap to_index,
readable_property_map_tag)
{
// Do nothing
}
template
inline void
maybe_initialize_vertex_indices(IteratorPair p, VertexIndexMap to_index)
{
typedef typename property_traits::category category;
maybe_initialize_vertex_indices(p, to_index, category());
}
template
inline void
maybe_initialize_vertex_indices(IteratorPair p,
::boost::detail::error_property_not_found)
{ }
/***********************************************************************
* Message Payloads *
***********************************************************************/
/**
* Data stored with a msg_add_edge message, which requests the
* remote addition of an edge.
*/
template
struct msg_add_edge_data
{
msg_add_edge_data() { }
msg_add_edge_data(Vertex source, Vertex target)
: source(source.local), target(target) { }
/// The source of the edge; the processor will be the
/// receiving processor.
LocalVertex source;
/// The target of the edge.
Vertex target;
template
void serialize(Archiver& ar, const unsigned int /*version*/)
{
ar & unsafe_serialize(source) & target;
}
};
/**
* Like @c msg_add_edge_data, but also includes a user-specified
* property value to be attached to the edge.
*/
template
struct msg_add_edge_with_property_data
: msg_add_edge_data,
maybe_store_property
{
private:
typedef msg_add_edge_data inherited_data;
typedef maybe_store_property inherited_property;
public:
msg_add_edge_with_property_data() { }
msg_add_edge_with_property_data(Vertex source,
Vertex target,
const EdgeProperty& property)
: inherited_data(source, target),
inherited_property(property) { }
template
void serialize(Archiver& ar, const unsigned int /*version*/)
{
ar & boost::serialization::base_object(*this)
& boost::serialization::base_object(*this);
}
};
//------------------------------------------------------------------------
// Distributed adjacency list property map details
/**
* Metafunction that extracts the given property from the given
* distributed adjacency list type. This could be implemented much
* more cleanly, but even newer versions of GCC (e.g., 3.2.3)
* cannot properly handle partial specializations involving
* enumerator types.
*/
template
struct get_adj_list_pmap
{
template
struct apply
{
typedef Graph graph_type;
typedef typename graph_type::process_group_type process_group_type;
typedef typename graph_type::inherited base_graph_type;
typedef typename property_map::type
local_pmap;
typedef typename property_map::const_type
local_const_pmap;
typedef graph_traits traits;
typedef typename graph_type::local_vertex_descriptor local_vertex;
typedef typename property_traits::key_type local_key_type;
typedef typename property_traits::value_type value_type;
typedef typename property_map::const_type
vertex_global_map;
typedef typename property_map::const_type
edge_global_map;
typedef typename mpl::if_c<(is_same::value),
vertex_global_map, edge_global_map>::type
global_map;
public:
typedef ::boost::parallel::distributed_property_map<
process_group_type, global_map, local_pmap> type;
typedef ::boost::parallel::distributed_property_map<
process_group_type, global_map, local_const_pmap> const_type;
};
};
/**
* The local vertex index property map is actually a mapping from
* the local vertex descriptors to vertex indices.
*/
template<>
struct get_adj_list_pmap
{
template
struct apply
: ::boost::property_map
{ };
};
/**
* The vertex index property map maps from global descriptors
* (e.g., the vertex descriptor of a distributed adjacency list)
* to the underlying local index. It is not valid to use this
* property map with nonlocal descriptors.
*/
template<>
struct get_adj_list_pmap
{
template
struct apply
{
private:
typedef typename property_map::const_type
global_map;
typedef property_map local;
public:
typedef local_property_map type;
typedef local_property_map const_type;
};
};
/**
* The vertex owner property map maps from vertex descriptors to
* the processor that owns the vertex.
*/
template<>
struct get_adj_list_pmap
{
template
struct apply
{
private:
typedef typename Graph::local_vertex_descriptor
local_vertex_descriptor;
public:
typedef global_descriptor_property_map type;
typedef type const_type;
};
};
/**
* The vertex owner property map maps from vertex descriptors to
* the processor that owns the vertex.
*/
template<>
struct get_adj_list_pmap
{
template
struct apply
{
private:
typedef typename Graph::local_vertex_descriptor
local_vertex_descriptor;
public:
typedef owner_property_map type;
typedef type const_type;
};
};
/**
* The vertex local property map maps from vertex descriptors to
* the local descriptor for that vertex.
*/
template<>
struct get_adj_list_pmap
{
template
struct apply
{
private:
typedef typename Graph::local_vertex_descriptor
local_vertex_descriptor;
public:
typedef local_descriptor_property_map type;
typedef type const_type;
};
};
/**
* The edge global property map maps from edge descriptors to
* a pair of the owning processor and local descriptor.
*/
template<>
struct get_adj_list_pmap
{
template
struct apply
{
private:
typedef typename Graph::local_edge_descriptor
local_edge_descriptor;
public:
typedef edge_global_property_map type;
typedef type const_type;
};
};
/**
* The edge owner property map maps from edge descriptors to
* the processor that owns the edge.
*/
template<>
struct get_adj_list_pmap
{
template
struct apply
{
private:
typedef typename Graph::local_edge_descriptor
local_edge_descriptor;
public:
typedef edge_owner_property_map type;
typedef type const_type;
};
};
/**
* The edge local property map maps from edge descriptors to
* the local descriptor for that edge.
*/
template<>
struct get_adj_list_pmap
{
template
struct apply
{
private:
typedef typename Graph::local_edge_descriptor
local_edge_descriptor;
public:
typedef edge_local_property_map type;
typedef type const_type;
};
};
//------------------------------------------------------------------------
// Directed graphs do not have in edges, so this is a no-op
template
inline void
remove_in_edge(typename Graph::edge_descriptor, Graph&, directedS)
{ }
// Bidirectional graphs have in edges stored in the
// vertex_in_edges property.
template
inline void
remove_in_edge(typename Graph::edge_descriptor e, Graph& g, bidirectionalS)
{
typedef typename Graph::in_edge_list_type in_edge_list_type;
in_edge_list_type& in_edges =
get(vertex_in_edges, g.base())[target(e, g).local];
typename in_edge_list_type::iterator i = in_edges.begin();
while (i != in_edges.end()
&& !(i->source_processor == source(e, g).owner)
&& i->e == e.local)
++i;
BOOST_ASSERT(i != in_edges.end());
in_edges.erase(i);
}
// Undirected graphs have in edges stored as normal edges.
template
inline void
remove_in_edge(typename Graph::edge_descriptor e, Graph& g, undirectedS)
{
typedef typename Graph::inherited base_type;
typedef typename graph_traits::vertex_descriptor vertex_descriptor;
// TBD: can we make this more efficient?
// Removing edge (v, u). v is local
base_type& bg = g.base();
vertex_descriptor u = source(e, g);
vertex_descriptor v = target(e, g);
if (v.owner != process_id(g.process_group())) {
using std::swap;
swap(u, v);
}
typename graph_traits::out_edge_iterator ei, ei_end;
for (boost::tie(ei, ei_end) = out_edges(v.local, bg); ei != ei_end; ++ei)
{
if (target(*ei, g.base()) == u.local
// TBD: deal with parallel edges properly && *ei == e
&& get(edge_target_processor_id, bg, *ei) == u.owner) {
remove_edge(ei, bg);
return;
}
}
if (v.owner == process_id(g.process_group())) {
}
}
//------------------------------------------------------------------------
// Lazy addition of edges
// Work around the fact that an adjacency_list with vecS vertex
// storage automatically adds edges when the descriptor is
// out-of-range.
template
inline std::pair
add_local_edge(typename Config::vertex_descriptor u,
typename Config::vertex_descriptor v,
const typename Config::edge_property_type& p,
vec_adj_list_impl& g_)
{
adj_list_helper& g = g_;
return add_edge(u, v, p, g);
}
template
inline std::pair
add_local_edge(typename Config::vertex_descriptor u,
typename Config::vertex_descriptor v,
const typename Config::edge_property_type& p,
boost::adj_list_impl& g)
{
return add_edge(u, v, p, g);
}
template
struct msg_nonlocal_edge_data
: public detail::parallel::maybe_store_property
{
typedef EdgeProperty edge_property_type;
typedef EdgeDescriptor local_edge_descriptor;
typedef detail::parallel::maybe_store_property
inherited;
msg_nonlocal_edge_data() {}
msg_nonlocal_edge_data(local_edge_descriptor e,
const edge_property_type& p)
: inherited(p), e(e) { }
local_edge_descriptor e;
template
void serialize(Archiver& ar, const unsigned int /*version*/)
{
ar & boost::serialization::base_object(*this) & e;
}
};
template
struct msg_remove_edge_data
{
typedef EdgeDescriptor edge_descriptor;
msg_remove_edge_data() {}
explicit msg_remove_edge_data(edge_descriptor e) : e(e) {}
edge_descriptor e;
template
void serialize(Archiver& ar, const unsigned int /*version*/)
{
ar & e;
}
};
} } // end namespace detail::parallel
/**
* Adjacency list traits for a distributed adjacency list. Contains
* the vertex and edge descriptors, the directed-ness, and the
* parallel edges typedefs.
*/
template
struct adjacency_list_traits,
DirectedS>
{
private:
typedef typename mpl::if_,
vecS,
InVertexListS>::type VertexListS;
typedef adjacency_list_traits
base_type;
public:
typedef typename base_type::vertex_descriptor local_vertex_descriptor;
typedef typename base_type::edge_descriptor local_edge_descriptor;
typedef typename boost::mpl::if_::type
>::type directed_category;
typedef typename parallel_edge_traits::type
edge_parallel_category;
typedef detail::parallel::global_descriptor
vertex_descriptor;
typedef detail::parallel::edge_descriptor
edge_descriptor;
};
#define PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS \
typename OutEdgeListS, typename ProcessGroup, typename InVertexListS, \
typename InDistribution, typename DirectedS, typename VertexProperty, \
typename EdgeProperty, typename GraphProperty, typename EdgeListS
#define PBGL_DISTRIB_ADJLIST_TYPE \
adjacency_list, \
DirectedS, VertexProperty, EdgeProperty, GraphProperty, \
EdgeListS>
#define PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG \
typename OutEdgeListS, typename ProcessGroup, typename InVertexListS, \
typename InDistribution, typename VertexProperty, \
typename EdgeProperty, typename GraphProperty, typename EdgeListS
#define PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directed) \
adjacency_list, \
directed, 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 @c v, no other processor can
* directly access the properties of @c 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 @c distributedS. 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 @c
* add_vertex and @c add_edge operations add vertices or edges
* stored on the local processor. For @c add_edge, this is
* accomplished by requiring that the source vertex of the new edge
* be local to the process executing @c 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
* @ref 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 @ref 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 @c 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 @c property_reduce doesn't do the
* right thing?
*/
template
class adjacency_list,
DirectedS, VertexProperty,
EdgeProperty, GraphProperty, EdgeListS>
: // Support for named vertices
public graph::distributed::maybe_named_graph<
adjacency_list,
DirectedS, VertexProperty,
EdgeProperty, GraphProperty, EdgeListS>,
typename adjacency_list_traits,
DirectedS>::vertex_descriptor,
typename adjacency_list_traits,
DirectedS>::edge_descriptor,
detail::parallel::adjacency_list_config >
{
typedef detail::parallel::adjacency_list_config
config_type;
typedef adjacency_list_traits,
DirectedS>
traits_type;
typedef typename DirectedS::is_directed_t is_directed;
typedef EdgeListS edge_list_selector;
public:
/// The container type that will store incoming edges for a
/// bidirectional graph.
typedef typename config_type::in_edge_list_type in_edge_list_type;
// typedef typename inherited::edge_descriptor edge_descriptor;
/// The type of the underlying adjacency list implementation
typedef typename config_type::inherited inherited;
/// The type of properties stored in the local subgraph
/// Bidirectional graphs have an extra vertex property to store
/// the incoming edges.
typedef typename inherited::vertex_property_type
base_vertex_property_type;
/// The type of the distributed adjacency list (this type)
typedef typename config_type::graph_type graph_type;
/// Expose graph components and graph category
typedef typename traits_type::local_vertex_descriptor
local_vertex_descriptor;
typedef typename traits_type::local_edge_descriptor
local_edge_descriptor;
typedef typename traits_type::vertex_descriptor vertex_descriptor;
typedef typename traits_type::edge_descriptor edge_descriptor;
typedef typename traits_type::directed_category directed_category;
typedef typename inherited::edge_parallel_category
edge_parallel_category;
typedef typename inherited::graph_tag graph_tag;
// Current implementation requires the ability to have parallel
// edges in the underlying adjacency_list. Which processor each
// edge refers to is attached as an internal property. TBD:
// remove this restriction, which may require some rewriting.
BOOST_STATIC_ASSERT((is_same::value));
/** Determine the graph traversal category.
*
* A directed distributed adjacency list models the Distributed
* Graph, Incidence Graph, and Adjacency Graph
* concepts. Bidirectional and undirected graphs also model the
* Bidirectional Graph concept. Note that when modeling these
* concepts the domains of certain operations (e.g., in_edges)
* are restricted; see the distributed adjacency_list
* documentation.
*/
typedef typename boost::mpl::if_<
is_same,
directed_distributed_adj_list_tag,
typename boost::mpl::if_,
bidirectional_distributed_adj_list_tag,
undirected_distributed_adj_list_tag>::type>
::type traversal_category;
typedef typename inherited::degree_size_type degree_size_type;
typedef typename inherited::vertices_size_type vertices_size_type;
typedef typename inherited::edges_size_type edges_size_type;
typedef VertexProperty vertex_property_type;
typedef EdgeProperty edge_property_type;
typedef typename inherited::graph_property_type graph_property_type;
typedef typename inherited::vertex_bundled vertex_bundled;
typedef typename inherited::edge_bundled edge_bundled;
typedef typename inherited::graph_bundled graph_bundled;
typedef typename container_gen::type
local_edge_list_type;
private:
typedef typename boost::mpl::if_,
typename in_edge_list_type::const_iterator,
typename inherited::out_edge_iterator>::type
base_in_edge_iterator;
typedef typename inherited::out_edge_iterator base_out_edge_iterator;
typedef typename graph_traits::edge_iterator
base_edge_iterator;
typedef typename inherited::edge_property_type base_edge_property_type;
typedef typename local_edge_list_type::const_iterator
undirected_edge_iterator;
typedef InDistribution in_distribution_type;
typedef parallel::trigger_receive_context trigger_receive_context;
public:
/// Iterator over the (local) vertices of the graph
typedef transform_iterator
vertex_iterator;
/// Helper for out_edge_iterator
typedef typename edge_descriptor::template out_generator
out_edge_generator;
/// Iterator over the outgoing edges of a vertex
typedef transform_iterator
out_edge_iterator;
/// Helper for in_edge_iterator
typedef typename edge_descriptor::template in_generator
in_edge_generator;
/// Iterator over the incoming edges of a vertex
typedef transform_iterator
in_edge_iterator;
/// Iterator over the neighbors of a vertex
typedef boost::adjacency_iterator<
adjacency_list, vertex_descriptor, out_edge_iterator,
typename std::iterator_traits
::difference_type>
adjacency_iterator;
/// Iterator over the (local) edges in a graph
typedef typename boost::mpl::if_,
undirected_edge_iterator,
transform_iterator
>::type
edge_iterator;
public:
/// The type of the mixin for named vertices
typedef graph::distributed::maybe_named_graph
named_graph_mixin;
/// Process group used for communication
typedef ProcessGroup process_group_type;
/// How to refer to a process
typedef typename process_group_type::process_id_type process_id_type;
/// Whether this graph is directed, undirected, or bidirectional
typedef DirectedS directed_selector;
// Structure used for the lazy addition of vertices
struct lazy_add_vertex_with_property;
friend struct lazy_add_vertex_with_property;
// Structure used for the lazy addition of edges
struct lazy_add_edge;
friend struct lazy_add_edge;
// Structure used for the lazy addition of edges with properties
struct lazy_add_edge_with_property;
friend struct lazy_add_edge_with_property;
/// default_distribution_type is the type of the distribution used if the
/// user didn't specify an explicit one
typedef typename graph::distributed::select_distribution<
InDistribution, VertexProperty, vertices_size_type,
ProcessGroup>::default_type
default_distribution_type;
/// distribution_type is the type of the distribution instance stored in
/// the maybe_named_graph base class
typedef typename graph::distributed::select_distribution<
InDistribution, VertexProperty, vertices_size_type,
ProcessGroup>::type
base_distribution_type;
typedef graph::distributed::shuffled_distribution<
base_distribution_type> distribution_type;
private:
// FIXME: the original adjacency_list contained this comment:
// Default copy constructor and copy assignment operators OK??? TBD
// but the adj_list_impl contained these declarations:
adjacency_list(const adjacency_list& other);
adjacency_list& operator=(const adjacency_list& other);
public:
adjacency_list(const ProcessGroup& pg = ProcessGroup())
: named_graph_mixin(pg, default_distribution_type(pg, 0)),
m_local_graph(GraphProperty()),
process_group_(pg, boost::parallel::attach_distributed_object())
{
setup_triggers();
}
adjacency_list(const ProcessGroup& pg,
const base_distribution_type& distribution)
: named_graph_mixin(pg, distribution),
m_local_graph(GraphProperty()),
process_group_(pg, boost::parallel::attach_distributed_object())
{
setup_triggers();
}
adjacency_list(const GraphProperty& g,
const ProcessGroup& pg = ProcessGroup())
: named_graph_mixin(pg, default_distribution_type(pg, 0)),
m_local_graph(g),
process_group_(pg, boost::parallel::attach_distributed_object())
{
setup_triggers();
}
adjacency_list(vertices_size_type n,
const GraphProperty& p,
const ProcessGroup& pg,
const base_distribution_type& distribution)
: named_graph_mixin(pg, distribution),
m_local_graph(distribution.block_size(process_id(pg), n), p),
process_group_(pg, boost::parallel::attach_distributed_object())
{
setup_triggers();
detail::parallel::maybe_initialize_vertex_indices(vertices(base()),
get(vertex_index, base()));
}
adjacency_list(vertices_size_type n,
const ProcessGroup& pg,
const base_distribution_type& distribution)
: named_graph_mixin(pg, distribution),
m_local_graph(distribution.block_size(process_id(pg), n), GraphProperty()),
process_group_(pg, boost::parallel::attach_distributed_object())
{
setup_triggers();
detail::parallel::maybe_initialize_vertex_indices(vertices(base()),
get(vertex_index, base()));
}
adjacency_list(vertices_size_type n,
const GraphProperty& p,
const ProcessGroup& pg = ProcessGroup())
: named_graph_mixin(pg, default_distribution_type(pg, n)),
m_local_graph(this->distribution().block_size(process_id(pg), n), p),
process_group_(pg, boost::parallel::attach_distributed_object())
{
setup_triggers();
detail::parallel::maybe_initialize_vertex_indices(vertices(base()),
get(vertex_index, base()));
}
adjacency_list(vertices_size_type n,
const ProcessGroup& pg = ProcessGroup())
: named_graph_mixin(pg, default_distribution_type(pg, n)),
m_local_graph(this->distribution().block_size(process_id(pg), n),
GraphProperty()),
process_group_(pg, boost::parallel::attach_distributed_object())
{
setup_triggers();
detail::parallel::maybe_initialize_vertex_indices(vertices(base()),
get(vertex_index, base()));
}
/*
* We assume that every processor sees the same list of edges, so
* they skip over any that don't originate from themselves. This
* means that programs switching between a local and a distributed
* graph will keep the same semantics.
*/
template
adjacency_list(EdgeIterator first, EdgeIterator last,
vertices_size_type n,
const ProcessGroup& pg = ProcessGroup(),
const GraphProperty& p = GraphProperty())
: named_graph_mixin(pg, default_distribution_type(pg, n)),
m_local_graph(this->distribution().block_size(process_id(pg), n), p),
process_group_(pg, boost::parallel::attach_distributed_object())
{
setup_triggers();
typedef typename config_type::VertexListS vertex_list_selector;
initialize(first, last, n, this->distribution(), vertex_list_selector());
detail::parallel::maybe_initialize_vertex_indices(vertices(base()),
get(vertex_index, base()));
}
template
adjacency_list(EdgeIterator first, EdgeIterator last,
EdgePropertyIterator ep_iter,
vertices_size_type n,
const ProcessGroup& pg = ProcessGroup(),
const GraphProperty& p = GraphProperty())
: named_graph_mixin(pg, default_distribution_type(pg, n)),
m_local_graph(this->distribution().block_size(process_id(pg), n), p),
process_group_(pg, boost::parallel::attach_distributed_object())
{
setup_triggers();
typedef typename config_type::VertexListS vertex_list_selector;
initialize(first, last, ep_iter, n, this->distribution(),
vertex_list_selector());
detail::parallel::maybe_initialize_vertex_indices(vertices(base()),
get(vertex_index, base()));
}
template
adjacency_list(EdgeIterator first, EdgeIterator last,
vertices_size_type n,
const ProcessGroup& pg,
const base_distribution_type& distribution,
const GraphProperty& p = GraphProperty())
: named_graph_mixin(pg, distribution),
m_local_graph(distribution.block_size(process_id(pg), n), p),
process_group_(pg, boost::parallel::attach_distributed_object())
{
setup_triggers();
typedef typename config_type::VertexListS vertex_list_selector;
initialize(first, last, n, this->distribution(), vertex_list_selector());
detail::parallel::maybe_initialize_vertex_indices(vertices(base()),
get(vertex_index, base()));
}
template
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())
: named_graph_mixin(pg, distribution),
m_local_graph(this->distribution().block_size(process_id(pg), n), p),
process_group_(pg, boost::parallel::attach_distributed_object())
{
setup_triggers();
typedef typename config_type::VertexListS vertex_list_selector;
initialize(first, last, ep_iter, n, distribution,
vertex_list_selector());
detail::parallel::maybe_initialize_vertex_indices(vertices(base()),
get(vertex_index, base()));
}
~adjacency_list()
{
synchronize(process_group_);
}
void clear()
{
base().clear();
local_edges_.clear();
named_graph_mixin::clearing_graph();
}
void swap(adjacency_list& other)
{
using std::swap;
base().swap(other);
swap(process_group_, other.process_group_);
}
static vertex_descriptor null_vertex()
{
return vertex_descriptor(processor_id_type(0),
inherited::null_vertex());
}
inherited& base() { return m_local_graph; }
const inherited& base() const { return m_local_graph; }
processor_id_type processor() const { return process_id(process_group_); }
process_group_type process_group() const { return process_group_.base(); }
local_edge_list_type& local_edges() { return local_edges_; }
const local_edge_list_type& local_edges() const { return local_edges_; }
// Redistribute the vertices of the graph by placing each vertex
// v on the processor get(vertex_to_processor, v).
template
void redistribute(VertexProcessorMap vertex_to_processor);
// Directly access a vertex or edge bundle
vertex_bundled& operator[](vertex_descriptor v)
{
BOOST_ASSERT(v.owner == processor());
return base()[v.local];
}
const vertex_bundled& operator[](vertex_descriptor v) const
{
BOOST_ASSERT(v.owner == processor());
return base()[v.local];
}
edge_bundled& operator[](edge_descriptor e)
{
BOOST_ASSERT(e.owner() == processor());
return base()[e.local];
}
const edge_bundled& operator[](edge_descriptor e) const
{
BOOST_ASSERT(e.owner() == processor());
return base()[e.local];
}
graph_bundled& operator[](graph_bundle_t)
{ return get_property(*this); }
graph_bundled const& operator[](graph_bundle_t) const
{ return get_property(*this); }
template
void save(std::string const& filename) const;
template
void load(std::string const& filename);
// Callback that will be invoked whenever a new vertex is added locally
boost::function on_add_vertex;
// Callback that will be invoked whenever a new edge is added locally
boost::function on_add_edge;
private:
// Request vertex->processor mapping for neighbors
template
void
request_in_neighbors(vertex_descriptor,
VertexProcessorMap,
directedS) { }
// Request vertex->processor mapping for neighbors
template
void
request_in_neighbors(vertex_descriptor,
VertexProcessorMap,
undirectedS) { }
// Request vertex->processor mapping for neighbors
template
void
request_in_neighbors(vertex_descriptor v,
VertexProcessorMap vertex_to_processor,
bidirectionalS);
// Clear the list of in-edges, but don't tell the remote processor
void clear_in_edges_local(vertex_descriptor v, directedS) {}
void clear_in_edges_local(vertex_descriptor v, undirectedS) {}
void clear_in_edges_local(vertex_descriptor v, bidirectionalS)
{ get(vertex_in_edges, base())[v.local].clear(); }
// Remove in-edges that have migrated
template
void
remove_migrated_in_edges(vertex_descriptor,
VertexProcessorMap,
directedS) { }
// Remove in-edges that have migrated
template