15

巨大なグラフ内のノード間の最短経路をリアルタイムで見つける方法を探しています。数十万の頂点と数百万のエッジがあります。この質問は以前に尋ねられたことを知っており、答えは幅優先検索を使用することだと思いますが、それを実装するために使用できるソフトウェアを知りたいと思っています。たとえば、無向グラフで bfs を実行するためのライブラリ (python バインディング付き!) が既に存在する場合、それは完全に完璧です。

4

7 に答える 7

19

python-グラフ

追加した：

OPの順番の問題でpygraphの性能がどうなのか気になったので、おもちゃのプログラムを作ってみました。問題のわずかに小さいバージョンの出力を次に示します。

$ python2.6 biggraph.py 4 6
biggraph generate 10000 nodes     00:00:00
biggraph generate 1000000 edges   00:00:00
biggraph add edges                00:00:05
biggraph Dijkstra                 00:01:32
biggraph shortest_path done       00:04:15
step: 1915 2
step: 0 1
biggraph walk done                00:04:15
path: [9999, 1915, 0]

10k ノードと 1M エッジにはそれほど悪くありません。Dijkstra が pygraph によって計算される方法は、1 つのターゲット (任意にノード 0 であり、グラフ内で特権的な位置を保持しない) に関連する各ノードのすべてのスパニング ツリーの辞書を生成することに注意することが重要です。したがって、計算に 3.75 分かかった解は、実際には「すべてのノードからターゲットまでの最短経路は?」に対する答えをもたらしました。確かにshortest_path、答えをたどることは単なる辞書の検索であり、本質的に時間はかかりませんでした。事前に計算されたエッジをグラフに追加すると、約 1.5 分とかなりコストがかかることにも注意してください。これらのタイミングは、複数の実行で一貫しています。

プロセスは適切にスケーリングされていると言いたいのですが、 15 時間以上実行されているbiggraph 5 6アイドル状態のコンピューター (Athlon 64、プロセッサあたり 4800 BogoMIPS、すべてコア内) で待機しています。少なくともメモリ使用量は約 0.5GB で安定しています。結果は次のとおりです。

biggraph generate 100000 nodes    00:00:00
biggraph generate 1000000 edges   00:00:00
biggraph add edges                00:00:07
biggraph Dijkstra                 00:01:27
biggraph shortest_path done       00:23:44
step: 48437 4
step: 66200 3
step: 83824 2
step: 0 1
biggraph walk done                00:23:44
path: [99999, 48437, 66200, 83824, 0]

それは長い時間ですが、重い計算でもありました (結果を漬けておけばよかったと心から思います)。好奇心旺盛な人のためのコードは次のとおりです。

#!/usr/bin/python

import pygraph.classes.graph
import pygraph.algorithms
import pygraph.algorithms.minmax
import time
import random
import sys

if len(sys.argv) != 3:
    print ('usage %s: node_exponent edge_exponent' % sys.argv[0])
    sys.exit(1)

nnodes = 10**int(sys.argv[1])
nedges = 10**int(sys.argv[2])

start_time = time.clock()
def timestamp(s):
    t = time.gmtime(time.clock() - start_time)
    print 'biggraph', s.ljust(24), time.strftime('%H:%M:%S', t)

timestamp('generate %d nodes' % nnodes)
bg = pygraph.classes.graph.graph()
bg.add_nodes(xrange(nnodes))

timestamp('generate %d edges' % nedges)
edges = set()
while len(edges) < nedges:
    left, right = random.randrange(nnodes), random.randrange(nnodes)
    if left == right:
        continue
    elif left > right:
        left, right = right, left
    edges.add((left, right))

timestamp('add edges')
for edge in edges:
    bg.add_edge(edge)

timestamp("Dijkstra")
target = 0
span, dist = pygraph.algorithms.minmax.shortest_path(bg, target)
timestamp('shortest_path done')

