From: Lie-Quan Lee (llee_at_[hidden])
Date: 2002-01-11 12:06:31
If the graph is a rooted tree, Start depth-first visit from the root
with discover time, finish time and parent recorded. After that, you can
get vertex u's parent and ask for its parent's parent ... to get a full
set of ancestors. To answer the second quesiton (is vertex A
an ancestor to vertex B), check the condition
discover_time(A) <= discover_time(B) and
finish_time(A) >= finish_time(B)
On the other hand, if you are talking about a general directed graph,
maybe a transitive closure-like algorithm is what you want?
On Fri, 2002-01-11 at 10:32, Asger Alstrup Nielsen wrote:
> What is the best way to get the full set of ancestors to a vertex in a
> directed graph?
> Alternatively, how can I answer the question:
> Is vertex A an ancestor to vertex B?
> Asger Alstrup
> Info: http://www.boost.org Send unsubscribe requests to: <mailto:boost-unsubscribe_at_[hidden]>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
-- Lie-Quan Lee (AKA: Rich Lee) Research Associate Open Systems Laboratory Phone: 1-812-855-3608 Computer Science Department Email: llee_at_[hidden] Indiana University Homepage: http://www.osl.iu.edu/~llee
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk