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