Node paths and distances¶

The toytree.distance module includes a number of methods for evaluating distances between nodes in a tree. This includes methods for generating paths between nodes such that each node or edge along the path can be evaluated, as well as methods for measuring distances as the sum of these values. A set of related methods for measuring "tree distances" as the differences between tree topologies are also contained in this module, but are described in a separate tutorial. Here we focus on distances between nodes within a single tree.

In [1]:

Copied!

import toytree

# a tree used in examples
tree = toytree.rtree.unittree(ntips=12, seed=123)
tree.draw(ts='s');
import toytree

# a tree used in examples
tree = toytree.rtree.unittree(ntips=12, seed=123)
tree.draw(ts='s');

Node Paths¶

get_node_path¶

The get_node_path method returns a tuple of Node objects between two queried Nodes of a tree (including both terminal nodes). This traces the shortest connecting path on the tree.

In [2]:

Copied!

# get all nodes between node 0 and 15
tree.distance.get_node_path(0, 15)
# get all nodes between node 0 and 15
tree.distance.get_node_path(0, 15)

Out[2]:

(<Node(idx=0, name='r0')>,
 <Node(idx=13)>,
 <Node(idx=17)>,
 <Node(idx=16)>,
 <Node(idx=15)>)

iter_node_path¶

The iter_node_path is a generator similar to the function above. This can be more efficient when writing a method that performs many iterations over a large tree, since the search can be terminated when a particular target is found while iterating along each path.

In [3]:

Copied!

list(tree.distance.iter_node_path(0, 15))
list(tree.distance.iter_node_path(0, 15))

Out[3]:

[<Node(idx=0, name='r0')>,
 <Node(idx=13)>,
 <Node(idx=17)>,
 <Node(idx=16)>,
 <Node(idx=15)>]

get_farthest_node¶

Returns the node that is farthest from a selected node. If multiple nodes are equidistant the one with the lowest idx label is returned.

In [4]:

Copied!

tree.distance.get_farthest_node("r0")
tree.distance.get_farthest_node("r0")

Out[4]:

<Node(idx=9, name='r9')>

Node Distances¶

Several methods are available to measure distances between nodes. The most general is get_node_distance_matrix, which returns the distances between all nodes. However, several other methods also provide convenient methods for measuring distances between nodes with particular relationships.

get_farthest_node_distance¶

Returns the distance to the farthest node from a selected node.

In [5]:

Copied!

tree.distance.get_farthest_node_distance(15)
tree.distance.get_farthest_node_distance(15)

Out[5]:

1.6666666666666665

get_descendant_dists¶

Returns a dictionary mapping Nodes to distances, where each node is a descendant of the selected target node, and the distances are the descendant node's distance from the target node.

In [6]:

Copied!

tree.distance.get_descendant_dists(15)
tree.distance.get_descendant_dists(15)

Out[6]:

{<Node(idx=15)>: 0,
 <Node(idx=3, name='r3')>: 0.3333333333333333,
 <Node(idx=14)>: 0.16666666666666666,
 <Node(idx=4, name='r4')>: 0.3333333333333333,
 <Node(idx=5, name='r5')>: 0.3333333333333333}

iter_descendant_dists¶

Similar to above but returns a generator that iterates over descendant nodes.

In [7]:

Copied!

list(tree.distance.iter_descendant_dists(15))
list(tree.distance.iter_descendant_dists(15))

Out[7]:

[(<Node(idx=15)>, 0),
 (<Node(idx=3, name='r3')>, 0.3333333333333333),
 (<Node(idx=14)>, 0.16666666666666666),
 (<Node(idx=4, name='r4')>, 0.3333333333333333),
 (<Node(idx=5, name='r5')>, 0.3333333333333333)]

get_node_distance_matrix¶

This returns an array with distances between all nodes as the sum of the edges separating them. The nodes are listed in node idx order. By default the result is returned as a numpy array, but using the argument df=True will return as a pandas DataFrame where nodes with names will be labeled by their name, and other labels (e.g. internal) by their idx label. The option topology_only can be used to measure distance as the number of nodes between each pair, rather than the sum edge lengths.

In [8]:

Copied!

tree.distance.get_node_distance_matrix(df=True)
tree.distance.get_node_distance_matrix(df=True)

Out[8]:

	r0	r1	r2	r3	r4	r5	r6	r7	r8	r9	...	13	14	15	16	17	18	19	20	21	22
