在Python中实现有向图

Question

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

在其他语言中，常见的解决方案是使用二维数组，但在Python中要做到这一点需要一个列表的列表。这似乎不像Python的特点。

有没有在Python中实现有向图的方法，可以快速找到所有与节点相连的入边和出边（以两个单独的列表形式）？

- jan

---

为什么列表的列表不符合 Python 的规范？在 Python 中，二维列表是相当常见的。您还可以使用成熟的 numpy.ndarray，它实现了 n 维数组，并支持按行或按列进行索引。 - David Robinson

Answer 1

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

- Michael Mauderer

Answer 2

networkx是目前最受欢迎的Python图形库。它文档齐全，API友好，执行效率高。假设你有以下图形：

下面是创建这个图形并计算指向节点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是一个很棒的库。详情请见这里。

- Powers

Answer 3

如果计算效率或科学计算是您关心的问题，Scipy提供了高效的图形处理程序:

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

- Edmon

---

而且，我认为压缩稀疏矩阵比普通的二维数组更适合表示图形，从空间效率上来看更加高效。 - JAB

如果我不知道图中节点的数量怎么办？ 如何使用矩阵高效地在运行时添加/删除节点？ - Salman Azmat

Answer 4

这并不回答你的关于图形的问题，但是你可以通过至少两种方式在Python中实现2D列表而不需要使用列表的方法:

你可以简单地使用字典:

import collections
t = collections.defaultdict(int)

t[0, 5] = 9
print t[0, 5]

这种方法的优点在于它是稀疏的。

如果需要更高级的方法，但需要更多的工作量，则可以使用1D列表，并使用2D坐标及表格的高度和宽度计算索引。

class Table(object):
    def __init__(self, width, height):
        self._table = [None,] * (width * height)
        self._width = width

    def __getitem__(self, coordinate):
        if coordinate[0] >= width or coordinate[1] >= height:
            raise IndexError('Index exceeded table dimensions')
        if coordinate[0] < 0 or coordinate[1] < 0:
            raise IndexError('Index must be non-negative')
        return self._table[coordinate[1] * width + coordinate[0]]

    def __setitem__(self, coordinate, value):
        if coordinate[0] >= width or coordinate[1] >= height:
            raise IndexError('Index exceeded table dimensions')
        if coordinate[0] < 0 or coordinate[1] < 0:
            raise IndexError('Index must be non-negative')
        self._table[coordinate[1] * width + coordinate[0]] = value


t = Table(10,10)
t[0, 5] = 9
print t[0, 5]

- Nathan

Answer 5

看一下Pygraph。我已经在大型有向（和无向）图中使用它很多次，没有内存或运行时问题，尽管它全部是用Python实现的，因此C++包装实现可能会更快。

- Pyrce