Consider two graphs: G=(V,E) and H=(V',E') such that: 
  1. V' \subset V and E' \subset 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] <[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


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.