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 : +32-10-47 2595 B-1348 Louvain-la-Neuve Belgium E-mail : dehalleux@auto.ucl.ac.be -----------------------------------------------------------------------------------

Cromwell Enage <sponage@yahoo.com> 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:

Thanks. That was more than prompt enough for my needs. Usually when people talk about having to reimplement something that they don't need, it can take months.

<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.

Hmm. This turns out to be a problem for me. My graphs are not necessarily trees. The nodes are not even guaranteed to have a common ancestor. However, it has been useful as a starting point. Based on what you have, I've managed to whip up a suitable implementation for me. It is rather hard-coded to my problem and probably wildly inefficient to boot, so there probably isn't much point is posting it here. Thanks, Walter Landry wlandry@ucsd.edu