DAG traversal

[schlegelp]

Skeletons being directed acyclic graphs (DAGs) opens up some neat options for graph traversal that would not work on general graphs. We can leverage that to speed up certain operations. Off the top of my head:

• shortest paths calculations (see 0b15588)
• geodesic distances
• connected components (?)
• finding the N longest paths

[schlegelp]

• cable length
• classifying nodes into leafs, slabs and branch points

[ceesem]

Fast DAG-assuming implementations that are drop in replacements for spicy.sparse.csgraph functions (dijkstra, connected components) would be particularly awesome...

[schlegelp]

I have since restarted re-implementing the fastcore functions in Rust (nice build system + the potential for R bindings): https://github.com/schlegelp/fastcore-rs

That library is more mature and importantly already on PyPI with pre-compiled binaries:

pip install navis-fastcore

As mentioned on Slack: it's called navis-fastcore but the only dependency is numpy.

The functions you were looking for already exist:

• navis_fastcore.geodesic_matrix
• navis_fastcore.connected_components

Both functions are ~ on par with the csgraph pendants in terms of functionality but not exactly drop-in replacements. Nothing a small wrapper can't fix though - happy to discuss adding a navis_fastcore.csgraph module that exactly mimics the csgraph interface.

Let me know how this works for you! I'm also still looking for other operation that may benefit from this approach - just in case you have more suggestions.

[schlegelp]

I just quickly cobbled something together: https://github.com/schlegelp/fastcore-rs/blob/main/navis_fastcore/wrappers/csgraph.py

So far this lives only on Github but with it you could do this:

try:
   from navis_fastcore.wrappers.csgraph import dijkstra
except ImportError:
   from scipy.sparse.csgraph import dijkstra

Have a look at the functions and let me know what you think.