search

clbarnes / arbor

A python implementation of (some of) Arbor.js and related tools
MIT License
1 stars 1 forks source link

distance_map is extremely slow #1

Open clbarnes opened 5 years ago

clbarnes commented 5 years ago

Using networkx's shortest_path_length is extremely slow for this data; the "classic" algorithm should be much faster (but the current implementation is incorrect).

I believe that the problem with the python implementation of the classic distance_map algorithm is the sorting of the partitions. The JS docs say that they should be sorted in order of length, but I think they should actually be ordered topologically. partitions_sorted should return the root-containing partition last.

clbarnes commented 5 years ago

the "classic" algorithm should be much faster

It's not.

unidesigner commented 5 years ago

I have not looked into the algo itself, so I can't tell. Maybe this is useful regarding faster implementations https://stackoverflow.com/questions/938338/what-is-the-fastest-dijkstra-implementation-you-know-in-c Maybe @ceesem can also comment.

clbarnes commented 5 years ago

Just a thought - this might be at least in part because the reference implementation constrains the maximum length of a path, where I'm not currently doing that in the ArborNX implementation.