# the paths from any node to target is in dict span, let's
# pick any arbitrary node (the last one) and walk to the
# target from there, the associated distance will decrease
# monotonically
lastnode = nnodes - 1
path = []
while lastnode != target:
    nextnode = span[lastnode]
    print 'step:', nextnode, dist[lastnode]
    assert nextnode in bg.neighbors(lastnode)
    path.append(lastnode)
    lastnode = nextnode
path.append(target)
timestamp('walk done')
print 'path:', path
于 2010-06-14T15:54:48.700 に答える
11

大きなグラフの場合は、igraphの Python インターフェースを試してください。そのコアは C で実装されているため、数百万の頂点とエッジを持つグラフを比較的簡単に処理できます。BFS 実装 (他のアルゴリズムの中でも) が含まれており、ダイクストラのアルゴリズムと加重グラフ用の Bellman-Ford アルゴリズムも含まれています。

「リアルタイム性」に関しては、いくつかの簡単なテストも行いました。

from igraph import *
from random import randint
import time

def test_shortest_path(graph, tries=1000):
    t1 = time.time()
    for _ in xrange(tries):
        v1 = randint(0, graph.vcount()-1)
        v2 = randint(0, graph.vcount()-1)
        sp = graph.get_shortest_paths(v1, v2)
    t2 = time.time()
    return (t2-t1)/tries

>>> print test_shortest_path(Graph.Barabasi(100000, 100))     
0.010035698396
>>> print test_shortest_path(Graph.GRG(1000000, 0.002))
0.413572219742

上記のコード スニペットによると、100K の頂点と 10M のエッジ (10M = 100K * 100) を持つ小さな世界のグラフで、2 つの特定の頂点間の最短経路を見つけるには、平均で約 0.01003 秒かかります (1000 回の試行の平均)。これは最初のテスト ケースであり、ネットワークのサイズに比べて直径が小さいことが知られているソーシャル ネットワーク データまたはその他のネットワークを使用している場合、これは妥当な見積もりです。2 番目のテストは、100 万点が 2D 平面にランダムにドロップされ、距離が 0.002 未満の場合に 2 つの点が接続される幾何学的ランダム グラフであり、約 1M の頂点と 6.5M のエッジを持つグラフになります。この場合、最短パスの計算には時間がかかりますが (パス自体が長いため)、平均で 0.41357 秒とかなりリアルタイムに近くなっています。

免責事項: 私はigraphの作成者の 1 人です。

于 2010-06-14T20:53:40.790 に答える
3

そのような大きなグラフ (およびパフォーマンスの制約がある) の場合、C++ で記述されているため、 Boost Graph Libraryが必要になるでしょう。探しているPython バインディングが含まれています。

于 2010-06-14T16:26:21.047 に答える
3

それは、ノードとエッジにアタッチしたメタデータの量によって異なります。比較的小さい場合、そのサイズのグラフはメモリに収まります。そのため、純粋な優れた NetworkX パッケージ (特にhttp://networkx.lanl.gov/reference/generated/networkx.shortest_path.htmlを参照) をお勧めします。パイソン。

何百万ものノード、大規模なメタデータ、トランザクション、ディスク ストレージなどを処理できるより堅牢なソリューションとして、私は neo4j ( http://www.neo4j.org/ ) でうまくいきました。Java で書かれていますが、Python バインディングを持っているか、REST サーバーとして実行できます。それを使ったトラバーサルは少しトリッキーですが、悪くはありません。

于 2010-06-14T20:37:41.443 に答える
1

無向グラフの BFS は、わずか 25 行のコードです。ライブラリは必要ありません。ウィキペディアの記事のサンプル コードを確認してください。

于 2010-06-14T15:54:27.297 に答える
0

持っている追加情報の種類によっては、A*が非常に効率的である場合があります。特に、ノードが与えられた場合、そのノードから目標までのコストの見積もりを計算できる場合、A*は最適に効率的です。

于 2010-06-15T02:06:49.120 に答える
0

neo4jに保存

Dijkstra、A*、「最短パス」アルゴリズムが含まれています。

于 2013-02-15T06:22:53.877 に答える