I think that such a traversal event might be a good application for the finish_tree_edge event I suggest [1], but for which I never got a reaction. Someone an opinion? Maybe some Boost.Graph developers reading? With that you can simulate traversal events (or what I think you want them to be) really easily: Implement the traversal-handler as an internal member function and call it at whenever a vertex is discoved and whenever a tree-edge is finished (with the source of the edge as parameter). What do you think? As your traversal events are easily simulated by that and IMO do not possess a canonical semantics for undirected or non-tree graphs, I don't think it wise to load the interface with them. Regards, Alex [1] http://lists.boost.org/Archives/boost/2014/07/215699.php On 08/25/2014 07:40 AM, Jeremy Murphy wrote:

I have been trying to figure out how to use the dfs_visitor to do something every time a vertex is 'traversed', which would be (num_children(v) + 1) times for any given vertex v, for a total of (2n - 1) traversals on a graph of size n. (I have been working on rooted trees, so the application to general graphs may be a bit rough.)

The use case is calculation of Eulerian paths, which I occasionally see people asking how to do.

So although the dfs_visitor doesn't support this notion of 'traverse', I have been able to simulate it using tree_edge and finish_vertex and some post-processing. If you let "result" be an output iterator in a dfs visitor class with these member functions:

template void tree_edge(Edge const &e, Graph const &g) { *result++ = boost::source(e, g); *result++ = boost::target(e, g); }

template void finish_vertex(Vertex const &v, Graph const &) { *result++ = v; }

Then apply std::unique to the resulting sequence to remove adjacent duplicates, the result is an Eulerian circuit (if one is possible). (Alternatively you could check for duplicate values at time of traversal.)

So apart from showing a simple way to calculate Eulerian path/circuit, I wanted to suggest: is it worth adding a 'traverse/visit' event to dfs (or bfs) visitor concept for this kind of use case? It would sure reduce the computation (though not the complexity) required in this case.

Cheers.

Jeremy

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost