On 14 Dec 2015, at 11:29, Quaglino Alessio <quagla@usi.ch> wrote:

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<vecS, distributedS<mpi_process_group, vecS>, undirectedS> Graph;

typedef iterator_property_map<std::vector<int>::iterator, property_map<Graph, vertex_index_t>::type> LocalMap;

int getConnectedComponents(std::vector< std::pair<int,int> > &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<nV; i++ ) add_edge(vertex(i,G),vertex(i,G),G);

        

        // Add edges to the graph

        for(std::vector<std::pair<int,int> >::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