Re: query that Bob is descendant of Alice

In article <3ae83d47.3289050_at_news.nextra.sk>, Robert Vazan <robova_at_nextra.sk> wrote:
>nmm1_at_cus.cam.ac.uk (Nick Maclaren) wrote:
>>All you do is to complete the graph. This can be done using links,
>>but it is typically most efficient using Warshall's method on a
>>bit matrix. With care, you can use vectorised bit operations on
>>complete words, and it runs like the clappers. I was analysing
>>programs with 1,000 routines in the 1970s and not using much in
>>the way of resources.
>
>OK, this is transitive closure. But if you have deep graph?
>For example, portion of expanded execution path with
>branches in it. 1,000 nodes generate ~ 500,000 links.
>100,000 nodes are imposible.

Not really. 100,000 nodes needs 2.5 GB even with two copies, and c. 1.6x10^13 operations. Even on a scalar machine, you could do that in 6 months, and it is parallelisable.

Remember the context was that of routine calls - a program with 100,000 inter-calling routines is pretty unusual. It is normally fairly easy to divide the problem up into (say) 1,000 components of 100 routines each, and you are rarely interested in both the component linkage and the internal routine linkage.

Regards,
Nick Maclaren,
University of Cambridge Computing Service, New Museums Site, Pembroke Street, Cambridge CB2 3QG, England. Email: nmm1_at_cam.ac.uk
Tel.: +44 1223 334761 Fax: +44 1223 334679 Received on Thu Apr 26 2001 - 22:44:14 CEST