# Fast initialization of graph

Hi there

I've just started using graph tool, and so far I'm very impressed with the
ease of use and the thorough documentation.

I'm currently trying to instantiate a fully connected graph with some 600
vertices, but I find that adding all the edges usually takes around 10
seconds on my system. The fastest way of doing it that I have come up with
so far is to write:

from itertools import combinations
edges = [g.add_edge(v1,v2) for (v1,v2) in combinations(g.vertices(),2)]

But I'm wondering if there is a faster method?

Thanks for a great tool

Jonas

Hi,

I'm currently trying to instantiate a fully connected graph with some 600
vertices, but I find that adding all the edges usually takes around 10
seconds on my system. The fastest way of doing it that I have come up with
so far is to write:

from itertools import combinations
edges = [g.add_edge(v1,v2) for (v1,v2) in combinations(g.vertices(),2)]

But I'm wondering if there is a faster method?

You can create a "random" graph with all degrees equal to N - 1:

g = random_graph(600, lambda: 600 - 1, directed=False, random=False)

This should be much faster. Note the option 'random=False' which avoids
the random placement of the edges, which would be completely pointless
in this case.

I'm planning to include a complete graph generator, as well as some
other simple generators, which would make this more straightforward.

Cheers,
Tiago

Thanks a lot, I'll try it out!

attachment.html (1.9 KB)

random_graph is indeed much faster (0.01s as opposed to 7s for a fully
connected graph with 500 vertices)

An important pitfall when using random_graph to generate a graph is that
the edges of the graph aren't iterated over in the order of their index.
This means that assigning values to the underlying array of a propertyMap
is tricky. A simple fix is to call

graph.reindex_edges()

after generating the graph. This operation also runs in about 0.01s on a
fully connected graph of 500 nodes on my machine.

attachment.html (3.02 KB)