[BGL] Connected components of a distributed graph with few edges
Hello, I am trying to compute the number of connected components of a graph with only few edges (i.e. many vertices do not have edges). This works OK for a non-distributed graph. The simplest example of the issue I could come up with is the following: typedef adjacency_list <vecS, vecS, undirectedS> SerialGraph; 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; #ifdef PARALLEL_GRAPH Graph G(nV+1); synchronize(G); std::vector<int> localComponent(nV+1); LocalMap components(localComponent.begin(),get(vertex_index, G)); num = connected_components_ps(G, components); #else SerialGraph G(nV+1); std::vector<int> globalComponent(nV+1); num = connected_components(G, &globalComponent[0]); #endif The distributed version causes a seg fault when calling connected_components_ps, while the non-distributed works fine and correctly finds nV+1 components. If I populate the graph connecting all vertices with edges, both do work fine. What am I doing wrong? Thank you in advance. Regards, Alessio
Is anyone using the parallel BGL? The following code gives me a segmentation fault for the parallel case but I can’t figure out what can be wrong. You can replace PetscInitialize and PetscFinalize with the respective standard MPI calls. Regards, Alessio Quaglino #define PARALLEL_GRAPH using namespace boost; using boost::graph::distributed::mpi_process_group; typedef adjacency_list <vecS, vecS, undirectedS> SerialGraph; 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; static char help[] = ""; int main(int argc,char **args) { PetscErrorCode ierr; PetscInitialize(&argc,&args,(char*)0,help); int nV = 40000; int num = 0; #ifdef PARALLEL_GRAPH Graph G(nV+1); synchronize(G); std::vector<int> localComponent(nV+1); LocalMap components(localComponent.begin(),get(vertex_index, G)); num = connected_components_ps(G, components); #else SerialGraph G(nV+1); std::vector<int> globalComponent(nV+1); num = connected_components(G, &globalComponent[0]); #endif std::cout << num << " connected components" << std::endl; ierr = PetscFinalize(); return 0; }
On Nov 2, 2015 6:55 AM, "Quaglino Alessio" <alessio.quaglino@usi.ch> wrote:
Is anyone using the parallel BGL? The following code gives me a
Regards, Alessio Quaglino
#define PARALLEL_GRAPH
using namespace boost; using boost::graph::distributed::mpi_process_group;
typedef adjacency_list <vecS, vecS, undirectedS> SerialGraph; typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>, undirectedS> Graph; typedef iterator_property_map<std::vector<int>::iterator,
segmentation fault for the parallel case but I can’t figure out what can be wrong. You can replace PetscInitialize and PetscFinalize with the respective standard MPI calls. Could you try with fewer vertices (just a few) and see if this still happens? If it does, can you try to add some edges and see if it makes a difference? A couple more things to try is to use a single MPI process and dummy_property_map. See if any of these steps make a difference. property_map<Graph, vertex_index_t>::type> LocalMap;
static char help[] = "";
int main(int argc,char **args) { PetscErrorCode ierr; PetscInitialize(&argc,&args,(char*)0,help);
int nV = 40000; int num = 0;
#ifdef PARALLEL_GRAPH Graph G(nV+1); synchronize(G); std::vector<int> localComponent(nV+1); LocalMap components(localComponent.begin(),get(vertex_index, G)); num = connected_components_ps(G, components); #else SerialGraph G(nV+1); std::vector<int> globalComponent(nV+1); num = connected_components(G, &globalComponent[0]); #endif
std::cout << num << " connected components" << std::endl;
ierr = PetscFinalize(); return 0; }
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Thanks for the reply. I am getting a seg fault even with nV=1.. Alessio On 02 Nov 2015, at 13:50, Marcin Zalewski <marcin.zalewski@gmail.com<mailto:marcin.zalewski@gmail.com>> wrote: On Nov 2, 2015 6:55 AM, "Quaglino Alessio" <alessio.quaglino@usi.ch<mailto:alessio.quaglino@usi.ch>> wrote:
Is anyone using the parallel BGL? The following code gives me a segmentation fault for the parallel case but I can’t figure out what can be wrong. You can replace PetscInitialize and PetscFinalize with the respective standard MPI calls.
Could you try with fewer vertices (just a few) and see if this still happens? If it does, can you try to add some edges and see if it makes a difference? A couple more things to try is to use a single MPI process and dummy_property_map. See if any of these steps make a difference.
Regards, Alessio Quaglino
#define PARALLEL_GRAPH
using namespace boost; using boost::graph::distributed::mpi_process_group;
typedef adjacency_list <vecS, vecS, undirectedS> SerialGraph; 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;
static char help[] = "";
int main(int argc,char **args) { PetscErrorCode ierr; PetscInitialize(&argc,&args,(char*)0,help);
int nV = 40000; int num = 0;
#ifdef PARALLEL_GRAPH Graph G(nV+1); synchronize(G); std::vector<int> localComponent(nV+1); LocalMap components(localComponent.begin(),get(vertex_index, G)); num = connected_components_ps(G, components); #else SerialGraph G(nV+1); std::vector<int> globalComponent(nV+1); num = connected_components(G, &globalComponent[0]); #endif
std::cout << num << " connected components" << std::endl;
ierr = PetscFinalize(); return 0; }
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org<mailto:Boost-users@lists.boost.org> http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org<mailto:Boost-users@lists.boost.org> http://lists.boost.org/mailman/listinfo.cgi/boost-users
Is it possible to get a stack trace? Also, have you tried any of the other things I suggested? On Mon, Nov 2, 2015 at 8:48 AM Quaglino Alessio <alessio.quaglino@usi.ch> wrote:
Thanks for the reply. I am getting a seg fault even with nV=1..
Alessio
On 02 Nov 2015, at 13:50, Marcin Zalewski <marcin.zalewski@gmail.com> wrote:
On Nov 2, 2015 6:55 AM, "Quaglino Alessio" <alessio.quaglino@usi.ch> wrote:
Is anyone using the parallel BGL? The following code gives me a
segmentation fault for the parallel case but I can’t figure out what can be wrong. You can replace PetscInitialize and PetscFinalize with the respective standard MPI calls.
Could you try with fewer vertices (just a few) and see if this still happens? If it does, can you try to add some edges and see if it makes a difference? A couple more things to try is to use a single MPI process and dummy_property_map. See if any of these steps make a difference.
Regards, Alessio Quaglino
#define PARALLEL_GRAPH
using namespace boost; using boost::graph::distributed::mpi_process_group;
typedef adjacency_list <vecS, vecS, undirectedS> SerialGraph; 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;
static char help[] = "";
int main(int argc,char **args) { PetscErrorCode ierr; PetscInitialize(&argc,&args,(char*)0,help);
int nV = 40000; int num = 0;
#ifdef PARALLEL_GRAPH Graph G(nV+1); synchronize(G); std::vector<int> localComponent(nV+1); LocalMap components(localComponent.begin(),get(vertex_index, G)); num = connected_components_ps(G, components); #else SerialGraph G(nV+1); std::vector<int> globalComponent(nV+1); num = connected_components(G, &globalComponent[0]); #endif
std::cout << num << " connected components" << std::endl;
ierr = PetscFinalize(); return 0; }
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
I have compiled with debug symbols and I got the following launching with mpirun -np 1 [alessios-mbp:95195] *** Process received signal *** [alessios-mbp:95195] Signal: Abort trap: 6 (6) [alessios-mbp:95195] Signal code: (0) [alessios-mbp:95195] [ 0] 0 libsystem_platform.dylib 0x00007fff8d8baf1a _sigtramp + 26 [alessios-mbp:95195] [ 1] 0 ??? 0x00007fff5cfe3d20 0x0 + 140734753553696 [alessios-mbp:95195] [ 2] 0 libsystem_c.dylib 0x00007fff89e929b3 abort + 129 [alessios-mbp:95195] [ 3] 0 libpetsc.3.6.dylib 0x0000000103090c66 PetscAbortErrorHandler + 486 [alessios-mbp:95195] [ 4] 0 libpetsc.3.6.dylib 0x00000001030897b7 PetscError + 1223 [alessios-mbp:95195] [ 5] 0 libpetsc.3.6.dylib 0x0000000103092d41 PetscSignalHandlerDefault + 2305 [alessios-mbp:95195] [ 6] 0 libpetsc.3.6.dylib 0x00000001030937f3 PetscSignalHandler_Private + 595 [alessios-mbp:95195] [ 7] 0 libsystem_platform.dylib 0x00007fff8d8baf1a _sigtramp + 26 [alessios-mbp:95195] [ 8] 0 ??? 0x00007feeea4c6e98 0x0 + 140664109821592 [alessios-mbp:95195] [ 9] 0 interiorpoint_graphonly 0x0000000102c83c84 _ZNK5boost6detail8parallel15edge_descriptorINS0_14edge_desc_implINS_12directed_tagEmEEE13out_generatorINS_14adjacency_listINS_4vecSENS_12distributedSINS_5graph11distributed17mpi_process_groupES9_NS_8defaultSEEENS_11undirectedSENS_11no_propertyESH_SH_NS_5listSEEEEclES5_ + 84 [alessios-mbp:95195] [10] 0 interiorpoint_graphonly 0x0000000102c83c17 _ZNK5boost9iterators18transform_iteratorINS_6detail8parallel15edge_descriptorINS2_14edge_desc_implINS_12directed_tagEmEEE13out_generatorINS_14adjacency_listINS_4vecSENS_12distributedSINS_5graph11distributed17mpi_process_groupESB_NS_8defaultSEEENS_11undirectedSENS_11no_propertyESJ_SJ_NS_5listSEEEEENS2_13out_edge_iterINSt3__111__wrap_iterIPNS2_20stored_edge_propertyImNS_8propertyINS_20edge_locally_owned_tEbNSR_INS_26edge_target_processor_id_tEsSJ_EEEEEEEEmS7_lEENS0_11use_defaultES10_E11dereferenceEv + 103 [alessios-mbp:95195] [11] 0 interiorpoint_graphonly 0x0000000102c83b7c _ZN5boost9iterators20iterator_core_access11dereferenceINS0_18transform_iteratorINS_6detail8parallel15edge_descriptorINS4_14edge_desc_implINS_12directed_tagEmEEE13out_generatorINS_14adjacency_listINS_4vecSENS_12distributedSINS_5graph11distributed17mpi_process_groupESD_NS_8defaultSEEENS_11undirectedSENS_11no_propertyESL_SL_NS_5listSEEEEENS4_13out_edge_iterINSt3__111__wrap_iterIPNS4_20stored_edge_propertyImNS_8propertyINS_20edge_locally_owned_tEbNST_INS_26edge_target_processor_id_tEsSL_EEEEEEEEmS9_lEENS0_11use_defaultES12_EEEENT_9referenceERKS14_ + 28 [alessios-mbp:95195] [12] 0 interiorpoint_graphonly 0x0000000102c83b4f _ZNK5boost9iterators6detail20iterator_facade_baseINS0_18transform_iteratorINS_6detail8parallel15edge_descriptorINS4_14edge_desc_implINS_12directed_tagEmEEE13out_generatorINS_14adjacency_listINS_4vecSENS_12distributedSINS_5graph11distributed17mpi_process_groupESD_NS_8defaultSEEENS_11undirectedSENS_11no_propertyESL_SL_NS_5listSEEEEENS4_13out_edge_iterINSt3__111__wrap_iterIPNS4_20stored_edge_propertyImNS_8propertyINS_20edge_locally_owned_tEbNST_INS_26edge_target_processor_id_tEsSL_EEEEEEEEmS9_lEENS0_11use_defaultES12_EESA_NS1_32iterator_category_with_traversalINSQ_18input_iterator_tagENS0_27random_access_traversal_tagEEESA_lLb0ELb0EEdeEv + 47 [alessios-mbp:95195] [13] 0 interiorpoint_graphonly 0x0000000102c83af5 _ZNK5boost18adjacency_iteratorINS_14adjacency_listINS_4vecSENS_12distributedSINS_5graph11distributed17mpi_process_groupES2_NS_8defaultSEEENS_11undirectedSENS_11no_propertyESA_SA_NS_5listSEEENS_6detail8parallel17global_descriptorImEENS_9iterators18transform_iteratorINSE_15edge_descriptorINSD_14edge_desc_implINS_12directed_tagEmEEE13out_generatorISC_EENSD_13out_edge_iterINSt3__111__wrap_iterIPNSD_20stored_edge_propertyImNS_8propertyINS_20edge_locally_owned_tEbNSU_INS_26edge_target_processor_id_tEsSA_EEEEEEEEmSM_lEENSH_11use_defaultES13_EElE11dereferenceEv + 37 [alessios-mbp:95195] [14] 0 interiorpoint_graphonly 0x0000000102c83a91 _ZN5boost9iterators20iterator_core_access11dereferenceINS_18adjacency_iteratorINS_14adjacency_listINS_4vecSENS_12distributedSINS_5graph11distributed17mpi_process_groupES5_NS_8defaultSEEENS_11undirectedSENS_11no_propertyESD_SD_NS_5listSEEENS_6detail8parallel17global_descriptorImEENS0_18transform_iteratorINSH_15edge_descriptorINSG_14edge_desc_implINS_12directed_tagEmEEE13out_generatorISF_EENSG_13out_edge_iterINSt3__111__wrap_iterIPNSG_20stored_edge_propertyImNS_8propertyINS_20edge_locally_owned_tEbNSW_INS_26edge_target_processor_id_tEsSD_EEEEEEEEmSO_lEENS0_11use_defaultES15_EElEEEENT_9referenceERKS18_ + 17 [alessios-mbp:95195] [15] 0 interiorpoint_graphonly 0x0000000102c69249 _ZNK5boost9iterators6detail20iterator_facade_baseINS_18adjacency_iteratorINS_14adjacency_listINS_4vecSENS_12distributedSINS_5graph11distributed17mpi_process_groupES5_NS_8defaultSEEENS_11undirectedSENS_11no_propertyESD_SD_NS_5listSEEENS_6detail8parallel17global_descriptorImEENS0_18transform_iteratorINSH_15edge_descriptorINSG_14edge_desc_implINS_12directed_tagEmEEE13out_generatorISF_EENSG_13out_edge_iterINSt3__111__wrap_iterIPNSG_20stored_edge_propertyImNS_8propertyINS_20edge_locally_owned_tEbNSW_INS_26edge_target_processor_id_tEsSD_EEEEEEEEmSO_lEENS0_11use_defaultES15_EElEESJ_NS1_32iterator_category_with_traversalINST_18input_iterator_tagENS0_27random_access_traversal_tagEEESJ_lLb0ELb0EEdeEv + 25 [alessios-mbp:95195] [16] 0 interiorpoint_graphonly 0x0000000102c1c61e _ZN5boost5graph11distributed23connected_components_psINS_14adjacency_listINS_4vecSENS_12distributedSINS1_17mpi_process_groupES4_NS_8defaultSEEENS_11undirectedSENS_11no_propertyESA_SA_NS_5listSEEENS_21iterator_property_mapINSt3__111__wrap_iterIPiEENS_18local_property_mapIS6_NS_6detail8parallel30global_descriptor_property_mapImEENS_26vec_adj_list_vertex_id_mapISA_mEEEEiRiEEEENS_15property_traitsIT0_E10value_typeERKT_ST_ + 2734 [alessios-mbp:95195] [17] 0 interiorpoint_graphonly 0x0000000102c1a8a7 main + 423 [alessios-mbp:95195] [18] 0 libdyld.dylib 0x00007fff94d385c9 start + 1 [alessios-mbp:95195] [19] 0 ??? 0x0000000000000002 0x0 + 2 [alessios-mbp:95195] *** End of error message *** As for your suggestions: Single MPI process - I get the crash anyway (as said above) Adding edges until there is only a single connected component solves the issue, but of course it also makes the computation trivial. Dummy_property_map - I am not sure how to use this. Thanks, Alessio On 02 Nov 2015, at 15:21, Marcin Zalewski <marcin.zalewski@gmail.com<mailto:marcin.zalewski@gmail.com>> wrote: Is it possible to get a stack trace? Also, have you tried any of the other things I suggested? On Mon, Nov 2, 2015 at 8:48 AM Quaglino Alessio <alessio.quaglino@usi.ch<mailto:alessio.quaglino@usi.ch>> wrote: Thanks for the reply. I am getting a seg fault even with nV=1.. Alessio On 02 Nov 2015, at 13:50, Marcin Zalewski <marcin.zalewski@gmail.com<mailto:marcin.zalewski@gmail.com>> wrote: On Nov 2, 2015 6:55 AM, "Quaglino Alessio" <alessio.quaglino@usi.ch<mailto:alessio.quaglino@usi.ch>> wrote:
Is anyone using the parallel BGL? The following code gives me a segmentation fault for the parallel case but I can’t figure out what can be wrong. You can replace PetscInitialize and PetscFinalize with the respective standard MPI calls.
Could you try with fewer vertices (just a few) and see if this still happens? If it does, can you try to add some edges and see if it makes a difference? A couple more things to try is to use a single MPI process and dummy_property_map. See if any of these steps make a difference.
Regards, Alessio Quaglino
#define PARALLEL_GRAPH
using namespace boost; using boost::graph::distributed::mpi_process_group;
typedef adjacency_list <vecS, vecS, undirectedS> SerialGraph; 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;
static char help[] = "";
int main(int argc,char **args) { PetscErrorCode ierr; PetscInitialize(&argc,&args,(char*)0,help);
int nV = 40000; int num = 0;
#ifdef PARALLEL_GRAPH Graph G(nV+1); synchronize(G); std::vector<int> localComponent(nV+1); LocalMap components(localComponent.begin(),get(vertex_index, G)); num = connected_components_ps(G, components); #else SerialGraph G(nV+1); std::vector<int> globalComponent(nV+1); num = connected_components(G, &globalComponent[0]); #endif
std::cout << num << " connected components" << std::endl;
ierr = PetscFinalize(); return 0; }
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org<mailto:Boost-users@lists.boost.org> http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org<mailto:Boost-users@lists.boost.org> http://lists.boost.org/mailman/listinfo.cgi/boost-users _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org<mailto:Boost-users@lists.boost.org> http://lists.boost.org/mailman/listinfo.cgi/boost-users _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org<mailto:Boost-users@lists.boost.org> http://lists.boost.org/mailman/listinfo.cgi/boost-users
Please find below the stack trace in GDB. As I said, I have tried a single process and it crashes anyway. If I add edges, then it doesn’t crash anymore. I also paste again the entire program below in case you want to try it. I can’t figure out what’s wrong and therefore I have to decide whether I need to stop using BOOST for this task. Thanks, Alessio Program received signal SIGSEGV, Segmentation fault. 0x000000010006ace3 in boost::detail::parallel::edge_descriptor<boost::detail::edge_desc_impl<boost::directed_tag, unsigned long> >::out_generator<boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS, boost::defaultS>, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS> >::map(boost::detail::edge_desc_impl<boost::directed_tag, unsigned long>, boost::undirectedS) const () (gdb) stack Undefined command: "stack". Try "help". (gdb) backtrace #0 0x000000010006ace3 in boost::detail::parallel::edge_descriptor<boost::detail::edge_desc_impl<boost::directed_tag, unsigned long> >::out_generator<boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS, boost::defaultS>, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS> >::map(boost::detail::edge_desc_impl<boost::directed_tag, unsigned long>, boost::undirectedS) const () #1 0x000000010006ac84 in boost::detail::parallel::edge_descriptor<boost::detail::edge_desc_impl<boost::directed_tag, unsigned long> >::out_generator<boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS, boost::defaultS>, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS> >::operator()(boost::detail::edge_desc_impl<boost::directed_tag, unsigned long>) const () #2 0x000000010006ac17 in boost::iterators::transform_iterator<boost::detail::parallel::edge_descriptor<boost::detail::edge_desc_impl<boost::directed_tag, unsigned long> >::out_generator<boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS, boost::defaultS>, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS> >, boost::detail::out_edge_iter<std::__1::__wrap_iter<boost::detail::stored_edge_property<unsigned long, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short, boost::no_property> > >*>, unsigned long, boost::detail::edge_desc_impl<boost::directed_tag, unsigned long>, long>, boost::iterators::use_default, boost::iterators::use_default>::dereference() const () #3 0x000000010006ab7c in boost::iterators::transform_iterator<boost::detail::parallel::edge_descriptor<boost::detail::edge_desc_impl<boost::directed_tag, unsigned long> >::out_generator<boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS, boost::defaultS>, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS> >, boost::detail::out_edge_iter<std::__1::__wrap_iter<boost::detail::stored_edge_property<unsigned long, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short, boost::no_property> > >*>, unsigned long, boost::detail::edge_desc_impl<boost::directed_tag, unsigned long>, long>, boost::iterators::use_default, boost::iterators::use_default>::reference boost::iterators::iterator_core_access::dereference<boost::iterators::transform_iterator<boost::detail::parallel::edge_descriptor<boost::detail::edge_desc_impl<boost::directed_tag, unsigned long> >::out_generator<boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS, boost::defaultS>, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS> >, boost::detail::out_edge_iter<std::__1::__wrap_iter<boost::detail::stored_edge_property<unsigned long, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short, boost::no_property> > >*>, unsigned long, boost::detail::edge_desc_impl<boost::directed_tag, unsigned long>, long>, boost::iterators::use_default, boost::iterators::use_default> >(boost::iterators::transform_iterator<boost::detail::parallel::edge_descriptor<boost::detail::edge_desc_impl<boost::directed_tag, unsigned long> >::out_generator<boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS, boost::defaultS>, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS> >, boost::detail::out_edge_iter<std::__1::__wrap_iter<boost::detail::stored_edge_property<unsigned long, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short, boost::no_property> > >*>, unsigned long, boost::detail::edge_desc_impl<boost::directed_tag, unsigned long>, long>, boost::iterators::use_default, boost::iterators::use_default> const&) () #4 0x000000010006ab4f in boost::iterators::detail::iterator_facade_base<boost::iterators::transform_iterator<boost::detail::parallel::edge_descriptor<boost::detail::edge_desc_impl<boost::directed_tag, unsigned long> >::out_generator<boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS, boost::defaultS>, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS> >, boost::detail::out_edge_iter<std::__1::__wrap_iter<boost::detail::stored_edge_property<unsigned long, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short, boost::no_property> > >*>, unsigned long, boost::detail::edge_desc_impl<boost::directed_tag, unsigned long>, long>, boost::iterators::use_default, boost::iterators::use_default>, boost::detail::parallel::edge_descriptor<boost::detail::edge_desc_impl<boost::directed_tag, unsigned long> >, boost::iterators::detail::iterator_category_with_traversal<std::__1::input_iterator_tag, boost::iterators::random_access_traversal_tag>, boost::detail::parallel::edge_descriptor<boost::detail::edge_desc_impl<boost::directed_tag, unsigned long> >, long, false, false>::operator*() const () #5 0x000000010006aaf5 in boost::adjacency_iterator<boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS, boost::defaultS>, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, boost::detail::parallel::global_descriptor<unsigned long>, boost::iterators::transform_iterator<boost::detail::parallel::edge_descriptor<boost::detail::edge_desc_impl<boost::directed_tag, unsigned long> >::out_generator<boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS, boost::defaultS>, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS> >, boost::detail::out_edge_iter<std::__1::__wrap_iter<boost::detail::stored_edge_property<unsigned long, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short, boost::no_property> > >*>, unsigned long, boost::detail::edge_desc_impl<boost::directed_tag, unsigned long>, long>, boost::iterators::use_default, boost::iterators::use_default>, long>::dereference() const () #6 0x000000010006aa91 in boost::adjacency_iterator<boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS, boost::defaultS>, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, boost::detail::parallel::global_descriptor<unsigned long>, boost::iterators::transform_iterator<boost::detail::parallel::edge_descriptor<boost::detail::edge_desc_impl<boost::directed_tag, unsigned long> >::out_generator<boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS, boost::defaultS>, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS> >, boost::detail::out_edge_iter<std::__1::__wrap_iter<boost::detail::stored_edge_property<unsigned long, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short, boost::no_property> > >*>, unsigned long, boost::detail::edge_desc_impl<boost::directed_tag, unsigned lon---Type <return> to continue, or q <return> to quit--- #define PARALLEL_GRAPH using namespace boost; using boost::graph::distributed::mpi_process_group; typedef adjacency_list <vecS, vecS, undirectedS> SerialGraph; 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; static char help[] = ""; int main(int argc,char **args) { PetscErrorCode ierr; PetscInitialize(&argc,&args,(char*)0,help); int nV = 1; int num = 0; #ifdef PARALLEL_GRAPH Graph G(nV+1); synchronize(G); std::vector<int> localComponent(nV+1); LocalMap components(localComponent.begin(),get(vertex_index, G)); num = connected_components_ps(G, components); #else SerialGraph G(nV+1); std::vector<int> globalComponent(nV+1); num = connected_components(G, &globalComponent[0]); #endif std::cout << num << " connected components" << std::endl; ierr = PetscFinalize(); return 0; }
This was missing in the trace g>, long>, boost::iterators::use_default, boost::iterators::use_default>, long>::reference boost::iterators::iterator_core_access::dereference<boost::adjacency_iterator<boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS, boost::defaultS>, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, boost::detail::parallel::global_descriptor<unsigned long>, boost::iterators::transform_iterator<boost::detail::parallel::edge_descriptor<boost::detail::edge_desc_impl<boost::directed_tag, unsigned long> >::out_generator<boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS, boost::defaultS>, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS> >, boost::detail::out_edge_iter<std::__1::__wrap_iter<boost::detail::stored_edge_property<unsigned long, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short, boost::no_property> > >*>, unsigned long, boost::detail::edge_desc_impl<boost::directed_tag, unsigned long>, long>, boost::iterators::use_default, boost::iterators::use_default>, long> >(boost::adjacency_iterator<boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS, boost::defaultS>, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, boost::detail::parallel::global_descriptor<unsigned long>, boost::iterators::transform_iterator<boost::detail::parallel::edge_descriptor<boost::detail::edge_desc_impl<boost::directed_tag, unsigned long> >::out_generator<boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS, boost::defaultS>, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS> >, boost::detail::out_edge_iter<std::__1::__wrap_iter<boost::detail::stored_edge_property<unsigned long, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short, boost::no_property> > >*>, unsigned long, boost::detail::edge_desc_impl<boost::directed_tag, unsigned long>, long>, boost::iterators::use_default, boost::iterators::use_default>, long> const&) () #7 0x0000000100050249 in boost::iterators::detail::iterator_facade_base<boost::adjacency_iterator<boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS, boost::defaultS>, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, boost::detail::parallel::global_descriptor<unsigned long>, boost::iterators::transform_iterator<boost::detail::parallel::edge_descriptor<boost::detail::edge_desc_impl<boost::directed_tag, unsigned long> >::out_generator<boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS, boost::defaultS>, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS> >, boost::detail::out_edge_iter<std::__1::__wrap_iter<boost::detail::stored_edge_property<unsigned long, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short, boost::no_property> > >*>, unsigned long, boost::detail::edge_desc_impl<boost::directed_tag, unsigned long>, long>, boost::iterators::use_default, boost::iterators::use_default>, long>, boost::detail::parallel::global_descriptor<unsigned long>, boost::iterators::detail::iterator_category_with_traversal<std::__1::input_iterator_tag, boost::iterators::random_access_traversal_tag>, boost::detail::parallel::global_descriptor<unsigned long>, long, false, false>::operator*() const () #8 0x000000010000361e in boost::property_traits<boost::iterator_property_map<std::__1::__wrap_iter<int*>, boost::local_property_map<boost::graph::distributed::mpi_process_group, boost::detail::parallel::global_descriptor_property_map<unsigned long>, boost::vec_adj_list_vertex_id_map<boost::no_property, unsigned long> >, int, int&> >::value_type boost::graph::distributed::connected_components_ps<boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS, boost::defaultS>, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, boost::iterator_property_map<std::__1::__wrap_iter<int*>, boost::local_property_map<boost::graph::distributed::mpi_process_group, boost::detail::parallel::global_descriptor_property_map<unsigned long>, boost::vec_adj_list_vertex_id_map<boost::no_property, unsigned long> >, int, int&> >(boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS, boost::defaultS>, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS> const&, boost::iterator_property_map<std::__1::__wrap_iter<int*>, boost::local_property_map<boost::graph::distributed::mpi_process_group, boost::detail::parallel::global_descriptor_property_map<unsigned long>, boost::vec_adj_list_vertex_id_map<boost::no_property, unsigned long> >, int, int&>) () #9 0x00000001000018a7 in main () On 05 Nov 2015, at 16:48, Quaglino Alessio <quagla@usi.ch<mailto:quagla@usi.ch>> wrote: Please find below the stack trace in GDB. As I said, I have tried a single process and it crashes anyway. If I add edges, then it doesn’t crash anymore. I also paste again the entire program below in case you want to try it. I can’t figure out what’s wrong and therefore I have to decide whether I need to stop using BOOST for this task. Thanks, Alessio Program received signal SIGSEGV, Segmentation fault. 0x000000010006ace3 in boost::detail::parallel::edge_descriptor<boost::detail::edge_desc_impl<boost::directed_tag, unsigned long> >::out_generator<boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS, boost::defaultS>, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS> >::map(boost::detail::edge_desc_impl<boost::directed_tag, unsigned long>, boost::undirectedS) const () (gdb) stack Undefined command: "stack". Try "help". (gdb) backtrace #0 0x000000010006ace3 in boost::detail::parallel::edge_descriptor<boost::detail::edge_desc_impl<boost::directed_tag, unsigned long> >::out_generator<boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS, boost::defaultS>, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS> >::map(boost::detail::edge_desc_impl<boost::directed_tag, unsigned long>, boost::undirectedS) const () #1 0x000000010006ac84 in boost::detail::parallel::edge_descriptor<boost::detail::edge_desc_impl<boost::directed_tag, unsigned long> >::out_generator<boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS, boost::defaultS>, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS> >::operator()(boost::detail::edge_desc_impl<boost::directed_tag, unsigned long>) const () #2 0x000000010006ac17 in boost::iterators::transform_iterator<boost::detail::parallel::edge_descriptor<boost::detail::edge_desc_impl<boost::directed_tag, unsigned long> >::out_generator<boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS, boost::defaultS>, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS> >, boost::detail::out_edge_iter<std::__1::__wrap_iter<boost::detail::stored_edge_property<unsigned long, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short, boost::no_property> > >*>, unsigned long, boost::detail::edge_desc_impl<boost::directed_tag, unsigned long>, long>, boost::iterators::use_default, boost::iterators::use_default>::dereference() const () #3 0x000000010006ab7c in boost::iterators::transform_iterator<boost::detail::parallel::edge_descriptor<boost::detail::edge_desc_impl<boost::directed_tag, unsigned long> >::out_generator<boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS, boost::defaultS>, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS> >, boost::detail::out_edge_iter<std::__1::__wrap_iter<boost::detail::stored_edge_property<unsigned long, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short, boost::no_property> > >*>, unsigned long, boost::detail::edge_desc_impl<boost::directed_tag, unsigned long>, long>, boost::iterators::use_default, boost::iterators::use_default>::reference boost::iterators::iterator_core_access::dereference<boost::iterators::transform_iterator<boost::detail::parallel::edge_descriptor<boost::detail::edge_desc_impl<boost::directed_tag, unsigned long> >::out_generator<boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS, boost::defaultS>, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS> >, boost::detail::out_edge_iter<std::__1::__wrap_iter<boost::detail::stored_edge_property<unsigned long, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short, boost::no_property> > >*>, unsigned long, boost::detail::edge_desc_impl<boost::directed_tag, unsigned long>, long>, boost::iterators::use_default, boost::iterators::use_default> >(boost::iterators::transform_iterator<boost::detail::parallel::edge_descriptor<boost::detail::edge_desc_impl<boost::directed_tag, unsigned long> >::out_generator<boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS, boost::defaultS>, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS> >, boost::detail::out_edge_iter<std::__1::__wrap_iter<boost::detail::stored_edge_property<unsigned long, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short, boost::no_property> > >*>, unsigned long, boost::detail::edge_desc_impl<boost::directed_tag, unsigned long>, long>, boost::iterators::use_default, boost::iterators::use_default> const&) () #4 0x000000010006ab4f in boost::iterators::detail::iterator_facade_base<boost::iterators::transform_iterator<boost::detail::parallel::edge_descriptor<boost::detail::edge_desc_impl<boost::directed_tag, unsigned long> >::out_generator<boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS, boost::defaultS>, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS> >, boost::detail::out_edge_iter<std::__1::__wrap_iter<boost::detail::stored_edge_property<unsigned long, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short, boost::no_property> > >*>, unsigned long, boost::detail::edge_desc_impl<boost::directed_tag, unsigned long>, long>, boost::iterators::use_default, boost::iterators::use_default>, boost::detail::parallel::edge_descriptor<boost::detail::edge_desc_impl<boost::directed_tag, unsigned long> >, boost::iterators::detail::iterator_category_with_traversal<std::__1::input_iterator_tag, boost::iterators::random_access_traversal_tag>, boost::detail::parallel::edge_descriptor<boost::detail::edge_desc_impl<boost::directed_tag, unsigned long> >, long, false, false>::operator*() const () #5 0x000000010006aaf5 in boost::adjacency_iterator<boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS, boost::defaultS>, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, boost::detail::parallel::global_descriptor<unsigned long>, boost::iterators::transform_iterator<boost::detail::parallel::edge_descriptor<boost::detail::edge_desc_impl<boost::directed_tag, unsigned long> >::out_generator<boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS, boost::defaultS>, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS> >, boost::detail::out_edge_iter<std::__1::__wrap_iter<boost::detail::stored_edge_property<unsigned long, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short, boost::no_property> > >*>, unsigned long, boost::detail::edge_desc_impl<boost::directed_tag, unsigned long>, long>, boost::iterators::use_default, boost::iterators::use_default>, long>::dereference() const () #6 0x000000010006aa91 in boost::adjacency_iterator<boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS, boost::defaultS>, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, boost::detail::parallel::global_descriptor<unsigned long>, boost::iterators::transform_iterator<boost::detail::parallel::edge_descriptor<boost::detail::edge_desc_impl<boost::directed_tag, unsigned long> >::out_generator<boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS, boost::defaultS>, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS> >, boost::detail::out_edge_iter<std::__1::__wrap_iter<boost::detail::stored_edge_property<unsigned long, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short, boost::no_property> > >*>, unsigned long, boost::detail::edge_desc_impl<boost::directed_tag, unsigned lon---Type <return> to continue, or q <return> to quit--- #define PARALLEL_GRAPH using namespace boost; using boost::graph::distributed::mpi_process_group; typedef adjacency_list <vecS, vecS, undirectedS> SerialGraph; 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; static char help[] = ""; int main(int argc,char **args) { PetscErrorCode ierr; PetscInitialize(&argc,&args,(char*)0,help); int nV = 1; int num = 0; #ifdef PARALLEL_GRAPH Graph G(nV+1); synchronize(G); std::vector<int> localComponent(nV+1); LocalMap components(localComponent.begin(),get(vertex_index, G)); num = connected_components_ps(G, components); #else SerialGraph G(nV+1); std::vector<int> globalComponent(nV+1); num = connected_components(G, &globalComponent[0]); #endif std::cout << num << " connected components" << std::endl; ierr = PetscFinalize(); return 0; }
It looks like the error appears only when a processor ends up with an empty edge list. That is, the following works with mpirun -np 1 but gives a segmentation fault with -np 2 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 nV = 30000; int num = 0; Graph G(nV); synchronize(G); std::vector<int> localComponent(nV); LocalMap components(localComponent.begin(),get(vertex_index, G)); add_edge(vertex(0,G),vertex(1,G),G); num = connected_components_ps(G, components); The following works with -np 2 as well (the only thing I did was adding an edge) int nV = 30000; int num = 0; Graph G(nV); synchronize(G); std::vector<int> localComponent(nV); LocalMap components(localComponent.begin(),get(vertex_index, G)); add_edge(vertex(0,G),vertex(1,G),G); add_edge(vertex(29998,G),vertex(29999,G),G); num = connected_components_ps(G, components); Unfortunately, in my application it is very likely that some processors end up with no edges. Is there a way to fix this other than adding fake edges from a vertex to itself? Thanks, Alessio
participants (2)
-
Marcin Zalewski -
Quaglino Alessio