[BGL] Trying to get a correclty working Parallel BFS code
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 correct output of input graph 0 --> 1 2 1 --> 2 3 2 --> 3 3 --> 4 6 4 --> 5 5 --> 6 --> should be Node ID : Level 0 : 0 1 : 1 2 : 1 3 : 2 4 : 3 5 : 4 6 : 3 But when ran with 2 processes the output comes out to be Node ID : Level 0 : 0 1 : 1 2 : 1 3 : 2 4 : 3 5 : 4294967295 6 : 3 Not sure why this is happening. Any suggestions or pointers would indeed be quite appreciated. Thanks for your time. -Sandeep
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
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
On Tue, 27 Oct 2009, Sandeep Gupta wrote:
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.
OK. I was mistaken on this point then. Could you please try the following graph with a distribution that puts vertices 0-3 on rank 0 and 4 on rank 1 (just add three dummy vertices on the end and use a block distribution)? 0 -> 1 1 -> 2 2 -> 3 0 -> 4 4 -> 3 See if the depths are reasonable for that graph. Also, the contents of the predecessor maps output by your search (both the original one and the graph I just gave) would be nice too; that is just an extra map you can give to BFS and you can just dump it the same way you dump depth values. -- Jeremiah Willcock
On Tue, Oct 27, 2009 at 10:27 AM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:
On Tue, 27 Oct 2009, Sandeep Gupta wrote:
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.
OK. I was mistaken on this point then. Could you please try the following graph with a distribution that puts vertices 0-3 on rank 0 and 4 on rank 1 (just add three dummy vertices on the end and use a block distribution)?
0 -> 1 1 -> 2 2 -> 3 0 -> 4 4 -> 3
See if the depths are reasonable for that graph. Also, the contents of the predecessor maps output by your search (both the original one and the graph I just gave) would be nice too; that is just an extra map you can give to BFS and you can just dump it the same way you dump depth values.
I tried adding predecessor map but I don't think its currently. No reduction function is defined for predecessor map. Please see below for the attached error.
I tried the bfs with your input (and distribution) and the depth number are coming out to be incorrect. This is a surely a better input to debug this problem:-). The depth value of node n=3 should be d=2 but its coming out to be d=0. I believe the update message from node n=4 on process 1 is not received or updated by process 0. Attached below is the output of levels: Finished Parallel BFS Node ID : Level 0 : 0 1 : 1 2 : 2 3 : 0 4 : 1 5 : 4294967295 6 : 4294967295 7 : 4294967295 The two subgraphs on each process Subgraph Begin n0 -> n1; n0 -> n4; n1 -> n2; n2 -> n3; Subgraph End Subgraph Begin n4 -> n3; Subgraph End Thanks, Sandeep //------------------------- The error snippet regarding predecessor map: error: no match for call to '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>) (const boost::detail::parallel::global_descriptor<unsigned int>&)' ../../../boost/property_map/parallel/impl/distributed_property_map.ipp:141: error: no match for call to '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>) (const boost::detail::parallel::global_descriptor<unsigned int>&, boost::detail::error_property_not_found&, const boost::detail::error_property_not_found&)' ../../../boost/graph/parallel/properties.hpp:95: note: candidates are: T boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T) const [with T = boost::detail::error_property_not_found] ../../../boost/graph/parallel/properties.hpp:96: note: T boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T, T, T) const [with T = boost::detail::error_property_not_found]
On Tue, Oct 27, 2009 at 12:33 PM, Sandeep Gupta <gupta.sandeep@gmail.com>wrote:
On Tue, Oct 27, 2009 at 10:27 AM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:
On Tue, 27 Oct 2009, Sandeep Gupta wrote:
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.
OK. I was mistaken on this point then. Could you please try the following graph with a distribution that puts vertices 0-3 on rank 0 and 4 on rank 1 (just add three dummy vertices on the end and use a block distribution)?
0 -> 1 1 -> 2 2 -> 3 0 -> 4 4 -> 3
See if the depths are reasonable for that graph. Also, the contents of the predecessor maps output by your search (both the original one and the graph I just gave) would be nice too; that is just an extra map you can give to BFS and you can just dump it the same way you dump depth values.
I tried adding predecessor map but I don't think its currently. No reduction function is defined for predecessor map. Please see below for the attached error.
I tried the bfs with your input (and distribution) and the depth number are coming out to be incorrect. This is a surely a better input to debug this problem:-). The depth value of node n=3 should be d=2 but its coming out to be d=0. I believe the update message from node n=4 on process 1 is not received or updated by process 0. Attached below is the output of levels: Finished Parallel BFS Node ID : Level 0 : 0
1 : 1 2 : 2 3 : 0 4 : 1 5 : 4294967295 6 : 4294967295 7 : 4294967295
The two subgraphs on each process Subgraph Begin n0 -> n1; n0 -> n4; n1 -> n2; n2 -> n3; Subgraph End
Subgraph Begin n4 -> n3; Subgraph End
Thanks, Sandeep
//------------------------- The error snippet regarding predecessor map:
error: no match for call to '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>) (const boost::detail::parallel::global_descriptor<unsigned int>&)'
../../../boost/property_map/parallel/impl/distributed_property_map.ipp:141: error: no match for call to '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>) (const boost::detail::parallel::global_descriptor<unsigned int>&, boost::detail::error_property_not_found&, const boost::detail::error_property_not_found&)' ../../../boost/graph/parallel/properties.hpp:95: note: candidates are: T boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T) const [with T = boost::detail::error_property_not_found] ../../../boost/graph/parallel/properties.hpp:96: note: T boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T, T, T) const [with T = boost::detail::error_property_not_found]
Jeremiah, Do you think that I should file a bug report for this.
Although I was hoping (and actually needed quite urgently) that it would be minor issue and get fixed quickly. Thanks, Sandeep
On Tue, 27 Oct 2009, Sandeep Gupta wrote:
The error snippet regarding predecessor map:
error: no match for call to '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>) (const boost::detail::parallel::global_descriptor<unsigned int>&)'
../../../boost/property_map/parallel/impl/distributed_property_map.ipp:141: error: no match for call to '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>) (const boost::detail::parallel::global_descriptor<unsigned int>&, boost::detail::error_property_not_found&, const boost::detail::error_property_not_found&)' ../../../boost/graph/parallel/properties.hpp:95: note: candidates are: T boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T) const [with T = boost::detail::error_property_not_found] ../../../boost/graph/parallel/properties.hpp:96: note: T boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T, T, T) const [with T = boost::detail::error_property_not_found]
Jeremiah, Do you think that I should file a bug report for this. Although I was hoping (and actually needed quite urgently) that it would be minor issue and get fixed quickly.
You need to pass a predecessor map to the algorithm as one of the parameters (or put it as a part of your graph but making an external property map to give to the algorithm is easier). -- Jeremiah Willcock
On Tue, Oct 27, 2009 at 9:31 PM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:
On Tue, 27 Oct 2009, Sandeep Gupta wrote:
The error snippet regarding predecessor map:
error: no match for call to
'(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>) (const boost::detail::parallel::global_descriptor<unsigned int>&)'
../../../boost/property_map/parallel/impl/distributed_property_map.ipp:141: error: no match for call to
'(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>) (const boost::detail::parallel::global_descriptor<unsigned int>&, boost::detail::error_property_not_found&, const boost::detail::error_property_not_found&)' ../../../boost/graph/parallel/properties.hpp:95: note: candidates are: T
boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T) const [with T = boost::detail::error_property_not_found] ../../../boost/graph/parallel/properties.hpp:96: note: T
boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T, T, T) const [with T = boost::detail::error_property_not_found]
Jeremiah, Do you think that I should file a bug report for this.
Although I was hoping (and actually needed quite urgently) that it would be minor issue and get fixed quickly.
You need to pass a predecessor map to the algorithm as one of the parameters (or put it as a part of your graph but making an external property map to give to the algorithm is easier).
Hi Jeremy,
It took me a while but I finally figure out how to pass the predecessor map. Unfortunately it doesn't have any effect. Also, I might be wrong but I don't see any logical reason why predecessor map should have any bearing on the correctness of the depth. I have attached the new code. I am not able to print out the predecessor because I am not able to figure out its type. Maybe you could help me resolve this.
It would be nice to have this code running. I need to profile graph performance on a new machine by tomorrow. Again, thanks for you patience and time. I really appreciate you looking into this. -Sandeep
On Wed, Oct 28, 2009 at 5:49 PM, Sandeep Gupta <gupta.sandeep@gmail.com>wrote:
On Tue, Oct 27, 2009 at 9:31 PM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:
On Tue, 27 Oct 2009, Sandeep Gupta wrote:
The error snippet regarding predecessor map:
error: no match for call to
'(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>) (const boost::detail::parallel::global_descriptor<unsigned int>&)'
../../../boost/property_map/parallel/impl/distributed_property_map.ipp:141: error: no match for call to
'(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>) (const boost::detail::parallel::global_descriptor<unsigned int>&, boost::detail::error_property_not_found&, const boost::detail::error_property_not_found&)' ../../../boost/graph/parallel/properties.hpp:95: note: candidates are: T
boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T) const [with T = boost::detail::error_property_not_found] ../../../boost/graph/parallel/properties.hpp:96: note: T
boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T, T, T) const [with T = boost::detail::error_property_not_found]
Jeremiah, Do you think that I should file a bug report for this.
Although I was hoping (and actually needed quite urgently) that it would be minor issue and get fixed quickly.
You need to pass a predecessor map to the algorithm as one of the parameters (or put it as a part of your graph but making an external property map to give to the algorithm is easier).
Hi Jeremy,
It took me a while but I finally figure out how to pass the predecessor map. Unfortunately it doesn't have any effect. Also, I might be wrong but I don't see any logical reason why predecessor map should have any bearing on the correctness of the depth. I have attached the new code. I am not able to print out the predecessor because I am not able to figure out its type. Maybe you could help me resolve this.
It would be nice to have this code running. I need to profile graph performance on a new machine by tomorrow. Again, thanks for you patience and time. I really appreciate you looking into this.
Hi Jeremiah,
Was just wondering if you had time to look into this or any suggestion on how further proceed. I can get you the output of predecessor map if that would help. Just that I haven't be been able to figure out what the is type of the property map returned by make_distributed_property_map. Please let me know your thoughts. Thanks, Sandeep
On Thu, 29 Oct 2009, Sandeep Gupta wrote:
On Wed, Oct 28, 2009 at 5:49 PM, Sandeep Gupta <gupta.sandeep@gmail.com>wrote:
On Tue, Oct 27, 2009 at 9:31 PM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:
On Tue, 27 Oct 2009, Sandeep Gupta wrote:
The error snippet regarding predecessor map:
error: no match for call to
'(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>) (const boost::detail::parallel::global_descriptor<unsigned int>&)'
../../../boost/property_map/parallel/impl/distributed_property_map.ipp:141: error: no match for call to
'(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>) (const boost::detail::parallel::global_descriptor<unsigned int>&, boost::detail::error_property_not_found&, const boost::detail::error_property_not_found&)' ../../../boost/graph/parallel/properties.hpp:95: note: candidates are: T
boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T) const [with T = boost::detail::error_property_not_found] ../../../boost/graph/parallel/properties.hpp:96: note: T
boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T, T, T) const [with T = boost::detail::error_property_not_found]
Jeremiah, Do you think that I should file a bug report for this.
Although I was hoping (and actually needed quite urgently) that it would be minor issue and get fixed quickly.
You need to pass a predecessor map to the algorithm as one of the parameters (or put it as a part of your graph but making an external property map to give to the algorithm is easier).
Hi Jeremy,
It took me a while but I finally figure out how to pass the predecessor map. Unfortunately it doesn't have any effect. Also, I might be wrong but I don't see any logical reason why predecessor map should have any bearing on the correctness of the depth. I have attached the new code. I am not able to print out the predecessor because I am not able to figure out its type. Maybe you could help me resolve this.
It would be nice to have this code running. I need to profile graph performance on a new machine by tomorrow. Again, thanks for you patience and time. I really appreciate you looking into this.
Hi Jeremiah,
Was just wondering if you had time to look into this or any suggestion on how further proceed. I can get you the output of predecessor map if that would help. Just that I haven't be been able to figure out what the is type of the property map returned by make_distributed_property_map. Please let me know your thoughts.
The person who really knows this library is not around as far as I know; he might be on vacation. The type returned from make_distributed_property_map is documented on <URL:http://www.osl.iu.edu/research/pbgl/documentation/graph/ distributed_property_map.html>. One thing that you could do to debug things is to put in your own color map and look at what values it ends up with at the end of the algorithm, and possibly even to put in a local color map that prints out when elements are changed. That might be a lot of work for what could end up being an obvious problem (that I just don't know how to diagnose), though. BTW, does the example in libs/graph_parallel/example/breadth_first_search.cpp work for you? It appears to be doing the same thing you want to do. If that works, it could be a problem in your visitor. -- Jeremiah Willcock
On Thu, 29 Oct 2009, Sandeep Gupta wrote:
On Wed, Oct 28, 2009 at 5:49 PM, Sandeep Gupta <gupta.sandeep@gmail.com
wrote:
On Tue, Oct 27, 2009 at 9:31 PM, Jeremiah Willcock <jewillco@osl.iu.edu
wrote:
On Tue, 27 Oct 2009, Sandeep Gupta wrote:
The error snippet regarding predecessor map:
error: no match for call to
'(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>) (const boost::detail::parallel::global_descriptor<unsigned int>&)'
../../../boost/property_map/parallel/impl/distributed_property_map.ipp:141: error: no match for call to
'(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>) (const boost::detail::parallel::global_descriptor<unsigned int>&, boost::detail::error_property_not_found&, const boost::detail::error_property_not_found&)' ../../../boost/graph/parallel/properties.hpp:95: note: candidates are: T
boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T) const [with T = boost::detail::error_property_not_found] ../../../boost/graph/parallel/properties.hpp:96: note: T
boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T, T, T) const [with T = boost::detail::error_property_not_found]
Jeremiah, Do you think that I should file a bug report for this.
Although I was hoping (and actually needed quite urgently) that it would be minor issue and get fixed quickly.
You need to pass a predecessor map to the algorithm as one of the parameters (or put it as a part of your graph but making an external property map to give to the algorithm is easier).
Hi Jeremy,
It took me a while but I finally figure out how to pass the predecessor
map. Unfortunately it doesn't have any effect. Also, I might be wrong but I don't see any logical reason why predecessor map should have any bearing on the correctness of the depth. I have attached the new code. I am not able to print out the predecessor because I am not able to figure out its type. Maybe you could help me resolve this.
It would be nice to have this code running. I need to profile graph performance on a new machine by tomorrow. Again, thanks for you patience and time. I really appreciate you looking into this.
Hi Jeremiah,
Was just wondering if you had time to look into this or any suggestion
on how further proceed. I can get you the output of predecessor map if that would help. Just that I haven't be been able to figure out what the is type of the property map returned by make_distributed_property_map. Please let me know your thoughts.
The person who really knows this library is not around as far as I know; he might be on vacation. The type returned from make_distributed_property_map is documented on <URL: http://www.osl.iu.edu/research/pbgl/documentation/graph/ distributed_property_map.html>. One thing that you could do to debug things is to put in your own color map and look at what values it ends up with at the end of the algorithm, and possibly even to put in a local color map that prints out when elements are changed. That might be a lot of work for what could end up being an obvious problem (that I just don't know how to diagnose), though. BTW, does the example in libs/graph_parallel/example/breadth_first_search.cpp work for you? It appears to be doing the same thing you want to do. If that works, it could be a problem in your visitor.
I derived this code from graph_parallel/example/breadth_first_search.cpp. The problem is that I don't understand the input and the output of the example code. It would be great if I could get an explanation for the
On Thu, Oct 29, 2009 at 1:12 PM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote: format of the input file. Then I can transform my graph into that format and pass to the algorithm. That would be enough for my current purpose. As time permits I would try out your suggestions and let know of update. In the meantime I am hoping that I would get input from other relevant authors. Thanks, Sandeep
On Thu, 29 Oct 2009, Sandeep Gupta wrote:
On Thu, Oct 29, 2009 at 1:12 PM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:
On Thu, 29 Oct 2009, Sandeep Gupta wrote:
On Wed, Oct 28, 2009 at 5:49 PM, Sandeep Gupta <gupta.sandeep@gmail.com
wrote:
On Tue, Oct 27, 2009 at 9:31 PM, Jeremiah Willcock <jewillco@osl.iu.edu
wrote:
On Tue, 27 Oct 2009, Sandeep Gupta wrote:
The error snippet regarding predecessor map:
> error: no match for call to > > > '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>) > (const boost::detail::parallel::global_descriptor<unsigned int>&)' > > > > > ../../../boost/property_map/parallel/impl/distributed_property_map.ipp:141: > error: no match for call to > > > '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>) > (const boost::detail::parallel::global_descriptor<unsigned int>&, > boost::detail::error_property_not_found&, const > boost::detail::error_property_not_found&)' > ../../../boost/graph/parallel/properties.hpp:95: note: candidates are: > T > > > boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T) > const [with T = boost::detail::error_property_not_found] > ../../../boost/graph/parallel/properties.hpp:96: note: > T > > > boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T, > T, T) const [with T = boost::detail::error_property_not_found] > > > Jeremiah, Do you think that I should file a bug report for this. > > Although I was hoping (and actually needed quite urgently) that it would be minor issue and get fixed quickly.
You need to pass a predecessor map to the algorithm as one of the parameters (or put it as a part of your graph but making an external property map to give to the algorithm is easier).
Hi Jeremy,
It took me a while but I finally figure out how to pass the predecessor
map. Unfortunately it doesn't have any effect. Also, I might be wrong but I don't see any logical reason why predecessor map should have any bearing on the correctness of the depth. I have attached the new code. I am not able to print out the predecessor because I am not able to figure out its type. Maybe you could help me resolve this.
It would be nice to have this code running. I need to profile graph performance on a new machine by tomorrow. Again, thanks for you patience and time. I really appreciate you looking into this.
Hi Jeremiah,
Was just wondering if you had time to look into this or any suggestion
on how further proceed. I can get you the output of predecessor map if that would help. Just that I haven't be been able to figure out what the is type of the property map returned by make_distributed_property_map. Please let me know your thoughts.
The person who really knows this library is not around as far as I know; he might be on vacation. The type returned from make_distributed_property_map is documented on <URL: http://www.osl.iu.edu/research/pbgl/documentation/graph/ distributed_property_map.html>. One thing that you could do to debug things is to put in your own color map and look at what values it ends up with at the end of the algorithm, and possibly even to put in a local color map that prints out when elements are changed. That might be a lot of work for what could end up being an obvious problem (that I just don't know how to diagnose), though. BTW, does the example in libs/graph_parallel/example/breadth_first_search.cpp work for you? It appears to be doing the same thing you want to do. If that works, it could be a problem in your visitor.
I derived this code from graph_parallel/example/breadth_first_search.cpp. The problem is that I don't understand the input and the output of the example code. It would be great if I could get an explanation for the format of the input file. Then I can transform my graph into that format and pass to the algorithm. That would be enough for my current purpose.
As time permits I would try out your suggestions and let know of update. In the meantime I am hoping that I would get input from other relevant authors.
This is what I could tell from the code. Input: http://people.sc.fsu.edu/~burkardt/data/metis_graph/metis_graph.html Output: http://www.graphviz.org/doc/info/lang.html -- Jeremiah Willcock
On Fri, Oct 30, 2009 at 6:41 AM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:
On Thu, 29 Oct 2009, Sandeep Gupta wrote:
On Thu, Oct 29, 2009 at 1:12 PM, Jeremiah Willcock <jewillco@osl.iu.edu
wrote:
On Thu, 29 Oct 2009, Sandeep Gupta wrote:
On Wed, Oct 28, 2009 at 5:49 PM, Sandeep Gupta <gupta.sandeep@gmail.com
wrote:
On Tue, Oct 27, 2009 at 9:31 PM, Jeremiah Willcock < jewillco@osl.iu.edu
wrote:
On Tue, 27 Oct 2009, Sandeep Gupta wrote:
The error snippet regarding predecessor map:
> error: no match for call to >> >> >> >> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>) >> (const boost::detail::parallel::global_descriptor<unsigned int>&)' >> >> >> >> >> >> ../../../boost/property_map/parallel/impl/distributed_property_map.ipp:141: >> error: no match for call to >> >> >> >> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>) >> (const boost::detail::parallel::global_descriptor<unsigned int>&, >> boost::detail::error_property_not_found&, const >> boost::detail::error_property_not_found&)' >> ../../../boost/graph/parallel/properties.hpp:95: note: candidates >> are: >> T >> >> >> >> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T) >> const [with T = boost::detail::error_property_not_found] >> ../../../boost/graph/parallel/properties.hpp:96: note: >> T >> >> >> >> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T, >> T, T) const [with T = boost::detail::error_property_not_found] >> >> >> Jeremiah, Do you think that I should file a bug report for this. >> >> Although I was hoping (and actually needed quite urgently) that it >> > would > be > minor issue and get fixed quickly. > > > You need to pass a predecessor map to the algorithm as one of the parameters (or put it as a part of your graph but making an external property map to give to the algorithm is easier).
Hi Jeremy,
It took me a while but I finally figure out how to pass the predecessor
map. Unfortunately it doesn't have any effect. Also, I might be wrong but I don't see any logical reason why predecessor map should have any bearing on the correctness of the depth. I have attached the new code. I am not able to print out the predecessor because I am not able to figure out its type. Maybe you could help me resolve this.
It would be nice to have this code running. I need to profile graph performance on a new machine by tomorrow. Again, thanks for you patience and time. I really appreciate you looking into this.
Hi Jeremiah,
Was just wondering if you had time to look into this or any suggestion
on how further proceed. I can get you the output of predecessor map if that would help. Just that I haven't be been able to figure out what the is type of the property map returned by make_distributed_property_map. Please let me know your thoughts.
The person who really knows this library is not around as far as I know; he might be on vacation. The type returned from make_distributed_property_map is documented on <URL: http://www.osl.iu.edu/research/pbgl/documentation/graph/ distributed_property_map.html>. One thing that you could do to debug things is to put in your own color map and look at what values it ends up with at the end of the algorithm, and possibly even to put in a local color map that prints out when elements are changed. That might be a lot of work for what could end up being an obvious problem (that I just don't know how to diagnose), though. BTW, does the example in libs/graph_parallel/example/breadth_first_search.cpp work for you? It appears to be doing the same thing you want to do. If that works, it could be a problem in your visitor.
I derived this code from graph_parallel/example/breadth_first_search.cpp.
The problem is that I don't understand the input and the output of the example code. It would be great if I could get an explanation for the format of the input file. Then I can transform my graph into that format and pass to the algorithm. That would be enough for my current purpose.
As time permits I would try out your suggestions and let know of update. In the meantime I am hoping that I would get input from other relevant authors.
This is what I could tell from the code.
Output: http://www.graphviz.org/doc/info/lang.html
Thanks Jeremiah. The link was helpful. I understood the input graph format. Its for undirected graph only. However the BFS output is still coming out to be incorrect. I tried with a sample line graph of 4 nodes and it exhibits the same problem as before.
The distances of nodes on process 2 is not getting updated. On the other hand dijkstra shortest paths example is working correctly. Thanks Sandeep
On Oct 31, 2009, at 1:00 AM, Sandeep Gupta wrote:
On Fri, Oct 30, 2009 at 6:41 AM, Jeremiah Willcock <jewillco@osl.iu.edu
wrote:
On Thu, 29 Oct 2009, Sandeep Gupta wrote:
On Thu, Oct 29, 2009 at 1:12 PM, Jeremiah Willcock <jewillco@osl.iu.edu
wrote:
On Thu, 29 Oct 2009, Sandeep Gupta wrote:
On Wed, Oct 28, 2009 at 5:49 PM, Sandeep Gupta <gupta.sandeep@gmail.com
wrote:
On Tue, Oct 27, 2009 at 9:31 PM, Jeremiah Willcock < jewillco@osl.iu.edu
> wrote: >
On Tue, 27 Oct 2009, Sandeep Gupta wrote:
> > The error snippet regarding predecessor map: > > >> error: no match for call to >>> >>> >>> >>> '(boost >>> ::property_reduce >>> < >>> boost >>> ::vertex_predecessor_t >>> >::apply<boost::detail::error_property_not_found>) >>> (const boost::detail::parallel::global_descriptor<unsigned >>> int>&)' >>> >>> >>> >>> >>> >>> ../../../boost/property_map/parallel/impl/ >>> distributed_property_map.ipp:141: >>> error: no match for call to >>> >>> >>> >>> '(boost >>> ::property_reduce >>> < >>> boost >>> ::vertex_predecessor_t >>> >::apply<boost::detail::error_property_not_found>) >>> (const boost::detail::parallel::global_descriptor<unsigned >>> int>&, >>> boost::detail::error_property_not_found&, const >>> boost::detail::error_property_not_found&)' >>> ../../../boost/graph/parallel/properties.hpp:95: note: >>> candidates >>> are: >>> T >>> >>> >>> >>> boost >>> ::property_reduce >>> <boost::vertex_predecessor_t>::apply<T>::operator()(T) >>> const [with T = boost::detail::error_property_not_found] >>> ../../../boost/graph/parallel/properties.hpp:96: note: >>> T >>> >>> >>> >>> boost >>> ::property_reduce >>> <boost::vertex_predecessor_t>::apply<T>::operator()(T, >>> T, T) const [with T = boost::detail::error_property_not_found] >>> >>> >>> Jeremiah, Do you think that I should file a bug report for >>> this. >>> >>> Although I was hoping (and actually needed quite urgently) >>> that it >>> >> would >> be >> minor issue and get fixed quickly. >> >> >> You need to pass a predecessor map to the algorithm as one of >> the > parameters > (or put it as a part of your graph but making an external > property map > to > give > to the algorithm is easier). > > Hi Jeremy, > > It took me a while but I finally figure out how to pass the predecessor
> map. Unfortunately it doesn't have any effect. Also, I might > be wrong > but I > don't see any logical reason why predecessor map should have any > bearing > on > the correctness of the depth. I have attached the new code. I > am not > able > to print out the predecessor because I am not able to figure > out its > type. > Maybe you could help me resolve this. > > > It would be nice to have this code running. I need to profile > graph performance on a new machine by tomorrow. Again, thanks for you patience and time. I really appreciate you looking into this.
Hi Jeremiah,
Was just wondering if you had time to look into this or any suggestion
on how further proceed. I can get you the output of predecessor map if that would help. Just that I haven't be been able to figure out what the is type of the property map returned by make_distributed_property_map. Please let me know your thoughts.
The person who really knows this library is not around as far as I know; he might be on vacation. The type returned from make_distributed_property_map is documented on <URL: http://www.osl.iu.edu/research/pbgl/documentation/graph/ distributed_property_map.html>. One thing that you could do to debug things is to put in your own color map and look at what values it ends up with at the end of the algorithm, and possibly even to put in a local color map that prints out when elements are changed. That might be a lot of work for what could end up being an obvious problem (that I just don't know how to diagnose), though. BTW, does the example in libs/graph_parallel/example/breadth_first_search.cpp work for you? It appears to be doing the same thing you want to do. If that works, it could be a problem in your visitor.
I derived this code from graph_parallel/example/ breadth_first_search.cpp.
The problem is that I don't understand the input and the output of the example code. It would be great if I could get an explanation for the format of the input file. Then I can transform my graph into that format and pass to the algorithm. That would be enough for my current purpose.
As time permits I would try out your suggestions and let know of update. In the meantime I am hoping that I would get input from other relevant authors.
This is what I could tell from the code.
Input: http://people.sc.fsu.edu/~burkardt/data/metis_graph/ metis_graph.html<http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/metis_graph.html
Output: http://www.graphviz.org/doc/info/lang.html
Thanks Jeremiah. The link was helpful. I understood the input graph format. Its for undirected graph only. However the BFS output is still coming out to be incorrect. I tried with a sample line graph of 4 nodes and it exhibits the same problem as before.
The distances of nodes on process 2 is not getting updated. On the other hand dijkstra shortest paths example is working correctly.
Thanks Sandeep
I rewrote most of your code before I realized that you're outputting all your distances on process 0, even for vertices process 0 doesn't own. The large value you see is std::numeric_limits<distance_type>::max. When you call get(distance, vertex(i, g)) for some i not owned by the current process a ghost cell is created for the requested value and a request sent to the owner of that vertex for the correct value. get() then returns whatever the default value is for the distance property map, which in this case is infinity (i.e. std::numeric_limits<distance_type>::max. In some cases you may get the correct distance value because process 0 has previously requested that value (and it may or may not be up to date). If process 0 has never requested that distance value and it doesn't own the vertex, then you'll get infinity. You need to gather all your data before you output it from a single node (i.e. issue a get() or request() which is a get with no return value, for each data element). If you want your code to be scalable you should output your data in a distributed fashion from all nodes at once. Remember that updated values won't be guaranteed to arrive until the next synchronization step. If you want the modified version of your code let me know and I'll finish it and ship it your way. -Nick
On Mon, Nov 2, 2009 at 12:43 PM, Nick Edmonds <ngedmond@cs.indiana.edu>wrote:
On Oct 31, 2009, at 1:00 AM, Sandeep Gupta wrote:
On Fri, Oct 30, 2009 at 6:41 AM, Jeremiah Willcock <jewillco@osl.iu.edu
wrote:
On Thu, 29 Oct 2009, Sandeep Gupta wrote:
On Thu, Oct 29, 2009 at 1:12 PM, Jeremiah Willcock <jewillco@osl.iu.edu
wrote:
On Thu, 29 Oct 2009, Sandeep Gupta wrote:
On Wed, Oct 28, 2009 at 5:49 PM, Sandeep Gupta < gupta.sandeep@gmail.com
wrote:
> >
On Tue, Oct 27, 2009 at 9:31 PM, Jeremiah Willcock < > jewillco@osl.iu.edu > > wrote: >> >> > On Tue, 27 Oct 2009, Sandeep Gupta wrote: > > >> The error snippet regarding predecessor map: >> >> >> error: no match for call to >>> >>>> >>>> >>>> >>>> >>>> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>) >>>> (const boost::detail::parallel::global_descriptor<unsigned int>&)' >>>> >>>> >>>> >>>> >>>> >>>> >>>> ../../../boost/property_map/parallel/impl/distributed_property_map.ipp:141: >>>> error: no match for call to >>>> >>>> >>>> >>>> >>>> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>) >>>> (const boost::detail::parallel::global_descriptor<unsigned int>&, >>>> boost::detail::error_property_not_found&, const >>>> boost::detail::error_property_not_found&)' >>>> ../../../boost/graph/parallel/properties.hpp:95: note: candidates >>>> are: >>>> T >>>> >>>> >>>> >>>> >>>> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T) >>>> const [with T = boost::detail::error_property_not_found] >>>> ../../../boost/graph/parallel/properties.hpp:96: note: >>>> T >>>> >>>> >>>> >>>> >>>> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T, >>>> T, T) const [with T = boost::detail::error_property_not_found] >>>> >>>> >>>> Jeremiah, Do you think that I should file a bug report for this. >>>> >>>> Although I was hoping (and actually needed quite urgently) that it >>>> >>>> would >>> be >>> minor issue and get fixed quickly. >>> >>> >>> You need to pass a predecessor map to the algorithm as one of the >>> >> parameters >> (or put it as a part of your graph but making an external property >> map >> to >> give >> to the algorithm is easier). >> >> Hi Jeremy, >> >> >> It took me a while but I finally figure out how to pass the > predecessor > > map. Unfortunately it doesn't have any effect. Also, I might be >> wrong >> but I >> don't see any logical reason why predecessor map should have any >> bearing >> on >> the correctness of the depth. I have attached the new code. I am >> not >> able >> to print out the predecessor because I am not able to figure out its >> type. >> Maybe you could help me resolve this. >> >> >> It would be nice to have this code running. I need to profile graph >> > performance on a new machine by tomorrow. Again, thanks for you > patience > and > time. I really appreciate you looking into this. > > Hi Jeremiah, > > Was just wondering if you had time to look into this or any > suggestion > > on how further proceed. I can get you the output of predecessor map if that would help. Just that I haven't be been able to figure out what the is type of the property map returned by make_distributed_property_map. Please let me know your thoughts.
The person who really knows this library is not around as far as I
know; he might be on vacation. The type returned from make_distributed_property_map is documented on <URL: http://www.osl.iu.edu/research/pbgl/documentation/graph/ distributed_property_map.html>. One thing that you could do to debug things is to put in your own color map and look at what values it ends up with at the end of the algorithm, and possibly even to put in a local color map that prints out when elements are changed. That might be a lot of work for what could end up being an obvious problem (that I just don't know how to diagnose), though. BTW, does the example in libs/graph_parallel/example/breadth_first_search.cpp work for you? It appears to be doing the same thing you want to do. If that works, it could be a problem in your visitor.
I derived this code from graph_parallel/example/breadth_first_search.cpp.
The problem is that I don't understand the input and the output of the
example code. It would be great if I could get an explanation for the format of the input file. Then I can transform my graph into that format and pass to the algorithm. That would be enough for my current purpose.
As time permits I would try out your suggestions and let know of update. In the meantime I am hoping that I would get input from other relevant authors.
This is what I could tell from the code.
Input: http://people.sc.fsu.edu/~burkardt/data/metis_graph/<http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/> metis_graph.html< http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/metis_graph.html>
Output: http://www.graphviz.org/doc/info/lang.html
Thanks Jeremiah. The link was helpful. I understood the input graph format. Its for undirected graph only. However the BFS output is still coming out to be incorrect. I tried with a sample line graph of 4 nodes and it exhibits the same problem as before.
The distances of nodes on process 2 is not getting updated. On the other
hand dijkstra shortest paths example is working correctly.
Thanks Sandeep
I rewrote most of your code before I realized that you're outputting all your distances on process 0, even for vertices process 0 doesn't own. The large value you see is std::numeric_limits<distance_type>::max. When you call get(distance, vertex(i, g)) for some i not owned by the current process a ghost cell is created for the requested value and a request sent to the owner of that vertex for the correct value. get() then returns whatever the default value is for the distance property map, which in this case is infinity (i.e. std::numeric_limits<distance_type>::max.
In some cases you may get the correct distance value because process 0 has previously requested that value (and it may or may not be up to date). If process 0 has never requested that distance value and it doesn't own the vertex, then you'll get infinity.
You need to gather all your data before you output it from a single node (i.e. issue a get() or request() which is a get with no return value, for each data element). If you want your code to be scalable you should output your data in a distributed fashion from all nodes at once. Remember that updated values won't be guaranteed to arrive until the next synchronization step.
If you want the modified version of your code let me know and I'll finish it and ship it your way.
-Nick
Hi Nick,
Thanks so much for looking into this. Sorry, I couldn't get to it earlier due to other concerns. I corrected the mistake you mentioned and I don't get numeric_limit<>::max() for any nodes anymore. I believe the graph/distributed/graphviz.hpp was outputting the distance in correct fashion. Unfortunately, the output is still coming out to be incorrect. It was also the case with output from graphviz.hpp. For the test graph that we mentioned before, essentially 0 --> 1 --> 2 --> 3, 0 --> 4 --> 3 the distance output is as follows: global node-id : distance 0 : 0 1 : 1 2 : 2 3 : 1 //(wrong: should be 2) 4 : 0 // should be 1 If possible can you send me your version of the code. Let me know if you need mine (the updated version). Thanks Sandeep
On Nov 3, 2009, at 10:44 PM, Sandeep Gupta wrote:
On Mon, Nov 2, 2009 at 12:43 PM, Nick Edmonds <ngedmond@cs.indiana.edu>wrote:
On Oct 31, 2009, at 1:00 AM, Sandeep Gupta wrote:
On Fri, Oct 30, 2009 at 6:41 AM, Jeremiah Willcock <jewillco@osl.iu.edu
wrote:
On Thu, 29 Oct 2009, Sandeep Gupta wrote:
On Thu, Oct 29, 2009 at 1:12 PM, Jeremiah Willcock <jewillco@osl.iu.edu
wrote:
On Thu, 29 Oct 2009, Sandeep Gupta wrote:
On Wed, Oct 28, 2009 at 5:49 PM, Sandeep Gupta < gupta.sandeep@gmail.com
wrote: > >> >> > > > On Tue, Oct 27, 2009 at 9:31 PM, Jeremiah Willcock < >> jewillco@osl.iu.edu >> >> wrote: >>> >>> >> On Tue, 27 Oct 2009, Sandeep Gupta wrote: >> >> >>> The error snippet regarding predecessor map: >>> >>> >>> error: no match for call to >>>> >>>>> >>>>> >>>>> >>>>> >>>>> '(boost >>>>> ::property_reduce >>>>> < >>>>> boost >>>>> ::vertex_predecessor_t >>>>> >::apply<boost::detail::error_property_not_found>) >>>>> (const boost::detail::parallel::global_descriptor<unsigned >>>>> int>&)' >>>>> >>>>> >>>>> >>>>> >>>>> >>>>> >>>>> ../../../boost/property_map/parallel/impl/ >>>>> distributed_property_map.ipp:141: >>>>> error: no match for call to >>>>> >>>>> >>>>> >>>>> >>>>> '(boost >>>>> ::property_reduce >>>>> < >>>>> boost >>>>> ::vertex_predecessor_t >>>>> >::apply<boost::detail::error_property_not_found>) >>>>> (const boost::detail::parallel::global_descriptor<unsigned >>>>> int>&, >>>>> boost::detail::error_property_not_found&, const >>>>> boost::detail::error_property_not_found&)' >>>>> ../../../boost/graph/parallel/properties.hpp:95: note: >>>>> candidates >>>>> are: >>>>> T >>>>> >>>>> >>>>> >>>>> >>>>> boost >>>>> ::property_reduce >>>>> <boost::vertex_predecessor_t>::apply<T>::operator()(T) >>>>> const [with T = boost::detail::error_property_not_found] >>>>> ../../../boost/graph/parallel/properties.hpp:96: note: >>>>> T >>>>> >>>>> >>>>> >>>>> >>>>> boost >>>>> ::property_reduce >>>>> <boost::vertex_predecessor_t>::apply<T>::operator()(T, >>>>> T, T) const [with T = >>>>> boost::detail::error_property_not_found] >>>>> >>>>> >>>>> Jeremiah, Do you think that I should file a bug report for >>>>> this. >>>>> >>>>> Although I was hoping (and actually needed quite urgently) >>>>> that it >>>>> >>>>> would >>>> be >>>> minor issue and get fixed quickly. >>>> >>>> >>>> You need to pass a predecessor map to the algorithm as one >>>> of the >>>> >>> parameters >>> (or put it as a part of your graph but making an external >>> property >>> map >>> to >>> give >>> to the algorithm is easier). >>> >>> Hi Jeremy, >>> >>> >>> It took me a while but I finally figure out how to pass the >> predecessor >> >> map. Unfortunately it doesn't have any effect. Also, I might be >>> wrong >>> but I >>> don't see any logical reason why predecessor map should have >>> any >>> bearing >>> on >>> the correctness of the depth. I have attached the new code. >>> I am >>> not >>> able >>> to print out the predecessor because I am not able to figure >>> out its >>> type. >>> Maybe you could help me resolve this. >>> >>> >>> It would be nice to have this code running. I need to >>> profile graph >>> >> performance on a new machine by tomorrow. Again, thanks for you >> patience >> and >> time. I really appreciate you looking into this. >> >> Hi Jeremiah, >> >> Was just wondering if you had time to look into this or any >> suggestion >> >> on > how further proceed. I can get you the output of predecessor > map if > that > would help. > Just that I haven't be been able to figure out what the is > type of the > property map returned by make_distributed_property_map. > Please let me know your thoughts. > > > The person who really knows this library is not around as far > as I know; he might be on vacation. The type returned from make_distributed_property_map is documented on <URL: http://www.osl.iu.edu/research/pbgl/documentation/graph/ distributed_property_map.html>. One thing that you could do to debug things is to put in your own color map and look at what values it ends up with at the end of the algorithm, and possibly even to put in a local color map that prints out when elements are changed. That might be a lot of work for what could end up being an obvious problem (that I just don't know how to diagnose), though. BTW, does the example in libs/graph_parallel/example/breadth_first_search.cpp work for you? It appears to be doing the same thing you want to do. If that works, it could be a problem in your visitor.
I derived this code from graph_parallel/example/breadth_first_search.cpp.
The problem is that I don't understand the input and the output of the
example code. It would be great if I could get an explanation for the format of the input file. Then I can transform my graph into that format and pass to the algorithm. That would be enough for my current purpose.
As time permits I would try out your suggestions and let know of update. In the meantime I am hoping that I would get input from other relevant authors.
This is what I could tell from the code.
metis_graph.html< http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/metis_graph.html
Output: http://www.graphviz.org/doc/info/lang.html
Thanks Jeremiah. The link was helpful. I understood the input graph format. Its for undirected graph only. However the BFS output is still coming out to be incorrect. I tried with a sample line graph of 4 nodes and it exhibits the same problem as before.
The distances of nodes on process 2 is not getting updated. On the other
hand dijkstra shortest paths example is working correctly.
Thanks Sandeep
I rewrote most of your code before I realized that you're outputting all your distances on process 0, even for vertices process 0 doesn't own. The large value you see is std::numeric_limits<distance_type>::max. When you call get(distance, vertex(i, g)) for some i not owned by the current process a ghost cell is created for the requested value and a request sent to the owner of that vertex for the correct value. get() then returns whatever the default value is for the distance property map, which in this case is infinity (i.e. std::numeric_limits<distance_type>::max.
In some cases you may get the correct distance value because process 0 has previously requested that value (and it may or may not be up to date). If process 0 has never requested that distance value and it doesn't own the vertex, then you'll get infinity.
You need to gather all your data before you output it from a single node (i.e. issue a get() or request() which is a get with no return value, for each data element). If you want your code to be scalable you should output your data in a distributed fashion from all nodes at once. Remember that updated values won't be guaranteed to arrive until the next synchronization step.
If you want the modified version of your code let me know and I'll finish it and ship it your way.
-Nick
Hi Nick,
Thanks so much for looking into this. Sorry, I couldn't get to it earlier due to other concerns. I corrected the mistake you mentioned and I don't get numeric_limit<>::max() for any nodes anymore.
I believe the graph/distributed/graphviz.hpp was outputting the distance in correct fashion.
Unfortunately, the output is still coming out to be incorrect. It was also the case with output from graphviz.hpp.
For the test graph that we mentioned before, essentially 0 --> 1 --> 2 --> 3, 0 --> 4 --> 3
the distance output is as follows: global node-id : distance 0 : 0 1 : 1 2 : 2 3 : 1 //(wrong: should be 2) 4 : 0 // should be 1
If possible can you send me your version of the code. Let me know if you need mine (the updated version).
Given the description of your problem above, and assuming you're using a block distribution with 8 vertices, it sounds like you're initializing the distance to the first vertex on *each* process to 0, as opposed to only the distance to the source. The vertex with global index 4 is actually local index 0 on process one using the above distribution. If you initialize the distances to the vertices with global indices 0 and 4 to 0, then your results make sense. Let me know if that's not the case, but I surmise that it is. Also there's a problem in your depth labeling visitor. In the case of cross-processor edges the process that owns the target of the edge doesn't necessarily have the distance to the source of the edge available locally. This will lead to incorrect distance labels even though tree and non-tree edges will still be correctly recognized since the BFS is level-synchronized. The fastest way to handle this is to modify the BFS queue to also pass distance data (which is how the shortest paths algorithms do it). You could also send the data separately and probe for it on the receiving side. Check out the distributed betweenness centrality code for how to create a distributed queue which contains tuples of data one element of which is a vertex (in order to know where to route the data). Integrating this type of vertex queue (i.e. one that contains a data payload) with BFS basically just requires handling the data payload on the receiving side. Cheers, Nick
On Wed, Nov 4, 2009 at 12:18 PM, Nick Edmonds <ngedmond@cs.indiana.edu>wrote:
On Nov 3, 2009, at 10:44 PM, Sandeep Gupta wrote:
On Mon, Nov 2, 2009 at 12:43 PM, Nick Edmonds <ngedmond@cs.indiana.edu
wrote:
On Oct 31, 2009, at 1:00 AM, Sandeep Gupta wrote:
On Fri, Oct 30, 2009 at 6:41 AM, Jeremiah Willcock <jewillco@osl.iu.edu
wrote:
On Thu, 29 Oct 2009, Sandeep Gupta wrote:
On Thu, Oct 29, 2009 at 1:12 PM, Jeremiah Willcock < jewillco@osl.iu.edu
wrote:
> > On Thu, 29 Oct 2009, Sandeep Gupta wrote:
> On Wed, Oct 28, 2009 at 5:49 PM, Sandeep Gupta < > gupta.sandeep@gmail.com > > wrote: > >> >> >>> >>> >> >> On Tue, Oct 27, 2009 at 9:31 PM, Jeremiah Willcock < >> >>> jewillco@osl.iu.edu >>> >>> wrote: >>> >>>> >>>> >>>> On Tue, 27 Oct 2009, Sandeep Gupta wrote: >>> >>> >>> The error snippet regarding predecessor map: >>>> >>>> >>>> error: no match for call to >>>> >>>>> >>>>> >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>) >>>>>> (const boost::detail::parallel::global_descriptor<unsigned >>>>>> int>&)' >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> ../../../boost/property_map/parallel/impl/distributed_property_map.ipp:141: >>>>>> error: no match for call to >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>) >>>>>> (const boost::detail::parallel::global_descriptor<unsigned >>>>>> int>&, >>>>>> boost::detail::error_property_not_found&, const >>>>>> boost::detail::error_property_not_found&)' >>>>>> ../../../boost/graph/parallel/properties.hpp:95: note: >>>>>> candidates >>>>>> are: >>>>>> T >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T) >>>>>> const [with T = boost::detail::error_property_not_found] >>>>>> ../../../boost/graph/parallel/properties.hpp:96: note: >>>>>> T >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T, >>>>>> T, T) const [with T = boost::detail::error_property_not_found] >>>>>> >>>>>> >>>>>> Jeremiah, Do you think that I should file a bug report for this. >>>>>> >>>>>> Although I was hoping (and actually needed quite urgently) that >>>>>> it >>>>>> >>>>>> would >>>>>> >>>>> be >>>>> minor issue and get fixed quickly. >>>>> >>>>> >>>>> You need to pass a predecessor map to the algorithm as one of the >>>>> >>>>> parameters >>>> (or put it as a part of your graph but making an external property >>>> map >>>> to >>>> give >>>> to the algorithm is easier). >>>> >>>> Hi Jeremy, >>>> >>>> >>>> It took me a while but I finally figure out how to pass the >>>> >>> predecessor >>> >>> map. Unfortunately it doesn't have any effect. Also, I might be >>> >>>> wrong >>>> but I >>>> don't see any logical reason why predecessor map should have any >>>> bearing >>>> on >>>> the correctness of the depth. I have attached the new code. I am >>>> not >>>> able >>>> to print out the predecessor because I am not able to figure out >>>> its >>>> type. >>>> Maybe you could help me resolve this. >>>> >>>> >>>> It would be nice to have this code running. I need to profile >>>> graph >>>> >>>> performance on a new machine by tomorrow. Again, thanks for you >>> patience >>> and >>> time. I really appreciate you looking into this. >>> >>> Hi Jeremiah, >>> >>> Was just wondering if you had time to look into this or any >>> suggestion >>> >>> on >>> >> how further proceed. I can get you the output of predecessor map if >> that >> would help. >> Just that I haven't be been able to figure out what the is type of >> the >> property map returned by make_distributed_property_map. >> Please let me know your thoughts. >> >> >> The person who really knows this library is not around as far as I >> > know; > he > might be on vacation. The type returned from > make_distributed_property_map > is documented on <URL: > http://www.osl.iu.edu/research/pbgl/documentation/graph/ > distributed_property_map.html>. One thing that you could do to debug > things is to put in your own color map and look at what values it > ends > up > with at the end of the algorithm, and possibly even to put in a local > color > map that prints out when elements are changed. That might be a lot > of > work > for what could end up being an obvious problem (that I just don't > know > how > to diagnose), though. BTW, does the example in > libs/graph_parallel/example/breadth_first_search.cpp work for you? > It > appears to be doing the same thing you want to do. If that works, it > could > be a problem in your visitor. > > > I derived this code from > graph_parallel/example/breadth_first_search.cpp. > > The problem is that I don't understand the input and the output of > the > example code. It would be great if I could get an explanation for the format of the input file. Then I can transform my graph into that format and pass to the algorithm. That would be enough for my current purpose.
As time permits I would try out your suggestions and let know of update. In the meantime I am hoping that I would get input from other relevant authors.
This is what I could tell from the code.
Input: http://people.sc.fsu.edu/~burkardt/data/metis_graph/<http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/> <http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/>
metis_graph.html< http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/metis_graph.html
Output: http://www.graphviz.org/doc/info/lang.html
Thanks Jeremiah. The link was helpful. I understood the input graph format. Its for undirected graph only. However the BFS output is still coming out to be incorrect. I tried with a sample line graph of 4 nodes and it exhibits the same problem as before.
The distances of nodes on process 2 is not getting updated. On the other
hand dijkstra shortest paths example is working correctly.
Thanks Sandeep
I rewrote most of your code before I realized that you're outputting all your distances on process 0, even for vertices process 0 doesn't own. The large value you see is std::numeric_limits<distance_type>::max. When you call get(distance, vertex(i, g)) for some i not owned by the current process a ghost cell is created for the requested value and a request sent to the owner of that vertex for the correct value. get() then returns whatever the default value is for the distance property map, which in this case is infinity (i.e. std::numeric_limits<distance_type>::max.
In some cases you may get the correct distance value because process 0 has previously requested that value (and it may or may not be up to date). If process 0 has never requested that distance value and it doesn't own the vertex, then you'll get infinity.
You need to gather all your data before you output it from a single node (i.e. issue a get() or request() which is a get with no return value, for each data element). If you want your code to be scalable you should output your data in a distributed fashion from all nodes at once. Remember that updated values won't be guaranteed to arrive until the next synchronization step.
If you want the modified version of your code let me know and I'll finish it and ship it your way.
-Nick
Hi Nick,
Thanks so much for looking into this. Sorry, I couldn't get to it earlier due to other concerns. I corrected the mistake you mentioned and I don't get numeric_limit<>::max() for any nodes anymore.
I believe the graph/distributed/graphviz.hpp was outputting the distance in correct fashion.
Unfortunately, the output is still coming out to be incorrect. It was also the case with output from graphviz.hpp.
For the test graph that we mentioned before, essentially 0 --> 1 --> 2 --> 3, 0 --> 4 --> 3
the distance output is as follows: global node-id : distance 0 : 0 1 : 1 2 : 2 3 : 1 //(wrong: should be 2) 4 : 0 // should be 1
If possible can you send me your version of the code. Let me know if you need mine (the updated version).
Given the description of your problem above, and assuming you're using a block distribution with 8 vertices, it sounds like you're initializing the distance to the first vertex on *each* process to 0, as opposed to only the distance to the source. The vertex with global index 4 is actually local index 0 on process one using the above distribution. If you initialize the distances to the vertices with global indices 0 and 4 to 0, then your results make sense. Let me know if that's not the case, but I surmise that it is.
Very much so :-). Thanks for getting me started with by catching these
minor but fatal mis-understandings with PBFS code. I get the feeling the I haven't read some vital documentation, apart from the manual, on regarding distributed graph. Also there's a problem in your depth labeling visitor. In the case of
cross-processor edges the process that owns the target of the edge doesn't necessarily have the distance to the source of the edge available locally. This will lead to incorrect distance labels even though tree and non-tree edges will still be correctly recognized since the BFS is level-synchronized. The fastest way to handle this is to modify the BFS queue to also pass distance data (which is how the shortest paths algorithms do it). You could also send the data separately and probe for it on the receiving side. Check out the distributed betweenness centrality code for how to create a distributed queue which contains tuples of data one element of which is a vertex (in order to know where to route the data). Integrating this type of vertex queue (i.e. one that contains a data payload) with BFS basically just requires handling the data payload on the receiving side.
I would try this out. So basically the default call
boost::breadth_first_search (g, start, boost::visitor(boost::make_bfs_visitor(boost::record_distances(distance, boost::on_tree_edge())))); wouldn't work. I assumed that distributed BFS implementation did exactly what you mentioned. Although I would write my own, parallel visitor as well per your suggestions. thanks Sandeep
Cheers,
On Wed, Nov 4, 2009 at 3:11 PM, Sandeep Gupta <gupta.sandeep@gmail.com>wrote:
On Wed, Nov 4, 2009 at 12:18 PM, Nick Edmonds <ngedmond@cs.indiana.edu>wrote:
On Nov 3, 2009, at 10:44 PM, Sandeep Gupta wrote:
On Mon, Nov 2, 2009 at 12:43 PM, Nick Edmonds <ngedmond@cs.indiana.edu
wrote:
On Oct 31, 2009, at 1:00 AM, Sandeep Gupta wrote:
On Fri, Oct 30, 2009 at 6:41 AM, Jeremiah Willcock <jewillco@osl.iu.edu
wrote:
On Thu, 29 Oct 2009, Sandeep Gupta wrote:
On Thu, Oct 29, 2009 at 1:12 PM, Jeremiah Willcock < jewillco@osl.iu.edu
wrote: > >> >> > On Thu, 29 Oct 2009, Sandeep Gupta wrote: > > >> On Wed, Oct 28, 2009 at 5:49 PM, Sandeep Gupta < >> gupta.sandeep@gmail.com >> >> wrote: >> >>> >>> >>>> >>>> >>> >>> On Tue, Oct 27, 2009 at 9:31 PM, Jeremiah Willcock < >>> >>>> jewillco@osl.iu.edu >>>> >>>> wrote: >>>> >>>>> >>>>> >>>>> On Tue, 27 Oct 2009, Sandeep Gupta wrote: >>>> >>>> >>>> The error snippet regarding predecessor map: >>>>> >>>>> >>>>> error: no match for call to >>>>> >>>>>> >>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>) >>>>>>> (const boost::detail::parallel::global_descriptor<unsigned >>>>>>> int>&)' >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> ../../../boost/property_map/parallel/impl/distributed_property_map.ipp:141: >>>>>>> error: no match for call to >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>) >>>>>>> (const boost::detail::parallel::global_descriptor<unsigned >>>>>>> int>&, >>>>>>> boost::detail::error_property_not_found&, const >>>>>>> boost::detail::error_property_not_found&)' >>>>>>> ../../../boost/graph/parallel/properties.hpp:95: note: >>>>>>> candidates >>>>>>> are: >>>>>>> T >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T) >>>>>>> const [with T = boost::detail::error_property_not_found] >>>>>>> ../../../boost/graph/parallel/properties.hpp:96: note: >>>>>>> T >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T, >>>>>>> T, T) const [with T = boost::detail::error_property_not_found] >>>>>>> >>>>>>> >>>>>>> Jeremiah, Do you think that I should file a bug report for >>>>>>> this. >>>>>>> >>>>>>> Although I was hoping (and actually needed quite urgently) that >>>>>>> it >>>>>>> >>>>>>> would >>>>>>> >>>>>> be >>>>>> minor issue and get fixed quickly. >>>>>> >>>>>> >>>>>> You need to pass a predecessor map to the algorithm as one of >>>>>> the >>>>>> >>>>>> parameters >>>>> (or put it as a part of your graph but making an external >>>>> property >>>>> map >>>>> to >>>>> give >>>>> to the algorithm is easier). >>>>> >>>>> Hi Jeremy, >>>>> >>>>> >>>>> It took me a while but I finally figure out how to pass the >>>>> >>>> predecessor >>>> >>>> map. Unfortunately it doesn't have any effect. Also, I might be >>>> >>>>> wrong >>>>> but I >>>>> don't see any logical reason why predecessor map should have any >>>>> bearing >>>>> on >>>>> the correctness of the depth. I have attached the new code. I am >>>>> not >>>>> able >>>>> to print out the predecessor because I am not able to figure out >>>>> its >>>>> type. >>>>> Maybe you could help me resolve this. >>>>> >>>>> >>>>> It would be nice to have this code running. I need to profile >>>>> graph >>>>> >>>>> performance on a new machine by tomorrow. Again, thanks for you >>>> patience >>>> and >>>> time. I really appreciate you looking into this. >>>> >>>> Hi Jeremiah, >>>> >>>> Was just wondering if you had time to look into this or any >>>> suggestion >>>> >>>> on >>>> >>> how further proceed. I can get you the output of predecessor map if >>> that >>> would help. >>> Just that I haven't be been able to figure out what the is type of >>> the >>> property map returned by make_distributed_property_map. >>> Please let me know your thoughts. >>> >>> >>> The person who really knows this library is not around as far as I >>> >> know; >> he >> might be on vacation. The type returned from >> make_distributed_property_map >> is documented on <URL: >> http://www.osl.iu.edu/research/pbgl/documentation/graph/ >> distributed_property_map.html>. One thing that you could do to >> debug >> things is to put in your own color map and look at what values it >> ends >> up >> with at the end of the algorithm, and possibly even to put in a >> local >> color >> map that prints out when elements are changed. That might be a lot >> of >> work >> for what could end up being an obvious problem (that I just don't >> know >> how >> to diagnose), though. BTW, does the example in >> libs/graph_parallel/example/breadth_first_search.cpp work for you? >> It >> appears to be doing the same thing you want to do. If that works, >> it >> could >> be a problem in your visitor. >> >> >> I derived this code from >> graph_parallel/example/breadth_first_search.cpp. >> >> The problem is that I don't understand the input and the output of >> the >> > example code. It would be great if I could get an explanation for > the > format of the input file. Then I can transform my graph into that > format > and pass to the algorithm. That would be enough for my current > purpose. > > As time permits I would try out your suggestions and let know of > update. > In > the meantime I am hoping that I would get input from other relevant > authors. > > > This is what I could tell from the code.
Input: http://people.sc.fsu.edu/~burkardt/data/metis_graph/<http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/> <http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/>
metis_graph.html< http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/metis_graph.html >
Output: http://www.graphviz.org/doc/info/lang.html
Thanks Jeremiah. The link was helpful. I understood the input graph format. Its for undirected graph only. However the BFS output is still coming out to be incorrect. I tried with a sample line graph of 4 nodes and it exhibits the same problem as before.
The distances of nodes on process 2 is not getting updated. On the other
hand dijkstra shortest paths example is working correctly.
Thanks Sandeep
I rewrote most of your code before I realized that you're outputting all your distances on process 0, even for vertices process 0 doesn't own. The large value you see is std::numeric_limits<distance_type>::max. When you call get(distance, vertex(i, g)) for some i not owned by the current process a ghost cell is created for the requested value and a request sent to the owner of that vertex for the correct value. get() then returns whatever the default value is for the distance property map, which in this case is infinity (i.e. std::numeric_limits<distance_type>::max.
In some cases you may get the correct distance value because process 0 has previously requested that value (and it may or may not be up to date). If process 0 has never requested that distance value and it doesn't own the vertex, then you'll get infinity.
You need to gather all your data before you output it from a single node (i.e. issue a get() or request() which is a get with no return value, for each data element). If you want your code to be scalable you should output your data in a distributed fashion from all nodes at once. Remember that updated values won't be guaranteed to arrive until the next synchronization step.
If you want the modified version of your code let me know and I'll finish it and ship it your way.
-Nick
Hi Nick,
Thanks so much for looking into this. Sorry, I couldn't get to it earlier due to other concerns. I corrected the mistake you mentioned and I don't get numeric_limit<>::max() for any nodes anymore.
I believe the graph/distributed/graphviz.hpp was outputting the distance in correct fashion.
Unfortunately, the output is still coming out to be incorrect. It was also the case with output from graphviz.hpp.
For the test graph that we mentioned before, essentially 0 --> 1 --> 2 --> 3, 0 --> 4 --> 3
the distance output is as follows: global node-id : distance 0 : 0 1 : 1 2 : 2 3 : 1 //(wrong: should be 2) 4 : 0 // should be 1
If possible can you send me your version of the code. Let me know if you need mine (the updated version).
Given the description of your problem above, and assuming you're using a block distribution with 8 vertices, it sounds like you're initializing the distance to the first vertex on *each* process to 0, as opposed to only the distance to the source. The vertex with global index 4 is actually local index 0 on process one using the above distribution. If you initialize the distances to the vertices with global indices 0 and 4 to 0, then your results make sense. Let me know if that's not the case, but I surmise that it is.
Very much so :-). Thanks for getting me started with by catching these
minor but fatal mis-understandings with PBFS code. I understood that call vertex(i,g) creates a descriptor for ith global vertex.
Also there's a problem in your depth labeling visitor. In the case of
cross-processor edges the process that owns the target of the edge doesn't necessarily have the distance to the source of the edge available locally. This will lead to incorrect distance labels even though tree and non-tree edges will still be correctly recognized since the BFS is level-synchronized. The fastest way to handle this is to modify the BFS queue to also pass distance data (which is how the shortest paths algorithms do it). You could also send the data separately and probe for it on the receiving side. Check out the distributed betweenness centrality code for how to create a distributed queue which contains tuples of data one element of which is a vertex (in order to know where to route the data). Integrating this type of vertex queue (i.e. one that contains a data payload) with BFS basically just requires handling the data payload on the receiving side.
I would try this out. So basically the default call
boost::breadth_first_search (g, start, boost::visitor(boost::make_bfs_visitor(boost::record_distances(distance, boost::on_tree_edge()))));
wouldn't work. I assumed that distributed BFS implementation did exactly what you mentioned. Although I would write my own, parallel visitor as well per your suggestions.
thanks Sandeep
Let me also add that I did modified code that initializes only the
distance to 0th vertex of processor 0. In this case i am facing the dilemma of what should I pass as start vertex for processes > 0. I can't pass the global start vertex (probably the type won't be acceptable to breadth_first_search. I will dig further into the betweeness centrality and dijkstra code to figure this out. Appreciate your input. Thanks Sandeep
On Nov 4, 2009, at 6:22 PM, Sandeep Gupta wrote:
On Wed, Nov 4, 2009 at 3:11 PM, Sandeep Gupta <gupta.sandeep@gmail.com>wrote:
On Wed, Nov 4, 2009 at 12:18 PM, Nick Edmonds <ngedmond@cs.indiana.edu
wrote:
On Nov 3, 2009, at 10:44 PM, Sandeep Gupta wrote:
On Mon, Nov 2, 2009 at 12:43 PM, Nick Edmonds <ngedmond@cs.indiana.edu
wrote:
On Oct 31, 2009, at 1:00 AM, Sandeep Gupta wrote:
On Fri, Oct 30, 2009 at 6:41 AM, Jeremiah Willcock <jewillco@osl.iu.edu
wrote: >
On Thu, 29 Oct 2009, Sandeep Gupta wrote:
> > On Thu, Oct 29, 2009 at 1:12 PM, Jeremiah Willcock < > jewillco@osl.iu.edu > > wrote: >> >>> >>> >> On Thu, 29 Oct 2009, Sandeep Gupta wrote: >> >> >>> On Wed, Oct 28, 2009 at 5:49 PM, Sandeep Gupta < >>> gupta.sandeep@gmail.com >>> >>> wrote: >>> >>>> >>>> >>>>> >>>>> >>>> >>>> On Tue, Oct 27, 2009 at 9:31 PM, Jeremiah Willcock < >>>> >>>>> jewillco@osl.iu.edu >>>>> >>>>> wrote: >>>>> >>>>>> >>>>>> >>>>>> On Tue, 27 Oct 2009, Sandeep Gupta wrote: >>>>> >>>>> >>>>> The error snippet regarding predecessor map: >>>>>> >>>>>> >>>>>> error: no match for call to >>>>>> >>>>>>> >>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> '(boost >>>>>>>> ::property_reduce >>>>>>>> < >>>>>>>> boost >>>>>>>> ::vertex_predecessor_t >>>>>>>> >::apply<boost::detail::error_property_not_found>) >>>>>>>> (const >>>>>>>> boost::detail::parallel::global_descriptor<unsigned >>>>>>>> int>&)' >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> ../../../boost/property_map/parallel/impl/ >>>>>>>> distributed_property_map.ipp:141: >>>>>>>> error: no match for call to >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> '(boost >>>>>>>> ::property_reduce >>>>>>>> < >>>>>>>> boost >>>>>>>> ::vertex_predecessor_t >>>>>>>> >::apply<boost::detail::error_property_not_found>) >>>>>>>> (const >>>>>>>> boost::detail::parallel::global_descriptor<unsigned >>>>>>>> int>&, >>>>>>>> boost::detail::error_property_not_found&, const >>>>>>>> boost::detail::error_property_not_found&)' >>>>>>>> ../../../boost/graph/parallel/properties.hpp:95: note: >>>>>>>> candidates >>>>>>>> are: >>>>>>>> T >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> boost >>>>>>>> ::property_reduce >>>>>>>> <boost::vertex_predecessor_t>::apply<T>::operator()(T) >>>>>>>> const [with T = boost::detail::error_property_not_found] >>>>>>>> ../../../boost/graph/parallel/properties.hpp:96: note: >>>>>>>> T >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> boost >>>>>>>> ::property_reduce >>>>>>>> <boost::vertex_predecessor_t>::apply<T>::operator()(T, >>>>>>>> T, T) const [with T = >>>>>>>> boost::detail::error_property_not_found] >>>>>>>> >>>>>>>> >>>>>>>> Jeremiah, Do you think that I should file a bug report >>>>>>>> for >>>>>>>> this. >>>>>>>> >>>>>>>> Although I was hoping (and actually needed quite >>>>>>>> urgently) that >>>>>>>> it >>>>>>>> >>>>>>>> would >>>>>>>> >>>>>>> be >>>>>>> minor issue and get fixed quickly. >>>>>>> >>>>>>> >>>>>>> You need to pass a predecessor map to the algorithm as >>>>>>> one of >>>>>>> the >>>>>>> >>>>>>> parameters >>>>>> (or put it as a part of your graph but making an external >>>>>> property >>>>>> map >>>>>> to >>>>>> give >>>>>> to the algorithm is easier). >>>>>> >>>>>> Hi Jeremy, >>>>>> >>>>>> >>>>>> It took me a while but I finally figure out how to pass the >>>>>> >>>>> predecessor >>>>> >>>>> map. Unfortunately it doesn't have any effect. Also, I >>>>> might be >>>>> >>>>>> wrong >>>>>> but I >>>>>> don't see any logical reason why predecessor map should >>>>>> have any >>>>>> bearing >>>>>> on >>>>>> the correctness of the depth. I have attached the new >>>>>> code. I am >>>>>> not >>>>>> able >>>>>> to print out the predecessor because I am not able to >>>>>> figure out >>>>>> its >>>>>> type. >>>>>> Maybe you could help me resolve this. >>>>>> >>>>>> >>>>>> It would be nice to have this code running. I need to >>>>>> profile >>>>>> graph >>>>>> >>>>>> performance on a new machine by tomorrow. Again, thanks >>>>>> for you >>>>> patience >>>>> and >>>>> time. I really appreciate you looking into this. >>>>> >>>>> Hi Jeremiah, >>>>> >>>>> Was just wondering if you had time to look into this or any >>>>> suggestion >>>>> >>>>> on >>>>> >>>> how further proceed. I can get you the output of >>>> predecessor map if >>>> that >>>> would help. >>>> Just that I haven't be been able to figure out what the is >>>> type of >>>> the >>>> property map returned by make_distributed_property_map. >>>> Please let me know your thoughts. >>>> >>>> >>>> The person who really knows this library is not around as >>>> far as I >>>> >>> know; >>> he >>> might be on vacation. The type returned from >>> make_distributed_property_map >>> is documented on <URL: >>> http://www.osl.iu.edu/research/pbgl/documentation/graph/ >>> distributed_property_map.html>. One thing that you could do >>> to >>> debug >>> things is to put in your own color map and look at what >>> values it >>> ends >>> up >>> with at the end of the algorithm, and possibly even to put >>> in a >>> local >>> color >>> map that prints out when elements are changed. That might >>> be a lot >>> of >>> work >>> for what could end up being an obvious problem (that I just >>> don't >>> know >>> how >>> to diagnose), though. BTW, does the example in >>> libs/graph_parallel/example/breadth_first_search.cpp work >>> for you? >>> It >>> appears to be doing the same thing you want to do. If that >>> works, >>> it >>> could >>> be a problem in your visitor. >>> >>> >>> I derived this code from >>> graph_parallel/example/breadth_first_search.cpp. >>> >>> The problem is that I don't understand the input and the >>> output of >>> the >>> >> example code. It would be great if I could get an explanation >> for >> the >> format of the input file. Then I can transform my graph into >> that >> format >> and pass to the algorithm. That would be enough for my current >> purpose. >> >> As time permits I would try out your suggestions and let know >> of >> update. >> In >> the meantime I am hoping that I would get input from other >> relevant >> authors. >> >> >> This is what I could tell from the code. > > Input: > http://people.sc.fsu.edu/~burkardt/data/metis_graph/<http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/ > > > <http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/> > > metis_graph.html< > http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/metis_graph.html >> > > > Output: > http://www.graphviz.org/doc/info/lang.html > > > Thanks Jeremiah. The link was helpful. I understood the input > graph > format. > Its for undirected graph only. However the BFS output is still > coming > out > to > be incorrect. I tried with a sample line graph of 4 nodes > and it > exhibits the same problem as before. > > The distances of nodes on process 2 is not getting updated. On > the > other > hand dijkstra shortest paths example is working correctly.
Thanks Sandeep
I rewrote most of your code before I realized that you're outputting all your distances on process 0, even for vertices process 0 doesn't own. The large value you see is std::numeric_limits<distance_type>::max. When you call get(distance, vertex(i, g)) for some i not owned by the current process a ghost cell is created for the requested value and a request sent to the owner of that vertex for the correct value. get() then returns whatever the default value is for the distance property map, which in this case is infinity (i.e. std::numeric_limits<distance_type>::max.
In some cases you may get the correct distance value because process 0 has previously requested that value (and it may or may not be up to date). If process 0 has never requested that distance value and it doesn't own the vertex, then you'll get infinity.
You need to gather all your data before you output it from a single node (i.e. issue a get() or request() which is a get with no return value, for each data element). If you want your code to be scalable you should output your data in a distributed fashion from all nodes at once. Remember that updated values won't be guaranteed to arrive until the next synchronization step.
If you want the modified version of your code let me know and I'll finish it and ship it your way.
-Nick
Hi Nick,
Thanks so much for looking into this. Sorry, I couldn't get to it earlier due to other concerns. I corrected the mistake you mentioned and I don't get numeric_limit<>::max() for any nodes anymore.
I believe the graph/distributed/graphviz.hpp was outputting the distance in correct fashion.
Unfortunately, the output is still coming out to be incorrect. It was also the case with output from graphviz.hpp.
For the test graph that we mentioned before, essentially 0 --> 1 --> 2 --> 3, 0 --> 4 --> 3
the distance output is as follows: global node-id : distance 0 : 0 1 : 1 2 : 2 3 : 1 //(wrong: should be 2) 4 : 0 // should be 1
If possible can you send me your version of the code. Let me know if you need mine (the updated version).
Given the description of your problem above, and assuming you're using a block distribution with 8 vertices, it sounds like you're initializing the distance to the first vertex on *each* process to 0, as opposed to only the distance to the source. The vertex with global index 4 is actually local index 0 on process one using the above distribution. If you initialize the distances to the vertices with global indices 0 and 4 to 0, then your results make sense. Let me know if that's not the case, but I surmise that it is.
Very much so :-). Thanks for getting me started with by catching these
minor but fatal mis-understandings with PBFS code. I understood that call vertex(i,g) creates a descriptor for ith global vertex.
Also there's a problem in your depth labeling visitor. In the case of
cross-processor edges the process that owns the target of the edge doesn't necessarily have the distance to the source of the edge available locally. This will lead to incorrect distance labels even though tree and non-tree edges will still be correctly recognized since the BFS is level-synchronized. The fastest way to handle this is to modify the BFS queue to also pass distance data (which is how the shortest paths algorithms do it). You could also send the data separately and probe for it on the receiving side. Check out the distributed betweenness centrality code for how to create a distributed queue which contains tuples of data one element of which is a vertex (in order to know where to route the data). Integrating this type of vertex queue (i.e. one that contains a data payload) with BFS basically just requires handling the data payload on the receiving side.
I would try this out. So basically the default call
boost::breadth_first_search (g, start, boost ::visitor(boost::make_bfs_visitor(boost::record_distances(distance, boost::on_tree_edge()))));
wouldn't work. I assumed that distributed BFS implementation did exactly what you mentioned. Although I would write my own, parallel visitor as well per your suggestions.
thanks Sandeep
Let me also add that I did modified code that initializes only the
distance to 0th vertex of processor 0. In this case i am facing the dilemma of what should I pass as start vertex for processes > 0. I can't pass the global start vertex (probably the type won't be acceptable to breadth_first_search.
I will dig further into the betweeness centrality and dijkstra code to figure this out. Appreciate your input.
The short answer is, just pass the same source vertex on all processors. Explanation: Each processor will push the source vertex on the distributed queue but all the non-local pushes end up being no-ops since the source vertex is black at the end of the first BFS level when the messages arrive. The 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 fact that all processors push the source vertex is an artifact of reusing the sequential BFS code, it could be changed but I haven't found it to be an issue thus far. This actually brings up an interesting feature of BFS, its possible to start a BFS from multiple source vertices by passing a different source on each processor (you can also pass a queue containing additional starting vertices if you need > num_procs sources). The strongly connected components algorithm uses this approach to run many BFSs on disconnected subgraphs in parallel. One last note on your visitor, my statement was incorrect, sorry. I was looking at some other code and confused it with yours, your depth labeling visitor will work fine because it 'pushes' distance labels. Basically it writes the distance to the vertex it pushes onto the queue into the distributed property map at the same time (actually immediately before). This means that at the next synchronization step both the distance and the vertex descriptor will arrive, in fact the ordering of the messages insures that the distance will arrive prior to the vertex on the queue. Sorry about that, I was looking at another visitor that was 'pulling' data, which is much more problematic. Hopefully that solves all your problems and my apologies again on leading you to believe there was something wrong with your visitor. The data model is a little tricky to wrap your head around, but once you've written some code it should become more intuitive. Cheers, Nick
On Wed, Nov 4, 2009 at 3:39 PM, Nick Edmonds <ngedmond@cs.indiana.edu>wrote:
On Nov 4, 2009, at 6:22 PM, Sandeep Gupta wrote:
On Wed, Nov 4, 2009 at 3:11 PM, Sandeep Gupta <gupta.sandeep@gmail.com
wrote:
On Wed, Nov 4, 2009 at 12:18 PM, Nick Edmonds <ngedmond@cs.indiana.edu
wrote:
On Nov 3, 2009, at 10:44 PM, Sandeep Gupta wrote:
On Mon, Nov 2, 2009 at 12:43 PM, Nick Edmonds <ngedmond@cs.indiana.edu
wrote:
On Oct 31, 2009, at 1:00 AM, Sandeep Gupta wrote:
On Fri, Oct 30, 2009 at 6:41 AM, Jeremiah Willcock < jewillco@osl.iu.edu
wrote: > >> >> > On Thu, 29 Oct 2009, Sandeep Gupta wrote: > > >> On Thu, Oct 29, 2009 at 1:12 PM, Jeremiah Willcock < >> jewillco@osl.iu.edu >> >> wrote: >> >>> >>> >>>> >>>> On Thu, 29 Oct 2009, Sandeep Gupta wrote: >>> >>> >>> On Wed, Oct 28, 2009 at 5:49 PM, Sandeep Gupta < >>>> gupta.sandeep@gmail.com >>>> >>>> wrote: >>>> >>>> >>>>> >>>>> >>>>>> >>>>>> >>>>> On Tue, Oct 27, 2009 at 9:31 PM, Jeremiah Willcock < >>>>> >>>>> jewillco@osl.iu.edu >>>>>> >>>>>> wrote: >>>>>> >>>>>> >>>>>>> >>>>>>> On Tue, 27 Oct 2009, Sandeep Gupta wrote: >>>>>>> >>>>>> >>>>>> >>>>>> The error snippet regarding predecessor map: >>>>>> >>>>>>> >>>>>>> >>>>>>> error: no match for call to >>>>>>> >>>>>>> >>>>>>>> >>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>) >>>>>>>>> (const boost::detail::parallel::global_descriptor<unsigned >>>>>>>>> int>&)' >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> ../../../boost/property_map/parallel/impl/distributed_property_map.ipp:141: >>>>>>>>> error: no match for call to >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>) >>>>>>>>> (const boost::detail::parallel::global_descriptor<unsigned >>>>>>>>> int>&, >>>>>>>>> boost::detail::error_property_not_found&, const >>>>>>>>> boost::detail::error_property_not_found&)' >>>>>>>>> ../../../boost/graph/parallel/properties.hpp:95: note: >>>>>>>>> candidates >>>>>>>>> are: >>>>>>>>> T >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T) >>>>>>>>> const [with T = boost::detail::error_property_not_found] >>>>>>>>> ../../../boost/graph/parallel/properties.hpp:96: note: >>>>>>>>> T >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T, >>>>>>>>> T, T) const [with T = >>>>>>>>> boost::detail::error_property_not_found] >>>>>>>>> >>>>>>>>> >>>>>>>>> Jeremiah, Do you think that I should file a bug report for >>>>>>>>> this. >>>>>>>>> >>>>>>>>> Although I was hoping (and actually needed quite urgently) >>>>>>>>> that >>>>>>>>> it >>>>>>>>> >>>>>>>>> would >>>>>>>>> >>>>>>>>> be >>>>>>>> minor issue and get fixed quickly. >>>>>>>> >>>>>>>> >>>>>>>> You need to pass a predecessor map to the algorithm as one of >>>>>>>> the >>>>>>>> >>>>>>>> parameters >>>>>>>> >>>>>>> (or put it as a part of your graph but making an external >>>>>>> property >>>>>>> map >>>>>>> to >>>>>>> give >>>>>>> to the algorithm is easier). >>>>>>> >>>>>>> Hi Jeremy, >>>>>>> >>>>>>> >>>>>>> It took me a while but I finally figure out how to pass the >>>>>>> >>>>>>> predecessor >>>>>> >>>>>> map. Unfortunately it doesn't have any effect. Also, I might be >>>>>> >>>>>> wrong >>>>>>> but I >>>>>>> don't see any logical reason why predecessor map should have >>>>>>> any >>>>>>> bearing >>>>>>> on >>>>>>> the correctness of the depth. I have attached the new code. I >>>>>>> am >>>>>>> not >>>>>>> able >>>>>>> to print out the predecessor because I am not able to figure >>>>>>> out >>>>>>> its >>>>>>> type. >>>>>>> Maybe you could help me resolve this. >>>>>>> >>>>>>> >>>>>>> It would be nice to have this code running. I need to profile >>>>>>> graph >>>>>>> >>>>>>> performance on a new machine by tomorrow. Again, thanks for you >>>>>>> >>>>>> patience >>>>>> and >>>>>> time. I really appreciate you looking into this. >>>>>> >>>>>> Hi Jeremiah, >>>>>> >>>>>> Was just wondering if you had time to look into this or any >>>>>> suggestion >>>>>> >>>>>> on >>>>>> >>>>>> how further proceed. I can get you the output of predecessor >>>>> map if >>>>> that >>>>> would help. >>>>> Just that I haven't be been able to figure out what the is type >>>>> of >>>>> the >>>>> property map returned by make_distributed_property_map. >>>>> Please let me know your thoughts. >>>>> >>>>> >>>>> The person who really knows this library is not around as far as >>>>> I >>>>> >>>>> know; >>>> he >>>> might be on vacation. The type returned from >>>> make_distributed_property_map >>>> is documented on <URL: >>>> http://www.osl.iu.edu/research/pbgl/documentation/graph/ >>>> distributed_property_map.html>. One thing that you could do to >>>> debug >>>> things is to put in your own color map and look at what values it >>>> ends >>>> up >>>> with at the end of the algorithm, and possibly even to put in a >>>> local >>>> color >>>> map that prints out when elements are changed. That might be a >>>> lot >>>> of >>>> work >>>> for what could end up being an obvious problem (that I just don't >>>> know >>>> how >>>> to diagnose), though. BTW, does the example in >>>> libs/graph_parallel/example/breadth_first_search.cpp work for you? >>>> It >>>> appears to be doing the same thing you want to do. If that works, >>>> it >>>> could >>>> be a problem in your visitor. >>>> >>>> >>>> I derived this code from >>>> graph_parallel/example/breadth_first_search.cpp. >>>> >>>> The problem is that I don't understand the input and the output of >>>> the >>>> >>>> example code. It would be great if I could get an explanation for >>> the >>> format of the input file. Then I can transform my graph into that >>> format >>> and pass to the algorithm. That would be enough for my current >>> purpose. >>> >>> As time permits I would try out your suggestions and let know of >>> update. >>> In >>> the meantime I am hoping that I would get input from other relevant >>> authors. >>> >>> >>> This is what I could tell from the code. >>> >> >> Input: >> http://people.sc.fsu.edu/~burkardt/data/metis_graph/<http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/> >> <http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/> >> <http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/> >> >> metis_graph.html< >> >> http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/metis_graph.html >> >>> >>> >> >> Output: >> http://www.graphviz.org/doc/info/lang.html >> >> >> Thanks Jeremiah. The link was helpful. I understood the input graph >> format. >> Its for undirected graph only. However the BFS output is still >> coming >> out >> to >> be incorrect. I tried with a sample line graph of 4 nodes and it >> exhibits the same problem as before. >> >> The distances of nodes on process 2 is not getting updated. On the >> other >> >> hand dijkstra shortest paths example is working correctly. > > Thanks > Sandeep > > > I rewrote most of your code before I realized that you're outputting all your distances on process 0, even for vertices process 0 doesn't own. The large value you see is std::numeric_limits<distance_type>::max. When you call get(distance, vertex(i, g)) for some i not owned by the current process a ghost cell is created for the requested value and a request sent to the owner of that vertex for the correct value. get() then returns whatever the default value is for the distance property map, which in this case is infinity (i.e. std::numeric_limits<distance_type>::max.
In some cases you may get the correct distance value because process 0 has previously requested that value (and it may or may not be up to date). If process 0 has never requested that distance value and it doesn't own the vertex, then you'll get infinity.
You need to gather all your data before you output it from a single node (i.e. issue a get() or request() which is a get with no return value, for each data element). If you want your code to be scalable you should output your data in a distributed fashion from all nodes at once. Remember that updated values won't be guaranteed to arrive until the next synchronization step.
If you want the modified version of your code let me know and I'll finish it and ship it your way.
-Nick
Hi Nick,
Thanks so much for looking into this. Sorry, I couldn't get to it
earlier due to other concerns. I corrected the mistake you mentioned and I don't get numeric_limit<>::max() for any nodes anymore.
I believe the graph/distributed/graphviz.hpp was outputting the distance in correct fashion.
Unfortunately, the output is still coming out to be incorrect. It was also the case with output from graphviz.hpp.
For the test graph that we mentioned before, essentially 0 --> 1 --> 2 --> 3, 0 --> 4 --> 3
the distance output is as follows: global node-id : distance 0 : 0 1 : 1 2 : 2 3 : 1 //(wrong: should be 2) 4 : 0 // should be 1
If possible can you send me your version of the code. Let me know if you need mine (the updated version).
Given the description of your problem above, and assuming you're using a block distribution with 8 vertices, it sounds like you're initializing the distance to the first vertex on *each* process to 0, as opposed to only the distance to the source. The vertex with global index 4 is actually local index 0 on process one using the above distribution. If you initialize the distances to the vertices with global indices 0 and 4 to 0, then your results make sense. Let me know if that's not the case, but I surmise that it is.
Very much so :-). Thanks for getting me started with by catching these
minor but fatal mis-understandings with PBFS code. I understood that call vertex(i,g) creates a descriptor for ith global vertex.
Also there's a problem in your depth labeling visitor. In the case of
cross-processor edges the process that owns the target of the edge doesn't necessarily have the distance to the source of the edge available locally. This will lead to incorrect distance labels even though tree and non-tree edges will still be correctly recognized since the BFS is level-synchronized. The fastest way to handle this is to modify the BFS queue to also pass distance data (which is how the shortest paths algorithms do it). You could also send the data separately and probe for it on the receiving side. Check out the distributed betweenness centrality code for how to create a distributed queue which contains tuples of data one element of which is a vertex (in order to know where to route the data). Integrating this type of vertex queue (i.e. one that contains a data payload) with BFS basically just requires handling the data payload on the receiving side.
I would try this out. So basically the default call
boost::breadth_first_search (g, start, boost::visitor(boost::make_bfs_visitor(boost::record_distances(distance, boost::on_tree_edge()))));
wouldn't work. I assumed that distributed BFS implementation did exactly what you mentioned. Although I would write my own, parallel visitor as well per your suggestions.
thanks Sandeep
Let me also add that I did modified code that initializes only the
distance to 0th vertex of processor 0. In this case i am facing the dilemma of what should I pass as start vertex for processes > 0. I can't pass the global start vertex (probably the type won't be acceptable to breadth_first_search.
I will dig further into the betweeness centrality and dijkstra code to figure this out. Appreciate your input.
The short answer is, just pass the same source vertex on all processors.
Explanation: Each processor will push the source vertex on the distributed queue but all the non-local pushes end up being no-ops since the source vertex is black at the end of the first BFS level when the messages arrive. The 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 fact that all processors push the source vertex is an artifact of reusing the sequential BFS code, it could be changed but I haven't found it to be an issue thus far.
This actually brings up an interesting feature of BFS, its possible to start a BFS from multiple source vertices by passing a different source on each processor (you can also pass a queue containing additional starting vertices if you need > num_procs sources). The strongly connected components algorithm uses this approach to run many BFSs on disconnected subgraphs in parallel.
One last note on your visitor, my statement was incorrect, sorry. I was looking at some other code and confused it with yours, your depth labeling visitor will work fine because it 'pushes' distance labels. Basically it writes the distance to the vertex it pushes onto the queue into the distributed property map at the same time (actually immediately before). This means that at the next synchronization step both the distance and the vertex descriptor will arrive, in fact the ordering of the messages insures that the distance will arrive prior to the vertex on the queue. Sorry about that, I was looking at another visitor that was 'pulling' data, which is much more problematic.
Hopefully that solves all your problems and my apologies again on leading you to believe there was something wrong with your visitor.
The data model is a little tricky to wrap your head around, but once you've written some code it should become more intuitive.
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
--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, Nick
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
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
Hi 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 :) How are you verifying your result? 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); } 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. Cheers, Nick
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>
participants (3)
-
Jeremiah Willcock -
Nick Edmonds -
Sandeep Gupta