問題タブ [directed-graph]

次のようなトーナメント グラフがあるとします。ヘルプ/説明をいただければ幸いです。

有向グラフを作成するために利用できるライブラリまたはクラスはありますか？エッジも容量をサポートしていますか？（または、自分で作成する必要がありますか？）

最近学んだ最大フローアルゴリズムをテストしたい

有向非巡回グラフGのソース頂点Vからすべての可能な頂点へのすべての可能なパスを見つける関数を実装したいと思います。

今はパフォーマンスは関係ありません。アルゴリズムを理解したいだけです。深さ優先探索アルゴリズムの定義を読みましたが、何をすべきか完全には理解していません。

方法がわからないため、ここで提供する完成したコードはありません。

• 結果を保存します（A-> B-> C->とともに、A->BおよびA->B-> Cも保存する必要があります）。
• グラフを表す（有向グラフ？タプルのリスト？）;
• 使用する再帰の数（隣接する各頂点で機能しますか？）。

Erlangの有向非巡回グラフで1つの特定のソース頂点を形成するすべての可能なパスを見つけるにはどうすればよいですか？

UPD：これまでの回答に基づいて、グラフの定義を再定義する必要があります。これは非循環グラフです。私の再帰関数がサイクルにヒットした場合、それは無期限のループであることを私は知っています。これを回避するために、現在の頂点が結果のパスのリストに含まれているかどうかを確認できます。含まれている場合は、トラバースを停止してパスを返します。

UPD2：考えさせられるコメントをありがとう！はい、1つのソース頂点から他のすべての頂点へのループがないすべての単純なパスを見つける必要があります。

このようなグラフでは：

ソース頂点Aを使用すると、アルゴリズムは次のパスを見つける必要があります。

• A、B
• A、B、C
• あいうえお
• 広告
• A、D、C
• A、D、C、B

次のコードは機能しますが、頂点が20を超えるグラフでは使用できません（再帰に問題があると思います。メモリが多すぎて、終了しません）。

UPD3：

問題は、通常の深さ優先探索アルゴリズムが最初にパスの1つ（（A、B、C、D）または（A、D、C、B））に移動し、2番目のパスには移動しないことです。

いずれの場合も、これが唯一のパスになります。たとえば、通常のDFSが（A、B、C、D）からバックトラックすると、Aに戻り、D（Aの2番目のネイバー）にアクセスしたかどうかを確認します。また、通常のDFSは各頂点のグローバル状態を維持するため、Dは「訪問済み」状態になります。

したがって、再帰に依存する状態を導入する必要があります。（A、B、C、D）からAまでバックトラックする場合、結果のリストに（A、B、C、D）が含まれている必要があり、アルゴリズムの最初の時点で、Dが未訪問としてマークされています。

末尾再帰のソリューションを最適化しようとしましたが、それでもアルゴリズムの実行時間は実行不可能です。頂点ごとに3つのエッジを持つ16の頂点の小さなグラフをトラバースするのに約4秒かかります。

これを許容可能な時間で実行するためのアイデアはありますか？

これらすべてのルート頂点間のルート頂点のセットが与えられた有向グラフで最小スパニング ツリー (最適分岐) を計算するアルゴリズムがあるかどうかを知りたいのですが、グラフ内の 1 つのルート頂点と他のすべての頂点だけではありません。 .

ルート頂点のセット [1,4,6] と、次の図のようなグラフ G があるとします。

...アルゴリズムは、同じ画像の緑色のサブグラフのようなものを返す必要があります。

アルゴリズムに提供されたすべてのルート頂点を接続するような MST を取得したいと思います。私は、自称アルゴリズムの結果は、すべてのルート頂点と G の他のいくつかの頂点を含むグラフ G のサブグラフであると考える傾向があります。

ノート：

1. 有向グラフの MST がないことは知っていますが、Chu–Liu/Edmonds アルゴリズムはあります。
2. このようなアルゴリズムの結果 (実際に可能であれば) は、グラフのいくつかの頂点とすべてのルート頂点を含む最適な分岐を返すと思います。

と の 2 つの頂点リストがVありSます。

V可能なすべての有向グラフをandから生成したいと思いますS。各頂点にVは 1 つのアウト エッジと 1 つのイン エッジしかなく、各頂点にSは任意の数のイン エッジとアウト エッジを含めることができます。V結果の各グラフには、と からのすべての頂点が正確に含まれている必要がありますS。結果には、接続されたグラフと切断されたグラフの両方を含めることができます。

