search

seung-lab / dijkstra3d

Dijkstra's Shortest Path for 6, 18, and 26-Connected 3D (Volumetric) Image Volumes
GNU General Public License v3.0
71 stars 13 forks source link

Allow multiple sources in distance_field #27

Closed tvercaut closed 3 years ago

tvercaut commented 3 years ago

In some scenarios, it might be interesting to get a distance field for multiple source.

The networkx library for example provides such a functionality for general graphs: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.multi_source_dijkstra_path_length.html

I am not sure how this could best be implemented in dijkstra3d but I believe a classical "trick" is choose (for example) the first source as "the source" and use a single-source implementation but make sure that all other "secondary sources" are connected to the first source with a zero-weight edge.

william-silversmith commented 3 years ago

For dijkstra3d, it would be simple to just insert the multiple sources into the priority queue at the start and proceed normally. The zero edge weight trick won't work in dijkstra3d unless the sources are all adjacent to each other due to the implicit graph structure.

william-silversmith commented 3 years ago

@tvercaut I have a prototype of this functionality ready. If you have a use case for it, give it a shot and let me know how it goes.

william-silversmith commented 3 years ago

Multi-source is now enabled in 1.10.0 give it a shot!

tvercaut commented 3 years ago

Brilliant, thanks! I have updated my quick notebook to reflect it: https://colab.research.google.com/drive/196EPtBO0BmIjYmi6RlBvLlD_JGyAE9zB?usp=sharing

I get qualitatively similar results than with networkx for either single or muli-source distance maps but get numerical differences. I guess this is just related to an inconsistent definition of the graph structure between my networkx manual definition and the implicit one from dijkstra3d as I have not cleanly defined the forward and backward edges. I was indeed initially looking for an undirected graph with an edge weight as per #26

william-silversmith commented 3 years ago

I was trying to play around with your python notebook but for some reason was running into problems with installing dijkstra3d. Are you running into the same problem? I tried releasing a new version that is compiled against oldest-supported-numpy to deal with the binary compatibility issue but it seems not to be working on the notebook. :(