r0	0.000000	1.000000	1.000000	1.333333	1.333333	1.333333	1.333333	1.666667	1.666667	2.000000	...	0.500000	1.166667	1.000000	0.833333	0.666667	1.000000	0.833333	1.333333	1.166667	1.000000
r1	1.000000	0.000000	0.666667	1.333333	1.333333	1.333333	1.333333	1.666667	1.666667	2.000000	...	0.500000	1.166667	1.000000	0.833333	0.666667	1.000000	0.833333	1.333333	1.166667	1.000000
r2	1.000000	0.666667	0.000000	1.333333	1.333333	1.333333	1.333333	1.666667	1.666667	2.000000	...	0.500000	1.166667	1.000000	0.833333	0.666667	1.000000	0.833333	1.333333	1.166667	1.000000
r3	1.333333	1.333333	1.333333	0.000000	0.666667	0.666667	1.000000	1.666667	1.666667	2.000000	...	0.833333	0.500000	0.333333	0.500000	0.666667	1.000000	0.833333	1.333333	1.166667	1.000000
r4	1.333333	1.333333	1.333333	0.666667	0.000000	0.333333	1.000000	1.666667	1.666667	2.000000	...	0.833333	0.166667	0.333333	0.500000	0.666667	1.000000	0.833333	1.333333	1.166667	1.000000
r5	1.333333	1.333333	1.333333	0.666667	0.333333	0.000000	1.000000	1.666667	1.666667	2.000000	...	0.833333	0.166667	0.333333	0.500000	0.666667	1.000000	0.833333	1.333333	1.166667	1.000000
r6	1.333333	1.333333	1.333333	1.000000	1.000000	1.000000	0.000000	1.666667	1.666667	2.000000	...	0.833333	0.833333	0.666667	0.500000	0.666667	1.000000	0.833333	1.333333	1.166667	1.000000
r7	1.666667	1.666667	1.666667	1.666667	1.666667	1.666667	1.666667	0.000000	1.333333	2.000000	...	1.166667	1.500000	1.333333	1.166667	1.000000	0.666667	0.833333	1.333333	1.166667	1.000000
r8	1.666667	1.666667	1.666667	1.666667	1.666667	1.666667	1.666667	1.333333	0.000000	2.000000	...	1.166667	1.500000	1.333333	1.166667	1.000000	0.666667	0.833333	1.333333	1.166667	1.000000
r9	2.000000	2.000000	2.000000	2.000000	2.000000	2.000000	2.000000	2.000000	2.000000	0.000000	...	1.500000	1.833333	1.666667	1.500000	1.333333	1.333333	1.166667	0.666667	0.833333	1.000000
r10	2.000000	2.000000	2.000000	2.000000	2.000000	2.000000	2.000000	2.000000	2.000000	1.333333	...	1.500000	1.833333	1.666667	1.500000	1.333333	1.333333	1.166667	0.666667	0.833333	1.000000
r11	2.000000	2.000000	2.000000	2.000000	2.000000	2.000000	2.000000	2.000000	2.000000	1.666667	...	1.500000	1.833333	1.666667	1.500000	1.333333	1.333333	1.166667	1.000000	0.833333	1.000000
12	0.666667	0.333333	0.333333	1.000000	1.000000	1.000000	1.000000	1.333333	1.333333	1.666667	...	0.166667	0.833333	0.666667	0.500000	0.333333	0.666667	0.500000	1.000000	0.833333	0.666667
13	0.500000	0.500000	0.500000	0.833333	0.833333	0.833333	0.833333	1.166667	1.166667	1.500000	...	0.000000	0.666667	0.500000	0.333333	0.166667	0.500000	0.333333	0.833333	0.666667	0.500000
14	1.166667	1.166667	1.166667	0.500000	0.166667	0.166667	0.833333	1.500000	1.500000	1.833333	...	0.666667	0.000000	0.166667	0.333333	0.500000	0.833333	0.666667	1.166667	1.000000	0.833333
15	1.000000	1.000000	1.000000	0.333333	0.333333	0.333333	0.666667	1.333333	1.333333	1.666667	...	0.500000	0.166667	0.000000	0.166667	0.333333	0.666667	0.500000	1.000000	0.833333	0.666667
16	0.833333	0.833333	0.833333	0.500000	0.500000	0.500000	0.500000	1.166667	1.166667	1.500000	...	0.333333	0.333333	0.166667	0.000000	0.166667	0.500000	0.333333	0.833333	0.666667	0.500000
17	0.666667	0.666667	0.666667	0.666667	0.666667	0.666667	0.666667	1.000000	1.000000	1.333333	...	0.166667	0.500000	0.333333	0.166667	0.000000	0.333333	0.166667	0.666667	0.500000	0.333333
18	1.000000	1.000000	1.000000	1.000000	1.000000	1.000000	1.000000	0.666667	0.666667	1.333333	...	0.500000	0.833333	0.666667	0.500000	0.333333	0.000000	0.166667	0.666667	0.500000	0.333333
19	0.833333	0.833333	0.833333	0.833333	0.833333	0.833333	0.833333	0.833333	0.833333	1.166667	...	0.333333	0.666667	0.500000	0.333333	0.166667	0.166667	0.000000	0.500000	0.333333	0.166667
20	1.333333	1.333333	1.333333	1.333333	1.333333	1.333333	1.333333	1.333333	1.333333	0.666667	...	0.833333	1.166667	1.000000	0.833333	0.666667	0.666667	0.500000	0.000000	0.166667	0.333333
21	1.166667	1.166667	1.166667	1.166667	1.166667	1.166667	1.166667	1.166667	1.166667	0.833333	...	0.666667	1.000000	0.833333	0.666667	0.500000	0.500000	0.333333	0.166667	0.000000	0.166667
22	1.000000	1.000000	1.000000	1.000000	1.000000	1.000000	1.000000	1.000000	1.000000	1.000000	...	0.500000	0.833333	0.666667	0.500000	0.333333	0.333333	0.166667	0.333333	0.166667	0.000000

