python – igraph：为什么add_edge函数如此缓慢地对add_edges？

我很惊讶：

import igraph
import random,time
start_time = time.time()
G = igraph.Graph(directed = True)
G.add_vertices(10000)
for i in range(30000):
   G.add_edge(random.randint(0,9999),random.randint(0,9999))
print "done in " + str(int(time.time() - start_time)) + " seconds"

返回在63秒内完成

而

import igraph
import random,time
start_time = time.time()
G = igraph.Graph(directed = True)
G.add_vertices(10000)
edges = []
for i in range(30000):
    edges += [(random.randint(0,9999))]
G.add_edges(edges)
print "done in " + str(int(time.time() - start_time)) + " seconds"

在0秒内完成返回.
项目中有人知道为什么吗？

解决方法

原因是igraph使用索引边列表作为C层中的数据结构.索引使得可以在恒定时间内查询特定顶点的邻居.如果您的图表很少更改,这很好,但是当修改操作比查询更频繁时,它会成为负担,因为无论何时添加或删除边缘,都必须更新索引.因此,每次调用add_edge都会使igraph重新索引其内部数据结构.好处是,如果你必须重建索引,你也可以使用add_edges以大致相同的成本添加许多边.因此,在您的第一个代码示例中,您重建索引30000次,而在第二个示例中,您只重建索引一次.

顺便说一下,使用Graph.Erdos_Renyi(n = 10000,m = 30000)可以更快地完成你正在做的事情.