We have modified the implementation of Dijkstra's algorithm contained in the csgraph module for compressed sparse graph routines to return a list of visited nodes. We use this package to help us construct a minimal spanning tree between single-cell transcriptomes. For more information about this, please refer to the MERLoT manuscript.
csgraph_mod can be installed using the pip package manager or any pip-compatible package manager:
git clone https://github.com/soedinglab/csgraph_mod.git
cd csgraph_mod/
pip install .
csgraph_mod was developed and tested in Python 3.5 and 3.6. While older Python 3 versions should work, there is no guarantee that they will. Installation requires:
In some cases (especially on Mac computers), the installer may complain that it cannot find some numpy headers:
fatal error: 'numpy/arrayobject.h' file not found
In this case, try exporting the headers yourself. Run export CFLAGS="-I <python_loc>/site-packages/numpy/core/include $CFLAGS", where <python_loc> is the directory where python is installed - something like /usr/local/lib/python3.6.