search

ysig / GraKeL

A scikit-learn compatible library for graph kernels
https://ysig.github.io/GraKeL/
Other
594 stars 97 forks source link

Possible improvement for initialisation of Floyd-Warshall? #27

Closed Alessi0X closed 4 years ago

Alessi0X commented 4 years ago

Dear Grakel developers, today I was playing with the Shortest Path kernel (Floyd-Warshall algorithm for building the shortest path matrix) and I was curious to look at the source code.

Your floyd_warshall() algorithm has been nicely divided into an Initialization step and a Calculation step. The initialization step seems a bit inefficient to me (a double for-loop with three if/else branches). May I propose the following vectorized alternative?

dist = copy.deepcopy(adjacency_matrix)
dist[dist==0] = float("Inf")
np.fill_diagonal(dist, 0)

where, obviously np stands for numpy and copy is included in the standard Python library.

I have been trying this new implementation on the DD dataset (a quite challenging one) by taking the wall-clock time between the original initialization step and the vectorized one (the calculation block has obviously been omitted) and on a Linux 19.04 machine with Intel i7-3770K I obtained 183.60 seconds (original) against 1.03 seconds (vectorized).

Hope you find this little investigation useful. All the best

ysig commented 4 years ago

Hi!

Thanks a lot for this really interesting feedback. Unfortunately this code was built in the beginning of the library and was not investigated till then. As so your feedback is really useful. We can totally pass it ourselves, but we think it would be better if you made a pull request on the 0.1a7 branch, so that your contribution is registered?

Thanks

PS: Reference this issue on the pull-request.

Alessi0X commented 4 years ago

Done! Sorry for opening PR #28 on your repo. Feel free to destroy it. PR #29 should be fine though