Re: query that Bob is descendant of Alice

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 - 16:02:49 CDT