16

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

誰かが正しい方向への例や指針を持っていますか?

明確化の更新

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

  • A には依存関係がありません
  • B は A、C、および E に依存する
  • C は A に依存する
  • D は A に依存する
  • E は C と A に依存する

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

--A

--+--B

---+--C

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

--+--え

トポロジカル ソート

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

  • あ
  • B
  • C
  • D
  • え

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

ありがとう

ローハン

4

6 に答える 6

23

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

  • 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

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

「大規模な」または「複雑な」ツリーがある場合は、事前にではなく動的にツリーを展開するのが最善の方法です。そうしないと、プロセスが非常にメモリを集中的に使用する可能性があります。

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

ただし、ツリーでできないことは、最後の文にあることです。つまり、トポロジーの順序を維持します。つまり、B が C と同じコンテナーに読み込まれる場合、C も同じコンテナーに読み込まれることはありません。または、すべてを 1 つのコンテナーに入れることに我慢する必要があるかもしれません (「同じコンテナーにロードする」という意味を完全に理解しているわけではありません)。

幸運を！

于 2009-07-13T08:58:39.403 に答える
5

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

于 2009-03-09T02:18:46.180 に答える
1

それは、DAG をどのように表すかによって大きく異なります。たとえば、隣接行列 (ノード i からノード j へのエッジがある場合は A[i,j] = 1、そうでない場合は 0)、ポインターのシステム、またはノードの配列とエッジ....

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

于 2009-03-09T02:06:51.623 に答える
0

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

于 2009-03-09T02:05:48.583 に答える