Following Issue #27 and following PR #29 I found a way also to speedup significantly the "Calculation" stage for Floyd-Warshall (in PR #29 only the "Initialization" stage was involved).
Briefly, instead of running a triple-nested for-loop, only 2 for-loops are involved + a vectorised statement.
I have been comparing your floyd_warshall() function against the fully vectorised one (PR #29 and this PR) on a Linux 19.10 machine with an Intel(R) Core(TM) i7-3770K CPU @ 3.50GHz and these are my results.
Dataset AIDS (entire dataset):
previous version: 23.5 seconds
vectorised version: 4.9 seconds
Dataset COX2 (entire dataset):
previous version: 20.5 seconds
vectorised version: 4.6 seconds
Dataset MSRC_9 (entire dataset):
previous version: 116.1 seconds
vectorised version: 24.9 seconds
Dataset MUTAG (entire dataset):
previous version: 0.86 seconds
vectorised version: 0.37 seconds
Dataset DD (first 20 graphs only):
previous version: 45125.30 seconds
vectorised version: 286.09 seconds
Needless to say, the two routines return the very same shortest path matrix.
Hi ysig.
Following Issue #27 and following PR #29 I found a way also to speedup significantly the "Calculation" stage for Floyd-Warshall (in PR #29 only the "Initialization" stage was involved).
Briefly, instead of running a triple-nested for-loop, only 2 for-loops are involved + a vectorised statement.
I have been comparing your
floyd_warshall()
function against the fully vectorised one (PR #29 and this PR) on a Linux 19.10 machine with an Intel(R) Core(TM) i7-3770K CPU @ 3.50GHz and these are my results.Dataset AIDS (entire dataset):
previous version: 23.5 seconds
vectorised version: 4.9 seconds
Dataset COX2 (entire dataset):
previous version: 20.5 seconds
vectorised version: 4.6 seconds
Dataset MSRC_9 (entire dataset):
previous version: 116.1 seconds
vectorised version: 24.9 seconds
Dataset MUTAG (entire dataset):
previous version: 0.86 seconds
vectorised version: 0.37 seconds
Dataset DD (first 20 graphs only):
previous version: 45125.30 seconds
vectorised version: 286.09 seconds
Needless to say, the two routines return the very same shortest path matrix.