Boost logo

Boost :

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


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

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:
>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
>* 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.
> Cromwell Enage
>Do you Yahoo!?
>Yahoo! Small Business $15K Web Design Giveaway
>Unsubscribe & other changes:

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_at_[hidden]

Boost list run by bdawes at, gregod at, cpdaniel at, john at