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

From: Jonathan de Halleux (dehalleux_at_[hidden])
Date: 2004-04-07 02:55:32

Hi,

Do you still have the Java source ? I would be interrested in that one.

Jonathan
At 00:28 7/04/2004 -0700, you wrote:

>I know this was a couple of days overdue, but I'm
>still learning my way through CVS.  If there's still
>an urgent need for the LCA algorithm, here it is:
>
><http://groups.yahoo.com/group/boost/files/bgl_algo/tarjan_offline_lca.zip>
>
>The example program provides a straightforward way of
>using it.
>
>Known issues:
>* The graph needs to be directed or bidirectional, it
>must be a tree, and the user must provide the root.
>* I forgot to discuss what type of output was desired.
>  As a "quick and dirty" approach I used a Boost.uBLAS
>matrix; if you have any ideas that could lead to
>better efficiency and genericity, please let me know.
>The documentation covers my approach in greater
>detail.
>* The disjoint sets parameter is available in the
>kitchen-sink version of the function but not in the
>default version; the object is strictly for utility
>purposes.  The bgl_named_params class doesn't appear
>to provide the ability to include custom named
>parameters; for this reason, I haven't included a
>named-parameter variant.  If you disagree, please let
>me know.
>* 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.  For the
>moment, the LCA algorithm runs its own recursive DFS,
>and the event visitor list parameter in the
>kitchen-sink function variant does nothing.
>
>BTW, one of the Java source files (the one with the
>Graph class) was missing, so it was necessary to
>restart from scratch.
>
>                               HTH
>                               Cromwell Enage
>
>
>__________________________________
>Do you Yahoo!?
>Yahoo! Small Business $15K Web Design Giveaway
>http://promotions.yahoo.com/design_giveaway/
>_______________________________________________
>Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

-----------------------------------------------------------------------------------
Jonathan de Halleux, Research Assistant
Center for Systems Engineering and Applied Mechanics (CESAME)
Universite catholique de Louvain
Batiment Euler , Av. Georges Lemaitre, 4 Tel : [phone]
B-1348 Louvain-la-Neuve Belgium
E-mail : dehalleux_at_[hidden]
-----------------------------------------------------------------------------------