11

DAG を「反転」(反転?裏返し?)するアルゴリズムを探しています。

       A*      # I can't ascii-art the arrows, so just
      / \      # pretend the slashes are all pointing
     B   C     # "down" (south-east or south-west)
    /   / \    # e.g. 
   G   E   D   # A -> (B -> G, C -> (E -> F, D -> F))
        \ /
         F

私が使用している表現は、真に不変の DAG です (「親」ポインターはありません)。同等のノードを使用して「鏡像」グラフを作成しながら、何らかの方法でグラフをトラバースしたいのですが、ノード間の関係の方向が逆になっています。

         F*
        / \
   G*  E   D   # F -> (E -> C -> A, D -> C -> A), G -> B -> A
    \   \ /    # 
     B   C     # Again, arrows point "down"
      \ /      # 
       A       #

したがって、入力は一連の「ルート」(ここでは {A}) です。出力は、結果グラフの「ルート」のセットである必要があります: {G, F}。(ルートとは、着信参照のないノードを意味します。リーフは、発信参照のないノードです。)

入力のルートは出力のリーフになり、その逆も同様です。変換はそれ自体の逆でなければなりません。

(興味深いことに、構造クエリ用の XML を表現するために使用しているライブラリに機能を追加したいと思います。これにより、最初のツリーの各ノードを 2 番目のツリーの「ミラー イメージ」にマップできます (また、元に戻すことができます)。繰り返します) クエリ ルールのナビゲーションの柔軟性を高めるためです)。

4

5 に答える 5

2

すでに行ったことがある場所で深さ優先の検索マーキングを行うだけで、矢印をトラバースするたびに、結果の DAG に逆方向が追加されます。葉を根として加えます。

于 2009-02-27T14:46:28.353 に答える
2

私の直感的な提案は、グラフの深さ優先トラバーサルを実行し、ミラーリングされたグラフを同時に構築することです。

各ノードをトラバースするとき、ミラーリングされたグラフに新しいノードを作成し、新しいグラフでそのノードとその前のノードの間にエッジを作成します。

子を持たないノードに到達した場合はいつでも、それをルートとしてマークします。

于 2009-02-27T14:47:35.403 に答える
1

単純なグラフ走査でこれを解決しました。トポロジカルソートは、有向非巡回グラフにのみ役立つことに注意してください。

隣接リストを使用しましたが、隣接行列でも同様のことができます。

Pythonでは次のようになります。

# Basic Graph Structure
g = {}
g[vertex] = [v1, v2, v3] # Each vertex contains a lists of its edges

vのすべてのエッジを見つけるには、リストg [v]をトラバースすると、すべての（v、u）エッジが得られます。

逆グラフを作成するには、新しい辞書を作成し、次のように作成します。

    reversed = {}
    for v in g:
        for e in g[v]:
            if e not in reversed:
                reversed[e] = []
            reversed[e].append(v)

これは、大きなグラフでは非常にメモリを消費します（メモリ使用量が2倍になります）が、非常に簡単に操作でき、非常に高速です。ジェネレーターを構築し、ある種のdfsアルゴリズムを使用することを含む、より賢い解決策があるかもしれませんが、私はそれに多くのことを考えていません。

于 2012-04-12T19:39:23.863 に答える
-1

深さ優先検索は、目的のものを生成できる可能性があります。ツリーを通るパスに注意し、トラバースするたびに、結果の DAG に逆を追加します (葉はルートです)。

于 2009-02-27T14:44:32.400 に答える