Re: query that Bob is descendant of Alice
From: Robert Vazan <robova_at_nextra.sk>
Date: Thu, 26 Apr 2001 21:02:49 GMT
Message-ID: <3ae83d47.3289050_at_news.nextra.sk>
Date: Thu, 26 Apr 2001 21:02:49 GMT
Message-ID: <3ae83d47.3289050_at_news.nextra.sk>
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.
/Robert Received on Thu Apr 26 2001 - 23:02:49 CEST