On 04/28/2014 09:21 PM, gogurt wrote:
import graph_tool.all as gt def extract_deg(G, start):
# Initialize lists deg = []
if start == 1: deg.append(1) norm.append(1) i = 2 else: i = start
while i < sum(1 for _ in G.vertices()):
Gcurr = gt.GraphView(G,vfilt=lambda v: int(v) <= i) Gprev = gt.GraphView(G,vfilt=lambda v: int(v) < i)
# For time i, get the degree (as of time i-1) of # the node which has the edge to the newly-added # node in time i
v = Gcurr.vertex(i) for j in v.all_neighbours(): w = Gprev.vertex(j) deg.append(w.in_degree() + w.out_degree()) i += 1
return deg
Your code is inefficient in many ways. In order to understand why, you have to ask yourself for all statements, how many operations are necessary for it to be completed. For instance, in your loop statement: while i < sum(1 for _ in G.vertices()): The sum simply counts the number of vertices, but takes O(N) time. You should simply use G.num_vertices() which is O(1). When you construct the filter, Gcurr = gt.GraphView(G,vfilt=lambda v: int(v) <= i) The function provided to vfilt is called for each vertex, which is again O(N). You can improve it by using array expressions: mask = G.vertex_index.copy("int") mask.a = mask.a <= i Gcurr = gt.GraphView(G,vfilt=mask) This is still O(N), but avoids that a python function gets called for each vertex. However, it is possible to remove the O(N) by not depending on the GraphView altogether. When you do the loop over the neighbours, you can simply ignore newer vertices as you go along: v = G.vertex(i) for w in v.out_neighbours(): if int(w) < i: continue k = len([u for u in w.out_neighbours() if int(u) < i]) deg.append(k) Which should do as you want, and is much faster. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>