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

Subject: Re: [boost] [Graph] 'traverse' event in DFS visitor concept?
From: Alexander Lauser (alxlaus_at_[hidden])
Date: 2014-08-25 04:48:37

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 <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
> 
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
>