// Copyright (C) 2007 Douglas Gregor
|
// Copyright (C) 2007 Hartmut Kaiser
|
|
// 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)
|
|
// TODO:
|
// - Cache (some) remote vertex names?
|
#ifndef BOOST_GRAPH_DISTRIBUTED_NAMED_GRAPH_HPP
|
#define BOOST_GRAPH_DISTRIBUTED_NAMED_GRAPH_HPP
|
|
#ifndef BOOST_GRAPH_USE_MPI
|
#error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
|
#endif
|
|
#include <boost/assert.hpp>
|
#include <boost/graph/named_graph.hpp>
|
#include <boost/functional/hash.hpp>
|
#include <boost/variant.hpp>
|
#include <boost/graph/parallel/simple_trigger.hpp>
|
#include <boost/graph/parallel/process_group.hpp>
|
#include <boost/graph/parallel/detail/property_holders.hpp>
|
|
namespace boost { namespace graph { namespace distributed {
|
|
using boost::parallel::trigger_receive_context;
|
using boost::detail::parallel::pair_with_property;
|
|
/*******************************************************************
|
* Hashed distribution of named entities *
|
*******************************************************************/
|
|
template<typename T>
|
struct hashed_distribution
|
{
|
template<typename ProcessGroup>
|
hashed_distribution(const ProcessGroup& pg, std::size_t /*num_vertices*/ = 0)
|
: n(num_processes(pg)) { }
|
|
int operator()(const T& value) const
|
{
|
return hasher(value) % n;
|
}
|
|
std::size_t n;
|
hash<T> hasher;
|
};
|
|
/// Specialization for named graphs
|
template <typename InDistribution, typename VertexProperty, typename VertexSize,
|
typename ProcessGroup,
|
typename ExtractName
|
= typename internal_vertex_name<VertexProperty>::type>
|
struct select_distribution
|
{
|
private:
|
/// The type used to name vertices in the graph
|
typedef typename remove_cv<
|
typename remove_reference<
|
typename ExtractName::result_type>::type>::type
|
vertex_name_type;
|
|
public:
|
/**
|
* The @c type field provides a distribution object that maps
|
* vertex names to processors. The distribution object will be
|
* constructed with the process group over which communication will
|
* occur. The distribution object shall also be a function
|
* object mapping from the type of the name to a processor number
|
* in @c [0, @c p) (for @c p processors). By default, the mapping
|
* function uses the @c boost::hash value of the name, modulo @c p.
|
*/
|
typedef typename mpl::if_<is_same<InDistribution, defaultS>,
|
hashed_distribution<vertex_name_type>,
|
InDistribution>::type
|
type;
|
|
/// for named graphs the default type is the same as the stored distribution
|
/// type
|
typedef type default_type;
|
};
|
|
/// Specialization for non-named graphs
|
template <typename InDistribution, typename VertexProperty, typename VertexSize,
|
typename ProcessGroup>
|
struct select_distribution<InDistribution, VertexProperty, VertexSize,
|
ProcessGroup, void>
|
{
|
/// the distribution type stored in the graph for non-named graphs should be
|
/// the variant_distribution type
|
typedef typename mpl::if_<is_same<InDistribution, defaultS>,
|
boost::parallel::variant_distribution<ProcessGroup,
|
VertexSize>,
|
InDistribution>::type type;
|
|
/// default_type is used as the distribution functor for the
|
/// adjacency_list, it should be parallel::block by default
|
typedef typename mpl::if_<is_same<InDistribution, defaultS>,
|
boost::parallel::block, type>::type
|
default_type;
|
};
|
|
|
/*******************************************************************
|
* Named graph mixin *
|
*******************************************************************/
|
|
/**
|
* named_graph is a mixin that provides names for the vertices of a
|
* graph, including a mapping from names to vertices. Graph types that
|
* may or may not be have vertex names (depending on the properties
|
* supplied by the user) should use maybe_named_graph.
|
*
|
* Template parameters:
|
*
|
* Graph: the graph type that derives from named_graph
|
*
|
* Vertex: the type of a vertex descriptor in Graph. Note: we cannot
|
* use graph_traits here, because the Graph is not yet defined.
|
*
|
* VertexProperty: the type of the property stored along with the
|
* vertex.
|
*
|
* ProcessGroup: the process group over which the distributed name
|
* graph mixin will communicate.
|
*/
|
template<typename Graph, typename Vertex, typename Edge, typename Config>
|
class named_graph
|
{
|
public:
|
/// Messages passed within the distributed named graph
|
enum message_kind {
|
/**
|
* Requests the addition of a vertex on a remote processor. The
|
* message data is a @c vertex_name_type.
|
*/
|
msg_add_vertex_name,
|
|
/**
|
* Requests the addition of a vertex on a remote processor. The
|
* message data is a @c vertex_name_type. The remote processor
|
* will send back a @c msg_add_vertex_name_reply message
|
* containing the vertex descriptor.
|
*/
|
msg_add_vertex_name_with_reply,
|
|
/**
|
* Requests the vertex descriptor corresponding to the given
|
* vertex name. The remote process will reply with a
|
* @c msg_find_vertex_reply message containing the answer.
|
*/
|
msg_find_vertex,
|
|
/**
|
* Requests the addition of an edge on a remote processor. The
|
* data stored in these messages is a @c pair<source, target>@,
|
* where @c source and @c target may be either names (of type @c
|
* vertex_name_type) or vertex descriptors, depending on what
|
* information we have locally.
|
*/
|
msg_add_edge_name_name,
|
msg_add_edge_vertex_name,
|
msg_add_edge_name_vertex,
|
|
/**
|
* These messages are identical to msg_add_edge_*_*, except that
|
* the process actually adding the edge will send back a @c
|
* pair<edge_descriptor,bool>
|
*/
|
msg_add_edge_name_name_with_reply,
|
msg_add_edge_vertex_name_with_reply,
|
msg_add_edge_name_vertex_with_reply,
|
|
/**
|
* Requests the addition of an edge with a property on a remote
|
* processor. The data stored in these messages is a @c
|
* pair<vertex_property_type, pair<source, target>>@, where @c
|
* source and @c target may be either names (of type @c
|
* vertex_name_type) or vertex descriptors, depending on what
|
* information we have locally.
|
*/
|
msg_add_edge_name_name_with_property,
|
msg_add_edge_vertex_name_with_property,
|
msg_add_edge_name_vertex_with_property,
|
|
/**
|
* These messages are identical to msg_add_edge_*_*_with_property,
|
* except that the process actually adding the edge will send back
|
* a @c pair<edge_descriptor,bool>.
|
*/
|
msg_add_edge_name_name_with_reply_and_property,
|
msg_add_edge_vertex_name_with_reply_and_property,
|
msg_add_edge_name_vertex_with_reply_and_property
|
};
|
|
/// The vertex descriptor type
|
typedef Vertex vertex_descriptor;
|
|
/// The edge descriptor type
|
typedef Edge edge_descriptor;
|
|
/// The vertex property type
|
typedef typename Config::vertex_property_type vertex_property_type;
|
|
/// The vertex property type
|
typedef typename Config::edge_property_type edge_property_type;
|
|
/// The type used to extract names from the property structure
|
typedef typename internal_vertex_name<vertex_property_type>::type
|
extract_name_type;
|
|
/// The type used to name vertices in the graph
|
typedef typename remove_cv<
|
typename remove_reference<
|
typename extract_name_type::result_type>::type>::type
|
vertex_name_type;
|
|
/// The type used to distribute named vertices in the graph
|
typedef typename Config::distribution_type distribution_type;
|
typedef typename Config::base_distribution_type base_distribution_type;
|
|
/// The type used for communication in the distributed structure
|
typedef typename Config::process_group_type process_group_type;
|
|
/// Type used to identify processes
|
typedef typename process_group_type::process_id_type process_id_type;
|
|
/// a reference to this class, which is used for disambiguation of the
|
// add_vertex function
|
typedef named_graph named_graph_type;
|
|
/// Structure returned when adding a vertex by vertex name
|
struct lazy_add_vertex;
|
friend struct lazy_add_vertex;
|
|
/// Structure returned when adding an edge by vertex name
|
struct lazy_add_edge;
|
friend struct lazy_add_edge;
|
|
/// Structure returned when adding an edge by vertex name with a property
|
struct lazy_add_edge_with_property;
|
friend struct lazy_add_edge_with_property;
|
|
explicit named_graph(const process_group_type& pg);
|
|
named_graph(const process_group_type& pg, const base_distribution_type& distribution);
|
|
/// Set up triggers, but only for the BSP process group
|
void setup_triggers();
|
|
/// Retrieve the derived instance
|
Graph& derived() { return static_cast<Graph&>(*this); }
|
const Graph& derived() const { return static_cast<const Graph&>(*this); }
|
|
/// Retrieve the process group
|
process_group_type& process_group() { return process_group_; }
|
const process_group_type& process_group() const { return process_group_; }
|
|
// Retrieve the named distribution
|
distribution_type& named_distribution() { return distribution_; }
|
const distribution_type& named_distribution() const { return distribution_; }
|
|
/// Notify the named_graph that we have added the given vertex. This
|
/// is a no-op.
|
void added_vertex(Vertex) { }
|
|
/// Notify the named_graph that we are removing the given
|
/// vertex. This is a no-op.
|
template <typename VertexIterStability>
|
void removing_vertex(Vertex, VertexIterStability) { }
|
|
/// Notify the named_graph that we are clearing the graph
|
void clearing_graph() { }
|
|
/// Retrieve the owner of a given vertex based on the properties
|
/// associated with that vertex. This operation just returns the
|
/// number of the local processor, adding all vertices locally.
|
process_id_type owner_by_property(const vertex_property_type&);
|
|
protected:
|
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);
|
|
template<typename U, typename V>
|
void handle_add_edge(int source, int tag, const boost::parallel::detail::untracked_pair<U, V>& msg,
|
trigger_receive_context);
|
|
template<typename U, typename V>
|
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);
|
|
template<typename U, typename V>
|
void
|
handle_add_edge_with_property
|
(int source, int tag,
|
const pair_with_property<U, V, edge_property_type>& msg,
|
trigger_receive_context);
|
|
template<typename U, typename V>
|
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);
|
|
/// The process group for this distributed data structure
|
process_group_type process_group_;
|
|
/// The distribution we will use to map names to processors
|
distribution_type distribution_;
|
};
|
|
/// Helper macro containing the template parameters of named_graph
|
#define BGL_NAMED_GRAPH_PARAMS \
|
typename Graph, typename Vertex, typename Edge, typename Config
|
/// Helper macro containing the named_graph<...> instantiation
|
#define BGL_NAMED_GRAPH \
|
named_graph<Graph, Vertex, Edge, Config>
|
|
/**
|
* Data structure returned from add_vertex that will "lazily" add the
|
* vertex, either when it is converted to a @c vertex_descriptor or
|
* when the most recent copy has been destroyed.
|
*/
|
template<BGL_NAMED_GRAPH_PARAMS>
|
struct BGL_NAMED_GRAPH::lazy_add_vertex
|
{
|
/// Construct a new lazyily-added vertex
|
lazy_add_vertex(named_graph& self, const vertex_name_type& name)
|
: self(self), name(name), committed(false) { }
|
|
/// Transfer responsibility for adding the vertex from the source of
|
/// the copy to the newly-constructed opbject.
|
lazy_add_vertex(const lazy_add_vertex& other)
|
: self(other.self), name(other.name), committed(other.committed)
|
{
|
other.committed = true;
|
}
|
|
/// If the vertex has not been added yet, add it
|
~lazy_add_vertex();
|
|
/// Add the vertex and return its descriptor. This conversion can
|
/// only occur once, and only when this object is responsible for
|
/// creating the vertex.
|
operator vertex_descriptor() const { return commit(); }
|
|
/// Add the vertex and return its descriptor. This can only be
|
/// called once, and only when this object is responsible for
|
/// creating the vertex.
|
vertex_descriptor commit() const;
|
|
protected:
|
named_graph& self;
|
vertex_name_type name;
|
mutable bool committed;
|
};
|
|
template<BGL_NAMED_GRAPH_PARAMS>
|
BGL_NAMED_GRAPH::lazy_add_vertex::~lazy_add_vertex()
|
{
|
typedef typename BGL_NAMED_GRAPH::process_id_type process_id_type;
|
|
/// If this vertex has already been created or will be created by
|
/// someone else, or if someone threw an exception, we will not
|
/// create the vertex now.
|
if (committed || std::uncaught_exception())
|
return;
|
|
committed = true;
|
|
process_id_type owner = self.named_distribution()(name);
|
if (owner == process_id(self.process_group()))
|
/// Add the vertex locally
|
add_vertex(self.derived().base().vertex_constructor(name), self.derived());
|
else
|
/// Ask the owner of the vertex to add a vertex with this name
|
send(self.process_group(), owner, msg_add_vertex_name, name);
|
}
|
|
template<BGL_NAMED_GRAPH_PARAMS>
|
typename BGL_NAMED_GRAPH::vertex_descriptor
|
BGL_NAMED_GRAPH::lazy_add_vertex::commit() const
|
{
|
typedef typename BGL_NAMED_GRAPH::process_id_type process_id_type;
|
BOOST_ASSERT (!committed);
|
committed = true;
|
|
process_id_type owner = self.named_distribution()(name);
|
if (owner == process_id(self.process_group()))
|
/// Add the vertex locally
|
return add_vertex(self.derived().base().vertex_constructor(name),
|
self.derived());
|
else {
|
/// Ask the owner of the vertex to add a vertex with this name
|
vertex_descriptor result;
|
send_oob_with_reply(self.process_group(), owner,
|
msg_add_vertex_name_with_reply, name, result);
|
return result;
|
}
|
}
|
|
/**
|
* Data structure returned from add_edge that will "lazily" add the
|
* edge, either when it is converted to a @c
|
* pair<edge_descriptor,bool> or when the most recent copy has been
|
* destroyed.
|
*/
|
template<BGL_NAMED_GRAPH_PARAMS>
|
struct BGL_NAMED_GRAPH::lazy_add_edge
|
{
|
/// The graph's edge descriptor
|
typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
|
|
/// Add an edge for the edge (u, v) based on vertex names
|
lazy_add_edge(BGL_NAMED_GRAPH& self,
|
const vertex_name_type& u_name,
|
const vertex_name_type& v_name)
|
: self(self), u(u_name), v(v_name), committed(false) { }
|
|
/// Add an edge for the edge (u, v) based on a vertex descriptor and name
|
lazy_add_edge(BGL_NAMED_GRAPH& self,
|
vertex_descriptor u,
|
const vertex_name_type& v_name)
|
: self(self), u(u), v(v_name), committed(false) { }
|
|
/// Add an edge for the edge (u, v) based on a vertex name and descriptor
|
lazy_add_edge(BGL_NAMED_GRAPH& self,
|
const vertex_name_type& u_name,
|
vertex_descriptor v)
|
: self(self), u(u_name), v(v), committed(false) { }
|
|
/// Add an edge for the edge (u, v) based on vertex descriptors
|
lazy_add_edge(BGL_NAMED_GRAPH& self,
|
vertex_descriptor u,
|
vertex_descriptor v)
|
: self(self), u(u), v(v), committed(false) { }
|
|
/// Copy a lazy_add_edge structure, which transfers responsibility
|
/// for adding the edge to the newly-constructed object.
|
lazy_add_edge(const lazy_add_edge& other)
|
: self(other.self), u(other.u), v(other.v), committed(other.committed)
|
{
|
other.committed = true;
|
}
|
|
/// If the edge has not yet been added, add the edge but don't wait
|
/// for a reply.
|
~lazy_add_edge();
|
|
/// Returns commit().
|
operator std::pair<edge_descriptor, bool>() const { return commit(); }
|
|
// Add the edge. This operation will block if a remote edge is
|
// being added.
|
std::pair<edge_descriptor, bool> commit() const;
|
|
protected:
|
BGL_NAMED_GRAPH& self;
|
mutable variant<vertex_descriptor, vertex_name_type> u;
|
mutable variant<vertex_descriptor, vertex_name_type> v;
|
mutable bool committed;
|
|
private:
|
// No copy-assignment semantics
|
void operator=(lazy_add_edge&);
|
};
|
|
template<BGL_NAMED_GRAPH_PARAMS>
|
BGL_NAMED_GRAPH::lazy_add_edge::~lazy_add_edge()
|
{
|
using boost::parallel::detail::make_untracked_pair;
|
|
/// If this edge has already been created or will be created by
|
/// someone else, or if someone threw an exception, we will not
|
/// create the edge now.
|
if (committed || std::uncaught_exception())
|
return;
|
|
committed = true;
|
|
if (vertex_name_type* v_name = boost::get<vertex_name_type>(&v)) {
|
// We haven't resolved the target vertex to a descriptor yet, so
|
// it must not be local. Send a message to the owner of the target
|
// of the edge. If the owner of the target does not happen to own
|
// the source, it will resolve the target to a vertex descriptor
|
// and pass the message along to the owner of the source.
|
if (vertex_name_type* u_name = boost::get<vertex_name_type>(&u))
|
send(self.process_group(), self.distribution_(*v_name),
|
BGL_NAMED_GRAPH::msg_add_edge_name_name,
|
make_untracked_pair(*u_name, *v_name));
|
else
|
send(self.process_group(), self.distribution_(*v_name),
|
BGL_NAMED_GRAPH::msg_add_edge_vertex_name,
|
make_untracked_pair(boost::get<vertex_descriptor>(u), *v_name));
|
} else {
|
if (vertex_name_type* u_name = boost::get<vertex_name_type>(&u))
|
// We haven't resolved the source vertex to a descriptor yet, so
|
// it must not be local. Send a message to the owner of the
|
// source vertex requesting the edge addition.
|
send(self.process_group(), self.distribution_(*u_name),
|
BGL_NAMED_GRAPH::msg_add_edge_name_vertex,
|
make_untracked_pair(*u_name, boost::get<vertex_descriptor>(v)));
|
else
|
// We have descriptors for both of the vertices, either of which
|
// may be remote or local. Tell the owner of the source vertex
|
// to add the edge (it may be us!).
|
add_edge(boost::get<vertex_descriptor>(u),
|
boost::get<vertex_descriptor>(v),
|
self.derived());
|
}
|
}
|
|
template<BGL_NAMED_GRAPH_PARAMS>
|
std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
|
BGL_NAMED_GRAPH::lazy_add_edge::commit() const
|
{
|
typedef typename BGL_NAMED_GRAPH::process_id_type process_id_type;
|
using boost::parallel::detail::make_untracked_pair;
|
|
BOOST_ASSERT(!committed);
|
committed = true;
|
|
/// The result we will return, if we are sending a message to
|
/// request that someone else add the edge.
|
boost::parallel::detail::untracked_pair<edge_descriptor, bool> result;
|
|
/// The owner of the vertex "u"
|
process_id_type u_owner;
|
|
process_id_type rank = process_id(self.process_group());
|
if (const vertex_name_type* u_name = boost::get<vertex_name_type>(&u)) {
|
/// We haven't resolved the source vertex to a descriptor yet, so
|
/// it must not be local.
|
u_owner = self.named_distribution()(*u_name);
|
|
/// Send a message to the remote vertex requesting that it add the
|
/// edge. The message differs depending on whether we have a
|
/// vertex name or a vertex descriptor for the target.
|
if (const vertex_name_type* v_name = boost::get<vertex_name_type>(&v))
|
send_oob_with_reply(self.process_group(), u_owner,
|
BGL_NAMED_GRAPH::msg_add_edge_name_name_with_reply,
|
make_untracked_pair(*u_name, *v_name), result);
|
else
|
send_oob_with_reply(self.process_group(), u_owner,
|
BGL_NAMED_GRAPH::msg_add_edge_name_vertex_with_reply,
|
make_untracked_pair(*u_name,
|
boost::get<vertex_descriptor>(v)),
|
result);
|
} else {
|
/// We have resolved the source vertex to a descriptor, which may
|
/// either be local or remote.
|
u_owner
|
= get(vertex_owner, self.derived(),
|
boost::get<vertex_descriptor>(u));
|
if (u_owner == rank) {
|
/// The source is local. If we need to, resolve the target vertex.
|
if (const vertex_name_type* v_name = boost::get<vertex_name_type>(&v))
|
v = add_vertex(*v_name, self.derived());
|
|
/// Add the edge using vertex descriptors
|
return add_edge(boost::get<vertex_descriptor>(u),
|
boost::get<vertex_descriptor>(v),
|
self.derived());
|
} else {
|
/// The source is remote. Just send a message to its owner
|
/// requesting that the owner add the new edge, either directly
|
/// or via the derived class's add_edge function.
|
if (const vertex_name_type* v_name = boost::get<vertex_name_type>(&v))
|
send_oob_with_reply
|
(self.process_group(), u_owner,
|
BGL_NAMED_GRAPH::msg_add_edge_vertex_name_with_reply,
|
make_untracked_pair(boost::get<vertex_descriptor>(u), *v_name),
|
result);
|
else
|
return add_edge(boost::get<vertex_descriptor>(u),
|
boost::get<vertex_descriptor>(v),
|
self.derived());
|
}
|
}
|
|
// If we get here, the edge has been added remotely and "result"
|
// contains the result of that edge addition.
|
return result;
|
}
|
|
/**
|
* Data structure returned from add_edge that will "lazily" add the
|
* edge with a property, either when it is converted to a @c
|
* pair<edge_descriptor,bool> or when the most recent copy has been
|
* destroyed.
|
*/
|
template<BGL_NAMED_GRAPH_PARAMS>
|
struct BGL_NAMED_GRAPH::lazy_add_edge_with_property
|
{
|
/// The graph's edge descriptor
|
typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
|
|
/// The Edge property type for our graph
|
typedef typename Config::edge_property_type edge_property_type;
|
|
/// Add an edge for the edge (u, v) based on vertex names
|
lazy_add_edge_with_property(BGL_NAMED_GRAPH& self,
|
const vertex_name_type& u_name,
|
const vertex_name_type& v_name,
|
const edge_property_type& property)
|
: self(self), u(u_name), v(v_name), property(property), committed(false)
|
{
|
}
|
|
/// Add an edge for the edge (u, v) based on a vertex descriptor and name
|
lazy_add_edge_with_property(BGL_NAMED_GRAPH& self,
|
vertex_descriptor u,
|
const vertex_name_type& v_name,
|
const edge_property_type& property)
|
: self(self), u(u), v(v_name), property(property), committed(false) { }
|
|
/// Add an edge for the edge (u, v) based on a vertex name and descriptor
|
lazy_add_edge_with_property(BGL_NAMED_GRAPH& self,
|
const vertex_name_type& u_name,
|
vertex_descriptor v,
|
const edge_property_type& property)
|
: self(self), u(u_name), v(v), property(property), committed(false) { }
|
|
/// Add an edge for the edge (u, v) based on vertex descriptors
|
lazy_add_edge_with_property(BGL_NAMED_GRAPH& self,
|
vertex_descriptor u,
|
vertex_descriptor v,
|
const edge_property_type& property)
|
: self(self), u(u), v(v), property(property), committed(false) { }
|
|
/// Copy a lazy_add_edge_with_property structure, which transfers
|
/// responsibility for adding the edge to the newly-constructed
|
/// object.
|
lazy_add_edge_with_property(const lazy_add_edge_with_property& other)
|
: self(other.self), u(other.u), v(other.v), property(other.property),
|
committed(other.committed)
|
{
|
other.committed = true;
|
}
|
|
/// If the edge has not yet been added, add the edge but don't wait
|
/// for a reply.
|
~lazy_add_edge_with_property();
|
|
/// Returns commit().
|
operator std::pair<edge_descriptor, bool>() const { return commit(); }
|
|
// Add the edge. This operation will block if a remote edge is
|
// being added.
|
std::pair<edge_descriptor, bool> commit() const;
|
|
protected:
|
BGL_NAMED_GRAPH& self;
|
mutable variant<vertex_descriptor, vertex_name_type> u;
|
mutable variant<vertex_descriptor, vertex_name_type> v;
|
edge_property_type property;
|
mutable bool committed;
|
|
private:
|
// No copy-assignment semantics
|
void operator=(lazy_add_edge_with_property&);
|
};
|
|
template<BGL_NAMED_GRAPH_PARAMS>
|
BGL_NAMED_GRAPH::lazy_add_edge_with_property::~lazy_add_edge_with_property()
|
{
|
using boost::detail::parallel::make_pair_with_property;
|
|
/// If this edge has already been created or will be created by
|
/// someone else, or if someone threw an exception, we will not
|
/// create the edge now.
|
if (committed || std::uncaught_exception())
|
return;
|
|
committed = true;
|
|
if (vertex_name_type* v_name = boost::get<vertex_name_type>(&v)) {
|
// We haven't resolved the target vertex to a descriptor yet, so
|
// it must not be local. Send a message to the owner of the target
|
// of the edge. If the owner of the target does not happen to own
|
// the source, it will resolve the target to a vertex descriptor
|
// and pass the message along to the owner of the source.
|
if (vertex_name_type* u_name = boost::get<vertex_name_type>(&u))
|
send(self.process_group(), self.distribution_(*v_name),
|
BGL_NAMED_GRAPH::msg_add_edge_name_name_with_property,
|
make_pair_with_property(*u_name, *v_name, property));
|
else
|
send(self.process_group(), self.distribution_(*v_name),
|
BGL_NAMED_GRAPH::msg_add_edge_vertex_name_with_property,
|
make_pair_with_property(boost::get<vertex_descriptor>(u), *v_name,
|
property));
|
} else {
|
if (vertex_name_type* u_name = boost::get<vertex_name_type>(&u))
|
// We haven't resolved the source vertex to a descriptor yet, so
|
// it must not be local. Send a message to the owner of the
|
// source vertex requesting the edge addition.
|
send(self.process_group(), self.distribution_(*u_name),
|
BGL_NAMED_GRAPH::msg_add_edge_name_vertex_with_property,
|
make_pair_with_property(*u_name, boost::get<vertex_descriptor>(v),
|
property));
|
else
|
// We have descriptors for both of the vertices, either of which
|
// may be remote or local. Tell the owner of the source vertex
|
// to add the edge (it may be us!).
|
add_edge(boost::get<vertex_descriptor>(u),
|
boost::get<vertex_descriptor>(v),
|
property,
|
self.derived());
|
}
|
}
|
|
template<BGL_NAMED_GRAPH_PARAMS>
|
std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
|
BGL_NAMED_GRAPH::lazy_add_edge_with_property::commit() const
|
{
|
using boost::detail::parallel::make_pair_with_property;
|
typedef typename BGL_NAMED_GRAPH::process_id_type process_id_type;
|
BOOST_ASSERT(!committed);
|
committed = true;
|
|
/// The result we will return, if we are sending a message to
|
/// request that someone else add the edge.
|
boost::parallel::detail::untracked_pair<edge_descriptor, bool> result;
|
|
/// The owner of the vertex "u"
|
process_id_type u_owner;
|
|
process_id_type rank = process_id(self.process_group());
|
if (const vertex_name_type* u_name = boost::get<vertex_name_type>(&u)) {
|
/// We haven't resolved the source vertex to a descriptor yet, so
|
/// it must not be local.
|
u_owner = self.named_distribution()(*u_name);
|
|
/// Send a message to the remote vertex requesting that it add the
|
/// edge. The message differs depending on whether we have a
|
/// vertex name or a vertex descriptor for the target.
|
if (const vertex_name_type* v_name = boost::get<vertex_name_type>(&v))
|
send_oob_with_reply
|
(self.process_group(), u_owner,
|
BGL_NAMED_GRAPH::msg_add_edge_name_name_with_reply_and_property,
|
make_pair_with_property(*u_name, *v_name, property),
|
result);
|
else
|
send_oob_with_reply
|
(self.process_group(), u_owner,
|
BGL_NAMED_GRAPH::msg_add_edge_name_vertex_with_reply_and_property,
|
make_pair_with_property(*u_name,
|
boost::get<vertex_descriptor>(v),
|
property),
|
result);
|
} else {
|
/// We have resolved the source vertex to a descriptor, which may
|
/// either be local or remote.
|
u_owner
|
= get(vertex_owner, self.derived(),
|
boost::get<vertex_descriptor>(u));
|
if (u_owner == rank) {
|
/// The source is local. If we need to, resolve the target vertex.
|
if (const vertex_name_type* v_name = boost::get<vertex_name_type>(&v))
|
v = add_vertex(*v_name, self.derived());
|
|
/// Add the edge using vertex descriptors
|
return add_edge(boost::get<vertex_descriptor>(u),
|
boost::get<vertex_descriptor>(v),
|
property,
|
self.derived());
|
} else {
|
/// The source is remote. Just send a message to its owner
|
/// requesting that the owner add the new edge, either directly
|
/// or via the derived class's add_edge function.
|
if (const vertex_name_type* v_name = boost::get<vertex_name_type>(&v))
|
send_oob_with_reply
|
(self.process_group(), u_owner,
|
BGL_NAMED_GRAPH::msg_add_edge_vertex_name_with_reply_and_property,
|
make_pair_with_property(boost::get<vertex_descriptor>(u), *v_name,
|
property),
|
result);
|
else
|
return add_edge(boost::get<vertex_descriptor>(u),
|
boost::get<vertex_descriptor>(v),
|
property,
|
self.derived());
|
}
|
}
|
|
// If we get here, the edge has been added remotely and "result"
|
// contains the result of that edge addition.
|
return result;
|
}
|
|
/// Construct the named_graph with a particular process group
|
template<BGL_NAMED_GRAPH_PARAMS>
|
BGL_NAMED_GRAPH::named_graph(const process_group_type& pg)
|
: process_group_(pg, boost::parallel::attach_distributed_object()),
|
distribution_(pg)
|
{
|
setup_triggers();
|
}
|
|
/// Construct the named_graph mixin with a particular process group
|
/// and distribution function
|
template<BGL_NAMED_GRAPH_PARAMS>
|
BGL_NAMED_GRAPH::named_graph(const process_group_type& pg,
|
const base_distribution_type& distribution)
|
: process_group_(pg, boost::parallel::attach_distributed_object()),
|
distribution_(pg, distribution)
|
{
|
setup_triggers();
|
}
|
|
template<BGL_NAMED_GRAPH_PARAMS>
|
void
|
BGL_NAMED_GRAPH::setup_triggers()
|
{
|
using boost::graph::parallel::simple_trigger;
|
|
simple_trigger(process_group_, msg_add_vertex_name, this,
|
&named_graph::handle_add_vertex_name);
|
simple_trigger(process_group_, msg_add_vertex_name_with_reply, this,
|
&named_graph::handle_add_vertex_name_with_reply);
|
simple_trigger(process_group_, msg_find_vertex, this,
|
&named_graph::handle_find_vertex);
|
simple_trigger(process_group_, msg_add_edge_name_name, this,
|
&named_graph::template handle_add_edge<vertex_name_type,
|
vertex_name_type>);
|
simple_trigger(process_group_, msg_add_edge_name_name_with_reply, this,
|
&named_graph::template handle_add_edge_with_reply
|
<vertex_name_type, vertex_name_type>);
|
simple_trigger(process_group_, msg_add_edge_name_vertex, this,
|
&named_graph::template handle_add_edge<vertex_name_type,
|
vertex_descriptor>);
|
simple_trigger(process_group_, msg_add_edge_name_vertex_with_reply, this,
|
&named_graph::template handle_add_edge_with_reply
|
<vertex_name_type, vertex_descriptor>);
|
simple_trigger(process_group_, msg_add_edge_vertex_name, this,
|
&named_graph::template handle_add_edge<vertex_descriptor,
|
vertex_name_type>);
|
simple_trigger(process_group_, msg_add_edge_vertex_name_with_reply, this,
|
&named_graph::template handle_add_edge_with_reply
|
<vertex_descriptor, vertex_name_type>);
|
simple_trigger(process_group_, msg_add_edge_name_name_with_property, this,
|
&named_graph::
|
template handle_add_edge_with_property<vertex_name_type,
|
vertex_name_type>);
|
simple_trigger(process_group_,
|
msg_add_edge_name_name_with_reply_and_property, this,
|
&named_graph::template handle_add_edge_with_reply_and_property
|
<vertex_name_type, vertex_name_type>);
|
simple_trigger(process_group_, msg_add_edge_name_vertex_with_property, this,
|
&named_graph::
|
template handle_add_edge_with_property<vertex_name_type,
|
vertex_descriptor>);
|
simple_trigger(process_group_,
|
msg_add_edge_name_vertex_with_reply_and_property, this,
|
&named_graph::template handle_add_edge_with_reply_and_property
|
<vertex_name_type, vertex_descriptor>);
|
simple_trigger(process_group_, msg_add_edge_vertex_name_with_property, this,
|
&named_graph::
|
template handle_add_edge_with_property<vertex_descriptor,
|
vertex_name_type>);
|
simple_trigger(process_group_,
|
msg_add_edge_vertex_name_with_reply_and_property, this,
|
&named_graph::template handle_add_edge_with_reply_and_property
|
<vertex_descriptor, vertex_name_type>);
|
}
|
|
/// Retrieve the vertex associated with the given name
|
template<BGL_NAMED_GRAPH_PARAMS>
|
optional<Vertex>
|
find_vertex(typename BGL_NAMED_GRAPH::vertex_name_type const& name,
|
const BGL_NAMED_GRAPH& g)
|
{
|
typedef typename Graph::local_vertex_descriptor local_vertex_descriptor;
|
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
|
|
// Determine the owner of this name
|
typename BGL_NAMED_GRAPH::process_id_type owner
|
= g.named_distribution()(name);
|
|
if (owner == process_id(g.process_group())) {
|
// The vertex is local, so search for a mapping here
|
optional<local_vertex_descriptor> result
|
= find_vertex(name, g.derived().base());
|
if (result)
|
return Vertex(owner, *result);
|
else
|
return optional<Vertex>();
|
}
|
else {
|
// Ask the ownering process for the name of this vertex
|
boost::parallel::detail::untracked_pair<vertex_descriptor, bool> result;
|
send_oob_with_reply(g.process_group(), owner,
|
BGL_NAMED_GRAPH::msg_find_vertex, name, result);
|
if (result.second)
|
return result.first;
|
else
|
return optional<Vertex>();
|
}
|
}
|
|
/// meta-function helping in figuring out if the given VertextProerty belongs to
|
/// a named graph
|
template<typename VertexProperty>
|
struct not_is_named_graph
|
: is_same<typename internal_vertex_name<VertexProperty>::type, void>
|
{};
|
|
/// Retrieve the vertex associated with the given name
|
template<typename Graph>
|
typename Graph::named_graph_type::lazy_add_vertex
|
add_vertex(typename Graph::vertex_name_type const& name,
|
Graph& g,
|
typename disable_if<
|
not_is_named_graph<typename Graph::vertex_property_type>,
|
void*>::type = 0)
|
{
|
return typename Graph::named_graph_type::lazy_add_vertex(g, name);
|
}
|
|
/// Add an edge using vertex names to refer to the vertices
|
template<BGL_NAMED_GRAPH_PARAMS>
|
typename BGL_NAMED_GRAPH::lazy_add_edge
|
add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
|
typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
|
BGL_NAMED_GRAPH& g)
|
{
|
typedef typename BGL_NAMED_GRAPH::lazy_add_edge lazy_add_edge;
|
typedef typename BGL_NAMED_GRAPH::process_id_type process_id_type;
|
|
process_id_type rank = process_id(g.process_group());
|
process_id_type u_owner = g.named_distribution()(u_name);
|
process_id_type v_owner = g.named_distribution()(v_name);
|
|
// Resolve local vertex names before building the "lazy" edge
|
// addition structure.
|
if (u_owner == rank && v_owner == rank)
|
return lazy_add_edge(g, add_vertex(u_name, g), add_vertex(v_name, g));
|
else if (u_owner == rank && v_owner != rank)
|
return lazy_add_edge(g, add_vertex(u_name, g), v_name);
|
else if (u_owner != rank && v_owner == rank)
|
return lazy_add_edge(g, u_name, add_vertex(v_name, g));
|
else
|
return lazy_add_edge(g, u_name, v_name);
|
}
|
|
template<BGL_NAMED_GRAPH_PARAMS>
|
typename BGL_NAMED_GRAPH::lazy_add_edge
|
add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
|
typename BGL_NAMED_GRAPH::vertex_descriptor const& v,
|
BGL_NAMED_GRAPH& g)
|
{
|
// Resolve local vertex names before building the "lazy" edge
|
// addition structure.
|
typedef typename BGL_NAMED_GRAPH::lazy_add_edge lazy_add_edge;
|
if (g.named_distribution()(u_name) == process_id(g.process_group()))
|
return lazy_add_edge(g, add_vertex(u_name, g), v);
|
else
|
return lazy_add_edge(g, u_name, v);
|
}
|
|
template<BGL_NAMED_GRAPH_PARAMS>
|
typename BGL_NAMED_GRAPH::lazy_add_edge
|
add_edge(typename BGL_NAMED_GRAPH::vertex_descriptor const& u,
|
typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
|
BGL_NAMED_GRAPH& g)
|
{
|
// Resolve local vertex names before building the "lazy" edge
|
// addition structure.
|
typedef typename BGL_NAMED_GRAPH::lazy_add_edge lazy_add_edge;
|
if (g.named_distribution()(v_name) == process_id(g.process_group()))
|
return lazy_add_edge(g, u, add_vertex(v_name, g));
|
else
|
return lazy_add_edge(g, u, v_name);
|
}
|
|
/// Add an edge using vertex names to refer to the vertices
|
template<BGL_NAMED_GRAPH_PARAMS>
|
typename BGL_NAMED_GRAPH::lazy_add_edge_with_property
|
add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
|
typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
|
typename Graph::edge_property_type const& property,
|
BGL_NAMED_GRAPH& g)
|
{
|
typedef typename BGL_NAMED_GRAPH::lazy_add_edge_with_property lazy_add_edge;
|
typedef typename BGL_NAMED_GRAPH::process_id_type process_id_type;
|
|
process_id_type rank = process_id(g.process_group());
|
process_id_type u_owner = g.named_distribution()(u_name);
|
process_id_type v_owner = g.named_distribution()(v_name);
|
|
// Resolve local vertex names before building the "lazy" edge
|
// addition structure.
|
if (u_owner == rank && v_owner == rank)
|
return lazy_add_edge(g, add_vertex(u_name, g), add_vertex(v_name, g),
|
property);
|
else if (u_owner == rank && v_owner != rank)
|
return lazy_add_edge(g, add_vertex(u_name, g), v_name, property);
|
else if (u_owner != rank && v_owner == rank)
|
return lazy_add_edge(g, u_name, add_vertex(v_name, g), property);
|
else
|
return lazy_add_edge(g, u_name, v_name, property);
|
}
|
|
template<BGL_NAMED_GRAPH_PARAMS>
|
typename BGL_NAMED_GRAPH::lazy_add_edge_with_property
|
add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
|
typename BGL_NAMED_GRAPH::vertex_descriptor const& v,
|
typename Graph::edge_property_type const& property,
|
BGL_NAMED_GRAPH& g)
|
{
|
// Resolve local vertex names before building the "lazy" edge
|
// addition structure.
|
typedef typename BGL_NAMED_GRAPH::lazy_add_edge_with_property lazy_add_edge;
|
if (g.named_distribution()(u_name) == process_id(g.process_group()))
|
return lazy_add_edge(g, add_vertex(u_name, g), v, property);
|
else
|
return lazy_add_edge(g, u_name, v, property);
|
}
|
|
template<BGL_NAMED_GRAPH_PARAMS>
|
typename BGL_NAMED_GRAPH::lazy_add_edge_with_property
|
add_edge(typename BGL_NAMED_GRAPH::vertex_descriptor const& u,
|
typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
|
typename Graph::edge_property_type const& property,
|
BGL_NAMED_GRAPH& g)
|
{
|
// Resolve local vertex names before building the "lazy" edge
|
// addition structure.
|
typedef typename BGL_NAMED_GRAPH::lazy_add_edge_with_property lazy_add_edge;
|
if (g.named_distribution()(v_name) == process_id(g.process_group()))
|
return lazy_add_edge(g, u, add_vertex(v_name, g), property);
|
else
|
return lazy_add_edge(g, u, v_name, property);
|
}
|
|
template<BGL_NAMED_GRAPH_PARAMS>
|
typename BGL_NAMED_GRAPH::process_id_type
|
BGL_NAMED_GRAPH::owner_by_property(const vertex_property_type& property)
|
{
|
return distribution_(derived().base().extract_name(property));
|
}
|
|
|
/*******************************************************************
|
* Message handlers *
|
*******************************************************************/
|
|
template<BGL_NAMED_GRAPH_PARAMS>
|
void
|
BGL_NAMED_GRAPH::
|
handle_add_vertex_name(int /*source*/, int /*tag*/,
|
const vertex_name_type& msg, trigger_receive_context)
|
{
|
add_vertex(msg, derived());
|
}
|
|
template<BGL_NAMED_GRAPH_PARAMS>
|
typename BGL_NAMED_GRAPH::vertex_descriptor
|
BGL_NAMED_GRAPH::
|
handle_add_vertex_name_with_reply(int source, int /*tag*/,
|
const vertex_name_type& msg,
|
trigger_receive_context)
|
{
|
return add_vertex(msg, derived());
|
}
|
|
template<BGL_NAMED_GRAPH_PARAMS>
|
boost::parallel::detail::untracked_pair<typename BGL_NAMED_GRAPH::vertex_descriptor, bool>
|
BGL_NAMED_GRAPH::
|
handle_find_vertex(int source, int /*tag*/, const vertex_name_type& msg,
|
trigger_receive_context)
|
{
|
using boost::parallel::detail::make_untracked_pair;
|
|
optional<vertex_descriptor> v = find_vertex(msg, derived());
|
if (v)
|
return make_untracked_pair(*v, true);
|
else
|
return make_untracked_pair(graph_traits<Graph>::null_vertex(), false);
|
}
|
|
template<BGL_NAMED_GRAPH_PARAMS>
|
template<typename U, typename V>
|
void
|
BGL_NAMED_GRAPH::
|
handle_add_edge(int source, int /*tag*/, const boost::parallel::detail::untracked_pair<U, V>& msg,
|
trigger_receive_context)
|
{
|
add_edge(msg.first, msg.second, derived());
|
}
|
|
template<BGL_NAMED_GRAPH_PARAMS>
|
template<typename U, typename V>
|
boost::parallel::detail::untracked_pair<typename BGL_NAMED_GRAPH::edge_descriptor, bool>
|
BGL_NAMED_GRAPH::
|
handle_add_edge_with_reply(int source, int /*tag*/, const boost::parallel::detail::untracked_pair<U, V>& msg,
|
trigger_receive_context)
|
{
|
std::pair<typename BGL_NAMED_GRAPH::edge_descriptor, bool> p =
|
add_edge(msg.first, msg.second, derived());
|
return p;
|
}
|
|
template<BGL_NAMED_GRAPH_PARAMS>
|
template<typename U, typename V>
|
void
|
BGL_NAMED_GRAPH::
|
handle_add_edge_with_property
|
(int source, int tag,
|
const pair_with_property<U, V, edge_property_type>& msg,
|
trigger_receive_context)
|
{
|
add_edge(msg.first, msg.second, msg.get_property(), derived());
|
}
|
|
template<BGL_NAMED_GRAPH_PARAMS>
|
template<typename U, typename V>
|
boost::parallel::detail::untracked_pair<typename BGL_NAMED_GRAPH::edge_descriptor, bool>
|
BGL_NAMED_GRAPH::
|
handle_add_edge_with_reply_and_property
|
(int source, int tag,
|
const pair_with_property<U, V, edge_property_type>& msg,
|
trigger_receive_context)
|
{
|
std:: pair<typename BGL_NAMED_GRAPH::edge_descriptor, bool> p =
|
add_edge(msg.first, msg.second, msg.get_property(), derived());
|
return p;
|
}
|
|
#undef BGL_NAMED_GRAPH
|
#undef BGL_NAMED_GRAPH_PARAMS
|
|
/*******************************************************************
|
* Maybe named graph mixin *
|
*******************************************************************/
|
|
/**
|
* A graph mixin that can provide a mapping from names to vertices,
|
* and use that mapping to simplify creation and manipulation of
|
* graphs.
|
*/
|
template<typename Graph, typename Vertex, typename Edge, typename Config,
|
typename ExtractName
|
= typename internal_vertex_name<typename Config::vertex_property_type>::type>
|
struct maybe_named_graph
|
: public named_graph<Graph, Vertex, Edge, Config>
|
{
|
private:
|
typedef named_graph<Graph, Vertex, Edge, Config> inherited;
|
typedef typename Config::process_group_type process_group_type;
|
|
public:
|
/// The type used to distribute named vertices in the graph
|
typedef typename Config::distribution_type distribution_type;
|
typedef typename Config::base_distribution_type base_distribution_type;
|
|
explicit maybe_named_graph(const process_group_type& pg) : inherited(pg) { }
|
|
maybe_named_graph(const process_group_type& pg,
|
const base_distribution_type& distribution)
|
: inherited(pg, distribution) { }
|
|
distribution_type& distribution() { return this->distribution_; }
|
const distribution_type& distribution() const { return this->distribution_; }
|
};
|
|
/**
|
* A graph mixin that can provide a mapping from names to vertices,
|
* and use that mapping to simplify creation and manipulation of
|
* graphs. This partial specialization turns off this functionality
|
* when the @c VertexProperty does not have an internal vertex name.
|
*/
|
template<typename Graph, typename Vertex, typename Edge, typename Config>
|
struct maybe_named_graph<Graph, Vertex, Edge, Config, void>
|
{
|
private:
|
typedef typename Config::process_group_type process_group_type;
|
typedef typename Config::vertex_property_type vertex_property_type;
|
|
public:
|
typedef typename process_group_type::process_id_type process_id_type;
|
|
/// The type used to distribute named vertices in the graph
|
typedef typename Config::distribution_type distribution_type;
|
typedef typename Config::base_distribution_type base_distribution_type;
|
|
explicit maybe_named_graph(const process_group_type&) { }
|
|
maybe_named_graph(const process_group_type& pg,
|
const base_distribution_type& distribution)
|
: distribution_(pg, distribution) { }
|
|
/// Notify the named_graph that we have added the given vertex. This
|
/// is a no-op.
|
void added_vertex(Vertex) { }
|
|
/// Notify the named_graph that we are removing the given
|
/// vertex. This is a no-op.
|
template <typename VertexIterStability>
|
void removing_vertex(Vertex, VertexIterStability) { }
|
|
/// Notify the named_graph that we are clearing the graph
|
void clearing_graph() { }
|
|
/// Retrieve the owner of a given vertex based on the properties
|
/// associated with that vertex. This operation just returns the
|
/// number of the local processor, adding all vertices locally.
|
process_id_type owner_by_property(const vertex_property_type&)
|
{
|
return process_id(pg);
|
}
|
|
distribution_type& distribution() { return distribution_; }
|
const distribution_type& distribution() const { return distribution_; }
|
|
protected:
|
/// The process group of the graph
|
process_group_type pg;
|
|
/// The distribution used for the graph
|
distribution_type distribution_;
|
};
|
|
} } } // end namespace boost::graph::distributed
|
|
#endif // BOOST_GRAPH_DISTRIBUTED_NAMED_GRAPH_HPP
|
