Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a simple, 1-directional tree representing the veins in a human body. It looks somewhat like this (red dots are nodes, blood flow is always downwards, sorry for my drawing):

enter image description here

What I need is a way to compare any two node N1 & N2 to see if N2 is downstream of N1, i.e. blood reaching N2 has passed N1. Which is the same as testing if N2 is a descendant of N1, I think.

I could of course use a recursive solution but that's WAY too slow. And a lookup table is WAY to big on memory.

What I'm trying to figure out is if there is a way to number each node and save this information, so that at runtime I can do a simple comparison of the two nodes' values as a O(1) complexity operation. I initially thought of simply using the distance from the source but of course that's no good.

Is this even possible and if so how could I approach it? I should re-emphasise this is for run-time use, in fact it's for real-time rendering (say 30Hz) where each frame all nodes must be compared against an 'insertion node' to see if they are downstream... which means it has to be very time & space efficient.

share|improve this question
    
What's your recursive solution that's "WAY too slow"? Just walk up the tree from $N_2$ until you hit either $N_1$ or the root. You can write this in a while loop. –  Rahul Jan 23 '13 at 23:18
    
@rahul Much better solutions are available. –  MJD Jan 24 '13 at 3:01
    
This is being done in a shader program on the GPU, which basically puts strict limits on the types of data structures and control structures (looping etc) I can do. I'm not sure I can explain better without a lot of words! –  Mr. Boy Jan 24 '13 at 10:06

1 Answer 1

up vote 3 down vote accepted

First, prepare a data structure as follows: Each node $N$ will be assigned a lower and an upper bound, $[lo, hi]$, where $lo$ is less than the smallest lower bound of any descendant, and $hi$ greater than the greatest upper bound of any descendant of $N$.

To prepare this data structure, traverse the tree in depth-first order. Maintain a counter, $c$. The first time your traversal reaches a new node $N$, set its lower bound $lo_N = c$ and increment $c$. The last time your traversal reaches $N$, just before the traversal ascends to $N$'s parent, set $N$'s upper bound $hi_N = c$ and increment $c$. For a leaf $\ell$, you have the option of setting $lo_\ell = hi_\ell$ or $lo_\ell + 1 = hi_\ell$; either way will work. Store all the $lo$ and $hi$ values in a table so that you can look up a node's $lo$ and $hi$ values efficiently.

Once you have the mapping from nodes to $[lo, hi]$ bounds, it is easy to efficiently check if $M$ is a descendant of $N$: Look up the bounds for $M$ and $N$, and then $M$ is a descendant of $N$ if and only if both $lo_M \ge lo_N$ and $hi_M\le hi_N$.

Here's what it might look like:

same tree, with labels

To tabulate the bounds requires a constant amount of time per node, and the complete table requires a constant amount of space per node. To check whether one node is a descendant of another requires constant time.

share|improve this answer
    
I see that I skipped the label 10 in my diagram, but it doesn't actually matter as long as the counter $c$ is strictly increasing. –  MJD Jan 24 '13 at 3:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.