-
Notifications
You must be signed in to change notification settings - Fork 185
Performance of diameter #1516
Comments
This is not a bug but performance issue, but a |
I think this might be, because |
In general using |
I am not sure if Floyd-Warshall is much more performant unless one finds a way to avoid allocating the temporary There might also be the possiblity for a parallel |
All-source bfs should be faster than FW for unweighted graphs. For weighted I think dijkstra will still beat FW but tests should confirm. And we should definitely specialize distance metrics for unweighted. |
igraph does BFS. F-W allocates but if graph is dense this should not be a problem as then |V| cannot be large anyway. |
Would something like https://who.rocq.inria.fr/Laurent.Viennot/road/papers/ifub.pdf be overkill for our purposes? Also, when you talk about distance metrics to specialize, what do you have in mind besides the diameter? |
Sorry for the delayed response. In general, if you have unweighted graphs, where we're currently using Dijkstra, we can simply substitute BFS. There's no need to track weights in an unweighted graph, and BFS is more performant specifically because we don't need to do these comparisons at each traversal. |
I have a
gh
graph on 37700 vertices and 289003 edges.Calculation of its diameter like this:
takes around 250 seconds (probably this is not an optimal algorithm for the task but at least it works).
However, when I run
diameter(gh)
the process takes so long that I did not wait till it finished.The text was updated successfully, but these errors were encountered: