問題タブ [directed-acyclic-graphs]

ファイル内の単純な依存関係を表す簡単な方法を探しています。できれば、構文が既に定義されている形式 (JSON、YAML など) を使用したいと考えています。私はgraphvizのドット構文に傾いています

これを行う他の方法はありますか？

これは、ユーザーが単純な依存関係を書き込んでアプリケーションで解析するためのものです。

クエリは次のようなものです

((A および (B または C)) から到達可能) かつ ((D および E) から到達不能) であるすべての頂点を返します。

クエリは、到達可能性に関するあらゆる種類のブール制約で形成できます。

このクエリを高速に実行する効率的な方法はありますか? 実際にすべてのアイテムの到達可能な頂点のセットを見つける以外に、それらのセットで和集合、交差、およびマイナスを設定しますか?

有向非巡回グラフの幅を見つけようとしています...隣接リストさえなくても、任意に順序付けられたノードのリストで表されます。

グラフ/リストは、実行順序の基準としてファイルを使用する並列 GNU Make のようなワークフロー マネージャー用です。各ノードには、ソース ファイルとターゲット ファイルのリストがあります。ファイル名を指定すると、それを生成するノードを決定できるように、ハッシュ テーブルが用意されています。このように、このテーブルを使用して各ソース ファイルを生成するノードを調べることで、ノードの親を特定できます。

これは、コードを大幅に変更することなく、現時点で私が持っている唯一の能力です。コードはしばらく公に使用されてきましたが、構造を大幅に変更して不適切なリリースを行うことは避けたいと考えています。いいえ、厳密にテストする時間はありません (私はアカデミックな環境にいます)。理想的には、ノードにフィールドを追加するよりも危険なことをせずにこれを実行できることを願っています。

私の現在のアプローチとその欠陥の概要を説明するコミュニティ wiki の回答を投稿します。誰かがそれを編集したり、出発点として使用したりしたい場合は、お気軽に. 物事を明確にするためにできることがあれば、質問に答えたり、必要に応じてコードを投稿したりできます。

ありがとう！

編集：気になる人のために、これはCになります。はい、私の疑似コードがひどく失敗したPythonのそっくりさんにあることは知っています。言語はあまり関係ないと思います。

しばらくの間、ポイント A からポイント B への有向非巡回グラフの最大パスを見つけるために、複雑さ O(V + E) で実行されるアルゴリズムを使用しています。 A、および各ノードが持つ「親」(他のノードから来るエッジ) の数に注意してください。次に、BFS を実行しますが、すべての「親」を既に使用している場合にのみ、ノードを「アクティブ化」します。

このアルゴリズムに特別な名前はありますか? 私はそれを情報学の教授に話しました.彼はそれを「DAGの最大パス」と呼んでいました.マキシマムパス」。

私の理解では、make実行すると、プロジェクト内のすべての依存関係を表す DAG が内部的に生成されます。その DAG を取得してグラフ化する方法はありますか? たとえば、graphviz のようなものを使用しますか?

Ubuntu 8.04 で gnu make を使用しています。

編集

mamdagおよびmamdotと呼ばれるこれらのツールに出くわしました。nmake と gnu make の両方で動作するはずですが、gnu make で mam ファイルを吐き出すオプションが見つからないようです。

ここからダウンロードできます- これらのパッケージ:

INIT
ast-base
ast-gpl

MAM 言語と mamdot ツールについて説明しているAT&T の Glenn Fowler によるこの記事を見つけました。

これを機能させるには gnu make にパッチを当てる必要があるようですが、まだ 100% 確実ではありません。

たぶん別の方法がありますか？

Floyd–Warshall/Dijkstra の返信が殺到する前に、状況を説明させてください。どちらのアルゴリズムもこのケースに合わせて調整できると確信しているためです。そのため、メモリの観点から管理しやすくする必要があります）

私が持っているのは、ノード 0 からノード n まで生成された Web グラフです。ノード 3 はノード 5 にリンクできません。すべての「ノード」は in_neighbours[nodeID] および out_neighbours[nodeID] として表され、nodeId=3 と言うので、ノード 3 について話していることになります。また、in_/out_ は両方ともソートされていることに注意してください (5 が選択されるため、in_ は自然にソートされます)。一度にすべてのリンクをアウトし、その場合にのみ 6 が out_links を選択するため、3 の in_ には {6, 5, 7} を含めることはできず、ofc の両方に重複を含めることができます。(in/out はサイズ n の ArrayList 配列です。ここで、out_ は常にサイズ d または m であり、n と共にユーザーによって起動時に指定されます)

