Re: [igraph] Speed up calculation of pairwise shortest distances

[Tamas Nepusz]

Hi,

> My implementation:
> for each of the 100 million pairs:
>       call get_shortest_paths()
>       take the min between 120 and the length of the list of edges in the
> shortest path
Why not like this:

for each of the vertices that occur as sources in the pairs:
    call shortest_paths([vertex], [all the vertices that occur as
targets for the source vertex])
    then take the min

shortest_paths() will return the lengths of the paths only, not the
actual paths. (I know, this function has quite a misleading name).
Also, running the calculation grouped by source vertices lets igraph
perform less work if one of the paths found (or some part of it) turns
out to be a prefix for some other path originating from the same
source but ending at a different target.

> I'm clearly wasting efforts because:
> - get_shortest_paths() returns the actual path between the two nodes, but
> I'm only interested in the distance (I need something like
> "get_shortest_distance")
Most of the computational effort is spent on finding that path, saving
it usually does not represent a large overhead (compared to what it
took to find that path in such a large graph).

> - get_shortest_paths() processes until it reaches destination node, but
> since we have an upper bound, I'd suffice to use a "cutoff" value for the
> distance calculation
Unfortunately this is not implemented in igraph yet for shortest path
calculations.

T.