22

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

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

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

4

5 に答える 5

25

同様のタスクにグラフツールを使用しました。

Graph-tool は、グラフ (別名ネットワーク) の操作と統計分析のための効率的な Python モジュールです。max-flow アルゴリズムに関する優れたドキュメントもあります。

現在、グラフツールは特定のアルゴリズムをサポートしています:

  • Edmonds-Karp - Edmonds-Karp アルゴリズムを使用して、グラフの最大フローを計算します。
  • 再ラベルのプッシュ - 再ラベルのプッシュ アルゴリズムを使用して、グラフの最大フローを計算します。
  • Boykov Kolmogorov - Boykov-Kolmogorov アルゴリズムを使用して、グラフの最大フローを計算します。

ドキュメントからの例: Boykov-Kolmogorov を使用して maxflow を見つける:

>>> g = gt.load_graph("flow-example.xml.gz") #producing example is in doc
>>> cap = g.edge_properties["cap"]
>>> src, tgt = g.vertex(0), g.vertex(1)
>>> res = gt.boykov_kolmogorov_max_flow(g, src, tgt, cap)
>>> res.a = cap.a - res.a  # the actual flow
>>> max_flow = sum(res[e] for e in tgt.in_edges())
>>> print max_flow
6.92759897841
>>> pos = g.vertex_properties["pos"]
>>> gt.graph_draw(g, pos=pos, pin=True, penwidth=res, output="example-kolmogorov.png")

この例をランダムな有向グラフ (ノード = 4000、頂点 = 23964) で実行したところ、すべてのプロセスにかかった時間はわずか11 秒でした。

代替ライブラリ:

于 2011-08-29T06:37:31.687 に答える
6

それがより速いかどうかはわかりません。それを確認する必要がありますが、networkxを試しましたか? 探している機能を提供しているようで、私の経験からすると、グラフを処理するための非常に使いやすいライブラリです。

于 2011-08-23T14:12:32.777 に答える
1

PyMaxflowとigraphを確認してください。

PyMaxflow は、グラフ構築と maxflow 計算 (一般にグラフ カットとして知られている) のための Python ライブラリです。このライブラリのコアは、Vladimir Kolmogorov による C++ 実装であり、彼のホームページからダウンロードできます。

C++ ライブラリへのラッパーに加えて、PyMaxflow は NumPy 統合、コンピューター ビジョンとグラフィックスで一般的なグラフ レイアウトを高速に構築するためのメソッド、および maxflow メソッド (αβ-swap と α-expansion) を使用する高速エネルギー最小化のためのアルゴリズムの実装を提供します。

igraph は、グラフを作成、操作、および分析するための C ライブラリです。大きなグラフを操作できるように、可能な限り強力 (つまり高速) にすることを目的としています。igraph は、R、Python、Mathematica からも使用できます。

私のテスト ケースでigraphは、 は より 2 ～ 5 倍速く、 よりPyMaxflow6 ～ 10 倍速く、 よりScipy100 ～ 115 倍速いですNetworkx。

于 2021-09-01T13:37:47.137 に答える
1

本当に優れたパフォーマンスを得るには、問題を整数線形計画法として再定式化してみることができます。標準の ILP ツールのいずれでも、十分以上のパフォーマンスが得られるはずです。

ウィキペディアには、そのような商用ツールとオープン ソースツールの両方の優れたリストが含まれており、その多くには Python バインディングが含まれているようです。最もよく知られているのはCPLEXとlp_solveです。

私はここ数年、lp_solve を個人的にかなり頻繁に使用してきましたが、入力をプレーン テキスト ファイルとして lp_solve に書き込み、シェルを使用して lp_solve を呼び出すだけで十分であることがわかりました。振り返ってみると、lp_solve への公式の python バインディングを機能させるために、もう少し労力を費やすべきだったでしょう。

于 2011-08-29T11:18:24.960 に答える