search

timlrx / graph-benchmarks

MIT License
79 stars 5 forks source link

NetworKit shortest path benchmark #2

Open angriman opened 4 years ago

angriman commented 4 years ago

Hi, I've noticed that the NetworKit shortest-path benchmark is executed with

distance.BFS(g, node_index).run()

However, with this API NetworKit will also store all shortest paths from node_index to all the other nodes, which implies a significant memory and time overhead. This behavior is a bit counterintuitive, and should be better documented, one does not expect BFS to store by default all shortest paths. Since the other tools only compute the shortest distances, for a fair comparison you should run this:

distance.BFS(g, node_index, storePaths=False).run()
timlrx commented 4 years ago

Hi, thanks for pointing this out and apologies that I did not get back earlier. Will use your suggested version in the upcoming re-run.