Skip to content

Geodesic Distances

Calculate geodesic ("along-the-arbor") distances.

Notes

Under-the-hood, this uses two different implementations depending on whether a full all-by-all or a partial (via sources/targets) matrix is requested. The partial implementation is faster and more memory efficient for small-ish subsets of nodes. However, for subsets that include a large portion of the nodes, it may be faster to calculate the full matrix and then subset it.

PARAMETER DESCRIPTION
node_ids 
     Array of node IDs.

TYPE: (N, ) array

parent_ids 
     Array of parent IDs for each node. Root nodes' parents
     must be -1.

TYPE: (N, ) array

directed 
     If ``True`` will only return distances in the direction of
     the child -> parent (i.e. towards the root) relationship.

TYPE: bool DEFAULT: False

sources 
     Source node IDs. If ``None`` all nodes are used as sources.

TYPE: iterable DEFAULT: None

targets 
     Target node IDs. If ``None`` all nodes are used as targets.

TYPE: iterable DEFAULT: None

weights 
     Array of distances for each child -> parent connection.
     If ``None`` all node to node distances are set to 1.

TYPE: (N, ) float32 array DEFAULT: None

RETURNS DESCRIPTION
matrix

Geodesic distances. Unreachable nodes are set to -1. If source and/or targets are provided, the matrix will be ordered accordingly.

TYPE: float32 (single) array

Examples:

>>> import navis_fastcore as fastcore
>>> import numpy as np
>>> node_ids = np.arange(7)
>>> parent_ids = np.array([-1, 0, 1, 2, 1, 4, 5])
>>> fastcore.geodesic_matrix(node_ids, parent_ids)
array([[0., 1., 2., 3., 2., 3., 4.],
       [1., 0., 1., 2., 1., 2., 3.],
       [2., 1., 0., 1., 2., 3., 4.],
       [3., 2., 1., 0., 3., 4., 5.],
       [2., 1., 2., 3., 0., 1., 2.],
       [3., 2., 3., 4., 1., 0., 1.],
       [4., 3., 4., 5., 2., 1., 0.]], dtype=float32)
>>> fastcore.geodesic_matrix(
...     node_ids, parent_ids,
...     sources=[0, 1], targets=[5, 6]
...     )
array([[3., 4.],
       [2., 3.]], dtype=float32)

Calculate geodesic ("along-the-arbor") distances between pairs of nodes.

This uses a simple algorithm that calculates distances using brute force. It's fast because we parallelize the calculation of each pair of nodes.

PARAMETER DESCRIPTION
node_ids 
     Array of node IDs.

TYPE: (N, ) array

parent_ids 
     Array of parent IDs for each node. Root nodes' parents
     must be -1.

TYPE: (N, ) array

pairs 
     Pairs of node IDs for which to calculate distances.

TYPE: (N, 2) array

directed 
     If ``True`` will only return distances in the direction of
     the child -> parent (i.e. towards the root) relationship.

TYPE: bool DEFAULT: False

weights 
     Array of distances for each child -> parent connection.
     If ``None`` all node to node distances are set to 1.

TYPE: (N, ) float32 array DEFAULT: None

RETURNS DESCRIPTION
matrix

Geodesic distances. Unreachable nodes are set to -1.

TYPE: float32 (single) array

Examples:

>>> import navis_fastcore as fastcore
>>> import numpy as np
>>> node_ids = np.arange(7)
>>> parent_ids = np.array([-1, 0, 1, 2, 1, 4, 5])
>>> pairs = np.array([(0, 1), (0, 2)])
>>> fastcore.geodesic_pairs(node_ids, parent_ids, pairs)
array([1., 2.], dtype=float32)

Find the nearest target for each source.

This is a memory-efficient companion to :func:geodesic_matrix: instead of materialising the full sources x targets distance matrix it only keeps, for each source, the distance to and ID of the nearest target. It uses a linear-time algorithm and therefore scales to several 100k nodes.

A source that is itself a target is matched to the nearest other (distinct) target, never to itself.

PARAMETER DESCRIPTION
node_ids 
     Array of node IDs.

TYPE: (N, ) array

parent_ids 
     Array of parent IDs for each node. Root nodes' parents
     must be -1.

TYPE: (N, ) array

sources 
     Source node IDs. If ``None`` all nodes are used as sources.

