Near and far

[Hans-Juergen Rennau <hrennau@yahoo.de>]

Dear colleagues,

for very practical reasons I have to think about data trees in a fairly abstract way. Namely, I need a firm and formal grounding for declaring tree nodes to be "related" or "unrelated" and compare "distances" between nodes, expressing how closely nodes are related.

I am sure such definitions have been made many times and in many places, but I do not know where to look, and, besides, definitions made with a certain domain of application in mind (e.g. graph theory) may be not so useful in a different context (e.g. the implementation of a graphical mapping tool). Therefore I propose a small set of definitions of my own, and any comments, links etc. would be much appreciated.

~ ~ ~

(1) Given two nodes, N1 and N2, from a node tree, N1 is *related* to N2 if one of the following is true:

(i) N1 is N2

(ii) N1 is ancestor or descendant of N2

(iii) There is a common ancestor of N1 and N2 which is not the root node

(2) N1 and N2 are *unrelated* if they are not related.

(3) Given three nodes, N1, N2, N3, from a node tree. N1 is *more closely related* to N2 than to N3 if one of the following is true:

(i) N1 and N2 are identical, but N1 and N3 are not

(ii) N1 is an ancestor or descendant of N2, but not of N3

(iii) If N1 is an ancestor or descendant of N2 and of N3: the number of steps along the child or parent axis required to reach N2, starting at N1, is less than the number of steps required to reach N3, starting at N1

(iv) If N1 is not ancestor or descendant of N2 and not ancestor or descendant of N3: the smallest possible number of steps, each one along the child or parent axis, required to reach N2, starting at N1, is less than the smallest possible number of steps required to reach N3, starting at N1

Informally, what it all means is "the closer the nearest common ancestor-or-self, the more closely related". So it all boils down to what is the container in which both nodes considered are found.

~ ~ ~

Perhaps you can think of better alternatives, would like to share links or make a comment?

With kind regards,

Hans-Jürgen