23 rows × 23 columns

get_node_distance¶

Returns the sum distance between two nodes. A shorter and faster call than getting the full distance matrix to calculate one distance.

In [9]:

Copied!

tree.distance.get_node_distance(15, 17)
tree.distance.get_node_distance(15, 17)

Out[9]:

0.3333333333333333

get_tip_distance_matrix¶

Return a distance matrix for only the tip nodes in the tree.

In [10]:

Copied!

tree.distance.get_tip_distance_matrix(df=True)
tree.distance.get_tip_distance_matrix(df=True)

Out[10]:

	r0	r1	r2	r3	r4	r5	r6	r7	r8	r9	r10	r11
r0	0.000000	1.000000	1.000000	1.333333	1.333333	1.333333	1.333333	1.666667	1.666667	2.000000	2.000000	2.000000
r1	1.000000	0.000000	0.666667	1.333333	1.333333	1.333333	1.333333	1.666667	1.666667	2.000000	2.000000	2.000000
r2	1.000000	0.666667	0.000000	1.333333	1.333333	1.333333	1.333333	1.666667	1.666667	2.000000	2.000000	2.000000
r3	1.333333	1.333333	1.333333	0.000000	0.666667	0.666667	1.000000	1.666667	1.666667	2.000000	2.000000	2.000000
r4	1.333333	1.333333	1.333333	0.666667	0.000000	0.333333	1.000000	1.666667	1.666667	2.000000	2.000000	2.000000
r5	1.333333	1.333333	1.333333	0.666667	0.333333	0.000000	1.000000	1.666667	1.666667	2.000000	2.000000	2.000000
r6	1.333333	1.333333	1.333333	1.000000	1.000000	1.000000	0.000000	1.666667	1.666667	2.000000	2.000000	2.000000
r7	1.666667	1.666667	1.666667	1.666667	1.666667	1.666667	1.666667	0.000000	1.333333	2.000000	2.000000	2.000000
r8	1.666667	1.666667	1.666667	1.666667	1.666667	1.666667	1.666667	1.333333	0.000000	2.000000	2.000000	2.000000
r9	2.000000	2.000000	2.000000	2.000000	2.000000	2.000000	2.000000	2.000000	2.000000	0.000000	1.333333	1.666667
r10	2.000000	2.000000	2.000000	2.000000	2.000000	2.000000	2.000000	2.000000	2.000000	1.333333	0.000000	1.666667
r11	2.000000	2.000000	2.000000	2.000000	2.000000	2.000000	2.000000	2.000000	2.000000	1.666667	1.666667	0.000000

get_internal_node_distance_matrix¶

Return a distance matrix for only the internal nodes in a tree.

In [11]:

Copied!

tree.distance.get_internal_node_distance_matrix(df=True)
tree.distance.get_internal_node_distance_matrix(df=True)

Out[11]:

	12	13	14	15	16	17	18	19	20	21	22
12	0.000000	0.166667	0.833333	0.666667	0.500000	0.333333	0.666667	0.500000	1.000000	0.833333	0.666667
13	0.166667	0.000000	0.666667	0.500000	0.333333	0.166667	0.500000	0.333333	0.833333	0.666667	0.500000
14	0.833333	0.666667	0.000000	0.166667	0.333333	0.500000	0.833333	0.666667	1.166667	1.000000	0.833333
15	0.666667	0.500000	0.166667	0.000000	0.166667	0.333333	0.666667	0.500000	1.000000	0.833333	0.666667
16	0.500000	0.333333	0.333333	0.166667	0.000000	0.166667	0.500000	0.333333	0.833333	0.666667	0.500000
17	0.333333	0.166667	0.500000	0.333333	0.166667	0.000000	0.333333	0.166667	0.666667	0.500000	0.333333
18	0.666667	0.500000	0.833333	0.666667	0.500000	0.333333	0.000000	0.166667	0.666667	0.500000	0.333333
19	0.500000	0.333333	0.666667	0.500000	0.333333	0.166667	0.166667	0.000000	0.500000	0.333333	0.166667
20	1.000000	0.833333	1.166667	1.000000	0.833333	0.666667	0.666667	0.500000	0.000000	0.166667	0.333333
21	0.833333	0.666667	1.000000	0.833333	0.666667	0.500000	0.500000	0.333333	0.166667	0.000000	0.166667
22	0.666667	0.500000	0.833333	0.666667	0.500000	0.333333	0.333333	0.166667	0.333333	0.166667	0.000000