TYPE: iterable DEFAULT: None

targets 
     Target node IDs. If ``None`` all nodes are used as targets.

TYPE: iterable DEFAULT: None

directed 
     If ``True`` only consider targets in the direction of the
     child -> parent (i.e. towards the root) relationship.

TYPE: bool DEFAULT: False

weights 
     Array of distances for each child -> parent connection.
     If ``None`` all node to node distances are set to 1.

TYPE: (N, ) float32 array DEFAULT: None

RETURNS DESCRIPTION
distances

Distance from each source to its nearest target. Sources without a reachable target are set to -1. Ordered to match sources (or node_ids if sources is None).

TYPE: float32 (single) array

nearest

Node ID of the nearest target for each source, in the same order as distances. Sources without a reachable target are set to -1.

TYPE: array

Examples:

>>> import navis_fastcore as fastcore
>>> import numpy as np
>>> node_ids = np.arange(7)
>>> parent_ids = np.array([-1, 0, 1, 2, 1, 4, 5])
>>> dist, nearest = fastcore.geodesic_nearest(
...     node_ids, parent_ids,
...     sources=[0, 3], targets=[5, 6]
...     )
>>> dist
array([3., 4.], dtype=float32)
>>> nearest
array([5, 5])

Find the farthest target for each source.

This is the mirror image of :func:geodesic_nearest: it uses the same linear-time algorithm but keeps, for each source, the distance to and ID of the farthest target. Like its counterpart it never materialises the full sources x targets distance matrix and therefore scales to several 100k nodes.

A source that is itself a target is matched to the farthest other (distinct) target, never to itself.

PARAMETER DESCRIPTION
node_ids 
     Array of node IDs.

TYPE: (N, ) array

parent_ids 
     Array of parent IDs for each node. Root nodes' parents
     must be -1.

TYPE: (N, ) array

sources 
     Source node IDs. If ``None`` all nodes are used as sources.

TYPE: iterable DEFAULT: None

targets 
     Target node IDs. If ``None`` all nodes are used as targets.

TYPE: iterable DEFAULT: None

directed 
     If ``True`` only consider targets in the direction of the
     child -> parent (i.e. towards the root) relationship. Note that
     with non-negative weights the farthest such target is the target
     ancestor closest to the root.

TYPE: bool DEFAULT: False

weights 
     Array of distances for each child -> parent connection.
     If ``None`` all node to node distances are set to 1.

TYPE: (N, ) float32 array DEFAULT: None

RETURNS DESCRIPTION
distances

Distance from each source to its farthest target. Sources without a reachable target are set to -1. Ordered to match sources (or node_ids if sources is None).

TYPE: float32 (single) array

farthest

Node ID of the farthest target for each source, in the same order as distances. Sources without a reachable target are set to -1.

TYPE: array

Examples:

>>> import navis_fastcore as fastcore
>>> import numpy as np
>>> node_ids = np.arange(7)
>>> parent_ids = np.array([-1, 0, 1, 2, 1, 4, 5])
>>> dist, farthest = fastcore.geodesic_farthest(
...     node_ids, parent_ids,
...     sources=[0, 3], targets=[5, 6]
...     )
>>> dist
array([4., 5.], dtype=float32)
>>> farthest
array([6, 6])

Calculate the distance from each node to its root.

PARAMETER DESCRIPTION
node_ids 
     Array of node IDs.

TYPE: (N, ) array

parent_ids 
     Array of parent IDs for each node. Root nodes' parents
     must be -1.

TYPE: (N, ) array

sources 
     Node IDs to measure from. If ``None`` all nodes are used.

TYPE: iterable DEFAULT: None

weights 
     Array of distances for each child -> parent connection.
     If ``None`` all node to node distances are set to 1.

TYPE: (N, ) float32 array DEFAULT: None

RETURNS DESCRIPTION
distances

Distance to the root for each node. Roots are at distance 0 from themselves. Ordered to match sources (or node_ids if sources is None).

TYPE: float32 (single) array

Examples:

>>> import navis_fastcore as fastcore
>>> import numpy as np
>>> node_ids = np.arange(7)
>>> parent_ids = np.array([-1, 0, 1, 2, 1, 4, 5])
>>> fastcore.dist_to_root(node_ids, parent_ids)
array([0., 1., 2., 3., 2., 3., 4.], dtype=float32)