問題タブ [directed-acyclic-graphs]

有向非巡回グラフの強度、特に特定のノードの強度を判断するための堅実なアルゴリズム/アプローチとして認識されているものは興味深いものです。これに関する主な質問は、次の 2 つのグラフに要約できます。

(グラフが表示されない場合は、ここをクリックするか、次のリンクにアクセスしてください: http://www.flickr.com/photos/86396568@N00/2893003041/

私の目には、A は A よりも強い立場にあります。リンクがノックアウトされた場合に、ノードがどれだけ強く残るかで強さを判断しています. 最初のものは細い「竹馬」、2番目のものは太い「茎」と呼んでいます。

ノードの強さを判断するためにこれまでに検討したアプローチは次のとおりです。

1) 下のノードの数をカウントし、上のノードの数を引きます。

• A=7、a=7、B=5、b=1

2) 各ノードの (終端までの) 完全なパスの数を数え、それらの長さを合計します。

• A=17 (1+5+5+5+1)、B=12 (4+4+4)、a=9 (3+3+3)、b=2
• これにより、茎ではなく支柱が強くなります。

3) すべての可能なパスを数え、すべてのノードを宛先として扱います。

• A=9 (A->B、A->C、A->D、A->E、A->G、2xA->F、2xA->H)、B=6、a=9、b= 2

これまでのところ、3 が最良の選択肢のように思えますが、DAG 用に一般化された、より優れた選択肢はありますか? これは既知の最善のアプローチを持っているものですか？原則は、グラフ内のできるだけ多くの情報を使用し、解決策を直感的に説明できるようにすることです。

有向グラフが非巡回かどうかを確認するにはどうすればよいですか? そして、アルゴリズムはどのように呼び出されますか? 参考になれば幸いです。

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

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

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

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

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

単一のソースからすべての最終目的地までの最長パスを見つけるにはどうすればよいですか。つまり、ソース i1 の場合、i1 -> o1 と i1 -> o2 の間の最長パスを指定します。

上記のグラフで説明されている凡例は次のとおりです。 (i1、i2) は開始ノード (o1、o2) は終了ノード (1-8) はサブグラフです エッジは +ive/-ive の重みを持つ場合があります

このネットワークの最長パスは、次の順序になっています。

最悪のパス: i1 -> 1 -> 4 -> o1

次に、すべてのパス i1 … -> … o1

その後、i1 -> 5 -> 6 -> o2

(i1 -> 3) または (3 -> 4) サブネットワークの選択が i1 -> 5 より長い場合でも無視する方法が必要

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 と同じコンテナにある必要があります。

ありがとう

ローハン

このデータ構造を C でどのように実装しますか? これは、DAWG に似た構造ですが、DAWG の 2 倍のスペース効率であり、プレフィックスのみを圧縮するトライよりも効率的です。

私はGitXの作者です。GitX の機能の 1 つは、ここで見られるように、ブランチの視覚化です。

この視覚化は現在、git から発行されたコミットを正しい順序で読み取ることによって行われています。コミットごとに親がわかっているため、正しい方法でレーンを構築するのはかなり簡単です。

独自のコミット プールを使用し、コミットを自分で線形化することで、このプロセスをスピードアップしたいと考えています。これにより、既存のロードされたコミットを再利用でき、正しい順序でコミットを発行する必要がないため、git がコミットをより速く発行できるようになります。

ただし、これを達成するためにどのアルゴリズムを使用すればよいかわかりません。コミットのロードには長い時間がかかる可能性があるため (100,000 件のコミットで 5 秒以上、すべて表示される必要があります)、ビルドがインクリメンタルであることが重要です。

Gitk も同じように進んでおり、実装方法を示すパッチがここにありますが、私の TCL スキルは弱く、パッチは十分にコメントされておらず、理解するのが少し難しくなっています。

また、何十万ものコミットを処理する必要があるため、このアルゴリズムが効率的であることも望んでいます。また、表に表示する必要があるため、特定の行へのアクセスが高速であることが重要です。

これまでの入力、必要な出力、およびいくつかの観察事項について説明します。

入力：

• コミット ID をコミット オブジェクトにマップするハッシュ テーブルの形式で、コミットの現在のプールがあります。このプールは完全である必要はありません (すべてのコミットが必要です)
• 新しいコミットがロードされるたびに呼び出すことができるコールバックを使用して、git からの新しいコミットで別のスレッドをロードしています。コミットが行われる順序は保証されていませんが、ほとんどの場合、次のコミットは前のコミットの親になります。
• commit オブジェクトには、独自のリビジョン ID とそのすべての親のリビジョン ID があります
• リストする必要がある支部長のリストがあります。つまり、表示されるべき DAG の単一の「トップ」はありません。また、単一のグラフ ルートである必要もありません。

