Search code examples
c++boostdepth-first-searchboost-graphvisitor-pattern

A visitor to provide all vertex routes from root to each branch end

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?

Solution

  • 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.