在Python中实现DAG

Question

我正在Python中实现一个DAG(directed acyclic graph)。我使用字典来实现该DAG，其中每个键表示图中的一个节点，与该键关联的值表示依赖于该键处节点的一组节点。 对于实现DAG，是否有必要使用OrderedDict而不是普通的Dict？OrderedDict会保留键插入的顺序。我想知道为什么在每个键的值表示相应键处节点的一组依赖节点时，有人希望保留节点插入顺序？

- Sharu Gupta

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或者将其放入您的requirements.txt文件中：

graphlib_backport; python_version < "3.9.0"

- Ian Goldby

Answer 2

假设你有以下DAG：

你可以将这个DAG表示为一个字典：

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

你也可以把这个DAG表示为一个有序字典，但这是不必要的。键/值对的顺序无关紧要。有一个有缺陷/不完整的Python DAG库使用了有序字典，但该库不是一个好的范例。用于Python DAG（和其他图形）的网络标准是networkx。你可以用代表图形边缘的元组列表创建一个networkx有向图：

import networkx as nx

graph = nx.DiGraph()
graph.add_edges_from([("root", "a"), ("a", "b"), ("a", "e"), ("b", "c"), ("b", "d"), ("d", "e")])

点击此处获取有关Python DAG的更多信息。

- Powers

---

我们如何为networkx安排位置，就像您所拥有的那个图形一样？ - alper

Answer 3

你可以使用普通字典或者有序字典(OrderedDict)来创建DAG，但如果使用有序字典(OrderedDict)，将会有一些优势。

• 保持顺序
• 键值改变：如果某个键的值被改变，该键的位置在有序字典(OrderedDict)中仍然不变。
• 删除和重新插入：删除和重新插入相同的键将把它推到队列的后面，而有序字典(OrderedDict)则会保持插入的顺序。

没有使用有序字典(OrderedDict)的代码：

class Graph:
    def __init__(self):
        self.nodes = {}
    
    def add_edges(self, edges):
        for edge_1, edge_2 in edges:
            if edge_1 not in self.nodes: self.nodes[edge_1] = []
            if edge_2 not in self.nodes: self.nodes[edge_2] = []
            self.nodes[edge_1].append(edge_2)
    

使用 OrderedDict 编写代码:

from collections import OrderedDict
class Graph:
    def __init__(self):
        self.nodes = OrderedDict()
    
    def add_edges(self, edges):
        for edge_1, edge_2 in edges:
            if edge_1 not in self.nodes: self.nodes[edge_1] = []
            if edge_2 not in self.nodes: self.nodes[edge_2] = []
            self.nodes[edge_1].append(edge_2)

- Mahendra S. Chouhan