10

私はPythonコーディングが初めてで、非常に大きなグラフの開始ノードと終了ノードの間のすべてのパスをすばやく見つけるアルゴリズムを探しています-約1000ノードと10,000エッジを持つグラフとします。開始ノードから終了ノードまで実際に存在するパスの数は少なく、10 以下です。質問をもう少し文脈化するのを助けるために、ソーシャルネットワークを考えてみてください.1000人の友達がいて、高校の親友が大学のルームメイトとつながる方法がいくつあるか知りたいとしたら、高校の親友は 200 人の高校の友達全員とつながっています。これらのパスがルームメイトにつながることはないからです。この python コードでやりたいことは、2 人の友人の間に存在するパスをすばやくサブセット化し、基本的にすべての「ノイズ」を取り除くことです。

いくつかのコード例を実装しようとしましたが、それらはすべて小さくて単純なグラフでうまく機能します。しかし、それらを大規模なグラフ分析に組み込もうとすると、すべてが役に立たなくなるまでに時間がかかりすぎます。

調査する方法（つまり、networkxですでに作成されているもの、またはスタックと再帰の使用に関する情報など）、実装するコード例、または追求するPython以外の他のルートについて提案はありますか？私はPythonの初心者です。

4

2 に答える 2

4

2 つのノード間のすべての単純な (ノードの繰り返しがない) パスが必要ですか? NetworkX には、深さ優先検索に基づく機能があります。http://networkx.github.com/documentation/development/reference/generated/networkx.algorithms.simple_paths.all_simple_paths.htmlを参照してください。

そこからの例は、単純なパスの数が大きくなる可能性があることを示しています。

>>> import networkx as nx
>>> G = nx.complete_graph(4)
>>> for path in nx.all_simple_paths(G, source=0, target=3):
...     print(path)
...
[0, 1, 2, 3]
[0, 1, 3]
[0, 2, 1, 3]
[0, 2, 3]
[0, 3]
于 2013-02-08T19:12:28.390 に答える
1

個人的には、これにはグラフ データベースを使用することをお勧めします。Neo4j または Rexter が思い浮かびます。

Python からこれらにアクセスする場合、利用可能なライブラリがいくつかあります。

これらの高速でスケーラブルな Python バージョンを作成することは不可能ではありませんが、私の知る限り、現時点ではありません。

于 2013-02-06T23:43:03.150 に答える