Skip to content

Scipy CSGraph Wrappers

If you are working with graphs (representing neurons or similar objects) you might already be using routines implemented in scipy.csgraph - for example, to compute distances or extract connected components.

Assuming your graphs are rooted trees, you can use fastcore as drop-in replacement for some of these scipy functions:

>>> from scipy.sparse import csr_array
>>> from navis_fastcore.wrappers.csgraph import dijkstra
>>> graph = [
... [0, 1, 0, 0],
... [0, 0, 0, 1],
... [0, 0, 0, 3],
... [0, 0, 0, 0]
... ]
>>> graph = csr_array(graph)
>>> dist_matrix = dijkstra(csgraph=graph, directed=False)
>>> dist_matrix
array([[0., 1., 5., 2.],
       [1., 0., 4., 1.],
       [5., 4., 0., 3.],
       [2., 1., 3., 0.]], dtype=float32)

fastcore currently implements the following scipy.csgraph functions:

  • dijkstra
  • connected_components

Notes

  1. Not all arguments are supported. For example, dijkstra currently does not support return_predecessors=True. See the docstrings for details!
  2. By default, these functions will perform a check to make sure the input graph is actually a rooted tree. These are generally fairly fast but if you are confident in your graphs and want to save the odd millisecond, you can set checks=False.

API

Wrapper for geodesic_matrix_graph() mimicking scipy.sparse.csgraph.dijkstra().

Unlike scipy's, this runs one Dijkstra per source in parallel — scipy's holds the GIL, so you cannot get that from Python by threading it yourself.

Notes: 1. min_only=True is not supported 2. return_predecessors=True is currently not supported (might change in the future) 3. checks is accepted for signature compatibility but is now a no-op: this used to route through the tree-only geodesic_matrix and so had to reject cyclic graphs. It no longer does, so any graph is fine. 4. targets and threads are extensions beyond scipy's API. targets is the important one: scipy has no notion of targets, so it always materialises all N columns and makes you slice afterwards. Passing targets here means only those columns are ever allocated, which is what makes a large graph tractable.

Wrapper for connected_components() that mimics the interfaces of scipy.sparse.csgraph.connected_components().

Notes: 1. connection='strong' makes no sense for trees, so it is not supported.