Skip to content

Topology

Functions that walk or rewire the tree itself, rather than measuring distances along it.

These exist because the operations look like general graph algorithms but are not: on a rooted forest, "everything below this node", "re-root here" or "collapse these nodes" are all linear passes over the parent vector. Building a graph object to answer them costs more than the answer does.

Traversal

descendants and paths_to_root are the two directions of the same walk: everything below a node, and everything above it.

import navis_fastcore as fastcore
import numpy as np

node_ids = np.array([0, 1, 2, 3, 4])
parent_ids = np.array([-1, 0, 1, 2, 1])

# Cutting the skeleton at node 2 = splitting it into this and everything else
distal = fastcore.descendants(node_ids, parent_ids, [2])[0]

Find the nodes distal to each source, i.e. its sub-tree.

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 collect the sub-tree of.

TYPE: iterable

RETURNS DESCRIPTION
subtrees

One array of node IDs per source, in sources order. Each starts with the source itself and is in depth-first pre-order, so a node always precedes its own descendants.

TYPE: list of arrays

Examples:

>>> import navis_fastcore as fastcore
>>> import numpy as np
>>> node_ids = np.arange(6)
>>> parent_ids = np.array([-1, 0, 1, 2, 1, 2])
>>> fastcore.descendants(node_ids, parent_ids, [2])
[array([2, 3, 5])]

A leaf is its own only descendant:

>>> fastcore.descendants(node_ids, parent_ids, [3, 4])
[array([3]), array([4])]
See Also

navis_fastcore.paths_to_root The same walk in the opposite direction.

Walk from each source up 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 walk up from.

TYPE: iterable

RETURNS DESCRIPTION
paths

One array of node IDs per source, in sources order, ordered source-first / root-last. A source that is itself a root gives a single-element path.

TYPE: list of arrays

Examples:

>>> import navis_fastcore as fastcore
>>> import numpy as np
>>> node_ids = np.arange(6)
>>> parent_ids = np.array([-1, 0, 1, 2, 1, 2])
>>> fastcore.paths_to_root(node_ids, parent_ids, [3, 4])
[array([3, 2, 1, 0]), array([4, 1, 0])]

A root is a path of one:

>>> fastcore.paths_to_root(node_ids, parent_ids, [0])
[array([0])]

Editing

reroot reverses the edges between a new root and the old one and leaves the rest of the tree alone. contract_nodes merges groups of nodes onto a representative. simplify_skeleton throws away the slab nodes that carry no topological information, keeping total cable length intact and reporting a node_map so anything you keep per node can follow — see Downsampling, whose three thinning methods share its output contract.

Note

contract_nodes does not re-root; chain it with reroot if you need the result rooted somewhere specific.

Re-root the skeleton at the given node(s).

Every edge on the path from a new root to its component's old root is reversed; the rest of the tree is untouched.

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

new_roots 
     Node IDs to root their components at. Components containing none
     of these are left exactly as they were - this re-roots, it does
     not renumber the rest of the forest. Where two new roots fall in
     the same component, the first one wins.

TYPE: iterable

RETURNS DESCRIPTION
parent_ids

New parent IDs, aligned with node_ids. Roots are -1.

TYPE: (N, ) array

Examples:

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

Re-rooting at the existing root is a no-op:

>>> fastcore.reroot(node_ids, parent_ids, [0])
array([-1,  0,  1,  2,  1])

Collapse groups of nodes onto a representative and rewire.

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

mapping 
     For each node, the ID of the node it collapses into. A node
     mapped to itself survives; nodes sharing a representative are
     merged into it. Edges that end up inside a group are dropped.

TYPE: (N, ) array

RETURNS DESCRIPTION
node_ids

The surviving node IDs, in their original relative order.

TYPE: (M, ) array

parent_ids

Their new parent IDs. Roots are -1.

TYPE: (M, ) array

RAISES DESCRIPTION
ValueError

If the contraction would produce a cycle - which happens when a node is mapped onto one of its own descendants.

Examples:

