Consider two graphs: G=(V,E) and H=(V',E') such that:
1. V'  V and E'  E
2. |E| = 66M
3. |E'|=2M.
Run:
1. X = shortest_distance(G, G.vertex(0), max_dist=x, weights=G.ep['weights'])
2. Y = shortest_distance(H, H.vertex(0), max_dist=x, weights=H.ep['weights'])
I verify that : X = Y

The execution took 320ms for (1) and 16ms for (2). However the number of visited vertices should be identical ? I expected to obtain comparable execution times.

Best,
François

2015-03-07 17:45 GMT+01:00 Tiago Peixoto [via Main discussion list for the graph-tool project] :
On 06.03.2015 19:15, François wrote:
>> With only two points it is not possible to distinguish between O(V),
>> O(V log V), O(V ^ 2) or anything else.
>
> Of course I wouldn't generalize from this example. But I can't explain
> myself why the execution time differs so much between the sub-sample and the
> full graph. I choose the same source-vertex. The graph around this source is
> the same in the sub-sample and the full graph.

I'm not sure I understand exactly what the problem is. Could you explain
in detail exactly what you are doing, and why you the think the
performance is unexpected?

Best,
Tiago

--
Tiago de Paula Peixoto <[hidden email]>

_______________________________________________
graph-tool mailing list
[hidden email]
http://lists.skewed.de/mailman/listinfo/graph-tool

--
Tiago de Paula Peixoto <[hidden email]>