// Copyright (C) 2004-2006 The Trustees of Indiana University. | |
// 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: Nick Edmonds | |
// Douglas Gregor | |
// Andrew Lumsdaine | |
#ifndef BOOST_GRAPH_PARALLEL_CC_HPP | |
#define BOOST_GRAPH_PARALLEL_CC_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/property_map/property_map.hpp> | |
#include <boost/property_map/parallel/caching_property_map.hpp> | |
#include <boost/graph/parallel/algorithm.hpp> | |
#include <boost/pending/indirect_cmp.hpp> | |
#include <boost/graph/graph_traits.hpp> | |
#include <boost/graph/overloading.hpp> | |
#include <boost/graph/distributed/concepts.hpp> | |
#include <boost/graph/parallel/properties.hpp> | |
#include <boost/graph/distributed/local_subgraph.hpp> | |
#include <boost/graph/connected_components.hpp> | |
#include <boost/graph/named_function_params.hpp> | |
#include <boost/graph/parallel/process_group.hpp> | |
#include <boost/optional.hpp> | |
#include <algorithm> | |
#include <vector> | |
#include <list> | |
#include <boost/graph/parallel/container_traits.hpp> | |
#include <boost/graph/iteration_macros.hpp> | |
#define PBGL_IN_PLACE_MERGE /* In place merge instead of sorting */ | |
//#define PBGL_SORT_ASSERT /* Assert sorted for in place merge */ | |
/* Explicit sychronization in pointer doubling step? */ | |
#define PBGL_EXPLICIT_SYNCH | |
//#define PBGL_CONSTRUCT_METAGRAPH | |
#ifdef PBGL_CONSTRUCT_METAGRAPH | |
# define MAX_VERTICES_IN_METAGRAPH 10000 | |
#endif | |
namespace boost { namespace graph { namespace distributed { | |
namespace cc_detail { | |
enum connected_components_message { | |
edges_msg, req_parents_msg, parents_msg, root_adj_msg | |
}; | |
template <typename Vertex> | |
struct metaVertex { | |
metaVertex() {} | |
metaVertex(const Vertex& v) : name(v) {} | |
template<typename Archiver> | |
void serialize(Archiver& ar, const unsigned int /*version*/) | |
{ | |
ar & name; | |
} | |
Vertex name; | |
}; | |
#ifdef PBGL_CONSTRUCT_METAGRAPH | |
// Build meta-graph on result of local connected components | |
template <typename Graph, typename ParentMap, typename RootIterator, | |
typename AdjacencyMap> | |
void | |
build_local_metagraph(const Graph& g, ParentMap p, RootIterator r, | |
RootIterator r_end, AdjacencyMap& adj) | |
{ | |
// TODO: Static assert that AdjacencyMap::value_type is std::vector<vertex_descriptor> | |
typedef typename boost::graph::parallel::process_group_type<Graph>::type | |
process_group_type; | |
typedef typename process_group_type::process_id_type process_id_type; | |
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; | |
BOOST_STATIC_ASSERT((is_same<typename AdjacencyMap::mapped_type, | |
std::vector<vertex_descriptor> >::value)); | |
using boost::graph::parallel::process_group; | |
process_group_type pg = process_group(g); | |
process_id_type id = process_id(pg); | |
if (id != 0) { | |
// Send component roots and their associated edges to P0 | |
for ( ; r != r_end; ++r ) { | |
std::vector<vertex_descriptor> adjs(1, *r); // Root | |
adjs.reserve(adjs.size() + adj[*r].size()); | |
for (typename std::vector<vertex_descriptor>::iterator iter = adj[*r].begin(); | |
iter != adj[*r].end(); ++iter) | |
adjs.push_back(get(p, *iter)); // Adjacencies | |
send(pg, 0, root_adj_msg, adjs); | |
} | |
} | |
synchronize(pg); | |
if (id == 0) { | |
typedef metaVertex<vertex_descriptor> VertexProperties; | |
typedef boost::adjacency_list<vecS, vecS, undirectedS, | |
VertexProperties> metaGraph; | |
typedef typename graph_traits<metaGraph>::vertex_descriptor | |
meta_vertex_descriptor; | |
std::map<vertex_descriptor, meta_vertex_descriptor> vertex_map; | |
std::vector<std::pair<vertex_descriptor, vertex_descriptor> > edges; | |
// Receive remote roots and edges | |
while (optional<std::pair<process_id_type, int> > m = probe(pg)) { | |
BOOST_ASSERT(m->second == root_adj_msg); | |
std::vector<vertex_descriptor> adjs; | |
receive(pg, m->first, m->second, adjs); | |
vertex_map[adjs[0]] = graph_traits<metaGraph>::null_vertex(); | |
for (typename std::vector<vertex_descriptor>::iterator iter | |
= ++adjs.begin(); iter != adjs.end(); ++iter) | |
edges.push_back(std::make_pair(adjs[0], *iter)); | |
} | |
// Add local roots and edges | |
for ( ; r != r_end; ++r ) { | |
vertex_map[*r] = graph_traits<metaGraph>::null_vertex(); | |
edges.reserve(edges.size() + adj[*r].size()); | |
for (typename std::vector<vertex_descriptor>::iterator iter = adj[*r].begin(); | |
iter != adj[*r].end(); ++iter) | |
edges.push_back(std::make_pair(*r, get(p, *iter))); | |
} | |
// Build local meta-graph | |
metaGraph mg; | |
// Add vertices with property to map back to distributed graph vertex | |
for (typename std::map<vertex_descriptor, meta_vertex_descriptor>::iterator | |
iter = vertex_map.begin(); iter != vertex_map.end(); ++iter) | |
vertex_map[iter->first] | |
= add_vertex(metaVertex<vertex_descriptor>(iter->first), mg); | |
// Build meta-vertex map | |
typename property_map<metaGraph, vertex_descriptor VertexProperties::*>::type | |
metaVertexMap = get(&VertexProperties::name, mg); | |
typename std::vector<std::pair<vertex_descriptor, vertex_descriptor> > | |
::iterator edge_iter = edges.begin(); | |
for ( ; edge_iter != edges.end(); ++edge_iter) | |
add_edge(vertex_map[edge_iter->first], vertex_map[edge_iter->second], mg); | |
edges.clear(); | |
// Call connected_components on it | |
typedef typename property_map<metaGraph, vertex_index_t>::type | |
meta_index_map_type; | |
meta_index_map_type meta_index = get(vertex_index, mg); | |
std::vector<std::size_t> mg_component_vec(num_vertices(mg)); | |
typedef iterator_property_map<std::vector<std::size_t>::iterator, | |
meta_index_map_type> | |
meta_components_map_type; | |
meta_components_map_type mg_component(mg_component_vec.begin(), | |
meta_index); | |
std::size_t num_comp = connected_components(mg, mg_component); | |
// Update Parent pointers | |
std::vector<meta_vertex_descriptor> roots(num_comp, graph_traits<metaGraph>::null_vertex()); | |
BGL_FORALL_VERTICES_T(v, mg, metaGraph) { | |
size_t component = get(mg_component, v); | |
if (roots[component] == graph_traits<metaGraph>::null_vertex() || | |
get(meta_index, v) < get(meta_index, roots[component])) | |
roots[component] = v; | |
} | |
// Set all the local parent pointers | |
BGL_FORALL_VERTICES_T(v, mg, metaGraph) { | |
// Problem in value being put (3rd parameter) | |
put(p, get(metaVertexMap, v), get(metaVertexMap, roots[get(mg_component, v)])); | |
} | |
} | |
synchronize(p); | |
} | |
#endif | |
/* Function object used to remove internal vertices and vertices > | |
the current vertex from the adjacent vertex lists at each | |
root */ | |
template <typename Vertex, typename ParentMap> | |
class cull_adjacency_list | |
{ | |
public: | |
cull_adjacency_list(const Vertex v, const ParentMap p) : v(v), p(p) {} | |
bool operator() (const Vertex x) { return (get(p, x) == v || x == v); } | |
private: | |
const Vertex v; | |
const ParentMap p; | |
}; | |
/* Comparison operator used to choose targets for hooking s.t. vertices | |
that are hooked to are evenly distributed across processors */ | |
template <typename OwnerMap, typename LocalMap> | |
class hashed_vertex_compare | |
{ | |
public: | |
hashed_vertex_compare (const OwnerMap& o, const LocalMap& l) | |
: owner(o), local(l) { } | |
template <typename Vertex> | |
bool operator() (const Vertex x, const Vertex y) | |
{ | |
if (get(local, x) < get(local, y)) | |
return true; | |
else if (get(local, x) == get(local, y)) | |
return (get(owner, x) < get(owner, y)); | |
return false; | |
} | |
private: | |
OwnerMap owner; | |
LocalMap local; | |
}; | |
#ifdef PBGL_EXPLICIT_SYNCH | |
template <typename Graph, typename ParentMap, typename VertexList> | |
void | |
request_parent_map_entries(const Graph& g, ParentMap p, | |
std::vector<VertexList>& parent_requests) | |
{ | |
typedef typename boost::graph::parallel::process_group_type<Graph> | |
::type process_group_type; | |
typedef typename process_group_type::process_id_type process_id_type; | |
typedef typename graph_traits<Graph>::vertex_descriptor | |
vertex_descriptor; | |
process_group_type pg = process_group(g); | |
/* | |
This should probably be send_oob_with_reply, especially when Dave | |
finishes prefetch-batching | |
*/ | |
// Send root requests | |
for (process_id_type i = 0; i < num_processes(pg); ++i) { | |
if (!parent_requests[i].empty()) { | |
std::vector<vertex_descriptor> reqs(parent_requests[i].begin(), | |
parent_requests[i].end()); | |
send(pg, i, req_parents_msg, reqs); | |
} | |
} | |
synchronize(pg); | |
// Receive root requests and reply to them | |
while (optional<std::pair<process_id_type, int> > m = probe(pg)) { | |
std::vector<vertex_descriptor> requests; | |
receive(pg, m->first, m->second, requests); | |
for (std::size_t i = 0; i < requests.size(); ++i) | |
requests[i] = get(p, requests[i]); | |
send(pg, m->first, parents_msg, requests); | |
} | |
synchronize(pg); | |
// Receive requested parents | |
std::vector<vertex_descriptor> responses; | |
for (process_id_type i = 0; i < num_processes(pg); ++i) { | |
if (!parent_requests[i].empty()) { | |
receive(pg, i, parents_msg, responses); | |
std::size_t parent_idx = 0; | |
for (typename VertexList::iterator v = parent_requests[i].begin(); | |
v != parent_requests[i].end(); ++v, ++parent_idx) | |
put(p, *v, responses[parent_idx]); | |
} | |
} | |
} | |
#endif | |
template<typename DistributedGraph, typename ParentMap> | |
void | |
parallel_connected_components(DistributedGraph& g, ParentMap p) | |
{ | |
using boost::connected_components; | |
typedef typename graph_traits<DistributedGraph>::adjacency_iterator | |
adjacency_iterator; | |
typedef typename graph_traits<DistributedGraph>::out_edge_iterator | |
out_edge_iterator; | |
typedef typename graph_traits<DistributedGraph>::edge_iterator | |
edge_iterator; | |
typedef typename graph_traits<DistributedGraph>::vertex_descriptor | |
vertex_descriptor; | |
typedef typename graph_traits<DistributedGraph>::edge_descriptor | |
edge_descriptor; | |
typedef typename boost::graph::parallel::process_group_type<DistributedGraph> | |
::type process_group_type; | |
typedef typename process_group_type::process_id_type process_id_type; | |
using boost::graph::parallel::process_group; | |
process_group_type pg = process_group(g); | |
process_id_type id = process_id(pg); | |
// TODO (NGE): Should old_roots, roots, and completed_roots be std::list | |
adjacency_iterator av1, av2; | |
std::vector<vertex_descriptor> old_roots; | |
typename std::vector<vertex_descriptor>::iterator liter; | |
typename std::vector<vertex_descriptor>::iterator aliter; | |
typename std::map<vertex_descriptor, | |
std::vector<vertex_descriptor> > adj; | |
typedef typename property_map<DistributedGraph, vertex_owner_t>::const_type | |
OwnerMap; | |
OwnerMap owner = get(vertex_owner, g); | |
typedef typename property_map<DistributedGraph, vertex_local_t>::const_type | |
LocalMap; | |
LocalMap local = get(vertex_local, g); | |
// We need to hold on to all of the parent pointers | |
p.set_max_ghost_cells(0); | |
// | |
// STAGE 1 : Compute local components | |
// | |
local_subgraph<const DistributedGraph> ls(g); | |
typedef typename property_map<local_subgraph<const DistributedGraph>, | |
vertex_index_t>::type local_index_map_type; | |
local_index_map_type local_index = get(vertex_index, ls); | |
// Compute local connected components | |
std::vector<std::size_t> ls_components_vec(num_vertices(ls)); | |
typedef iterator_property_map<std::vector<std::size_t>::iterator, | |
local_index_map_type> | |
ls_components_map_type; | |
ls_components_map_type ls_component(ls_components_vec.begin(), | |
local_index); | |
std::size_t num_comp = connected_components(ls, ls_component); | |
std::vector<vertex_descriptor> | |
roots(num_comp, graph_traits<DistributedGraph>::null_vertex()); | |
BGL_FORALL_VERTICES_T(v, g, DistributedGraph) { | |
size_t component = get(ls_component, v); | |
if (roots[component] == graph_traits<DistributedGraph>::null_vertex() || | |
get(local_index, v) < get(local_index, roots[component])) | |
roots[component] = v; | |
} | |
// Set all the local parent pointers | |
BGL_FORALL_VERTICES_T(v, g, DistributedGraph) { | |
put(p, v, roots[get(ls_component, v)]); | |
} | |
if (num_processes(pg) == 1) return; | |
// Build adjacency list for all roots | |
BGL_FORALL_VERTICES_T(v, g, DistributedGraph) { | |
std::vector<vertex_descriptor>& my_adj = adj[get(p, v)]; | |
for (boost::tie(av1, av2) = adjacent_vertices(v, g); | |
av1 != av2; ++av1) { | |
if (get(owner, *av1) != id) my_adj.push_back(*av1); | |
} | |
} | |
// For all vertices adjacent to a local vertex get p(v) | |
for ( liter = roots.begin(); liter != roots.end(); ++liter ) { | |
std::vector<vertex_descriptor>& my_adj = adj[*liter]; | |
for ( aliter = my_adj.begin(); aliter != my_adj.end(); ++aliter ) | |
request(p, *aliter); | |
} | |
synchronize(p); | |
// Update adjacency list at root to make sure all adjacent | |
// vertices are roots of remote components | |
for ( liter = roots.begin(); liter != roots.end(); ++liter ) | |
{ | |
std::vector<vertex_descriptor>& my_adj = adj[*liter]; | |
for ( aliter = my_adj.begin(); aliter != my_adj.end(); ++aliter ) | |
*aliter = get(p, *aliter); | |
my_adj.erase | |
(remove_if(my_adj.begin(), my_adj.end(), | |
cull_adjacency_list<vertex_descriptor, | |
ParentMap>(*liter, p) ), | |
my_adj.end()); | |
// This sort needs to be here to make sure the initial | |
// adjacency list is sorted | |
sort(my_adj.begin(), my_adj.end(), std::less<vertex_descriptor>()); | |
my_adj.erase(unique(my_adj.begin(), my_adj.end()), my_adj.end()); | |
} | |
// Get p(v) for the new adjacent roots | |
p.clear(); | |
for ( liter = roots.begin(); liter != roots.end(); ++liter ) { | |
std::vector<vertex_descriptor>& my_adj = adj[*liter]; | |
for ( aliter = my_adj.begin(); aliter != my_adj.end(); ++aliter ) | |
request(p, *aliter); | |
} | |
#ifdef PBGL_EXPLICIT_SYNCH | |
synchronize(p); | |
#endif | |
// Lastly, remove roots with no adjacent vertices, this is | |
// unnecessary but will speed up sparse graphs | |
for ( liter = roots.begin(); liter != roots.end(); /*in loop*/) | |
{ | |
if ( adj[*liter].empty() ) | |
liter = roots.erase(liter); | |
else | |
++liter; | |
} | |
#ifdef PBGL_CONSTRUCT_METAGRAPH | |
/* TODO: If the number of roots is sufficiently small, we can | |
use a 'problem folding' approach like we do in MST | |
to gather all the roots and their adjacencies on one proc | |
and solve for the connected components of the meta-graph */ | |
using boost::parallel::all_reduce; | |
std::size_t num_roots = all_reduce(pg, roots.size(), std::plus<std::size_t>()); | |
if (num_roots < MAX_VERTICES_IN_METAGRAPH) { | |
build_local_metagraph(g, p, roots.begin(), roots.end(), adj); | |
// For each vertex in g, p(v) = p(p(v)), assign parent of leaf | |
// vertices from first step to final parent | |
BGL_FORALL_VERTICES_T(v, g, DistributedGraph) { | |
put(p, v, get(p, get(p, v))); | |
} | |
synchronize(p); | |
return; | |
} | |
#endif | |
// | |
// Parallel Phase | |
// | |
std::vector<vertex_descriptor> completed_roots; | |
hashed_vertex_compare<OwnerMap, LocalMap> v_compare(owner, local); | |
bool any_hooked; | |
vertex_descriptor new_root; | |
std::size_t steps = 0; | |
do { | |
++steps; | |
// Pull in new parents for hooking phase | |
synchronize(p); | |
// | |
// Hooking | |
// | |
bool hooked = false; | |
completed_roots.clear(); | |
for ( liter = roots.begin(); liter != roots.end(); ) | |
{ | |
new_root = graph_traits<DistributedGraph>::null_vertex(); | |
std::vector<vertex_descriptor>& my_adj = adj[*liter]; | |
for ( aliter = my_adj.begin(); aliter != my_adj.end(); ++aliter ) | |
// try to hook to better adjacent vertex | |
if ( v_compare( get(p, *aliter), *liter ) ) | |
new_root = get(p, *aliter); | |
if ( new_root != graph_traits<DistributedGraph>::null_vertex() ) | |
{ | |
hooked = true; | |
put(p, *liter, new_root); | |
old_roots.push_back(*liter); | |
completed_roots.push_back(*liter); | |
liter = roots.erase(liter); | |
} | |
else | |
++liter; | |
} | |
// | |
// Pointer jumping, perform until new roots determined | |
// | |
// TODO: Implement cycle reduction rules to reduce this from | |
// O(n) to O(log n) [n = cycle length] | |
bool all_done; | |
std::size_t parent_root_count; | |
std::size_t double_steps = 0; | |
do { | |
++double_steps; | |
#ifndef PBGL_EXPLICIT_SYNCH | |
// Get p(p(v)) for all old roots, and p(v) for all current roots | |
for ( liter = old_roots.begin(); liter != old_roots.end(); ++liter ) | |
request(p, get(p, *liter)); | |
synchronize(p); | |
#else | |
// Build root requests | |
typedef std::set<vertex_descriptor> VertexSet; | |
std::vector<VertexSet> parent_requests(num_processes(pg)); | |
for ( liter = old_roots.begin(); liter != old_roots.end(); ++liter ) | |
{ | |
vertex_descriptor p1 = *liter; | |
if (get(owner, p1) != id) parent_requests[get(owner, p1)].insert(p1); | |
vertex_descriptor p2 = get(p, p1); | |
if (get(owner, p2) != id) parent_requests[get(owner, p2)].insert(p2); | |
} | |
request_parent_map_entries(g, p, parent_requests); | |
#endif | |
// Perform a pointer jumping step on all old roots | |
for ( liter = old_roots.begin(); liter != old_roots.end(); ++liter ) | |
put(p, *liter, get(p, get(p, *liter))); | |
// make sure the parent of all old roots is itself a root | |
parent_root_count = 0; | |
for ( liter = old_roots.begin(); liter != old_roots.end(); ++liter ) | |
if ( get(p, *liter) == get(p, get(p, *liter)) ) | |
parent_root_count++; | |
bool done = parent_root_count == old_roots.size(); | |
all_reduce(pg, &done, &done+1, &all_done, | |
std::logical_and<bool>()); | |
} while ( !all_done ); | |
#ifdef PARALLEL_BGL_DEBUG | |
if (id == 0) std::cerr << double_steps << " doubling steps.\n"; | |
#endif | |
// | |
// Add adjacent vertices of just completed roots to adjacent | |
// vertex list at new parent | |
// | |
typename std::vector<vertex_descriptor> outgoing_edges; | |
for ( liter = completed_roots.begin(); liter != completed_roots.end(); | |
++liter ) | |
{ | |
vertex_descriptor new_parent = get(p, *liter); | |
if ( get(owner, new_parent) == id ) | |
{ | |
std::vector<vertex_descriptor>& my_adj = adj[new_parent]; | |
my_adj.reserve(my_adj.size() + adj[*liter].size()); | |
my_adj.insert( my_adj.end(), | |
adj[*liter].begin(), adj[*liter].end() ); | |
#ifdef PBGL_IN_PLACE_MERGE | |
#ifdef PBGL_SORT_ASSERT | |
BOOST_ASSERT(__gnu_cxx::is_sorted(my_adj.begin(), | |
my_adj.end() - adj[*liter].size(), | |
std::less<vertex_descriptor>())); | |
BOOST_ASSERT(__gnu_cxx::is_sorted(my_adj.end() - adj[*liter].size(), | |
my_adj.end(), | |
std::less<vertex_descriptor>())); | |
#endif | |
std::inplace_merge(my_adj.begin(), | |
my_adj.end() - adj[*liter].size(), | |
my_adj.end(), | |
std::less<vertex_descriptor>()); | |
#endif | |
} | |
else if ( adj[*liter].begin() != adj[*liter].end() ) | |
{ | |
outgoing_edges.clear(); | |
outgoing_edges.reserve(adj[*liter].size() + 1); | |
// First element is the destination of the adjacency list | |
outgoing_edges.push_back(new_parent); | |
outgoing_edges.insert(outgoing_edges.end(), | |
adj[*liter].begin(), adj[*liter].end() ); | |
send(pg, get(owner, new_parent), edges_msg, outgoing_edges); | |
adj[*liter].clear(); | |
} | |
} | |
synchronize(pg); | |
// Receive edges sent by remote nodes and add them to the | |
// indicated vertex's adjacency list | |
while (optional<std::pair<process_id_type, int> > m | |
= probe(pg)) | |
{ | |
std::vector<vertex_descriptor> incoming_edges; | |
receive(pg, m->first, edges_msg, incoming_edges); | |
typename std::vector<vertex_descriptor>::iterator aviter | |
= incoming_edges.begin(); | |
++aviter; | |
std::vector<vertex_descriptor>& my_adj = adj[incoming_edges[0]]; | |
my_adj.reserve(my_adj.size() + incoming_edges.size() - 1); | |
my_adj.insert( my_adj.end(), aviter, incoming_edges.end() ); | |
#ifdef PBGL_IN_PLACE_MERGE | |
std::size_t num_incoming_edges = incoming_edges.size(); | |
#ifdef PBGL_SORT_ASSERT | |
BOOST_ASSERT(__gnu_cxx::is_sorted(my_adj.begin(), | |
my_adj.end() - (num_incoming_edges-1), | |
std::less<vertex_descriptor>())); | |
BOOST_ASSERT(__gnu_cxx::is_sorted(my_adj.end() - (num_incoming_edges-1), | |
my_adj.end(), | |
std::less<vertex_descriptor>())); | |
#endif | |
std::inplace_merge(my_adj.begin(), | |
my_adj.end() - (num_incoming_edges - 1), | |
my_adj.end(), | |
std::less<vertex_descriptor>()); | |
#endif | |
} | |
// Remove any adjacent vertices that are in the same component | |
// as a root from that root's list | |
for ( liter = roots.begin(); liter != roots.end(); ++liter ) | |
{ | |
// We can probably get away without sorting and removing | |
// duplicates Though sorting *may* cause root | |
// determination to occur faster by choosing the root with | |
// the most potential to hook to at each step | |
std::vector<vertex_descriptor>& my_adj = adj[*liter]; | |
my_adj.erase | |
(remove_if(my_adj.begin(), my_adj.end(), | |
cull_adjacency_list<vertex_descriptor, | |
ParentMap>(*liter, p) ), | |
my_adj.end()); | |
#ifndef PBGL_IN_PLACE_MERGE | |
sort(my_adj.begin(), my_adj.end(), | |
std::less<vertex_descriptor>() ); | |
#endif | |
my_adj.erase(unique(my_adj.begin(), my_adj.end()), my_adj.end()); | |
} | |
// Reduce result of empty root list test | |
all_reduce(pg, &hooked, &hooked+1, &any_hooked, | |
std::logical_or<bool>()); | |
} while ( any_hooked ); | |
#ifdef PARALLEL_BGL_DEBUG | |
if (id == 0) std::cerr << steps << " iterations.\n"; | |
#endif | |
// | |
// Finalize | |
// | |
// For each vertex in g, p(v) = p(p(v)), assign parent of leaf | |
// vertices from first step to final parent | |
BGL_FORALL_VERTICES_T(v, g, DistributedGraph) { | |
put(p, v, get(p, get(p, v))); | |
} | |
synchronize(p); | |
} | |
} // end namespace cc_detail | |
template<typename Graph, typename ParentMap, typename ComponentMap> | |
typename property_traits<ComponentMap>::value_type | |
number_components_from_parents(const Graph& g, ParentMap p, ComponentMap c) | |
{ | |
typedef typename graph_traits<Graph>::vertex_descriptor | |
vertex_descriptor; | |
typedef typename boost::graph::parallel::process_group_type<Graph>::type | |
process_group_type; | |
typedef typename property_traits<ComponentMap>::value_type | |
ComponentMapType; | |
process_group_type pg = process_group(g); | |
/* Build list of roots */ | |
std::vector<vertex_descriptor> my_roots, all_roots; | |
BGL_FORALL_VERTICES_T(v, g, Graph) { | |
if( find( my_roots.begin(), my_roots.end(), get(p, v) ) | |
== my_roots.end() ) | |
my_roots.push_back( get(p, v) ); | |
} | |
all_gather(pg, my_roots.begin(), my_roots.end(), all_roots); | |
/* Number components */ | |
std::map<vertex_descriptor, ComponentMapType> comp_numbers; | |
ComponentMapType c_num = 0; | |
// Compute component numbers | |
for (std::size_t i = 0; i < all_roots.size(); i++ ) | |
if ( comp_numbers.count(all_roots[i]) == 0 ) | |
comp_numbers[all_roots[i]] = c_num++; | |
// Broadcast component numbers | |
BGL_FORALL_VERTICES_T(v, g, Graph) { | |
put( c, v, comp_numbers[get(p, v)] ); | |
} | |
// Broadcast number of components | |
if (process_id(pg) == 0) { | |
typedef typename process_group_type::process_size_type | |
process_size_type; | |
for (process_size_type dest = 1, n = num_processes(pg); | |
dest != n; ++dest) | |
send(pg, dest, 0, c_num); | |
} | |
synchronize(pg); | |
if (process_id(pg) != 0) receive(pg, 0, 0, c_num); | |
synchronize(c); | |
return c_num; | |
} | |
template<typename Graph, typename ParentMap> | |
int | |
number_components_from_parents(const Graph& g, ParentMap p, | |
dummy_property_map) | |
{ | |
using boost::parallel::all_reduce; | |
// Count local roots. | |
int num_roots = 0; | |
BGL_FORALL_VERTICES_T(v, g, Graph) | |
if (get(p, v) == v) ++num_roots; | |
return all_reduce(g.process_group(), num_roots, std::plus<int>()); | |
} | |
template<typename Graph, typename ComponentMap, typename ParentMap> | |
typename property_traits<ComponentMap>::value_type | |
connected_components | |
(const Graph& g, ComponentMap c, ParentMap p | |
BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, distributed_graph_tag)) | |
{ | |
cc_detail::parallel_connected_components(g, p); | |
return number_components_from_parents(g, p, c); | |
} | |
/* Construct ParentMap by default */ | |
template<typename Graph, typename ComponentMap> | |
typename property_traits<ComponentMap>::value_type | |
connected_components | |
( const Graph& g, ComponentMap c | |
BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, distributed_graph_tag) ) | |
{ | |
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; | |
std::vector<vertex_descriptor> x(num_vertices(g)); | |
return connected_components | |
(g, c, | |
make_iterator_property_map(x.begin(), get(vertex_index, g))); | |
} | |
} // end namespace distributed | |
using distributed::connected_components; | |
} // end namespace graph | |
using graph::distributed::connected_components; | |
} // end namespace boost | |
#endif // BOOST_GRAPH_PARALLEL_CC_HPP |