ウェイトはありません。私がしなければならないことは、 averageDistance() を見つけることです

私がこれまでに持っているのは、最良のケースです。すべての距離を同時にではなく、j と i の間の距離だけを見つけたいことに注意してください (メモリが不足しています。m=20 d=1 000 000 でテストされます)。

したがって、「より新しい」（この時点でグラフが完成している）ノードiが古い仲間のいずれかに直接リンクしているかどうかを尋ねています。そうであれば、距離は1ホップです。

それは私だけですか、それともノードが後方にトラバースされた場合、「最短」パスが常に最初に見つかったパスになりますか?

基本ケースの後の「else」である 1 でないかどうかを確認するにはどうすればよいですか? 私の数学はかなり弱いです 優しくしてください:) リンクがソートされているという事実を利用するためのヒントはありますか?

それは宿題でも、ごまかそうとしているものでもなく、コード自体の問題でもありません。これは便利なツールでなければなりません。「学習」は途中で自然に行われます。

m=7 n=13 のノード ID、アウト リンク、イン リンクでグラフがどのように見えるかを次に示します (0 サイクルは、グラフがどのように初期化されるかに注意してください)。

長々と読んで辛くてすみません。 EDIT：メソッドのコードが間違っています。これは私が今正しいと思うものです。

dist nr2 のリビジョンです。パスが存在するかどうかを試してみてください:

重複の可能性：
[python]：2つのノード間のパス

誰かがこれを行う方法に関するいくつかのリソースを私に指摘できますか？私はnetworkxPythonライブラリとして使用しています。

ありがとう！

非巡回有向グラフがあります。エッジ (v1,v2) がグラフ内にある場合、レベル (v1) > レベル (v2) になることを保証する方法で、各頂点にレベルを割り当てたいと思います。(v1,v2) と (v3,v2) がグラフにあるときは常に level(v1) = level(v3) である場合も同様です。また、可能なレベルは離散的です（自然数であると見なすこともできます）。理想的なケースは、(v1,v2) がグラフ内にあり、v1 から v2 へのパスが他にない場合は常に level(v1) = level(v2) + 1 ですが、他の制約ではそれが不可能な場合があります -たとえば、エッジ (a,b) (b,d) (d,e) (a,c) (c,e) を持つ 5 つの頂点上のグラフを考えます。
これを解決するための適切なアルゴリズムを知っている人はいますか? 私のグラフはかなり小さい (|V| <= 25 程度) ので、非常に高速なものは必要ありません。シンプルさがより重要です。

これまでの私の考えでは、最小の要素を見つけてレベル 0 を割り当て、すべての親を見つけてレベル 1 を割り当て、適切な頂点に +0.5 を追加して矛盾を解決するだけですが、これはかなりひどいようです。

また、すべての「暗黙の」エッジを削除する (つまり、グラフに (v1,v2) と (v2,v3) の両方が含まれる場合は (v1,v3) を削除する) と役立つかもしれないと感じています。

次の基準に従ってサンプル ノードを効率的に描画したい、大きな有向非環状グラフ (DAG) があります。

1. 絶対にサンプリングしてはならない固定ノード A を指定します
2. A を直接的または間接的に参照するノードはサンプリングされません
3. 他のすべてのノードは等しい確率でサンプリングされます

ノードは、それらが参照する他のノードへのポインターを持つオブジェクトとして格納されます。グラフ全体は、他のすべてを直接的または間接的に参照する単一のルート ノードから到達できます。

これを行うための適切なアルゴリズムはありますか? DAG は大きいため、大量の追加メモリを必要としないのが理想的です。

ビットマップ画像で視覚化したい大きな有向非巡回グラフがあります。

理想的には、すべてのルート ノードを画像の上部に配置し、すべてのリーフ ノードを下部に配置したいと考えています。つまり、グラフのエッジはすべて下方向を向いています。

これらの制約を満たし、優れた視覚化を生成するすべてのノードの座標を計算するための優れたアルゴリズムはありますか?