最初は powerset 関連の問題だと思っていましたが、powerset には 1 つの要素だけを含む可能性のある他の多くのセットがあります (それらは必要ありません)。

私の現在の戦略は次のとおりです。

• から頂点間のすべてのペアを見つけV、に追加しPairsます。
• から頂点間のすべてのペアを見つけS、に追加しPairsます。
• Vとからの頂点間のすべてのペアを見つけS、 に追加しPairsます。
• V各サブセットがv最初の位置に頂点のインスタンスを 1 つだけ持ち、2 番目の位置に頂点のインスタンスを 1 つ持ち、任意の位置からv任意の頂点の任意の数のインスタンスを持つような方法で、以上のサイズのペアのサブセットを生成する.sS

これが正しいかどうか確信が持てないので、アイデアについて知りたいです。

たぶん、完全に接続されたグラフを作成しG、VそれからS何らかの方法でサブグラフを抽出できますか? (おそらく digraph:utils の助けを借りて)

PS私はこれをErlangで解決しようとしています.Erlangは私が使用していて、現在積極的に学んでいる言語だからです. しかし、Java、Ruby、または疑似コードが回答に含まれていることを嬉しく思います。

私はこれまでにこの論文を見つけました。時代遅れですか？より速く、より良い実装はありますか？

ちなみに、ウィキペディアによると、無向グラフにはn^n-2のスパニングツリーが存在する可能性があります。有向グラフにはスパニングツリーをいくつ含めることができますか？

完全に接続された有向グラフがあるとしましょうG。頂点は[a,b,c]. 各頂点間に両方向のエッジがあります。

開始頂点aを指定すると、グラフをすべての方向にトラバースし、パスに既にある頂点にヒットした場合にのみパスを保存したいと思います。

したがって、関数full_paths(a,G)は次を返す必要があります。

[{a,b}]またはのような「不完全な」結果は必要ありません[{a,b}, {b,c}]。最初の結果に既に含まれているからです。

G のパワーセットを生成し、特定のサイズの結果を除外する以外に、それを行う方法はありますか?

どうすればこれを計算できますか？

編集：イーサンが指摘したように、これは深さ優先検索法で解決できますが、残念ながら、バックトラックする前にパスを保存するように変更する方法がわかりません（Ruby Gratrを使用してアルゴリズムを実装します）

プログラムをテストすることになっている先生からいくつかの入力ファイルを受け取りました。タスクは、ファイルから読み取り、有向グラフを作成し、出力を印刷することです。しかし、サイクルがある場合は、プログラムを終了することになっています。

house1とhouse2という名前のファイルがいくつかあります。ファイルhouse1にはサイクルはありませんが、house2にはサイクルがあります。しかし、なぜ私のプログラムがそのサイクルを見つけられないのか理解できません。ここに私はすべてのコードを持っています、そして私がどこを見るべきかを言う助けはありがたいです:)

私は現在、有向ハイパーグラフ フレームワークを使用して動的プログラムの k-best ソリューションを列挙するプロジェクトに取り組んでいます。私の現在の実装 (Python で) はうまく機能しますが、かなり遅いです。このアルゴリズムは、多くのタイトなループとかなりの再帰を実行します。C++ 実装を使用して大幅な速度向上を実現できると本当に思います。ただし、かなりの検索を行った後、C++ でハイパーグラフの実装を提供するライブラリを見つけることができませんでした (特に有向ハイパーグラフ -- しかし、無向ハイパーグラフのライブラリさえ見つけることができませんでした)。そのようなライブラリを知っている人はいますか？数年前にブーストにハイパーグラフをサポートするという GSoC の提案があったようですが、実際にはうまくいかなかったようです。

頂点とエッジGを持つ完全に接続された有向グラフがあるとしましょう。NM

グラフにはいくつのエッジがありますか？それM = N^2ですか？

1つの頂点を取得し、「深さ優先探索」方式でその隣接頂点を訪問し、ループを回避すると、非循環的な単純なパスがいくつ取得されますか？

たとえば、4つの頂点のグラフの頂点1から開始する場合、パスは次のようになります。

頂点のあるグラフの場合はそれN!以上ですか？Nこれを一般化し、使用可能な式を導き出す方法を見つけることができませんでした。