// 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)
|
|
// This file contains code for the distributed adjacency list's
|
// initializations. It should not be included directly by users.
|
|
#ifndef BOOST_GRAPH_DISTRIBUTED_ADJLIST_INITIALIZE_HPP
|
#define BOOST_GRAPH_DISTRIBUTED_ADJLIST_INITIALIZE_HPP
|
|
#ifndef BOOST_GRAPH_USE_MPI
|
#error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
|
#endif
|
|
namespace boost {
|
|
template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
|
template<typename EdgeIterator>
|
void
|
PBGL_DISTRIB_ADJLIST_TYPE::
|
initialize(EdgeIterator first, EdgeIterator last,
|
vertices_size_type, const base_distribution_type& distribution,
|
vecS)
|
{
|
process_id_type id = process_id(process_group_);
|
while (first != last) {
|
if ((process_id_type)distribution(first->first) == id) {
|
vertex_descriptor source(id, distribution.local(first->first));
|
vertex_descriptor target(distribution(first->second),
|
distribution.local(first->second));
|
add_edge(source, target, *this);
|
}
|
++first;
|
}
|
|
synchronize(process_group_);
|
}
|
|
template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
|
template<typename EdgeIterator, typename EdgePropertyIterator>
|
void
|
PBGL_DISTRIB_ADJLIST_TYPE::
|
initialize(EdgeIterator first, EdgeIterator last,
|
EdgePropertyIterator ep_iter,
|
vertices_size_type, const base_distribution_type& distribution,
|
vecS)
|
{
|
process_id_type id = process_id(process_group_);
|
while (first != last) {
|
if (static_cast<process_id_type>(distribution(first->first)) == id) {
|
vertex_descriptor source(id, distribution.local(first->first));
|
vertex_descriptor target(distribution(first->second),
|
distribution.local(first->second));
|
add_edge(source, target, *ep_iter, *this);
|
}
|
++first;
|
++ep_iter;
|
}
|
|
synchronize(process_group_);
|
}
|
|
template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
|
template<typename EdgeIterator, typename EdgePropertyIterator,
|
typename VertexListS>
|
void
|
PBGL_DISTRIB_ADJLIST_TYPE::
|
initialize(EdgeIterator first, EdgeIterator last,
|
EdgePropertyIterator ep_iter,
|
vertices_size_type n, const base_distribution_type& distribution,
|
VertexListS)
|
{
|
using boost::parallel::inplace_all_to_all;
|
|
typedef vertices_size_type vertex_number_t;
|
typedef typename std::iterator_traits<EdgePropertyIterator>::value_type
|
edge_property_init_t;
|
|
typedef std::pair<vertex_descriptor, vertex_number_t>
|
st_pair;
|
typedef std::pair<st_pair, edge_property_init_t> delayed_edge_t;
|
|
process_group_type pg = process_group();
|
process_id_type id = process_id(pg);
|
|
// Vertex indices
|
std::vector<local_vertex_descriptor> index_to_vertex;
|
index_to_vertex.reserve(num_vertices(*this));
|
BGL_FORALL_VERTICES_T(v, base(), inherited)
|
index_to_vertex.push_back(v);
|
|
// The list of edges we can't add immediately.
|
std::vector<delayed_edge_t> delayed_edges;
|
|
std::vector<std::vector<vertex_number_t> > descriptor_requests;
|
descriptor_requests.resize(num_processes(pg));
|
|
// Add all of the edges we can, up to the point where we run
|
// into a descriptor we don't know.
|
while (first != last) {
|
if (distribution(first->first) == id) {
|
if (distribution(first->second) != id) break;
|
vertex_descriptor source
|
(id, index_to_vertex[distribution.local(first->first)]);
|
vertex_descriptor target
|
(distribution(first->second),
|
index_to_vertex[distribution.local(first->second)]);
|
add_edge(source, target, *ep_iter, *this);
|
}
|
++first;
|
++ep_iter;
|
}
|
|
// Queue all of the remaining edges and determine the set of
|
// descriptors we need to know about.
|
while (first != last) {
|
if (distribution(first->first) == id) {
|
vertex_descriptor source
|
(id, index_to_vertex[distribution.local(first->first)]);
|
process_id_type dest = distribution(first->second);
|
if (dest != id) {
|
descriptor_requests[dest]
|
.push_back(distribution.local(first->second));
|
// Compact request list if we need to
|
if (descriptor_requests[dest].size() >
|
distribution.block_size(dest, n)) {
|
std::sort(descriptor_requests[dest].begin(),
|
descriptor_requests[dest].end());
|
descriptor_requests[dest].erase(
|
std::unique(descriptor_requests[dest].begin(),
|
descriptor_requests[dest].end()),
|
descriptor_requests[dest].end());
|
}
|
}
|
|
// Save the edge for later
|
delayed_edges.push_back
|
(delayed_edge_t(st_pair(source, first->second), *ep_iter));
|
}
|
++first;
|
++ep_iter;
|
}
|
|
// Compact descriptor requests
|
for (process_id_type dest = 0; dest < num_processes(pg); ++dest) {
|
std::sort(descriptor_requests[dest].begin(),
|
descriptor_requests[dest].end());
|
descriptor_requests[dest].erase(
|
std::unique(descriptor_requests[dest].begin(),
|
descriptor_requests[dest].end()),
|
descriptor_requests[dest].end());
|
}
|
|
// Send out all of the descriptor requests
|
std::vector<std::vector<vertex_number_t> > in_descriptor_requests;
|
in_descriptor_requests.resize(num_processes(pg));
|
inplace_all_to_all(pg, descriptor_requests, in_descriptor_requests);
|
|
// Reply to all of the descriptor requests
|
std::vector<std::vector<local_vertex_descriptor> >
|
descriptor_responses;
|
descriptor_responses.resize(num_processes(pg));
|
for (process_id_type dest = 0; dest < num_processes(pg); ++dest) {
|
for (std::size_t i = 0; i < in_descriptor_requests[dest].size(); ++i) {
|
local_vertex_descriptor v =
|
index_to_vertex[in_descriptor_requests[dest][i]];
|
descriptor_responses[dest].push_back(v);
|
}
|
in_descriptor_requests[dest].clear();
|
}
|
in_descriptor_requests.clear();
|
inplace_all_to_all(pg, descriptor_responses);
|
|
// Add the queued edges
|
for(typename std::vector<delayed_edge_t>::iterator i
|
= delayed_edges.begin(); i != delayed_edges.end(); ++i) {
|
process_id_type dest = distribution(i->first.second);
|
local_vertex_descriptor tgt_local;
|
if (dest == id) {
|
tgt_local = index_to_vertex[distribution.local(i->first.second)];
|
} else {
|
std::vector<vertex_number_t>& requests = descriptor_requests[dest];
|
typename std::vector<vertex_number_t>::iterator pos =
|
std::lower_bound(requests.begin(), requests.end(),
|
distribution.local(i->first.second));
|
tgt_local = descriptor_responses[dest][pos - requests.begin()];
|
}
|
add_edge(i->first.first, vertex_descriptor(dest, tgt_local),
|
i->second, *this);
|
}
|
synchronize(process_group_);
|
}
|
|
template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
|
template<typename EdgeIterator, typename VertexListS>
|
void
|
PBGL_DISTRIB_ADJLIST_TYPE::
|
initialize(EdgeIterator first, EdgeIterator last,
|
vertices_size_type n, const base_distribution_type& distribution,
|
VertexListS)
|
{
|
using boost::parallel::inplace_all_to_all;
|
|
typedef vertices_size_type vertex_number_t;
|
|
typedef std::pair<vertex_descriptor, vertex_number_t> delayed_edge_t;
|
|
process_group_type pg = process_group();
|
process_id_type id = process_id(pg);
|
|
// Vertex indices
|
std::vector<local_vertex_descriptor> index_to_vertex;
|
index_to_vertex.reserve(num_vertices(*this));
|
BGL_FORALL_VERTICES_T(v, base(), inherited)
|
index_to_vertex.push_back(v);
|
|
// The list of edges we can't add immediately.
|
std::vector<delayed_edge_t> delayed_edges;
|
|
std::vector<std::vector<vertex_number_t> > descriptor_requests;
|
descriptor_requests.resize(num_processes(pg));
|
|
// Add all of the edges we can, up to the point where we run
|
// into a descriptor we don't know.
|
while (first != last) {
|
if (distribution(first->first) == id) {
|
if (distribution(first->second) != id) break;
|
vertex_descriptor source
|
(id, index_to_vertex[distribution.local(first->first)]);
|
vertex_descriptor target
|
(distribution(first->second),
|
index_to_vertex[distribution.local(first->second)]);
|
add_edge(source, target, *this);
|
}
|
++first;
|
}
|
|
// Queue all of the remaining edges and determine the set of
|
// descriptors we need to know about.
|
while (first != last) {
|
if (distribution(first->first) == id) {
|
vertex_descriptor source
|
(id, index_to_vertex[distribution.local(first->first)]);
|
process_id_type dest = distribution(first->second);
|
if (dest != id) {
|
descriptor_requests[dest]
|
.push_back(distribution.local(first->second));
|
// Compact request list if we need to
|
if (descriptor_requests[dest].size() >
|
distribution.block_size(dest, n)) {
|
std::sort(descriptor_requests[dest].begin(),
|
descriptor_requests[dest].end());
|
descriptor_requests[dest].erase(
|
std::unique(descriptor_requests[dest].begin(),
|
descriptor_requests[dest].end()),
|
descriptor_requests[dest].end());
|
}
|
}
|
|
// Save the edge for later
|
delayed_edges.push_back(delayed_edge_t(source, first->second));
|
}
|
++first;
|
}
|
|
// Compact descriptor requests
|
for (process_id_type dest = 0; dest < num_processes(pg); ++dest) {
|
std::sort(descriptor_requests[dest].begin(),
|
descriptor_requests[dest].end());
|
descriptor_requests[dest].erase(
|
std::unique(descriptor_requests[dest].begin(),
|
descriptor_requests[dest].end()),
|
descriptor_requests[dest].end());
|
}
|
|
// Send out all of the descriptor requests
|
std::vector<std::vector<vertex_number_t> > in_descriptor_requests;
|
in_descriptor_requests.resize(num_processes(pg));
|
inplace_all_to_all(pg, descriptor_requests, in_descriptor_requests);
|
|
// Reply to all of the descriptor requests
|
std::vector<std::vector<local_vertex_descriptor> >
|
descriptor_responses;
|
descriptor_responses.resize(num_processes(pg));
|
for (process_id_type dest = 0; dest < num_processes(pg); ++dest) {
|
for (std::size_t i = 0; i < in_descriptor_requests[dest].size(); ++i) {
|
local_vertex_descriptor v =
|
index_to_vertex[in_descriptor_requests[dest][i]];
|
descriptor_responses[dest].push_back(v);
|
}
|
in_descriptor_requests[dest].clear();
|
}
|
in_descriptor_requests.clear();
|
inplace_all_to_all(pg, descriptor_responses);
|
|
// Add the queued edges
|
for(typename std::vector<delayed_edge_t>::iterator i
|
= delayed_edges.begin(); i != delayed_edges.end(); ++i) {
|
process_id_type dest = distribution(i->second);
|
local_vertex_descriptor tgt_local;
|
if (dest == id) {
|
tgt_local = index_to_vertex[distribution.local(i->second)];
|
} else {
|
std::vector<vertex_number_t>& requests = descriptor_requests[dest];
|
typename std::vector<vertex_number_t>::iterator pos =
|
std::lower_bound(requests.begin(), requests.end(),
|
distribution.local(i->second));
|
tgt_local = descriptor_responses[dest][pos - requests.begin()];
|
}
|
add_edge(i->first, vertex_descriptor(dest, tgt_local), *this);
|
}
|
synchronize(process_group_);
|
}
|
|
} // end namespace boost
|
|
#endif // BOOST_GRAPH_DISTRIBUTED_ADJLIST_INITIALIZE_HPP
|
