You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Instead of calculating paths between all pairs of input vertices, each iteration could store all IDs of vertex pairs along all previously-traced paths. A new Dijkstra would then need only be run if the start and end vertices did not appear in this list. This would effectively be equivalent to implementing the Floyd-Warshall algorithm.
Extra efficiency could likely be gained by first calculating straight-line distances between all vertices (where possible, which may not always be the case), and running Dijkstra's on the vertex pairs as sorted in order of decreasing distance. Because distances would be calculated from each from vertex to all other vertices, these distances could be calculated as maximal pair-wise distances from each from vertex to all nominated to vertices.
The ultimate aim here would be to speed up flow aggregation, which is currently pretty slow compared, for example, to igraph::betweenness().
The text was updated successfully, but these errors were encountered:
Actually, a better way to speed up flow aggregation will be to have no edge properties at all, and just calculate paths, then re-trace them and add the flows along each segment. The actual dijkstra stage would then be <int>-based, with uniform values of 1, and so would be much quicker. This should be done. Nah, that's not right at all; paths still have to be traced with weighted distances, so this can't really be done efficiently after all (not in any general way at least).
Instead of calculating paths between all pairs of input vertices, each iteration could store all IDs of vertex pairs along all previously-traced paths. A new Dijkstra would then need only be run if the start and end vertices did not appear in this list. This would effectively be equivalent to implementing the Floyd-Warshall algorithm.
Extra efficiency could likely be gained by first calculating straight-line distances between all vertices (where possible, which may not always be the case), and running Dijkstra's on the vertex pairs as sorted in order of decreasing distance. Because distances would be calculated from each
from
vertex to all other vertices, these distances could be calculated as maximal pair-wise distances from eachfrom
vertex to all nominatedto
vertices.The ultimate aim here would be to speed up flow aggregation, which is currently pretty slow compared, for example, to
igraph::betweenness()
.The text was updated successfully, but these errors were encountered: