2

Node特に後継者と先行者のセットを持つ有向グラフのノードを表すクラスを実装しようとしています。セットのように動作したいNode.predecessorsとNode.predecessors思います。特に、それらの要素を反復処理し、要素を追加および削除し、包含をチェックし、反復可能オブジェクトからそれらを設定したいと考えています。ただし、node_1.sucessors.add(node_2)それが True である必要がありますnode_1 in node_2.pedecessors。

この魔法を実装する の新しいサブクラスを書くことは可能だと思われますsetが、私が見る限り、そのようなクラスの実装は非常に面倒ですNode。後継者であり、追加などのためにいくつかの特別なメソッドが必要になるため、それnode_1.sucessors.add(node_2)は呼び出さnode_2.predecessors.add(node_1)れず、無限ループにつながります。

その場で 2 つのアトリビュートの 1 つを生成する(node for node in all_nodes if self in node.sucessors)ことは可能ですが、グラフに属するすべてのノードを追跡する必要がありweakref.WeakSetます__init__。すべてのノードの大きなセットは、複数のばらばらなグラフがある場合に計算量が大きくなり、先行ノードのセットを変更する方法がわかりません。

誰かがこれに対する良い解決策を持っていますか?

4

1 に答える 1

5

add メソッドをクラスでラップし、そのラッパー メソッド内で predecessors と sucessors の 2 つの属性を使用するとどうなるでしょうか。このようなもの

それが私の頭に浮かぶ最初の解決策です：

class Node:

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

    def addSucessor(self, node):
        self.suce.add(node)
        node.pred.add(self)
于 2012-04-08T14:57:32.607 に答える