Collapse nodes 1 and 2 onto node 1:

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

Note this does not re-root; follow with navis_fastcore.reroot if you need the result rooted somewhere specific.

Reduce a skeleton to its roots, leafs and branch points.

The slab nodes in between carry no topological information. Dropping them leaves the same tree at a fraction of the size, with each replacement edge carrying the total length of the chain it stands in for - so total cable length is preserved.

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

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
node_ids

The surviving node IDs, in their original relative order.

TYPE: (M, ) array

parent_ids

Their new parent IDs. Roots are -1.

TYPE: (M, ) array

weights

Length of each node's edge to its new parent, i.e. the summed length of the chain it replaces. Roots are 0. None exactly when weights was None.

TYPE: (M, ) float32 array or None

node_map

For each input node, the ID of the surviving node its data belongs to now - indexed like node_ids, valued in the returned node_ids. Surviving nodes map to themselves; a dropped node maps to whichever end of its chain is nearer, measured in weights (in hops if weights is None), with ties going towards the root. Use it to re-attach anything you keep per node, such as synapses.

TYPE: (N, ) array

Examples:

>>> import navis_fastcore as fastcore
>>> import numpy as np
>>> node_ids = np.arange(5)
>>> parent_ids = np.array([-1, 0, 1, 2, 2])
>>> weights = np.array([0, 1, 2, 4, 8], dtype=np.float32)
>>> ids, parents, w, node_map = fastcore.simplify_skeleton(
...     node_ids, parent_ids, weights=weights
... )

Node 1 was the only slab, so it is gone and nodes 3 and 4 now hang off node 2 directly. Node 2's new edge carries both the 2 -> 1 and 1 -> 0 lengths:

>>> ids
array([0, 2, 3, 4])
>>> parents
array([-1,  0,  2,  2])
>>> w
array([0., 3., 4., 8.], dtype=float32)

Node 1 sat 1 unit from node 0 and 2 units from node 2, so anything attached to it now belongs to node 0:

>>> node_map
array([0, 0, 2, 3, 4])

Adjacency

adjacency hands back the three arrays of a CSR matrix, so a skeleton can be fed to scipy.sparse (or anything else) without going through an edge list.

from scipy.sparse import csr_matrix

n = len(node_ids)
indptr, indices, data = fastcore.adjacency(node_ids, parent_ids)
# N.B. scipy takes the three arrays in the opposite order
A = csr_matrix((data, indices, indptr), shape=(n, n))

Build the skeleton's adjacency matrix in CSR form.

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

weights 
     Array of distances for each child -> parent connection.
     If ``None`` all edges weigh 1.

TYPE: (N, ) float32 array DEFAULT: None

directed 
     If ``True`` only the child -> parent edge is emitted. If
     ``False`` both directions are.

TYPE: bool DEFAULT: True

transpose 
     If ``True`` flip every edge, so rows are parents and columns
     children.

TYPE: bool DEFAULT: False

RETURNS DESCRIPTION
indptr

TYPE: (N + 1, ) int32 array

indices

TYPE: (nnz, ) int32 array

data

The three arrays of a scipy.sparse.csr_matrix. Rows and columns follow node_ids order, i.e. index i is node_ids[i]. Column indices are ascending within each row.

TYPE: (nnz, ) float32 array

Notes

Returning the raw triple rather than a matrix keeps this package free of a scipy dependency. To build the matrix - note scipy takes the three arrays in the opposite order to the conventional CSR description used here::

from scipy.sparse import csr_matrix
n = len(node_ids)
indptr, indices, data = fastcore.adjacency(node_ids, parent_ids)
A = csr_matrix((data, indices, indptr), shape=(n, n))

Examples:

>>> import navis_fastcore as fastcore
>>> import numpy as np
>>> node_ids = np.arange(3)
>>> parent_ids = np.array([-1, 0, 1])
>>> indptr, indices, data = fastcore.adjacency(node_ids, parent_ids)

Row i holds node i's edge to its parent, so the root's row is empty:

