PLoS supp. material by Hermann Cuntz
The labeling of the nodes of a tree should be unique if one wants
to for example compare the graphs of two trees topologically or electrotonically.
In principle, the labels on the nodes describing a graph
can be attributed arbitrarily.
As mentioned before, all permutations of labels (indices)
i → j result in the same tree by rearranging
the adjacency matrix and any metric elements attributed to the nodes:
dA(i,i) → dA(j,j)
X(i) → X(j)
Y(i) → Y(j)
Z(i) → Z(j)
D(i) → D(j)
In a hierarchical sorting, node label values always increase towards daughter nodes.
This can constrain the otherwise arbitrary labelling.
As discussed before, labelling can be constrained further in the BCT order
(see introduction part “BCT formalism”).
Within any sub-tree, the labelling is then continuous.
A truly unique labelling arises in a topological sorting
when labels additionally carry a weight according to some
topological values such as the topological depth or the number of child nodes.
At each branch point for example,
the heavier sub-trees can then be labelled first.
Rearranging the metrics of a tree based
on its topologically sorted label order leads
to a unique electrotonic equivalent tree.
In order to arrive to such a labelling,
nodes are first sorted according to their topological depth.
Each node is then inserted in that order into a one dimensional
string one by one directly behind its direct parent node.
Subsequently, the resulting string of labels is mapped back onto the nodes of the tree.
This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 License