問題タブ [max-flow]

有向グラフで最大フローと最小カットを見つけるアルゴリズムの高速実装を備えた、信頼性が高く十分に文書化された Python ライブラリはありますか?

python-graph のpygraph.algorithms.minmax.maximum_flowは問題を解決しますが、非常に遅いです: 4000 ノードと 11000 エッジのような有向グラフで最大フローと最小カットを見つけるには 1 分以上かかります。少なくとも一桁速いものを探しています。

報奨金 : この質問に対して報奨金を提供して、この質問が行われた時点から状況が変わったかどうかを確認します。お勧めの図書館で個人的な経験がある場合は、ボーナス ポイントを獲得できます。

グラフに ford-fulkerson 法を適用して最大フローを見つける方法について、順を追って説明しているサイトを教えてください。

よろしくお願いします。

グラフの最小カットを見つける必要があります。フロー ネットワークについて読んできましたが、Ford-Fulkerson、push-relabel などの最大フロー アルゴリズムしか見つかりませんでした。最大フローアルゴリズムを使用したグラフの最小カット? どのように？

これまでに見つけた最良の情報は、「飽和」エッジ、つまりフローが容量に等しいエッジを見つけた場合、それらのエッジは最小カットに対応するということです。本当？私には 100% 正しいとは思えません。最小カットのすべてのエッジが飽和するのは事実ですが、最小カットの「パス」から外れている飽和エッジもあると思います。

制御フローグラフでいくつかのデータを維持する必要があるプログラムを作成する必要があります。実行時に最大フローを計算する必要があります。

グラフを処理するためのライブラリがいくつかあり、ほとんどすべての古典的なアルゴリズムを実装していることは知っていますが、私の問題は、グラフが動的であるということです。つまり、実行時に進化します。すべての進化の後、新しい最大フローを再計算する必要があります。

進化は次のいずれかです。

• エッジを追加する
• エッジの容量を増やす

再計算する必要があるのは、ソースSからそのステップで変更されたエッジの宛先ノードへの最大フローです。例えば：

私のグラフの進化の非常に具体的な性質を考慮すると、どのアルゴリズム/ライブラリがより時間のパフォーマンスが高いでしょうか？つまり、各ステップでグラフが前のステップ（1つのエッジを除く）とほぼ同じであるという事実を考慮すると、前の計算の中間結果を効率的に再利用できるアルゴリズムはありますか？

目的地が毎回違うという事実が問題を少し難しくしていることを私は知っています....各ステップでO（VE ^ 2）よりも優れている方法について何か考えはありますか？

そして、私がこの可能な進化も考慮した場合はどうなりますか？

• ノード（およびそのノードとの間のすべての着信/発信エッジ）の削除

私はすべての標準的なアルゴリズムを理解し、それらをどのように変更できるかを考えようとしましたが、グラフ理論が私の分野ではないため、悲惨なことに失敗しました...

どんな助けでもありがたいです。ありがとう。

動的グラフの最大フローを計算するための高速アルゴリズムを探しています（グラフに関連するエッジを持つノードを追加/削除）。つまり、Gに最大フローがあり、関連するエッジで新しいノードが追加/削除されました。新しいグラフの最大フローを再計算するのは好きではありません。実際、このグラフには以前に利用可能な結果を​​使用したいと思います。

時間/メモリの消費量が少ない前処理が適切に使用されます。

最も簡単なアイデアは、フローを再計算することです。

もう1つの簡単なアイデアは、これまでのmaxflow計算で使用したすべての拡張パスを保存し、頂点を追加するために、ソースから開始して宛先に移動するv単純なパス（前のステップで更新された容量グラフ）を見つけることができますが、v問題は、このパスは単純である必要があることです。この場合、O（n * E）よりも優れたものを見つけることができませんでした。（それが1つのパスであるか、パスが互いに素である場合、これはO（n + E）で実行できますが、そうではありません）。

また、上記のノードを削除するためのアイデアは機能しません。

また、私の質問は、動的エッジの追加/削除を調べる別の質問とは関係ありません。

CLRS から次の補題を理解するのが困難です。

G をフロー ネットワーク、s と t をソース ノードとシンク ノード、f を s から t へのプリフロー、h を G の高さ関数とします。この場合、残差グラフ G _fには s から t への拡張パスはありません。 .

どうしてこれなの？

私のアルゴリズムの一部では、整数の容量を持つネットワークで最大フローを計算する必要があります。boost::edmonds_karp_max_flow アルゴリズムを使用して最大フローを見つけたい。

ドキュメントを読んでみましたが、これまで BGL を使用したことがなかったので、非常に困難でした。次のようにグラフを作成しました。ここでは、グラフのエッジの容量として の重み属性をEdge使用する必要があります。

私の目標は、次の関数を書くことです

誰かがこの機能を実装する方法の例を教えてもらえますか?

Edmond Karp アルゴリズムを実装しますが、それは正しくないようで、正しいフローが得られません。次のグラフと 4 から 8 までのフローを検討してください。

アルゴリズムは次のように実行されます。

最初に 4→1→8 を見つけ、次に 4→5→8 を見つけ、その後 4→1→6→8 を見つけます

そして、3 番目のパスは間違っていると思います。このパスを使用すると、6 → 8 のフローが使用できず (使用されているため)、実際には 4 → 5 → 6 → 8 のフローが使用できないからです。

実際、4→5→6→8、次に 4→1→3→7→8、次に 4→1→3→7→8 を選択すると、より良いフローを得ることができます(40)。

ウィキのサンプルコードからアルゴリズムを実装しました。有効なパスは使用できないと思います。実際、この貪欲な選択は間違っています。

私が間違っている？

コードは次のとおりです (c# では、しきい値は 0 で、アルゴリズムには影響しません)。

元の最大フローがわかっているグラフで最大フローを見つける線形アルゴリズム (O(|V| + |E|) を見つける必要がありますが、各エッジの容量は 1 増加します。

一般化された（非純粋な）ネットワークでゲインを伴う最大フローを解決するための、できれば実装を伴う、効率的で公開されているアルゴリズムを見つけようとしています。すべての乗数、容量、およびフロー値はゼロ以外の整数です。

そのようなアルゴリズムは存在しますか、それともこの問題は多項式時間では解決できませんか?