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