[graph-tool] Fast initialization of graph

Jonas Arnfred jonas at ifany.org
Wed Mar 20 08:34:28 CET 2013


To follow up on your answer in case others will encounter it someday: Using
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.


On 19 March 2013 21:35, Jonas Arnfred <jonas at ifany.org> wrote:

> Thanks a lot, I'll try it out!
>
>
> On 19 March 2013 18:51, Tiago de Paula Peixoto <tiago at skewed.de> wrote:
>
>> Hi,
>>
>> On 03/19/2013 09:39 AM, arnfred wrote:
>> > 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
>>
>> --
>> Tiago de Paula Peixoto <tiago at skewed.de>
>>
>>
>> _______________________________________________
>> graph-tool mailing list
>> graph-tool at skewed.de
>> http://lists.skewed.de/mailman/listinfo/graph-tool
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.skewed.de/pipermail/graph-tool/attachments/20130320/8ea77ea4/attachment.htm>


More information about the graph-tool mailing list