9

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

この件に関する私の考え: 最も明白な方法は、頂点モデルと、2 つの頂点を参照するエッジ モデルを使用することですが、それでは、すべての操作に対して非常に多くのクエリを使用することになるように思えます。より良い方法があります（リンク情報を各頂点に何らかの方法で構築するかもしれません）

4

3 に答える 3

7

最も簡単な方法は次のとおりです。

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)
于 2009-07-27T16:24:58.330 に答える
2

頂点/リンクの数によっては、一連の新しいエンティティを作成する代わりに、リストを使用したい場合があります。Google IO 2009 のビデオの後半で説明されているフレンズ グラフの問題を確認してください: http://www.youtube.com/watch?v=AgaL6NGpkB8

頂点の数が十分に多いと思われる場合は、接続を表すリストを使用して頂点モデルを作成できます。

于 2009-07-27T16:30:26.167 に答える
0

Google アプリ エンジンを使用していることを考えると、情報を別のテーブルに保存するのが最善です。

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

GAE は、保存する情報が非正規化されている場合に最適に機能するため、計算を行う必要はありません。

于 2009-07-27T10:38:05.547 に答える