Re: query that Bob is descendant of Alice

From: Magnus Lie Hetland <mlh_at_idi.ntnu.no>
Date: Sun, 22 Apr 2001 17:40:01 +0200
Message-ID: <9buu0b$96h$1@tyfon.itea.ntnu.no>

"Nick Maclaren" <nmm1_at_cus.cam.ac.uk> wrote in message news:9bu2pc$amj$1_at_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):

Perform a topological sort on the data (can be a preprocessing step)
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

Received on Sun Apr 22 2001 - 10:40:01 CDT