[boost] [Graph] 'traverse' event in DFS visitor concept?

Subject: [boost] [Graph] 'traverse' event in DFS visitor concept?
From: Jeremy Murphy (jeremy.william.murphy_at_[hidden])
Date: 2014-08-25 01:40:02

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 <typename Edge, typename Graph>
        void tree_edge(Edge const &e, Graph const &g)
        {
            *result++ = boost::source(e, g);
            *result++ = boost::target(e, g);
        }

        template <typename Vertex, typename Graph>
        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