出力：

• これらのコミットをトポロジー順に線形化する必要があります。つまり、親がリストされた後にコミットをリストすることはできません。
• 上のスクリーンショットに見られる「分岐線」も必要です。それらのほとんどは子に依存しているため、これらはおそらく事前に計算する必要があります。

いくつかの注意事項:

• コミットのリストを再配置する必要があります。たとえば、一方のヘッドを他方の先祖にするコミットが現れるまで、関連のないコミット (ブランチ ヘッド) が必要になる場合があります。
• 複数のブランチ ヒントを表示する必要があります
• データがまだロードされている間、少なくとも部分的なビューを利用できるように、このプロセスは増分的であることが重要です。これは、新しいデータを途中で挿入する必要があり、支線を再調整する必要があることを意味します。

半順序を表す有向非巡回グラフ (DAG)をエンコードする XML ファイルがあります 。このようなグラフは、依存関係の指定やクリティカル パスの検索などに役立ちます。興味深いことに、私の現在のアプリケーションはビルド システムのコンポーネントの依存関係を指定することなので、頂点はコンポーネントであり、エッジはコンパイル時の依存関係を指定します。簡単な例を次に示します。

この DAG は次のように描画できます。

_{（出典：iparelan.com）}

半順序の最小要素に対応する頂点のみを含む別の XML ドキュメントを生成するXSLT スタイルシートを適用したいと考えています。つまり、着信エッジを持たない頂点です。サンプル グラフの最小頂点のセットは です。私のビルド依存関係アプリケーションでは、このセットを見つけることは価値があります。なぜなら、このセットのメンバーをビルドすると、プロジェクト内のすべてがビルドされることがわかっているからです。{A, B, F}

これが私の現在のスタイルシート ソリューションです (Apache Ant のxsltタスクを使用して、Java 上の Xalan でこれを実行しています)。重要な観察事項は、最小頂点はどのdirected-edge-to要素でも参照されないということです。

このスタイルシートを適用すると、次の出力が生成されます (これは正しいと思います)。

問題は、私はこのソリューションに完全に満足していないということです。のとのを XPath 構文と組み合わせる方法があるかどうか疑問に思っています。selectfor-eachtestif

私は次のようなものを書きたい：

current()しかし、関数は外側の//vertex式によって選択されたノードを参照しないため、それは私が望むことではありません。

これまでのところ、私のソリューションではXPath 1.0とXSLT 1.0の構文を使用していますが、XPath 2.0とXSLT 2.0の構文も受け入れています。

必要に応じて、Ant ビルド スクリプトを次に示します。

dotターゲットは、グラフをレンダリングするための Graphviz Dot 言語コードを生成し ます 。ここにあるxml-to-dot.xsl：

ウィキペディア: 有向非巡回グラフ

リーフノードは実際にはツリーではないため(各ノードは複数の子と複数の親を持つことができます)、実際にすべてのルートノードを見つけようとしているため、リーフノードがまだ適切な用語であるかどうかはわかりません(これは実際にはセマンティクスの問題です.すべてのエッジの方向を逆にすると、それらはリーフ ノードになります)。

現在、グラフ全体 (指定されたノードから到達可能) をトラバースしているだけですが、それはやや高価であることが判明したため、これを行うためのより良いアルゴリズムがあるかどうか疑問に思っています. 私が考えていることの 1 つは、(別のパスをたどっている間) 既にアクセスされたノードを追跡し、それらを再チェックしないことです。

他にアルゴリズムの最適化はありますか?

また、このノードが子孫であるルート ノードのリストを保持することも考えましたが、ノードが追加、移動、または変更されるたびに変更されるかどうかを確認する必要がある場合、そのようなリストを保持するのもかなりコストがかかるようです。削除されました。

編集：

これは、単一のノードを見つけるだけではなく、エンドポイントであるすべてのノードを見つけることです。

また、ノードのマスター リストもありません。各ノードには、その子と親のリストがあります。(まあ、それは完全に正しいわけではありませんが、事前に DB から数百万のノードをプルすると、非常にコストがかかり、OutOfMemory 例外が発生する可能性があります)

編集2:

可能な解決策を変更する場合と変更しない場合がありますが、グラフは、多くても数十のルート ノード (私が見つけようとしているもの) と数百万 (おそらく数千万または数億) のリーフ ノード (ここでから始めています）。