优化函数以将（有向）边列表转换为邻接列表
Optimising a function to convert a (directed) edge list to an adjacency list
我写了一个函数，它将一个二元组列表（表示有向图的边）转换成一个列表数组（表示如果你从数组给定的顶点开始，你可以到达哪些顶点指数）。
我目前拥有的：
def make_graph(edges, amount_of_vertices):
graph = [[] for _ in range(amount_of_vertices)]
for edge in edges:
graph[edge[0]].append(edge[1])
return graph
因此，对于此图：
它会这样做：
>>> make_graph([(0, 1), (2, 0), (1, 2), (0, 2)], 3)
[[1, 2], [2], [0]]
从顶点 0 开始，您可以到达顶点 1 和 2，依此类推。
它工作正常并提供了我想要的输出，但对于我的应用程序，这个 不够快 – 我的 real 图表将有大约 100,000 到 1,000,000 个顶点和 1-400 万条边。有没有办法提高性能？也许另一个列表理解，或者 numpy?
如果Python不能更快，我愿意接受其他语言的解决方案。
您可以从使用 defaultdict 删除与 dict 相关的开销开始
from collections import defaultdict
connenctions = defaultdict(list)
connection_input = [(0, 1), (2, 0), (1, 2), (0, 2)]
for x, y in connection_input:
connenctions[x].append(y)
>>> connenctions.values()
dict_values([[1, 2], [0], [2]])
最流行的方法是使用 networkx 包。实际上，尽管它的设计非常友好，但速度还是很慢。幸运的是，它有一些 Python 的替代方案。这是 detailed analysis of performace. I've tested alternatives such as igraph and graph-tools. However, graph-tools has a pretty good documentation but is Linux based and since I'm a Windows user, it was not accessible for me. Finally igraph did work for me after installing it from unoficial binaries，我对性能非常满意。然而，igraph 接受标记为从 0 开始的整数的节点，因此如果需要，您将需要创建节点的重新映射。
我写了一个函数，它将一个二元组列表（表示有向图的边）转换成一个列表数组（表示如果你从数组给定的顶点开始，你可以到达哪些顶点指数）。
我目前拥有的：
def make_graph(edges, amount_of_vertices):
graph = [[] for _ in range(amount_of_vertices)]
for edge in edges:
graph[edge[0]].append(edge[1])
return graph
因此，对于此图：
它会这样做：
>>> make_graph([(0, 1), (2, 0), (1, 2), (0, 2)], 3)
[[1, 2], [2], [0]]
从顶点 0 开始，您可以到达顶点 1 和 2，依此类推。
它工作正常并提供了我想要的输出，但对于我的应用程序，这个 不够快 – 我的 real 图表将有大约 100,000 到 1,000,000 个顶点和 1-400 万条边。有没有办法提高性能？也许另一个列表理解，或者 numpy?
如果Python不能更快，我愿意接受其他语言的解决方案。
您可以从使用 defaultdict 删除与 dict 相关的开销开始
from collections import defaultdict
connenctions = defaultdict(list)
connection_input = [(0, 1), (2, 0), (1, 2), (0, 2)]
for x, y in connection_input:
connenctions[x].append(y)
>>> connenctions.values()
dict_values([[1, 2], [0], [2]])
最流行的方法是使用 networkx 包。实际上，尽管它的设计非常友好，但速度还是很慢。幸运的是，它有一些 Python 的替代方案。这是 detailed analysis of performace. I've tested alternatives such as igraph and graph-tools. However, graph-tools has a pretty good documentation but is Linux based and since I'm a Windows user, it was not accessible for me. Finally igraph did work for me after installing it from unoficial binaries，我对性能非常满意。然而，igraph 接受标记为从 0 开始的整数的节点，因此如果需要，您将需要创建节点的重新映射。