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

- V' V and E' 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

--

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.htmlTo 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

View this message in context: Re: Shortest_distance complexity when used with max_dist

Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.