私はグーグルアプリエンジンで簡単なグラフ検索を実装しようとしています。これは私の初めての gae プロジェクトと python プロジェクト、そしてグラフ検索です! やって学ぶことです（おそらく間違っています）。ndb データベースとしてアップロードされた頂点間の接続の大きな cvs ファイルがあります。
class Connection(ndb.Model):
vertexid = ndb.StringProperty()
connectedto = ndb.StringProperty()
約 8000 の頂点があり、それぞれが他のいくつかの頂点に接続されているため、合計で約 14,000 の接続があるため、接続 ndb には 14,000 のエンティティがあります。すでに、各頂点を単一のエンティティとして接続変数を繰り返して保存する方が効率的だと思いますが、それを行うために cvs データを適切にアップロードする方法がわかりません。その場合も、ID をキーとして使用し、以下のフェッチの代わりに取得を使用できます。これにより速度が向上する可能性があります。
とにかく、私はこの投稿のいくつかのpythonコードに基づいて、幅優先検索を行っています。幅優先検索でパスをトレースする方法は? 、だから私はそれを使用し、それを少しいじって動作させました:
def bfs(origin, destination):
queue = []
# push the first path into the queue
queue.append(str(origin.vertexid))
count = 0
while queue:
# get the first path from the queue
if len(queue) ==1:
path = queue.pop(0)
node = path
else:
path = queue.pop(0)
node=path[-1]
# get the last node from the path
# path found
if node == destination.vertexid:
return path
if count>21000:
return count
# enumerate all adjacent nodes, construct a new path and push it into the queue
nodeconns=Connection.query(Connection.vertexid == node).fetch(10)
for nodeconn in nodeconns:
count = count+1
new_path = []
new_path.append(path)
new_path.append(str(nodeconn.connectedto))
queue.append(new_path)
とにかく、出発地と目的地が互いに近い (6 つまたは 7 つの接続が離れている) 場合は機能しますが、頂点が遠く離れている場合は非常にうまくスケーリングしないようです。
これは、データストアからすべてのデータを読み取る必要があるためですか? 上記のように、21000回の試行の上限があっても非常に遅い理由がよくわかりません.SSDラップトップでは、非常に離れた起点と終点でタイムアウトするまでに50秒ほどかかります（カウント> 21,000）。
進行中のndbデータベースへのすべての読み取りと組み合わせると、これはオンラインで実行するのに適していません（私はローカルでのみ実行しています）。
だから...私の質問は、上記のアルゴリズムに根本的な欠陥があると思いますか? Google アプリ エンジンで ndb に基づいてグラフ検索を実行するのはばかげた考えですか? グラフを表現するためのより賢明な方法はありますか? 多分私のためにこれを行うことができるいくつかの既存のパッケージがありますか？（ダイクストラのアルゴリズムのコードをいくつか見つけましたが、それを自分のデータとインターフェースする方法がよくわかりません）
ありがとう！！