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 <[email protected]>
signature.asc
Description: OpenPGP digital signature
_______________________________________________ graph-tool mailing list [email protected] http://lists.skewed.de/mailman/listinfo/graph-tool
