有向非巡回グラフ（DAG）をツリーに変換する方法

StackOverflow https://stackoverflow.com/questions/624778

質問

DAGをツリーに変換するC＃の例を探しています。

正しい方向に例や指針がある人はいますか？

明確化の更新

アプリケーションのロードに必要なモジュールのリストを含むグラフがあります。各モジュールには、依存するモジュールのリストがあります。たとえば、ここに私のモジュール、A、B、C、D、Eがあります

  • Aには依存関係がありません
  • BはA、C、Eに依存しています
  • CはAに依存しています
  • DはAに依存しています
  • EはCとAに依存します

依存関係を解決し、次のようなツリーを生成したい...

-A

-+-B

----- +-C

--------- +-D

-+-E

トポロジカルソート

情報のおかげで、トポロジカルソートを実行して出力を逆にすると、次の順序になります

  • A
  • B
  • C
  • D
  • E

モジュールが正しいコンテキストにロードされるように、階層構造を維持したい、例えば...モジュールEはBと同じコンテナにあるべきです

ありがとう

ロハン

役に立ちましたか？

解決

グラフの理論的な答えと、これに対するプログラマーの答えがあります。プログラマー部分を自分で処理できると思います。グラフの理論的答え：

  • DAGは、AがBを必要とし、同時にB（またはBが必要とするモジュールの1つ）がAを必要とすることがないモジュールのセットです。循環的に依存しません。循環依存が発生するのを見てきました（例についてはGentooフォーラムを検索してください）。したがって、DAGがあることを100％確信することすらできませんが、持っていると仮定しましょう。循環依存関係を確認するのはそれほど難しくないので、モジュールローダーのどこかで確認することをお勧めします。
  • ツリーでは、AがBとCに依存し、BとCの両方がD（ダイアモンド）に依存するということはありえませんが、これはDAGで発生する可能性があります。
  • また、ツリーにはルートノードが1つだけありますが、DAGには複数の「ルート」を含めることができます。ノード（つまり、何も依存しないモジュール）。たとえば、GIMPのようなプログラムの場合、GIMPプログラムはモジュールセットのルートノードになりますが、GENTOOの場合、GUIを備えたほとんどすべてのプログラムは「ルート」です。ノード、ライブラリなどはそれらの依存関係です。 （つまり、KonquerorとKmailはどちらもQtlibに依存していますが、Konquerorに依存するものはなく、Kmailに依存するものもありません）

あなたの質問に対するグラフ理論的答えは、他の人が指摘したように、DAGはツリーに変換できないが、すべてのツリーはDAGであるということです。

ただし、（高レベルのプログラマーは答えます）グラフィカルな表現のためにツリーが必要な場合、特定のモジュールの依存関係だけに関心があり、そのモジュールに依存するものには関心がありません。例を挙げましょう：

A depends on B and C
B depends on D and E
C depends on D and F

これをASCIIアートツリーとして表示することはできません。これは、これをツリーに変換できないという単純な理由からです。 ただし、Aが依存するものを表示したい場合は、これを表示できます。

A
+--B
|  +--D
|  +--E
+--C
   +--D
   +--F

ご覧のとおり、ツリーにダブルエントリが表示されます。この場合は、「のみ」のみです。 Dただし、「すべて展開」を行う場合Gentooツリーでは、ツリーがモジュールの少なくとも1000倍のノードを持つことを保証します。 （Qtに依存するパッケージが少なくとも100個あるため、Qtが依存するすべてのものがツリーに少なくとも100回存在します。）

＆quot;大＆quot;がある場合または＆quot; complex＆quot;ツリー、事前にではなく、動的にツリーを展開するのが最善かもしれません。そうしないと、非常にメモリ集約型のプロセスになる可能性があります。

上記のツリーの欠点は、Bを開いてからDをクリックすると、AとBがDに依存するが、CもDに依存することではないことです。ただし、状況によっては、重要なのは、ロードされたモジュールのリストを保持している場合、Cのロード時にDがすでにロードされていることであり、CではなくBにロードされたことが重要です。ロードされた、それだけです重要です。特定のモジュールに直接依存するものを動的に維持する場合は、反対の問題（アンロード）も処理できます。

ただし、ツリーでできないことは最終文にあります。トポロジの順序を保持します。つまり、BがCと同じコンテナにロードされた場合、Cと同じコンテナにロードすることはできません。まあ。または、すべてを1つのコンテナに入れることに我慢しなければならない場合があります（「同じコンテナにロードする」とはどういう意味かを完全に理解しているわけではありません）

がんばって！

他のヒント

DAGとツリーは数学的には同じものではありません。したがって、変換を行うとあいまいさが生じます。定義上、ツリーにはサイクルや期間はありません。

モジュールをロードする順序を見つけるために探しているのは、ですDAGのトポロジカルソート。エッジがモジュールから依存するモジュールに移動する場合（最も可能性が高いと思われます）、モジュールはすべてのモジュールの前に表示されるため、トポロジソートの逆の順序でモジュールをロードする必要があります依存します。

エッジが依存するモジュールからそれらに依存するモジュールに移動するようにDAGを表す場合（上記のグラフのすべてのエッジを逆にすることでこれを取得できます）、順番にモジュールをロードできますトポロジカルソートの

DAGの表現方法に大きく依存します。たとえば、隣接行列（ノードiからノードjへのエッジがある場合はA [i、j] = 1、そうでない場合は0）、またはポインターのシステムとして、またはノードの配列および配列としてエッジ....

さらに、どの変換を適用しようとしているかは明確ではありません。接続されたDAGはツリーであるため、質問を少し明確にする必要があると思います。

すべてのサブツリーに単一のルートノードがある場合にのみ、それを行うことができます。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top