用python实现有向图

Question

我读过Python Patterns - Implementing Graphs。但是，这种实现对于获取指向节点的边是低效的。

在其他语言中，一个常见的解决方案是使用二维数组，但要在Python中实现这一点，需要一个列表列表。这看起来不像是Python。

python中有向图的一个实现是什么？在python中，查找一个节点（作为两个单独的列表）的边的所有节点都很快？

Answer 1

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

Answer 2

这并不能回答您的图形问题，但您肯定可以在Python中实现2D列表，而不必以至少两种方式求助于列表列表：

你可以简单地使用字典：

import collections
t = collections.defaultdict(int)

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

这也有一个优点，那就是它是稀疏的。

对于更奇特的方法，但需要更多的工作，您可以使用1d列表并使用二维坐标以及表的高度和宽度计算索引。

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]

Answer 3

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

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