[graph-tool] Performance question

Tiago de Paula Peixoto tiago at skewed.de
Fri Mar 21 11:00:52 CET 2014


On 03/21/2014 10:10 AM, Guillaume Gay wrote:
> Hi,
>
> There is a propertymap that contains the out degrees of each vertex, it might be much faster to access it, i.e.:
>
> `i_degree = graph.degree_property_map('out')[i]`

This is not a good idea, since "g.degree_property_map('out')" will
create an entire property map anew (which is O(N)) each time you want a
single degree (which should be O(1)). It is best to compute the property
map before the loop, and just look it up when you need it.

    d = graph.degree_property_map('out') # this is O(N)
    ...

    k = d[v]  # this is O(1)

Best,
Tiago

-- 
Tiago de Paula Peixoto <tiago at skewed.de>

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 901 bytes
Desc: OpenPGP digital signature
URL: <https://lists.skewed.de/pipermail/graph-tool/attachments/20140321/4f522e47/attachment.asc>


More information about the graph-tool mailing list