問題タブ [directed-graph]

有向グラフを「シリアル化」する単純なアルゴリズムを探しています。特に、実行順序に相互依存関係がある一連のファイルがあり、コンパイル時に正しい順序を見つけたいと考えています。私はそれがかなり一般的なことであるに違いないことを知っています-コンパイラは常にそれを行います-しかし、私のgoogle-fuは今日弱いです。このための「頼りになる」アルゴリズムは何ですか?

約 3500 の洪水制御施設があり、フロー パスを決定するためにネットワークとして表現したいと考えています (基本的に有向グラフ)。私は現在、SqlServer と CTE を使用して、すべてのノードとその上流コンポーネントを再帰的に調べています。これは、上流パスが多く分岐しない限り機能します。ただし、一部のクエリは、物理的にパスを下っていなくても (つまり、「ダウンストリーム」セグメントが 2 つまたは 3 つ)、アップストリームの複雑さが増すため、他のクエリよりも指数関数的に時間がかかります。場合によっては、クエリを強制終了する前に 10 分以上放置しました。私は単純な 2 列のテーブルを使用しています。1 つの列は施設自体で、もう 1 つは最初の列にリストされている施設の上流にある施設です。

現在の機能を使用してインデックスを追加して高速化を試みましたが、違いはありませんでした。また、グラフで可能な接続に関しては、どのノードも複数の上流接続を持つことができ、複数の「下流」ノードから接続することができます。

データに循環がある可能性は確かにありますが、これを確認する良い方法をまだ見つけていません (CTE クエリが最大再帰カウント ヒットを報告した場合を除き、それらは簡単に修正できました)。

それで、私の質問は、この情報を間違って保存しているのでしょうか? 上流のポイントを照会する CTE 以外のより良い方法はありますか?

有向グラフ内のサイクルを検出するための効率的なアルゴリズムはありますか?

実行する必要があるジョブのスケジュールを表す有向グラフがあります。ジョブはノードであり、依存関係はエッジです。循環依存関係につながるこのグラフ内の循環のエラー ケースを検出する必要があります。

トーナメントグラフは有向完全グラフと同じですか? また、トーナメント グラフのすべての頂点の辺の数は同じですか?

アプリケーションのユーザー別に分類された項目 (下の青いノード) のリストがあります。カテゴリ自体をグループ化して分類することができます。

結果の構造は有向非巡回グラフ (DAG)として表すことができます。項目はグラフのトポロジの下部にあるシンクであり、上部のカテゴリはソースです。一部のカテゴリは適切に定義されている可能性がありますが、多くはユーザー定義であり、非常に厄介な場合があることに注意してください。

例：

_{(出典: theuprightape.net )}

その構造で、次の操作を実行したいと思います。

• 特定のノードの下にあるすべてのアイテム (シンク) を見つける (ヨーロッパのすべてのアイテム)
• n 個のノードのセット (example.com から SMTP 経由で送信されたすべてのアイテム) のすべてを通過するすべてのパス (存在する場合) を検索します。
• 一連のノードのすべての下にあるすべてのノードを見つけます (交差: 茶色い食べ物)

1 つ目は非常に簡単に見えます。ノードから開始し、考えられるすべてのパスをたどって最下部にアイテムを集めます。しかし、より速いアプローチはありますか？すでに通過したノードを覚えておくと、おそらく不要な繰り返しを避けるのに役立ちますが、さらに最適化はありますか?

2つ目はどうすればいいですか？最初のステップは、セット内の各ノードの高さを決定し、開始するノードを決定してから、セットの残りを含むその下のすべてのパスを見つけることです。しかし、これは最善の (または良い) アプローチですか?

ウィキペディアにリストされているグラフ トラバーサル アルゴリズムはすべて、特定のノードを見つけること、または 2 つのノード間の最短または最も効果的なルートを見つけることに関係しているようです。どちらも私が望んでいるものではないと思いますか、それともこれが私の問題にどのように適用されるかわかりませんでしたか? 他にどこを読むべきですか？

有向グラフのノードのデータ型を簡単に定義できます。

show 関数を使用してグラフをファイルに保存し、read を使用して復元できます。ただし、show はサイクルに対応しません。グラフを保存して復元する簡単な方法はありますか?

複雑なグラフ構造をたどるパスを見つける必要があります。グラフは、次のようなものを使用して作成されます。

これを複雑にしているのは、ノードが以前のノードを参照できることです。例えば、

A -> C -> E -> A

私がする必要があるのは、特定の値を持つノードに到達するまで、ノードを通るパスを表すスタックのリストを取得することです。非常に大きなパスが利用できる可能性があるため、最大のノードを試すことができます。

誰かがこれを構築する方法を持っていますか (または同様のもの)? 私は過去に再帰を行ったことがありますが、何らかの理由でこれについて考えて、完全に脳のおならをしています。私の質問はラムダ式を指定しましたが、ラムダの使用は必ずしも必要ではありません。どんな解決策にも感謝します。

補足:この再帰の質問に対する aku の優れた回答からクラスを取り上げました。以下に示す彼のエレガントなソリューションはツリー構造をトラバースしますが、必要なことを実行するのに十分な柔軟性がないようです (たとえば、循環するパスを却下し、成功したパスを追跡します)。

編集：

以下のコメントと回答からの入力に基づいて、CodeProject で優れたソリューションを見つけました。A* パス検索アルゴリズムを使用します。 ここにリンクがあります。

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

ここでのグラフとは、これらの画像に似たものを意味します。

理想的なソリューションは次のとおりです。

• マネージド コードのみを使用する
• ビットマップ画像への出力を許可する
• WPF 要素への出力を許可する
• ノードのズーム、パン、および再編成をサポートするグラフを表示するためのある種のインタラクティブなサーフェスを含める

また、この種の作業の出発点として使用できる可能性のあるプロジェクトについても興味があります。私が望むものを達成するために何らかの開発が必要な場合は、それに取り組む準備ができています. この目標の最も複雑な部分は、適切な時間枠内でグラフ レイアウトを取得することのようです。

ノードインターフェイス、基本的には各ノードが入力接続で操作を実行し、何かを出力するDAGを実装したいと思います（別のノードに接続できます）

いくつかのサンプルアプリケーション：

• Apples"Shake" -スクリーンショット
• Foundrys"Nuke" -スクリーンショット
• MindNode-スクリーン ショット
• vvvv-スクリーンショット
• QuartzComposer-スクリーンショット

最初の目標として、ノードが2つしかないグラフィカルアプリケーションが必要です。単純に固定数を出力する「数値」と、2つの入力を受け取り、2つの合計を出力する「追加」ノード。

これまでのところ人々が答えているように、私はデータをコードで表現する方法、たとえばPythonのように見える擬似コードでデータを表現する方法について大まかな考えを持っています。

これにカスタムGUIをラップするにはどうすればよいですか？次のようなものですが、手描きは少し少ないです！

どこから始めますか？私は現在、Objective-C / Cocoaでそれを書くことを計画していますが、他の言語の提案を受け入れる以上のことをしています。