問題タブ [directed-acyclic-graphs]

これが単純な解決策なのか、「名前付き」アルゴリズムなのかわからないので、ここで質問したいと思いました。

コンパイラからのデータフローグラフ（DFG）があります。これはアーク加重DAGです。アークの重みはさまざまな操作の待ち時間を示し、ノードは操作自体（加算、減算、負荷など）を表します。クリティカルパスで計算を実行できるようにする最小限のリソースセットを見つけようとしています。

私はすでにこれを次の方法で行っています：

次に、resources配列には、競合が発生しないようにするために必要な最小限のリソースが含まれ、最終的なクロック値がクリティカルパスになります（これは、これが宿題の問題ではないことを証明するためだけのものです=]）

これに「名前」があるのか​​、それとも他にかわいい方法があるのか​​、疑問に思っています。ありがとう！

有向非巡回グラフをツリーに変換するアルゴリズムを実装しようとしています(楽しみ、学習、カタ、名前を付けてください)。だから私はデータ構造ノードを思い付きました：

それはかなり簡単です。方法:

そしてテスト：

さらに、データ構造にはいくつかの改善が必要です。

• GetHash、toString、Equals、== 演算子のオーバーライド
• IComparable の実装
• LinkedList はおそらくより良い選択です

また、変換の前に確認する必要がある特定の事柄があります。

• マルチグラフ
• DAG(Cycles)なら
• DAG のダイアモンド
• DAG の複数のルート

全体として、いくつかの質問に絞り込まれ ます。コンバージョンを改善するにはどうすればよいですか? これは再帰であるため、スタックを爆破することができます。スタックを追加して記憶することができます。継続渡しスタイルを行うと、より効率的になりますか?

この場合、不変のデータ構造の方が良いと思います。それが正しいか？

チャイルズは正しい名前ですか？:)

次のことができるJavaに推奨される「グラフ化」アルゴリズムライブラリはどれですか。

1. カスタム オブジェクトをノードとして使用する (すべて同じオブジェクト タイプを想定)
2. これらのノード間の接続の指定を許可する
3. これらのノードで標準アルゴリズムを提供します (サイクル検出、最短パス...)
4. ノード + 接続でカスタム ビジターを許可する (ビジター パターン)

過度に複雑にしないでください (可能な場合)。まともなレベルのjavadocを用意してください（+ mavenパッケージがあればいいでしょう）。

ここで私の深みから少し離れており、友人に電話する必要があります。トラバースする必要がある有向非循環グラフがあり、初めてグラフ理論に出くわしています。私は最近それについてたくさん読んでいますが、残念ながら私はこれを学術的に理解する時間がありません. このツリーを処理する方法について、誰かが助けてくれますか?

ルールは次のとおりです。

• n 個のルート ノードがあります(私はそれらを「ソース」と呼びます)
• n個のエンドノードがあります
• ソースノードは数値を運ぶ
• 下流のノード (私は「ワーカー」ノードと呼んでいます) は、追加、多重化などの受信値に対してさまざまな操作を実行します。

以下のグラフからわかるように、ノードa、b、およびは、 、、または のc前に処理する必要があります。def

この木を歩く正しい順番は？

各キーワードにIDが割り当てられ、一意であるキーワードテーブルがあります。親キーワードのIDを子キーワードのIDにリンクする2番目のテーブルがあります。1つのキーワードには、最大で約800人の子を含めることも、まったく子を持たないこともできます。子供はさらに多くのキーワードの親になることができます（そして...）

私が遭遇している問題は、子供（または孫または曽孫）が最初のキーワードの親であり、循環構造を引き起こす可能性があることです。再帰関数を使用して最初のキーワードのツリーデータ構造を構築しようとしていますが、関数が終了しないか、Pythonの1000レベルの再帰制限を超えています。

これを防ぐために（または挿入中に事前チェックを行うために）親/子テーブルを設計するためのより良い方法はありますか、またはこの状態が発生するのを防ぐために再帰関数を書くためのより良い方法はありますか？再帰関数の深さを制限しようとしましたが、単一レベルの問題が発生しました（つまり、子が親の親になります）。繰り返しますが、私の目標は、最初のキーワードのツリー構造を作成することです。

大きなグラフサイズでトポロジカル ソートが実行される実際のアプリケーションを探しています。

そのような事例を見つけることができると私が想像するいくつかの分野は、バイオインフォマティクス、依存関係の解決、データベース、ハードウェア設計、データ ウェアハウジングなどでしょう。トップソート。

データ/プロジェクトが公開されていない場合でも、ヒント (および潜在的なグラフ サイズの大きさの見積もり) が役立つ場合があります。

抽象的な言葉での質問:

クエリ時に排他的な頂点のサブセットを含む有向非巡回グラフ (DAG) があります (サブセットごとに 1 つのアイテムのみがクエリの結果に存在する必要があります)。グラフ構造を照会するとき、グラフ内の頂点の既知のサブセットから単一のアイテムのみを選択しながら、特定の頂点から流れる頂点のセットを取得したいと考えています。

具体的な質問:

アセンブリ (頂点) とその依存関係 (エッジ) を格納する DAG があります。アセンブリまたはアセンブリのセットを指定すると、関連するすべてのアセンブリとその依存関係のセットを取得するためにクエリを実行する必要があります。難しいのは、各アセンブリには複数のバージョンがあり、アセンブリの 1 つのインスタンスしかプロセスにロードできないことです。特定のアセンブリの依存関係は、アセンブリのさまざまなバージョン間で異なります。

この問題または一連の問題に名前はありますか? 解決策を見つけるために調査できる標準アルゴリズムは?

考えられるソリューション分野:

推移閉包は良い解決策に近いように見えますが、サブセット (アセンブリ バージョン) から選択されたアイテムは、グラフを通過するパスに応じて変化します。おそらく複数の分岐を通過するため、グラフを通過するパスをトレースして生成する必要があります。推移閉包。

グラフデータベースはかなり役立つかもしれませんが、絶対に必要でない限り、今はその道をたどりたくありません。

次の条件と制約を使用して、DAG 内の特定のノードを横切るパスの数をカウントするアルゴリズムを探しています (「間」の概念に似ています)。

グラフ内のソース/宛先ノードのセットのカウントを行う必要があり、すべてのノード、つまり中間ノード n の場合ではありません。ノード S のセットからノード D のセットへの個別の最短パスの数を知りたいです。 n まで (そして個別とは、少なくとも 1 つの非共通ノードを持つ 2 つのパスごとを意味します)

DAG が非常に大きくてもエッジがまばらである可能性があるため、ノード上の深いネストされたループが優先されないことを考慮して、これを行うために提案できるアルゴリズムは何ですか。

私はCouchDBを見ています。ドキュメントにはバージョンがあり、競合するバージョンが存在する可能性があります。dvcsのように、バージョンシーケンスを有向非巡回グラフ（DAG）として保存しますか？そうでない場合、それはどのように実装されますか？