在 python 中实现 DAG

Question

我正在 python 中实现一个 DAG。我正在使用字典来实现 DAG。每个键代表图中的一个节点。与键相关联的值表示依赖于该键节点的一组节点。

是否有必要使用orderedDict 而不是Dict 来实现DAG。OrderedDict 保留了键的插入顺序。我想知道为什么当每个键的值表示依赖于该对应键的节点的一组节点时，为什么要保留 DAG 中节点的插入顺序？

Answer 1

graphlib是Python标准库中用于创建有向非循环图形的模块。它是 3.9 版本中的新增内容。

从文档中复制/粘贴示例似乎有点多余，但这是一个非常简短的示例：

>>> graph = {"D": {"B", "C"}, "C": {"A"}, "B": {"A"}}
>>> ts = TopologicalSorter(graph)
>>> tuple(ts.static_order())
('A', 'C', 'B', 'D')

对于早期版本的 Python，有一个向后移植：pip install graphlib_backport或将其放入您的 requests.txt 文件中：

graphlib_backport; python_version < "3.9.0"

Answer 2

假设您有以下 DAG：

您可以将此 DAG 表示为字典：

graph = {
    'root': ['a'],
    'a': ['b', 'e'],
    'b': ['c', 'd'],
    'd': ['e']}

您还可以将此 DAG 表示为有序字典，但这是不必要的。键/值对的顺序并不重要。有一个有缺陷/不完整的 Python DAG 库，它使用有序字典，但该库并不是一个很好的例子。

networkx是 Python DAG（和其他图）的黄金标准。您可以使用表示图边的元组列表创建一个 networkx 有向图：

graph = {
    'root': ['a'],
    'a': ['b', 'e'],
    'b': ['c', 'd'],
    'd': ['e']}

有关 Python DAG 的更多信息，请参阅此处。