Good Morning,
I am trying to use the parallel BGL to compute the weakly connected components of a graph. I have managed to obtain the correct results with the code pasted below, however I am getting the following times:
- Sequential BGL 0.01 seconds
- Parallel BGL on 1 core 0.04 seconds
- Parallel BGL on 2 cores 0.64 seconds
That doesn’t look right to me. What am I doing wrong?
using namespace boost;
using boost::graph::distributed::mpi_process_group;
typedef adjacency_list, undirectedS> Graph;
typedef iterator_property_map::type> LocalMap;
int getConnectedComponents(std::vector< std::pair > &arcs, const std::vector<int> &isActive) {
// Allocate structures
Graph G(nV+1);
std::vector<int> localComponent(nV+1);
std::vector<int> globalComponent(nV+1);
// Only rank 0 has got the arc data structure
if( rank == 0 ) {
// Add dummy edges to each vertex (required to avoid BGL crash for a single node with no edges)
for( int i=0; i >::iterator it = arcs.begin(); it != arcs.end(); ++it)
if( isActive[arcCnt++]==0 )
add_edge(vertex(it->first,G),vertex(it->second,G),G);
}
synchronize(G);
// Compute number of connected components
LocalMap components(localComponent.begin(),get(vertex_index, G));
int num = connected_components_ps(G, components);
// Let rank 0 collect the global component vector
if( rank == 0 ) {
components.set_max_ghost_cells(0);
for( PetscInt i = 0; i < nV+1; i++ ) globalComponent[i] = get(components, vertex(i, G));
}
synchronize(components);
}
Regards,
-------------------------------------------------
Alessio Quaglino
Postdoctoral Researcher
University of Lugano