>>> indptr
array([0, 0, 1, 2], dtype=int32)
>>> indices
array([0, 1], dtype=int32)

Longest paths

longest_path finds the longest path from a node to its root; longest_paths repeats that, removing each path before looking for the next, which is how a neuron gets split into its n longest neurites.

This is not the (NP-hard) general longest-path problem. In a rooted forest every maximal path is fixed by its start node — just follow the parents up — so the longest one starts at whichever node is farthest from its own root.

min_length measures the catchment, not the path

Every edge whose parent lies on the path counts towards min_length, so each twig hanging off the path contributes its first edge too. The comparison is <= and hitting it stops the search rather than skipping one path. This is inherited from navis so that results do not shift.

Find the longest path in the skeleton.

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

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
path

Node IDs along the path, distal first - so path[0] is the far end and path[-1] is a root. Ties are broken towards the node that comes first in node_ids.

TYPE: (L, ) array

Notes

This is not the (NP-hard) general longest-path problem. In a rooted forest every maximal path is fixed by its start node - just follow the parents up - so the longest one starts at whichever node is farthest from its own root.

Examples:

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

Weights change which path is longest - here one heavy hop beats two light ones:

>>> weights = np.array([0, 1, 1, 1, 50], dtype=np.float32)
>>> fastcore.longest_path(node_ids, parent_ids, weights=weights)
array([4, 1, 0])
See Also

navis_fastcore.longest_paths The n longest paths, each peeled off before the next.

Find the n longest paths, peeling each one off before the next.

Each path is removed from the skeleton before the next is sought, so the second path is the longest of what remains rather than the second-longest of the original - and the paths are pairwise disjoint. Removing a path turns the children hanging off it into roots of their own.

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

n 
     How many paths to take. Fewer are returned if the skeleton runs
     out, or if `min_length` stops the search.

TYPE: int

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

min_length 
     Stop as soon as a path measures no more than this.

TYPE: float DEFAULT: None

RETURNS DESCRIPTION
paths

Up to n arrays of node IDs, longest first, each distal-first.

TYPE: list of arrays

Warnings

min_length measures the path's whole catchment, not just its own edges: every edge whose parent lies on the path counts, so each twig hanging off the path contributes its first edge too. The comparison is <=, and hitting it stops the search rather than skipping that one path.

That is inherited from navis' split_into_fragments, where it is flagged as "preserved as-is from the networkx implementation", and it is kept here deliberately so that results do not shift.

Examples:

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

Note the second path stops at node 4: node 1 went with the first path, so 4 is the root of what was left.

Validity

Everything on this page assumes the parent vector describes a rooted forest: follow parents from any node and you arrive at a root. has_cycles is that assumption, checked in a linear pass — worth doing once on data of unknown provenance, since a cycle is malformed input rather than an unusual shape. The functions here are written so that a cycle cannot hang them, but on one they return a truncated walk, not an answer.

if fastcore.has_cycles(node_ids, parent_ids):
    raise ValueError("not a skeleton")

Check whether the parent structure contains a cycle.

A well-formed skeleton is a rooted forest: walking parents from any node has to arrive at a root. Every other function in this module assumes that without checking it; this is the check, in a single linear pass.

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

RETURNS DESCRIPTION
bool

Whether any node is its own ancestor.
Notes

A parent ID that does not appear in node_ids is treated as -1, i.e. as a root - the same convention as everywhere else here - so a dangling parent is not a cycle.

Cyclic input is malformed, not merely unusual. The other functions are written so that it cannot hang them, but what they hand back is a truncated walk rather than an answer. Use this if you need to know rather than survive.

Examples:

>>> import navis_fastcore as fastcore
>>> import numpy as np
>>> node_ids = np.array([1, 2, 3, 4])
>>> fastcore.has_cycles(node_ids, np.array([-1, 1, 2, 3]))
False

Every node an ancestor of itself, with no root anywhere:

>>> fastcore.has_cycles(node_ids, np.array([4, 1, 2, 3]))
True