1

I have found this general example for building a visitor for a depth first search, but I'm unsure of how to build a visitor for my intent.

I have an unweighted tree. I want to find all shortest routes from a root to each branch end, a vertex with only one edge connecting to the rest of the graph.

For example, in this graph (borrowed from elsewhere)

enter image description here

if 12 were the root, the branch ends would be 4, 1, 9, 10, and 7. The first route would contain 12, 11, 5, 2, 4. The second route would contain 12, 11, 5, 2, 1. And so on.

In the example provided

class MyVisitor : public boost::default_dfs_visitor
{
public:
  void discover_vertex(MyVertex v, const MyGraph& g) const
  {
    cerr << v << endl;
    return;
  }
};

I do no see a way to determine which route discover_vertex is currently searching.

How can my intent be implemented?

Community
  • 1
  • 1
  • Sorry, I have read the question more carefully and now I don't understand it at all. Obviously you cannot change the boost visitor interface. Your visitor object should probably keep track of the routes. – n. m. could be an AI Dec 10 '14 at 06:39

1 Answers1

0

If you want to "track" which "route" vertex is currently being explored, you can use code similar to "predecessor_recorder" in your visitor.

Details on predefined predecessor_recorder can be found here: http://www.boost.org/doc/libs/1_57_0/libs/graph/doc/predecessor_recorder.html.

In fact, you probably would better of with dijkstra_shortest_paths. That algorithm reports a predecessor map for you. You can call Dijkstra and afterwards simply go over predecessor map and generate your paths of interest for vertices of interest.

Michael Simbirsky
  • 3,045
  • 1
  • 12
  • 24
  • Thank you for that hidden nugget. I think I'm missing something fundamental because I can't seem to reconstruct the paths from the output of these functions: http://www.boost.org/doc/libs/1_57_0/libs/graph/doc/depth_first_search.html I've avoided Dijkstra because I'm using bundled properties and can't figure out how to apply the weights. The weights are all equal in my case. –  Dec 20 '14 at 00:54
  • The algorithms DFS and BFS do not store the predecessor map; that is why you cannot extract it from their output. You can work around that using predecessor_recorder, which will register the predecessors. – Michael Simbirsky Dec 20 '14 at 04:00
  • 1
    To use Dijkstra with all edge weights equal to 1, you pass 'boost::dummy_property_map(1)' as edge-weight map to Dijkstra. – Michael Simbirsky Dec 20 '14 at 04:01