10


5

大きくて動的な無向グラフをgoogle appengineに保存する必要があります。これを行うための最良の方法は何ですか? グラフ表現は、(ページ上にレンダリングするための)一連の頂点と特定の頂点からのすべてのリンクの迅速な引き出し、およびグラフ全体にわたるパス検索をサポートする必要があります(ただし、最適なパスは実際には必要ありませんが、かなり適切です)。良いもの)

私の話題:私の考えでは、最も明白な方法は、頂点モデルと2つの頂点を参照するエッジモデルを持つことです。しかし、それはすべての操作に対してひどくたくさんのクエリを使うことになるようです。もっと良い方法があります(リンク情報をどうにかして各頂点に構築します)。

3 回答


8


これが最も簡単な方法です:

クラスVertex(db.Model):outedges = db.ListProperty(db.Key)#その他の頂点に関する情報はこちら

これで、クエリをまったく行わずにグラフを調べることができます。関連する頂点を取得するには、1つ以上のキーでdb.getを呼び出すだけです。

#最初に参照される頂点vertex2 = db.get(vertex1.outedges [0])を取得します

#参照されている頂点をすべて取得するvertices = db.get(vertex1.outedges)


2


頂点/リンクの数によっては、たくさんの新しいエンティティを作成するのではなく、単にリストを使用したい場合があります。 Google IO 2009のこのビデオの後半に記載されている友達グラフの問題を確認します。

頂点の数が十分に多いと思われる場合は、接続を表すリストを含むVertexモデルを作成するだけです。


0


GoogleのAppエンジンを使用していることを考えると、情報を別々のテーブルに格納しておくのが最善です。

1つは頂点用、もう1つは頂点からのリンク用(すでに述べたとおり)、もう1つはパスが既に事前計算されているものです。

あなたが保存する情報が非正規化されているのでGAEは最もうまくいきます。