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 , 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.
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.
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk