Pseudo-Distances within a depth-determination problem

  • Thread starter Thread starter Shaitan00
  • Start date Start date
Join the discussion
Ask a follow-up here, or get your own question answered by working scientists, mathematicians and engineers — people, not an autocomplete.
Real named experts · corrections over time · the nuance an AI answer skips
Sign up Log in
4 replies · 3K views
Shaitan00
Messages
13
Reaction score
0
I was given the following problem description for a depth-determination problem, however I am completely unable to figure out how this "pseudo-distance" feature works, if anyone has any clues and can provide a uber-simple example it would be much appreciated - I just can't see how it works/applies.

[Problem]
In the depth-determination problem, we maintain a forest F = {Ti} of rooted trees. We use the disjoint-set forest S=Si, where each set Si (which is itself a tree) corresponds to a tree Ti in the forest F. The tree structure within a set Si, however, does not necessarily correspond to that of Ti. In fact, the implementation of Si does not record the exact parent-child relationships but nevertheless allows us to determine any node’s depth in Ti.

The key idea is to maintain each node v a ”pseudo-distance” d[v], which is defined so that the sum of the pseudo-distances along the path from v to the root of its set Si equals the depth of v in Ti. That is, if the path from v to its root in v0 , v1 , . . . , vk , where v0 = v and vk is Si’s root, then the depth of v in Ti is the sum of d[vj] where j=0 to j=k.
 
Physics news on Phys.org
The key idea is to maintain each node v a ”pseudo-distance” d[v], which is defined so that the sum of the pseudo-distances along the path from v to the root of its set Si equals the depth of v in Ti.
The definition of "pseudo-distance" seems to be recursive here. Could you check the wording of the question?
 
Very possible that is it recursive - because the wording is copy/paste from the problem statement - I just don't see how it works...

If Si is a subtree of Ti (but they don't necessarily have the same root) then how can d[v] in Si allow you to calculate the depth it Ti? Or am I looking at this completely wrong?

Thanks,
 
It is common to have a recursive algorithm. But a definition that is recursive would not help the cause of defining or explaining something.
For example:
"A rectangle is a rectangle that has opposite sides parallel and adjacent side perpendicular to each other."
is a faulty definition.
 
I see your point - but this is given in the textbook, not sure how else to interpret it...