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 -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
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@skewed.de>
Thanks a lot, I'll try it out! On 19 March 2013 18:51, Tiago de Paula Peixoto <tiago@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@skewed.de>
_______________________________________________ graph-tool mailing list graph-tool@skewed.de http://lists.skewed.de/mailman/listinfo/graph-tool
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@ifany.org> wrote:
Thanks a lot, I'll try it out!
On 19 March 2013 18:51, Tiago de Paula Peixoto <tiago@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@skewed.de>
_______________________________________________ graph-tool mailing list graph-tool@skewed.de http://lists.skewed.de/mailman/listinfo/graph-tool
participants (3)
-
arnfred -
Jonas Arnfred
-
Tiago de Paula Peixoto