Am 22.01.20 um 06:54 schrieb Zouhair:
How are you doing steps 3.a and 3.e exactly?
Are you calling g.add_vertex() and g.remove_vertex() repeatedly?
Yes I am. I assumed that's not the best thing but compared to copying the graph, adding then removing the vertices was performing better.
The point here is that this is sub-optimal and can be avoided. Both the g.add_vertex() and g.remove_vertex() functions should not be called repeatedly. Graph.add_vertex() can be called with an optional argument specifying the number of vertices to be added, which happens much faster than calling it multiple times. Likewise, Graph.remove_vertex() can be called with a list of vertices that need to be removed, which is performed in a much more efficient way, specially if the vertices removed happen to be the ones with the largest indexes. -- Tiago de Paula Peixoto <tiago@skewed.de>