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

From: Walter Landry (wlandry_at_[hidden])
Date: 2004-04-08 21:21:29

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