python - 有向图节点 : Keep track of successors and predecessors

Question

我正在尝试实现一个类 Node 表示有向图中的一个节点，特别是有一组后继者和前任者。我希望 Node.predecessors 和 Node.predecessors 表现得像集合，特别是我想遍历它们的元素、添加和删除元素、检查包含并设置它们从一个可迭代的。但是，在 node_1.sucessors.add(node_2) 之后，node_1 in node_2.pedecessors 应该为 True。

似乎可以编写一个 set 的新子类来实现这个魔法，但据我所知，这样一个类的实现会非常麻烦，因为它必须知道Node 它所属的对象，如果它是前驱或后继，则需要一些特殊的方法来添加等等，这样 node_1.sucessors.add(node_2) 就会不调用 node_2.predecessors.add(node_1) 从而导致无限循环。

动态生成两个属性之一 (node for node in all_nodes if self in node.sucessors) 应该是可能的，但是我需要跟踪属于一个图的所有节点，如果我只有一个图，这很容易(将它添加到 __init__ 中的 weakref.WeakSet 类属性)，但对所有节点使用一个大集合会导致大量计算努力，如果我有多个不相交的图，我不知道如何修改前辈的集合。

有人对此有好的解决方案吗？

Answer 1

如果您将 add 方法包装在您的类中，然后在该包装方法中，您只需使用前驱和后继这两个属性会怎么样。像这样

这是我想到的第一个解决方案:

class Node:

    def __init__(self):
        self.pred = set()
        self.suce = set()

    def addSucessor(self, node):
        self.suce.add(node)
        node.pred.add(self)