On 01/11/2013 11:49 AM, Giuseppe Profiti wrote: > 2013/1/11 Va Sa <[email protected] <mailto:[email protected]>> > > 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 <[email protected]>
signature.asc
Description: OpenPGP digital signature
_______________________________________________ graph-tool mailing list [email protected] http://lists.skewed.de/mailman/listinfo/graph-tool
