[graph-tool] Performance question

Hang Mang gucko.gucko at googlemail.com
Fri Mar 21 10:30:29 CET 2014


Indeed out_degree() is very very slow. I just replaced it with a constant 
and it finished the computation in 0.5 seconds compared to the 2.7 
minutes!!! But I guess what you mentioned is also slow since 'graph.
degree_property_map('out')[i]' since assumes 'i' is a vertex object and not 
the index of the vertex. In that case I need to call graph.vertex(index) 
and get the vertex and then call degree_property_map('out')[vertex]. I 
guess this is still very slow!

On Friday, March 21, 2014 10:10:37 AM UTC+1, 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]`
>
> I guess I would also iterate over the edges rather than the indices of the 
> adjacency matrix...
>
>
> G.
>
> Le 21/03/2014 09:44, Hang Mang a écrit :
>  
> Maybe graph.vertex(i).out_degree() is slow itself? If so, should I store 
> all the degrees in a matrix then?
>
> On Friday, March 21, 2014 9:09:23 AM UTC+1, Hang Mang wrote: 
>>
>> I have a graph with 1034 vertices and 53498 edges. I'm manually computing 
>> the preferential attachement index for the vertices, and other indices. I'm 
>> aware that graph-tool has that implemented but I'm doing it for personal 
>> stuff. However I noticed that my computations are very slow. It took 2.7 
>> minutes to compute that for the mentioned graph. I'm not sure if it's my 
>> algorithm that is slow or the something is wrong with graph-tool. I would 
>> be very thankful if someone could have a little look into my code. 
>>
>>  def pa(graph):
>>
>>     """
>>
>>         Calculates Preferential Attachment index.
>>
>>         Returns S the similarity matrix.
>>  
>>     """
>>
>>     A = gts.adjacency(graph)
>>
>>     S = np.zeros(A.shape)
>>
>>     for i in xrange(S.shape[0]):
>>
>>         for j in xrange(S.shape[0]):
>>
>>             i_degree = graph.vertex(i).out_degree()
>>
>>             j_degree = graph.vertex(j).out_degree()
>>
>>             factor = i_degree * j_degree
>>
>>             S[i,j] = factor
>>
>>     return S
>>  
>  
>  
> _______________________________________________
> graph-tool mailing listgraph... at skewed.de <javascript:>http://lists.skewed.de/mailman/listinfo/graph-tool
>
>  
> 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.skewed.de/pipermail/graph-tool/attachments/20140321/45382328/attachment.htm>


More information about the graph-tool mailing list