GoogleのAppEngineのデータストア内の有向グラフを記憶します
-
19-09-2019 - |
質問
私はGoogleのAppEngineの中で大規模かつダイナミックな無向グラフを格納する必要があり、これを行うための最善の方法は何ですか? グラフ表現はちょうどかなり、最適なパスが本当に必要ないが(グラフ全体に及び、特定の頂点からのすべてのリンク、および経路探索(ページ上でレンダリングするために)頂点の集合を引き出す急速にサポートすることができなければなりません良い1)
件名に私の考え: 最も明白な方法は、頂点のモデルを持っていることであり、すべての操作のためのクエリの非常に多くを使用して終了するために起こっているように2つの頂点を参照するエッジモデルは、しかし、それが鳴り、より良い方法は、(存在する場合、私は思ったんだけど多分)何とか各頂点へのリンク情報を構築する
解決
ここでは最も簡単な方法です
class Vertex(db.Model):
outedges = db.ListProperty(db.Key)
# Other information about the vertex here
これがすべてで任意のクエリせずにグラフを探索することができます - ちょうど、関連する頂点を取得するために、1つのまたは複数のキーにdb.get呼び出します:
# Get the first referenced vertex
vertex2 = db.get(vertex1.outedges[0])
# Get all referenced vertices
vertices = db.get(vertex1.outedges)
他のヒント
あなただけの新しいエンティティの束を作成するのではなく、リストを使用する場合があります頂点/リンクの数に応じて。グーグルIO 2009からこのビデオの後半で説明した友人のグラフの問題を確認してください:ます。http:// www.youtube.com/watch?v=AgaL6NGpkB8する
あなたが考える場合は、頂点の数はあなただけの接続を表しリストと頂点モデルを作成することができ、十分に高いです。
あなたが別々のテーブルに情報を保存した場合、それが最善だろうGoogleのアプリケーションエンジンを使用している考えます
の頂点、頂点からのリンクのための1つの(すでに述べたように)パスが既に事前に計算されている追加のいずれかの一つの
あなたはそれ上の任意の計算を行う必要はありませんので、あなたが保存した情報が非正規化された場合は、GAEが最も適しています。