Consider two graphs: G=(V,E) and H=(V',E') such that:

V' $\subset$ V and E' $\subset$ E
|E| = 66M
|E'|=2M.

Run:

X = shortest_distance(G, G.vertex(0), max_dist=x, weights=G.ep['weights'])
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] <[hidden email]>:

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

signature.asc (836 bytes) Download Attachment

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

If you reply to this email, your message will be added to the discussion below:
http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/Shortest-distance-complexity-when-used-with-max-dist-tp4026018p4026025.html

To start a new topic under Main discussion list for the graph-tool project, email [hidden email]
To unsubscribe from Shortest_distance complexity when used with max_dist, click here.
NAML

François Kawala