// 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 |