python - igraph：为什么 add_edge 函数比 add_edges 慢？

Question

我很惊讶：

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), random.randint(0,9999))]
G.add_edges(edges)
print "done in " + str(int(time.time() - start_time)) + " seconds"

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

Answer 1

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

顺便说一句，使用Graph.Erdos_Renyi(n=10000, m=30000).