Am 27.10.21 um 13:20 schrieb Monecke, Stephan:
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.
I would not try to generalize much from this, since it is likely to
depend substantially on the underlying graph.
Best,
Tiago
--
Tiago de Paula Peixoto <ti...@skewed.de>
_______________________________________________
graph-tool mailing list -- graph-tool@skewed.de
To unsubscribe send an email to graph-tool-le...@skewed.de