Hello,
For experimental purpose I benchmarked the *topology.shortest_distance* run
time. I stumbled upon something I fail to explain. In this benchmark I
compare two graphs :
(*) The first graph is undirected and has about 11M edges and 8M
vertices;
(*) The second graph is a copy of the first one with directed edges. In
this graph, for each edge from the first graph the backward edge is added.
Hence, the second graph has about 22M edge and 8M vertices.
I use https://gist.github.com/Fkawala/f7a3366a0d702163d7499ce29efec78e
<https://gist.github.com/Fkawala/f7a3366a0d702163d7499ce29efec78e> to
measure the run time of a shortest path to all vertices within a given
distance.
With the first graph the run time is :
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.035 0.035 0.060 0.060
graph_tool/topology/__init__.py:1272(shortest_distance)
1 0.000 0.000 0.019 0.019
graph_tool/decorators.pyc:1(copy_property)
2/1 0.000 0.000 0.019 0.019
graph_tool/decorators.py:126(wrapper)
1 0.013 0.013 0.019 0.019
graph_tool/__init__.py:2247(copy_property)
10 0.000 0.000 0.011 0.001
graph_tool/__init__.py:146(_prop)
8 0.000 0.000 0.011 0.001
graph_tool/__init__.py:476(_get_any)
8 0.011 0.001 0.011 0.001
graph_tool/__init__.py:893(reserve)
1 0.000 0.000 0.001 0.001
graph_tool/__init__.py:2559(set_edge_filter)
1 0.000 0.000 0.001 0.001
graph_tool/__init__.py:680(__set_array)
1 0.000 0.000 0.000 0.000
graph_tool/__init__.py:643(get_array)
4 0.000 0.000 0.000 0.000
graph_tool/__init__.py:667(_get_data)
[truncated]
With the second graph the run is :
ncalls tottime percall cumtime percall filename:lineno(function)
1 2.347 2.347 2.372 2.372
graph_tool/topology/__init__.py:1272(shortest_distance)
1 0.000 0.000 0.019 0.019
graph_tool/decorators.pyc:1(copy_property)
2/1 0.000 0.000 0.019 0.019
graph_tool/decorators.py:126(wrapper)
1 0.012 0.012 0.018 0.018
graph_tool/__init__.py:2247(copy_property)
9 0.000 0.000 0.011 0.001
graph_tool/__init__.py:146(_prop)
5 0.000 0.000 0.011 0.002
graph_tool/__init__.py:476(_get_any)
5 0.011 0.002 0.011 0.002
graph_tool/__init__.py:893(reserve)
1 0.001 0.001 0.001 0.001
graph_tool/__init__.py:975(_check_prop_scalar)
[truncated]
How could we explain this difference? I there a something to do to reduce
the run time observed with the second graph ?
Bests,
F.