問題タブ [directed-graph]

大規模で動的な無向グラフを Google appengine に保存する必要があります。これを行う最善の方法は何ですか? グラフ表現は、一連の頂点 (ページ上でのレンダリング用) と特定の頂点からのすべてのリンクの迅速な引き出し、およびグラフ全体のパスファインディングをサポートできなければなりません (ただし、最適なパスは実際には必要ありません。良いもの）

この件に関する私の考え: 最も明白な方法は、頂点モデルと、2 つの頂点を参照するエッジ モデルを使用することですが、それでは、すべての操作に対して非常に多くのクエリを使用することになるように思えます。より良い方法があります（リンク情報を各頂点に何らかの方法で構築するかもしれません）

Erlangの有向グラフモジュールは、状態を変更することで私を驚かせました。

Erlangで他のデータ構造モジュールを処理する場合、たとえば、渡されたデータ構造のインスタンスであるsetsモジュールは変更されません。この関数は、変更された新しいバージョンを返します。

これは、有向グラフモジュールを処理するときの動作ではありません。

まず、この点で有向グラフラ​​イブラリが異なるのはなぜですか？

次に、さらに重要なことに、digraphモジュールは既存のバインディングに対して新しい状態をどのように追加しますか？

状態は、既存の変更されていないバインディングGを使用してdigraphモジュールが識別している別のプロセスに格納されていると思います。これは本当ですか？または、バインディングに関連付けられた状態を変更する他の方法はありますか？

有向グラフが強く接続されているかどうか、つまり、他のノードがすべてのノードに到達できるかどうかを確認する必要があります（必ずしも直接エッジを経由する必要はありません）。

これを行う1つの方法は、すべてのノードでDFSとBFSを実行し、他のすべてのノードがまだ到達可能であることを確認することです。

それを行うためのより良いアプローチはありますか？

いくつかの条件が満たされるまでエッジを 1 つずつ削除するグラフ構造があります。私の脳は完全に停止しており、エッジを削除するとグラフが 2 つ以上のグラフに分割されるかどうかを効率的に検出する方法が見つかりません。

ブルートフォースの解決策は、ランダムなノードからすべてのノードに到達できるまでbfsを実行することですが、大きなグラフでは時間がかかりすぎます...

何か案は？

編集:少し検索した後、私がやろうとしていることは、エッジが「ブリッジ」であるかどうかを見つける必要があるフルーリーのアルゴリズムに非常に似ているようです。

のDOT言語でGraphViz、依存関係図を表現しようとしています。コンテナ内にノードを配置し、ノードやコンテナを他のノードやコンテナに依存させることができる必要があります。

subgraphコンテナを表すために使用しています。ノードのリンクは問題なく機能しますが、サブグラフを接続する方法がわかりません。

cluster_1以下のプログラムを考えると、矢印を使用して接続できる必要がありますが、cluster_2試したものはすべて、クラスターを接続する代わりに新しいノードを作成します。

ここにツリーがあります：

1. ルートは1つになります。

2. 各ツリー ノードには、0 個以上の子があります。

3. 2 つのノードが同じ子を指すことができます。ノード A とノード B の両方に子 C があるとします。

ただし、禁止事項として、

ノード A はノード B の子孫であり、ノード B はノード A の子孫です。

禁止されているケースの 1 つは、

ノード A には子ノード C とノード D があり、

ノード C と D の両方に子ノード E があり、

ノード E には A の子があります。

問題は、この円を最速で決定する方法です。

更新:これは、有向グラフで任意のサイクルを見つけることだと認識しています。たった今、Tarjan のアルゴリズムに似た解決策を考え出すことができました。

コメントありがとうございます。

開始ノードを選択してからDFSを介して続行することにより、重み付けされていない非巡回有向グラフをトラバースする特定のグラフアルゴリズムがあるかどうか知りたいです。検索されていない先行ノードがあるノードが検出された場合、開始するすべてのパスが探索されるまで、着信パスをバックトラックする必要があります。

グラフアルゴリズムのウィキペディアカテゴリを見つけましたが、ここにはアルゴリズムの小さな海があり、それらのほとんどに精通していません。

編集：例：グラフ{AB、EB、BC、BD}が与えられた場合、{A、B、E、B、C、D}としてトラバースするか、{A、B、E、C、D}として一意の順序でトラバースします。BFSやDFSとは異なり、このアルゴリズムは、最初の開始ノードのすべてのパスが使い果たされた場合に、新しい開始ノードで再開する必要がないことに注意してください。

私は、問題の1つが、有向グラフG =（V、E）が単一に接続されているかどうかを確認するアルゴリズムを導出するように要求する割り当てに取り組んでいます（すべての異なる頂点uに対してuからvへの単純なパスが最大で1つあります。 Vのv。

もちろん、ブルートフォースチェックを行うこともできます。これは私が現在行っていることですが、もっと効率的な方法があるかどうかを知りたいと思います。誰かが私を正しい方向に向けることができますか？

有向グラフが循環的かどうかをどのように検出できますか? 幅優先探索をしようと思ったのですが、よくわかりません。何か案は？