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

From: Cromwell Enage (sponage_at_[hidden])
Date: 2004-04-07 02:28:38

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/