Consider two graphs: G=(V,E) and H=(V',E') such that:
1. V' [image: \subset] V and E' [image: \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] <[email protected]>:
> 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]
> <http:///user/SendEmail.jtp?type=node&node=4026025&i=0>>
>
>
> _______________________________________________
> graph-tool mailing list
> [hidden email] <http:///user/SendEmail.jtp?type=node&node=4026025&i=1>
> http://lists.skewed.de/mailman/listinfo/graph-tool
>
> *signature.asc* (836 bytes) Download Attachment
> <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/attachment/4026025/0/signature.asc>
> --
> Tiago de Paula Peixoto <[email protected]>
>
>
> ------------------------------
> 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 [email protected]
> To unsubscribe from Shortest_distance complexity when used with max_dist,
> click
> here
> <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/template/NamlServlet.jtp?macro=unsubscribe_by_code&node=4026018&code=ZnJhbmNvaXMua2F3YWxhQGdtYWlsLmNvbXw0MDI2MDE4fDIxMTQ0MDk4Nzk=>
> .
> NAML
> <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/template/NamlServlet.jtp?macro=macro_viewer&id=instant_html%21nabble%3Aemail.naml&base=nabble.naml.namespaces.BasicNamespace-nabble.view.web.template.NabbleNamespace-nabble.view.web.template.NodeNamespace&breadcrumbs=notify_subscribers%21nabble%3Aemail.naml-instant_emails%21nabble%3Aemail.naml-send_instant_email%21nabble%3Aemail.naml>
>
--
François Kawala
--
View this message in context:
http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/Shortest-distance-complexity-when-used-with-max-dist-tp4026018p4026026.html
Sent from the Main discussion list for the graph-tool project mailing list
archive at Nabble.com.
_______________________________________________
graph-tool mailing list
[email protected]
http://lists.skewed.de/mailman/listinfo/graph-tool
