Re: [boost] [BGL] Tarjan's offline LCA algorithm.

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2004-04-07 09:22:48

Hi Cromwell,

On Apr 7, 2004, at 2:28 AM, Cromwell Enage wrote:
> I know this was a couple of days overdue, but I'm
> still learning my way through CVS.

If you have any particular questions, I'll try to answer.

> * I tried implementing Tarjan's LCA using the builtin
> depth-first-search function and event visitor lists.
> The major stumbling block was my inability to execute
> any code during post-traversal of an edge.  (The
> on_tree_edge event fires during pre-traversal, and
> neither the on_back_edge event nor the
> on_forward_or_cross_edge event would fire using DFS on
> the example graph.)  So, in the future, I'd like to
> see an on_post_traversal event filter and a
> corresponding vis.post_traversal(edge,graph) function
> implemented, and I'm pretty sure other graph
> algorithms could use this feature, too.

That looks like a useful and straightforward addition
to the DFS visitor.

Cheers,
Jeremy

_______________________________________________
Jeremy Siek <jsiek_at_[hidden]>
http://www.osl.iu.edu/~jsiek
Ph.D. Student, Indiana University Bloomington
Graduating in August 2004 and looking for work
C++ Booster (http://www.boost.org)
_______________________________________________