有向图节点:跟踪后继者和前任者

Question

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

似乎有可能编写一个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)应该可以动态生成两个属性中的一个属性,但是我需要跟踪属于图形的所有节点,如果我只有一个图形,但是使用一个,这很容易(将其添加到weakref.WeakSet类属性中__init__)如果我有多个不相交的图,那么所有节点的大集合会导致大量的计算工作,而我看不到如何修改前辈集.

有人有一个很好的解决方案吗？

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)