On Tue, 23 Feb 2010, Alexandre de Morais Amory wrote:
Hi,
I am starting to use BGL. I manage to read/write in dot format, add few attribs, etc.
my next task is to get the set of vertex in the shortest path between vertex A and B. In a graph like this:
a - b b - c c - d
assuming 'a' and 'c', the result would be {a,b,c}.
I know it sounds silly, but most similar examples I could find are much more complex than this. I guess breadth_first_search would solve the problem, but I am having trouble with the visitor concept... how to implement a visitor to get the set of vertex in the path between two points.
Other features of the problem: I am assuming an undirected graph. all edges have unitary distances. If there are multiple shortest paths between A and B, any of the valid solutions can be returned.
You do not need to write your own visitor: the built-in predecessor_recorder will fill in the path for you. Define a predecessor property for your graph (either internal to the graph or external), and then pass boost::record_predecessors(pred_map, boost::on_tree_edge()) as the visitor to BFS. To get the path, assume that you are searching for a path from s to t. Run BFS with s as the start vertex. You can get the path with code like: std::vector<vertex> path(1, t); vertex v = t; while (v != s) { v = get(pred_map, v); path.push_back(v); } std::reverse(path.begin(), path.end()); If you do not know that there is a path from s to t, initialize the predecessor map with boost::graph_traits<your_graph>::null_vertex(). After BFS, if get(pred_map, t) is equal to null_vertex(), there is no path from s to t. -- Jeremiah Willcock