On 01/11/2013 11:49 AM, Giuseppe Profiti wrote:

2013/1/11 Va Sa <mihtal@gmail.com <mailto:mihtal@gmail.com>>

Greetings,

Is it possible to somehow enter a list of vertices to be removed all at once?

My naive approach

for v in g.vertices(): if v.in_degree() == 0 and v.out_degree()==0: g.remove_vertex(v)

is taking a while to run on a 3M Vertices graph, i.e. ~9 trillion memory shifts..

If one could avoid the memory shifting after each removal, the complexity would go down to just O(g.num_vertices)

Sincerely, Val

Instead of iterating, you could use a filter on the vertices, by using a GraphView (and maybe building a graph from the view using the prune parameter) like that

gv = gt.GraphView(g,vfilt=lambda x: x.in_degree()>0 or x.out_degree()>0) g2 = gt.Graph(gv,prune=True)

Pruning the graph like this is the fastest approach, since it is O(N). The disadvantage is that you get another graph. This may, or may not be convenient for your algorithm. Another alternative would be to remove the vertices with higher index first. This is can by sorting the list of vertices to be removed, and then repeatedly calling g.remove_vertex(). Another way of essentially doing the same thing is to first mask the vertices which are going to be deleted, and then call g.purge_vertices(), i.e.: mask = g.new_vertex_property("bool") d = g.degree_property_map("total") mask.a = d.a > 0 # only vertices with nonzero total degree are kept g.set_vertex_filter(d) g.purge_vertices() The call to g.purge_vertices() is still O(N^2) in the worst case, but can be much faster if the vertices being removed tend to be at the "end" of the graph (i.e. have highest indexes). Another option would be simply to work with the filtered graph, since in this case each vertex "removal" is O(1). You can then either prune or purge the vertices at a later stage of the algorithm. Cheers, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>