[prev in list] [next in list] [prev in thread] [next in thread]
List: boost-users
Subject: [Boost-users] [BGL] Connected components of a distributed graph with few edges
From: Quaglino Alessio <alessio.quaglino () usi ! ch>
Date: 2015-10-19 9:39:41
Message-ID: 85E5AF85-80CD-4CC3-AD21-FB781C9E9FED () usi ! ch
[Download RAW message or body]
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
[Attachment #3 (text/html)]
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
</head>
<body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: \
after-white-space;" class=""> Hello,
<div class=""><br class="">
</div>
<div class="">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:</div> <div class=""><br class="">
</div>
<div class="">
<div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""><span \
style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" \
class="">typedef</span> adjacency_list <vecS, vecS, undirectedS> \
SerialGraph;</div> <div style="margin: 0px; font-size: 11px; font-family: Menlo;" \
class=""><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" \
class="">typedef</span> adjacency_list<vecS, distributedS<mpi_process_group, \
vecS>, undirectedS> Graph;</div> <div style="margin: 0px; font-size: 11px; \
font-family: Menlo;" class=""><span style="font-variant-ligatures: \
no-common-ligatures; color: #bb2ca2" class="">typedef</span> \
iterator_property_map<std::vector<<span style="font-variant-ligatures: \
no-common-ligatures; color: #bb2ca2" class="">int</span>>::iterator, \
property_map<Graph, vertex_index_t>::type> LocalMap;</div> </div>
<div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""><br class="">
</div>
<div class="">
<div style="margin: 0px; font-size: 11px; font-family: Menlo; color: rgb(120, 73, \
42);" class=""> #ifdef PARALLEL_GRAPH</div>
<div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> \
Graph G(nV+<span style="font-variant-ligatures: no-common-ligatures; color: \
#272ad8" class="">1</span>);</div> <div style="margin: 0px; font-size: 11px; \
font-family: Menlo;" class=""> <div style="margin: 0px;" class=""> \
synchronize(G);</div> <div style="margin: 0px;" class="">
<div style="margin: 0px;" class=""> std::vector<<span style="color: \
rgb(187, 44, 162);" class="">int</span>> localComponent(nV+<span \
style="font-variant-ligatures: no-common-ligatures; color: #272ad8" \
class="">1</span>);</div> </div>
<div class="">
<div style="margin: 0px;" class=""> LocalMap \
components(localComponent.begin(),get(vertex_index, G));</div> <div style="margin: \
0px;" class=""> num = connected_components_ps(G, components);</div> \
</div> </div>
<div style="margin: 0px; font-size: 11px; font-family: Menlo; color: rgb(120, 73, \
42);" class=""> #else</div>
<div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> \
SerialGraph G(nV+<span style="font-variant-ligatures: no-common-ligatures; color: \
#272ad8" class="">1</span>);</div> <div style="margin: 0px; font-size: 11px; \
font-family: Menlo;" class=""> <div style="margin: 0px;" class=""> \
std::vector<<span style="color: rgb(187, 44, 162);" \
class="">int</span>> globalComponent(nV+<span style="font-variant-ligatures: \
no-common-ligatures; color: #272ad8" class="">1</span>);</div> </div>
<div style="margin: 0px; font-size: 11px; font-family: Menlo;" class="">
<div style="margin: 0px;" class=""> num = connected_components(G, \
&globalComponent[<span style="font-variant-ligatures: no-common-ligatures; color: \
#272ad8" class="">0</span>]);</div> </div>
<div style="margin: 0px; font-size: 11px; font-family: Menlo; color: rgb(120, 73, \
42);" class=""> #endif</div>
</div>
<div class=""><br class="">
</div>
<div class="">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.</div>
<div class=""><br class="">
</div>
<div class="">Regards,</div>
<div class="">Alessio</div>
</body>
</html>
_______________________________________________
Boost-users mailing list
Boost-users@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users
--===============6476998785779709450==--
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic