Re: query that Bob is descendant of Alice

"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):

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)

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