python - 在python中实现有向图

Question

我阅读了Python Patterns - Implementing Graphs。然而，这种实现对于获取指向节点的边来说效率很低。

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

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

Answer 1

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

Answer 2

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

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

Answer 3

这不能回答您的图形问题，但您当然可以在 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]

Answer 4

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 是一个很棒的库。有关更多详细信息，请参见此处。

Answer 5

看看Pygraph。我已经将它用于没有内存或运行时问题的大型有向（和无向）图，尽管它都是在 Python 中实现的，因此 C++ 包装的实现可能会快得多。