在python中实现有向图

Question

我读了Python模式 - 实现图形.然而,这种实现对于获得指向节点的边缘是低效的.

在其他语言中,常见的解决方案是使用二维数组,但要在Python中执行此操作需要列表列表.这似乎不是pythonic.

什么是Python中向图,其中发现所有边缘和从节点的节点(作为两个单独的列表)的实现是快？

Answer 1

您可以使用的另一个库是NetworkX.它提供了有向图的实现,它提供了用于获得任意节点集的边缘DiGraph.in_edges()和输出边缘的函数DiGraph.out_edges().使用示例在链接文档中提供,但遗憾的是我没有看到有关效率或运行时的任何详细信息.

Answer 2

networkx绝对是最流行的 Python 图形库。它有完善的文档，有很棒的 AP​​I，并且性能良好。假设您有以下图表：

以下是如何创建此图并计算指向节点 e 的所有边：

import networkx as nx

graph = nx.DiGraph()
graph.add_edges_from([("root", "a"), ("a", "b"), ("a", "e"), ("b", "c"), ("b", "d"), ("d", "e")])
print(graph.in_edges("e")) # => [('a', 'e'), ('d', 'e')]

以下是计算节点 b 指向的所有边的方法：

print(graph.out_edges("b")) # => [('b', 'c'), ('b', 'd')]

networkx 是一个很棒的库。请参阅此处了解更多详细信息。

Answer 3

如果您关心计算效率或科学计算，Scipy 会提供高效的 Graph 例程：

http://docs.scipy.org/doc/scipy/reference/sparse.csgraph.html