From: "Magnus Lie Hetland" Newsgroups: comp.databases.theory,comp.theory Subject: Re: query that Bob is descendant of Alice Date: Sun, 22 Apr 2001 17:40:01 +0200 Organization: Norwegian university of science and technology Lines: 39 Message-ID: <9buu0b$96h$1@tyfon.itea.ntnu.no> References: <3ae19a54.156698@news.nextra.sk> <9bsksm$p76$06$1@news.t-online.com> <9bu2pc$amj$1@pegasus.csx.cam.ac.uk> NNTP-Posting-Host: dhcp-111-15.idi.ntnu.no X-Trace: tyfon.itea.ntnu.no 987953995 9425 129.241.111.250 (22 Apr 2001 15:39:55 GMT) X-Complaints-To: usenet@itea.ntnu.no NNTP-Posting-Date: Sun, 22 Apr 2001 15:39:55 +0000 (UTC) X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 5.50.4522.1200 X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4522.1200 "Nick Maclaren" wrote in message news:9bu2pc$amj$1@pegasus.csx.cam.ac.uk... [snip] > >> 1. Can this be done? (practically) If you have a DAG you can find whether there is a path from A to B in O(n) time and memory, assuming that the degree of any node is o(n): 1. Perform a topological sort on the data (can be a preprocessing step) 2. Assuming that A is to the left of B (otherwise we have failed already), start traversing the nodes from A to B (in sorted order): 2.1. Mark node A with 1 2.2. Go one step to the right 2.3. For each edge pointing into current node: If predecessor is marked with 1, mark current with 1 (and break) 2.4 If we haven't reached B yet, go to 2.2 3. If B is marked with 1, then A can reach B. Otherwise it cannot. (This can also be used to calculate the distance) If this misses your question -- sorry. :) -- Magnus Lie Hetland http://www.hetland.org "Reality is that which, when you stop believing in it, doesn't go away." -- Philip K. Dick