On my test graph with 4201 nodes and 9683 edges I already tried a quick test with both:


I need ~ 70 random (source, target) node pairs to approximate the real mean of all pairs shortest path with an error of about 1 %.

This is about 40 % of the run-time of all pairs shortest path.


Using single source all targets shortest path I need to sample at least 6 random sources to approximate the real mean of all pairs shortest path with an error of about 1 %.

This is about 45-50 % of the run-time of all pairs shortest path.


So, although single source all targets shortest path is waay more efficient in it's computation than shortest_path manually it apparently is not a good candidate for subsampling and effectively doing worse.



Von: Tiago de Paula Peixoto <tiago@skewed.de>
Gesendet: Dienstag, 26. Oktober 2021 16:52
An: graph-tool@skewed.de
Betreff: [graph-tool] Re: Speed up graph_tool.topology.shortest_distance
 
Am 26.10.21 um 16:23 schrieb Tiago de Paula Peixoto:
> It is possible to pass a single source but multiple targets.

It is possible to pass also a single source and no target, in which case
the function computes the distances to all other vertices.

By sub-sampling the source vertices you can avoid the "overhead" you
were referring to.

--
Tiago de Paula Peixoto <tiago@skewed.de>
_______________________________________________
graph-tool mailing list -- graph-tool@skewed.de
To unsubscribe send an email to graph-tool-leave@skewed.de