Operations on Tree Graphs

Neurons can be represented as centerline skeletons which themselves are rooted trees or "directed acyclic graphs" (DAG) where each node has at most a single parent (root nodes will have no parents).

Figure 1: Representing a neuron as directed acyclic graph.

Rooted trees have two huge advantages over general graphs:

First, they are super compact and can, at the minimum, be represented by just a single vector of parent indices (with root nodes having negative indices).

Figure 2: Rooted tree graphs are compact.

Second, they are much easier/faster to traverse because we can make certain assumptions that we can't for general graphs. For example, we know that there is only ever (at most) a single possible path between any pair of nodes.

Figure 3: Finding the distance between two nodes.

While networkx has some DAG-specific functions they don't implement anything related to graph traversal.

Available functions

The Python bindings for navis-fastcore currently cover the following functions:

fastcore.geodesic_matrix: calculate geodesic ("along-the-arbor") distances either between all pairs of nodes or between specific sources and targets
fastcore.geodesic_pairs: calculate geodesic ("along-the-arbor") distances between given pairs of nodes
fastcore.connected_components: generate the connected components
fastcore.synapse_flow_centrality: calculate synapse flow centrality (Schneider-Mizell, eLife, 2016)
fastcore.generate_segments: break the neuron into linear segments
fastcore.segment_coords: generate coordinates per lineaer segment (useful for plotting)