Graph Library Question
Hi, I was able to find the shortest distances between my starting node and the rest of the nodes. Now I would like to output the path between my starting node and destination node. I have tried a number of different examples but none of them seem to do what I want. I am pretty sure I need to use some type of get but I can not find it in the documentation. Thanks for any help.
I was able to find the shortest distances between my starting node and the rest of the nodes.
Now I would like to output the path between my starting node and destination node. I have tried a number of different examples but none of them seem to do what I want.
For this you need the predecessor map, just as you needed the distance map to look up distances. This is what Arne Vogel wrote last week: To read the path from the PredecessorMap, you work your way backwards from the destination vertex to the source vertex, always looking up the predecessor of the current vertex in the predecessor map, until the current vertex is equal to the source vertex. Then you just reverse the path if necessary. Or, as simplified code: vector<vertex> path; for ( vertex current = destination; current != source; current = predecessor[current] ) { path.push_back(current); } path.push_back(source); std::reverse(path.begin(), path.end());
Is there an example of how to do this on the web site?
Thanks
Sent from my iPhone
On May 16, 2014, at 9:13, alex
I was able to find the shortest distances between my starting node and the rest of the nodes.
Now I would like to output the path between my starting node and destination node. I have tried a number of different examples but none of them seem to do what I want.
For this you need the predecessor map, just as you needed the distance map to look up distances.
This is what Arne Vogel wrote last week:
To read the path from the PredecessorMap, you work your way backwards from the destination vertex to the source vertex, always looking up the predecessor of the current vertex in the predecessor map, until the current vertex is equal to the source vertex. Then you just reverse the path if necessary. Or, as simplified code:
vector<vertex> path; for ( vertex current = destination; current != source; current = predecessor[current] ) { path.push_back(current); } path.push_back(source); std::reverse(path.begin(), path.end());
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Hi Alex,
I tried to implement the simplified code but I guess I really do not understand the Boost Graph lib.
Here is my function:
std::string myGraph::GetPathAndDistanceBetweenNodes(int StartNode, int EndNode)
{
std::string OutputPath = "";
std::stringstream TempString;
boost::property_map
I was able to find the shortest distances between my starting node and the rest of the nodes.
Now I would like to output the path between my starting node and destination node. I have tried a number of different examples but none of them seem to do what I want.
For this you need the predecessor map, just as you needed the distance map to look up distances. This is what Arne Vogel wrote last week: To read the path from the PredecessorMap, you work your way backwards from the destination vertex to the source vertex, always looking up the predecessor of the current vertex in the predecessor map, until the current vertex is equal to the source vertex. Then you just reverse the path if necessary. Or, as simplified code: vector<vertex> path; for ( vertex current = destination; current != source; current = predecessor[current] ) { path.push_back(current); } path.push_back(source); std::reverse(path.begin(), path.end()); _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
I tried to implement the simplified code but I guess I really do not understand the Boost Graph lib.
You might find it easier to use shared_array_property_maps (I do). Try if
the following works for you.
typedef typename boost::graph_traits
participants (2)
-
alex -
Ken Kazinski