Efficient mass removal of vertices possible?

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

attachment.html (667 Bytes)

2013/1/11 Va Sa <mihtal(a)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)

However I don't know if with this approach the complexity would go down.

Good luck,
Giuseppe

attachment.html (1.5 KB)

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

Thanks guys for the help!

filtering to GraphView and then pruning to a new graph when needed was
indeed the most efficient way for my needs.

Val