On Mon, Oct 26, 2009 at 11:29 PM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:
On Mon, 26 Oct 2009, Sandeep Gupta wrote:
Hi All,
I have spent significant effort on parallel bfs. Currently its almost working. I would really appreciate some help to get it running correctly. I have attached the code (self contained and requires no input file). I think I have followed all the guidelines regarding distributed property maps mentioned in the docs (
http://www.osl.iu.edu/research/pbgl/documentation/graph/breadth_first_search... ). I am out of ideas of where things can could have gone wrong.
The graph is distributed by source vertex across all processors, and so you need to add them on every processor (or at least on the processor that owns them, which is probably not processor 0). Thus, your graph is missing whichever edges would be on processor 1, leading to incorrect results. Try adding all of the edges on all processors and see if this fixes your problem.
-- Jeremiah Willcock
Jeremiah, thanks so much looking into this promptly. I took cues from building distributed graph section of distributed adjacency list page which has an example: ///---------------Begin example Graph g(n); // initialize with the total number of vertices, n if (process_id(g.process_group()) == 0) { // Only process 0 loads the graph, which is distributed automatically int source, target; for (std::cin >> source >> target) add_edge(vertex(source, g), vertex(target, g), g); } // All processes synchronize at this point, then the graph is complete synchronize(g.process_group()); //---------End Looking at this, it seems that distribution happens automatically which is what the manual says. This is further confirmed when I output the subgraphs at each process. Subgraph For process 0 n0 -> n1; n0 -> n2; n1 -> n2; n1 -> n3; n2 -> n3; n3 -> n4; n3 -> n6; Subgraph End Subgraph For process 1 n4 -> n5; Subgraph End As you suggested I also tried adding all the edges on all the processes. Unfortunately, the problem still remains the same. The BFS output is Node ID : Level 0 : 0 1 : 1 2 : 1 3 : 2 4 : 3 5 : 4294967295 6 : 3 and the edges gets duplicated Subgraph For process 0 n0 -> n1; n0 -> n2; n0 -> n1; n0 -> n2; n1 -> n2; n1 -> n3; n1 -> n2; n1 -> n3; n2 -> n3; n2 -> n3; n3 -> n4; n3 -> n6; n3 -> n4; n3 -> n6; Subgraph End Subgraph For process 1 n4 -> n5; n4 -> n5; Subgraph End Hope this clarifies the problem a bit better and that i helps to pinpoint the source of error. Appreciate your input. Thanks Sandeep