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.
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.