2

タスク: igraph ライブラリへの Python インターフェイスを使用して、負の重みを持つ DAG (有向非巡回グラフ) の最短パスを、単一ソース/単一ターゲット セットアップのエッジ/頂点のリストとして見つけます。

試した:ドキュメントで見つけた最も近い一致はget_shortest_paths. ただし、関数を試してみると、次のように返さ れます。 igraph._igraph.InternalError: Error at structural_properties.c:5220: Weight vector must be non-negative, Invalid value 内部的には、関数がダイクストラのアルゴリズムを適用しようとして失敗したようです。同時に、ドキュメントによると、他の最短経路関数 ( shortest_paths、shortest_paths_dijkstra) はアルゴリズムをグラフのプロパティに適応させることができます。

質問:

  • この場合に使用する代替機能はありますか?
  • またはget_shortest_paths、正しい内部アルゴリズムを選択する方法は?
  • または、アルゴリズムを明示的に指定することもできます (R インターフェースのように)

関連する質問:

  • igraph は、グラフが DAG であることを検出し、トポロジー的に並べ替えられたグラフでより高速な最短経路アルゴリズムを使用できますか?
  • このためのカスタム python コードは、汎用の内部 igraph のアルゴリズム (おそらく C++ で記述) の 1 つよりも必然的に遅くなりますか? (|E| は万単位、|V| は千単位)

ありがとう。

PS。Python 2.7、IGraph 0.6.5

4

2 に答える 2

3

get_shortest_pathsigraph_get_shortest_paths_bellman_fordは、基になる C ライブラリに対応する関数がまだないため、負の重みを持つグラフを処理できません。があるigraph_get_shortest_paths_dijkstraので、Python インターフェイスは単純に重みがあるかどうかをチェックし、もしあれば呼び出しを にリダイレクトしigraph_get_shortest_paths_dijkstraますigraph_get_shortest_paths。対照的にshortest_paths、C ライブラリには という名前の関数がigraph_shortest_paths_bellman_fordあり、エッジの重みの少なくとも 1 つが負の場合に Bellman-Ford 実装を呼び出すため、負の重みで動作します。

残念ながら、唯一の方法igraph_get_shortest_paths_bellman_fordは、C レイヤーに実装してから、負の重みを適切に処理するように Python インターフェイスを更新することです。

関連する質問への回答:

  • igraph は、最短パス関連の関数を実行する前に、グラフが DAG であるかどうかをチェックしません。はい、最短パスは DAG でより高速に見つけることができますが、このユースケースは非常にまれであるため、これまでのところ誰も特別なケースを実装することを気にしませんでした.

  • 純粋な Python で記述されたカスタム コードは、C 実装よりも遅くなる可能性がありますが、問題によって異なります。特に Bellman-Ford アルゴリズムを意味する場合、純粋な Python 実装は遅くなる可能性が非常に高くなりますが、それでもグラフには使用できる可能性があります。NetworkXで実装を試すことができます。私の知る限り、NetworkX は純粋な Python であり、何万ものノードとエッジを持つグラフに今でも使用されています。

于 2013-07-26T23:22:31.630 に答える
0

遅いRバージョンもありました。200k のエッジと 30k の頂点に約 20 分かかっていたので、分解しget.shortest.paths()て R (Python ではありません。申し訳ありません) とigraph_get_shortest_paths_bellman_ford()エッジの重みが負のグラフに実装しました。ここで R igraph のフォークを試すことができます。

R 実装から C に切り替えると、100 倍から 1000 倍のスピードアップを経験しました。

于 2015-03-22T23:41:22.580 に答える