2

サイクルやダイアモンドを持たない hibernate/sql (つまり、単純な多対多の自己関連付け) で有向グラフを維持したいと考えています。

「ひし形なし」とは、ノードから他のノードへの「パス」が 1 つしかないことを意味します。これら 2 つのルールは、すべてのノードが 2 つのツリーのルートとして扱われる可能性があることを意味すると考えています。

これにはよく知られたアルゴリズムがありますか？質問は次のように要約されます:「グラフが現在整形式であるとすると、A と B の間に円弧を配置すると、ループまたはダイアモンドが作成されますか?」

4

1 に答える 1

0

エッジを追加するだけで削除しない場合は、グラフにも素集合セマンティクスを持たせることでこれを解決できると考えてください。新しいエッジを作成するときは、最初に 2 つのノードがまだ同じセットの一部になっていないことを確認します。そうでない場合は、リンクを作成し、セットでユニオンを実行します。

Python を知らなくても理解できるように、疑似コードに十分近い Python コードを次に示します。

class Node:
    # constructor
    def __init__(self):
        self.setParent = None
        self.graphParents = []
        self.graphChildren = []

    # disjoint set operations
    def getSetRoot(self):
        if self.setParent == None:
            return self
        else:
            self.setParent = self.setParent.getSetRoot()
            return self.setParent

    def joinSet(self, other):
        other.getSetRoot().setParent = self.getSetRoot()

    # graph operation
    def addChild(self, child):
        if self.getSetRoot() == child.getSetRoot():
            raise ValueError("Cannot add child!")
        else:
            self.graphChildren.append(child)
            child.graphParents.append(self)
            self.joinSet(child)

前述したように、これはエッジをまったく削除しない場合にのみ機能します。これを行うには、新しく分離されたグラフ セグメントのばらばらなセットを再構築する必要があり、非常に時間がかかる可能性があります。ごくまれにしかエッジを削除しない場合 (追加する頻度の何倍も少ない場合) は、このルートに進むのが妥当かもしれません。

于 2012-05-20T07:18:37.643 に答える