On Wed, Nov 11, 2009 at 9:22 AM, Nick Edmonds <ngedmond@cs.indiana.edu>wrote:
On Nov 10, 2009, at 6:53 PM, Sandeep Gupta wrote:
On Tue, Nov 10, 2009 at 2:51 PM, Nick Edmonds <ngedmond@cs.indiana.edu
wrote:
--snip-- (sorry, first reply was too big)
Hi Nick,
Thanks for the explanation of the distributed BFS. This is indeed quite
helpful. Especially at later stages. I haven't gotten to a point to comment on the data model but the current architecture is swell from what I can judge.
I hesitate to ask explanation at every minor detail but I now confused about passing the same vertex descriptor. Specifically I didn't quite grasp the statement "source vertex just has to be graph_traits<Graph>::vertex_descriptor, which you can construct using vertex() call if you want to generate it from a global vertex index". The source vertex has to graph_traits<Graph>::vertex_descriptor which I takes two arguments the index and the graph --these two parameters can only identify local vertices. For global vertices we need global descriptors which also require the owner.
Appreciate your help in clarifying this.
Thanks Sandeep
The vertex() call takes a global index and constructs a vertex_descriptor, which is basically a pair containing the local index and the owning process. vertex(i, g) will construct the i'th vertex descriptor in g on any process, regardless of where the vertex is actually stored. The confusion is that there are two indices here, global indices, and local indices. The graph distribution object maps between the two. vertex() takes a global index, specifically for this use case.
Hope that helps,
Hi Nick,
Sorry, I didn't mean to imply that your first reply was too big. Your
explanation of how the PBFS is actually working is indeed quite helpful. Just that rIght now I just too focussed on get the code working. Ofcourse, when I dig deeper I would certainly have to refer to your exposition.
Right now in the code I am passing vertex(0,g) to all processes. This means, based upon the explanation, that we are performing BFS on all processes from the node with global identifier as 0. But still the code is not outputting right result. There is something more to it or I again misunderstood your explanation.
Thanks for your patience.
Sandeep
I didn't mean that you implied my reply was too big, this thread just exceeded the 75k limit on messages so I trimmed it :)
Ahh..I see.
How are you verifying your result?
I used this code to output results. BOOST_FOREACH(Vertex vtx, vertices(g)) { int local_idx = get(vidx, vtx); std::cout<<pid<<":"<<local_idx<<" : "<<get(distance, vtx)<<std::endl; } Try inserting:
BGL_FORALL_EDGES(e, g, Graph) { request(distance, target(e, g)); // to fetch all the distances where one endpoint of an edge is non-local }
synchronize(distance); // deliver fetched distances
BGL_FORALL_EDGES(e, g, Graph) { assert(get(distance, target(e, g)) <= get(distance, source(e, g)) + 1); }
I did that. The assertions don't fail. However the BFS output was still incorrect. Let me know if that passes. Also, can you give me the type of
distributed_property_map? I'll also attach the version of your code I cleaned up a while ago in case things haven't changed much and it's still useful. This version of the code passes for me.
Can't un-ravel the full type but its of type "property_map<Graph, vertex_distance_t>::type" . The code you gave doesn't pass for me :-(. The level output for number of process = 1 is Node ID : Level 0 : 0 1 : 1 2 : 2 3 : 2 4 : 1
But for np = 2 it is 1: distance of 0@1 = 3 (should be <= 2) Finished Parallel BFS Node ID : Level 0 : 0 1 : 1 2 : 2 3 : 3 4 : 1 5 : 4294967295 Whats more strange is that your code overestimates the depth values which previous version underestimates the depth values. What machine/boost version are you running your code. thanks Sandeep <http://lists.boost.org/mailman/listinfo.cgi/boost>